数据结构的程序实现

数据结构的程序实现

数据结构是对程序中数据信息的结构组织，供给定问题求解算法的控制结构来处理。Niklauswirth曾经给出“算法+数据结构=程序”的公式，得到了计算机科学界的普遍认可。在程序设计语言中如何表示数据和控制，很大程度上决定了如何使用这个语言来编写程序；所以在程序设计语言中不仅提供了与程序控制流程有关的控制结构，同时也提供了与程序中数据信息组织有关的数据结构。程序设计的主要任务就是在选取或组织适当的数据结构的基础上，利用三种基本结构（顺序、选择、重复）把逐级分解得到的一系列基本操作组织起来，形成用某种特定语言书写的源程序。第1页/共132页数据结构的程序实现全文共132页，当前为第1页。数据结构的程序实现(续)《算法与数据结构》课程讨论数据结构的目的，就是为了在设计给定问题的求解算法时，应用这些数据结构来组织程序中的数据；从而降低问题的分析与设计难度，提高程序（或算法）的设计质量，缩短设计周期。这里就有一个在程序中如何实现各种数据结构的问题。实现是使用的前提，只有在程序中实现了数据结构，才能在程序中利用数据结构对给定问题进行有效地求解。本章将从几个不同的角度讨论如何在程序中实现各种数据结构的问题。第2页/共132页数据结构的程序实现全文共132页，当前为第2页。第9章数据结构的程序实现9.1基本的实现策略9.2动态结构的静态实现9.3大批量数据的组织策略9.4数据结构在问题建模中的应用

第3页/共132页数据结构的程序实现全文共132页，当前为第3页。基本的实现策略

程序设计语言中提供了与程序中数据信息组织有关的数据结构，但没有也不可能提供所有的数据结构。一方面，受科学技术和生产力发展水平的限制，人类认知世界具有历史局限性；人们不可能在某一天完成对现实世界的认知过程，同样也不可能在某一天说对数据结构的认知过程已经完结，这种认知过程是一个渐进式不断深化和逐步完善的过程。另一方面，受计算机科学发展和计算机系统本身的限制，人们不可能研制出一种设施包罗万象、功能应有尽有的计算机语言和语言翻译系统。因此，程序设计语言中只可能提供一些基本的和常用的数据结构设施，并提供一些构造求解现实世界中问题所需数据结构的基本设施和方法手段。

第4页/共132页数据结构的程序实现全文共132页，当前为第4页。9.1基本的实现策略9.1.1简单数据结构的程序实现9.1.2构造型数据结构的程序实现9.1.3数据结构的链式实现9.1.4数据结构的数组实现第5页/共132页数据结构的程序实现全文共132页，当前为第5页。简单数据结构的程序实现

简单的数据结构，在程序设计语言中已经实现了，并作为数据类型提供给程序设计人员。诸如整型数据、实型数据、布尔型数据和字符型数据等等。程序设计人员只要在程序中用相应的类型标识符直接说明程序中数据变量的类型就可以直接使用了，如C语言中的int，unsignedint，longint，shortint，unsignedshortint，char，float和double等。第6页/共132页数据结构的程序实现全文共132页，当前为第6页。9.1基本的实现策略9.1.1简单数据结构的程序实现9.1.2构造型数据结构的程序实现9.1.3数据结构的链式实现9.1.4数据结构的数组实现第7页/共132页数据结构的程序实现全文共132页，当前为第7页。构造型数据结构的程序实现还有一些简单类型和构造类型，也是在程序设计语言中已经实现了的数据结构。如枚举型、子界型、日期型、集合、数组、字符串、记录、文件等。程序设计语言中提供了程序设计人员在程序中说明这些数据类型的方法，程序设计人员只要在程序中的适当位置按照相应的格式和要求对程序中的数据进行说明就可以使用了。如C语言中的枚举、数组、字符串、结构体、共同体、文件等。第8页/共132页数据结构的程序实现全文共132页，当前为第8页。9.1基本的实现策略9.1.1简单数据结构的程序实现9.1.2构造型数据结构的程序实现9.1.3数据结构的链式实现9.1.4数据结构的数组实现第9页/共132页数据结构的程序实现全文共132页，当前为第9页。数据结构的链式实现

其它的数据结构，如链表、循环链表、栈、队列、广义表、树、二叉树、图、网和堆等，在程序设计语言中一般都没有提供其相应的数据类型，程序设计人员不能够在程序中用类型说明的办法直接引入。然而，许多程序设计语言都提供有指针类型，程序设计人员可以利用指针类型在程序中动态建立所需要的某种数据结构。一般地，在建立某种数据结构之前，先需要说明其数据元素的结点类型，如说明成记录、结构体等，再用指针变量动态建立起相应的数据结构，以供求解问题的程序使用或处理。第10页/共132页数据结构的程序实现全文共132页，当前为第10页。9.1基本的实现策略9.1.1简单数据结构的程序实现9.1.2构造型数据结构的程序实现9.1.3数据结构的链式实现9.1.4数据结构的数组实现第11页/共132页数据结构的程序实现全文共132页，当前为第11页。数据结构的数组实现如果在程序设计语言中没有提供指针变量，就不能动态实现程序中需要的数据结构；还有一些数据结构，不宜借助指针来实现，如顺序表、顺序栈、顺序队列等。对于这两种情况，程序设计人员都可以在程序中利用数组模拟实现程序中需要的一些数据结构。

数组是每一种高级程序设计语言都提供了的数据结构。可以利用一维数组模拟实现顺序表、顺序栈、顺序队列。可以利用二维数组模拟实现链表或循环链表，其中一列描写一个数据元素（或结点）；若构成数据元素各字段类型不一致，也可改用两个或多个一维数组来模拟实现之。可用三个一维数组来模拟实现二叉树，其中一个数组存放数据域的值，两个数组分别作为左右链域。树可通过左孩子右兄弟表示法转化为二叉树用数组表示，而图和网的邻接矩阵表示法本身就是用二维数组表示的方法。

第12页/共132页数据结构的程序实现全文共132页，当前为第12页。第9章数据结构的程序实现9.1基本的实现策略9.2动态结构的静态实现9.3大批量数据的组织策略9.4数据结构在问题建模中的应用

第13页/共132页数据结构的程序实现全文共132页，当前为第13页。动态结构的静态实现所谓动态数据结构（dynamicdatastructure）是指可以随着程序的执行而动态地改变大小程形状的一类数据结构，如链表、树和图等。动态结构的数据，在编译时无法预先规定它们所需要分配的存储空间大小，只有在运行时进行动态存储分配，与之相对应的是静态数据结构（staticdatastructure），数据所需存储空间是一个固定的有限区域，可在程序说明中显式规定，在编译时静态进行存储分配。

凡是可以用指针动态实现的数据结构，都可以利用数组静态地模拟实现。有时也把这种利用数组静态模拟实现了的动态结构称之为半静态数据结构（semi-staticdatastructure）。当然，半动态结构中也包含可变数组和变长记录等部分采用静态分配、部分采用动态分配的数据结构。

第14页/共132页数据结构的程序实现全文共132页，当前为第14页。9.2动态结构的静态实现9.2.1静态链表9.2.2二叉树的静态二叉链表表示法9.2.3树和森林的双亲表示法9.2.4哈夫曼算法的静态实现第15页/共132页数据结构的程序实现全文共132页，当前为第15页。静态链表

在利用提供指针类型的高级程序设计语言编写程序时，链表的实现是很简单和很自然的。如果语言中没有提供指针类型，可以用数组来模拟实现链表结构，并称之为静态链表（staticlinkedlist），用以记录类型作为基类型的数组来模拟实现静态链表。模拟实现静态链表的数组可如下定义：

#definemaxsize100typedefstruct{elementypedata;/*数据域为元素类型*/intnext;/*指针域为整型*/}snode;/*snode为结点类型标识符*/snodes[maxsize];/*s为基类型是snode的一维数组，即记录数组*/第16页/共132页数据结构的程序实现全文共132页，当前为第16页。静态链表（续）注意这里的next域说明与单链表中的说明不同，在单链表中是指向结构体的指针类型，值为结点的实际地址；在静态链表中是int类型，值为结点在s

数组中的下标值，指针值为空时用-1表示。

对于静态链表实现线性表的各种运算操作与动态的单链表上的实现基本相同，所不同的是在存储区的管理上有差别。单链表上的运算操作实现不要考虑存储区的管理问题，是通过malloc函数获得结点空间并利用free函数释放结点空间，存储区的管理交由系统完成；而静态链表的存储区就是这个记录数组s，获得结点空间和释放结点空间都对数组s进行，必须在程序中设计相应的管理程序段。

第17页/共132页数据结构的程序实现全文共132页，当前为第17页。静态链表及其存储区管理举例第18页/共132页数据结构的程序实现全文共132页，当前为第18页。9.2动态结构的静态实现9.2.1静态链表9.2.2二叉树的静态二叉链表表示法9.2.3树和森林的双亲表示法9.2.4哈夫曼算法的静态实现第19页/共132页数据结构的程序实现全文共132页，当前为第19页。二叉树的静态二叉链表表示法对于没有提供指针类型的高级程序设计语言，程序中要用到二叉树结构组织数据信息，可用静态二叉链表（staticbinarylinkedlist）表示法实现二叉树结构。和静态链表类似，静态二叉链表的存储区管理也是利用以结点类型作为基类型的一维数组实现；获得结点空间的函数malloc和释放结点空间的free函数的实现也是类似的。

用静态二叉链表表示二叉树的类型定义如下：

#definemaxsize100typedefstruct/*定义结点类型为结构体*/{elementypedata;/*数据域为元素类型*/intlchild,rchild;/*定义左右孩子域为整型*/}sbinarytree;sbinarytreest[maxsize];第20页/共132页数据结构的程序实现全文共132页，当前为第20页。二叉树的静态二叉链表表示法

和静态链表一样，静态二叉链表的左孩子域和右孩子域也都是int类型，其值为数组中的下标值。静态二叉链表的存储区管理是利用右孩子域形成的静态链栈av，用-1表示指针为NULL的情况。除了在插入结点时获取一个结点空间以及在删除时释放一个结点空间的存储区管理是要在程序中完成之外，用静态二叉链表表示的二叉树的各种运算操作与用二叉链表表示的二叉树的相应运算操作一致。第21页/共132页数据结构的程序实现全文共132页，当前为第21页。二叉树的静态二叉链表表示法举例

第22页/共132页数据结构的程序实现全文共132页，当前为第22页。9.2动态结构的静态实现9.2.1静态链表9.2.2二叉树的静态二叉链表表示法9.2.3树和森林的双亲表示法9.2.4哈夫曼算法的静态实现第23页/共132页数据结构的程序实现全文共132页，当前为第23页。树和森林的双亲表示法举例在前面我们介绍了树和森林的两种存储表示方法，即孩子链表表示法和左孩子右兄弟表示法；这两种表示方法，都可以通过静态链表和静态二叉链表来实现。树和森林还有一种存储表示方法，就是双亲表示法。因为树和森林中的每一个结点，其双亲结点是惟一的；利用这一性质，在存储结点信息时为每个结点增加一个指向其双亲的指针parent，就可以惟一地表示树或森林。

若用静态链表实现树和森林的双亲表示法，其类型定义如下：

#definemaxsize100typedefstruct{elementypedata;intparent;}sptnode;sptnodept[maxsize];第24页/共132页数据结构的程序实现全文共132页，当前为第24页。树和森林的双亲表示法第25页/共132页数据结构的程序实现全文共132页，当前为第25页。9.2动态结构的静态实现9.2.1静态链表9.2.2二叉树的静态二叉链表表示法9.2.3树和森林的双亲表示法9.2.4哈夫曼算法的静态实现第26页/共132页数据结构的程序实现全文共132页，当前为第26页。哈夫曼算法的静态实现

由于哈夫曼树中没有度为1的结点，一棵有n个叶子结点的哈夫曼树有2n-1个结点，所以可用大小为2n-1个元素的数组构造静态链表来存储哈夫曼树，一个数组元素中存放一个结点。结点的结构可以这样来考虑，由于每个叶子结点都有一个权重值，构造哈夫曼树的过程中每个分枝结点的权重值等于两个孩子结点权重值的和，所以应该有一个权重域和指向左右孩子的两个指针域；另外在建成哈夫曼树之后，为了求得每个叶子结点的哈夫曼编码，需要走一条从叶子结点到根结点的路径，而译码的过程是从根结点出发到叶子结点的不断匹配的过程，所以既需要知道孩子结点的信息，也需要知道双亲结点的信息，应该再有一个指向双亲结点的指针域。由此可知每个结点至少应该有一个权重域weight和三个指针域parent、lchild和rchild，也就是说要用静态三叉链表来表示哈夫曼树。第27页/共132页数据结构的程序实现全文共132页，当前为第27页。哈夫曼树及其静态三叉链表存储表示示例

第28页/共132页数据结构的程序实现全文共132页，当前为第28页。哈夫曼算法的静态实现(续)由于在实际构造哈夫曼树时，是由叶子结点的权值逐级构造最后生成树根，且在构造过程中仅与叶子结点的权值有关而与叶子结点的数据域值无关；所以构造算法的实现中可以不考虑叶子结点的数据域值，并且在静态三叉链表中从叶子结点开始存放，然后不断地把两棵权值最小的子树合并成为一棵权值为其和的较大的子树，逐步生成各内部结点直到树根。哈夫曼树的类型定义如下：

#definemaxvalue10000#definemaxnodenumber100typedefstruct{intweight;intparent,lchild,rchild;}htnode;/*定义结点类型标识符*/typehtnode*huffmantree;/*定义哈夫曼树类型*/htnodeht[maxnodenumber];第29页/共132页数据结构的程序实现全文共132页，当前为第29页。建立哈夫曼树的算法的描述

在以上类型定义的基础上，对于给定的一组权重值，建立其哈夫曼树的算法可描述如下：

huffmantreecrthuffmantree(intn){inti,j,m1,m2,k1,k2;for(i=0;i<2*n-1;i++){ht[i].weight=0;/*权重初始化为0*/ht[i].parent=-1;ht[i].lchild=-1;ht[i].rchild=-1;}for(i=0;i<n;i++)scanf(“%d”,&ht[i].weight);

第30页/共132页数据结构的程序实现全文共132页，当前为第30页。建立哈夫曼树的算法的描述(续)

for(i=0;i<n-1;i++){m1=maxvalue;m2=maxvalue;k1=0;k2=0;for(j=0;j<n+i;j++)if(ht[j].parent==-1&&ht[j].weight<m1){m2=m1;k2=k1;m1=ht[j].weight;k1=j;}elseif(ht[j].parent==-1&&ht[j].weight<m2){m2=ht[j].weight;k2=j;}第31页/共132页数据结构的程序实现全文共132页，当前为第31页。建立哈夫曼树的算法的描述(续)

ht[k1].parent=n+i;ht[k2].parent=n+i;ht[n+i].weight=ht[k1].weight+ht[k2].weight;ht[n+i].lchild=k1;ht[n+i].rchild=k2;}returnht;}/*crthuffmantreeend*/

注意，在建立哈夫曼树的算法描述中，有效地利用了每个结点的双亲域parent的值是否为-1来区分该结点是否是哈夫曼森林中一棵树的根结点；每次是在根结点中找出两个权重值weight最小的树作为左右子树构造一棵更大的树。第32页/共132页数据结构的程序实现全文共132页，当前为第32页。求哈夫曼编码的方法求哈夫曼编码的方法是，在已建好的哈夫曼树中从每个叶子结点开始沿双亲链域回退到根结点，每回退一步走过哈夫曼树的一个分枝得到一位哈夫曼编码值；由于每个叶子结点的哈夫曼编码是从根结点到相应叶子结点的路径上各分枝代码所组成的0、1序列，所以先得到的分枝代码为所求编码的低位码而后得到的为高位码。对于每个叶子结点的哈夫曼编码可以考虑用一个一维数组bit从后向前依次保存所求得的各位编码值，并用start记住编码在数组bit中的开始位置。由此可做如下的类型定义：

#definemaxbit10typedefstruct{intbit[maxbit];intstart;}hcodetype;/*定义哈夫曼编码类型*/第33页/共132页数据结构的程序实现全文共132页，当前为第33页。求哈夫曼编码的算法描述从叶子结点到根结点逆向求每个叶子结点所代表值的哈夫曼编码的算法可描述如下：

voidgethuffmancode(htnodeht,intn){inti,j,c,p;hcodetypecd[n];for(i=0;i<n;i++){c=i;j=maxbit+1;do{j--;p=ht[c].parent;if(ht[p].lchild==c)/*如果c是p的左孩子*/cd[i].bit[j]=0;elsecd[i].bit[j]=1;c=p;}while(p!=-1);第34页/共132页数据结构的程序实现全文共132页，当前为第34页。求哈夫曼编码的算法描述(续)cd[i].start=j;}for(i=0;i<n;i++){for(j=cd[i].start;j<maxbit;j++)printf(“%d”,cd[i].bit[j]);printf(“\n”);}}/*gethuffmancodeend*/第35页/共132页数据结构的程序实现全文共132页，当前为第35页。求哈夫曼编码的算法举例例如，已知某系统在通讯联络中只可能出现六种字符，其使用各字符的频度分别为（0.05，0.20，0.12，0.07，0.47，0.09）。若要为这六种字符设计哈夫曼编码，可设权w=(5，20，12，7，47，9)，n=6，2n-1=11；按上述crthuffmantree算法构造的哈夫曼树如下左图所示。按gethuffmancode算法求得的哈夫曼编码在cd数组中的状态如下右图所示。第36页/共132页数据结构的程序实现全文共132页，当前为第36页。求哈夫曼编码的算法举例(续)其存储结构的静态三叉链表ht的初始状态如下左图所示，最终状态如下右图所示。第37页/共132页数据结构的程序实现全文共132页，当前为第37页。第9章数据结构的程序实现9.1基本的实现策略9.2动态结构的静态实现9.3大批量数据的组织策略9.4数据结构在问题建模中的应用

第38页/共132页数据结构的程序实现全文共132页，当前为第38页。9.3大批量数据的组织策略9.3.1文件的组织9.3.2数据库技术第39页/共132页数据结构的程序实现全文共132页，当前为第39页。1.文件的基本概念文件的概念和线性表类似，是由大量性质相同的记录组成的集合；二者的区别在于线性表是把记录全部组织在内存储器中，而文件则是把大量记录都组织在外存储器中。按照记录的类型，可以把文件分为操作系统文件和数据库文件两大类。操作系统文件中的记录只是一个字符序列，无结构，无解释，仅是为了加工，存取的方便划分的字符组。而数据库文件中的记录是有结构的，可以由一个或多个数据项组成，是存取文件中数据的基本单位；数据项是不可再分的最基本单位，也是文件中可使用数据的最小单位。第40页/共132页数据结构的程序实现全文共132页，当前为第40页。文件的基本概念（续）

按照记录的长度特性，可以把文件分为定长记录文件和不定长记录文件。定长记录文件中每个记录含有的信息长度相同，不定长记录文件中每个记录含有的信息长度不等。按照记录中关键字的多少，可以把文件分为单关键字文件和多关键字文件。单关键字文件中的记录只有一个惟一标识记录的主关键字；多关键字文件中的记录除了主关键字外，还含有一个或多个次关键字，记录中所有非关键字的数据项称作记录的属性。第41页/共132页数据结构的程序实现全文共132页，当前为第41页。文件的基本概念（续）记录有逻辑结构和物理结构之分。逻辑结构是指记录在用户或应用程序员面前呈现的方式，是用户对数据的表示和存取方式；用户读写一个记录是指逻辑记录。记录的物理结构是数据在物理存储器上存储的方式，是数据的物理表示和组织方式。一个物理记录是指计算机用一条I/O命令进行读写的基本数据单位，对于固定的设备和操作系统，它的大小基本上是固定不变的；而逻辑记录的大小是根据使用的需要确定的。一个物理记录可以存放一个或多个逻辑记录，多个物理记录可以表示一个逻辑记录。用户读写的是逻辑记录，查找其对应的物理记录是操作系统的职责。第42页/共132页数据结构的程序实现全文共132页，当前为第42页。文件的基本概念（续）

文件的操作有三类，检索、修改和排序。检索的方式有三种：①顺序检索，按记录的相对位置检索下一个逻辑记录；②按记录号检索，根据记录存入文件时的顺序编号，检索第i个逻辑记录；③按关键字检索，检索关键字值与给定值相关的一个或多个逻辑记录，在数据库文件中又可按给定关键字值、给定关键字的范围、给定关键字的某个函数以及组合条件等方式进行检索。修改操作包括插入、删除和更新一个记录这三种操作。排序操作则是为了检索方便高效对文件中记录的重新有序整理。第43页/共132页数据结构的程序实现全文共132页，当前为第43页。文件的基本概念（续）

文件的操作可以有实时和批处理两种不同的方式。实时处理通常对应答时间要求严格，应在接收询问后立即完成相应的操作；而批处理则不同，可以根据需要对积累一段时间的记录进行成批处理。文件在存储介质上的组织方式（即物理结构）有顺序组织、随机组织和链式组织等基本方式，具体选用哪种方式应结合存储介质类型（磁盘、磁带等）、记录类型、记录大小、关键字数目以及对文件进行何种操作等各种因素综合考虑。第44页/共132页数据结构的程序实现全文共132页，当前为第44页。2.顺序文件

顺序文件（sequentialfile）是把记录按建立文件时的逻辑顺序依次存放在外存储器中，文件中的物理记录顺序和逻辑记录顺序一致。若次序相继的两个物理记录在存储器上的存储位置是相邻的，则又称为连续文件；若物理记录之间的次序由指针链接，则称为串联文件。顺序文件的存取方式是根据记录号或记录的相对位置进行的，其特点是：存取第i个记录必须先搜索在它之前的i-1个记录；插入的新记录只能加在文件的未尾；若要更新文件中的某个记录，必须在整个文件的复制过程中进行。第45页/共132页数据结构的程序实现全文共132页，当前为第45页。顺序文件（续）

由于顺序文件的优点是连续存取速度快，因此主要用于顺序存取和批量修改的情况。若对应答时间要求不严时亦可进行直接存取。在对顺序文件作修改时，可对原文件中的记录复制一遍，并在复制的过程中插入新的记录、跳过待删除的记录、或用修改过的新记录代替原记录。为了修改方便起见，要求待修改文件按关键字有序（对非数据库文件可将逻辑记录号作为关键字）。第46页/共132页数据结构的程序实现全文共132页，当前为第46页。顺序文件（续）

磁带是一种典型的顺序存取设备，存储在磁带上的文件就是顺序文件。然而现在很少使用磁带，较多使用的是磁盘上的顺序文件。对磁盘上的顺序文件进行修改时，若不增加记录的长度，也可在原文件上直接修改而不必复制文件。对顺序文件进行顺序检索的方法类似于静态表的顺序检索，其平均检索长度为(n+1)/2，其中n为文件中所含物理记录的数目（内存检索时间可以忽略不计）。也可以对磁盘文件进行分块检索或二分法检索。但当文件很大时，二分法检索将会引起磁头在存储文件的多个柱面之间来回移动而增加检索时间。第47页/共132页数据结构的程序实现全文共132页，当前为第47页。3.索引文件

除了主文件（即数据文件）之外，再建立一张索引表来指示逻辑记录和物理记录之间的一一对应关系；索引表中的每一项称作索引项，由记录的关键字和记录的存放地址构成；把索引表和主文件总称为索引文件（indexedfile）。索引表通常是按关键字的升序排列。若主文件也按关键字升序排列，则构成的索引文件称作索引顺序文件；若主文件是无序的，则称所构造的索引文件为索引非顺序文件。第48页/共132页数据结构的程序实现全文共132页，当前为第48页。索引文件（续）

索引文件只适用于直接存取的外存储器（如磁盘）。索引文件的存储分索引区和数据区来进行，索引区存放索引表，数据区存放主文件。在输入记录建立数据区的同时建立索引表，表中的索引项按记录输入的先后次序排列；待全部记录输入完毕后再对索引表按关键字排序，排序后的索引表和主文件一起构成了索引文件。第49页/共132页数据结构的程序实现全文共132页，当前为第49页。索引非顺序文件举例第50页/共132页数据结构的程序实现全文共132页，当前为第50页。索引文件（续）索引文件的检索，应先在索引表中检索。若在索引表中找到关键字值等于给定值的索引项，则按索引项指示从外部存储器读取该记录；否则说明待检索记录不存在无需访问外存储器。相对于记录而言索引项长度较小，即由索引项构成的索引表所占空间较小，通常可一次读入内存。然而当主文件中记录数目很大时，索引表仍可能超出一个物理块的容量，这样对索引表的检索就可能需要多次访问外存储器。为此，可对索引表再次建立二级索引；检索时先在二级索引中找，再检索索引表，然后读取记录。索引表和二级索引表都是有序表，在内存储器中可用检索效率较高的方法如二分法检索方法进行检索。第51页/共132页数据结构的程序实现全文共132页，当前为第51页。4.ISAM文件

ISAM（indexedsequentialaccessmethod）即索引顺序存取方法，是一种专为磁盘存取设计的文件组织方式。由于磁盘是以盘组、柱面和磁道三级地址存取的设备，所以可以对磁盘上的数据文件建立盘组、柱面和磁道三级索引。文件的记录在同一盘组上存放时，应先集中放在一个柱面上，然后再顺序存放在相邻柱面上；对同一柱面，则应按盘面的次序顺序存放。第52页/共132页数据结构的程序实现全文共132页，当前为第52页。ISAM文件结构举例第53页/共132页数据结构的程序实现全文共132页，当前为第53页。ISAM文件（续）在一个磁盘组上的ISAM文件，每个柱面建立一个磁道索引，每个磁道索引项由基本索引项和溢出索引项两部分组成，每一部分都包括关键字和指针两个域，前者表示该磁道中最大关键字，后者指示该磁道中第一个记录的位置。柱面索引的每一个索引项也由关键字和指针两部分组成，前者表示该柱面中的最大关键字，后者指示该柱面上的磁道索引位置。柱面索引存放在某个柱面上，若柱面索引较大占多个磁道时，则可建立柱面索引的一个主索引。第54页/共132页数据结构的程序实现全文共132页，当前为第54页。ISAM文件（续）

在ISAM文件上检索记录时，先从主索引出发找到相应的柱面索引，再从柱面索引找到记录所在柱面的磁道索引，最后从磁道索引找到记录所在磁道的第一个记录的位置，由此出发在该磁道上进行顺序查找直至找到为止；反之，若找遍磁道而不存在此记录，则表明文件中无此记录。在前例中为每个柱面开辟了一个溢出区，并在磁道索引项中有溢出索引项（后面两个域），这是为插入记录所设置的。第55页/共132页数据结构的程序实现全文共132页，当前为第55页。ISAM文件（续）由于ISAM文件中记录是按关键字顺序存放的，在插入一个记录时需要向后移动记录，并将同一磁道上的最后一个记录移至溢出区，同时修改磁道索引项。除了为每个柱面设置一个溢出区的方法外，还可只集中设置一个大的公共溢出区；也可以既为每个柱面设置溢出区，同时也设置了一个公共溢出区，在柱面溢出区满后再使用公共溢出区。ISAM文件中删除记录比较简单，只需作删除标记而不用移动记录或改变指针。当然应该周期性地把记录读入内存重排整理ISAM文件，以尽量填满基本区而空出溢出区。第56页/共132页数据结构的程序实现全文共132页，当前为第56页。5.VSAM文件VSAM（virtualstorageaccessmethod）即虚拟存储存取方法。它利用了操作系统的虚拟存储器的功能，使用户只需考虑控制区间等逻辑存储单位，而无需考虑其物理位置以及何时对外存储器进行读写操作，给用户使用文件提供了方便。

VSAM文件的结构由索引集、顺序集和数据集三部分组成。数据集存放文件的所有记录，顺序集和索引集构成一棵B+树是文件的索引部分。数据集中的一个结点称为控制区间（controlinterval），它由一组连续的存储单元组成，是读写操作的基本单位。第57页/共132页数据结构的程序实现全文共132页，当前为第57页。VSAM文件的结构举例第58页/共132页数据结构的程序实现全文共132页，当前为第58页。VSAM文件（续）同一文件上的控制区间大小相同，含有一个或多个按关键字升序排列的记录。顺序集中的一个结点，存放着若干相邻控制区间的索引项，每个索引项由控制区间中的最大关键字和指向该控制区间的指针组成。顺序集中的一个结点连同其下层所有控制区间形成的整体称作控制区域（controlrange）。顺序集中的结点之间用指针相链接；在它们上层的结点又以它们为基础形成索引，并逐级向上建立索引，形成B+树的非终端结点。第59页/共132页数据结构的程序实现全文共132页，当前为第59页。VSAM文件（续）

对VSAM文件中记录的检索，既可以从最高层的索引逐层往下按关键字进行查找，又可以在顺序集中沿着指针链顺序查找。VSAM文件没有专门的溢出区，但可利用控制区间中的空隙或控制区域中空的控制区间来插入记录（即在B+树上插入记录）。在控制区间中插入记录时，为了保证区间内记录按关键字有序需要移动记录；而当区间中记录已满时，为了插入记录需要将区间分裂。在VSAM文件中删除记录时，也是需要移动记录的。第60页/共132页数据结构的程序实现全文共132页，当前为第60页。VSAM文件（续）

VSAM文件占有较多的存储空间，存储空间的利用率一般也只能保持在75%左右。然而它具有许多优点，如动态地分配和释放存储空间，无需像ISAM文件那样定期重排文件，并能较快地执行插入操作和保持较高的检索效率。

VSAM文件通常作为组织大型索引顺序文件的标准形式。第61页/共132页数据结构的程序实现全文共132页，当前为第61页。9.散列文件散列文件（Hashfile）也称作直接存取文件，它是利用哈希方法组织的数据文件；即根据某个哈希函数和一定的冲突消解策略而得到的存放在外存储器上的散列表。

与哈希表不同的是，磁盘上的文件记录通常是成组存放的。若干个记录组成一个存储单位，在散列文件中这个存储单位称作桶。一个桶能存放的逻辑记录的总数称作桶的容量。假如桶的容量为m，即m个同义词的记录可以存放在同一地址的桶中，当第m+1个同义词记录出现时则发生溢出。处理溢出也可采用哈希表中的各种处理冲突的方法，但对散列文件主要是采用链地址法消解冲突。

第62页/共132页数据结构的程序实现全文共132页，当前为第62页。散列文件（续）当发生溢出时，需要将第m+1个同义词存放到另一个桶中，通常称作“溢出桶”；相应地把存放前m个同义词的桶称作“基桶”。溢出桶可以有多个，它们和基桶大小相同，相互之间用指针相链接。当在基桶中没有检索到待查记录时，就顺指针所指到溢出桶中去检索；因此，同一散列地址的溢出桶和基桶在磁盘上的物理位置不要相距太远，最好是在同一柱面上。第63页/共132页数据结构的程序实现全文共132页，当前为第63页。散列文件举例例如，某文件有20个记录，其关键字分别为28、19、13、93、89、25、14、55、69、8、9、16、21、33、81、62、11、71、34、35。用除留余数法选定哈希函数H(key)=key%7，用链地址法消解地址冲突。桶的容量m=3，基桶个数b=7，由此得到的散列文件如下图所示。

第64页/共132页数据结构的程序实现全文共132页，当前为第64页。散列文件（续）

在散列文件中检索时：先根据给定的关键字值k求得哈希地址，即基桶号；然后将基桶的记录读入内存进行顺序检索，若找到关键字值为k的记录则检索成功；若基桶中虽无关键字值为k的记录但指针域非空，需要把溢出桶中的记录读入内存继续检索，直到检索成功或检索不成功。检索不成功的情况为基桶没有填满记录，或虽填满但指针域为空（无溢出桶），或虽有溢出桶但仍未找到关键字为k的记录。

第65页/共132页数据结构的程序实现全文共132页，当前为第65页。散列文件（续）在散列文件中，装填因子为，其中n为文件中的记录数，b为桶数，m为桶的容量；而存取桶数的期望值为。如上例，。在散列文件中，删除记录时仅需对被删记录作一删除标记即可。总之，散列文件的优点是插入和删除方便，存取速度比索引文件要快；不需要索引区，节省存储空间。其缺点是不能进行顺序存取，只能按关键字随机存取，且询问方式只有简单询问；在经过多次的插入和删除之后，也可能造成溢出桶满而基桶内多数为被删除记录的不合理文件结构，亦需对文件进行重新整理。第66页/共132页数据结构的程序实现全文共132页，当前为第66页。7.多关键字文件多关键字文件（multiplekeyfile）的特点是，在对文件进行检索操作时不仅对主关键字进行简单询问，还经常需要对次关键字进行其它类型的询问检索。因此，对多关键字文件还需要建立一系列的次关键字索引。次关键字索引和主关键字索引所不同的是，每个索引项应包含次关键字和具有同一次关键字的多个记录的主关键字或物理记录号。多重表文件和倒排文件是常见的两种多关键字文件组织方法。第67页/共132页数据结构的程序实现全文共132页，当前为第67页。多关键字文件（续）

多重表文件（multilistfile）的特点是，记录按主关键字的顺序构成一个串联文件，并建立主关键字索引（称为主索引）；对每一个次关键字项建立次关键字索引（称为次索引），所有具有同一次关键字的记录构成一个链表。主索引为非稠密索引，一组记录建立一个索引项；次索引为稠密索引，每个记录建立一个索引项，每个索引项包括次关键字、头指针和链表长度。第68页/共132页数据结构的程序实现全文共132页，当前为第68页。多关键字文件举例例如，下图所示为一个多重表文件。其中工号为主关键字，记录按工号顺序链接。

第69页/共132页数据结构的程序实现全文共132页，当前为第69页。多关键字文件举例（续）对工号非稠密索引分成三个子链表，其索引如下图(b)所示，索引项中的主关键字为各组中关键字的最大值。职称和专业是两个次关键字项，其索引分别如下图(c)和(d)所示，具有相同次关键字值的记录链接在同一链表中。第70页/共132页数据结构的程序实现全文共132页，当前为第70页。多关键字文件（续）有了这些次关键字索引，根据关键字值找到链表头指针，然后从头指针出发可列出链表中所有记录。比如查询数学专业的教授，可以专业索引表中找到“数学”的头指针和表长，逐一读取记录查看哪些记录的职称为教授即可。此查询也可从职称索引入手进行。当然，较好的方法是先读长度较短的链表中的记录。

在多重表文件中插入一个记录是容易的，只要修改指针将记录插在链表的头指针之后即可。然而要删去一个记录却很繁琐

，需要在每个次关键字的链表中删去该记录。第71页/共132页数据结构的程序实现全文共132页，当前为第71页。多关键字文件（续）

倒排文件（invertedfile）和多重表文件的区别在于次关键字索引的结构不同。倒排文件的次关键字索引称为倒排表，在倒排表的索引项中没有头指针和链长度，而是直接用一个项存放具有同一关键字的所有记录的物理记录号或主关键字值。值得注意的是，倒排表中具有同一次关键字的记录号是有序排列的。上例的倒排表如下图所示：

第72页/共132页数据结构的程序实现全文共132页，当前为第72页。多关键字文件（续）倒排表作索引的好处在于检索记录较快。特别是对某些询问，不用读取记录就可得到答案。例如上例查询数学专业教授，只要将“数学”索引中的记录号和“教授”索引中的记录号求集合的交集运算就可以了，即{2，5，9}∩{2，6}={2}就得到记录号为2者便是数学教授。在插入和删除记录时，倒排表也要进行相应修改；需要移动索引项中记录号以保持其有序排列。若数据文件是索引顺序文件（如ISAM文件），倒排表中应存放记录的主关键字而不是物理记录号。倒排文件的缺点是维护困难。同一倒排表中各项长度不同，不同倒排表的长度也不同，这些都给倒排文件的维护带来一定的困难。第73页/共132页数据结构的程序实现全文共132页，当前为第73页。9.3大批量数据的组织策略9.3.1文件的组织9.3.2数据库技术第74页/共132页数据结构的程序实现全文共132页，当前为第74页。文件系统的缺陷利用文件组织大批量数据是数据组织中行之有效的方法，然而，文件系统也存在着一些明显的缺陷。如：数据冗余大。因为每个文件都是为特定用途设计的，因此会造成同样的数据在多个文件中的重复存储。数据的不一致性，这往往是由于数据冗余所造成的；在数据更新时，稍有不慎就会造成同一数据在不同文件中的不一致。程序和数据之间的独立性差。应用程序依赖于文件的存储结构，使得在对文件的存储结构进行修改时，必须修改应用程序。数据联系弱。文件与文件之间是独立的，文件之间的联系必须通过程序来构造。因此，文件系统是一个不具有弹性的无结构的数据集合，难以反应客观世界中事物之间的联系。

第75页/共132页数据结构的程序实现全文共132页，当前为第75页。数据库技术诞生为了克服上述文件系统的不足，20世纪60年代后期开始诞生了解决大批量数据组织和管理的数据库技术。数据库技术诞生的标志性事件是：1968年研制成功，1969年形成产品的美国IBM公司的数据库管理系统IMS（informationmanagementsystem）的问世，该系统支持的是层次数据模型。美国数据系统语言协会CODASYL（conferenceondatasystemlanguage）下属的数据库任务组DBTG（databasetaskgroup）对数据库方法进行了系统的研究，在20世纪60年代末期和70年代初期发表了若干个报告（称为DBTG报告），该报告建立了数据库的许多概念、方法和技术。DBTG所提议的方法是基于网状数据模型的。从1970年起，IBM的研究员E.F.Codd发表了一系列的论文，提出了数据库的关系模型，开创了数据库关系方法和关系数据理论的研究，为关系数据库的发展和理论研究奠定了基础。

第76页/共132页数据结构的程序实现全文共132页，当前为第76页。数据库技术

数据库技术发展到现在，已经是一门非常成熟的技术，作为算法与数据结构课程的后续课程。概括地讲，数据库具有如下基本特征：数据库是相互关联的数据的集合。数据库用综合的方法组织数据，并保证尽可能高的访问效率。数据库具有较小的数据冗余，可供多个用户共享。数据库具有较高的数据独立性。数据库具有安全控制机制，能够保证数据的安全性和可靠性。数据库允许并发使用，能有效和及时地处理数据，并能保证数据的一致性和完整性。第77页/共132页数据结构的程序实现全文共132页，当前为第77页。层次数据库

层次数据库和网状数据库可以看作是第一代数据库系统。

层次数据库是建立在层次数据模型的基础上的数据库，层次数据模型以树结构来表示实体之间的联系。树中的结点表示实体集（文件或记录型），连线表示两个实体之间的联系，且这种联系只能是一对多的。对于多对多的联系不能直接用层次模型表示，需要分解成两个层次型。层次数据库的典型代表是IBM公司1969年诞生的IMS。第78页/共132页数据结构的程序实现全文共132页，当前为第78页。网状数据库网状数据库是建立在网状数据模型的基础上的数据库，网状数据模型以图结构来表示实体之间的联系，这种联系是一种多对多的联系。然而，多对多的联系实现起来太复杂了，所以在一些实际的支持网状数据模型的数据库管理系统上，对多对多联系还是做了限制。如网状模型的典型代表CODASYL系统就仅支持一对多的联系，它按系（set）组织数据。系可理解为命了名的联系，由一个双亲记录和一个或多个子记录型组成。

第79页/共132页数据结构的程序实现全文共132页，当前为第79页。关系数据库

关系数据库可以看作是第二代数据库系统。关系数据库是建立在关系数据模型基础之上的数据库，关系数据模型用关系（即二维表格数据）表示实体之间的联系。通俗地讲，关系就是二维表格；表格中的每一行称作一个元组，相当于一个记录值；每一列是一个属性值集，列可以命名，称作属性名。由此可以说，关系是元组的集合，如果表格有n列，则称该关系为n元关系。第80页/共132页数据结构的程序实现全文共132页，当前为第80页。关系模型中的操作

关系模型中的操作有：传统的集合运算：交、并、差和广义笛卡积等；专门的关系运算：选择、投影、连接和除等；有关的数据操作：查询、插入、删除和修改等。第81页/共132页数据结构的程序实现全文共132页，当前为第81页。对数据库技术的研究对数据库技术的研究是从以下三个方面进行的：

数据模型。数据模型的研究是数据库系统的基础研究，重点研究如何构造数据模型，如何表示数据及其联系。现在的重点研究课题是面向对象模型。

应用领域。数据库技术的最初应用主要是信息管理领域，事实上，只要有大量数据要管理或者需要大批量数据支持的工作，都可以使用数据库。计算机技术。计算机技术的发展促进了数据库技术的发展。通过将计算机技术的一些研究领域与数据库技术相结合，产生了许多新的数据库系统。第82页/共132页数据结构的程序实现全文共132页，当前为第82页。第9章数据结构的程序实现9.1基本的实现策略9.2动态结构的静态实现9.3大批量数据的组织策略9.4数据结构在问题建模中的应用

第83页/共132页数据结构的程序实现全文共132页，当前为第83页。9.4

数据结构在问题建模中的应用

9.4.1Josephus问题9.4.2教务管理与二分图9.4.3学籍管理系统中的数据组织第84页/共132页数据结构的程序实现全文共132页，当前为第84页。Josephus问题Josephus问题是由古罗马著名史学家Josephus所提出的问题演变而来的。Josephus问题的提法很多，如“猴子选大王问题”、“旅行社奖游客问题”等，就其数学本质而言是相同的问题。Josephus问题的一般描述如下：设有n个人围坐一圈并由1到n编号。从某个人（例如编号为k的人）开始报数，数到m的人出列；接着从出列的下一个人开始重新1到m报数，数到m的人又出列；如此反复地报数和出列，直到最后一个人出列为止。试设计确定这n个人出列序列的程序。

第85页/共132页数据结构的程序实现全文共132页，当前为第85页。Josephus问题（续）由问题描述可以很自然地联想到循环链表，用循环链表对Josephus问题建模，可以做到程序世界和问题世界的完全一致性，符合面向对象的程序设计思想。考虑到反复报数的过程，可选用不带头结点的单循环链表，以避免报数过程中识别头结点的麻烦。由此，程序中可以先构建一个具有n个结点的单循环链表，然后从约定的结点开始1到m计数，计到m时从链表中删除对应结点；接着从被删除结点的下一个结点起计数，直到最后一个结点从链表中删除后结束。

第86页/共132页数据结构的程序实现全文共132页，当前为第86页。Josephus问题举例例如，若n＝8，m=3，k=1时，出列的序列为3，6，1，5，2，8，4，7。如下图给出了问题求解过程示意图，图中的箭头表示当前报数的位置，虚线框中为要出列者的序号，实黑框中为已出列者的序号，空白框中为未出列者的序号。

第87页/共132页数据结构的程序实现全文共132页，当前为第87页。Josephus问题算法描述

用C语言编写利用单循环链表求解Josephus问题程序如下：

#include“stdio.h”#include“malloc.h”typedefstructnode{intnum;structnode*next;}linklist;linklist*creat(head,n)linklist*head;intn;{linklist*s,*p;inti;s=(linklist*)malloc(sizeof(linklist));head=s;第88页/共132页数据结构的程序实现全文共132页，当前为第88页。Josephus问题算法描述（续）

s->num=1;p=s;for(i=2;i<=n;i++){s=(linklist*)malloc(sizeof(linklist));s->num=i;p->next=s;p=s;}p->next=head;returnhead;}/*creat*/第89页/共132页数据结构的程序实现全文共132页，当前为第89页。Josephus问题算法描述（续）

linklist*select(head,m)linklist*head;intm;{linklist*p,*q;inti,t;p=head;t=1;q=p;do{p=q->next;t=t+1;第90页/共132页数据结构的程序实现全文共132页，当前为第90页。Josephus问题算法描述（续）

if(t%m==0){printf(“%4d”,p->num);q->next=p->next;free(p);}elseq=p;}while(q==p);head=p;return(head);}/*select*/第91页/共132页数据结构的程序实现全文共132页，当前为第91页。Josephus问题算法描述（续）main(){intn,m;linklist*head;printf(“inputthetotalnumber\n”);scanf(“%d”,&n);printf(“inputthenumbertocall:\n”);scanf(“%d”,&m);creat(head,n);select(head,m);printf(“thelastoneis%d\n”,head->num);}/*main*/第92页/共132页数据结构的程序实现全文共132页，当前为第92页。Josephus问题算法描述（续）求解Josephus问题，也可以考虑用静态循环链表组织数据。由于数组下标与n个人的编号可以一致起来（不用下标0），故仅用一维数组即可，其中数组元素作为静态指针指向下一个人，这种实现方法称作环形数组实现方法，程序如下：

#include“stdio.h”#include“malloc.h”

voidJosephus(n,m,k)intm,n,k;{intR[];inti,j;for(i=1;i<n;i++)R[i]=i+1;第93页/共132页数据结构的程序实现全文共132页，当前为第93页。Josephus问题算法描述（续）

R[n]=1;if(k=1)j=n;elsej=k-1;

/*初始化报数变量j*/while(R[j]!=j){for(i=1;i<=m;i++)/*由1到m报数*/J=R[j];printf(“%d\n”,R[j]);

/*出列*/R[j]=R[R[j]];/*删除第j个结点*/}printf(“%d\n”,R[j]);/*最后一个出列者*/}/*Josephusend*/第94页/共132页数据结构的程序实现全文共132页，当前为第94页。Josephus问题算法描述（续）voidmain(){intn,m,k;printf(“Josephus问题求解：”);scanf(“%d%d%d”,&n,&m,&k);printf(“n=%d,m=%d,k=%d\n”,n,m,k);Josephus(n,m,k);}/*mainend*/第95页/共132页数据结构的程序实现全文共132页，当前为第95页。9.4

数据结构在问题建模中的应用

9.4.1Josephus问题9.4.2教务管理与二分图9.4.3学籍管理系统中的数据组织第96页/共132页数据结构的程序实现全文共132页，当前为第96页。二分图

设G=(V，E)是一个无向图，其中V={v1，v2，…，vn}，E＝{e1，e2，…，en}。如果顶点集合V可以分割成为两个互不相交的子集X和Y，使图中每条边ei=(vi，vj)都具这样的性质：其一个端点vi是X中的顶点（即viX）而另一个端点vj是Y中的顶点（即vjY），则称图G是一个二分图（bipartitegraph）。第97页/共132页数据结构的程序实现全文共132页，当前为第97页。教务管理与二分图

在高等学校的教务管理中，处理学生选课是一项日常工作。每个学生可同时选修多门课程，每门课程也允许多个学生同时选修。这种学生与课程之间的关系可以用二分图表示为如右图所示，图中的顶点由学生和课程组成，边（s，c）表示学生s选修课程c。第98页/共132页数据结构的程序实现全文共132页，当前为第98页。教务管理与二分图（续）教务员经常需要做如下一些管理工作：登记学生选修的课程；撤销学生的修课登记；查看某个学生选修哪些课程；查看某个课程有哪些学生选修。这些管理工作即是对二分图做相应的插入、删除和检索操作。在现实社会中，诸如商店与商品、商店与顾客、技术人员与技术职称、教师与课程等许多管理问题都和学生与课程问题类似，都可以用二分图来表示。二分图是数据库等应用系统的重要的数据结构。第99页/共132页数据结构的程序实现全文共132页，当前为第99页。教务管理与二分图（续）

由于二分图中顶点集合V分割成为两个互不相交的子集X和Y，同一子集中（X中或Y中）的顶点无边相连，这就使得二分图的邻接矩阵呈现为一个对称分块矩阵：即二分图可以用特殊的存储结构矩阵B阵来表示。显然，用矩阵B表示二分图比邻接矩阵A节省存储空间。然而矩阵B也可能是一个稀疏矩阵，可针对具体情况作进一步的压缩存储处理，

第100页/共132页数据结构的程序实现全文共132页，当前为第100页。教务管理与二分图举例例如，前例中图的二分图SCG的邻接矩阵如下图(a)所示，为一对称分块矩阵；其特殊存储表示即矩阵B如下图(b)所示。第101页/共132页数据结构的程序实现全文共132页，当前为第101页。教务管理与二分图（续）

教务管理中的另一项重要的日常工作是安排教师教学工作。在一般情况下，每位教师通常可以胜任多门课程的教学，而在一个学期内只讲授他所胜任的一门课程；反之，在一个学期内一门课程只需一位教师主讲。这就需要对教师和课程作合理安排，我们可以用一个二分图来表示教师与课程之间的这种关系，教师和课程都是图中的顶点，边（t，c）表示教师t胜任课程c，右图给出了五位教师和五门课程之间关系的二分图。第102页/共132页数据结构的程序实现全文共132页，当前为第102页。教务管理与二分图（续）为每位教师安排一门课程，相当于为每个教师顶点选择一条和课程顶点相关联的边，使任何两个教师顶点不和同一课程顶点相邻接。这种安排课程给每位教师的问题，实际上是图的匹配问题。图匹配问题的一般描述如下：给定一个图G=(V，E)，若边集合E的一个子集M中任意两条边都不依附图中的同一个顶点，称M是图G的一个匹配（matching）；G的边数最多的匹配称作G的最大匹配（maximalmatching）。如果在图G的一个匹配中，图中每个顶点都是该匹配中某条边的端点，则称该匹配为图G的完全匹配（completematching）。图G的任何一个完全匹配，一定都是图G的最大匹配。第103页/共132页数据结构的程序实现全文共132页，当前为第103页。二分图TCG的匹配和最大匹配示例

下图(a)和(b)的实线边分别给出了前例中二分图TCG的一个匹配和一个最大匹配的示例。

第104页/共132页数据结构的程序实现全文共132页，当前为第104页。二分图TCG的匹配和最大匹配

为了求出一个图的最大匹配，显而易见的办法是列举出该图的全部匹配，然后选出边数最多的一个匹配。然而，这种方法的时间复杂度是边数的指数阶函数。因此，需要一种更有效的匹配算法。下面介绍一种利用增广路径求最大匹配的有效算法。设M是图G的一个匹配，我们将M中的边所关联的顶点称为已匹配顶点，其余顶点称为未匹配顶点。若P是图G中一条连通两个未匹配顶点的路径，并且在P上属于M的边和不属于M的边交替出现，则称P为一条关于M的增广路径（augmentingpath）。第105页/共132页数据结构的程序实现全文共132页，当前为第105页。二分图TCG的匹配和最大匹配（续）由利用增广路径求最大匹配的有效算法的定义可有如下结论：⑴一条关于M的增广路径的长度必为奇数，且路径上的第一条边和最后一条边都不属于M。⑵对于一条关于M的增广路径P，由对称差集运算M⊕P可以得到一个比M更大的匹配。即这个更大的匹配包括所有在M中但不在P中和在P中但不在M中的边的集合构成。⑶M为G的一个最大匹配，当且仅当不存在关于M的增广路径。

结论⑴和⑵是显而易见的。对于结论⑶，当存在一条关于M的增广路径时，由结论⑵知M不是最大匹配；反之，当M不是最大匹配时，一定可以找到一条关于M的增广路径。第106页/共132页数据结构的程序实现全文共132页，当前为第106页。二分图TCG的匹配和最大匹配（续）事实上，设N是一个比M更大的匹配，并令=(V，M⊕N)；因为M和N都是G的一个匹配，所以V中的顶点最多和M中的一条边相关联，也最多和N中的一条边相关联；于是的每个连通分量都是由M和N中的边交替组成的一条简单路径或环，每个环中所含M和N的边数相等，而每条简单路径是一条关于M的增广路径或关于N的增广路径，由于中的边M⊕N所含N的边数较M多，所以中必含一条关于M的增广路径。由此，求图G=(V，E)的最大匹配M的算法可描述如下：⑴置M为空集；⑵找出一条关于M的增广路径P，并用M⊕P代替M；⑶重复步骤⑵直至不存在关于M的增广路径，此时得到的匹配M即为G的最大匹配。第107页/共132页数据结构的程序实现全文共132页，当前为第107页。二分图TCG的匹配和最大匹配（续）

在上述算法中，关键问题是如何根据已有匹配M找出G中关于M的一条增广路径。为简化起见，我们只讨论G是二分图的情形。设M是G的一个匹配，用类似于图的广度优先搜索过程构造一棵树。设层号为i，当i=0时取G的一个未匹配顶点作为树根；当i为奇数时，将那些与第i-1层中一个顶点相关联但不属于M的边，连同该边相关联的另一个顶点一起添加到树上；