数据结构基础

1、第 6 章数据结构基础【教学内容相关章节】6.1 栈和队列6.2链表6.3二叉树6.4图【教学目标 】（ 1）熟练掌握栈和队列及其实现；（ 2）了解双向链表及其实现；（ 3）掌握对比测试的方法；（ 4）掌握随机数据生成方法；（ 5）掌握完全二叉树的数组实现；（ 6）了解动态内存分配和释放方法及其注意事项；（ 7）掌握二叉树的链式表示法；（ 8）掌握二叉树的先序、后序和中序遍历和层次遍历；（ 9）掌握图的 DFS及连通块计数；（ 10）掌握图的 BFS及最短路的输出；（ 11）掌握拓扑排序算法；（ 12）掌握欧拉回路算法。【教学要求 】掌握栈和队列及其实现； 掌握对比测试的方法； 掌握随机数据生

2、成方法； 掌握完全二叉树的数组实现和链式表示法；掌握二叉树的先序、后序和中序遍历和层次遍历；掌握图的DFS和 BFS遍历；掌握拓扑排序算法；掌握欧拉回路算法。【教学内容提要】本章介绍基础数据结构，包括线性表、二叉树和图。有两种特殊的线性表：栈和队列。对于树型结构主要讨论二叉树， 还有二叉树的先序、 中序和后序的遍历方式。 对于图主要讨论图的 DFS 和 BFS 的遍历方法。 这些内容是很多高级内容的基础。 如果数据基础没有打好，很难设计正确、高效的算法。【教学重点、难点】教学重点：（ 1）掌握栈和队列及其实现；（ 2）掌握对比测试的方法；（ 3）掌握随机数据生成方法；（ 4）掌握完全二叉树的数

3、组实现和链式表示法；（ 5）掌握二叉树的先序、后序和中序遍历和层次遍历；（ 6）掌握图的 DFS和 BFS遍历；（ 7）掌握拓扑排序算法和欧拉回路算法。教学难点：（ 1）掌握完全二叉树的数组实现和链式表示法；（ 2）掌握二叉树的先序、后序和中序遍历和层次遍历；（ 3）掌握图的 DFS和 BFS遍历；（ 4）掌握拓扑排序算法和欧拉回路算法。【课时安排（共 9 学时） 】6.1 栈和队列6.2链表6.3二叉树6.4图（1 学时）6.1栈和队列线性表是“所有元素排成一行”的数据结构。 除了第一个元素之外，所有元素都有一个“前一个元素” ；除了最后一个元素外，所有元素都有“后一个元素”。线性结构是重要

4、的算法和数据结构的基础。下面介绍两种特殊的线性表：栈和队列。6.1.1卡片游戏桌上有叠牌，从第一张牌（即位于顶面的牌）开始从上往下依次编号为1 n。当至少还剩两张牌时进行以下操作：把第一张牌扔掉，然后把新的第一张放一整叠牌的最后。输入n，输出每次扔掉的牌，以及最后剩下的牌。样例输入： 7样例输出： 1357426【分析】本题中牌像在排队。每次从排头拿到两个，其中第二个再次排到尾部。这种数据结构称为队列。在数据结构称为FIFO（ First in First out，先进先出）表。用一个数组queue 来实现这个队列，可设两个指针front和 rear 。完整的程序如下：#include con

5、st int MAXN = 50;int queueMAXN;int main() int n, front, rear;scanf(%d, &n);for(int i = 0; i n; i+) queuei = i+1; /front = 0;/rear = n;/while(front rear) /printf(%d , queuefront+);/queuerear+ = queuefront+;/初始化队列队首元素的位置队尾元素的后一个位置当队列非空输出并抛弃队首元素队首元素转移到队尾return 0;注意： 上面的程序有bug。如果在最后把rear的值打印出来，rear比 n 大

6、。即在程序运行的后期， queuerear+=queuefront+读写了非法内存。也可以采取将数组空间开大些，或采取一种称为循环队列的技术，重用已出队元素占用的空间。C+提供了一种更加简单的处理方式STL队列。下面是代码：#include #include using namespace std;queue q;int main() int n, front, rear;scanf(%d, &n);for(int i = 0; i n; i+) q.push(i+1); /while(!q.empty() /printf(%d , q.front();/q.pop();/q.push(q.f

7、ront();/q.pop();/初始化队列当队列非空抛弃队首元素把队首元素加入队尾抛弃队首元素return 0;上面的程序的可读性大大增强了，体现在“queue”、“ front”见名知义的命名，使用了C+ STL。除此之外，上面的代码还有两个附加的好处。首先，不需要事先知道n 的大小；其次，可以少用两个变量front和 rear 。减少魔术数（magic number ）和变量个数都是提高代码可读性、减少错误可能性的重要手段。说明：（ 1）在 ACM竞赛中，需要用到数组、字符串、队列、堆栈、链表、平衡二叉检索树等数据结构和排序、搜索等算法，以提高程序的时间、空间运行效率，这些数据结构，如果

8、需要手工来编写，那是相当麻烦的事情。（ 2） ANSI C+中包含了一个 C+ STL（Standard Template Library ），即 C+标准模板库，又称为 C+泛型库，它在 std 命名空间中定义了常用的数据结构和算法，使用起来十分方便。（ 3） C+ STL 组件STL 组件三种类型的组件：容器、迭代器和算法，它们都支持泛型程序设计标准。容器主要有两类：顺序容器和关联容器。顺序容器（ vector 、list、queue、string等）一系列元素的有序集合。关联容器 （ set 、multiset、map和 mulimap ）包含查找元素的键值。迭代器的作用是遍历容器。ST

9、L 算法库包含四类算法：排序算法、不可变序算法、变序性算法和数值算法。（ 4） queue 队列容器queue 队列容器是一个先进先出（First In First Out， FIFO）线性存储表，元素的插入只能在队尾、元素的删除只能在队首。使用 queue 需要声明头文件包含语句“#include ”， queue 文件在 C:ProgramFilesMicrosoft Visual StudioVC98Include文件夹里。queue 队列的操作有入队push() （即插入元素） 、出队元素front()、读取队尾元素back() 、判断队列是否为空pop() （即删除元素） 、读取队首

10、empty() 和队列当前元素的数目size()。下面给出一个程序来说明queue队列的使用方法。#include #include using namespace std;int main() / 定义队列，元素类型是整型 queue q;/ 入队，即插入元素 q.push(1); q.push(2); q.push(3);q.push(9);/ 返回队列元素数量coutq.size()endl;/ 队列是否为空，是空，则返回逻辑真，否则返回逻辑假coutq.empty()endl;/ 读取队首元素coutq.front()endl;/ 读取队尾元素coutq.back()endl;/ 所有

11、元素出列（删除所有元素）while(q.empty()!=true) coutq.front() ;/ 队首元素出队（删除队首元素）q.pop();/ 回车换行coutendl;return 0;运行结果：401912396.1.2铁轨某城市有一个火车站，铁轨铺设 如图 6-1 所示 。有 n 节车厢从A 方向驶入车站， 按进站顺序编号为1 n。你的任务是让它们按照某种特定的顺序进入B 方向的铁轨并驶出车站。为了重组车厢，你可以借助中转站C。这是一个可以停放任意多节车厢的车站，但由于末端封顶，驶入C的车厢必须按照相反的顺序驶出C。对于每个车厢，一旦从A 移入 C，就不能再回到 A 了；一旦从C

12、 移入 B，就不能回到C 了。换句话说，在任意时刻，只有两种选择：A C 和 CB。图6-1铁轨样例输入：5123455541236654321样例输出：YesNoYes【分析】在中转站 C 中，车厢符合后进先出的原则，称为栈，即由于它只有一端生成，实现栈时只需要一个数组stack完整的程序如下：LIFO （ Last In FirstOut ）表。和栈顶指针（始终指向栈顶元素）。#include const int MAXN = 1000 + 10;int n, targetMAXN;int main() while(scanf(%d, &n) = 1) int stackMAXN, top

13、 = 0;int A = 1, B = 1;for(int i = 1; i = n; i+)scanf(%d, &targeti);int ok = 1;while(B = n) if(A = targetB) A+; B+; else if(top & stacktop = targetB) top-; B+; else if(A = n) stack+top = A+;else ok = 0; break; printf(%sn, ok ? Yes : No);return 0;说明： 为了方便起见，使用的数组下标均从 1 开始。例如，第一个车厢的编号，而 stack1 是栈底元素（这样

14、，栈空当且仅当target1是指目标序列中top=0 ）。下面给出 STL 栈来实现的程序：#include #include using namespace std;const int MAXN = 1000 + 10;int n, targetMAXN;int main() while(scanf(%d, &n) = 1) stack s;int A = 1, B = 1;for(int i = 1; i = n; i+)scanf(%d, &targeti);int ok = 1;while(B = n) if(A = targetB) A+; B+; else if(!s.empty(

15、) & s.top() = targetB) s.pop(); B+; else if(A = n) s.push(A+);else ok = 0; break; printf(%sn, ok ? Yes : No);return 0;说明：（ 1） stack栈容器是一种C+ STL中的容器，它是一个后进先出（Last In First（ Stack Top），而另一端称为栈底（ Stack Bottom ）。插入元素称为入栈（ Push），元素的删除则称为出栈（ Pop）。（ 2）要使用 stack ，必须声明头文件包含语句“ #include ”。stack 文件在 C:Program

16、FilesMicrosoft Visual StudioVC98Include文件夹中。（ 3）栈只提供入栈、出栈、栈顶元素访问和判断是否为空等几种方法。采用法将元素入栈；采用pop() 方法出栈；采用top() 方法访问栈顶元素；采用断栈是否为空，如果为空，则返回逻辑真，否则返回逻假。当然，可以采用回当前栈中有几个元素。下面的程序是对栈各种方法的示例：push() 方empty() 方法判size()方法返#include #include using namespace std;int main() / 定义栈 s，其元素类型是整型 stack s;/ 元素入栈，即插入元素 s.push(

17、1);s.push(2);s.push(3);s.push(9);/ 读取栈顶元素 couts.top()endl;/ 返回栈元素数量 couts.size()endl;/ 判断栈是否为空 couts.empty()endl;/ 所有元素出栈（删除所有元素）while(s.empty()!=true) /栈非空couts.top() ;/读取栈顶元素s.pop();/出栈（即删除栈顶元素）/ 回车换行coutendl;return 0;运行结果：940993216.2链表在多数情况下， 线性表都用它的顺序存储结构数组很轻松实现，但对有些问题有时用它的链式存储结构链表更好。6.2.1初步分析例

18、6-1移动小球。你有一些小球，从左到右依次编号为1,2,3,n ，如图 6-2 所示 。图 6-2链表的初始状态可以执行两种指令。其中，A X Y 表法把小球X 移动到小球Y 左边， B X Y 表示把小球X 移动到小球Y 右边。指令保证合法，即X 不等于 Y。例如，在初始状态下执行A 1 4后，小球被移动小球4 的左边， 如图 6-3 所示。图 6-3一次操作后的链表状态如果再执行B 3 5 ，结点 3 将会移到5 的右边， 如图 6-4 的所示 。图 6-4两次操作后的链表状态输入小球个数n，指令条数m和 n 条指令，从左到右输出最后的序列。注意，n 可能高达 500000，而 m可能高达

19、 100000。样例输入：6 2 A 1 4B 3 5样例输出：214536【分析】各个小球在逻辑上是相邻的，因此可考虑把它们放在一个数组A 中，所以完整的程序如下：#include const int MAXN = 1000;int n, AMAXN;int find(int X) for(int i = 1; i = n; i+)if(Ai = X) return i;return 0;void shift_circular_left(int a, int b) int t = Aa;for(int i = a; i a; i-) Ai = Ai-1;Aa = t;int main() i

20、nt m, X, Y, p, q;char type9;scanf(%d%d, &n, &m);for(int i = 1; i = n; i+)/Ai = i;for(int i = 0; i p) shift_circular_left(p, q-1);else shift_circular_right(q, p);/Ap到 Aq-1 往左循环移动/Aq到 Ap 往右循环移动else if(q p) shift_circular_left(p, q); else shift_circular_right(q+1, p);/Ap/Aq+1到 Aq 往左循环移动到 Ap 往右循环移动for(i

21、nt i = 1; i = n; i+)printf(%d , Ai);printf(n);return 0;对于上面的程序， 当数据量很大时，代码是否会超时。 一般来说， 可以用两种方法判断：测试和分析。计时测试的方法在前面已讲过，它的优点是原理简单、可操作性强， 缺点在于必须事先程序写好包括主程序和测试数据生成器。如果算法非常复杂，这是相当花时间的。另一种方法是写程序之前进行算法分析，估算时间效率， 这种方法在第8 章会详细分析。不过现在可以直观分析一下：如果反复执行B 1 n 和 A 1 2 ，每次都移动几乎所有元素。元素个数和指令条数都那么大，移动总次数将是相当可观的。6.2.2链式结

22、构第二种方法是强调小球之间的相对顺序，而非绝对顺序。 用 lefti和 righti分别表示编号为i的小球左边和右边的小球编号（如果是0，表示不存在） ，则在移动过程中可以分成两个步骤：把X 移出序列；把X 重新插入序列。第一步让leftX和 rightX相互连接即可 ，如图6-5 所示。 注意，其他所有的left和 right都不会变化。图6-5在链表中删除结点第二步类似。对于A 指令，需要修改leftY的right值和Y 的left值，如图6-6所示。图 6-6在链表中插入结点（情况A）而对于B 指令，需要修改Y 的right值和rightY的left的值， 如图6-7所示。图 6-7在链

23、表中插入结点（情况B）不管在哪种情况下，最后都需要修改X 自己的 left和 right。对于特殊情况下，对于最左的小球X，它的 leftX的值为0，但可以假想最左的小球左边有一个编号为0 的虚拟的小球。那么对最右的小球的右边的虚拟小球编号为n+1。核心的代码如下：scanf(%s%d%d, type, &X, &Y);link(leftX, rightX);if(type0 = A) link(leftY, X); /这一行和下一行不能搞反link(X, Y);else link(X, rightY); /这一行和下一行不能搞反link(Y, X);函数 link(X,Y)的作用是赋值rig

24、htX=Y，然后 leftY=X。完整的程序如下：#include const int MAXN = 1000;int n, leftMAXN, rightMAXN;void link(int X, int Y) rightX = Y; leftY = X;int main() int m, X, Y;char type9;scanf(%d%d, &n, &m);for(int i = 1; i = n; i+) lefti = i-1; righti = i+1;for(int i = 0; i m; i+) scanf(%s%d%d, &type, &X, &Y);link(leftX,

25、rightX);if(type0 = A) link(leftY, X);/这一行和下一行不能搞反link(X, Y);else link(X, rightY);/这一行和下一行不能搞反link(Y, X);for(int X = right0; X != n+1; X = rightX)printf(%d , X);printf(n);return 0;6.2.3对比测试对于写好的程序， 可能会花费较长的时间进行调试，所以要具备一定的调试和测试能力。测试的任务就是检查一份代码是否正确。 如果找到了错误， 最好还能提供一个让它错误的数据。有了错误数据之后，接下来的任务便是调试：找出出错的原因。

26、如果找到了错，最好把它改对至少对于刚才的错误数据能得到正确的结果。改对一组数据之后， 可能还有其他错误， 因此需要进一步测试； 即使以前曾经正确的数据，也可能因为多次改动之后反而变错了，需要再次调试。总之，在编码结束后，为确保程序的正确性，测试和调试往往要交替进行。确保代码正确的方法是： 再找一份完成同样功能的代码与之对比， 用它来和这个新程序“对答案”（俗称对拍） 。对比测试首先需要数据，而且是大量数据。为此，需要编写数据生成器，完整的代码如下：#include #include /rand()#include /time()和 srand()需要需要int n = 100, m = 100

27、000;double random() / 生成 0,1 return (double)rand() / RAND_MAX;之间的均匀随机数int random(int m) /生成 0,m-1return (int)(random() * (m-1) + 0.5);之间的均匀随机数int main() srand(time(NULL);/利用系统时间，初始化随机数种子printf(%d %dn, n, m);for(int i = 0; i m; i+) if(rand() % 2 = 0) printf(A); else printf(B); /int X, Y;for(;) X = ra

28、ndom(n)+1;Y = random(n)+1;if(X != Y)break; /只有 X 和 Y 不相等时才是合法的随机指令种类printf( %d %dn, X, Y);return 0;核心函数是stdlib.h中的 rand() ，它生成一个闭区间0,RAND_MAX的均匀随机整数 （均15在不同的环境下的值可能不同。严格地说，这个随机数是“伪随机数”，因为它也是由数学公式计算出来的。6.2.4随机数发生器上面的程序使用了rand()函数和srand()函数，下面就这个两个函数进行说明。1 rand()函数rand() 函数的主要功能是产生随机数。（ 1）表头文件： #inclu

29、de （ 2）函数原型： int rand(void)（ 3）函数说明rand （）函数的内部实现是线性同余法的，它不是真的随机数，只不过是因为其周期特别长，所以在一定的范围里可看成是随机的，rand() 会返回一随机数， 范围在 0 至 RAND_MAX区间。在调用此函数产生随机数前，必须先利用srand()设好随机数种子，如果未设随机数种子， rand() 在调用时会自动设随机数种子为1（即调用srand(1)）， rand() 产生的是假随机数字，每次执行是相同的，若要不同，以不同的值来初始化它，初始化函数是srand()。（ 4）返回值返回值是 0 至 RAND_MAX之间的随机整数值

30、，RAND_MAX的范围最少是32767 之间（int ），取双字节（ 16 位数）。若用 unsigned int双字节是65535，四字节是4294967295 的整数范围， 0 RAND_MAX每个数字被选中的机率是相同的。提示 6-1 ： stdlib.h中的 rand() 生成闭区间 0,RAND_MAX内均匀分布的随机整数，其中 RAND_MAX至少为 32767。如果生成更大的随机整数，在精度要求不太高的情况下可以用 rand() 的结果“放大”得到。说明： 用“ int x=1+rand()%n; ”来生成 1,n 之间的随机数这种方法是不可取的，比较好的做法是： j=1+(i

31、nt)(n*rand()/(RAND_MAX+1.0);2 srand()函数产生一个 1,n之间的随机数。srand()函数的功能是设置随机数种子。（ 1）函数原型： void srand(unsigned int seed);（ 2）函数说明srand()函数用来设置rand() 产生随机数时的随机数种子。参数常可以利用getpid()（即取目前进程的进程识别码）或time(NULL)seed 必须是整数，通的返回值来当做seed。time()函数的功能是返回从1970/01/01到现在的秒数。如果每次seed 都设相同值，rand() 所产生的随机数值每次就会一样。由于每一次运行程序的时

32、间是不同，time(NULL) 函数的返回值也不同，即种子不同， 所以产生的随机数也不同。提示 6-2 ：stdlib.h中的 srand()函数初始化随机数种子。如果需要程序每次执行是使用一个不同的种子，可以用time.h中的 time(NULL) 为参数调用srand 。一般来说，只在程序执行的开头调用一次srand 。“同一套随机数”可能是好事也可能是坏事。例如， 若要反复测试程序对不同随机数据的响应， 需要每次得到的随机数不同，就可用当前时间time(NULL) 作为参数调用srand 。如果程序是由操作系统自动批量执行的，可能因为每次运行时间过短，导致在相邻若干次执行时 time 的

33、返回值全部相同，一个解决办法是在测试程序的主函数中设置一个循环，做足够多次测试后退出。另一方面， 如果发现某程序对于一组随机数据出错，就需要在测试时 “重视” 这组数据。这时，“每次相同的随机序”就显得十分重要了。注意，不同的编译器计算随机数的方法可能不同。如果是不同编译器编译出来的程序，即使是相同的参数调用srand()，也可能得到不同的随机序列。最后，可以反复执行下面的操作：生成随机数据， 分别执行两个程序，比较它们的结果。合理地使用操作系统提供的脚本功能，可以自动完成对比测试。最后如果发现让两个程序答案不一致的数据， 最好别急着对它进行调试。 可以尝试着减少数据生成器中的 n 和 m，试

34、图找到一组尽量简单的错误数据。一般来说，数据越简单，越容易调试。如果发现只有很大的数据才会出错，通常意味着程序在处理极限数据方面有问题。对于这些技巧，平时要多积累。6.3 二叉 树二叉树（ BinaryTree ）的递归定义如下：二叉树要么为空，要么由根结点（root ）、左子树（ left subtree）和右子树（ right subtree）组成，而左子树和右子树分别是一棵二叉树。注意，在计算机中，树一般是“倒置”的根在上，叶子在下。6.3.1小球下落有一棵二叉树，最大深度为D，且所有叶子的深度都相同。所有结点从上到下从左到右编号为 1,2,3, ,2 D-1。在结点1 处放一个小球，它

35、会往下落。每个内结点上都有一个开关，初始全部关闭， 当每次有小球落到一个开关上时，它的状态都会改变。 当小球到达一个内结点时，如果该结点上的开关关闭，则往左走，否则往右走，直到走到叶子结点，如图 6-8所示 。图 6-8 所有叶子深度相同的二叉树一些小球从结点1 处依次开始下落，最后一个小球将全落到哪里呢？输入叶子深度D和小球个数 I ，输出第 I 个小球最后所在的叶子编号。假设I 不超过整棵树的叶子个数。D 20。输入最多包含 1000 组数据。样例输入：4 23 410 12 28 12816 12345样例输出：127512325536358【分析】对于一个结点的k，它的左儿子、右儿子的

36、编号分别是2k 和 2k+1。可以写出如下的模拟程序：#include#includeconst int MAXD = 20;MAXDint s1MAXD;/最大结点个数为2-1int main() int D, I;while(scanf(%d%d, &D, &I) = 2) memset(s, 0, sizeof(s);/开关int k, n = (1D)-1;/n是最大结点编号for(int i = 0; i n) break;/已经落“出界”了printf(%dn, k/2);/“出界”之前的叶子编号return 0;说明： 这个程序和前面数组模拟小球移动的程序有一个共同的特点：运算晨

37、太大。由于每个小球会落在根结点上，因此前两个小球必然是一个在左子树，一个在右子树。一般地， 只需看小球编号的奇偶性，就能知道它是最终在哪棵子树中。对于那些落入根结点左子树的小球来说，只需知道该小球是第几个落在根的左子树里的，就可以知道它下一步往左还是往右。依此类推，直到小球落在叶子上。如果使用题目中给出的编号I ，则当 I 是奇数时，它往左走的第(I+1)/2个小球；当I是偶数时，它是往右走的第I/2个小球。所以给出模拟最后一个小球的路线：#includeint main() int D, I;while(scanf(%d%d, &D, &I) = 2) int k = 1;for(int i

38、 = 0; i have_value = 0; /显式的初始化为0，因为 malloc申请内存时并不把它清零u-left = u-right = NULL;/初始化时并没有左右儿子return u;提示 6-3 ：可以用 stdlib.h中的函数将返回一个指针。如果返回值为malloc函数申请空间。 向该函数传入所需空间的大小，NULL，说明空间不足，申请失败。说明：（ 1）malloc是 C+/C 语言的标准库函数，用于申请动态内存。函数malloc的原型如下：void* malloc(size_t size);所需的头文件是“#inlcude （ 2）用 malloc申请一块长度为”或“

39、#inlcude ”。lengh 的整型数组的内存，程序如下：int *p=(int *)mallo(sizeof(int)*length); 要注意两个要素： “类型转换”和“ sizeof ”。 malloc 函数返回值的类型是 void* ，所以调用 malloc 时要显式地进行类型转换，将 void* 转换成所需要的指针类型。 malloc 函数本身并不识别要申请的内存是什么类型，它只关心内存的总字节数。可以用 sizeof 运算符算出 int 、float 等数据类型的变量的确切字节数。用 malloc 来申请内存，应该用 if(p=NULL) 、if(p!=NULL) 来捕获异常来进行错误处理。接下来是在 read_input 中调用 addnode 函数。它按照移动序列行走，目标不存在时调用 newnode 来创建新结点。int failed;void addnode(int v, char* s) int n = strlen(s);Node* u = root;/从根结点开始往下走for(int i = 0; i left = NULL)u-left = newnode(); /结点不存在，建立新结点u