资源简介

第1章 绪论
第2章 线性表
第3章 栈
第4章 队列
第5章 树和二叉树
第6章 图
第1章 绪论
程序设计就是使用计算机解决现实世界中的实际问题。对于给定的一个实际问题，在进行程序设计时，首先要把实际问题中用到的信息抽象为能够用计算机表示的数据；第二要把抽象出来的这些数据建立一个数据模型，这个数据模型也称为逻辑结构，即建立数据的逻辑结构；第三要把逻辑结构中的数据及数据之间的关系存放到计算机中，即建立数据的存储结构；最后在所建立的存储结构上实现对数据元素的各种操作，即算法的实现。
本章就是要使大家了解计算机中的数据表示，理解数据元素、逻辑结构、存储结构和算法的有关概念；掌握基本逻辑结构和常用的存储方法，能够选择合适的数据的逻辑结构和存储结构；掌握算法及算法的五个重要特性，能够对算法进行时间复杂度分析，从而选择一个好的算法，为后面的学习打下良好的基础。
1.1基本概念和术语
1.数据(data)：
是对客观事物的符号的表示,是所有能输入到计算机中并被计算机程序处理的符号的总称。
2.数据元素(data element):
是数据的基本单位，在计算机程序中通常作为一个整体来处理。一个数据元素由多个数据项（data item）组成，数据项是数据不可分割的最小单位。
3.数据结构(data structure):
是相互之间存在一种或多种特定关系的数据元素的集合。数据结构是一个二元组，记为:
data_structure=(D,S).其中D为数据元素的集合，S是D上关系的集合。
数据元素相互之间的关系称为结构（structure）。根据数据元素之间关系的不同特性，通常由下列四类基本结构：
（1）集合:数据元素间的关系是同属一个集合。（图1）
（2）线性结构:数据元素间存在一对一的关系。（图2）
（3）树形结构：结构中的元素间的关系是一对多的关系。（图3）
（4）图（网）状结构：结构中的元素间的关系是多对多的关系。（图4）
图1 图2
图3 图4
1.2 数据的逻辑结构和物理结构
1.逻辑结构：数据元素之间存在的关系（逻辑关系）叫数据的逻辑结构。即上面给出的四种结构。
2.物理结构：数据结构在计算机中的表示（映象）叫数据的物理结构，又称存储结构。
一种逻辑结构可映象成不同的存储结构：顺序存储结构和非顺序存储结构（链式存储结构和散列结构）。
1.3算法及算法分析
1. 算法：是对特定问题求解步骤的一种描述，是指令的有限序列。一个算法是一系列将输入转换为输出的计算步骤。
2. 算法的重要特性
①输入：一个算法应该有零个或多个输入。
②有穷性：一个算法必须在执行有穷步骤后正常结束，而不能形成无穷循环。
③确定性：算法中的每一条指令必须有确切的含义，不能产生多义性。
④可行性：算法中的每一条指令必须是切实可执行的，即原则上可以通过已经实现的基本运算执行有限次来实现。
⑤输出：一个算法应该有一个或多个输出，这些输出是同输入有某个特定关系的量。
3. 算法的时间复杂度
①定义：设问题的规模为n，把一个算法的时间耗费T(n)称为该算法的时间复杂度，它是问题规模为n的函数。
②算法的渐进时间复杂度
设T(n)为一个算法的时间复杂度，如果当n趋向无穷大时T(n)与函数f(n)的比值的极限是一个非零常数M，即记作T(n)=O(f(n))，则称O(f(n))为算法的渐进时间复杂度，简称时间复杂度，也称T(n)与f(n)的数量级相同，通常，f(n)应该是算法中频度最大的语句的频度。
③常用的算法的时间复杂度的顺序
O(1)④算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始状态有关。
例如：在数组A[0...n-1]中查找给定值K的算法如下：
(1)i=n-1;
(2)while(i>=0&&(A[i]!=k))
(3)?i--;
(4)return i;
此算法中的语句(3)的频度不仅与问题规模n有关，还与输入实例中A的各元素取值及K的取值有关：
若A中没有与K相等的元素，则语句(3)的频度f(n)=n；
若A的最后一个元素等于K，则语句(3)的频度f(n)是常数0。
⑤最坏时间复杂度和平均时间复杂度
最坏情况下的时间复杂度称为最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。
这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何情况下更长。
平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。
例1 求下列交换两个变量i和j的值的算法的时间复杂度。
(1) i=10;
(2) j=20;
(3) t=i;
(4) i=j;
(5) j=t;
解：各行语句的执行次数均为1，所以该算法的时间耗费T(n)= 1+1+1+1+1=5，该算法的时间耗费T(n)与问题的规模n无关，因此，该算法的时间复杂度T(n)=O(1)。
例2 求两个n阶方阵的乘积C=A×B，其算法如下，计算该时间复杂度。
程序段：
(1) for(i=0; i(2) for(j=0; j(3) {c[i][j]=0;
(4) for(k=0; k(5) c[i][j]+=a[i][k]*b[k][j];
}
解：解法1
计算程序段中的每一行的执行次数。
第(1)行for(i=0; i第(2)行for(j=0; j第(3)行c[i][j]=0;在表达式i第(4)行for(k=0; k第(5)行c[i][j]+=a[i][k]*b[k][j]; 在表达式i因此，各行执行次数分别为：n+1，n（n+1），n2，n2（n+1），n3。
如果用T(n)表示该算法的时间耗费，则
T(n)= n+1+n（n+1）+n2+n2（n+1）+n3=2n3+3n2+2n+1
由此可知，该算法的时间耗费T(n)是矩阵阶数n的函数，T(n)=O(n3)。
解法2
只计算执行频度最高的行。
显然，在该程序段中，执行频度最高的行为c[i][j]+=a[i][k]*b[k][j]; 在表达式i【课堂实践】分析并计算下面程序段执行的时间复杂度。
i=1; k=0;?
while(i<=n-1)
{ k+=10*i;
i++;
}
第2章 线性表
线性表是最常用且最简单的一种数据结构，一个线性表是n个数据元素的有序系列，每个数据元素可以是一个数或一个符号，也可以使一页书，甚至其他更复杂的信息。如26个字母的字母表：（A,B,C,D…..,Z）在复杂的线性表中，一个数据元素可以由若干个数据项组成，在这种情况下，常把数据元素称为一个记录，含有大量记录的线性表又称文件。如图
综合上述例子，可以将线性表描述为：
线性表是由n个数据元素的有限序列(a1,a2,…,an)组成的，其中每一个数据元素ai的具体含义可以按不同的情况和要求定义具体的内容，它可以是一个数、一个符号、一串文字，甚至是其他更复杂的信息。线性表中数据元素的个数n称为线性表的长度。
2.1 线性表的逻辑结构及基本运算
1.线性表简单的定义
n个数据元素的有限序列其特点是除了表头和表尾外，表中的每一个元素有且仅有唯一的前驱和唯一的后继，表头有且只有一个后继，表尾有且只有一个前驱。线性表中的数据元素不仅可以进行访问，还可进行插入和删除。
若n=0，则表示一个空表，即没有任何数据元素的线性表；若n>0，则除a1和an外，有且仅有一个直接前驱和一个直接后继，即ai(其中1< i2.线性表的基本运算
（1）线性表初始化
格式：InitList(L)
初始条件：线性表L不存在。
操作结果：构造一个空的线性表L。
（2）求线性表的长度
格式：LengthList(L)
初始条件：线性表L存在。
操作结果：返回线性表L中所有元素的个数。
（3）取表元
格式：GetList(L，i)
初始条件：线性表L存在，且1≤i≤LengthList(L)。
操作结果：返回线性表L的第i个元素(ai)的值。
（4）按值查找
格式：LocateList(L，x)
初始条件：线性表L存在，x有确定的值。
操作结果：在线性表L中查找值为x的数据元素，并返回该元素在L中的位置。若L中有多个元素的值与x相同，则返回首次找到的元素的位置；若L中没有值为x的数据元素，返回一个特殊值（通常为-1）表示查找失败。
（5）插入操作
格式：InsertList(L，i，x)
初始条件：线性表L存在，i为插入位置（1≤i≤n+1，n为插入前的表长）。
操作结果：在线性表L的第i个元素(ai)位置上插入值为x的新元素，原序号为i,i+1, …,n的数据元素的序号插入后变为i+1,i+2, …,n+1，插入后表长=原表长+1。
（6）删除操作
格式：DeleteList(L，i)
初始条件：线性表L存在，i（1≤i≤n）为给定的待删除元素的位置值。
操作结果：在线性表L中删除序号为i的数据元素(ai)，删除后，原序号为i+1,i+2, …,n的数据元素的序号变为i,i+1, …,n-1，删除后表长=原表长-1。
注：以上给出的是线性表的基本运算，并不是全部运算，其它运算可用这些基本运算来实现，这些运算都是定义在逻辑结构层次上的运算，只有确定了存储结构之后，才能具体实现这些运算。
例1 假设两个线性表LA,LB分别代表两个集合A和B:求A=A U B
void union(List &La ,List &Lb){
//将所有在线性表Lb中，但不在La中的数插入到La中
La.len=ListLength(La);
Lb.len=ListLength(Lb); //求两表的长度
for(i=1;i<=Lb.len;i++)
GetElem(Lb,i,e);//取Lb中第i个的元素复制给e
If(!LocateElem(La,e,equal))
ListInsert(La,++La.len,e);//若其中不存在相同的，则插入
}//union
例2 已知线性表la，lb中的数据元素按值非递减有序排列，现要求将la，lb归并为一个新的线性表lc且lc按值非递减。
例如 la=（3,5,8,11）,
Lb=(2,6,8,9,11,15,20)
则lc=(2,3,5,6,8,8,9,11,11,15,20)
分析：由于两表都是按照一定顺序进行排列，所有设置2个指针，分别指向a、b表，先分别比较比较最初指向的两数据，比较一下大小，谁小就放入到c表中，然后数小的指针向下移动，再进行比较。直到2表有一表结束,再将剩余的表存放到c中。
Void MergeList(List La, List Lb,List &Lc){
//已知线性表la和lb中的数据元素
InitList(Lc);//初始化表c
Int i=j=1;k=0;
La.len=ListLength(La);
Lb.len= ListLength(Lb);
While((i<= La.len)&&( (j<= Lb.len)){
GetElem（La,i,ai）;
GetElem（Lb,j,bj）;//获取数值
If(ai<=bj){
ListInsert(Lc,++k,ai);
i++;
}else{
ListInsert(Lc,++k,bj);
j++;
}//if结束
}//whie结束,其中一表结束；
While(i<=La.len){//表B数据全访问完，表a未到最后
GetElem（La,i++,ai）;
ListInsert(Lc,++k,ai);
}
While(j<=Lb.len){//表a数据全访问完，表b未到最后
GetElem（Lb,j++,bj）;
ListInsert(Lc,++k,bj);
}
}//程序结束
分析：上述2个算法的时间复杂度（基本操作的执行时间），例1为O(ListLength(La)*ListLength(Lb)),例2的时间复杂度为O(ListLength(La)+ListLength(Lb))。
2.2 线性表的顺序存储结构
线性表的顺序存储即用一组地址连续的存储单元依次存储线性表中的元素。设线性表中每个元素需占用r个存储单元则
loc（ai+1 ）=loc（ai）+r
loc（ai）=loc（a1）+（i-1）*r
线性表的这种机内表示称做线性表的顺序存储结构或顺序映像，通常，称这种存储结构的线性表为顺序表。只要确定了存储线性表的起始位置，线性表中任一数据元素可随机存储，所以线性表的顺序结构是一种随机存储的存储结构。
//======线性表的动态顺序存储结构
#define LIST_INIT_SIZE 100 // 初始分配量
#define LISTINCREMENT 10 //分配增量
Typedef struct{
Elemtype *elem; //存储空间基址
Int length; //当前长度
Int listsize; //当前分配的存储容量
}SqList;
Elem表示基地址，length指示线性表的当前长度。上述的含义是为顺序表分配一个预定义大小的数据空间，并将当前的长度设为0；
Status InitList_sq(SqList &L){
//====创建一个空的线性表
L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));// ElemType指数据类型，malloc新分配空间
If(!L.elem) exit(OVERFLOW);//存储分配失败
L.length=0;//空表长度为0
L.listsize= LIST_INIT_SIZE;//初始存储容量
Return ok；
}//InitList_sq
在这种存储方式下，容易实现对表的遍历。要在表的尾部插入一个新元素，也很容易。但是要在表的中间位置插入一个新元素，就必须先将其后面的所有元素都后移一个单元，才能腾出新元素所需的位置。
Status ListInsert_sq(SqList &L,int I,ElemType e){
//在顺序表中插入一个新元素 e
If(i<1||i>L.length+1) return Error;
If(L.length>= L.listsize){//当前存储空间已满，增加分配
Newbase=(ElemType*)realloc(L.elem,(LIST_INIT_SIZE+LISTINCREMENT)*sizeof(ElemType));// ElemType指数据类型，realloc再次分配，L.elem存储基地址
}//if
q=&(L.elem[i-1]);//q为插入位置
for(p=&(L.elem[L.length-1]);p>=q;--p){
*(p+1)=*q;
}//for
*q=e;//插入e
++ L.length；
Return ok；
}
执行删除运算的情形类似。如果被删除的元素不是表中最后一个元素，则必须将它后面的所有元素前移一个位置，以填补由于删除所造成的空缺。这两种运算的时间复杂度均为O(n)n为表的长度。
Status ListDelete_sq(SqList &L,int I,ElemType &e){
//在顺序表中插入一个新元素 e
If(i<1||i>L.length+1) return Error;
p=&(L.elem[i-1]);//p为删除位置
e=*p;
q=L.elem+L.length-1;
for(++p;p<=q;++p){
*(p-1)=*p;
}//for
-- L.length；
Return ok；
}
2.3 线性表的链式存储结构
线性表顺序结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻，因此可以随机存储表中的任一元素，但是在插入删除时须移动大量元素。而线性表的链式存储由于其不要求逻辑上相邻，因此它没有顺序存储结构的弱点，但同时也失去了顺序表可随机存取的优点。
1.单链表
线性链表的特点是用一组任意的存储单元存储线性表的元素，用指针将存储表元素的那些单元依次串联在一起。这种方法避免了在数组中用连续的单元存储元素的缺点，因而在执行插入或删除运算时，不再需要移动元素来腾出空间或填补空缺。然而我们为此付出的代价是，需要在每个单元中设置指针来表示表中元素之间的逻辑关系，因而增加了额外的存储空间的开销。
为了将存储表元素的所有单元用指针串联起来，我们让每个单元包含一个元素域和一个指针域如图所示：
其中，存储单元由两部分构成，即数据域存储数据元素，指针域存储下一个元素所在的单元
如果表是a1,a2,…,an ，那么含有元素ai的那个单元中的指针应指向含有元素ai+1的单元(i=1,2,…,n-1)。含有an的那个单元中的指针是空指针null。此外，通常我们还为每一个表设置一个表头单元header，其中的指针指向开始元素中所在的单元，但表头单元header中不含任何元素。设置表头单元的目的是为了使表运算中的一些边界条件更容易处理。这一点我们在后面可以看到。如果我们愿意单独地处理诸如在表的第一个位置上进行插人与删除操作等边界情况，也可以简单地用一个指向表的第一个单元的指针来代替表头单元。
上述这种用指针来表示表的结构通常称为单链接表，或简称为单链表或链表。单链表的逻辑结构如图1所示。表示空表的单链表只有一个单元，即表头单元header，其中的指针是空指针null。

图1 单链表示意图
为了便于实现表的各种运算，在单链表中位置变量的意义与用数组实现的表不同。在单链表中位置i是一个指针，它所指向的单元是元素ai-1所在的单元，而不是元素ai所在的单元(i=2,3,…,n)。位置1是指向表头单元header的指针。位置End(L)是指向单链表L中最后一个单元的指针。这样做的目的是为了避免在修改单链表指针时需要找一个元素的前驱元素的麻烦，因为在单链表中只设置指向后继元素的指针，而没有设置指向前驱元素的指针。
单链表存储结构
Typedef struct Lnode{
ElemType data;
Struct Lnode *next;//指向后继节点的指针
}Lnode, *LinkList;//线性链表的实质就是指针
基本运算
(1)ListInsert.L(L,i,e)
功能:在表L的位置p处插入元素x，并将原来占据位置p的元素及其后面的元素都向后推移一个位置。例如，设L为a1,a2,…,an，那么在执行Insert(x,p)后，表L变为a1,a2,…ap-1,x,ap,…,an 。若p为End(L)，那么表L变为a1,a2,…,an,x 。若表L中没有位置p，则该运算无定义。
实现P为指向a节点的指针，s为指向X节点的指针:s->next=p->next; p->next=s;
上述算法中，链表指针的修改情况见图2
图2(a)是执行Insert运算之前的情况。我们要在指针p所指的单元之后插入一个新元素x。图2(b)是执行Insert运算以后的结果，其中的虚线表示新的指针。在上述Insert算法中，位置变量p指向单链表中一个合法位置，要插入的新元素x应紧接在p所指单元的后面。指针p的合法性应在执行Insert运算之前判定。往一个单链表中插入新元素通常在表头或表尾进行，因此p的合法性容易判定。Insert运算所需的时间显然为O(1)。
(2)Delete(p)
功能:从表L中删除位置p的下一元素。例如，当L为a1,a2,…,an时，执行Delete(p)后，L变为a1,a2,…,ap-1,ap+1,…,an 。当L中没有位置p或p=End(L)时，该运算无定义。实现:p.next=p.next.next;
这个过程很简单，其指针的修改如图3所示。
若要从一个表中删除一个元素x，但不知道它在表中的位置，则应先用Locate(x,L)找出指示要删除的元素的位置，然后再用Delete删除该位置指示的元素。Delete过程所需的时间显然也为O(1)。
2.静态链表
静态链表：用游标指示数组单元地址的下标值，它属整数类型数组元素是记录类型，记录中包含一个表元素和一个作为游标的整数；具体说明如下:
type jid=record
data:datatype;
next:integer;
end;
var alist=array[0..maxsize] of jid
游标即我们可以用游标来模拟指针, 对于一个表L，我们用一个整型变量Lhead(如Lhead=0)作为L的表头游标。。这样，我们就可以用游标来模拟指针，实现单链表中的各种运算。当i>1时，表示第i个位置的位置变量pi的值是数组alist中存储表L的第i-1个元素next值,用p:=alist(p).next后移。照此，我们虽然是用数组来存储表中的元素，但在作表的插人和删除运算时，不需要移动元素，只要修改游标，从而保持了用指针实现表的优点。因此，有时也将这种用游标实现的表称为静态链表。
3.循环链表
循环链表是另一种链式存储结构，特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。因此，可由表中任一结点出发均可找到表中其他结点。如图6所示的是一个单链的循环链表或简称为单循环链表。
(a)非空表
(b)空表
图6单循环链表
在单循环链表上实现表的各种运算的算法与单链表的情形是类似的。它们仅在循环终止条件上有所不同:前者是p或p^.next指向表头单元；后者是p或p^.next指向空(nil)。在单链表中我们用指向表头单元的指针表示一个表L，这样就可以在O(1)时间内找到表L中的第一个元素。然而要找到表L中最后一个元素就要花O(n)时间遍历整个链表。在单循环链表中，我们也可以用指向表头单元的指针表示一个表L。但是，如果我们用指向表尾的指针表示一个表L时，我们就可以在O(1)时间内找到表上中最后一个元素。同时通过表尾单元中指向表头单元的指针，我们也可以在O(1)时间内找到表L中的第一个元素。在许多情况下，用这种表示方法可以简化一些关于表的运算。
4.双链表
单循环链表中，只有一个指示直接后继的指针域，虽然从任一单元出发，可以找到其前驱单元，但需要O(n)时间。如果我们希望能快速确定表中任一元素的前驱和后继元素所在的单元，可以在链表的每个单元中设置两个指针，一个指向后继，另一个指向前驱，形成图8所示的双向链表或简称为双链表。
图8 双链表
由于在双链表中可以直接确定一个单元的前驱单元和后继单元，我们可以用一种更自然的方式表示元素的位置，即用指向双链表中第i个单元而不是指向其前一个单元的指针来表示表的第i个位置。
双链表的单元类型定义如下。

和单链的循环表类似，双链表也可以有相应的循环表。我们用一个表头单元将双链表首尾相接，即将表头单元中的previous指针指向表尾，并将表尾单元的next指针指向表头单元，构成如图9所示的双向循环链表。
图9 双向循环链表
下面仅以双向循环链表为例给出三种基本运算的实现。
(1)在双向循环链表L的位置p处插入一个新元素x的过程Insert可实现如下。

上述算法对链表指针的修改情况见图10。
图10 在双向循环链表中插入一个元素
算法Insert中没有检查位置p的合法性，因此在调用Insert之前应保证位置p的合法性。由于插入通常是在表的头尾两端进行的，所以容易检查位置p的合法性。
(2)从双向循环链表L中删除位置p处的元素可实现如下:
上述算法对链表指针的修改情况见图11。
图11 从双向循环链表中删除一个元素
5.链表的应用
例1：求 (A-B)U(B-A)其中A,B代表两个集合（用静态链表）
例2 求p1(x)+p2(x) (两个多项式的和）
练习题：
1.约瑟夫问题:
有M个猴子围成一圈，每个有一个编号，编号从1到M。打算从中选出一个大王。经过协商，决定选大王的规则如下：从第一个开始，每隔N个，数到的猴子出圈，最后剩下来的就是大王。
要求：从键盘输入M，N，编程计算哪一个编号的猴子成为大王。(_?¨????_）
2.求多项式的减与乘法.(_?¨????_）
第3章 栈
栈是一种特殊的线性表，它的逻辑结构与线性表相同，只是其运算规则较线性表有更多的限制，故又称它为运算受限的线性表。
3.1 栈的概念及运算
栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。向栈中插入元素称为进（入）栈，从栈中删除元素称为退（出）栈。
通常插入、删除的这一端称为栈顶，由于元素的进栈和退栈，使得栈顶的位置经常是变动的，因此需要用一个整型量Top指示栈顶的位置，通常称Top 为栈顶指针；另一端称为栈底。
当表中没有元素时称为空栈，即Top=-1。
栈的修改是按后进先出的原则进行。每次删除的总是当前栈中“最新”的元素，即最后插入的元素，而最先插入的是被放在栈的底部，要到最后才能删除。。
假设一个栈S中的元素为an,an-1,..,a1，则称a1为栈底元素，an为栈顶元素。栈中的元素按a1 ,a2,..,an-1,an的次序进栈。在任何时候，出栈的元素都是栈顶元素。换句话说，栈的修改是按后进先出的原则进行的，如图1所示。因此，栈又称为后进先出(Last In First Out)表，简称为LIFO表。所以，只要问题满足LIFO原则，就可以使用栈。　

图1
栈的运算：为一种抽象数据类型，常用的栈运算有:
运算 含义
inistack(S) 使S成为一个空栈。
getTop(S) 这是一个函数，函数值为S中的栈顶元素。
Pop(S) 从栈S中删除栈顶元素，简称为抛栈。
Push(S,x) 在S的栈顶插入元素x，简称为将元素x入栈。
Empty(S) 这是一个函数。当S为空栈时，函数值为true，否则函数值为false。
3.2 栈的存储与实现
1.顺序栈及基本操作的实现
由于栈是运算受限线性表，因此线性表的存储结构对栈也适用，而线性表有顺序存储和链式存储两种，所以，栈也有顺序存储和链式存储两种。
（1）顺序栈：栈的顺序存储结构简称为顺序栈，它是运算受限的顺序表。
（2）顺序栈的描述
#define StackSize 100 //假定栈空间最多为100个元素
typedef char DataType;//假定栈元素的类型为字符类型
typedef struct{
DataType data[StackSize];//栈元素定义
int top;//栈指针定义
}SeqStack;
SeqStack *S;// 定义栈S
设S是SeqStack类型的指针变量，则栈顶指针可表示为S-> top；若栈底位置在向量的低端，则S->data[0]是栈底元素，栈顶元素可表示为S->data[S-> top]。
注意：
①有元素x进栈时，需要先将S->top加1，然后再将元素进栈，即依次完成下列操作：++S->top;S->data[S-> top]=x;。
②当栈顶元素做退栈操作后，需要将S->top减1，即完成操作：S->top--;。
③条件S->top==StackSize-1表示栈满；S->top==-1表示栈空。
④当栈满时，再做进栈运算所产生的空间溢出现象称为上溢。上溢是一种出错状态，应设法避免。
⑤当栈空时，做退栈运算所产生的溢出现象称为下溢。
3、顺序栈上基本运算的算法
①置栈空
void InitStack（SeqStack *S）{//将顺序栈置空
???? S->top=-1;
}
②判栈空
如果栈S为空，则S->top==-1，此时应该返回1，而关系表达式S->top==-1的值为1；如果栈S为非空，则S->top!=-1，此时应该返回0，而关系表达式S->top==-1的值为0，因此，无论怎样只需返回S->top==-1的值。
int StackEmpty（SeqStack *S）{
return S->top==-1;
}
③判栈满
与判栈空的道理相同，只需返回S->top==StackSize-1。
int StackFull（SeqStack *S）{
return S->top==StackSize-1;
}
④进栈
进栈操作需要将栈和进栈元素的值作为函数参数，由于使用栈指针作为函数参数，对栈进行操作，所以进栈函数不需要有返回值；进栈操作时，需要判断是否栈满，当栈不满时，先将栈顶指针加1，再进栈。
int Push（SeqStack *S，DataType x）{
if (StackFull(S))
{puts("栈满"); return 0;}
S->data[++S->top]=x;//栈顶指针加1后将x入栈
return 1;
}
⑤退栈
退栈操作需要将栈指针作为函数参数，并返回栈顶元素的值，所以函数返回值的类型为DataType；退栈操作时，需要判断是否栈空，当栈不空时，先退栈，再将栈顶指针减1，可以先将栈顶元素的值记录下来，然后栈顶指针减1，最后返回记录下来的值，也可以像给出的退栈函数那样来操作。
DataType Pop（SeqStack * S）{
if(StackEmpty(S))
{puts("栈空"); return 0;}
return S->data[S->top--];//返回栈顶元素并将栈顶指针减1
}
⑥取栈顶元素
取栈顶元素与退栈的区别在于，退栈需要改变栈的状态，而取栈顶元素不需要改变栈的状态。
DataType StackTop（SeqStack *S）{
if(StackEmpty(S))
{puts("栈空"); return 0;}
return S->data[S->top];
}
由于栈的插入和删除操作具有它的特殊性，所以用顺序存储结构表示的栈并不存在插入删除数据元素时需要移动的问题，但栈容量难以扩充的弱点仍就没有摆脱。
例 元素a1，a2，a3，a4依次进入顺序栈，则下列不可能的出栈序列是
A．a4, a3, a2, a1 B．a3, a2, a4, a1
C．a3, a4, a2, a1 D．a3, a1, a4, a2
分析：对于A，由于元素a1，a2，a3，a4依次进栈，而a4先出栈，说明a1，a2，a3已经入栈，所以出栈顺序只能是a4，a3，a2，a1，因此A是正确的出栈序列；对于B，C，D，由于都是a3先出栈，说明a1，a2已经入栈，所以a1，a2的相对位置一定是不变的，这就是a2一定在a1之前出栈，比较上述三个答案，只有D中的a1出现在a2的前面，这显然是错误的。因此，答案为D。
2.链栈及基本操作的实现
若栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。用链式存储结构表示的栈称作“链栈”。链栈通常用一个无头结点的单链表表示。
由于栈的插入删除操作只能在一端进行，而对于单链表来说，在首端插入删除结点要比尾端相对地容易一些，所以，我们将单链表的首端作为栈顶端，即将单链表的头指针作为栈顶指针。链栈如图3.2。
（1）链栈：栈的链式存储结构称为链栈，它是运算受限的单链表，其插入和删除操作仅限制在表头位置上进行，栈顶指针就是链表的头指针。
（2）链栈的描述
typedef char DataType;//假定栈元素的类型为字符类型
typedef struct stacknode{//结点的描述
DataType data;
struct stacknode *next;
}StackNode;
typedef struct{//栈的描述
StackNode??*top;? //栈顶指针
}LinkStack;
LinkStack *S; //定义指向链栈的指针S
设S是LinkStack类型的指针变量，则S是指向链栈的指针，链栈栈顶指针可表示为S-> top；链栈栈顶元素可表示为S-> top ->data。
设p是StackNode类型的指针变量，则p是指向链栈某结点的指针，该结点的数据域可表示为p ->data，该结点的指针域可表示为p -> next。
注意：
①LinkStack结构类型的定义是为了方便在函数体中修改top指针本身。
②若要记录栈中元素个数，可将元素个数属性作为LinkStack类型中的成员定义。
③条件S->top== NULL表示空栈，链栈没有栈满的情况。
3、链栈上基本运算的算法
①置栈空
void InitStack（LinkStack *S）{//将链栈置空
S->top=NULL;
}
②判栈空
int StackEmpty（LinkStack *S）{
return S->top==NULL;
}
③进栈
void Push（LinkStack *S，DataType x ）{//将元素x插入链栈头部
StackNode *p=(StackNode *)malloc(sizeof(StackNode));
p->data=x;
p->next=S->top;//将新结点*p插入链栈头部
S->top=p; //栈顶指针指向新结点
}
④退栈
DataType Pop（LinkStack *S）{
DataType x;
StackNode *p=S->top;//保存栈顶指针
if(StackEmpty(S))
{puts(“栈空”); return 0;}//下溢，退出运行
x=p->data;? //保存栈顶结点数据
S->top=p->next;? //将栈顶结点从链上摘下
free(p);
return x;
}
⑤取栈顶元素
DataType StackTop（LinkStack *S）{
if(StackEmpty(S))
{puts(“栈空”); return 0;}
return S->top->data;
}
注：由于链栈中的结点是动态分配的，可以不考虑上溢，所以无须定义StackFull运算。
3.3 栈的应用
1.数值转换
十进制整数N向其它进制数d(二、八、十六)的转换是计算机实现计算的基本问题。
转换法则：该转换法则对应于一个简单算法原理:n=(n div d)*d+n mod d
其中：div为整除运算,mod为求余运算
例如 (1348)10= (2504)8，其运算过程如下：
n n div 8 n mod 8
1348 168 4
168 21 0
21 2 5
2 0 2
采用静态顺序栈方式实现
void conversion(int n , int d) { /*将十进制整数N转换为d(2或8)进制数*/
SqStack S ; int k, *e ;
S=Init_Stack();
while (n>0) { k=n%d ; push(S , k) ; n=n/d ;
} /* 求出所有的余数，进栈 */
while (S.top!=0) { /* 栈不空时出栈，输出 */
pop(S, e) ;
printf(“%1d” , *e) ;
}
}
2.表达式的求值
问题:能否设计算法，编制一个程序，让计算机扫描如下表达式，并将其值打印出来。
　　# 3 * ( 4 + 8 ) / 2 -5 #
　　注：给表达式设置#，标志扫描的开始和结束。
这个表达式的计算顺序是：3*（4+8）/2-5=3*12/2-5=36/2-5=18-5=13
任何一个表达式都是由操作数、运算符和界位符组成的，操作数可以使一些常数也可以使一些变量或是常量的标示符，运算符则分为算数运算符、关系运算符和逻辑运算符；基本界位符有左右括号和表达式结束。一般将运算符和界位符看做是界符。
　　提示算法：为实现算符优先算法，可以实现2个工作栈，一个是操作数栈opnd，用来存放操作数，如3、4、8等，另一个是运算符栈optr，用来存放运算符。
　　首先将标志“#”进运算符栈的栈底。
　　然后依次扫描，按照栈的后进先出原则进行：
　　（1）遇到操作数，进操作数栈；
　　（2）遇到运算符时，则需将此运算符的优先级与栈顶运算符的优先级比较，
　　若若高于栈顶元素则进栈，继续扫描下一符号，
　　否则，将运算符栈的栈顶元素退栈，形成一个操作码Q，同时操作数栈的栈顶元素两次退栈，形成两个操作数a、b，让计算机对操作数与操作码完成一次运算操作，即aQb，并将其运算结果存放在操作数栈中……
模拟计算机处理算术表达式过程。从键盘上输入算术表达式串（只含＋、－、×、÷运算符，充许含括号），输出算术表达式的值。设输入的表达式串是合法的。
附源程序：
3.背包问题
问题：假设有n件质量分配为w1，w2，...，wn的物品和一个最多能装载总质量为T的背包，能否从这n件物品中选择若干件物品装入背包，使得被选物品的总质量恰好等于背包所能装载的最大质量，即wi1+wi2+...+wik=T。若能，则背包问题有解，否则无解。
　　算法思想：首先将n件物品排成一列，依次选取；若装入某件物品后，背包内物品的总质量不超过背包最大装载质量时，则装入（进栈）；否则放弃这件物品的选择，选择下一件物品试探，直至装入的物品总和正好是背包的最大转载质量为止。这时我们称背包装满。
　　若装入若干物品的背包没有满，而且又无其他物品可以选入背包，说明已装入背包的物品中有不合格者，需从背包中取出最后装入的物品（退栈），然后在未装入的物品中挑选，重复此过程，直至装满背包（有解），或无物品可选（无解）为止。
　　具体实现：设用数组weight[1..N]，stack[1,N]分别存放物品重量和已经装入背包（栈）的物品序号，MaxW表示背包的最大装载量。每进栈一个物品，就从MaxW中减去该物品的质量,设i为待选物品序号,若MaxW-weight[i]>=0，则该物品可选；若MaxW-weight[i] < 0，则该物品不可选,且若i>n，则需退栈，若此时栈空，则说明无解。
练习:完整完成背包问题
第4章 队列
队列与栈一样都是运算受限的线性表，但与栈的限制不同。
4.1 队列的概念及运算
队列是一种特殊的线性表，对这种线性表，删除操作只在表头(称为队头)进行，插入操作只在表尾(称为队尾)进行。队列的修改是按先进先出的原则进行的，所以队列又称为先进先出(First In First Out)表，简称FIFO表。
假设队列为a1,a2,..,an，那么a1就是队头元素，an为队尾元素。队列中的元素是按a1,a2,..,an的顺序进入的，退出队列也只能按照这个次序依次退出。也就是说，只有在a1离开队列之后，a2才能退出队列，只有在a1,a2,..,an-1都离开队列之后，an才能退出队列。图1是队列的示意图。
图1
队列的运算：
为一种抽象数据类型，常用的队列运算有:
　
4.2 队列的存储与实现
队列是一种特殊的表，因此凡是可以用来实现表的数据结构都可以用来实现队列。不过，队列的中的元素的个数通常不固定，因此常用循环数组和链表两种方法实现队列。
1.顺序队列及基本操作
（1）顺序队列：队列的顺序存储结构称为顺序队列，它是运算受限的顺序表。
（2）顺序队列的表示
①和顺序表一样，顺序队列用一个数组来存放当前队列中的元素。
②由于随着入队和出队操作的变化，队列的队头和队尾的位置是变动的，所以应设置两个整型量front和rear分别指示队头和队尾在向量空间中的位置，它们的初值在队列初始化时均应置为0。通常称front为队头指针，称rear为队尾指针。
（3）顺序队列的基本操作
①入队：入队时将新元素插入rear所指的位置，然后将rear加1。
②出队：出队时删去front所指的元素，然后将front加1并返回被删元素。
注意：
①当头尾指针相等时，队列为空。
②在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。
顺序队列基本操作如图3.3。
（4）顺序队列中的溢出现象
①“下溢”现象：当队列为空时，做出队操作产生的溢出现象。
②“真上溢”现象：当队列满时，做入队操作产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。
③“假上溢”现象：由于入队和出队操作中，头尾指针只增加不减少，致使被删元素的空间永远无法重新利用。当队列中实际元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为“假上溢”现象。
（5）解决“假上溢”现象的方法
①当出现“假上溢”现象时，把所有的元素向低位移动，使得空位从低位区移向高位区，显然这种方法很浪费时间。
②把队列的向量空间的元素位置0~Queuesize-1看成一个首尾相接的环形，当进队的队尾指针等于最大容量，即rear==Queuesize时，使rear=0。
2.循环队列
（1）循环队列：把向量空间的元素位置首尾相接的顺序队列称为循环队列。
例如，设队列的容量Queuesize=8，元素a1，a2，a3，a4，a5，a6，a7依次入队，然后a1，a2，a3出队的循环队列如图3.4。
（2）循环队列头尾指针的操作
循环队列Q进行出队、入队操作时，头尾指针仍要加1。当头尾指针指向向量上界（QueueSize-1）时，其加1操作的结果是指向向量的下界0。这种循环意义下的加1操作可以描述为：
①利用选择结构
if(i+1==QueueSize)//i为Q->front或Q->rear
i=0;
else
i++;
②利用模运算
i=(i+1)%QueueSize;//i为Q->front或Q->rear
我们将采用此方法实现循环意义下的队头、队尾指针的加1操作。
（3）循环队列边界条件的处理方法
循环队列Q中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件Q->front== Q->rear来判别队列是“空”还是“满”。解决这个问题的方法至少有三种：
①另设一标志变量flag以区别队列的空和满，比如当条件Q->front== Q->rear成立，且 flag 为0时表示队列空，而为1时表示队列满。
②少用一个元素的空间。约定入队前，测试尾指针在循环意义下加1后是否等于队头指针，若相等则认为队满（注意：rear所指的单元始终为空），此时队空的条件是Q->front== Q->rear，队满的条件是(Q->rear+1)%QueueSize== Q->front。
③使用一个计数器count记录队列中元素的总数，当Q->count ==0时表示队列空；当Q->count ==QueueSize时表示队列满。 我们将使用此方法。
（4）循环队列的描述
#define QueueSize 100?? //定义队列最大容量
typedef char DataType;? //定义队列元素类型
typedef struct cirqueue{
DataType data[QueueSize];//队列元素定义
int front; //队头指针定义
int rear; //队尾指针定义
int count; //计数器定义
}CirQueue;
CirQueue *Q; //定义循环队列Q
设Q是CirQueue类型的指针变量，则Q是指向循环队列的指针，队头指针、队尾指可分别表示为Q->front、Q-> rear，计数器可表示为Q-> count，队头元素可表示为Q->data[Q->front]，队尾元素可表示为Q->data[Q-> rear]。
（5）循环队列的基本运算的算法
① 置队空
void InitQueue(CirQueue *Q){
Q->front=Q->rear=0;
Q->count=0;???? //计数器置0
}
② 判队空
int QueueEmpty(CirQueue *Q){
return Q->count==0;? //队列无元素为空
}
③ 判队满
int QueueFull(CirQueue *Q){
return Q->count==QueueSize;?//队中元素个数等于QueueSize时队满
?}
④ 入队
int EnQueue(CirQueue *Q,DataType x){
if(QueueFull(Q))?
{puts(“队满”); return 0;} ???? //队满上溢
Q->count ++;?? //队列元素个数加1
Q->data[Q->rear]=x;? //新元素插入队尾
Q->rear=(Q->rear+1)%QueueSize;? //循环意义下将尾指针加1
return 1;
}
⑤ 出队
DataType DeQueue(CirQueue *Q){
DataType temp;
if(QueueEmpty(Q))
{puts(“队空”); return 0;} //队空下溢
temp=Q->data[Q->front];
Q->count--; //队列元素个数减1
Q->front=(Q->front+1)%QueueSize;?? //循环意义下的头指针加1
return temp;
}
⑥取队头元素
DataType QueueFront(CirQueue *Q){
if(QueueEmpty(Q))
{puts(“队空”); return 0;}
return Q->data[Q->front];
}
3．链队列及基本操作的实现
（1）链队列：队列的链式存储结构称为链队列，它是限制仅在表头删除和表尾插入的单链表。由于需要在表尾进行插入操作，所以为操作方便除头指针外有必要再增加一个指向尾结点的指针。
（2）链队列的描述
typedef char DataType; //定义队列元素类型
typedef struct queuenode{//队列中结点的类型
DataType data;
struct queuenode *next;
}QueueNode;
typedef struct{
QueueNode *front;?//队头指针
QueueNode *rear;? //队尾指针
}LinkQueue;
LinkQueue *Q; //定义链队列Q
设Q是LinkQueue类型的指针变量，则Q是指向链队列的指针，队头指针、队尾指可分别表示为Q->front、Q-> rear。
设p是QueueNode类型的指针变量，则p是指向链队列某结点的指针，该结点的数据域可表示为p ->data，该结点的指针域可表示为p -> next。
（3）链队列示意图
链队列如图3.5。
（4）链队列的基本运算
由于链队列结点的存储空间是动态分配的，所以无须考虑判队满的运算。
①置空队
void InitQueue(LinkQueue *Q){
????? Q->front=Q->rear=NULL;
}
②判队空
int QueueEmpty(LinkQueue *Q){
return Q->front==NULL&&Q->rear==NULL;//实际上只须判断队头指针是否为空即可
}
③入队
void EnQueue(LinkQueue *Q,DataType x){//将元素x插入链队列尾部
QueueNode *p;
p=(QueueNode *)malloc(sizeof(QueueNode));
p->data=x;?? p->next=NULL;
if(QueueEmpty(Q))
Q->front=Q->rear=p;? //将x插入空队列
else { //x插入非空队列的尾
Q->rear->next=p;???? //*p链到原队尾结点后
Q->rear=p;?????????? //队尾指针指向新的尾
}
}
④出队
DataType DeQueue (LinkQueue *Q){
DataType x;
QueueNode *p;
if(QueueEmpty(Q))
{puts(“队空”); return 0;}
p=Q->front;?????//指向队头结点
x=p->data;???????//保存队头结点的数据
Q->front=p->next;??//将对头结点从链上摘下
if(Q->rear==p)//原队中只有一个结点，删去后队列变空，此时队头指针已为空
Q->rear=NULL;
free(p);?? //释放被删队头结点
return x;? //返回原队头数据
?}
⑤取队头元素
DataType QueueFront(LinkQueue *Q)
{
if(QueueEmpty(Q))
{puts(“队空”); return 0;}
return Q->front->data;
}
注意：在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。
4.3 队列的应用
例1：一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。
如:阵列
0234500067
1034560500
2045600671
0000000089
有4个细胞。
算法步骤：
1． 从文件中读入m*n矩阵阵列，将其转换为boolean矩阵存入bz数组中；
2． 沿bz数组矩阵从上到下，从左到右，找到遇到的第一个细胞；
3． 将细胞的位置入队h，并沿其上、下、左、右四个方向上的细胞位置入队，入队后的位置bz数组置为FLASE；
4． 将h队的队头出队，沿其上、下、左、右四个方向上的细胞位置入队，入队后的位置bz数组置为FLASE；
5． 重复4，直至h队空为止，则此时找出了一个细胞；
6． 重复2，直至矩阵找不到细胞；
7． 输出找到的细胞数。
程序：练习：如下图：求图中被*围成的封闭区域的面积（方格的个数不包括*所在的方格，且*不在最外一层）。
第5章 树和二叉树
树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并具有层次关系的结构。它非常类似于自然界中的树。
树型结构在客观世界中是大量存在的，在计算机领域中也有着广泛的应用，如在编译程序中，用树来表示源程序的语法结构；在数据库系统可用树来组织信息。
5.1树的概念
1.树的递归定义
树是n(n≥0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：
①有且仅有一个特定的称为根(Root)的结点；
②其余的结点可分为m(m≥0)个互不相交的有限子集Tl，T2，…，Tm，其中每个子集本身又是一棵树，并称其为根的子树(Subtree)。
注意：树的递归定义刻画了树的固有特性：一棵非空树是由若干棵子树构成的，而子树又可由若干棵更小的子树构成。
2.树结构的基本术语
（1）结点的度
①结点的度：一个结点拥有子树的个数称为该结点的度。
例如图5.1表示的树中结点A的度为3，其它结点的度都为2或0。
②树的度：该树中结点的最大度数称为该树的度。
例如图5.1表示的树的度为3。
③叶子结点：度为零的结点称为叶子结点或终端结点。
例如图5.1表示的树中结点C、E、G、H、I、J都是叶子结点。
④分支结点：度不为零的结点称分支结点或非终端结点。即除叶子结点外的结点均为分支结点。
例如图5.1表示的树中结点A、B、D、F都是分支结点。
⑤内部结点：除根结点之外的分支结点统称为内部结点。
⑥开始结点：根结点又称为开始结点。
例如图5.1表示的树中结点A是开始结点。
（2）结点之间的关系
①孩子结点：树中某个结点的子树的根称为该结点的孩子结点。
例如图5.1表示的树中结点B、C、D都是结点A的孩子结点，结点E、F都是结点B的孩子结点，结点G、H都是结点D的孩子结点。
②双亲结点：孩子结点的根称为该结点的双亲。
例如图5.1表示的树中结点A是结点B、C、D的双亲结点，结点B是结点E、F的双亲结点，结点D是结点G、H的双亲结点。
③兄弟结点：同一个双亲的孩子互称为兄弟结点。
例如图5.1表示的树中结点B、C、D互为兄弟结点，结点E、F互为兄弟结点，而结点F和G非兄弟结点。
④堂兄弟：在后面介绍。
⑤祖先和子孙：在后面介绍。
（3）路径
①路径或道路：若树中存在一个结点序列k1,k2,…,kj,使得ki是ki+1的双亲(1≤i②路径的长度：指路径所经过的边的数目。
注意：若一个结点序列是路径，则在树的树形图表示中，该结点序列“自上而下”地通过路径上的每条边。从树的根结点到树中其余结点均存在一条惟一的路径。
例如图5.1表示的树中结点序列ABFI是结点A到I的一条路径，因为自上而下A是B的双亲，B是F的双亲，F是I的双亲。该路径的长度为3。而结点B和G之间不存在路径，因为既不能从B出发自上而下地经过若干个结点到达G，也不能从G出发自上而下地经过若干个结点到达B。
③祖先和子孙：若树中结点k到ks存在一条路径，则称k是ks的祖先，ks是k的子孙。一个结点的祖先是从根结点到该结点路径上所经过的所有结点，而一个结点的子孙则是以该结点为根的子树中的所有结点。
约定：结点k的祖先和子孙不包含结点k本身。
（4）结点的层数和树的深度
①结点的层数：根结点的层数为1，其余结点的层数等于其双亲结点的层数加1。
②堂兄弟：双亲在同一层的结点互为堂兄弟。
③树的深度：树中结点的最大层数称为树的深度。
要注意结点的度、树的度和树的深度的区别。
（5）有序树和无序树
若将树中每个结点的各子树看成是从左到右有次序的，则称该树为有序树；否则称为无序树。
若不特别指明，一般讨论的树都是有序树。
（6）森林
森林是m(m≥0)棵互不相交的树的集合。
删去一棵树的根，就得到一个森林；反之，加上一个结点作树根，森林就变为一棵树。
5.2 二叉树
二叉树是树型结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树的特点是每个结点最多只能有两棵子树，且有左右之分。
1.二叉树的定义
（1）二叉树的递归定义
二叉树是n(n≥0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。
（2）二叉树的五种基本形态
二叉树可以是空集；可以有空的左子树或空的右子树；或者左、右子树皆为空。
二叉树的五种基本形态如图5.3。
图中(a)为空二叉树，(b)是仅有一个根结点的二叉树，(c)是右子树为空的二叉树，(d) 是左子树为空的二叉树，(e)是左右子树均非空的二叉树。
2. 二叉树的性质
性质1 二叉树第i层上的结点数目最多为2i-1(i≥1)个。
证明：假设树非空，用数学归纳法证明。
当i=1时，因为第1层上只有一个根结点，而2i-1=20=1。所以命题成立。
假设对所有的j(1≤j根据归纳假设，第i-1层上至多有2i-2个结点。由于二叉树的每个结点至多有两个孩子，故第i层上的结点数至多是第i-1层上的最大结点数的2倍。即j=i时，该层上至多有2?2i-2=2i-1个结点，故命题成立。
性质2 深度为k的二叉树至多有2k-1(k≥1)个结点。
证明：由性质1，第i层至多有2i-1个(1≤i≤k)结点，所以深度为k的二叉树的结点总数至多为20+21+…+2k-1=2k-1个。
性质3 在任意一棵非空二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1。
证明：因为二叉树中所有结点的度数均不大于2，所以结点总数（记为n）应等于0度结点数n0、1度结点数n1和2度结点数n2之和：
n=n0+n1+n2
另一方面，1度结点有一个孩子，2度结点有两个孩子，故二叉树中孩子结点总数是：nl+2?n2，而树中只有根结点不是任何结点的孩子，故二叉树中的结点总数又可表示为：
n=n1+2?n2+1
综合以上两个式子得到：
n0=n2+1
性质3说明：在任意非空二叉树中叶子结点数总比度为2的结点数多1个。
例如，如图5.4所示的二叉树中
叶子结点数为6，度为2的结点数为5，叶子结点数正好比度为2的结点数多1个。
（1）满二叉树：一棵深度为k且有2k-1个结点的二叉树称为满二叉树。
满二叉树的特点：
①每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。
②满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层。
例如，如图5.5所示的二叉树
是一棵深度为4的满二叉树，每一层上的结点数都达到最大值2i-1(i≥1) 。不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层。
（2）完全二叉树
若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。
完全二叉树特点：
①在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树是一棵完全二叉树。
②满二叉树是完全二叉树，但完全二叉树不一定是满二叉树。
③在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。
④深度为k的完全二叉树的前k-1层是深度为k-1的满二叉树，一共有2k-1-1个结点。
例如，如图5.6所示的两颗二叉树中
1）(a)是满二叉树，也是完全二叉树； (b)是完全二叉树，但不是满二叉树。
2）在(a)的最下一层上，从最右边开始连续删去3个结点后得到完全二叉树(b) 。
3）在完全二叉树(b)中，结点6没有左孩子，也一定没有右孩子，即该结点6是叶结点。
4）(b)是深度为4的完全二叉树，它的前3层是深度为3的满二叉树，一共有23-1=7个结点。
性质4 具有n个结点的完全二叉树的深度为或，其中表示取小于等于lgn的整数部分，表示取大于等于lg(n+1)的整数部分，lg表示以2为底的对数。
证明：设所求完全二叉树的深度为k。由完全二叉树特点知：深度为k的完全二叉树的前k-1层是深度为k-1的满二叉树，一共有2k-1-1个结点。
由于完全二叉树深度为k，故第k层上还有若干个结点，因此该完全二叉树的结点个数n>2k-1-1。
另一方面，由性质2知：深度为k的二叉树至多有2k-1(k≥1)个结点，因此，n≤2k-1，
即：2k-1-l又因k-1和k是相邻的两个整数，故有
由此即得：。
另外，由2k-1-l3.二叉树的存储结构：
　　(1) 顺序存储方式
用一组地址连续的存储单元依次“自上而下、自左至右”存储完全二叉树的数据元素。对于完全二叉树上编号为i的结点元素存储在一维数组的下标值为i-1的分量中，如图所示。对于一般的二叉树，将其每个结点与完全二叉树上的结点相对照，存储在一维数组中，如图所示。
(2)链表存储方式，如：设计不同的结点结构可构成不同的链式存储结构。
二叉链表结点。有三个域：一个数据域，两个分别指向左右子结点的指针域，如图6-7(a)所示。
typedef struct BTNode
{ ElemType data ;
struct BTNode *Lchild , *Rchild ;
}BTNode ;
　
4.普通树转换成二叉树：凡是兄弟就用线连起来，然后去掉父亲到儿子的连线，只留下父母到其第一个子女的连线。　　　　　
5.二叉树的遍历运算（递归定义）
(1)先序遍历
访问根；按先序遍历左子树；按先序遍历右子树
算法的递归定义是：
若二叉树为空，则遍历结束；否则
访问根结点
先序遍历左子树(递归调用本算法)；
先序遍历右子树(递归调用本算法)。
void PreorderTraverse(BTNode *T){
if (T!=NULL) {
visit(T->data) ; /* 访问根结点 */
PreorderTraverse(T->Lchild) ;
PreorderTraverse(T->Rchild) ;
}
}
(2)中序遍历
按中序遍历左子树；访问根；按中序遍历右子树
void InorderTraverse(BTNode *T){
if (T!=NULL) {
InorderTraverse(T->Lchild) ;
visit(T->data) ; /* 访问根结点 */
InorderTraverse(T->Rchild) ;
}
}
(3)后序遍历
按后序遍历左子树；按后序遍历右子树；访问根
void PostorderTraverse(BTNode *T){
if (T!=NULL) {
PostorderTraverse(T->Lchild) ;
PostorderTraverse(T->Rchild) ;
visit(T->data) ; /* 访问根结点 */
}
}
例1.用顺序存储方式建立一棵有31个结点的满二叉树，并对其进行先序遍历。　　
例2.用顺序存储方式建立一棵如图所示的二叉树，并对其进行先序遍历。
例3 用链表存储方式生成上述二叉树，中序遍历之。
1.将上述二叉树用广义表表示为A(B(D,E(G)),C(F(,H)))
2.根据广义表串（以#结束）生成二叉树。
5.3二叉树的应用
1. 哈夫曼树与哈夫曼码
树的路径长度：一棵树的每一个叶结点到根结点的路径长度的和。
带权二叉树：给树的叶结点赋上某个实数值（称叶结点的权）。
带权路径长度：各叶结点的路径长度与其权值的积的总和。
哈夫曼树（最优二叉树）：带权路径长度最小的二叉树。
如何构建哈夫树：（思想是：权越大离跟越近）
哈夫曼码：哈夫曼树的非叶结点到左右孩子的路径分别用0，1 表示，从根到叶的路径序列即为哈夫曼码。
哈夫曼码是不会发生译码多义性的不等长编码，广泛应用实际中。
2.排序二叉树
排序二叉树：每一个参加排列的数据对应二叉树的一个结点，且任一结点如果有左（右）子树，则左（右）子树各结点的数据必须小（大）于该结点的数据。中序遍历排序二叉树即得排序结果。程序如下：
3.堆排序
堆：设有数据元素的集合（R1,R2,R3,...Rn)它们是一棵顺序二叉树的结点且有 Ri<=R2i 和Ri<=R2i+1(或>=)
堆的性质：堆的根结点上的元素是堆中的最小元素，且堆的每一条路径上的元素都是有序的。
堆排序的思想是：
1）建初始堆（将结点[n/2],[ n/2]-1,...3,2,1分别调成堆）
2）当未排序完时
输出堆顶元素，删除堆顶元素，将剩余的元素重新建堆。
第6章 图
图(Graph)是一种复杂的非线性结构，在图结构中，对结点的前驱和后继的个数没有任何限制，结点之间的关系是任意的，图中任意两个结点之间都可能有关系。图结构在计算机科学、人工智能、工程、数学、物理等领域中，有着广泛的应用。
6.1图的概念
1.图的二元组定义
图G由两个集合V和E组成，记为：G=(V，E)
其中：V是有限的非空集合，V中的元素称为顶点或结点，E是V中顶点偶对(vi,vj)的集合，E中的元素称为边。
说明：图G的顶点集和边集也可记为V(G)和E(G)。E(G)可以是空集，若为空，则图G只有顶点没有边；图中的边(vi,vj)描述了两个顶点之间是相关的。
图6.1中G1给出了一个图的示例，在该图中：
集合V＝{v1,v2,v3,v4,v5}；
集合E＝{(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5) }。
图6.1 无向图G1 图6.2 有向图G2
2.无向图和有向图
（1）无向图
若图G中的每条边都是没有方向的，则称G为无向图。
无向图中边的表示：无向图中的边均是顶点的无序对，无序对通常用圆括号表示，无序对(vi,vj)和(vj,vi) 表示图中的同一条边。
如图6.1所示图G1是一个无向图。
（2）有向图
若图G中的每条边都是有方向的，则称G为有向图。
有向图中边的表示：有向图中的边是由顶点的有序对组成，有序对通常用尖括号表示，有序对和 表示的是图中不同的边。有向边也称为弧，边的始点称为弧尾，终点称为弧头。
说明：
①若(v1，v2)或是E(G)中的一条边，则要求v1≠v2；
②不允许一条边在图中重复出现；
③不允许在同一个图中既有有向边又有无向边。
如图6.2所示图G2是一个有向图：
G2=(V2,E2)
V2={v1,v2,v3,v4}
E2={,,,}
（3）完全图
①无向完全图：若G是具有n个顶点e条边的无向图，则顶点数与边数的关系为0≤e≤n(n-1)/2。把恰有n(n-1)/2条边的无向图称为无向完全图。
②有向完全图：若G是具有n个顶点e条边的有向图，则顶点数与边数的关系为0≤e≤n(n-1)。把恰有n(n-1)条边的有向图称为有向完全图。
说明：完全图具有最多的边数。任意一对顶点间均有边相连。
3.图的边和顶点的关系
（1）无向边和顶点关系
若(vi,vj)是一条无向边，则称顶点vi和vj互为邻接顶点，或称vi和vj相邻接；并称(vi,vj)依附或关联于顶点vi和vj，或称(vi,vj)与顶点vi和vj相关联。
（2）有向边和顶点关系
若是一条有向边，则称顶点vi邻接到vj，顶点vi邻接于顶点vj；并称边关联于vi和vj或称与顶点vi和vj相关联。
（3）顶点的度
①无向图中顶点v的度：无向图中顶点v的度是关联于该顶点的边的数目，记为D(v)。
②有向图顶点v的入度：有向图中，以顶点v为终点的边的数目称为v的入度，记为ID(v)。
③有向图顶点v的出度：有向图中，以顶点v为始点的边的数目，称为v的出度，记为OD(v)
④有向图顶点v的度：有向图中，顶点v的度定义为该顶点的入度和出度之和，即D(v)=ID(v)+OD(v)。
⑤无论有向图还是无向图，顶点数n、边数e和度数之间有如下关系：
例如，在图6.1无向图G1中有：
D(v1)=2 D(v2)=3 D(v3)=3 D(v4)=2 D(v5)=2
在图6.2有向图G2中有：
ID(v1)=1 OD(v1)=2 D(v1)=3
ID(v2)=1 OD(v2)=0 D(v2)=1
ID(v3)=1 OD(v3)=1 D(v3)=2
ID(v4)=1 OD(v4)=1 D(v4)=2
4.子图
设G=(V，E)是一个图，若V'是V的子集，E'是E的子集，且E'中的边所关联的顶点均在V'中，则G'=(V'，E')也是一个图，并称其为G的子图。
图G1和G2的子图如图6.3所示。


图6.3 图G1和G2的两个子图
5.路径
（1）无向图的路径
在无向图G中，若存在一个顶点序列vp，vi1，vi2，…，vim，vq，使得(vp,vi1)，(vi1,vi2)，…，(vim,vq)均属于E(G)，则称该序列为顶点vp到vq的一条路径。
（2）有向图的路径
在有向图G中，若存在一个顶点序列vp，vi1，vi2，…，vim，vq，使得有向边，，…，均属于E(G) ，则称该序列为顶点vp到vq的一条路径。
（3）路径长度
路径长度定义为该路径上边的数目。
（4）简单路径
若一条路径除两端顶点可以相同外，其余顶点均不相同，则称此路径为一条简单路径。
（5）回路
起点和终点相同的路径称为回路。
（6）简单回路或简单环
起点和终点相同的简单路径称为简单回路或简单环。
（7）有根图和图的根
在一个有向图中，若存在一个顶点v，从该顶点有路径可以到达图中其它所有顶点，则称此有向图为有根图，v称作图的根。
6.连通图和连通分量
（1）顶点间的连通性
在无向图G中，若从顶点vi到顶点vj有路径，则称vi和vj是连通的。
（2）连通图
若在无向图G中，任意两个不同的顶点vi和vj都连通(即有路径)，则称G为连通图。
（3）连通分量
无向图G的极大连通子图称为G的连通分量。示意图见图6.4。
说明：
①任何连通图的连通分量只有一个，即是其自身；
②非连通的无向图有多个连通分量。
7.强连通图和强连通分量
（1）强连通图
有向图G中，若对于V(G)中任意两个不同的顶点vi和vj，都存在从vi到vj以及从vj到vi的路径，则称G是强连通图。
（2）强连通分量
有向图的极大强连通子图称为G的强连通分量。
说明：
①强连通图只有一个强连通分量，即是其自身；
②非强连通的有向图有多个强连分量。
有向图的强连通分量见图6.5。
8.网络
若将图的每条边都赋上一个权，则称这种带权图为网络(Network)。
如图6.6。
说明：权是表示两个顶点之间的距离、耗费等具有某种意义的数。
6.2 图的存储结构
图的存储表示方法很多，这里介绍两种最常用的方法。至于具体选择哪一种方法，主要取决于具体的应用和要施加的操作。
为了适合用C语言描述，以下假定顶点序号从0开始，即n个顶点图G顶点集是V(G)={v0,v1,…,vn-1}。
1.图的邻接矩阵表示法
（1）图的邻接矩阵
设G=(V，E)是具有n个顶点的图，则G的邻接矩阵是元素具有如下性质的n阶方阵：
（2）图的邻接矩阵表示法
①用邻接矩阵表示顶点间的相邻关系；
②用一个顺序表来存储顶点信息。
（3）网络的邻接矩阵
若G是网络，则邻接矩阵可定义为：
其中：wij表示边上的权值；∞表示一个计算机允许的、大于所有边上权值的数。网络的邻接矩阵如图6.8。
【课堂实践6.1】分别写出图6.1的无向图G1和图6.2的有向图G2的邻接矩阵。
（4）图的邻接矩阵存储结构的描述
#define VertexNum 20 //最大顶点数
typedef char VertexType;//顶点类型定义
typedef int EdgeType;//权值类型定义
typedef struct{
VertexType vexs[VertexNum]; //顶点表
EdgeType edges[VertexNum][VertexNum];//邻接矩阵，可看作边表
int n,e;//图中当前的顶点数和边数
}MGraph;
（5）建立无向网络的算法
void CreateMGraph(MGraph *G){//建立无向网(图)的邻接矩阵表示
int i,j,k,w;
scanf("%d%d",&G->n,&G->e); //输入顶点数边数
getchar();
printf("读入顶点信息，建立顶点表:");
for(i=0;in;i++) //读入顶点信息，建立顶点表
G->vexs[i]=getchar();
getchar();
for(i=0;in;i++)
for(j=0;jn;j++)
G->edges[i][j]=0; //邻接矩阵初始化
for(k=0;ke;k++){//读入e条边,建立邻接矩阵
scanf("%d%d%d",&i,&j,&w);//输入权w
G->edges[i][j]=w;
G->edges[j][i]=w;
}
}
2.图的邻接表表示法
（1）图的邻接表
对于图G中的每个顶点vi，把所有邻接于vi的顶点vj链成一个带头结点的单链表，这个单链表就称为顶点vi的邻接表(Adjacency List)。
（2）邻接表的结点结构
①表结点结构
邻接表中每个表结点均有两个域
（1）邻接点域adjvex,存放与vi相邻接的顶点vj的序号j；
（2）链域next,将邻接表的所有表结点链在一起。
注意：若要表示边上的信息(如权值)，则在表结点中还应增加一个数据域。
②头结点结构
顶点vi邻接表的头结点包含两个域
（1）顶点域vertex,存放顶点vi的信息；
（2）指针域firstedge,vi的邻接表的头指针。
（3）无向图的邻接表
对于无向图，vi的邻接表中每个表结点都对应于与vi相关联的一条边。因此，将邻接表的表头向量称为顶点表。将无向图的邻接表称为边表。
图6.7的无向图的邻接表如图6.9。
序号 vertex firstedge
1 3 ∧
0 2 3 ∧


0 1 ∧


注意：n个顶点e条边的无向图的邻接表表示中有n个顶点表结点和2e个边表结点。
（4）有向图的邻接表
对于有向图，vi的邻接表中每个表结点都对应于以vi为始点射出的一条边。因此，将有向图的邻接表称为出边表。
图6.2的有向图G2的邻接表如图6.10(a)。
注意：n个顶点e条边的有向图，它的邻接表表示中有n个顶点表结点和e个边表结点。
（5）有向图的逆邻接表
?在有向图中，为图中每个顶点vi建立一个入边表的方法称逆邻接表表示法。入边表中的每个表结点均对应一条以vi为终点(即射入vi)的边。
图6.2的有向图G2的逆邻接表如图6.10(b)。

（6）图的邻接表存储结构的描述
图的邻接表存储结构的描述
typedef struct node{//边表结点定义
int adjvex; //邻接点域
struct node *next; //链域
//若要表示边上的权，则应增加一个数据域
}EdgeNode;
typedef struct vnode{ //顶点表结点定义
VertexType vertex; //顶点域
EdgeNode *firstedge;//边表头指针
}VertexNode;
typedef VertexNode AdjList[VertexNum];//AdjList是邻接表类型
typedef struct{//邻接表定义
AdjList adjlist;//邻接表
int n,e; //图中当前顶点数和边数
}ALGraph;
（7）建立无向图的邻接表算法
建立无向图的邻接表算法：
void CreateALGraph(ALGraph *G){//建立无向图的邻接表表示
int i,j,k;
EdgeNode *s;
scanf("%d%d",&G->n,&G->e); //读入顶点数和边数
getchar();
for(i=0;in;i++){//建立顶点表
G->adjlist[i].vertex=getchar(); //读入顶点信息
G->adjlist[i].firstedge=NULL;//边表置为空表
}
for(k=0;ke;k++){//建立边表
scanf("%d%d",&i,&j);//读入边(vi,vj)顶点对序号
s=(EdgeNode *)malloc(sizeof(EdgeNode)); //生成边表结点
s->adjvex=j; //邻接点序号为j
s->next=G->adjlist[i].firstedge;
G->adjlist[i].firstedge=s;//将新结点*s插入顶点vi的边表头部
s=(EdgeNode *)malloc(sizeof(EdgeNode));
s->adjvex=i; //邻接点序号为i
s->next=G->adjlist[j].firstedge;
G->adjlist[j].firstedge=s;//将新结点*s插入顶点vj的边表头部
}
}
6.3 图的遍历
从图的某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问，这一过程称为图的遍历。它是许多图的算法的基础。深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。它们对无向图和有向图均适用。由于图中任一顶点都可能和其它顶点相邻接，所以在遍历图时，访问了某顶点之后，有可能顺着某条回路又回到了该顶点。为了避免重复访问同一个顶点，必须记住每个已访问的顶点。为此，可设一向量visited[0…n-1]，该向量的每个元素的初值均为0，如果访问了顶点Vi，就将visited[i]置为1，这样便可通过visited[i]的值来标志顶点Vi是否被访问过。以下假定遍历过程中访问顶点的操作是简单地输出顶点。
1.图的深度优先遍历
假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)。
（1）递归定义
首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。
说明：图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。
（2）深度优先搜索的过程
设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的边(x，y)。若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时，若x不是源点，则回溯到在x之前被访问过的顶点；否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过，若图G是连通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新源点，进行新的搜索过程。
（3）深度优先遍历的递归算法(DFS算法)?
①邻接矩阵表示的深度优先遍历算法
int visited[VertexNum]={0};//定义标志向量
void DFSM(MGraph *G,int i)
{//以vi为出发点进行搜索，设邻接矩阵是0,l矩阵
int j;
printf("%4c",G->vexs[i]);//访问顶点vi
visited[i]=1;
for(j=0;jn;j++) //依次搜索vi的邻接点
if((G->edges[i][j]==1)&&(!visited[j]))
DFSM(G,j); //(vi,vj)∈E，且vj未访问过
}
void DFSTraverse(MGraph *G)
{ //深度优先遍历以邻接矩阵表示G
int i;
for(i=0;in;i++)
visited[i]=0; //标志向量初始化
for(i=0;in;i++)
if(!visited[i]) //vi未访问过
DFSM(G,i); //以vi为源点开始DFSM搜索
}
②邻接表表示的深度优先搜索算法
int visited[VertexNum]={0};//定义标志向量
void DFS(ALGraph *G,int i)
{//以vi为出发点进行深度优先搜索
EdgeNode *p;
printf("%4c",G->adjlist[i].vertex);//访问顶点vi
visited[i]=1; //标记vi已访问
p=G->adjlist[i].firstedge; //取vi边表的头指针
while(p){//依次搜索vi的邻接点vj，这里j=p->adjvex
if (!visited[p->adjvex])//若vi尚未被访问
DFS(G,p->adjvex);//则以vj为出发点向纵深搜索
p=p->next; //找vi的下一邻接点
}
}
void DFSTraverse(ALGraph *G)
{//深度优先遍历以邻接表表示G
int i;
for(i=0;in;i++)
visited[i]=0; //标志向量初始化
for(i=0;in;i++)
if(!visited[i]) //vi未访问过
DFS(G,i); //以vi为源点开始DFS搜索
}
【课堂实践6.3】已知含6个顶点(v0，v1，v2，v3，v4，v5)的无向图的邻接矩阵如下，求从顶点v0出发进行深度优先遍历得到的顶点访问序列。
2.图的广度优先遍历
设图G的初态是所有顶点均未访问过。在G中任选一顶点v为源点，则广度优先遍历可以定义为：
（1）递归定义
首先访问出发点v，接着依次访问v的所有邻接点w1，w2，…，wt，然后再依次访问与wl，w2，…，wt邻接的所有未曾访问过的顶点。依此类推，直至图中所有和源点v有路径相通的顶点都已访问到为止。此时从v开始的搜索过程结束。
若G是连通图，则遍历完成；否则，在图G中另选一个尚未访问的顶点作为新源点继续上述的搜索过程，直至G中所有顶点均已被访问为止。
广度优先遍历类似于树的按层次遍历。采用的搜索方法的特点是尽可能先对横向进行搜索，故称其为广度优先搜索(Breadth-FirstSearch)。相应的遍历也就自然地称为广度优先遍历。
（2）广度优先搜索的过程
在广度优先搜索过程中，设x和y是两个相继要被访问的未访问过的顶点。它们的邻接点分别记为x1，x2，…，xs和y1，y2，…，yt。
为确保先访问的顶点其邻接点亦先被访问，在搜索过程中使用FIFO队列来保存已访问过的顶点。当访问x和y时，这两个顶点相继入队。此后，当x和y相继出队时，我们分别从x和y出发搜索其邻接点x1，x2，…，xs和y1，y2，…，yt，对其中未访者进行访问并将其入队。这种方法是将每个已访问的顶点入队，故保证了每个顶点至多只有一次入队。
（3）广度优先遍历的递归算法(BFS算法)
①邻接矩阵表示的广度优先遍历算法
int visited[VertexNum]={0};//定义标志向量
void BFSM(MGraph *G,int k){//以vk为源点对用邻接矩阵表示的图G进行广度优先搜索
int i,j;
CirQueue Q;
InitQueue(&Q);
printf("%4c",G->vexs[k]);//访问源点vk
visited[k]=1;
EnQueue(&Q,k);
while(!QueueEmpty(&Q)){
i=DeQueue(&Q);//vi出队
for(j=0;jn;j++)//依次搜索vi的邻接点vj
if(G->edges[i][j]==1&&!visited[j]){//vi未访问
printf("%4c",G->vexs[j]);//访问vi
visited[j]=1;
EnQueue(&Q,j);//访问过的vi入队
}
}
}
void DFSTraverse(MGraph *G){//广度优先遍历以邻接矩阵表示G
int i;
for(i=0;in;i++)
visited[i]=0; //标志向量初始化
for(i=0;in;i++)
if(!visited[i]) //vi未访问过
BFSM(G,i); //以vi为源点开始DFSM搜索
}
②邻接表表示的广度优先遍历算法
int visited[VertexNum]={0};//定义标志向量
void BFS(ALGraph*G,int k)
{// 以vk为源点对用邻接表表示的图G进行广度优先搜索
int i;
CirQueue Q;//须将队列定义中DataType改为int
EdgeNode *p;
InitQueue(&Q);//队列初始化
printf("%4c",G->adjlist[k].vertex); //访问源点vk
visited[k]=1;
EnQueue(&Q,k);//vk已访问，将其入队。（实际上是将其序号入队）
while(!QueueEmpty(&Q)){//队非空则执行
i=DeQueue(&Q);//相当于vi出队
p=G->adjlist[i].firstedge;//取vi的边表头指针
while(p){//依次搜索vi的邻接点vj(令p->adjvex=j)
if(!visited[p->adjvex]){ //若vj未访问过
printf("%4c",G->adjlist[p->adjvex].vertex);//访问vj
visited[p->adjvex]=1;
EnQueue(&Q,p->adjvex);//访问过的vj人队
}//endif
p=p->next;//找vi的下一邻接点
}//endwhile
}//endwhile
}
6.4 最小生成树
1.生成树
在图论中，通常将一个无回路的联通图定义成树。无回路的连通图叫做自由树(在自由树中选定一顶点作根，则成为一棵通常的树)。
（1）生成树
如果连通图G的一个子图是一棵包含G的所有顶点的树，则该子图称为G的生成树。
例如：下面是一个连通图G和它的生成树。
G （a） （b）
图 6.12
(a)图是从v0出发按深度优先搜索得到的生成树。
(b)图是从v4出发按深度优先搜索得到的生成树。
说明：
①生成树是连通图的包含图中的所有顶点的极小连通子图；
②图的生成树不惟一。从不同的顶点出发进行遍历，可以得到不同的生成树。
（2）生成树的求解方法
设图G=(V，E)是一个具有n个顶点的连通图。则从G的任一顶点(源点)出发，作一次深度(广度)优先搜索，搜索到的n个顶点和搜索过程中从一个已访问过的顶点vi搜索到一个未曾访问过的邻接点vj，所经过的边(vi，vj)(共n-1条)组成的极小连通子图就是生成树(源点是生成树的根) 。
（3）深度优先生成树和广度优先生成树
由深度优先搜索得到的生成树称为深度优先生成树，简称为DFS生成树；由广度优先搜索得到的生成树称为广度优先生成树，简称为BFS生成树。
2.最小生成树
（1）最小生成树
对于连通的带权图(连通网)G，其生成树也是带权的。生成树T各边的权值总和称为该树的权，记作：
其中：TE表示T的边集，w(u,v)表示边(u,v)的权。
权最小的生成树称为G的最小生成树(Minimum SpannirngTree)。最小生成树可简记为MST。
（2）普里姆(Prim)算法
假设G=(V,E)是连通图，最小生成树为T=(V,TE)，求T的步骤如下：
①初始化：U={u0},TE={Φ}, u0是图G中任意一个顶点；
②在所有u∈U,v∈V-U中，找一条权值最小的边(u’,v’),令TE+{(u’,v’)}=>TE,U+{v’}=>U；
③如果U=V，则算法结束，否则重复步骤②。
普里姆算法的执行过程：
对图6.13(a)的图G，使用普里姆算法求最小生成树T的执行过程如图6.13(b)~(l)。





（3）克鲁斯卡尔(Kruskal)算法
假设G=(V,E)是连通图，最小生成树为T=(V,TE)，求T的步骤如下：
①T的初始状态是只有n个顶点而无边的非连通图T=(V,?)。
②按边长递增的顺序选择E中的边(u,v)加入到T中，要求u、v分属于T的两个连通分量；若u、v是T的当前同一个连通分量中的顶点，则舍去此边。
③重复步骤②直到T中所有顶点都在同一连通分量上为止。
克鲁斯卡尔算法的执行过程：
对图6.13(a)的图G，使用克鲁斯卡尔算法求最小生成树T的执行过程如图6.14(a)~(f)。



说明：Prim算法的时间复杂度与图中边数无关，适合稠密图。Cruskal算法的时间取决于边数，适合于稀疏图。
【课堂实践6.5】分别用Prim算法和Cruskal算法求如图6.8所示的无向带权图的最小生成树。
6.5 最短路径
1.带权图的最短路径问题
（1）带权图的最短路径问题
求两个顶点间长度最短的路径。路径长度是指路径上各边的权值总和。例如，交通网络中常常提出的如下问题就是带权图中求最短路径的问题。
两地之间是否有路相通？
在有多条通路的情况下，哪一条最短？
其中:交通网络可以用带权图表示：图中顶点表示城镇，边表示两个城镇之间的道路，边上的权值可表示两城镇间的距离、交通费用或途中所需的时间等等。
由于交通网络存在有向性，所以一般以有向网络表示交通网络。
（2）源点和终点
习惯上称路径的开始顶点为源点(Source)，路径的最后一个顶点为终点(Destination)。
为了讨论方便，设顶点集V={0，1，…，n-1}，并假定所有边上的权值均是表示长度的非负实数。
2.最短路径问题
（1）单源最短路径问题
已知有向带权图(简称有向网) G=(V，E)，找出从某个源点s∈V到V中其余各顶点的最短路径。后3个问题可由此问题解决。
（2）单目标最短路径问题
找出图中每一顶点v到某指定顶点u的最短路径。
（3）单顶点对间最短路径问题
对图中某对顶点u和v，找出从u到v的一条最短路径。
（4）所有顶点对间最短路径问题
对图中每对顶点u和v，找出从u到v的一条最短路径。
3.迪杰斯特拉(Dijkstra)算法求单源最短路径
由Dijkstra提出的一种按路径长度递增序产生各顶点最短路径的算法。
（1）例子
在有向图6.14有向图中，从源点0到其余各顶点的最短路径如表6.1：
说明：表中源点到各终点的最短路径按递增顺序排列；源点到每个终点的最短路径途径的顶点都已生成最短路径。
（2）按路径长度递增序产生各顶点最短路径
当前正在生成的最短路径上除终点以外，其余顶点的最短路径均已生成(将源点到其自身的路径看作0)。
（3）算法的基本思想
（1）将顶点集V分成 S(开始只包含源点s, S包含的点都是已经计算出最短路径的点) 和 V-S 集合（V-S 包含那些未确定最短路径的点）；
（2）从V-S中选取这样一个顶点w: 满足经过S集合中任意顶点 v到w的路径最短, 即满足{v到w的路径}最小的那个w。 其中v 属于S, w属于V-S。将w 加入S, 并从V-S中移除w；
（3）如此反复，直到V-S变空集为止。
说明：
①开始 S中只有源点s, 从V-S中选取离s最近的点w, 则s直接到w的路径一定最短，将w加入S，并从V-S中移除w；s直接到w的路径一定最短是因为如果存在另一个点w2, 使得 s->w2->w 的路径比s 直接到w短，那么w2就是我们要选取的w。
②设经过算法的一些步骤后S中已有顶点v1,v2,...,vk，V-S中剩下顶点w1,w2,...,wn-k。下面选取V-S中离S集合最近的顶点w，用D[x]表示从源点到x的最短路径长，则w必然满足 D[w]=Min{D[v]+D[v to w]}，将w加入 S集合。这个w 此时一定取得了最短路径D[w], 因为如果有其他的路径，假设是 S集合某路径->wi->w, 那么就应当去选取wi做为该点而不是w。因为 S集合某路径长D[v] + D[v to wi ] < D[v]+D[v to w] 与w满足的公式矛盾。
用迪杰斯特拉算法求单源最短路径的过程：
以图6.13为例说明求解过程：
①设源点为顶点0，
则S={0},V-S={1,2,3,4}；
②从S中的顶点0到V-S的顶点{1,2,3,4}的带
权边{<0,1>(10),<0,3>(30),<0,4>(100)}中取离
0最近的点1,将1加入S，并从V-S中移除1,则S={0,1(10)},V-S={2,3,4}；
③从S中的顶点{0,1}到V-S的顶点{2,3,4}的带权边{<0,3>(30), <0,4>(100),<1,2>(50)}中取离0最近的点3,将3加入S，并从V-S中移除3,则S={0,1(10),3(30)},V-S={2, 4}；
④从S中的顶点{0,1,3}到V-S的顶点{2,4}的带权边
{<0,4>(100),<1,2>(50),<3,2>(20),<3,4>(60)}中取离0最近的点2,将2加入S，并从V-S中移除2,则S={0,1(10), 3(30), 2(50)},V-S={4}；
⑤从S中的 {0,1,3,2}到V-S的顶点{4}的带权边{<0,4>(100), <3,4>(60),<2,4>(10)}中取离0最近的点4,将4加入S，并从V-S中移除4,则S={0,1(10), 3(30),2(50),4(60)},V-S=Φ。
6.6 拓扑排序
对一个有向无环图G进行拓扑排序，是指将G中所有顶点排成一个线性序列，使得对图中任意一对顶点u和v，若∈E(G),则u在线性序列中出现在v之前。通常将这样的线性序列称为满足拓扑次序的序列，简称拓扑序列。若将图中顶点按拓扑次序排成一行，则图中所有的有向边均是从左指向右的。显然，若图中存在有向环，则不可能使顶点满足拓扑次序。
一个有向图经常用来说明事件之间的先后关系。通常将事件表示为顶点，而事件间的依赖关系表示为有向边。若事件u必须先于事件v完成且u完成后直接导致v的发生，则在顶点u和v有一条边，可将u称为v的直接前趋，v称为u的直接后继。1个DAG的拓扑序列通常表示某种方案切实可行。
表6.2 计算机专业的必修课示例
课程代号 课程名称 先修课程
C0 高等数学 无
C1 程序设计基础 无
C2 离散数学 C0,C1
C3 数据结构 C2,C4
C4 程序设计语言 C1
C5 编译技术 C3,C4
C6 操作系统 C3,C8
C7 普通物理 C0
C8 计算机原理 C7
以表6.2为例说明上述的有关概念。该表可用有向图G(见图6.14（a）)更清楚地表示，图中顶点表示课程代号，是一对有向边当且仅当课程i是课程j的先修课程。因为该图是一个DAG，故至少存在一个拓扑序列。一般情况下，一个DAG可能有多个拓扑序列。例如，我们对图6.14（a）的图进行拓扑排序，至少可得到如下的两个（实际上远不止两个）拓扑序列：C0,C1,C2,C4,C3,C5,C7,C8,C6和C0,C7,C8,C1,C4,C2,C3,C6,C5.若某学生每学期只能修一门课程，则该生必须按某一拓扑序列安排学习计划，方能保证学习任一课程时其先修课程均已学过。若将此图按上述的第一个拓扑序列排成一行，则可得到该图的另一表示（见图6.15（b）），使得边均从左指向右。
当有向图存在环时，若将顶点排成一行，则无论如何安排，必定至少有一条边是和其余边反向的，亦即该图的拓扑序列不存在。例如图6.16 (a)图中的有向环重排后如(b)所示，有向边和其它边反向。若有向图被用来表示某项工程实施方案或某项工作计划，则找不到该图的拓扑序列(即含有向环)，就意味着该方案或计划是不可行的。
图6.16 有向环示例
对于一个有向图的拓扑序列仔细分析，我们会发现这样一个事实：在一个拓扑序列里，每个顶点必定出现在它的所有后继顶点之前。因此我们有两种方法对有向图进行拓扑排序。
1.无前趋的顶点优先
该方法的每一步总是输出当前无前趋(即入度为零)的顶点，其抽象算法可描述为：
NonPreFirstTopSort(G){//优先输出无前趋的顶点
while(G中有人度为0的顶点)do{
从G中选择一个人度为0的顶点v且输出之；
从G中删去v及其所有出边；
}
if(输出的顶点数目<|V(G)|)
//若此条件不成立，则表示所有顶点均已输出，排序成功。
Error("G中存在有向环，排序失败！")；
}
注意：无前驱的顶点优先的拓扑排序算法在具体存储结构下，为便于考察每个顶点的入度，

展开更多......

收起↑