算法竞赛入门经典授课教案第6章数据结构基础.docx
- 文档编号:15864544
- 上传时间:2023-07-08
- 格式:DOCX
- 页数:49
- 大小:87.97KB
算法竞赛入门经典授课教案第6章数据结构基础.docx
《算法竞赛入门经典授课教案第6章数据结构基础.docx》由会员分享,可在线阅读,更多相关《算法竞赛入门经典授课教案第6章数据结构基础.docx(49页珍藏版)》请在冰点文库上搜索。
算法竞赛入门经典授课教案第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栈和队列
线性表是“所有元素排成一行”的数拯结构。
除了第一个元素之外,所有元素都有一个“前一个元素S除了最后一个元素外,所有元素都有“后一个元素化
线性结构是重要的算法和数据结构的基础。
下而介绍两种特姝的线性表:
栈和队列。
6.1.1卡片游戏
桌上有叠牌,从第一张牌(即位于顶而的牌)开始从上往下依次编号为1〜n。
当至少还剩两张牌时进行以下操作:
把第一张牌扔掉,然后把新的第一张放一整叠牌的最后。
输入m输出每次扔掉的牌,以及最后剩下的牌匚
样例输入:
7
样例输出:
1357426
【分析】
本题中牌像在排队。
每次从排头拿到两个,其中第二个再次排到尾部。
这种数据结构称为队列。
在数据结构称为FIFO(FirstinFirstout,先进先出)表。
用一个数组queue来实现这个队列,可设两个指针front和rear0
完整的程序如下:
^include
constintMAXN=50;
intqueue[MAXN];
intmainO{
intn,front,rear;
scanf(W&n);
for(inti=0;i front二0; //队首元素的位置 rear=n; //队尾元素的后一个位置 while(front 〃当队列非空 printf(? ,%d"、queueLfront++]); //输出并抛弃队首元素 queue^rear++]=queue[front++]; //队首元素转移到队尾 } return0; } 注意: 上而的程序有bug。 如果在最后把rear的值打印出来,rear比n大。 即在程序运行的后期,queue[rear++]=queue[front++]读写了非法内存。 也可以采取将数组空间开大些,或采取一种称为循环队列的技术,重用已出队元素占用的空间。 C++提供了一种更加简单的处理方式一一STL队列。 下面是代码: ^include frinclude usingnamespacestd; queue intmainO{ intn,front,rear; q.push(i+l);//初始化队列 〃当队列非空 //打印队首元素 //抛弃队首元素 //把队首元素加入队尾 //抛弃队首元素 scanff&n); for(inti=0;i q.empty()){ printf(? ,%d",q.front());q・pop0; q.push(q.front()); Q-Pop0; } return0; } 上而的程序的可读性大大增强了,体现在“queue: "front"见名知义的命名,使用了C++STL。 除此之外,上而的代码还有两个附加的好处。 首先,不需要事先知道n的大小: 其次,可以少用两个变front和rear0减少魔术数(magicnumber)和变量个数都是提高代码可读性.减少错误可能性的重要手段。 说明: (1)任ACH竞赛中,需要用到数组.字符串.队列.堆栈、链表、平衡二叉检索树等数据结构和排序、搜索等算法,以提髙程序的时间、空间运行效率,这些数据结构,如果需要手工来编写,那是相当麻烦的事情。 (2)ANSIC++中包含了一个C++STL(StandardTemplateLibrary)^即C卄标准模板库,又称为C卄泛型库,它在std命名空间中左义了常用的数据结构和算法,使用起来十分方便。 (3)C++STL组件 STL组件三种类型的组件: 容器、迭代器和算法,它们都支持泛型程序设计标准。 容器主要有两类: 顺序容器和关联容器。 顺序容器(vector,list,queue,string等)一系列元素的有序集合◎关联容器(set、multisetsmap和mulimap)包含査找元素的键值。 迭代器的作用是遍历容器。 STL算法库包含四类算法: 排序算法.不可变序算法、变序性算法和数值算法。 (4)queue队列容器 queue队列容器是一个先进先岀(FirstInFirstOut,FIFO)线性存储表,元素的插入只能在队尾、元素的删除只能在队首。 使用queue需要声明头文件包含语句“#include \ProgramFiles\MicrosoftVisualStudio\VC98\Include文件夹里。 queue队列的操作有入队pushO(即插入元素)、岀队pop()(即删除元素)、读取队首元素front0.读取队尾元素backO.判断队列是否为空empty0和队列当前元素的数目sizeOo 下而给出一个程序来说明queue队列的使用方法。 ^include ^include usingnamespacestd; intmainO{ 〃定义队列,元素类型是整型 queue //入队,即插入元素 q.push(l); q.push (2); q.push(3); q.push(9); 〃返回队列元素数咼 cout< 〃队列是否为空,是空,则返回逻辑真,否则返回逻辑假cout< //读取队首元素 cout«q.front0«endl; //读取队尾元素 cout< //所有元素出列(删除所有元素) while(q.empty()! =true){ cout< //队首元素出队(删除队首元素) Q-Pop0; } //回车换行 cout«endl; return0; } 运行结果: 4 0 1 9 1239 6.1.2铁轨 某城市有一个火车站,铁轨铺设如图6-1所示。 有n打车厢从A方向驶入车站,按进站顺序编号为1〜你的任务是让它们按照某种特左的顺序进入B方向的铁轨并驶出车站。 为了重组车厢,你可以借助中转站C。 这是一个可以停放任意多节车厢的车站,但由于末端封顶,驶入C的车厢必须按照相反的顺序驶岀C。 对于每个车厢,一旦从A移入C,就不能再回到AT: 一旦从C移入B,就不能回到CTo换句话说,在任意时刻,只有两种选择: A-C和C-Bc 样例输入: 5 12345 5 54123 6 654321 样例输岀: Yes No Yes 【分析】 在中转站C中,车厢符合后进先出的原则,称为栈,即LIFO(LastInFirstOut)表。 由于它只有一端生成,实现栈时只需要一个数组stack和栈顶指针(始终指向栈顶元素)。 完整的程序如T*: Sinclude constintMAXN=1000+10; intn,target[MAXN]; intmainO{ while(scanf(”%d",&n)=1){ intstack[MAXN],top=0; intA=1,B=1; for(inti=1;i<=n;i++) scanff&target[i]); intok=1; while(B<=n){ if(A=target[B]){A++;B++;} elseif(top&&stack[top]==targetEB]){top--;B++;} elseif(A<=n)stack[++top]=A++; else{ok=0;break;} } printf("%s\n",ok? "Yes": "No"); } return0; } 说明: 为了方便起见,使用的数组下标均从1开始。 例如,target[1]是指目标序列中第一个车厢的编号,而stackEl]是栈底元素(这样,栈空当且仅当top二0)。 下而给出STL栈来实现的程序: ^include ^include usingnamespacestd; constintMAXN=1000+10; intn,target[MAXN]; intmainO{ while(scanf(z,%d,/,&n)==1){stack intA=1,B=1; for(inti=1;i<=n;i++)scanf&target[i]); intok=1; while(B<=n){ 辻(A=targetLB]){A++;B++;} elseif(! s・empty()&& s.top0 =target[B]){ s・pop0; B++;} elsei.f(A<=n)s ;・push(A++); else{ok=0;break;} } printf(”%s\n",ok? "Yes": "No"); } return0; } 说明: (1)stack栈容器是一种C++STL中的容器,它是一个后进先出(LastInFirstOut,LIFO)的线性表,插入和删除元素都只能在表的一端进行。 插入元素的一端称为栈顶(StackTop),而另一端称为栈底(StackBottom)«插入元素称为入栈(Push),元素的删除则称为出栈(Pop)o (2)要使用stack,必须声明头文件包含语句“#include〈stack〉"。 stack文件在C: \ProgramF订es\MicrosoftVisualStudio\VC98\Include文件夹中。 (3)栈只提供入栈、出栈、栈顶元素访问和判断是否为空等几种方法。 釆用pushO方法将元素入栈: 采用pop()方法出栈: 釆用top()方法访问栈顶元素;采用empty0方法判断栈是否为空,如果为空,则返回逻辑真,否则返回逻假。 当然,可以采用sizeO方法返回当前栈中有几个元素。 下而的程序是对栈各种方法的示例: ^include ^include intmainO{ //立义栈s,其元素类型是整型 stack //元素入栈,即插入元素 s.push(l); s.push (2); s.push(3); s.push(9); //读取栈顶元素 cout«s・top0< //返回栈元素数量 cout«s・size()«endl; 〃判断栈是否为空 cout«s・empty()«endl; //所有元素出栈(删除所有元素) while(s.empty0! =true){//栈非空 COUt«S.top()V”;//读取栈顶元素 s.pop();//出栈(即删除栈顶元素) } //回车换行 cout«endl; return0; } 运行结果: 9 4 0 9 9321 6.2链表 在多数情况下,线性表都用它的顺序存储结构一一数组很轻松实现,但对有些问题有时用它的链式存储结构一一链表更好。 6.2.1初步分析 例6-1移动小球。 你有一些小球,从左到右依次编号为1,2,3,-sn,如图6-2所示。 图6-2链表的初始状态 可以执行两种指令。 其中,AXY表法把小球X移动到小球Y左边,BXY表示把小球X移动到小球Y右边。 指令保证合法,即X不等于人 例如,在初始状态下执行A14后,小球被移动小球4的左边,如图6-3所示。 图6-3—次操作后的链表状态 如果再执行B35,结点3将会移到5的右边,如图6-4的所示。 图6-4两次操作后的链表状态 输入小球个数m指令条数m和n条指令,从左到右输出最后的序列。 注意,n可能髙达500000,而m可能高达100000. 样例输入: 62 A14 B35 样例输出: 214536 【分析】 各个小球在逻辑上是相邻的,因此可考虑把它们放在一个数组A中,所以完整的程序如下: ^include constintMAXN=1000; intn,A[MAXN]; intfind(intX){ for(inti=1;i<=n;i++) 辻(A[i]=X)returni; return0; } voidshift_circular_left(inta,intb){ intt=A[a]; for(inti=a;i A[b]=t; } voidshift_circular_right(inta,intb){ intt=A[b]; for(inti=b;i>a;i—)A[i]二A[i-1]; A[a]=t; } intmainO{ intm,X,Y,p,q; chartype[9]; scanf(,z%d%d/z,&n,&m); for(inti=1;i<=n;i++)//初始化数组 A[i]=i; for(inti=0;i scanfC%s%d%d\type,&X,&Y); P二find(X);//查找X和Y在数组中的位置 q=find(Y); if(typeE0]==,A,){ if(q>P)shift_circular_left(p,qT);//A[p]到A[qT]往左循环移动 elseshift_circular_right(q,p);//A[q]到A[p]往右循环移动 }else{ if(q>p)shift_circular_left(p,q);//A[p]到A[q]往左循环移动 elsesh辻t_circular_right(q+1,p);//A[q+1]到A[p]往右循环移动 } } for(inti=l;i<=n;i++) printf(z,%d"、A[i]); printf(,z\n/z); return0; } 对于上而的程序,当数据量很大时.代码是否会超时。 一般来说,可以用两种方法判断: 测试和分析。 讣时测试的方法在前而已讲过,它的优点是原理简单、可操作性强,缺点在于必须事先程序写好一一包括主程序和测试数据生成器」如果算法非常复杂,这是相当花时间的。 另一种方法是写程序之前进行算法分析,估算时间效率,这种方法在第8章会详细分析。 不过现在可以直观分析一下: 如果反复执行B1n和A12,每次都移动几乎所有元素。 元素个数和指令条数都那么大,移动总次数将是相当可观的。 6.2.2链式结构 第二种方法是强调小球之间的相对顺序,而非绝对顺序。 用left[i]和right[i]分别表示编号为i的小球左边和右边的小球编号(如果是0,表示不存在),则在移动过程中可以分成两个步骤: 把X移岀序列: 把X重新插入序列。 第一步让1eft[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和righto对于特殊情况下,对于最左的小球X,它的leftEX]的值为0,但可以假想最左的小球左边有一个编号为0的虚拟的小球。 那么对最右的小球的右边的虚拟小球编号为n+1。 核心的代码如下: scanfC%s%d%d",type,&X,&Y); link(leftEX],right[X]); if(type[01='A'){ linkdeftEY],X);//这一行和下一行不能搞反 link(X,Y); } else{ link(X,right[Y]);//这一行和下一行不能搞反 link(Y,X); } 函数link(X,Y)的作用是赋值right[X]二Y,然后left[Y]=Xo 完整的程序如下: ^include constintMAXN=1000; intn,left[MAXN],right[MAXN]; voidlink(intX,intY){ right[X]=Y;left[Y]=X; } intmainO{ intm,X,Y; chartype[9]; scanf(z/%d%dz\&n,&m); for(inti=1;i<=n;i卄){ leftti]二i-1;right[i]二i+1; } for(inti=0;i scanfC%s%d%d",&type,&X,&Y); 1ink(left[X],right[X]); if(type[0]二二’A'){ link(left[Y],X);//这一行和下一行不能搞反 link(X,Y); } else{ link(X,right[Y]);//这一行和下一行不能搞反 link(Y,X); } } for(intX=right[0];X! =n+1;X=right[X]) printf(z,%d",X); printf(,z\n/z); return0; } 6.2.3对比测试 对于写好的程序,可能会花费较长的时间进行调试,所以要具备一上的调试和测试能力。 测试的任务就是检查一份代码是否正确匚如果找到了错误,最好还能提供一个让它错误的数据。 有了错误数据之后,接下来的任务便是调试: 找出岀错的原因。 如果找到了错,最好把它改对一一至少对于刚才的错误数拯能得到正确的结果。 改对一组数据之后,可能还有其他错误,因此需要进一步测试: 即使以前曾经正确的数据,也可能因为多次改动之后反而变错了,需要再次调试。 总之,在编码结朿后,为确保程序的正确性,测试和调试往往要交替进行。 确保代码正确的方法是: 再找一份完成同样功能的代码与之对比,用它来和这个新程序“对答案”(俗称对拍)。 对比测试首先需要数据,而且是大虽: 数据。 为此,需要编写数据生成器,完整的代码如下: ^include ^include ^include intn=100,m=100000; doublerandom(){〃生成[0,1]之间的均匀随机数 return(double)randO/RAND_MAX; } intrandom(intm){//生成[0,mT]之间的均匀随机数 return(int)(random0*(m-1)+0・5); } intmainO{ srand(time(NULL));//利用系统时间,初始化随机数种子 printf(,z%d%d\n,z,n,m); for(inti=0;i if(randO%2=0)printf("A");elseprintf("B");//随机指令种类 intX,Y; for(;;){ X=random(n)+l; Y=random(n)+l; if(X! =Y)break;//只有X和Y不相等时才是合法的 } printfC%d%d\n',X,Y); } return0; } 核心函数是stdlib.h中的randO,它生成一个闭区间[0,RAND_MAX]的均匀随机整数(均匀的含义是: 该区间内每个整数被产生的概率相同),其中RAND_MAX至少为32767(215-1),在不同的环境下的值可能不同。 严格地说,这个随机数是“伪随机数笃因为它也是由数学公式计算出来的。 6.2.4随机数发生器 上而的程序使用了randO函数和s
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 竞赛 入门 经典 授课 教案 数据结构 基础