第6章_数据结构基础

jklee 贡献于2016-10-14

作者 yyw  创建于2010-03-31 09:25:00   修改者yyw  修改于2011-09-01 08:41:00字数25946

文档摘要:本章介绍基础数据结构,包括线性表、二叉树和图。有两种特殊的线性表:栈和队列。对于树型结构主要讨论二叉树,还有二叉树的先序、中序和后序的遍历方式。对于图主要讨论图的DFS和BFS的遍历方法。这些内容是很多高级内容的基础。如果数据基础没有打好,很难设计正确、高效的算法。
关键词:

第6章 数据结构基础 第6章 数据结构基础 【教学内容相关章节】 6.1栈和队列 6.2链表 6.3二叉树 6.4图 【教学目标】 (1)熟练掌握栈和队列及其实现; (2)了解双向链表及其实现; (3)掌握对比测试的方法; (4)掌握随机数据生成方法; (5)掌握完全二叉树的数组实现; (6)了解动态内存分配和释放方法及其注意事项; (7)掌握二叉树的链式表示法; (8)掌握二叉树的先序、后序和中序遍历和层次遍历; (9)掌握图的DFS及连通块计数; (10)掌握图的BFS及最短路的输出; (11)掌握拓扑排序算法; (12)掌握欧拉回路算法。 【教学要求】 掌握栈和队列及其实现;掌握对比测试的方法;掌握随机数据生成方法;掌握完全二叉树的数组实现和链式表示法;掌握二叉树的先序、后序和中序遍历和层次遍历;掌握图的DFS和BFS遍历;掌握拓扑排序算法;掌握欧拉回路算法。 【教学内容提要】 本章介绍基础数据结构,包括线性表、二叉树和图。有两种特殊的线性表:栈和队列。对于树型结构主要讨论二叉树,还有二叉树的先序、中序和后序的遍历方式。对于图主要讨论图的DFS和BFS的遍历方法。这些内容是很多高级内容的基础。如果数据基础没有打好,很难设计正确、高效的算法。 【教学重点、难点】 教学重点: (1)掌握栈和队列及其实现; (2)掌握对比测试的方法; (3)掌握随机数据生成方法; (4)掌握完全二叉树的数组实现和链式表示法; (5)掌握二叉树的先序、后序和中序遍历和层次遍历; (6)掌握图的DFS和BFS遍历; (7)掌握拓扑排序算法和欧拉回路算法。 教学难点: (1)掌握完全二叉树的数组实现和链式表示法; (2)掌握二叉树的先序、后序和中序遍历和层次遍历; (3)掌握图的DFS和BFS遍历; (4)掌握拓扑排序算法和欧拉回路算法。 【课时安排(共9学时)】 6.1栈和队列 6.2链表 6.3二叉树 6.4图 (1学时) 6.1 栈 和 队 列 第 页 第6章 数据结构基础 线性表是“所有元素排成一行”的数据结构。除了第一个元素之外,所有元素都有一个“前一个元素”;除了最后一个元素外,所有元素都有“后一个元素”。 线性结构是重要的算法和数据结构的基础。下面介绍两种特殊的线性表:栈和队列。 6.1.1 卡片游戏 桌上有叠牌,从第一张牌(即位于顶面的牌)开始从上往下依次编号为1~n。当至少还剩两张牌时进行以下操作:把第一张牌扔掉,然后把新的第一张放一整叠牌的最后。输入n,输出每次扔掉的牌,以及最后剩下的牌。 样例输入:7 样例输出:1 3 5 7 4 2 6 【分析】 本题中牌像在排队。每次从排头拿到两个,其中第二个再次排到尾部。这种数据结构称为队列。在数据结构称为FIFO(First in First out,先进先出)表。 用一个数组queue来实现这个队列,可设两个指针front和rear。 完整的程序如下: #include const int MAXN = 50; int queue[MAXN]; int main() { int n, front, rear; scanf("%d", &n); for(int i = 0; i < n; i++) queue[i] = i+1; //初始化队列 front = 0; //队首元素的位置 rear = n; //队尾元素的后一个位置 while(front < rear) { //当队列非空 printf("%d ", queue[front++]); //输出并抛弃队首元素 queue[rear++] = queue[front++]; //队首元素转移到队尾 } return 0; } 注意:上面的程序有bug。如果在最后把rear的值打印出来,rear比n大。即在程序运行的后期,queue[rear++]=queue[front++]读写了非法内存。也可以采取将数组空间开大些,或采取一种称为循环队列的技术,重用已出队元素占用的空间。 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.front()); //把队首元素加入队尾 q.pop(); //抛弃队首元素 } return 0; 第 页 第6章 数据结构基础 } 上面的程序的可读性大大增强了,体现在“queue”、“front”见名知义的命名,使用了C++ STL。除此之外,上面的代码还有两个附加的好处。首先,不需要事先知道n的大小;其次,可以少用两个变量front和rear。减少魔术数(magic number)和变量个数都是提高代码可读性、减少错误可能性的重要手段。 说明:(1)在ACM竞赛中,需要用到数组、字符串、队列、堆栈、链表、平衡二叉检索树等数据结构和排序、搜索等算法,以提高程序的时间、空间运行效率,这些数据结构,如果需要手工来编写,那是相当麻烦的事情。 (2)ANSI C++中包含了一个C++ STL(Standard Template Library),即C++标准模板库,又称为C++泛型库,它在std命名空间中定义了常用的数据结构和算法,使用起来十分方便。 (3)C++ STL组件 STL组件三种类型的组件:容器、迭代器和算法,它们都支持泛型程序设计标准。 容器主要有两类:顺序容器和关联容器。顺序容器(vector、list、queue、string等)一系列元素的有序集合。关联容器(set、multiset、map和mulimap)包含查找元素的键值。 迭代器的作用是遍历容器。 STL算法库包含四类算法:排序算法、不可变序算法、变序性算法和数值算法。 (4)queue队列容器 queue队列容器是一个先进先出(First In First Out,FIFO)线性存储表,元素的插入只能在队尾、元素的删除只能在队首。 使用queue需要声明头文件包含语句“#include ”,queue文件在C:\Program Files\Microsoft Visual Studio\VC98\Include文件夹里。 queue队列的操作有入队push()(即插入元素)、出队pop()(即删除元素)、读取队首元素front()、读取队尾元素back()、判断队列是否为空empty()和队列当前元素的数目size()。 下面给出一个程序来说明queue队列的使用方法。 #include #include using namespace std; int main() { //定义队列,元素类型是整型 queue q; //入队,即插入元素 q.push(1); q.push(2); q.push(3); q.push(9); //返回队列元素数量 cout< const int MAXN = 1000 + 10; int n, target[MAXN]; int main() { while(scanf("%d", &n) == 1) { int stack[MAXN], top = 0; int A = 1, B = 1; for(int i = 1; i <= n; i++) 第 页 第6章 数据结构基础 scanf("%d", &target[i]); int ok = 1; while(B <= n) { if(A == target[B]){ A++; B++; } else if(top && stack[top] == target[B]){ top--; B++; } else if(A <= n) stack[++top] = A++; else { ok = 0; break; } } printf("%s\n", ok ? "Yes" : "No"); } return 0; } 说明:为了方便起见,使用的数组下标均从1开始。例如,target[1]是指目标序列中第一个车厢的编号,而stack[1]是栈底元素(这样,栈空当且仅当top=0)。 下面给出STL栈来实现的程序: #include #include using namespace std; const int MAXN = 1000 + 10; int n, target[MAXN]; int main() { while(scanf("%d", &n) == 1) { stack s; int A = 1, B = 1; for(int i = 1; i <= n; i++) scanf("%d", &target[i]); int ok = 1; while(B <= n) { if(A == target[B]){ A++; B++; } else if(!s.empty() && s.top() == target[B]){ s.pop(); B++; } else if(A <= n) s.push(A++); else { ok = 0; break; } } printf("%s\n", ok ? "Yes" : "No"); } return 0; } 说明:(1)stack栈容器是一种C++ STL中的容器,它是一个后进先出(Last In First Out,LIFO)的线性表,插入和删除元素都只能在表的一端进行。插入元素的一端称为栈顶(Stack Top),而另一端称为栈底(Stack Bottom)。插入元素称为入栈(Push),元素的删除则称为出栈(Pop)。 (2)要使用stack,必须声明头文件包含语句“#include ”。stack文件在C:\ Program Files\Microsoft Visual Studio\VC98\Include文件夹中。 (3)栈只提供入栈、出栈、栈顶元素访问和判断是否为空等几种方法。采用push()方法将元素入栈;采用pop()方法出栈;采用top()方法访问栈顶元素;采用empty()方法判断栈是否为空,如果为空,则返回逻辑真,否则返回逻假。当然,可以采用size()方法返回当前栈中有几个元素。 下面的程序是对栈各种方法的示例: 第 页 第6章 数据结构基础 #include #include using namespace std; int main() { //定义栈s,其元素类型是整型 stack s; //元素入栈,即插入元素 s.push(1); s.push(2); s.push(3); s.push(9); //读取栈顶元素 cout< const int MAXN = 1000; int n, A[MAXN]; int find(int X) { for(int i = 1; i <= n; i++) if(A[i] == X) return i; return 0; } void shift_circular_left(int a, int b) { int t = A[a]; for(int i = a; i < b; i++) A[i] = A[i+1]; A[b] = t; } void shift_circular_right(int a, int b) { int t = A[b]; for(int i = b; i > a; i--) A[i] = A[i-1]; A[a] = t; } int main() { int m, X, Y, p, q; char type[9]; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) //初始化数组 A[i] = i; for(int i = 0; i < m; i++) { scanf("%s%d%d", type, &X, &Y); p = find(X); //查找X和Y在数组中的位置 q = find(Y); if(type[0] == 'A') { if(q > p) shift_circular_left(p, q-1); //A[p]到A[q-1]往左循环移动 else shift_circular_right(q, p); //A[q]到A[p]往右循环移动 } else { if(q > p) shift_circular_left(p, q); //A[p]到A[q]往左循环移动 else shift_circular_right(q+1, p); //A[q+1]到A[p]往右循环移动 } 第 页 第6章 数据结构基础 } for(int i = 1; i <= n; i++) printf("%d ", A[i]); printf("\n"); return 0; } 对于上面的程序,当数据量很大时,代码是否会超时。一般来说,可以用两种方法判断:测试和分析。 计时测试的方法在前面已讲过,它的优点是原理简单、可操作性强,缺点在于必须事先程序写好——包括主程序和测试数据生成器。如果算法非常复杂,这是相当花时间的。 另一种方法是写程序之前进行算法分析,估算时间效率,这种方法在第8章会详细分析。不过现在可以直观分析一下:如果反复执行B 1 n和A 1 2,每次都移动几乎所有元素。元素个数和指令条数都那么大,移动总次数将是相当可观的。 6.2.2 链式结构 第二种方法是强调小球之间的相对顺序,而非绝对顺序。用left[i]和right[i]分别表示编号为i的小球左边和右边的小球编号(如果是0,表示不存在),则在移动过程中可以分成两个步骤:把X移出序列;把X重新插入序列。 第一步让left[X]和right[X]相互连接即可,如图6-5所示。注意,其他所有的left和right都不会变化。 图6-5 在链表中删除结点 第二步类似。对于A指令,需要修改left[Y]的right值和Y的left值,如图6-6所示。 图6-6 在链表中插入结点(情况A) 而对于B指令,需要修改Y的right值和right[Y]的left的值,如图6-7所示。 图6-7 在链表中插入结点(情况B) 不管在哪种情况下,最后都需要修改X自己的left和right。对于特殊情况下,对于最左的小球X,它的left[X]的值为0,但可以假想最左的小球左边有一个编号为0的虚拟的小球。那么对最右的小球的右边的虚拟小球编号为n+1。核心的代码如下: scanf("%s%d%d", type, &X, &Y); link(left[X], right[X]); if(type[0] == 'A') { link(left[Y], X); //这一行和下一行不能搞反 link(X, Y); } else { link(X, right[Y]); //这一行和下一行不能搞反 link(Y, X); } 函数link(X,Y)的作用是赋值right[X]=Y,然后left[Y]=X。 完整的程序如下: #include const int MAXN = 1000; int n, left[MAXN], right[MAXN]; void link(int X, int Y) { right[X] = Y; left[Y] = X; } 第 页 第6章 数据结构基础 int main() { int m, X, Y; char type[9]; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) { left[i] = i-1; right[i] = i+1; } for(int i = 0; i < m; i++) { scanf("%s%d%d", &type, &X, &Y); link(left[X], right[X]); if(type[0] == 'A') { link(left[Y], X); //这一行和下一行不能搞反 link(X, Y); } else { link(X, right[Y]); //这一行和下一行不能搞反 link(Y, X); } } for(int X = right[0]; X != n+1; X = right[X]) printf("%d ", X); printf("\n"); return 0; } 6.2.3 对比测试 对于写好的程序,可能会花费较长的时间进行调试,所以要具备一定的调试和测试能力。 测试的任务就是检查一份代码是否正确。如果找到了错误,最好还能提供一个让它错误的数据。有了错误数据之后,接下来的任务便是调试:找出出错的原因。如果找到了错,最好把它改对——至少对于刚才的错误数据能得到正确的结果。 改对一组数据之后,可能还有其他错误,因此需要进一步测试;即使以前曾经正确的数据,也可能因为多次改动之后反而变错了,需要再次调试。总之,在编码结束后,为确保程序的正确性,测试和调试往往要交替进行。 确保代码正确的方法是:再找一份完成同样功能的代码与之对比,用它来和这个新程序“对答案”(俗称对拍)。 对比测试首先需要数据,而且是大量数据。为此,需要编写数据生成器,完整的代码如下: #include #include //rand()和srand()需要 #include //time()需要 int n = 100, m = 100000; double random() { //生成[0,1]之间的均匀随机数 return (double)rand() / RAND_MAX; } int random(int m) { //生成[0,m-1]之间的均匀随机数 return (int)(random() * (m-1) + 0.5); } int main() { srand(time(NULL)); //利用系统时间,初始化随机数种子 第 页 第6章 数据结构基础 printf("%d %d\n", n, m); for(int i = 0; i < m; i++) { if(rand() % 2 == 0) printf("A"); else printf("B"); //随机指令种类 int X, Y; for(;;) { X = random(n)+1; Y = random(n)+1; if(X != Y) break; //只有X和Y不相等时才是合法的 } printf(" %d %d\n", X, Y); } return 0; } 核心函数是stdlib.h中的rand(),它生成一个闭区间[0,RAND_MAX]的均匀随机整数(均匀的含义是:该区间内每个整数被产生的概率相同),其中RAND_MAX至少为32767(215-1),在不同的环境下的值可能不同。严格地说,这个随机数是“伪随机数”,因为它也是由数学公式计算出来的。 6.2.4 随机数发生器 上面的程序使用了rand()函数和srand()函数,下面就这个两个函数进行说明。 1.rand()函数 rand()函数的主要功能是产生随机数。 (1)表头文件:#include (2)函数原型:int rand(void) (3)函数说明 rand()函数的内部实现是线性同余法的,它不是真的随机数,只不过是因为其周期特别长,所以在一定的范围里可看成是随机的,rand()会返回一随机数,范围在0至RAND_MAX区间。在调用此函数产生随机数前,必须先利用srand()设好随机数种子,如果未设随机数种子,rand()在调用时会自动设随机数种子为1(即调用srand(1)),rand()产生的是假随机数字,每次执行是相同的,若要不同,以不同的值来初始化它,初始化函数是srand()。 (4)返回值 返回值是0至RAND_MAX之间的随机整数值,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+(int)(n*rand()/(RAND_MAX+1.0));产生一个[1,n]之间的随机数。 2.srand()函数 srand()函数的功能是设置随机数种子。 (1)函数原型:void srand(unsigned int seed); (2)函数说明 srand()函数用来设置rand()产生随机数时的随机数种子。参数seed必须是整数,通常可以利用getpid()(即取目前进程的进程识别码)或time(NULL)的返回值来当做seed。time()函数的功能是返回从1970/01/01到现在的秒数。 如果每次seed都设相同值,rand()所产生的随机数值每次就会一样。由于每一次运行程序的时间是不同,time(NULL)函数的返回值也不同,即种子不同,所以产生的随机数也不同。 第 页 第6章 数据结构基础 提示6-2:stdlib.h中的srand()函数初始化随机数种子。如果需要程序每次执行是使用一个不同的种子,可以用time.h中的time(NULL)为参数调用srand。一般来说,只在程序执行的开头调用一次srand。 “同一套随机数”可能是好事也可能是坏事。例如,若要反复测试程序对不同随机数据的响应,需要每次得到的随机数不同,就可用当前时间time(NULL)作为参数调用srand。如果程序是由操作系统自动批量执行的,可能因为每次运行时间过短,导致在相邻若干次执行时time的返回值全部相同,一个解决办法是在测试程序的主函数中设置一个循环,做足够多次测试后退出。 另一方面,如果发现某程序对于一组随机数据出错,就需要在测试时“重视”这组数据。这时,“每次相同的随机序”就显得十分重要了。注意,不同的编译器计算随机数的方法可能不同。如果是不同编译器编译出来的程序,即使是相同的参数调用srand(),也可能得到不同的随机序列。 最后,可以反复执行下面的操作:生成随机数据,分别执行两个程序,比较它们的结果。合理地使用操作系统提供的脚本功能,可以自动完成对比测试。 最后如果发现让两个程序答案不一致的数据,最好别急着对它进行调试。可以尝试着减少数据生成器中的n和m,试图找到一组尽量简单的错误数据。一般来说,数据越简单,越容易调试。如果发现只有很大的数据才会出错,通常意味着程序在处理极限数据方面有问题。对于这些技巧,平时要多积累。 6.3 二 叉 树 二叉树(Binary Tree)的递归定义如下:二叉树要么为空,要么由根结点(root)、左子树(left subtree)和右子树(right subtree)组成,而左子树和右子树分别是一棵二叉树。注意,在计算机中,树一般是“倒置”的——根在上,叶子在下。 6.3.1 小球下落 有一棵二叉树,最大深度为D,且所有叶子的深度都相同。所有结点从上到下从左到右编号为1,2,3,…,2D-1。在结点1处放一个小球,它会往下落。每个内结点上都有一个开关,初始全部关闭,当每次有小球落到一个开关上时,它的状态都会改变。当小球到达一个内结点时,如果该结点上的开关关闭,则往左走,否则往右走,直到走到叶子结点,如图6-8所示。 图6-8 所有叶子深度相同的二叉树 一些小球从结点1处依次开始下落,最后一个小球将全落到哪里呢?输入叶子深度D和小球个数I,输出第I个小球最后所在的叶子编号。假设I不超过整棵树的叶子个数。D≤20。输入最多包含1000组数据。 样例输入: 4 2 3 4 10 1 2 2 8 128 16 12345 样例输出: 12 7 512 3 255 36358 【分析】 第 页 第6章 数据结构基础 对于一个结点的k,它的左儿子、右儿子的编号分别是2k和2k+1。可以写出如下的模拟程序: #include #include const int MAXD = 20; int s[1< n) break; //已经落“出界”了 } } printf("%d\n", k/2); //“出界”之前的叶子编号 } return 0; } 说明:这个程序和前面数组模拟小球移动的程序有一个共同的特点:运算晨太大。 由于每个小球会落在根结点上,因此前两个小球必然是一个在左子树,一个在右子树。一般地,只需看小球编号的奇偶性,就能知道它是最终在哪棵子树中。对于那些落入根结点左子树的小球来说,只需知道该小球是第几个落在根的左子树里的,就可以知道它下一步往左还是往右。依此类推,直到小球落在叶子上。 如果使用题目中给出的编号I,则当I是奇数时,它往左走的第(I+1)/2个小球;当I是偶数时,它是往右走的第I/2个小球。所以给出模拟最后一个小球的路线: #include int main() { int D, I; while(scanf("%d%d", &D, &I) == 2) { int k = 1; for(int i = 0; i < D-1; i++) if(I%2) { k = k*2; I = (I+1)/2; } else { k = k*2+1; I /= 2; } printf("%d\n", k); } return 0; } 6.3.2 层次遍历 输入一棵二叉树,按从上到下、从左到右的顺序输出各个结点的值。每个结点都按照从根结点到它的移动序列给出(L表示左,R表示右)。在输入中,每个结点的左括号和右括号之间没有括号,相邻结点之间用一个空格隔开。每棵树的输入用一对空括号()结束(这对括号本身不代表一个结点),如图6-9所示。 图6-9 一棵二叉树 注意,如果从根到某个叶结点的路径上有的结点没有在输入中给出,或者给出了超过一次,应当输出-1。结点个数不超过256。 第 页 第6章 数据结构基础 样例输入: (11,LL)(7,LLL)(8,R)(5,)(4,L)(13,RL)(2,LLR)(1,RRR)(4,RR)() (3,L)(4,R)() 样例输出: 5 4 8 11 13 4 7 2 1 -1 【分析】 需要采用动态结构,根据需要建立新的结点,然后把它们组织成一棵树。首先,编写输入部分和主程序: char s[MAXN + 10]; //保存读入结点 int read_input() { failed = 0; remove_tree(root); root = newnode(); //创建根结点 for(;;) { if(scanf("%s", s) != 1) return 0; //整个输入结束 if(!strcmp(s, "()")) break; //读到结束标志,退出循环 int v; sscanf(&s[1], "%d", &v); //读入结点值 addnode(v, strchr(s, ',')+1); //查找逗号,然后插入结点 } return 1; } 从上述程序可知,不停输入结点,如果子读到空格号之前文件结束,则返回0。注意,两次用到了C语言中字符串的灵活性——可以把任意“指向字符的指针”看成是字符串,从该位置开始,直到字符“\0”。 接下来是二叉树的结点定义和操作。首先,需要定义一个称为Node的数据类型,并且对应整棵二叉树的树根root: //结点类型 typedef struct TNode{ int have_value; int v; //结点值 struct TNode *left, *right; //是否被赋值过 } Node; Node* root; 由于二叉树是递归定义的,它的左右儿子类型都是“指向结点类型的指针”。也就是说,如果结点的结构体体名称为TNode,则左右儿子的类型都是struct TNode *。 每次需要一个新的Node时,都要调用stdlib.h中的malloc函数申请内存,返回一个未初始化的空间。下面把申请新结点的操作封装到newnode函数中: Node* newnode() { Node* u = (Node*) malloc(sizeof(Node)); //申请动态内存 if(u != NULL) { //若申请成功 u->have_value = 0; //显式的初始化为0,因为malloc申请内存时并不把它清零 u->left = u->right = NULL; //初始化时并没有左右儿子 } return u; } 提示6-3:可以用stdlib.h中的malloc函数申请空间。向该函数传入所需空间的大小,函数将返回一个指针。如果返回值为NULL,说明空间不足,申请失败。 第 页 第6章 数据结构基础 说明:(1)malloc是C++/C语言的标准库函数,用于申请动态内存。函数malloc的原型如下: void* malloc(size_t size); 所需的头文件是“#inlcude ”或“#inlcude ”。 (2)用malloc申请一块长度为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 < n; i++) if(s[i] == 'L') { if(u->left == NULL) u->left = newnode(); //结点不存在,建立新结点 u = u->left; //往左走 } else if(s[i] == 'R') { if(u->right == NULL) u->right = newnode(); u = u->right; } //忽略其他情况,即最后那个多余的右括号 if(u->have_value) failed = 1; //已经赋过值,表明输入有误 u->v = v; u->have_value = 1; //别忘了做标记 } 由上面可知,输入和建树部分已经结束,接下来需要按照层次顺序遍历这棵树。使用一个队列来完成这个任务,初始时只有一个根结点,然后每次取出一个结点,就把它的左右儿子(如果有)放进队列。 int n = 0, ans[MAXN]; //结点数和输出序列 int bfs() { int front = 0, rear = 1; Node* q[MAXN]; q[0] = root; //初始时只有一个根结点 while(front < rear) { Node* u = q[front++]; if(!u->have_value) return 0; //有结点没有被赋值过,表明输入有误 ans[n++] = u->v; //增加到输出序列尾部 if(u->left != NULL) q[rear++] = u->left; //把左儿子(如果有)放进队列 if(u->right != NULL) q[rear++] = u->right; //把右儿子(如果有)放进队列 } return 1; //输入正确 } 说明:上面就是按层次顺序遍历整棵二叉树的bfs函数,这样的遍历二叉树的方法又称为宽度优先遍历(Breadth-First Search,BFS)。 第 页 第6章 数据结构基础 注意:(1)在输入一组新数据时,没有释放上一棵二叉树所申请的内存空间。一旦执行了root=newnode(),就再也不能访问到那些内存,尽管那些内存在物理上仍然存在。这种现象就是内存泄漏。 (2)内存泄漏(memory leak)就是申请了一块内存空间,使用完毕后没有释放掉。它的一般表现方式是程序运行时间越长,占用内存越多,最终用尽全部内存,整个系统崩溃。由程序申请的一块内存,且没有任何一个指针指向它,那么这块内存就泄露了。 下面释放一棵二叉树的代码,请在root=newnode()之前加一行remove_tree(root): void remove_tree(Node* u) { if(u == NULL) return; //提前判断比较稳妥 remove_tree(u->left); //递归释放左子树的空间 remove_tree(u->right); //递归释放右子树的空间 free(u); //释放u结点本身的内存 } 说明:(1)free函数是C++/C语言的标准库函数,用来释放程序动态申请的内存。其函数原型为: void free(void * memblock); 所需的头文件是“#inlcude ”或“#inlcude ”。 (2)只有当使用了动态内存申请函数malloc calloc realloc申请内存之后,p指针指向这块内存,才可以使用free(p)来释放之。如果p是NULL指针,那么函数free对p无论操作多少次都不会问题。如果p不是NULL指针,那么函数free对p连续操作两次就会导致程序运行时错误。切记,动态申请内存使用完后,一定要记得释放,否则会有内存泄露问题。 将上面各个函数综合起来,再加上主函数,就可以得到如下的完整程序: #include #include #include const int MAXN = 256; //结点类型 typedef struct TNode{ int have_value; int v; //结点值 struct TNode *left, *right; //是否被赋值过 } Node; Node* root; Node* newnode() { Node* u = (Node*) malloc(sizeof(Node)); //申请动态内存 if(u != NULL) { //若申请成功 u->have_value = 0; //显式的初始化为0,因为malloc申请内存时并不把它清零 u->left = u->right = NULL; //初始化时并没有左右儿子 } return u; } int failed; void addnode(int v, char* s) { int n = strlen(s); Node* u = root; //从根结点开始往下走 for(int i = 0; i < n; i++) 第 页 第6章 数据结构基础 if(s[i] == 'L') { if(u->left == NULL) u->left = newnode(); //结点不存在,建立新结点 u = u->left; //往左走 } else if(s[i] == 'R') { if(u->right == NULL) u->right = newnode(); u = u->right; } //忽略其他情况,即最后那个多余的右括号 if(u->have_value) failed = 1; //已经赋过值,表明输入有误 u->v = v; u->have_value = 1; //别忘了做标记 } void remove_tree(Node* u) { if(u == NULL) return; //提前判断比较稳妥 remove_tree(u->left); //递归释放左子树的空间 remove_tree(u->right); //递归释放右子树的空间 free(u); //释放u结点本身的内存 } char s[MAXN + 10]; //保存读入结点 int read_input() { failed = 0; remove_tree(root); root = newnode(); //创建根据结点 for(;;) { if(scanf("%s", s) != 1) return 0; //整个输入结束 if(!strcmp(s, "()")) break; //读到结束标志,退出循环 int v; sscanf(&s[1], "%d", &v); //读入结点值 addnode(v, strchr(s, ',')+1); //查找逗号,然后插入结点 } return 1; } int n = 0, ans[MAXN]; //结点数和输出序列 int bfs() { int front = 0, rear = 1; Node* q[MAXN]; q[0] = root; //初始时只有一个根结点 while(front < rear) { Node* u = q[front++]; if(!u->have_value) return 0; //有结点没有被赋值过,表明输入有误 ans[n++] = u->v; //增加到输出序列尾部 if(u->left != NULL) q[rear++] = u->left; //把左儿子(如果有)放进队列 if(u->right != NULL) q[rear++] = u->right; //把右儿子(如果有)放进队列 } return 1; //输入正确 } int main() { 第 页 第6章 数据结构基础 while(read_input()) { if(!bfs()) failed = 1; if(failed) printf("-1\n"); else { for(int i = 0; i < n; i++) printf("%d ", ans[i]); printf("\n"); } } return 0; } 给出指针版的程序,主要是与数组版的程序相比较。下面将指针完全去掉,改用数组版的程序。 首先,还是给每个结点编号,但不是按照从上到下从左到右的顺序,而是按照结点的生成顺序。用计数器cnt表示已存在的结点编号的最大值,因此newnode函数需在改成这样: const int root = 1; void newtree() { left[root] = right[root] = 0; cnt = root; } int newnode() { int u = ++cnt; left[u] = right[u] = 0; return u; } 上面的newtree()是用来代替前面的remove_tree(root)和root=newnode()两条语句:由于没有动态内存的申请和释放,只需要重置结点计数器和根结点的左右子树了。 接下来,把所有的Node*类型改为int型,然后把结点结构中的成员变量改成全局数组(例如,u->left和u->right分别改为left[u]和right[u]),除了char*外,整个程序就没有任何指针了。 在编程时尽量避免指针和动态内存,但仍然需要具体问题具体分析。例如,用指针直接访问比“数组+下标”的方式略快,因此有的竞赛选手喜欢用“结构体+指针”的方式处理动态数据结构,但在申请结点时仍然用“动态化静态”的思想,把newnode函数写成: Node* newnode(){ Node* u = &node[++cnt]; u->left = u->right = NULL; return u; } 其中,node是静态申请的结构体数组。 下面给出数组版的完整程序: #include #include #include const int MAXN = 256; const int root = 1; int cnt, vis[MAXN], val[MAXN], left[MAXN], right[MAXN]; void newtree() { left[root] = right[root] = 0; cnt = root; } int newnode() { int u = ++cnt; left[u] = right[u] = 0; return u; } int failed; void addnode(int v, char* s) { int n = strlen(s), u = root; for(int i = 0; i < n; i++) if(s[i] == 'L') { if(!left[u]) left[u] = newnode(); u = left[u]; } else if(s[i] == 'R') { if(!right[u]) right[u] = newnode(); u = right[u]; } if(vis[u]) failed = 1; val[u] = v; 第 页 第6章 数据结构基础 vis[u] = 1; } char s[MAXN + 10]; int read_input() { failed = 0; newtree(); for(;;) { if(scanf("%s", s) != 1) return 0; if(!strcmp(s, "()")) break; int v; sscanf(&s[1], "%d", &v); addnode(v, strchr(s, ',')+1); } return 1; } int n = 0, ans[MAXN]; int bfs() { int front = 0, rear = 1; int q[MAXN]; q[0] = root; while(front < rear) { int u = q[front++]; if(!vis[u]) return 0; ans[n++] = val[u]; if(left[u]) q[rear++] = left[u]; if(right[u]) q[rear++] = right[u]; } return 1; } int main() { while(read_input()) { if(!bfs()) failed = 1; if(failed) printf("-1\n"); else { for(int i = 0; i < n; i++) printf("%d ", ans[i]); printf("\n"); } } return 0; } 6.3.3 二叉树重建 对于二叉树T,可以递归定义它的先序遍历、中序遍历和后序遍历如下: PreOrder(T)=T的根结点+ PreOrder(T的左子树)+ PreOrder(T的右子树) InOrder(T)= InOrder(T的左子树)+T的根结点+InOrder(T的右子树) PostOrder(T)= PostOrder(T的左子树)+ PostOrder(T的右子树)+T的根结点 其中,加号表示字符串连接运算。例如,对于如图6-10所示的二叉树,先序遍历为DBACEGF,中序遍历为ABCDEFG。 第 页 第6章 数据结构基础 图6-10 另一棵二叉树 输入一棵二叉树的先序遍历和中序遍历序列,输出它的后序遍历序列。 样例输入: DBACEGF ABCDEFG BCAD CBAD 样例输出: ACBFGED CDAB #include #include const int MAXN = 30; void build(int n, char* s1, char* s2, char* s) { if(n <= 0) return; int p = strchr(s2, s1[0]) - s2; build(p, s1+1, s2, s); build(n-p-1, s1+p+1, s2+p+1, s+p); s[n-1] = s1[0]; } int main() { char s1[MAXN], s2[MAXN], ans[MAXN]; while(scanf("%s%s", s1, s2) == 2) { int n = strlen(s1); build(n, s1, s2, ans); ans[n] = '\0'; printf("%s\n", ans); } return 0; } 【分析】 先序遍历的第一个字符是根,因此只需在中序遍历中找到它,就知道左右子树的先序和后序遍历了。可以编写一个递归程序: void build(int n, char* s1, char* s2, char* s) { if(n <= 0) return; int p = strchr(s2, s1[0]) - s2; //找到根结点在中序遍历中位置 build(p, s1+1, s2, s); //递归构造左子树的后序遍历 build(n-p-1, s1+p+1, s2+p+1, s+p); //递归构造右子树的后序遍历 s[n-1] = s1[0]; //把根结点添加到最后 } 它的作用是根据一个长度为n的先序序列s1和中序序列s2,构造一个长度为n的后序序列。注意,再次用到了C语言中字符串的储存方式,并灵活运用字符指针的加减法简化了程序。 下面给出完整的程序如下: #include #include const int MAXN = 30; void build(int n, char* s1, char* s2, char* s) { 第 页 第6章 数据结构基础 if(n <= 0) return; int p = strchr(s2, s1[0]) - s2; //找到根结点在中序遍历中位置 build(p, s1+1, s2, s); //递归构造左子树的后序遍历 build(n-p-1, s1+p+1, s2+p+1, s+p); //递归构造右子树的后序遍历 s[n-1] = s1[0]; //把根结点添加到最后 } int main() { char s1[MAXN], s2[MAXN], ans[MAXN]; while(scanf("%s%s", s1, s2) == 2) { int n = strlen(s1); build(n, s1, s2, ans); ans[n] = '\0'; //别忘了加上字符串结束标志 printf("%s\n", ans); } return 0; } 6.4 图 图(Graph)是一种线性表和二叉树更为复杂的数据结构,它的结点间既不是前驱后继的顺序关系,也不是层次关系,而是错综复杂的网状关系。 6.4.1 黑白图像 输入一个n*n的黑白图像(1表示黑色,0表示白色),任务是统计其中八连块的个数。如果两个黑格子有公共边或者公共顶点,就说它们属于同一个八连块。如图6-11所示的图形有3个八连块。 图6-11 拥有3个八连块的黑白图形 【分析】 用递归求解:从每个黑格子出发,递归访问它所有的相邻黑格。 int mat[MAXN][MAXN], vis[MAXN][MAXN]; void dfs(int x, int y) { if(!mat[x][y] || vis[x][y]) return; // 曾经访问过这个格子,或者当前格子是白色 vis[x][y] = 1; // 标记(x,y)已访问过 dfs(x-1,y-1); dfs(x-1,y); dfs(x-1,y+1); dfs(x-1,y); dfs(x,y+1); dfs(x+1,y-1); dfs(x+1,y); dfs(x+1,y+1); // 递归访问周围的八个格子 } 这里,黑格(x,y)的mat[x][y]为1,白格为0。为了避免同一个格子访问多次,用标志vis[x][y]记录格子(x,y)是否访问过。在输入之前,在迷宫的外面加上一圈虚拟的白格子,见下面的程序。 memset(mat, 0, sizeof(mat)); //所有格子都初始化为白色,包括周围一圈的虚拟格子 memset(vis, 0, sizeof(vis)); // 所有格子都没有访问过 scanf("%d", &n); 第 页 第6章 数据结构基础 for(int i = 0; i < n; i++) { scanf("%s", s); for(int j = 0; j < n; j++) mat[i+1][j+1] = s[j]-'0'; // 把图像往中间移动一点,空出一圈白格子 } 接下来,只需不断找黑格,然后调用dfs。从它出发寻找八连块: int count = 0; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(!vis[i][j] && mat[i][j]) { count++; dfs(i,j); } //找到没有访问过的黑格 printf("%d\n", count); 完整的程序如下: #include #include const int MAXN = 1000; int n; int mat[MAXN][MAXN], vis[MAXN][MAXN]; void dfs(int x, int y) { if(!mat[x][y] || vis[x][y]) return; //曾经访问过这个格子,或者当前 格子是白色 vis[x][y] = 1; // 标记(x,y)已访问过 dfs(x-1,y-1); dfs(x-1,y); dfs(x-1,y+1); dfs(x-1,y); dfs(x,y+1); dfs(x+1,y-1); dfs(x+1,y); dfs(x+1,y+1); // 递归访问周围的八个格子 } int main() { char s[MAXN + 10]; memset(mat, 0, sizeof(mat)); // 所有格子都初始化为白色,包括周围 一圈的虚拟格子 memset(vis, 0, sizeof(vis)); // 所有格子都没有访问过 scanf("%d", &n); for(int i = 0; i < n; i++) { scanf("%s", s); for(int j = 0; j < n; j++) mat[i+1][j+1] = s[j]-'0'; // 把图像往中间移动一点,空出一圈白格子 } int count = 0; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) // 找到没有访问过的黑格 if(!vis[i][j] && mat[i][j]) { count++; dfs(i,j); } printf("%d\n", count); return 0; } 上面的函数dfs就是深度优先遍历(Depth-First Search,DFS)的算法,DFS和BFS一样,都是从一个结点出发,按照某种特定的次序访问图中的其他特点。不同的是,BFS使用队列来存放待扩展结点,而DFS使用的是栈。 第 页 第6章 数据结构基础 6.4.2 走迷宫 一个网格迷宫由n行m列的单元格组成,每个单元格要么是空地(用1表示),要么障碍物(用0来表示)。你的任务是找一条从起点到终点的最短移动序列,其中UDLR分别表示往上、下、左、右移动到相邻单元格。任何时候都不能在障碍格中,也不能走到迷宫之外。起点和终点保证是空地。n,m≤100。 【分析】 二叉树的BFS是结点的访问顺序恰好是它们到根结点距离从小到大的顺序。类似地,也可以用BFS来按照到起点的距离顺序遍历迷宫图。 举例:假定起点在左上角,从左上角开始用BFS遍历迷宫图,逐步计算出它到每个结点的最短距离(如图6-12(a)所示),以及这些最短路径上每个结点的“前一个结点”(如图6-12(b)所示)。 图6-12 用BFS求迷宫中最短路 注意,如果把图6-12(b)中箭头理解为“指向父亲的指针”,那么迷宫中的格子就变成了一棵树——除了起点外,每个结点恰好有一个父亲。如果还看不出来,可以把这棵树画成如图6-13所示的样子。 图6-13 BFS树的层次画法 图的BFS几乎与二叉树的BFS一样,但需要避免重复访问一个结点。下面代码用标记vis[x][y]记录格子(x,y)是否被走过,和DFS一样。 int q[MAXN*MAXN]; void bfs(int x, int y) { int front=0, rear=0, d, u; u = x*m+y; vis[x][y] = 1; fa[x][y] = u; dist[x][y] = 0; q[rear++] = u; while(front=0 && nx=0 && ny #include #define MAXN 105 int n, m, xs, ys, xt, yt; int maze[MAXN][MAXN], vis[MAXN][MAXN], fa[MAXN][MAXN], dist[MAXN][MAXN], last_dir[MAXN][MAXN], num[MAXN][MAXN]; int dx[] = {-1,1,0,0}; int dy[] = {0,0,-1,1}; char name[] = "UDLR"; int q[MAXN*MAXN]; void bfs(int x, int y) { int front=0, rear=0, d, u; u = x*m+y; vis[x][y] = 1; fa[x][y] = u; dist[x][y] = 0; q[rear++] = u; while(front=0 && nx=0 && ny #include const int MAXN = 1000; int n, m, G[MAXN][MAXN]; int c[MAXN]; int topo[MAXN], t; bool dfs(int u){ c[u] = -1; for(int v = 0; v < n; v++) if(G[u][v]) { if(c[v]<0) return false; else if(!c[v]) dfs(v); } c[u] = 1; topo[--t]=u; return true; } bool toposort(){ t = n; memset(c, 0, sizeof(c)); for(int u = 0; u < n; u++) if(!c[u]) if(!dfs(u)) return false; return true; } int main() { scanf("%d%d", &n, &m); memset(G, 0, sizeof(G)); for(int i = 0; i < m; i++) { int u, v; scanf("%d%d", &u, &v); G[u][v] = 1; } if(toposort()) { for(int i = 0; i < n; i++) printf("%d\n", topo[i]); } else printf("No\n"); } 说明:本程序中用到了一个c数组,c[u]=0表示从来没有访问过(从来没有调用过dfs(u));c[u]=1表示已经访问过,并且还递归访问它的所有孙子(即dfs(u)曾被调用过,并已返回);c[u]=-1表示正访问(即递归调用dfs(u)正在栈帧,尚未返回)。 6.4.4 欧拉回路 有一条名为Pregel的河流经过Konigsberg城。城中有7座桥,把河中的两个岛与河岸连接起来。当地居民热衷于一个难题:是否存在一条路线,可以不重复地走遍7座桥。这就是著名的七桥问题。它由大数学家欧拉首先提出,并给出了完美的解答, 第 页 第6章 数据结构基础 如图6-14所示。 图6-14 七桥问题 欧拉首先把图6-14(a)中的七桥问题用图论的语言改写成图6-14(b),则问题变成了:能否从无向图中的一个结点出发走出一条道路,每条边恰好经过一次。这样的路线称为欧拉道路(enlerian path),可以形象地称为“一笔画”。 不难发现,在欧拉道路中,“进”和“出”是对应的——除了起点和终点外,其他点的“进出”次数应该相等,换句话说,除了起点和终点外,其他点的度数应该有偶数。很可惜,在七桥问题中,所有4个点的度数均是奇数(这样的点也称为奇点),因此不可能存在欧拉道路。上述条件也是充分条件——如果一个无向图是连通的,且最多只有两上奇点,则一定存在欧拉道路。如果有两个奇点,则必须从其中一个奇点出发,另一个奇点终止;如果奇点不存在,则可以从任意点出发,最终一定会回到该点(称为欧拉回路)。 用类似的推理方式可以得到有向图的结论:最多只能有两个点的入度不等于出度,而且必须是其中一个点的出度恰好比入度在1(把它作为起点),另一个的入度比出度大1(把它作为终点)。当然了,还有一个前提条件:在忽略边的方向后,图必须是连通的。 下面的程序,它同时适用于欧拉道路和回路。但如果需要打印的是欧拉道路,在主程序中调用时,参数必须是道路的起点。另外,打印的顺序是逆序的,因此在真正使用这份代码时,你应当把printf语句替换成一条push语句,把边(u,v)压入一个栈内。 #include #include const int MAXN = 1000; int n, m, G[MAXN][MAXN], vis[MAXN][MAXN]; void euler(int u){ for(int v = 0; v < n; v++) if(G[u][v] && !vis[u][v]) { vis[u][v] = vis[v][u] = 1; euler(v); // 打印的顺序是逆序的:最先打印的边实际上应该最后经过 printf("%d %d\n", u, v); } } int main() { scanf("%d%d", &n, &m); memset(G, 0, sizeof(G)); for(int i = 0; i < m; i++) { int u, v; scanf("%d%d", &u, &v); G[u][v] = G[v][u] = 1; // 无向图 } euler(0); } 尽管上面的代码只适用于无向图,但不难改成有向图:把vis[u][v]=vis[v][u]=1改成vis[u][v]即可。 本 章 小 结 如果要设计出正确、高效的算法,必须要有数据结构基础。本章主要对ACM/ICPC竞赛中,所使用的基础数据结构进行了介绍,如线性表、二叉树和图,但这些内容是许多高级内容的基础。对每一个内容进行了相关的题目的讲解,给出了分析过程和源程序,还给出在解决问题的一些小技巧,这对进行在线练习非常有用。 第 页 第6章 数据结构基础 布 置 作 业 可以在UVaOJ上进行在线练习。可以练习10道线性表题、8道二叉树题、14道和图与图遍历题。 第 页

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 10 金币 [ 分享文档获得金币 ] 0 人已下载

下载文档