nbhkdz.com冰点文库

NOIP高中信息技术竞赛资料 ----数据结构


第 1 章 绪论

第 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

第 1 章 绪论

图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)应该 是算法中频度最大的语句的频度。 ③常用的算法的时间复杂度的顺序

第 1 章 绪论

O(1)<O(lgn)<O(n)<O(n·lgn)<O(n2)<O(n3)<…<O(2n) ④算法的时间复杂度不仅仅依赖于问题的规模, 还与输入实例的初始状态有 关。 例如:在数组 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
(1) (2) (3) (4) (5)

求两个 n 阶方阵的乘积 C=A×B,其算法如下,计算该时间复杂度。
for(i=0; i<n; i++) for(j=0; j<n; j++) {c[i][j]=0; for(k=0; k<n; k++) c[i][j]+=a[i][k]*b[k][j];

程序段:

第 1 章 绪论

}

解:解法 1 计算程序段中的每一行的执行次数。 第(1)行 for(i=0; i<n; i++)中只考虑循环条件表达式 i<n 的执行次数(忽略初 始化表达式 i=0 和修正表达式 i++的执行次数,下同),表达式 i<n 共执行 n+1 次(i 为 0 到 n-1 时该表达式非零,共 n 次,i 为 n 时该表达式为零,共 1 次,合 计执行 n+1 次),所以,第(1)行共执行 n+1 次; 第(2)行 for(j=0; j<n; j++),在第(1)行 for(i=0; i<n; i++)中的表达式 i<n 非零时 (共 n 次)都要执行一遍,而每一遍同样要执行 n+1 次,所以,第(2)行共执行 n (n+1)次; 第(3)行 c[i][j]=0;在表达式 i<n 和 j<n 均非零时执行,共执行 n2 次; 第(4)行 for(k=0; k<n; k++)在表达式 i<n 和 j<n 均非零时执行一遍,而每一遍 同样要执行 n+1 次,所以,第(4)行共执行 n2(n+1)次; 第(5)行 c[i][j]+=a[i][k]*b[k][j]; 在表达式 i<n、j<n 和 k<n 均非零时执行,共 执行 n3 次; 因此,各行执行次数分别为: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<n、j<n 和 k<n 均非零时执行,而表达式 i<n、j<n 和 k<n 均有 n 次非零,所 以,该行共执行 n3 次。因此,该算法的时间耗费 T(n)是矩阵阶数 n 的函数, T(n)=O(n3)。 【课堂实践】分析并计算下面程序段执行的时间复杂度。
i=1; k=0; while(i<=n-1) { k+=10*i; i++; }

第 2 章 线性表

第 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< i<n)是线性表中第 i个数据元素, 在ai之前仅有一个数据元素ai-1, 而在ai之后也仅有一个数据元素ai+1。 称a1称为起始结点,an称为终端结点,i称为ai在线性表中的序号或位置。线性表 中结点的之间的关系就是上述的邻接关系,由于该关系是线性的,我们称线性表 是一种线性结构。 2.线性表的基本运算 (1)线性表初始化 格式:InitList(L) 初始条件:线性表L不存在。 操作结果:构造一个空的线性表L。 (2)求线性表的长度 格式:LengthList(L)

第 2 章 线性表

初始条件:线性表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 按值非递减。

第 2 章 线性表

例如 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 线性表的这种机内表示称做线性表的顺序存储结构或顺序映像,通常,称这 种存储结构的线性表为顺序表。 只要确定了存储线性表的起始位置,线性表中任

第 2 章 线性表

一数据元素可随机存储,所以线性表的顺序结构是一种随机存储的存储结构。 //======线性表的动态顺序存储结构
#define LIST_INIT_SIZE 100 #define LISTINCREMENT Typedef struct{ Elemtype *elem; //存储空间基址 Int length; //当前长度 //当前分配的存储容量 Int listsize; }SqList; 10 // 初始分配量 //分配增量

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; }

第 2 章 线性表

执行删除运算的情形类似。 如果被删除的元素不是表中最后一个元素,则必 须将它后面的所有元素前移一个位置,以填补由于删除所造成的空缺。这两种运 算的时间复杂度均为 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。

第 2 章 线性表

图1 单链表示意图 为了便于实现表的各种运算, 在单链表中位置变量的意义与用数组实现的表 不同。在单链表中位置 i 是一个指针,它所指向的单元是元素 ai-1所在的单元, 而不是元素 ai 所在的单元(i=2,3,…,n)。位置1是指向表头单元 header 的指针。位 置 End(L)是指向单链表 L 中最后一个单元的指针。这样做的目的是为了避免在 修改单链表指针时需要找一个元素的前驱元素的麻烦, 因为在单链表中只设置指 向后继元素的指针,而没有设置指向前驱元素的指针。 单链表存储结构
Typedef struct ElemType data; Struct Lnode *next;//指向后继节点的指针 }Lnode, *LinkList;//线性链表的实质就是指针 Lnode{

基本运算 (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 章 线性表

图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 后移。照此,我们虽然 是用数组来存储表中的元素,但在作表的插人和删除运算时,不需要移动元素, 只要修改游标,从而保持了用指针实现表的优点。因此,有时也将这种用游标实

第 2 章 线性表

现的表称为静态链表。 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 个位置。 双链表的单元类型定义如下。

第 2 章 线性表

和单链的循环表类似, 双链表也可以有相应的循环表。我们用一个表头单元 将双链表首尾相接,即将表头单元中的 previous 指针指向表尾,并将表尾单元的 next 指针指向表头单元,构成如图9所示的双向循环链表。

图9 双向循环链表 下面仅以双向循环链表为例给出三种基本运算的实现。 (1)在双向循环链表 L 的位置 p 处插入一个新元素 x 的过程 Insert 可实现如下。

上述算法对链表指针的修改情况见图10。

图10 在双向循环链表中插入一个元素 算法 Insert 中没有检查位置 p 的合法性,因此在调用 Insert 之前应保证位置 p 的合法性。由于插入通常是在表的头尾两端进行的,所以容易检查位置 p 的合 法性。

第 2 章 线性表

(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章 栈
栈是一种特殊的线性表,它的逻辑结构与线性表相同,只是其运算规则较线 性表有更多的限制,故又称它为运算受限的线性表。

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 入栈。 这是一个函数。当 S 为空栈时,函数值为 true, Empty(S) 否则函数值为 false。

3.2 栈的存储与实现
1.顺序栈及基本操作的实现

第3章 栈

由于栈是运算受限线性表,因此线性表的存储结构对栈也适用,而线性表有 顺序存储和链式存储两种,所以,栈也有顺序存储和链式存储两种。 (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; }

③判栈满

第3章 栈

与判栈空的道理相同,只需返回 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]; }

由于栈的插入和删除操作具有它的特殊性, 所以用顺序存储结构表示的栈并 不存在插入删除数据元素时需要移动的问题, 但栈容量难以扩充的弱点仍就没有

第3章 栈

摆脱。 例 元素 a1,a2,a3,a4 依次进入顺序栈,则下列不可能的出栈序列是 B.a3, a2, a4, a1 D .a3, a1, a4, a2 A.a4, a3, a2, a1 C.a3, a4, a2, a1

分析:对于 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。 top 栈顶
? ^

栈底

图 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。

第3章 栈

注意: ①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){

第3章 栈

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 SqStack n , int d) { /*将十进制整数 N 转换为 d(2 或 8)进制数*/

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 任何一个表达式都是由操作数、运算符和界位符组成的,操作数可以使一些 常数也可以使一些变量或是常量的标示符,运算符则分为算数运算符、关系运算 符和逻辑运算符; 基本界位符有左右括号和表达式结束。一般将运算符和界位符 看做是界符。

第3章 栈

提示算法:为实现算符优先算法,可以实现2个工作栈,一个是操作数栈 opnd,用来存放操作数,如3、4、8等,另一个是运算符栈 optr,用来存放运算 符。 首先将标志“#”进运算符栈的栈底。 然后依次扫描,按照栈的后进先出原则进行: (1)遇到操作数,进操作数栈; (2)遇到运算符时,则需将此运算符的优先级与栈顶运算符的优先级比较, 若若高于栈顶元素则进栈,继续扫描下一符号, 否则,将运算符栈的栈顶元素退栈,形成一个操作码 Q,同时操作数栈的栈 顶元素两次退栈,形成两个操作数 a、b,让计算机对操作数与操作码完成一次 运算操作,即 aQb,并将其运算结果存放在操作数栈中…… 模拟计算机处理算术表达式过程。 从键盘上输入算术表达式串 (只含+、 -、 × 、÷ 运算符,充许含括号) ,输出算术表达式的值。设输入的表达式串是合法的。 附源程序:

第3章 栈

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 章 队列
队列与栈一样都是运算受限的线性表,但与栈的限制不同。

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 章 队列

4.2 队列的存储与实现
队列是一种特殊的表, 因此凡是可以用来实现表的数据结构都可以用来实现 队列。不过,队列的中的元素的个数通常不固定,因此常用循环数组和链表两种 方法实现队列。 1.顺序队列及基本操作 (1)顺序队列:队列的顺序存储结构称为顺序队列,它是运算受限的顺序 表。 (2)顺序队列的表示 ①和顺序表一样,顺序队列用一个数组来存放当前队列中的元素。 ②由于随着入队和出队操作的变化,队列的队头和队尾的位置是变动的,所 以应设置两个整型量 front 和 rear 分别指示队头和队尾在向量空间中的位置,它 们的初值在队列初始化时均应置为 0。通常称 front 为队头指针,称 rear 为队尾 指针。 (3)顺序队列的基本操作 ①入队:入队时将新元素插入 rear 所指的位置,然后将 rear 加 1。 ②出队:出队时删去 front 所指的元素,然后将 front 加 1 并返回被删元素。 注意: ①当头尾指针相等时,队列为空。 ②在非空队列里,队头指针始终指向队头元素,尾指针始终指向队尾元素的 下一位置。 顺序队列基本操作如图 3.3。
A 0 front rear (a)空队列 B 0 1 front (c)A 出队 C 2 3 rear (d)BC 出队 0 1 2 3 t front o rear p 1 2 3 0 front (b)ABC 入队 B 1 C 2 3 rear

第 4 章 队列

图 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。 rear 5 a6 4 a5 a4 2 循环队列 6 a7 7 0 1

3 front 图 3.4 (2)循环队列头尾指针的操作

循环队列 Q 进行出队、入队操作时,头尾指针仍要加 1。当头尾指针指向向 量上界(QueueSize-1)时,其加 1 操作的结果是指向向量的下界 0。这种循环意 义下的加 1 操作可以描述为: ①利用选择结构
if(i+1==QueueSize)//i 为 Q->front 或 Q->rear

第 4 章 队列

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){

第 4 章 队列

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--; Q->front=(Q->front+1)%QueueSize; return temp; } //队列元素个数减 1 //循环意义下的头指针加 1

⑥取队头元素
DataType QueueFront(CirQueue *Q){ if(QueueEmpty(Q)) {puts(“队空”); return 0;}

第 4 章 队列

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。 *Q Q->front Q->rear
^ ^

(a)空链队列 *Q Q->front Q->rear (4)链队列的基本运算 (b)非空链队列 由于链队列结点的存储空间是动态分配的,所以无须考虑判队满的运算。 图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; Q->rear=p; } } //*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; //返回原队头数据 }

第 4 章 队列

⑤取队头元素
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. 输出找到的细胞数。 程序:练习:如下图:求图中被*围成的封闭区域的面积(方格的个数不包括* 所在的方格,且*不在最外一层) 。

第 4 章 队列

第 5 章 树和二叉树

第 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 章 树和二叉树

例如图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<j),则称该结点序列是从kl到kj的一条路径或道路。 ②路径的长度:指路径所经过的边的数目。 注意:若一个结点序列是路径,则在树的树形图表示中,该结点序列“自上 而下” 地通过路径上的每条边。 从树的根结点到树中其余结点均存在一条惟一的 路径。 例如图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 章 树和二叉树

为一棵树。

5.2 二叉树
二叉树是树型结构的一个重要类型。 许多实际问题抽象出来的数据结构往往 是二叉树形式, 即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结 构及其算法都较为简单, 因此二叉树显得特别重要。二叉树的特点是每个结点最 多只能有两棵子树,且有左右之分。 1.二叉树的定义 (1)二叉树的递归定义 二叉树是n(n≥0)个结点的有限集,它或者是空集(n=0),或者由一个根结点 及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。 (2)二叉树的五种基本形态 二叉树可以是空集;可以有空的左子树或空的右子树;或者左、右子树皆为 空。 二叉树的五种基本形态如图5.3。

(a)

(b)

(c) 图5.3

(d) 二叉树的五种基本形态

(e)

图中(a)为空二叉树,(b)是仅有一个根结点的二叉树,(c)是右子树为空的二 叉树,(d) 是左子树为空的二叉树,(e)是左右子树均非空的二叉树。 2. 二叉树的性质 性质 1 二叉树第 i 层上的结点数目最多为 2i-1(i≥1)个。 证明:假设树非空,用数学归纳法证明。 当 i=1 时,因为第 1 层上只有一个根结点,而 2i-1=20=1。所以命题成立。 假设对所有的 j(1≤j<i)命题成立,即第 j 层上至多有 2j-1 个结点,证明 j=i 时 命题亦成立。 根据归纳假设,第 i-1 层上至多有 2i-2 个结点。由于二叉树的每个结点至多 有两个孩子,故第 i 层上的结点数至多是第 i-1 层上的最大结点数的 2 倍。即 j=i 时,该层上至多有 2?2i-2=2i-1 个结点,故命题成立。 性质 2 深度为 k 的二叉树至多有 2k-1(k≥1)个结点。

第 5 章 树和二叉树

证明:由性质 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 所示的二叉树中

图5.4 叶子结点数为 6,度为 2 的结点数为 5,叶子结点数正好比度为 2 的结点数 多 1 个。 (1)满二叉树:一棵深度为 k 且有 2k-1 个结点的二叉树称为满二叉树。 满二叉树的特点: ①每一层上的结点数都达到最大值。即对给定的高度,它是具有最多结点数 的二叉树。 ②满二叉树中不存在度数为 1 的结点, 每个分支结点均有两棵高度相同的子 树,且树叶都在最下一层。 例如,如图 5.5 所示的二叉树

第 5 章 树和二叉树

图5.5 是一棵深度为 4 的满二叉树,每一层上的结点数都达到最大值 2i-1(i≥1) 。不存 在度数为 1 的结点, 每个分支结点均有两棵高度相同的子树,且树叶都在最下一 层。 (2)完全二叉树 若一棵二叉树至多只有最下面的两层上结点的度数可以小于 2,并且最下一 层上的结点都集中在该层最左边的若干位置上,则此二叉树称为完全二叉树。 完全二叉树特点: ①在满二叉树的最下一层上, 从最右边开始连续删去若干结点后得到的二叉 树是一棵完全二叉树。 ②满二叉树是完全二叉树,但完全二叉树不一定是满二叉树。 ③在完全二叉树中,若某个结点没有左孩子,则它一定没有右孩子,即该结 点必是叶结点。 ④深度为 k 的完全二叉树的前 k-1 层是深度为 k-1 的满二叉树, 一共有 2k-1-1 个结点。 例如,如图 5.6 所示的两颗二叉树中

6 6

(a)

(b)

1)(a)是满二叉树,也是完全二叉树; 图5.6 (b)是完全二叉树,但不是满二叉树。 2)在(a)的最下一层上,从最右边开始连续删去 3 个结点后得到完全二叉树

第 5 章 树和二叉树

(b) 。 3)在完全二叉树(b)中,结点 6 没有左孩子,也一定没有右孩子,即该结点 6 是叶结点。 4)(b)是深度为 4 的完全二叉树,它的前 3 层是深度为 3 的满二叉树,一共 有 23-1=7 个结点。 性质 4 具有 n 个结点的完全二叉树的深度为 ?lg n? ? 1 或 ?lg(n ? 1)? ,其中

?lg n? 表示取小于等于 lgn 的整数部分,?lg(n ? 1)? 表示取大于等于 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<n≤2k-1,由此可推出:2k-1≤n<2k,取对数后有:k-1≤lgn<k 又因 k-1 和 k 是相邻的两个整数,故有 k ? 1 ? ?lg n? 由此即得: k ? ?lg n? ? 1 。 另外,由2k-1-l<n≤2k-1得2k-1<n+1≤2k,两边再取对数便可得到 3.二叉树的存储结构: (1) 顺序存储方式

用一组地址连续的存储单元依次“自上而下、 自左至右”存储完全二叉树的数 据元素。对于完全二叉树上编号为 i 的结点元素存储在一维数组的下标值为 i-1 的分量中,如图所示。对于一般的二叉树,将其每个结点与完全二叉树上的结点 相对照,存储在一维数组中,如图所示。

第 5 章 树和二叉树

(2)链表存储方式,如:设计不同的结点结构可构成不同的链式存储结构。 二叉链表结点。 有三个域: 一个数据域, 两个分别指向左右子结点的指针域, 如图6-7(a)所示。
typedef struct BTNode { ElemType data ; *Lchild , *Rchild ; struct BTNode }BTNode ;

4.普通树转换成二叉树: 凡是兄弟就用线连起来, 然后去掉父亲到儿子的连 线,只留下父母到其第一个子女的连线。

5.二叉树的遍历运算(递归定义) (1)先序遍历 访问根;按先序遍历左子树;按先序遍历右子树 算法的递归定义是: 若二叉树为空,则遍历结束;否则 a) 访问根结点 b) 先序遍历左子树(递归调用本算法); c) 先序遍历右子树(递归调用本算法)。

第 5 章 树和二叉树 void PreorderTraverse(BTNode if (T!=NULL) { /* 访问根结点 */ visit(T->data) ; *T){

PreorderTraverse(T->Lchild) ; PreorderTraverse(T->Rchild) ; } }

(2)中序遍历 按中序遍历左子树;访问根;按中序遍历右子树
void if InorderTraverse(BTNode (T!=NULL) { /* 访问根结点 */ *T){

InorderTraverse(T->Lchild) ; visit(T->data) ; } } InorderTraverse(T->Rchild) ;

(3)后序遍历 按后序遍历左子树;按后序遍历右子树;访问根
void PostorderTraverse(BTNode if (T!=NULL) { PostorderTraverse(T->Lchild) ; PostorderTraverse(T->Rchild) ; visit(T->data) ; } } /* 访问根结点 */ *T){

例1.用顺序存储方式建立一棵有31个结点的满二叉树,并对其进行先序遍历。 例2.用顺序存储方式建立一棵如图所示的二叉树,并对其进行先序遍历。

例3 用链表存储方式生成上述二叉树,中序遍历之。 1.将上述二叉树用广义表表示为 A(B(D,E(G)),C(F(,H))) 2.根据广义表串(以#结束)生成二叉树。

5.3 二叉树的应用
1. 哈夫曼树与哈夫曼码 树的路径长度:一棵树的每一个叶结点到根结点的路径长度的和。

第 5 章 树和二叉树

带权二叉树:给树的叶结点赋上某个实数值(称叶结点的权) 。 带权路径长度:各叶结点的路径长度与其权值的积的总和。 哈夫曼树(最优二叉树) :带权路径长度最小的二叉树。 如何构建哈夫树: (思想是:权越大离跟越近) 哈夫曼码:哈夫曼树的非叶结点到左右孩子的路径分别用0,1 表示,从根 到叶的路径序列即为哈夫曼码。 哈夫曼码是不会发生译码多义性的不等长编码,广泛应用实际中。 2.排序二叉树 排序二叉树: 每一个参加排列的数据对应二叉树的一个结点,且任一结点如 果有左(右)子树,则左(右)子树各结点的数据必须小(大)于该结点的数据。 中序遍历排序二叉树即得排序结果。程序如下: 3.堆排序 堆:设有数据元素的集合(R1,R2,R3,...Rn)它们是一棵顺序二叉树的结点且 有 Ri<=R2i 和 Ri<=R2i+1(或>=) 堆的性质: 堆的根结点上的元素是堆中的最小元素,且堆的每一条路径上的 元素都是有序的。 堆排序的思想是: 1)建初始堆(将结点[n/2],[ n/2]-1,...3,2,1分别调成堆) 2)当未排序完时 输出堆顶元素,删除堆顶元素,将剩余的元素重新建堆。

第6章 图

第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) }。
V1 V3 V4 V5 V3 V4 V2 V1 V2

图 6.1

无向图 G1

图 6.2

有向图 G2

2.无向图和有向图 (1)无向图 若图 G 中的每条边都是没有方向的,则称 G 为无向图。 无向图中边的表示:无向图中的边均是顶点的无序对,无序对通常用圆括号 表示,无序对(vi,vj)和(vj,vi) 表示图中的同一条边。 如图6.1所示图G1是一个无向图。 (2)有向图 若图 G 中的每条边都是有方向的,则称 G 为有向图。 有向图中边的表示:有向图中的边是由顶点的有序对组成,有序对通常用尖 括号表示,有序对<vi,vj>和<vj,vi> 表示的是图中不同的边。有向边也称为弧, 边的始点称为弧尾,终点称为弧头。

第6章 图

说明: ①若(v1,v2)或<vl,v2>是 E(G)中的一条边,则要求 v1≠v2; ②不允许一条边在图中重复出现; ③不允许在同一个图中既有有向边又有无向边。 如图6.2所示图G2是一个有向图: G2=(V2,E2) V2={v1,v2,v3,v4} E2={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>} (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>关联于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章 图

e?

1 n ? D (v i ) 2 i ?1

例如,在图6.1无向图G1中有: D(v1)=2 ID(v1)=1 ID(v2)=1 ID(v3)=1 ID(v4)=1 4.子图 设G=(V,E)是一个图,若V'是V的子集,E'是E的子集,且E'中的边所关联的 顶点均在V'中,则G'=(V',E')也是一个图,并称其为G的子图。 图G1和G2的子图如图6.3所示。
V1 V3 V3 V4 V5 V4 V2 V1

D(v2)=3 OD(v1)=2 OD(v2)=0 OD(v3)=1 OD(v4)=1

D(v3)=3 D(v1)=3 D(v2)=1 D(v3)=2 D(v4)=2

D(v4)=2

D(v5)=2

在图6.2有向图G2中有:

图 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,使得有向 边<vp,vi1>,<vi1,vi2>,…,<vim,vq>均属于 E(G) ,则称该序列为顶点 vp 到 vq 的 一条路径。 (3)路径长度 路径长度定义为该路径上边的数目。 (4)简单路径 若一条路径除两端顶点可以相同外,其余顶点均不相同,则称此路径为一条 简单路径。

第6章 图

(5)回路 起点和终点相同的路径称为回路。 (6)简单回路或简单环 起点和终点相同的简单路径称为简单回路或简单环。 (7)有根图和图的根 在一个有向图中,若存在一个顶点 v,从该顶点有路径可以到达图中其它所 有顶点,则称此有向图为有根图,v 称作图的根。 6.连通图和连通分量 (1)顶点间的连通性 在无向图 G 中,若从顶点 vi 到顶点 vj 有路径,则称 vi 和 vj 是连通的。 (2)连通图 若在无向图 G 中,任意两个不同的顶点 vi 和 vj 都连通(即有路径),则称 G 为连通图。 (3)连通分量 无向图 G 的极大连通子图称为 G 的连通分量。示意图见图 6.4。
A C D E F E F B A B C D

(a) 无向图 G3 图 6.4

(b)G3 的两个连通分量 无向图及连通分量

说明: ①任何连通图的连通分量只有一个,即是其自身; ②非连通的无向图有多个连通分量。

7.强连通图和强连通分量
(1)强连通图 有向图 G 中,若对于 V(G)中任意两个不同的顶点 vi 和 vj,都存在从 vi 到 vj 以及从 vj 到 vi 的路径,则称 G 是强连通图。 (2)强连通分量 有向图的极大强连通子图称为 G 的强连通分量。

第6章 图

说明: ①强连通图只有一个强连通分量,即是其自身; ②非强连通的有向图有多个强连分量。 有向图的强连通分量见图 6.5。
V1 V2

V3

V4

8.网络

图 6.5

有向图 G2 的两个强连通分量

若将图的每条边都赋上一个权,则称这种带权图为网络(Network)。 如图 6.6。
8 A 5 C 7 2 B 3 D

图 6.6

一个无向网

说明:权是表示两个顶点之间的距离、耗费等具有某种意义的数。

第6章 图

6.2 图的存储结构
图的存储表示方法很多, 这里介绍两种最常用的方法。至于具体选择哪一种 方法,主要取决于具体的应用和要施加的操作。 为了适合用 C 语言描述,以下假定顶点序号从 0 开始,即 n 个顶点图 G 顶 点集是 V(G)={v0,v1,…,vn-1}。 1.图的邻接矩阵表示法 (1)图的邻接矩阵 设 G=(V,E)是具有 n 个顶点的图,则 G 的邻接矩阵是元素具有如下性质的 n 阶方阵:
?1 A[i, j ] ? ? ?0 (vi , v j )或 ? vi , v j ? 是E (G )中的边 (vi , v j )或 ? vi , v j ? 不是E (G )中的边

(2)图的邻接矩阵表示法 ①用邻接矩阵表示顶点间的相邻关系; ②用一个顺序表来存储顶点信息。
V0 V3

V1

V2

?0 ? ?1 A?? 0 ? ?1 ?

1 0 1 1

0 1 0 0

1? ? 1? 0? ? 0? ?

图 6.7 (3)网络的邻接矩阵

一个无向图的邻接矩阵表示

若 G 是网络,则邻接矩阵可定义为:
(vi , v j )或 ? vi , v j ? 是E (G )中的边 ? wij A[i, j ] ? ? (vi , v j )或 ? vi , v j ? 不是E (G )中的边 ?0或? 其中:wij 表示边上的权值;∞表示一个计算机允许的、大于所有边上权值

的数。网络的邻接矩阵如图 6.8。
9 B 5 D 3 A 4 7 E 6 C

8

?? 9 6 3 ?? ? ? ? 9 ? 4 5 ?? A??6 4 ? ? 7? ? ? ?3 5 ? ? 8? ?? ? 7 8 ?? ? ?

图 6.8

一个网络的邻接矩阵表示

第6章 图

【课堂实践 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;i<G->n;i++) //读入顶点信息,建立顶点表 G->vexs[i]=getchar(); getchar(); for(i=0;i<G->n;i++) for(j=0;j<G->n;j++) G->edges[i][j]=0; //邻接矩阵初始化 for(k=0;k<G->e;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 链成一个带头结点的

第6章 图

单链表,这个单链表就称为顶点 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。
序号
0 1 2 3

vertex V0 V1 V2 V3

firstedge 1 0 1 0 ∧ 1


3 2



3



顶点表 图 6.9

边表 图的邻接表表示

注意: n 个顶点 e

条边的无向图的邻接表表

示中有 n 个顶点表结点和 2e 个边表结点。 (4)有向图的邻接表 对于有向图,vi 的邻接表中每个表结点都对应于以 vi 为始点射出的一条边。 因此,将有向图的邻接表称为出边表。 图 6.2 的有向图 G2 的邻接表如图 6.10(a)。 注意:n 个顶点 e 条边的有向图,它的邻接表表示中有 n 个顶点表结点和 e 个边表结点。 (5)有向图的逆邻接表

第6章 图

在有向图中,为图中每个顶点 vi 建立一个入边表的方法称逆邻接表表示法。 入边表中的每个表结点均对应一条以 vi 为终点(即射入 vi)的边。 图 6.2 的有向图 G2 的逆邻接表如图 6.10(b)。
0 1 2 3 V1 V2 V3 V4 ∧ 3 0 ∧ ∧ 2 1 ∧ 0 1 2 3 V1 V2 V3 V4 3 0 0 2 ∧ ∧ ∧ ∧

(a) 邻接表 图 6.10

(b) 逆邻接表 图 6.2 中 G2 的邻接表和逆邻接表

(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;

第6章 图

scanf("%d%d",&G->n,&G->e); //读入顶点数和边数 getchar(); for(i=0;i<G->n;i++){//建立顶点表 G->adjlist[i].vertex=getchar(); //读入顶点信息 G->adjlist[i].firstedge=NULL;//边表置为空表 } for(k=0;k<G->e;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章 图

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 之前被访问过的顶点;否则图中所有和源点有路径相通的顶点(即从源点可

第6章 图

达的所有顶点)都已被访问过,若图 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;j<G->n;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;i<G->n;i++) visited[i]=0; //标志向量初始化 for(i=0;i<G->n;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 尚未被访问

第6章 图

DFS(G,p->adjvex);//则以 vj 为出发点向纵深搜索 p=p->next; //找 vi 的下一邻接点 } } void DFSTraverse(ALGraph *G) {//深度优先遍历以邻接表表示 G int i; for(i=0;i<G->n;i++) visited[i]=0; //标志向量初始化 for(i=0;i<G->n;i++) if(!visited[i]) //vi 未访问过 DFS(G,i); //以 vi 为源点开始 DFS 搜索 }

【课堂实践 6.3】已知含 6 个顶点(v0,v1,v2,v3,v4,v5)的无向图的邻 接矩阵如下,求从顶点 v0 出发进行深度优先遍历得到的顶点访问序列。 ?0 1 1 0 0 0 ? ?1 0 1 1 0 0 ? ? ? ?1 1 0 0 0 1 ? ? ? ?0 1 0 0 0 0 ? ?0 0 0 0 0 1 ? ? ? ? ?0 0 1 0 1 0 ? ?

2.图的广度优先遍历
设图 G 的初态是所有顶点均未访问过。在 G 中任选一顶点 v 为源点,则广 度优先遍历可以定义为: (1)递归定义 首先访问出发点 v,接着依次访问 v 的所有邻接点 w1,w2,…,wt,然后 再依次访问与 wl,w2,…,wt 邻接的所有未曾访问过的顶点。依此类推,直至 图中所有和源点 v 有路径相通的顶点都已访问到为止。 此时从 v 开始的搜索过程 结束。 若 G 是连通图,则遍历完成;否则,在图 G 中另选一个尚未访问的顶点作 为新源点继续上述的搜索过程,直至 G 中所有顶点均已被访问为止。 广度优先遍历类似于树的按层次遍历。 采用的搜索方法的特点是尽可能先对 横向进行搜索,故称其为广度优先搜索(Breadth-FirstSearch)。相应的遍历也就自

第6章 图

然地称为广度优先遍历。 (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;j<G->n;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;i<G->n;i++) visited[i]=0; //标志向量初始化

第6章 图

for(i=0;i<G->n;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.生成树
在图论中, 通常将一个无回路的联通图定义成树。无回路的连通图叫做自由

第6章 图

树(在自由树中选定一顶点作根,则成为一棵通常的树)。 (1)生成树 如果连通图 G 的一个子图是一棵包含 G 的所有顶点的树,则该子图称为 G 的生成树。 例如:下面是一个连通图 G 和它的生成树。

v0 v3 v6

v1

v2 v3 v6

v0

v1 v4 v5 v7
(a) 图 6.12

v2 v3 v6

v0

v1 v4 v5 v7
(b)

v2

v4 v 5 v7
G

(a)图是从 v0 出发按深度优先搜索得到的生成树。 (b)图是从 v4 出发按深度优先搜索得到的生成树。 说明: ①生成树是连通图的包含图中的所有顶点的极小连通子图; ②图的生成树不惟一。 从不同的顶点出发进行遍历, 可以得到不同的生成树。 (2)生成树的求解方法 设图 G=(V,E)是一个具有 n 个顶点的连通图。则从 G 的任一顶点(源点)出 发,作一次深度(广度)优先搜索,搜索到的 n 个顶点和搜索过程中从一个已访问 过的顶点 vi 搜索到一个未曾访问过的邻接点 vj,所经过的边(vi,vj)(共 n-1 条) 组成的极小连通子图就是生成树(源点是生成树的根) 。 (3)深度优先生成树和广度优先生成树 由深度优先搜索得到的生成树称为深度优先生成树,简称为 DFS 生成树; 由广度优先搜索得到的生成树称为广度优先生成树,简称为 BFS 生成树。

2.最小生成树
(1)最小生成树 对于连通的带权图(连通网)G,其生成树也是带权的。生成树 T 各边的权值 总和称为该树的权,记作: W (T ) ?
( u ,v )?TE

? w(u, v)

第6章 图

其中: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)。 v0 5 v3 6 v1 1 v2 2 v5 6
(a) (b) (c) (d)

v0 v1 6 1 5 v2 7 6 4

v0 5 v3

v0 1 v2

3 v4

v0 v0 v1 6 5 6 1 5 v2 7 4 v3 v0 v1 1 v2 v5 4 v5 v4 6 5 6 6 1 5 v2 7 4 2 v5 v3

v4

(e)

(f)

(g)

v0 v0 v1 1 v2 4 2 v5
(h)

6 v3 5 6 1

v0 v 第6章 图 3 v2 4 6
(i) (j)

v1 5

1

v3 v2 4 2 v5

2 v5

v4

v0 v0 v1 5 3 v4 6 6
(k)

1

v3 v2 4 2 v5 3 v4
(l)

v1 5

1

v3 v2 4 2 v5

图 6.13 普里姆算法的执行过程 (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)。 v1 v2 v0 v3 v1 v0 1 v3 v2

v4
(a)

v5

v4

v5

(b)

v0 v1 1 v3 v2 2 v4
(c)
第6章 图

v0 v1 1 v3 v2 2 v4
(d)

3

v5

v5

v0 v1 1 v3 v2 4 2 v5
(e)

v0 v1 5 3 v4
(f)

1

v3 v2 4 2 v5

3 v4

图 6.14 克鲁斯卡尔算法的执行过程 说明:Prim 算法的时间复杂度与图中边数无关,适合稠密图。Cruskal 算法 的时间取决于边数,适合于稀疏图。 【课堂实践 6.5】分别用 Prim 算法和 Cruskal 算法求如图 6.8 所示的无向带 权图的最小生成树。

第6章 图

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章 图

在有向图 6.14 有向图中,从源点 0 到其余各顶点的最短路径如表 6.1:

表6.1 源点到其他各点的最短路径
10 30 1 10 50 60 2 20 0 3,2 4 60 3 0 0 3 3 2 30 50 4 0 1 10 0 100 源点 0 中间顶点 终点 0 路径长度 0

图 6.14 有向图

说明: 表中源点到各终点的最短路径按递增顺序排列;源点到每个终点的最 短路径途径的顶点都已生成最短路径。 (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 集合。

第6章 图

这个 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.6 拓扑排序
对一个有向无环图 G 进行拓扑排序,是指将 G 中所有顶点排成一个线性序 列,使得对图中任意一对顶点 u 和 v,若<u,v>∈E(G),则 u 在线性序列中出现在 v 之前。通常将这样的线性序列称为满足拓扑次序的序列,简称拓扑序列。若将 图中顶点按拓扑次序排成一行,则图中所有的有向边均是从左指向右的。显然, 若图中存在有向环,则不可能使顶点满足拓扑次序。 一个有向图经常用来说明事件之间的先后关系。通常将事件表示为顶点,而 事件间的依赖关系表示为有向边。 若事件 u 必须先于事件 v 完成且 u 完成后直接 导致 v 的发生,则在顶点 u 和 v 有一条边<u,v>,可将 u 称为 v 的直接前趋,v 称为 u 的直接后继。1 个 DAG 的拓扑序列通常表示某种方案切实可行。 表6.2 计算机专业的必修课示例 课程代号 C0 C1 C2 C3 C4 C5 C6 C7 C8 课程名称 高等数学 程序设计基础 离散数学 数据结构 程序设计语言 编译技术 操作系统 普通物理 计算机原理 先修课程 无 无 C0,C1 C2,C4 C1 C3,C4 C3,C8 C0 C7

以表 6.2 为例说明上述的有关概念。该表可用有向图 G(见图 6.14(a))更清 楚地表示,图中顶点表示课程代号,<i,j>是一对有向边当且仅当课程 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章 图

(a) 有向图 G

(b) G 的拓扑次序排列

图 6.15 表示课程之间依赖关系的有向图 当有向图存在环时,若将顶点排成一行,则无论如何安排,必定至少有一条 边是和其余边反向的,亦即该图的拓扑序列不存在。例如图 6.16 (a)图中的有向 环重排后如(b)所示,有向边<v3,vl>和其它边反向。若有向图被用来表示某项工 程实施方案或某项工作计划,则找不到该图的拓扑序列(即含有向环),就意味着 该方案或计划是不可行的。

图6.16 有向环示例 对于一个有向图的拓扑序列仔细分析,我们会发现这样一个事实:在一个拓 扑序列里, 每个顶点必定出现在它的所有后继顶点之前。因此我们有两种方法对 有向图进行拓扑排序。

1.无前趋的顶点优先
该方法的每一步总是输出当前无前趋(即入度为零)的顶点,其抽象算法可描 述为:
NonPreFirstTopSort(G){//优先输出无前趋的顶点 while(G中有人度为0的顶点)do{ 从G中选择一个人度为0的顶点v且输出之; 从G中删去v及其所有出边; } if(输出的顶点数目<|V(G)|) //若此条件不成立,则表示所有顶点均已输出,排序成功。

第6章 图

Error("G中存在有向环,排序失败!"); }

注意: 无前驱的顶点优先的拓扑排序算法在具体存储结构下,为便于考察每 个顶点的入度,可保存各顶点当前的入度。为避免每次选入度为0的顶点时扫描 整个存储空间,可设一个栈或队列暂存所有入度为零的顶点: 在开始排序前,扫描对应的存储空间,将入度为零的顶点均入栈(队)。以后 每次选入度为零的顶点时,只需做出栈(队)操作即可。

2.无后继的顶点优先
(1)思想方法 该方法的每一步均是输出当前无后继(即出度为0)的顶点。对于一个DAG, 按此方法输出的序列是逆拓扑次序。因此设置一个栈(或向量)T来保存输出的顶 点序列,即可得到拓扑序列。若T是栈,则每当输出顶点时,只需做人栈操作, 排序完成时将栈中顶点依次出栈即可得拓扑序列。若T是向量,则将输出的顶点 从T[n-1]开始依次从后往前存放,即可保证T中存储的顶点是拓扑序列。 (2)抽象算法描述 算法的抽象描述为:
NonSuccFirstTopSort(G){//优先输出无后继的顶点 while(G中有出度为0的顶点)do { 从G中选一出度为0的顶点v且输出v; 从G中删去v及v的所有人边 } if(输出的顶点数目<|V(G)|) Error("G中存在有向环,排序失败!"); }

6.7 图的应用
例1:有 A,B,C,D,E 5本书,要分给张、王、刘、赵、钱5位同学,每人 只选一本。每人将喜爱的书填写下表,输出每人都满意的分书方案。 A B C D E 张 1 1 王 1 1 1 刘 1 1 赵 1

第6章 图

钱 1 1 用递归方式程序如下: 用非递归方法编程如下: 一般的情况的递归方法流程图如下:

非递归方法的流程图如下:

例2: 中国象棋棋盘如下图马自左下角往右上角跳.规定只许往左跳,不许往 右跳(如图 跳法)编程找出所有跳法。

递归算法如下: 非递归算法如下: 例3:找出图3:C1 到 C6的一条经过点最少的路径并求出其路程总长度。

第6章 图

程序如下: 例4:8数码难题 :2 8 3 123 1 6 4 -> 8 4(用最少的步数) 7 5 765 程序如下:

练习: 1.覆盖问题。设有边长为 N(N 为偶数)的正方形用 N*N/2个长为2,宽为1 的长方形覆盖, 打印所有覆盖方案。 如 N=4

2.用深度优先法找出 C1 到 C6的没有重复城市的所有不同路径及路程总长 度。

第6章 图

3.骑士周游世界。在国际象棋的棋盘上,有一位骑士按照国际象棋中马的行走规 则从棋盘上的某一方格出发, 开始在棋盘上周游。若能不重复地走遍棋盘上的每 一个方格,这样的一条周游路线在数学上被称之为国际象棋盘上马的哈密尔顿 链。请你设计一个程序,对于从键盘输入的任意一个起始方格的坐标,由计算机 自动寻找并按如下格式打印出国际象棋盘上马的哈密尔顿链。例如,当马从坐标 点(5,8)出发时,相应的哈密尔顿链如下图所示: ┌───┬───┬───┬───┬───┬───┬───┬───┐ │ 60 │ 11 │ 26 │ 29 │ 54 │ 13 │ 24 │ 21 │ ├───┼───┼───┼───┼───┼───┼───┼───┤ │ 27 │ 30 │ 61 │ 12 │ 25 │ 22 │ 51 │ 14 │ ├───┼───┼───┼───┼───┼───┼───┼───┤ │ 10 │ 59 │ 28 │ 55 │ 50 │ 53 │ 20 │ 23 │ ├───┼───┼───┼───┼───┼───┼───┼───┤ │ 31 │ 64 │ 57 │ 62 │ 43 │ 48 │ 15 │ 52 │ ├───┼───┼───┼───┼───┼───┼───┼───┤ │ 58 │ 9 │ 32 │ 49 │ 56 │ 19 │ 42 │ 1 │ ├───┼───┼───┼───┼───┼───┼───┼───┤ │ 33 │ 6 │ 63 │ 44 │ 47 │ 36 │ 39 │ 16 │ ├───┼───┼───┼───┼───┼───┼───┼───┤ │ 8 │ 45 │ 4 │ 35 │ 18 │ 41 │ 2 │ 37 │ ├───┼───┼───┼───┼───┼───┼───┼───┤ │ 5 │ 34 │ 7 │ 46 │ 3 │ 38 │ 17 │ 40 │ └───┴───┴───┴───┴───┴───┴───┴───┘

第6章 图


NOIP高中信息技术竞赛资料 ----数据结构

NOIP高中信息技术竞赛资料 ---数据结构_学科竞赛_高中教育_教育专区。第 1 章 绪论 第 1 章 绪论程序设计就是使用计算机解决现实世界中的实际问题。 对于给定的...

信息竞赛复习资料4--数据结构(NOIP)

信息竞赛复习资料4--数据结构(NOIP)信息竞赛复习资料4--数据结构(NOIP)隐藏>> 第一章 什么是数据结构 1.1 基本概念和术语 1.数据 数据(data): 数据 是对客...

信息技术竞赛-基础知识整理

信息技术竞赛-基础知识整理_其它课程_高中教育_教育专区。计算机基础知识一、 计算机...高中信息竞赛-数据结构—... 78页 1下载券 2011高中信息技术基本功... 3页...

信息技术竞赛培训教程_数据结构

高中信息竞赛-数据结构—树... 78页 2财富值 信息竞赛复习资料4--数据结.....NOIP实用算法 33页 免费 一个北大学生学习数据结构... 13页 免费如要投诉违规...

信息技术2015数据结构重修辅导资料

信息技术2015数据结构重修辅导资料_其它课程_高中教育_教育专区。信息技术 2014 数据结构重修辅导资料 第一章 绪论第一题:选择题 1、求解下面程序段的时间复杂度。...

信息学奥林匹克竞赛资料(初赛资料)

noip 初赛 复赛 试题 解析青少年信息竞赛简要介绍...注:试题语言两者选一、高中学生必须参加提高组联赛。...四.数据结构数据结构是计算机专业基础课程之一, 是...

广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 07树教案

广东省汕头市金山中学高中信息技术 竞赛数据结构专项培训教程 07树教案_其它...[样例] 输入:abc**d**c** 输出:cbdae c 2、 求先序排列(NOIP2001 普及...

信息学竞赛辅导资料

信息竞赛辅导资料_学科竞赛_高中教育_教育专区。信息...NOIP 是同一时间在全国各个省份同时开展的比赛,1995...中读入数据,并输出到文本文件中) 数据结构 程序设计...

NOIP《 数据结构》练习题及答案

NOIP数据结构》练习题及答案_学科竞赛_初中教育_...C1 数据 结构 C1,C2 编译 技术 C3 操作 系统 C3...东北师大附中理科学霸高中化学选修5笔记80份文档 家装...

高中信息技术奥林匹克竞赛试题

数据信号与地址信号 8.不同类型的存储器组成了多层次结构的存储器体系,按存储...以上都不对 10.NOIP 竞赛推荐使用的语言环境有(ACD) 。 A. Dev-C++ B. ...