初识数据结构

叶鹏　沈晓恬

只见菩提老祖大袖轻挥，悟空眼前的场景顿时变化，像是来到一处荒山。只见十几米远的地方有一块巨石。有个小妖从岩石后蹦出。那小妖手握一根骨棒，嗷嗷叫着向悟空冲来。悟空默运火眼金睛，见小妖身后隐约有层黑雾，雾中凝结出一道题目：“1+1=？”

悟空想起菩提老祖的教导，默默定义一个变量a，并将1+1赋值给此变量，随后调用print（a）函数将结果輸出。

[a=1+1

print（a） ]

随着数字2在天地间闪现，那小妖顿时如遭雷击，瞬间被打得灰飞烟灭。

悟空心想，这还挺简单的嘛，有这个程序，加法类型的小妖是来多少灭多少。

“悟空，”菩提老祖打断悟空的思路，将他的念头拉回来，“Python和其他一些语言不同，它使用缩进来表示代码块，不需要使用大括号{}。缩进的空格数是可变的，但同一代码块的语句，必须包含相同的缩进空格数。通常每一行包含一条Python语句，语句结尾直接换行，不需要加分号。”

“另外，代码中可以添加一些说明性文字，称为注释，Python中的单行注释以#开头，多行可以用多个#号，也可以用'''或者"""。注释不会被执行，只是方便人们阅读代码。”

[# 第一个注释

# 第二个注释

'''

第三个注释

第四个注释

'''

"""

第五个注释

第六个注释

"""

print （"Hello， Python！"） ]

悟空点头表示记下，这时的猴子已经算是入门了。

内存和数据结构

悟空默运火眼金睛，内视己身，发现自己的内存单元密密麻麻，不太数得清楚，便好奇地问菩提老祖：“师父，我现在到底有多少个内存单元呢？”

菩提老祖回答：“内存的最小单位叫作字节，西方的叫法是byte。你现在有32GB，大约320亿个字节。”

悟空脱口而出：“俺滴个乖乖，320亿，居然这么多。”

菩提老祖发出一阵笑声，“你这个没见识的猢狲，零壹天尊的内存至少是NB级别的，1NB=1024BB，1BB=1024YB，1YB=1024ZB，1ZB=1024EB，1EB=1024PB，1PB=1024TB，1TB=1024

GB，1GB=1024MB，1MB=1024KB，1KB=

1024Byte，1Byte=8bit。bit是内存中的最小单位，称为位。每位中只能存放0或1这两个值之一。”

悟空心里大概合计了下，暗道：“1NB大约等于十万亿亿GB，差距有点大。怪不得这单位就叫NB。”

说着，菩提老祖又挥了挥袖子。下一刻，悟空回转到之前的禅房中。菩提老祖继续说道：“你才刚刚上路。”

不服输的猴子想到只要自己的内存翻倍80次就能赶上零壹天尊，顿时觉得前途一片光明。

“为了应付更复杂的情况，你内存中的数据，需要进行组织，在此界，我们将数据的组织形式和存储方法称为数据结构。常用的数据结构主要包括线性结构和非线性结构，非线性结构中又包含树结构和图结构。”

线性结构

线性结构是最基本也是最简单的一种数据结构，它是由若干个数据元素构成的有限序列。

线性结构的特征是：

[1.必定存在唯一的一个第一个元素

2.必定存在唯一的一个最后的元素

3.除最后元素外，其他数据元素都有唯一的后继元素

4.除第一个元素外，其他元素都有唯一的前驱元素 ]

线性结构按不同的物理存储方式可分成顺序表和链表。

顺序表在内存中连续存储数据。链表除了存储数据，还包含指针，指针记录了下一块数据在内存中的位置（地址）。

“懂了！”悟空兴奋地大叫。

菩提老祖对悟空说：“既然你已经懂了，那么我来考考你。你替我构建一个结构，并且要让这个结构实现下面的功能，越先进入这个结构的数据，越后才能被取出，这种结构我们称之为栈。”

在程序中，我们通常只记录某一个数据结构的开始地址，而要取得这个结构中任何一个数据时，我们需要通过一些方法来计算目标数据的地址。

要建立一个栈，其实就是实现两个方法：push（进栈）和pop（出栈）。push方法是将新的值放到栈结构的顶部，pop方法将获得该结构顶部元素的值。

悟空心想，我可以使用一个顺序表来存储变量，同时使用一个栈指针来表示栈结构顶部元素的位置。在push时，指针加1，然后把新的值存在新的顶部位置。在pop时，根据指针，得到顶部元素的值，然后位置减1。

核心算法如下：

[def  push（i）：

global n

if n>=10：

print （"无法压栈"）

return err

stack[n]=i

n+=1

def  pop（）：

global n

if n<1：

print （"无法出栈"）

return err

# 返回栈顶的元素

n-=1

return stack[n]

]

悟空建立栈之后，问菩提老祖：“师父，既然有一种结构是先进后出的，那么是不是还有一种结构是先进先出的呢？”

（入队列叫enqueue，出队列叫dequeue）

“不错！” 菩提老祖的声音中透出赞赏的意味。

“这种结构叫作队列。悟空，那么你觉得队列这种结构，应该用数组还是链表来实现呢？”

悟空挠挠脑袋，说道：“应该还是用链表来实现更好一些吧？之前我们讲到数组和链表优缺点的时候，提到一系列属性……所以更加适合链表吧？”

菩提老祖点点头：“以后你有机会，也试着去实现一下吧！”

所以基本来说，从存储形式来看，线性结构可以分为顺序表和链表;而从逻辑功能来看，可以分为堆栈和队列。

非线性结构

悟空不愧是灵明石猴出生，学起东西来确实有举一反三的能耐。他继续向菩提老祖发问：“师父，不管是栈还是队列，都是一个接一个下来的，是否有更复杂一点的结构呢？我在看管蟠桃园的时候，见那些蟠桃树，都是枝枝杈杈，甚是复杂。”

菩提老祖哈哈大笑：“你这猴头，还是忘不了王母娘娘的蟠桃！此间确实有一种名为树的结构，对你非常有用。来来来，我们再来研讨一番。”

在现实世界中，有些复杂的情况，线性结构有时难以胜任。一些数据之间，存在着一对多的关系，这就构成了所谓的树状结构，简称树。

与线性结构不同，树采用非线性结构组织数据。

直观地看，树结构组织起来的数据应该有层次关系。我们真实的世界中，这类特性的数据应用十分广泛。

用形式化的语言描述，树是由n个结点（n≥0）组成的有穷集合。在任意一棵非空树中，有且仅有一个称为根（root）的结点;当n>1时，其余的结点分为m个互不相交的有限集合（m>0），T1，T2…Tm。其中，每個集合本身又是一棵树，称为根的子树（subtree）。

树结构的物理存储形式很多，最简单的一种被称为多重链表。在多重链表中，每个结点由一个数据域和若干指针域组成，其中，每个指针指向该结点的一个子结点。

“这零壹之道真是了不起啊！”悟空由衷地赞叹道，“那么还有更厉害的结构吗？”

“还有一种更复杂的结构，被称为图。”

“图？这名字一听就很厉害啊，如同太上老君的太极图、通天教主的诛仙阵图，都是能镇压大教气运的宝贝。”悟空心道。

从之前的描述中，我们可以发现线性结构是一种前后关系，树结构是一种层次关系，各个子树互不相交。而图结构中，任何两个数据元素之间都可能存在关系。图（Graph）是由顶点的非空有限集合V（由n>0个顶点组成），与边的集合E（顶点之间的关系）所构成。如果图G中每一条边都没有方向，称为无向图;若有方向，则称为有向图。

最常见的存储方法有两种：邻接矩阵的存储方法和邻接表的存储方法。

邻接矩阵利用两个数组来存储一个图，一个一维数组表示图的各个顶点，一个二维数组表示顶点间的关系。

邻接表利用数组和链表来存储一个图。使用一个一维数组表示图的各个顶点，每个顶点有一个对应的链表，用来表示由这个顶点发出的边。对于边数比较少的图而言，更适合用邻接表的存储结构。

讲完图的概念后，菩提老祖又传授了悟空几个基本的小法术，比如如何飞行、如何变化等。悟空默默记在心头。

说完这些，菩提老祖道：“我在此界的时间有限，对于零壹之道的了解也已经基本传授于你，剩下就靠你自己了。唐三藏一干人等目前身陷排序塔中，你速去解救众人。日后你重回四大部洲，我们依然保持原来的关系吧！”说罢，身形如同青烟一般，缓缓消逝。

悟空大喊：“师父！师父！”

不出所料，他的声音回荡在这房间里，无人应答。悟空心想，当务之急，是将取经组众人解救，然后从这零壹界中脱身。

扫一扫，有视频课哦！学Python算法，看西游漫记