数据结构基础.docx

数据结构基础.docx

《数据结构基础.docx》由会员分享，可在线阅读，更多相关《数据结构基础.docx（51页珍藏版）》请在冰点文库上搜索。

数据结构基础

第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.1.1卡片游戏

桌上有叠牌，从第一张牌（即位于顶面的牌）开始从上往下依次编号为1～n。

当至少还剩两张牌时进行以下操作：

把第一张牌扔掉，然后把新的第一张放一整叠牌的最后。

输入n，输出每次扔掉的牌，以及最后剩下的牌。

样例输入：

7

样例输出：

1357426

【分析】

本题中牌像在排队。

每次从排头拿到两个，其中第二个再次排到尾部。

这种数据结构称为队列。

在数据结构称为FIFO（FirstinFirstout，先进先出）表。

用一个数组queue来实现这个队列，可设两个指针front和rear。

完整的程序如下：

#include

constintMAXN=50;

intqueue[MAXN];

intmain（）{

intn,front,rear;

scanf（"%d",&n）;

for（inti=0;i

front=0;//队首元素的位置

rear=n;//队尾元素的后一个位置

while（front

printf（"%d",queue[front++]）;//输出并抛弃队首元素

queue[rear++]=queue[front++];//队首元素转移到队尾

}

return0;

}

注意：

上面的程序有bug。

如果在最后把rear的值打印出来，rear比n大。

即在程序运行的后期，queue[rear++]=queue[front++]读写了非法内存。

也可以采取将数组空间开大些，或采取一种称为循环队列的技术，重用已出队元素占用的空间。

C++提供了一种更加简单的处理方式——STL队列。

下面是代码：

#include

#include

usingnamespacestd;

queueq;

intmain（）{

intn,front,rear;

scanf（"%d",&n）;

for（inti=0;i

while（!

q.empty（））{//当队列非空

printf（"%d",q.front（））;//打印队首元素

q.pop（）;//抛弃队首元素

q.push（q.front（））;//把队首元素加入队尾

q.pop（）;//抛弃队首元素

}

return0;

}

上面的程序的可读性大大增强了，体现在“queue”、“front”见名知义的命名，使用了C++STL。

除此之外，上面的代码还有两个附加的好处。

首先，不需要事先知道n的大小；其次，可以少用两个变量front和rear。

减少魔术数（magicnumber）和变量个数都是提高代码可读性、减少错误可能性的重要手段。

说明：

（1）在ACM竞赛中，需要用到数组、字符串、队列、堆栈、链表、平衡二叉检索树等数据结构和排序、搜索等算法，以提高程序的时间、空间运行效率，这些数据结构，如果需要手工来编写，那是相当麻烦的事情。

（2）ANSIC++中包含了一个C++STL（StandardTemplateLibrary），即C++标准模板库，又称为C++泛型库，它在std命名空间中定义了常用的数据结构和算法，使用起来十分方便。

（3）C++STL组件

STL组件三种类型的组件：

容器、迭代器和算法，它们都支持泛型程序设计标准。

容器主要有两类：

顺序容器和关联容器。

顺序容器（vector、list、queue、string等）一系列元素的有序集合。

关联容器（set、multiset、map和mulimap）包含查找元素的键值。

迭代器的作用是遍历容器。

STL算法库包含四类算法：

排序算法、不可变序算法、变序性算法和数值算法。

（4）queue队列容器

queue队列容器是一个先进先出（FirstInFirstOut，FIFO）线性存储表，元素的插入只能在队尾、元素的删除只能在队首。

使用queue需要声明头文件包含语句“#include”，queue文件在C:

\Program

Files\MicrosoftVisualStudio\VC98\Include文件夹里。

queue队列的操作有入队push（）（即插入元素）、出队pop（）（即删除元素）、读取队首元素front（）、读取队尾元素back（）、判断队列是否为空empty（）和队列当前元素的数目size（）。

下面给出一个程序来说明queue队列的使用方法。

#include

#include

usingnamespacestd;

intmain（）{

//定义队列，元素类型是整型

queueq;

//入队，即插入元素

q.push

（1）;

q.push

（2）;

q.push（3）;

q.push（9）;

//返回队列元素数量

cout<

//队列是否为空，是空，则返回逻辑真，否则返回逻辑假

cout<

//读取队首元素

cout<

//读取队尾元素

cout<

//所有元素出列（删除所有元素）

while（q.empty（）!

=true）{

cout<

//队首元素出队（删除队首元素）

q.pop（）;

}

//回车换行

cout<

return0;

}

运行结果：

4

0

1

9

1239

6.1.2铁轨

某城市有一个火车站，铁轨铺设如图6-1所示。

有n节车厢从A方向驶入车站，按进站顺序编号为1～n。

你的任务是让它们按照某种特定的顺序进入B方向的铁轨并驶出车站。

为了重组车厢，你可以借助中转站C。

这是一个可以停放任意多节车厢的车站，但由于末端封顶，驶入C的车厢必须按照相反的顺序驶出C。

对于每个车厢，一旦从A移入C，就不能再回到A了；一旦从C移入B，就不能回到C了。

换句话说，在任意时刻，只有两种选择：

A→C和C→B。

图6-1铁轨

样例输入：

5

12345

5

54123

6

654321

样例输出：

Yes

No

Yes

【分析】

在中转站C中，车厢符合后进先出的原则，称为栈，即LIFO（LastInFirstOut）表。

由于它只有一端生成，实现栈时只需要一个数组stack和栈顶指针（始终指向栈顶元素）。

完整的程序如下：

#include

constintMAXN=1000+10;

intn,target[MAXN];

intmain（）{

while（scanf（"%d",&n）==1）{

intstack[MAXN],top=0;

intA=1,B=1;

for（inti=1;i<=n;i++）

scanf（"%d",&target[i]）;

intok=1;

while（B<=n）{

if（A==target[B]）{A++;B++;}

elseif（top&&stack[top]==target[B]）{top--;B++;}

elseif（A<=n）stack[++top]=A++;

else{ok=0;break;}

}

printf（"%s\n",ok?

"Yes":

"No"）;

}

return0;

}

说明：

为了方便起见，使用的数组下标均从1开始。

例如，target[1]是指目标序列中第一个车厢的编号，而stack[1]是栈底元素（这样，栈空当且仅当top=0）。

下面给出STL栈来实现的程序：

#include

#include

usingnamespacestd;

constintMAXN=1000+10;

intn,target[MAXN];

intmain（）{

while（scanf（"%d",&n）==1）{

stacks;

intA=1,B=1;

for（inti=1;i<=n;i++）

scanf（"%d",&target[i]）;

intok=1;

while（B<=n）{

if（A==target[B]）{A++;B++;}

elseif（!

s.empty（）&&s.top（）==target[B]）{s.pop（）;B++;}

elseif（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）。

（2）要使用stack，必须声明头文件包含语句“#include”。

stack文件在C:

\

ProgramFiles\MicrosoftVisualStudio\VC98\Include文件夹中。

（3）栈只提供入栈、出栈、栈顶元素访问和判断是否为空等几种方法。

采用push（）方法将元素入栈；采用pop（）方法出栈；采用top（）方法访问栈顶元素；采用empty（）方法判断栈是否为空，如果为空，则返回逻辑真，否则返回逻假。

当然，可以采用size（）方法返回当前栈中有几个元素。

下面的程序是对栈各种方法的示例：

#include

#include

usingnamespacestd;

intmain（）{

//定义栈s，其元素类型是整型

stacks;

//元素入栈，即插入元素

s.push

（1）;

s.push

（2）;

s.push（3）;

s.push（9）;

//读取栈顶元素

cout<

//返回栈元素数量

cout<

//判断栈是否为空

cout<

//所有元素出栈（删除所有元素）

while（s.empty（）!

=true）{//栈非空

cout<

s.pop（）;//出栈（即删除栈顶元素）

}

//回车换行

cout<

return0;

}

运行结果：

9

4

0

9

9321

6.2链表

在多数情况下，线性表都用它的顺序存储结构——数组很轻松实现，但对有些问题有时用它的链式存储结构——链表更好。

6.2.1初步分析

例6-1移动小球。

你有一些小球，从左到右依次编号为1,2,3,…,n，如图6-2所示。

图6-2链表的初始状态

可以执行两种指令。

其中，AXY表法把小球X移动到小球Y左边，BXY表示把小球X移动到小球Y右边。

指令保证合法，即X不等于Y。

例如，在初始状态下执行A14后，小球被移动小球4的左边，如图6-3所示。

图6-3一次操作后的链表状态

如果再执行B35，结点3将会移到5的右边，如图6-4的所示。

图6-4两次操作后的链表状态

输入小球个数n，指令条数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++）

if（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;

}

intmain（）{

intm,X,Y,p,q;

chartype[9];

scanf（"%d%d",&n,&m）;

for（inti=1;i<=n;i++）//初始化数组

A[i]=i;

for（inti=0;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]往左循环移动

elseshift_circular_right（q,p）;//A[q]到A[p]往右循环移动

}

else{

if（q>p）shift_circular_left（p,q）;//A[p]到A[q]往左循环移动

elseshift_circular_right（q+1,p）;//A[q+1]到A[p]往右循环移动

}

}

for（inti=1;i<=n;i++）

printf（"%d",A[i]）;

printf（"\n"）;

return0;

}

对于上面的程序，当数据量很大时，代码是否会超时。

一般来说，可以用两种方法判断：

测试和分析。

计时测试的方法在前面已讲过，它的优点是原理简单、可操作性强，缺点在于必须事先程序写好——包括主程序和测试数据生成器。

如果算法非常复杂，这是相当花时间的。

另一种方法是写程序之前进行算法分析，估算时间效率，这种方法在第8章会详细分析。

不过现在可以直观分析一下：

如果反复执行B1n和A12，每次都移动几乎所有元素。

元素个数和指令条数都那么大，移动总次数将是相当可观的。

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

constintMAXN=1000;

intn,left[MAXN],right[MAXN];

voidlink（intX,intY）{

right[X]=Y;left[Y]=X;

}

intmain（）{

intm,X,Y;

chartype[9];

scanf（"%d%d",&n,&m）;

for（inti=1;i<=n;i++）{

left[i]=i-1;right[i]=i+1;

}

for（inti=0;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（intX=right[0];X!

=n+1;X=right[X]）

printf（"%d",X）;

printf（"\n"）;

return0;

}

6.2.3对比测试

对于写好的程序，可能会花费较长的时间进行调试，所以要具备一定的调试和测试能力。

测试的任务就是检查一份代码是否正确。

如果找到了错误，最好还能提供一个让它错误的数据。

有了错误数据之后，接下来的任务便是调试：

找出出错的原因。

如果找到了错，最好把它改对——至少对于刚才的错误数据能得到正确的结果。

改对一组数据之后，可能还有其他错误，因此需要进一步测试；即使以前曾经正确的数据，也可能因为多次改动之后反而变错了，需要再次调试。

总之，在编码结束后，为确保程序的正确性，测试和调试往往要交替进行。

确保代码正确的方法是：

再找一份完成同样功能的代码与之对比，用它来和这个新程序“对答案”（俗称对拍）。

对比测试首先需要数据，而且是大量数据。

为此，需要编写数据生成器，完整的代码如下：

#include

#include//rand（）和srand（）需要

#include//time（）需要

intn=100,m=100000;

doublerandom（）{//生成[0,1]之间的均匀随机数

return（double）rand（）/RAND_MAX;

}

intrandom（intm）{//生成[0,m-1]之间的均匀随机数

return（int）（random（）*（m-1）+0.5）;

}

intmain（）{

srand（time（NULL））;//利用系统时间，初始化随机数种子

printf（"%d%d\n",n,m）;

for（inti=0;i

if（rand（）%2==0）printf（"A"）;elseprintf（"B"）;//随机指令种类

intX,Y;

for（;;）{

X=random（n）+1;

Y=random（n）+1;

if（X!

=Y）break;//只有X和Y不相等时才是合法的

}

printf（"%d%d\n",X,Y）;

}

return0;

}

核心函数是stdlib.h中的rand（），它生成一个闭区间[0,RAND_MAX]的均匀随机整数（均匀的含义是：

该区间内每个整数被产生的概率相同），其中RAND_MAX至少为32767（215-1），在不同的环境下的值可能不同。

严格地说，这个随机数是“伪随机数”，因为它也是由数学公式计算出来的。

6.2.4