返回
§4.1 数据结构概述
§4.1.1 数据结构的定义
数据(data)是一些可以输入到计算机中的描述客观事物的符号,即信息的载体。这些符号可以是数值、字符、图象等。在计算机领域，人们把能够被计算机加工的对象，或者说能够被计算机输入、存储、处理、输出的一切信息都叫做数据。
数据的单位用数据元素(data element)表示，数据元素是计算机可以处理的最小数据单位，是一个数据整体中相对独立的单位。数据和数据元素是相对而言的，是整体和个体之间的关系。例如，对一个字符串来说，每个字符都是它的数据元素；对一个数组来说，每个数组元素都是它的数据元素。
数据元素也用记录（或结点或结构体）来表示，它是数据处理领域组织数据的基本单位，它又由更小的单位——数据项(item)（或成员）所组成，一个记录一般包括一个或若干个数据项。记录是数据的基本组织单位，数据元素经常表示为记录的形式，所以记录（结构体）和数据元素这几个术语往往不加区别地使用。
简单的说数据结构（data structure）就是研究数据和数据之间关系的一门学科，它包括三个方面。
① 数据的逻辑结构 ② 数据的物理结构 ③ 数据的运算 §4.1.1.1 数据的逻辑结构
数据元素之间的逻辑关系就是数据的逻辑结构。
一般情况下，一组数据元素并不是杂乱无章的，而是具有某种联系形式。这里的联系形式指数据元素与元素间的相互关系。数据之间的联系可以是固有的，也可以是根据数据处理的需要人为定义的。根据数据元素之间关系的不同特性，通常有以下三种基本结构。
① 线性结构 结构中的每个元素之间存在一个对一个的关系。 ② 树形结构 结构中的每个元素之间存在一个对多个的关系。
③ 图形结构或网状结构 结构中的每个元素之间存在多个对多个的关系。 其中，树形结构和图形结构统称为非线形结构。 数据结构通常用二元组表示，其形式如下：
Data_struct=(D,R)
其中D为数据元素的集合，R为数据元素之间关系的集合。即：
D={ai | 1≤i≤n,n≥0} R={rj | 1≤j≤m,m≥1}
ai 为第i个数据元素，n为数据元素的个数，特别地，当n=0，D为空集，则无结构可言。rj表示第j个关系，m为关系的个数。
然而讨论数据结构的目的是为了在计算机上实现对它的操作，因此还需研究如何在计算机中表示它。
§4.1.1.2 数据的物理结构
数据结构（包括数据及其数据之间的关系）在计算机存储器上的存储表示称为数据的物理结构或存储结构。由于存储表示的方法有多种，诸如顺序、链接、索引等，所以一种数据结构可以根据需要表示成一种或多种存储结构。
数据元素之间的关系在计算机中有两种不同的表示方法：顺序结构和非顺序结构，又称为顺序存储结构和链式存储结构。顺序存储结构的特点是借助元素在存储器中的相对位置来表示数据元素之间的关系。链式存储结构是借助指示元素存储位置的指针表示数据元素之间的关系。数据的逻辑结构和物理结构是两个密切相关的方面，以后读者可看到，任何一个算法的设计取决于选定的逻辑结构，而算法的实现依赖于采取的存储结构。
如何描述存储结构呢？虽然存储结构涉及数据元素及其关系在存储器中的存储方式，但由于本书是在高级语言的层次上讨论数据结构的操作，因此可以借助高级语言中提供的“数据类型”来描述它。例如可以用C语言中提供的“数组类型”来描述顺序存储结构，用“指针”来描述链式存储结构。
§4.1.1.3 数据的运算
研究数据结构，除了研究数据结构本身以外，还要研究与数据结构相关联的运算。这里的运算是指对数据结构中的数据元素进行的操作处理，而这些操作与数据的逻辑结构和物理结构有直接的关系，结构不同，则实现方法也不同。运算的种类很多，但常用的有以下几种：
1． 检索（查找）
在给定的数据结构中，找出满足一定条件的结点来，这个条件往往与一个或几个数据项的值有关。
2． 排序
根据给定的条件，将数据结构中所有结点重新排列顺序 3． 插入
在给定的数据结构中，根据某些条件，将一个结点插入到一个合适的位置。 4． 删除
在给定的数据结构中，根据某些条件，将一个结点删除。 5． 修改
修改数据结构中某些结点的值。
运算的种类很多，同一种运算也存在各种各样的算法。在一种数据结构中要进行那一
种或那几种运算，往往取决于要解决的实际问题。完成一种指定的运算，当然要选一种最好的算法。但对一种具体的数据结构来说，完成一种运算的效率较高，完成另外一种则可能较低，对另一种数据结构来说，情况可能正好相反。因此，要解决一个实际问题，数据结构的设计和算法的选择要结合起来考虑，对各种情况要反复比较，最终选择一个较好的数据结构和高效率的算法。
§4.2 线性表
§4.2.1 线性表的逻辑结构
线性表（linear list）是具有相同特性的数据元素的一个有限序列。该序列中所含元素的个数叫线性表的长度，用n表示，n≥0。当n=0时，线性表是一个空表，即表中不包含任何元素。当n≠0时，设序列中的第i个元素为ai (1≤i≤n)，则线性表的一般表示为：
（a1，a2，……，ai，……，an）
其中，a1为第一个元素，又称为表头元素，an为最后一个元素，又称为表尾元素。每一个元素在表中的位置用其下标来表示。线性表具有如下特点：
（1） 数据元素ai在不同的情况下含义不同。可以为一个数、一个字符或更复杂的信息；
但是在一个表中，元素类型必须相同。
（2） 表非空的情况下，除第一个元素以外，每个元素都有一个直接前驱；除最后一个元
素以外，每个元素都有一个直接后继。 线性表中的元素在逻辑上是有序的，即第i个元素处在第i-1和第i+1个元素的中间，这种逻辑上的有序性就是一种线性关系，所以线性表的逻辑结构是线性结构。
用二元组表示为： Linear_list=(D,R)
D={ ai | 1≤i≤n,n≥0, ai∈elemtype} /* elemtype为任何数据类型 */ R={r|r=< ai, ai+1 >1≤i≤n-1} 下面给出几个线性表的例子： （‘0’，‘1’，‘2’，‘3’，‘4’，‘5’，‘5’，‘6’，‘7’，‘8’，‘9’，‘-’，‘=’） （12，34，56，78，89，54，76，32，98） （“basic”, “fortran”, “pascal”, “cobol”）”
其中，第一个线性表数据元素为字符型，第二个线性表数据元素为数值型，第三个线性表数据元素为字符串。
§4.2.2 线性表的存储结构
线性表的存储结构有两种，即顺序存储结构和链式存储结构。具有顺序存储结构的线性表称为顺序表，具有链式存储结构的线性表称为线性链表。根据不同的需要对线性表可以进行多种操作，其基本运算有：
1． 清表 清除表中的结点使其成为空表。
2． 排序 根据给定的条件，将表中结点重新排列顺序。
3． 插入 根据条件在表中插入一个结点。 4． 删除 根据某些条件，将一个结点删除。 5． 修改 修改表中给定结点的值。
6． 检索（查找） 查找表中具有某一特征的结点。 7． 求长 求线性表的长度。
对线性表所采取的存储结构不同，其实现方法也不一样。下面分别介绍。 §4.2.2.1 线性表的顺序存储结构及其算法
线性表的顺序存储结构是线性表的一种最简单的存储结构，其存储方法是：在内存中为线性表开辟一块连续的存储空间，该存储空间所包含的存储单元数要大于等于线性表的长度（假定每个存储单元存储线性表中的一个元素）。
因为一个数组在内存中占据一段连续的存储单元，所以可以借助数组来为线性表的顺序存储开辟空间，如图4.1所示。其中L为每个元素占据的字节数，Loc(a1)为线性表的起始地址。
存储地址 内存状态 数据元素序号 Loc(a1) 1 a1 Loc(a1)+L a2 2 „ „ „ Loc(a1)+L*(i-1) ai i „ „ „ Loc(a1)+L*(n-1) an n
图4.1线性表的顺序存储结构示意图
另外为了存储线性表的长度，还要定义一个整型变量。若将线性表的顺序存储结构定义为一个数组与一个整型变量，则可将它们放在一个结构体中，C语言定义形式为：
#define N 1000 /* N为线性表的最大元素个数 */ typedef struct list
{ elemtype v[N]; int len; } LIST;
其中，N为线性表开辟的存储单元数，可以根据需要改变其大下。elemtype为线性表中元素的类型。设L为LIST型的变量，则L.len 为线性表的长度，L.v[i]为线性表中的第 i 个元素。
在上述定义的存储结构中，可以看到逻辑上相邻的两个元素在物理位置上也相邻，因此可以随机存储表中的任一元素，它的存贮位置可以用一个直观、简单的公式来表示。然而，这种存储形式也造成了这种存储结构的几个弱点：其一，插入、删除时须移动大量元素；其二，给表分配空间时需按最大的空间分配。
1． 插入运算
根据给定的条件不同，插入算法也不一样，如果要在线性表L的第i(0≤i≤L.len)个位置上插入一个元素x，那么只需要将第i个元素及其以后的所有元素后移一位，第i个位置上存入x，线性表的长度加1，如图4.2所示。
算法如下:
LIST inslist(LIST L,int i,elemtype x) { if (L.len= =N)
printf(“OVERFLOW\\n”); elseif (i<0)||(i>L.len)
printf(“position ERROR\\n”); else
{ for(j=L.len-1;j>=i;j--)
L.v[j+1]=L.v[j]; L.v[i]=x; L.len++; } return L } 数组下标 0 1 … i-1 i … len-1 L.v[i-1] L.v[i] … L.v[len-1] L.v[0] L.v[1] … （a）插入前 数组下标 0 1 … i-1 i i+1 … len L.v[0] L.v[1] … L.v[i-1] x L.v[i] … L.v[len-1] （b）插入后 图4.2顺序存储结构插入运算示意图 从算法中可见，当i的位置不合适时，插入无法进行。当表中有L.len个元素时，插入位置可以是从0到L.len。当插入位置在最后一个元素的后边（即下标L.len）时，不需要移动元素。
如果插入条件是：在线性表中的某一元素之前（或之后）插入一元素，则应先查找该元素的位置，然后利用上述方法实现即可。读者可自行编写该算法。 2． 删除运算
将线性表中的第i个元素删除的情况，可以用图4.3所示的方法实现。
数组下标 0 1 … i-1 i … len-1
L.v[0] L.v[1] … L.v[i-1] L.v[i] … L.v[len-1]
（a）删除前
数组下标 0 1 … i-1 i … len-2 len-1
L.v[0] L.v[1] … L.v[i-1] L.v[i+1] … L.v[len-1] L.v[len-1] （b）删除后 图4.3顺序存储结构删除运算示意图
只要将从第i+1个元素到最后一个元素向前各移动一个元素，表的长度减一即可，相应的算法为：
LIST dellist(LIST L,int i) /* 删除线性表L中的第i个元素 */ { if (i<0)||(i>=L.len)
printf(“position ERROR\\n”); else
{ for(j=i+1;j<=L.len-1;j++)
L.v[j-1]=L.v[j]; L.len--; }
return L }
从算法中可见，当i的位置不合适时，删除无法进行。
如果删除条件是：删除线性表中某一特定元素x，则应先查找该元素x的位置，然后利用上述方法实现即可。读者可自行编写该算法。 3． 检索（查找）
在线性表中检索值为x的元素，检索的方法很多，有顺序检索、折半检索、分块检索、散列检索等。下面仅介绍顺序检索，方法是，从线性表的第一个元素起，依次使每一个元素与值为x的元素进行比较，直到某个元素与x 相等（既查找成功）或查完所有元素都找不到值为x的元素（查找失败）为止。算法为：
int searchlist(LIST L,elemtype x)
{ for(i=0;i return i; } 4． 算法评价 上述的几个算法，总的执行时间与循环次数有关，而循环次数取决于元素的移动次数，所以通过元素的平均移动次数，对在顺序表中插入和删除一个元素的算法进行评估。为了讨论方便，设表长为n（即L.len）。 对于插入来说，若i=n，元素的移动次数为0，最少；当i=0时，元素的移动次数最多，为n，当0 p(ni) ii0n不失一般性，设在线性表的任何位置上插入元素的概率都相等，即pi=1/(n+1)，则元素的平均移动次数为： n1nPEis =pi(ni)== (ni)2n1i0i0可见在顺序表的第i个位置插入一个元素，最好情况是不移动元素，最坏情况是移动表中的所有元素，平均情况是移动表中的一半元素，在最坏和平均情况下，算法的时间复杂性为O(n)。 对于删除来说，若表长为n，则可以删除的元素范围是0≤i≤n-1。若i=n-1，元素的移动次数为0，最少；当i=0时，元素的移动次数最多，为n-1，在第i个位置上删除一个元素须移动元素的次数为n-i-1。若用qi 表示在第i个位置上删除一个元素的概率，则在长度为n的线性表中删除一个元素所需的平均移动次数为： PEds = nq(ni1) ii0n1同样不失一般性，设在线性表的任何位置上删除元素的概率都相等，即qi=1/n，则元素的平均移动次数为： n11n1PEds =qi(ni1)=(ni1)= 2ni0i0可见在顺序表的第i个位置删除一个元素，最好情况是不移动元素，最坏情况是移动表 中的所有元素个数减1，平均情况是移动表中的一半元素，在最坏和平均情况下，算法的时间复杂性为O(n)。 总之，插入和删除的平均时间复杂度均为O(n)。 查找算法的复杂度读者可自行分析。 §4.2.2.2 线性表的链式存储结构及其算法 由于链式存储结构不要求逻辑上相邻的元素物理位置上也相邻，故它没有顺序存储结构的弱点，但它也有局限性。 它的存储特点是用随机的存储单元存储线性表中的元素，其存储空间可连续、也可以不连续。因为存储空间的不连续性，所以在存储完每一个数据元素的内容以后，还应指出下一元素的存储位置，将这两部分信息共同称为一个结点。 一个链接表由n（n≥0）个结点组成，当n=0时称为空表。每一个结点中的指针域可以有一个，也可以有两个。有一个指针域的链表称为单链表，其中的指针域存储数据元素的后继结点的位置。有两个指针域的链表称为双链表，其中一个指针域存储数据元素的后继结点的位置，另一个指针域存储数据元素的前驱结点的位置。下面我们重点介绍单链表。 n1单链表的定义如下： typedef struct node {elemtype data; struct node *next; } NODE; NODE *H; 设单链表H中有n个元素，分别为(a1,a2,……an),可以用图4.4描述单链表的结构。 H „ a1 a2 an NULL 图4.4单链表示意图 其中H为单链表中第一个结点的地址，称为头指针。最后一个元素an所在的结点不存 在后继，因此其指针域的值为空(NULL)，从上面的结构中可以看到，链表在存储空间上的要求比线性表要付出更大的代价，因为它除了存储数据元素外，还要存储每个元素的后继元素的位置。 判断一个链表为空的条件为：H= =NULL。 有时，在单链表的第一个元素所在的结点之前附设一个结点——头结点。头结点的指针域存放第一个元素所在结点的存储位置，数据域不存储任何信息，因此单链表的头指针指向头结点，如图4.5（a）为带头结点的单链表的一般形式。如图4.5（b）为带头结点的单链表为空时的形式。 „ a1 an NULL a2 H (a) 带头结点的单链表 NULL H (b) 空的带头结点的单链表 图4.5 带头结点的单链表示意图 判断一个链表是否为空的条件是：H->next= =NULL 链表加上头结点以后将空表和非空表的处理统一起来，因而简化了单链表的实现算法。 下面介绍在这种存储结构上链表的几个主要操作。 1． 带头结点单链表的查找 设H为一带头结点的单链表的头指针，在线性表中查找第i（i>0）个元素所在的结点。要查找单链表中的某一结点，必须从头指针出发，沿结点的指针域往后找直到找到所要结点为止。算法如下： NODE *get(NODE *H,int i) {NODE *p; int j=1; p=H->next; while((p!=NULL)&&(j if (p!=NULL) return p; /* 返回所查结点的地址 */ else return NULL; /* 查找的位置不合适 */ } 查找元素的时间复杂度为O(n)。 2． 带头结点单链表的插入 设H为一带头结点的单链表的头指针，在线性表的两个元素a和c之间插入一个元素b，设p为存储数据元素a的结点的指针，设q为存储数据元素b的结点的指针，如图4.6(a)所示 „p a c „ „p a c „ q b q b (a) 插入前 (b) 插入后 图4.6单链表的插入示意图 从图中可以看出插入时需要修改两个指针，将a结点的指针域的值由指向c改为指向b，再使b的指针域的值指向c，从而实现改变a，b和c之间的逻辑关系，插入后各元素的关系如图4.6(b)所示。修改指针关系的语句为： q->next=p->next; p->next=q; 下面的算法是在链表H中第 i个位置上插入一元素为x的结点： void insnode(NODE *H,int i,int x) {NODE *p,*q; if (i= =1)p=H; else p=get(H,i-1); /* 查找插入元素的位置 */ if (p!=NULL) { q=(NODE*)malloc(sizeof(NODE)); q->date=x; q->next=p->next; p->next=q; /* 实现插入 */ } else printf(“ i<1或者i>表长，插入位置错误\\n”); } 与顺序表的插入比较，链表的插入更容易实现，不需要移动元素，只须修改几个指针，时间复杂度为O(1)。但是为了找到插入位置，需花费的时间复杂度为O(n)。 3．带头结点单链表的删除 删除操作和插入基本相同，应先找到待删结点的前驱结点的位置后再完成删除。如图4.7（a）所示，设b为待删除的元素，p为待删元素的前一结点的指针，删除结束后元素a的后继由b改为c，操作中将b所在结点的地址记为q，以便处理和回收结点，如图4.7（b）所示。 „p a c p „p „ a c „ b q b q (a) 删除前 (b) 删除后 图4.7单链表的删除示意图 删除语句为： q=p->next; p->next=q->next; free(q); 下面的算法是在头指针为H的带头结点的单链表中删除第i个结点： void delnode(NODE *H,int i) {NODE *p,*q; if (i= =1)p=H; else p=get(H,i-1); /* 查找删除元素的位置 */ if ((p==NULL)||(p->next==NULL)) printf(“表中无此结点\\n”); else {q=p->next; p->next=q->next; free(q); } } 与顺序表的删除比较，链表的删除也更容易实现，不需要移动元素，只须修改几个指针，时间复杂度为O(1)。同样为了找到删除位置，需花费的时间复杂度为O(n)。 4．不带头结点的单链表的删除 在不带头结点的单链表中进行操作时，一般情况下要区分第一个结点和表中结点，因为第一个结点的地址值发生变化后，表示链表的头指针H的值也会发生变化（参考图4.4），比如删除操作，若删除的元素为a1，则删除后H的值为a2的地址，若是在带头结点的单链表中进行操作则不同（参考图4.5（a）），此时即使删除的元素为a1，删除后H的值也不会发生变化。 下面给出在不带头结点的单链表中删除第i个元素的算法。用此算法和上面带头结点的单链表中删除第i个元素的算法进行比较，读者可发现两种方法的不同之处。 void del(NODE *H,int i) /*将头指针为H的链表中第i个结点删除 */ { NODE *p,*q; int m=1; if(H!=NULL) { q=H; if(i= =1) { H=H->next; /* 删除表头结点 */ free(q); } else { while(q!=NULL&&m if(q==NULL) printf(\"%d not been found\\n\没找到待删结点 */ else { p->next=q->next; /* 删除结点q */ free(q); } } } else printf(\"the list empty\\n\"); /* 表空 */ } 5．循环单链表和双向链表 指针的用途非常广泛，除了单链表以外，还有循环单链表和双向链表。 ① 循环单链表 如果有一个单链表其表尾元素的指针域的值不为NULL，而让它指向头结点，这样的链表叫循环单链表或环形链表。图4.8为带头结点的循环链表示意图： 循环单链表与单链表的大部分操作相同，如插入、删除、查找等。与单链表比较有以下不同点。 „ a1 an a2 H (a) 循环单链表 H (b) 空的表循环单链表 图4.8循环单链表示意图 1） 判断链表结束的条件不同。设p为链表中任意一结点的指针，在单链表中当某一结 点p的next域指向NULL时，则说明链表操作结束（p->next= =NULL）。而在循环单链表中没有指向NULL的指针，链表操作结束的条件应为：某一结点p的next域指向表头结点（p->next= =H）。 2） 从单链表的某一结点出发只能访问到其后继结点，所需的时间复杂度为O(1)，而循 环单链表除了能访问结点p的后继结点外，也能访问其前驱结点，其方法是从此结点出发，找到满足条件（q->next= =p）的结点q，则q为p的前驱结点，时间复杂度为O(n)。 如果一个链表为循环链表，则许多操作可只对链表设一个尾指针，而没有头指针，因为这样更利于链表的操作，如链表的合并等。 ② 双向链表 如果在每个结点上再增加一个指向线性表中每个元素的前驱结点的指针prior，就可以很方便的找到前驱结点（p->prior）或后继结点（p->next）。所以有时为了满足需要，也为了操作的方便，用双向链表对线性表进行定义和操作。双向链表的定义如下。 typedef struct dnode {elemtype num; struct node *prior, *next; } DNODE 其中prior为指向前趋结点的指针，next为指向后继结点的指针。 图4.9(a)为双向链表的示意图，图4.9(b)为空的双向链表的示意图， H NULL a1 (a) 双向链表 H NULL NULL (b) 空表 a2 „ an NULL 图4.9双向链表示意图 与循环单链表相同，也可以定义循环双链表。如图4.10(a)为循环双链表，图4.10(b)为空的循环双链表。 „ a1 an H a2 (a) 循环双链表 H ( b) 空表 图4.10 循环双链表示意图 在双向链表中凡涉及一个方向的操作与单链表一样。只是在做插入和删除时的操作不同。 1) 定位删除 设p为待删结点的指针，如图4.11所示， p x z y （a） 删除前 x y z （b）删除后 图4.11 双向链表中结点删除情况 删除语句为： p->prior->next=p->next; p->next->prior=p->prev; free(p); 2） 定位插入 设p为待插入结点的位置，待插结点指针为q,在p结点之前或之后插入均可。如图4.12为在p结点之前插入q结点的示意图。 在p结点之前插入的语句可描述为： q->prior=p->prior; p->prior->next=q; p->prior=q; q->next=p; p x z y s q （a） 插入前 p z x y s q （b）插入后 图4.12 双向链表中结点charu 情况 同样的，也可以在p结点之后插入q结点，插入语句可描述为： q->next=p->next; p->next->prior=q; p->next=q; q->prior=p; §4.3 特殊线性表 §4.3.1 栈 栈又称堆栈（Stack），是在程序设计中广泛应用的一种数据结构，就其逻辑结构而言，是一种特殊的线性表，其特殊性主要体现在做插入和删除时受限制。 栈是允许在一端进行插入和删除操作的特殊线性表，其中，允许进行插入和删除的一端叫栈顶，另一端叫栈底。向栈顶插入元素叫入栈、进栈或压栈，从栈顶删除元素叫出栈或退栈。 由于栈的插入和删除仅在栈顶一端进行，后进栈的元素必先删除，所以栈又叫后进先出（Last In First Out 简称LIFO）表。 设有三个元素，入栈序列为a、b、c，则可能的出栈序列有以下五种，如图4.13所示，其中s代表入栈，p代表出栈。 不可能得到的出栈序列为cab。 出栈序列 a b c a c b b a c b c a c b a 操作序列 s p s p s p s p s s p p s s p p s p s s p s p p s s s p p p 图4.13出入栈示意图 对于栈常进行的运算有以下几种。 ① 初始化 初始化栈为空。 ② 判空 判断栈是否为空，若为空，则返回真，否则返回假。 ③ 入栈 向栈顶插入一个元素。 ④ 出栈 删除栈顶元素。 ⑤ 读栈 取出栈顶元素。 §4.3.1.1 栈的顺序存储结构 1．定义 栈的顺序存储结构是利用一组地址连续的存储单元依次存储栈中元素，利用C语言中的结构体和数组对栈定义如下： #define N 1000 /* 设N为栈的最大元素个数 */ typedef struct stack {elemtype v[N]; int top； }STACK; 其中top中存储栈顶元素的编号，又称栈顶指针。elemtype为栈中元素的类型。v数组用来存储栈的实际元素。图4.14展示了顺序栈中元素与栈顶指针之间的关系。 „ top= -1 （a） 空栈 a b c „ top=2 (b) 元素a,b,c入栈后的状态 a b „ top=1 (c) 元素c出栈后的状态 图4.14 出入栈示意图 2．栈的运算 ① 初始化栈空 初始化栈时只须将栈顶指针设为-1即可。 void inistack(STACK *s) {s->top= -1;} ② 入栈 在栈中插入元素时，若top已指向下标为N-1的分量，则栈满，不可入栈。算法如下： void push(STACK *s,elemtype x) /* 将值为x的元素入栈*/ { if (s->top= =N-1) {printf(“栈满,overflow\\n”); exit(1);} else {s->top=s->top+1; s->v[s->top]=x;} } 算法的时间复杂度为O(1)。 ③ 出栈 当在栈顶删除元素时，首先要判断栈是否为空，若为空，则不能删除，否则将栈顶指针减1，原栈顶元素返回即可，算法如下： elemtype pop(STACK *s) { if (s->top= = -1) {printf(“栈空,downflow\\n”); exit(1);} else {s->top=s->top-1; return s->v[s->top+1];} } 算法的时间复杂度为O(1)。 3．双栈操作 „ top1= -1 top2=N （a） 两个栈均空时 a1 „ am „ bj „ b1 top1 top2 （b）两个栈均有若干元素入栈 a1 „ „ b1 top1 top2 （c）栈满时 图4.15 两个栈共享空间示意图 当在一个程序中需要同时使用具有相同类型的两个栈时，一种最直接的方法是为两个栈开辟一段存储空间，此时如果栈顶位置设置不当，会出现当一个栈满时，另一个栈还有许多空间的情况。较好的方法是将两个栈的栈顶的初始位置设在空间的两端，两个栈的入栈操作各自向中间延伸，当两个栈的栈顶相遇时栈满，如图4.15所示。 下面是两个栈共享空间时的定义和出入栈算法。 #define N 1000 /* 设N为两个栈总的最大元素个数 */ typedef struct stack {elemtype v[N]; int top1，top2; }LSTACK; 入栈算法： void push(LSTACK *s,int i, elemtype x) /* 将值为x的元素入栈*/ { if (s->top1+1= =s->top2) {printf(“栈满,overflow\\n”); exit(1);} else {switch (i) 1: s->top1=s->top1+1; s->v[s->top1]=x; break; 2: s->top2=s->top2-1; s->v[s->top2]=x; break; default : printf(“i不合法\\n”); } } 出栈算法： elemtype pop(LSTACK *s,int i) { elemtype x; switch ( i ) {1: if (s->top1= =-1) {printf(“栈空,downflow\\n”); exit(1);} else {x=s->v[s->top1];s->top1--;} break; 2: if (s->top2= =N-1) {printf(“栈空,downflow\\n”); exit(1);} else {x=s->v[s->top2];s->top2++;} break; default : printf(“i不合法\\n”); } return x; } §4.3.1.2 栈的链式存储结构（链栈） 由于栈的实际容量是动态变化的，当一个程序中同时使用多个栈时，为了防止栈满溢出，需要为每个栈分配较大的空间，此时往往会出现这样的情况，当一个栈已溢出，其它的栈还有很多的存储空间。这时就要讨论多个栈共享存储空间的问题。因为栈的容量不好事先估计，所以最好采用链式存储结构，也叫链栈。 链栈是只允许在表头进行插入和删除的单链表，表头指针可以作为栈顶指针。 图4.16为链栈的存储结构示意图。top为栈顶指针。 top „ a1 a2 an NULL 图4.16链栈示意图 链栈的定义如下： typedef struct node {elemtype data; struct node *next; } SNODE; SNODE *top; 栈空的条件为top= =NULL.。 1． 进栈操作 首先申请一结点new，若申请成功才可入栈，否则结束操作。入栈时将new结点插入栈顶指针之前即可。算法如下： void push(SNODE *top,elemtype x) {SNODE *new; new=(SNODE *)malloc(sizeof(SNODE)); /* 生成结点 */ if(new!=NULL) { new->data=x; new->next=top; top=new; } /*入栈 */ else {printf(“申请空间失败\\n”); exit(1);} } 2． 出栈操作 若链栈头指针为空，则栈空，否则删除栈顶结点并将栈顶指针后移。算法如下。 elemtype pop(SNODE *top) {SNODE *new; elemtype x; if (top!=NULL) {new=top; top=top->next; x=new->data; free(new); /* 出栈 */ return x; } else {printf(“栈空删除失败\\n”); exit(1);} } §4.3.2 队列 同栈一样，队列也是一种操作受限的线性表。它只允许在线性表的一端进行插入而在另一端进行删除操作，其中，允许进行插入的一端叫队尾，允许进行删除的一端叫队头。当队列中没有元素时叫空队列。 由于队列的插入和删除各在一端进行，所以最先进队的元素必先删除，即队列具有先进先出的特性，所以队列又叫先进先出（First In First Out 简称FIFO）表。 对队列可以进行的运算有以下几种： ① 初始化 初始化队列为空。 ② 判空 判断队列是否为空，若为空，则返回真，否则返回假。 ③ 入队 若队列未满，向队尾插入一个元素。 ④ 出队 若队列未空，删除队头元素。 ⑤ 读取队头元素 若队列未空，读取队头元素。 日常生活中队列的例子比比皆是。如购物排队、等车排队等；在计算机操作系统中，队 列的应用也非常广泛，如操作系统中的作业排队、进程排队等。根据操作的需要，队列的存储也可分为顺序存储和链式存储。 §4.3.2.1 队列的顺序存储结构 队列的顺序存储结构是利用一组地址连续的存储单元依次存储队列中的元素，但是因为队列分队头和队尾，所以对队列的定义除了一组地址连续的存储单元外还需要两个量分别存储队头和队尾指针。利用C语言中的结构体和数组对队列定义如下： #define N 1000 /* 设N为队列的最大元素个数 */ typedef struct queue {elemtype v[N]; /* elemtype为队中元素的类型 */ int front; /* 队头指针 */ int rear; /* 队尾指针*/ }QUEUE; QUEUE Q; 在进行操作时，约定队列的队头元素始终指向队头元素的前一位置，队尾元素指向队尾元素的实际位置。此时队列的出、入队变化图如图4.17所示。 从下图可以看出，入队列的命令可叙述如下： { Q.rear++ ; Q.v[Q.rear]=x ; } 类似的，出队列的命令可叙述如下： { Q.front++ ; } 在上述前提下，空队列时头、尾指针的关系如下： Q.front= =Q.rear 如图4.17中的(a)和(c)。 值得考虑的是队列满的判断条件是什么？假设当前队列处于图4.17的（d）状态，此时Q.rear=N-1，显然不能作入队操作，（因为Q.rear+1=N，超过了队列的最大容量）但是队列里还有剩余空间，这种现象称为假溢出。 6 g Q.rear 5 f 4 e Q.rear 3 d Q.rear Q.front Q.front 2 c 1 b 0 a Q.rear=-1 Q.front= -1 Q.front= -1 (a) (b) (c) (d) (a) 空队列； （b）a,b,c,d相继入队列； （c） a,b,c,d相继出队列； （d）e,f,g相继入队列； 图4.17 顺序结构队列的头、尾指针变化情况 解决“假溢出”的办法有两个。 其一：将队列中的所有元素向前移动，使队列中的第一个元素位于第0分量中，且置队头指针为-1。这种方法较费时。 其二：将队列设想为一个循环队列，即第0分量连在第N-1分量之后，使向量v成为一个首尾相接的环，即如果Q.rear+1等于N,则Q.rear=0;如图4.18所示： N-1 0 1 Q.rear „ Q.front 图4.18 循环队列示意图 此时，入队操作可叙述为： { Q.rear=(Q.rear+1)%N ; Q.v[Q.rear]=x ;} 相应的出队操作可叙述为： { Q.front=(Q.front+1)%N ;} 然而，此时队列又出现一个新问题，即如何判断队空和队满？ 假设当前循环队列的状态如图4.19(a)所示。 Q.rear Q.rear Q.front b c b c a a f e d Q.front Q.front Q.rear (a) 队列未满时 (b) 队列满时 （c）队列空时 图 4.19 循环队列的头尾指针变化情况示意图 现有三个元素相继入队，则队列满如图4.19(b)，此时Q.front=Q.rear。又设在图4.19(a)状态下，有三个元素相继出队，则队列空如图4.19(c)。从图中可以看到这两种情况都存在等式Q.front=Q.rear，由此可见不能只凭该等式去判断队空还是队满。可以有两种方法处理此问题，其一是另设一标志表示队满或队空；其二是少用一个存储空间，以尾指针加1等于头指针作为队满的条件。此时队满和队空分别如图4.20所示。 Q.rear Q.front b c d a e Q.front Q.rear (b) 队列满时 （c）队列空时 图 4.20 循环队列的队满和队空示意图 下面是循环队列的入队和出队算法。 void addqueue(QUEUE Q,elemtype x) /* 入队 */ { if ( Q.front= =(Q.rear+1)%N ) {print(“ 队满，上溢\\n”); exit(1); } else {Q.rear=(Q.rear+1)%N; Q.v[Q.rear]=x; } } elemtype delqueue(QUEUE Q) /* 出队 */ { elemtype x; if ( Q.front= =Q.rear ) {print(“ 队空，下溢\\n”); exit(1); } else {Q.front =(Q.front+1)%N; x=Q.v[Q.front]; return x; } } §4.3.2.2 队列的链式存储结构 利用带头结点的单链表来存储队列，称为队列的链式存储结构。因为一个队列需要队头和队尾两个指针才能更方便其操作，所以在链队列里，设两个指针，其一指向带头结点的单链表的头结点，称为队头指针。其二指向单链表的表尾结点，称为队尾指针，其定义如下： typedef struct node {elemtype data; struct node *next; } QNODE; QNODE *front,*rear; 链队列如图4.21所示 Q.front „ a1 an NULL a2 Q.rear 图4.21(a) 链队列 Q.front NULL Q.rear 图4.21.(b) 空队 与线性表比较，链队列的操作更方便，入队只需要在表尾添加结点，出队在表头删除结点即可。链队列的出入队算法如下： 1． 入队操作 首先申请一结点new，若申请成功才可入队，否则结束操作。入队时将new结点插入链队列最后即可。算法如下： void insqueue(QNODE *front, QNODE *rear, elemtype x) {QNODE *new; new=(QNODE *)malloc(sizeof(QNODE)); if(new!=NULL) { new->next=NULL; new->data=x; rear->next=new; rear=new; } else {printf(“申请空间失败\\n”); exit(1);} } 2． 出队操作 若链队列的结点个数大于1时，只须修改队头指针的next域的值，若链队列的结点个数等于1时，出队列操作除修改队头指针的next域的值外，还应该修改尾指针。如图4.22所示。 Q.front „ a1 an NULL a2 Q.rear 图4.22(a) Q.front Q.front NULL Q.rear a1 NULL Q.rear 图4.22.(c) 图4.22.(b) 图4.22 （a）结点个数大于1时，出队示意图 （b）结点个数等于1时，删除前 （c）结点个数等于1时，删除后 算法如下： elemtype pop(QNODE *front, QNODE *rear) {QNODE *new; elemtype x; if (front= =rear) {printf(“链队列空，删除失败\\n”); exit(1);} else { new=front->next; front->next =new->next; if (new->next= =NULL)rear=front; x=new->data; free(new); return x; }} §4.3.3串 串是每个数据元素仅由一个字符组成的特殊线性表。 §4.3.3.1 串的定义 串是字符的一个有限序列，表示为： String=‟a1a2a3…an‟ 其中，单引号为字符串的起始界限符，不属于字符串本身的字符，ai(1≤i≤n,n≥0),表示非空字符串中的第i个字符，n为串中字符的个数，称为串的长度；当n=0时，表示空串，即串中不含任何字符。由一个或多个空格字符组成的串称为空格串。 串中任意个连续的字符组成的子序列称为该串的子串。相应的包含子串的串称为主串。称某一个字符在主串中的序号为该字符在串中的位置。用子串的第一个字符在主串中的位置 作为子串在主串中的位置。 当两个串的长度相等，并且每个对应位置上的字符均相等时，称两个串是相等串。 例如： s1=„‟ s2=„ ‟ s3=„data structure‟ s4=„This is a pen‟ s5=„is‟ 上面的串长分别为0、3、14、13、2，其中s1为空串，s2 为空格串，串s5 是s4 的子串，串s4 是串s5 的主串，串s5 在串s4中的位置是3。值得注意的是：空串是任意串的子串，任意串又是自己的子串。 因为字符串是数据元素为字符型数据的特殊的线性表，因此对线性表的一切运算都能够对字符串进行。从字符串的表示来看，它是字符的紧密排列。能够用它来描术事物的基本属性，如用串表示姓名、产品名称等，就如同用整型数据表示年龄、用浮点型数据表示职工工资一样。因此对简单类型数据可做的操作如赋值、输入、输出等都能够对串进行操作。 除此之外对串还可进行的操作有（设s、s1、s2均为串）： （1） 求串长length(s) 返回串中字符的个数。 （2） 取子串substr(s,i,n) 从串s中的第i个位置开始取出n个字符构成一个串，其 中的参数应满足：1≤i≤length(s), 1≤n≤length(s)-i+1。 （3） 串连接cancat(s1,s2) 将串s2连接在串s1之后组成一个新串，新串为s1。 （4） 求子串位置 index(s,s1) 从主串s中求出首次与子串s1相等的串，若s中不 存在s1，则返回0值，否则返回子串s1在主串s中的位置。例如 index(„this is a book‟,‟is‟)=3 index(„this is a book‟,‟books‟)=0 求子串在主串中的位置的运算也叫模式匹配。 （5） 替换操作 replace(s,s1,s2) 用串s2替换s中所有与子串s1相等的且不重叠的子 串。例如： s=„this is a book‟ 则执行replace(s,‟is‟,‟are‟)后，s变为‟thare are a book‟。 利用以上几种运算还可以实现串的插入与删除操作。 §4.3.3.2 串的顺序存储结构 串的存储也分为链式存储结构和顺序存储结构。 串的顺序存储结构是利用一块地址连续的存储单元存储串中的字符序列。用c语言描述时除了描述串本身之外，还应指出串的实际长度。描述如下： #define N 1000 /* N为串中实际字符的最大可能值 */ char string[N]; C语言中，串的实际长度为串结束符‘\\0’之前的所有字符。 当计算机的存储结构采用字编址时（1字=4字节），数组的一个分量至少占一个字的存 储单元，此时串的存储结构有两种存储格式：紧缩存储格式和非紧缩存储格式。所谓非紧缩存储格式是一个字的存储单元存放1个字符，所谓紧缩存储格式是一个字的存储单元存放4个字符，设串为‘c language’则紧缩存储格式和非紧缩存储格式示意图如图4.23所示。 c l a n g c l a u n g u a a g e g e (b) 紧缩存储格式 (a) 非紧缩存储格式 图 4.23 串的顺序存储结构 从上图中可以看出，与非紧缩存储格式相比，紧缩存储格式比较节约存储单元，但对串的访问要相对慢一些，因为要花费时间去分离同一字中的单个字符，非紧缩存储格式操作方便，却浪费3/4的存储空间。两种存储格式在作插入和删除时都要移动字符。 当计算机采用字节编址时，串的顺序存储结构中各种操作的实现都很方便。 §4.3.3.3 串的链式存储结构 串是一种特殊的线性表，也可以采用链式存储方式。其链式存储结构描述如下： typedef struct gnode {char data; struct gnode *next; } GNODE; 与线性表的链式存储结构比较，串的定义中数据类型为char，而线性表为elemtype，即任意类型。 由于串结构的特殊性，则用链式结构存储串时，存在一个“结点大小”的问题，每个结点可以存储一个字符，也可以存储多个字符。如果是存储多个字符，则最后一个结点不一定被串全部占满，此时可以用一些特殊的字符去填充。如图4.24所示。设串s=‟c language‟。 H e NULL c „ l （a）结点含的字符个数为1 H c la ngua ge## NULL （b）结点含的字符个数为4 图4.24 串的链式存储结构 当串采用链式存储结构时，存在一个空间利用率的问题，即存储密度。存储密度的定义为： 存储 = 串值所占的存储位数 实际分配的存储位数设一个next指针域占两个字节，当一个结点包含的字符数为1时，存储密度为1/3，当一个结点包含的字符数为4时，存储密度为2/3。结点的存储密度越小，存取越方便，然而存储空间的利用率越低。扩大“结点大小”可以提高存储密度，但是在做串的插入和删除时，可能会引起大量字符的移动。 从上述两种存储结构的讨论可知，无论采用什么方式存储都有一些弊端。若采用顺序存储结构，由于串类型定义中事先定义了一个串允许的最大长度，则当串较小时，浪费空间。另外串的某些操作如连接、插入等都会受到限制。当采用链式存储结构时，虽然串长不受限制，却存在存储密度的制约。所以在实际操作中要根据系统的要求及所采用的语言来决定采用那种方式存储及定义串。 §4.3.4数组 在各种高级语言中均有数组的定义和使用，从结构上看，数组是线性表的推广，下面只讨论二维数组的逻辑结构定义及使用方法。 §4.3.4.1 数组的定义 二维数组如数学中的矩阵、日常生活中的各种报表，都是行、列性质的矩形表，表中的每个元素具有相同属性，例如一个m行n列的数组可定义为： a11 a12 „ a1n Am*n= a21 a22 „ a2n „ am1 am2 „ amn 从逻辑结构上看，一个m行n列的二维数组含有m*n个元素，每个元素都受到行和列两个关系的制约。从行上看aij 既是ai,j-1的直接后继，又是ai,j+1 的直接前驱，ai1 无前驱，ain无后继，即每一行元素都是一个线性表。同样的从列上看，aij 既是ai-1,j 的直接后继，又是ai+1,j的直接前驱，a1j无前驱，amj无后继，即每一列元素也是一个线性表。所以二维数组的每一个元素既在一个行表中，又在一个列表中，每个元素都受到两个关系制约。如果将每行元素看作一个整体，则二维数组是如下形式的线性表： Am*n=（（a11 a12 „ a1n），（a21 a22 „ a2n），„，（am1 am2 „ amn）） 其每个元素都是一个线性表，同样的将二维数组的每列元素看作一个整体，则二维数组可表示为如下形式： Am*n=（（a11 a21 „ am1），（a12 a22 „ am2），„，（a1n a2n „ amn）） 所以二维数组是一种特殊形式的线性表。其特殊性主要体现在线性表中的每个元素又是一个线性表。 三维数组是二维数组的推广，所以三维数组中每个元素都受三个关系的制约。每个元素有三个直接前驱和三个直接后继（特殊元素除外）。推广到m维数组，每个元素最多受m个关系的制约。每个元素有m个直接前驱和m个直接后继（特殊元素除外）。 对数组的运算通常有以下几种： （1） 给定一组下标，存取数组元素。 （2） 给定一组下标，修改数组元素。 一般地，不对数组做插入和删除操作，数组的运算效率主要取决于存取各行、列中元素的总时间，而存取元素又与数组本身的存储结构有关。下面讨论二维数组的存贮方式。 §4.3.4.2 数组的顺序存储结构 由于计算机的存储单元是一维的结构，而数组是多维结构，要将多维结构的数组元素存贮到一维的空间里，就要考虑存放顺序的问题。对于一个m行n列的二维数组来说，可以以行为主序存贮，也可以以列为主序存贮。 1． 以行为主序存贮 存放时先存放第一行，再第二行，依次，„。所以元素的存放顺序为： （a11 a12 „ a1n a21 a22 „ a2n „ am1 am2 „ amn） PASCAL和C语言中数组都是以行为主序存放的。 设一个m行n列的数组中每个元素占L个字节，元素a11的存放地址为Loc(a11),则元素aij的存放地址可以表示为： Loc(aij)=Loc(a11)+(i-1)*n*L+(j-1)*L 2． 以列为主序存贮 以列为主序的存贮方式是存放时先存放第一列，再第二列，依次，„。所以元素的存放顺序为： （a11 a21 „ am1 a12 a22 „ am2 „ a1n a2n „ amn） 同样的设数组中每个元素占L个字节，则元素aij的存放位置是：前面已存放了j-1列个元素，每一列有m个元素，对于第j列来说，也存放了i-1个元素。设元素a11的存放地址为Loc(a11),则元素aij的存放地址可以表示为： Loc(aij)=Loc(a11)+(j-1)*m*L+(i-1)*L 可以看出不管采用以行为主序存贮还是以列为主序存贮，数组元素的存放位置是其下标的线性函数，一旦数组下标确定，元素类型确定（则每个元素所占的字节数也确定了），计算存放位置的时间仅取决于乘法的时间，因此存取数组中每个元素的时间相等。我们称具有这一特点的存贮结构为随机存贮结构。 同样的可以写出三维数组和多维数组元素存贮地址的计算公式。 §4.3.4.3 矩阵的压缩存储结构 通常在数值分析中，经常会用到一些阶数很高的矩阵，同时此类矩阵中有许多值相同的元素或零元素。有时为了节约空间，采用压缩存储。所谓压缩存储是指为多个值相同的元素分配一个存储空间，对零元不分配空间。 假设值相同的元素或零元素在矩阵中的分布有一定的规律，称此类矩阵为特殊矩阵，反之称为稀疏矩阵。其实稀疏矩阵无确切的定义，实际操作中人们只是凭直觉来了解。如果在高阶矩阵中非零元素的分布无规律可寻且个数远远少于矩阵中的元素个数，就可以认为此类矩阵为稀疏矩阵。下面分别讨论这两种矩阵的压缩存储方式。 1． 特殊矩阵的压缩存储结构 下面讨论两种特殊矩阵的压缩存储结构。其一为对称阵，其二为三对角阵。 ① 对称阵 若一个n阶矩阵中的元素满足下面的条件 aij=aji 1≤i,j≤n 则称此矩阵为n阶对称阵。 2 对于对称矩阵，我们可以为每一对对称元分配一个存储空间，则可以将n个元素压缩存储到n(n+1)/2个元素的空间中。不失一般性，我们可以以行为主序存储其下三角（包含对角线）中的元素，设对称矩阵形式为： a11 a12 „ a1n a21 a22 „ a2n An*n= „ an1 an2 „ ann 其中虚线中的元素为要存储的元素，将下三角中的元按以行为主序存放为： ( a11 a21 a22 a31 „ an1 „ ann) 从第一行到第i-1行的非零元个数为： kk1i1i(i1) 2i(i1)则在一维的地址空间里元素aij的存放位置为： Loc(aij)=Loc(a11)++j-1 (1≤j≤i≤n) 2此种存储方式同样适用于三角矩阵。所谓上（下）三角矩阵是指矩阵的下（上）三角中的元均为常数或零的n阶矩阵。此时除了存储上（下）三角矩阵中的元素之外再加一个存储常数的空间即可。 ② 三对角阵 设矩阵Ann的形式如下： a11 a12 0 0 „ 0 0 a21 a22 a23 0 „ 0 0 An*n= 0 a32 a33 a34 „ 0 0 „ „ 0 0 „ 0 an,n-1 ann 这种矩阵的非零元分布在以主对角线为中心的带状区域中，即除了主对角线和主对角线邻近的上、下方元素外，所有其它元素均为零。 若以行为主序的方式存储此矩阵，则元素的存放次序为： ( a11 a12 a21 a22 a23 a32 „ an,n-1 ann) 在一维空间里，第i行元素的起始存储地址为： Loc(a11)+3(i-1)-1 则元素aij的存放地址为： Loc(aij)=Loc(a11)+2(i-1)+j-1 其中|i-j|≤1; 从上述两种矩阵的压缩存储方式可见，一旦规定了数组的维数及界偶，便可为它分配存储空间，同时只要第一个元素的地址知道，便可依据上述公式求得相应的数组元素的存放位置。 2． 稀疏矩阵的压缩存储结构 在存储稀疏矩阵时，为了节约存储单元，只存储非零元素，但因为非零元的分布无规律，因此在存储非零元的同时还应记下它所在的行下标和列下标，这样稀疏矩阵的每一个非零元由一个三元组（行号，列号，元素值)唯一确定。设有稀疏矩阵 0 0 0 0 7 0 0 3 0 0 0 0 0 0 A6*7= 0 2 0 0 0 1 0 0 0 0 –3 0 0 0 0 0 0 0 0 0 0 0 18 0 0 0 0 0 则线性表 （（1，5，7）（2，1，3）（3，2，2）（3，6，1）（4，4，-3）（6，2，18）） 再加上（6，7，6）这一组稀疏矩阵的行、列及非零元个数的三元组便可作为该矩阵的另一种描述。而由上述三元组线性表的不同存储结构可引出稀疏矩阵的两种压缩存储方式：三元组表和十字链表。假设以顺序存储结构来表示三元组的线性表，则可得到三元组的一种存储方式──三元组表，假设以链式存储结构来表示三元组的线性表，则可得到三元组的另一种存储方式──十字链表。本节主要介绍三元组表。 三元组表可定义如下： #define N 100 /* 非零元个数 */ typedef struct { int i, j; elemtype x; }SYZ1; /* 三元组中每个元素所在的行号、列号、元素值*/ typedef struct { int mu, nu,vu; /* 分别表示矩阵的行数、列数、非零元个数*/ SYZ1 v[N]; }SYZ; 当稀疏矩阵以三元组存储以后，矩阵的某些运算如相加、相减、相乘、转置等都要做相应的改变。若运算结果所形成的矩阵也是稀疏矩阵，则可以用三元组表存储之；若运算结果所形成的矩阵不是稀疏矩阵，则可以用二维数组存储之。具体情况应视实际操作数据而定。 §4.4 树 §4.4.1 树的定义及存储结构 §4.4.1.1 树的定义 树型结构（简称树）是一种重要的非线形数据结构，在这类结构中，元素之间存在着明显的分支和层次关系。树型结构广泛存在于客观世界中，如家族关系中的家谱，各单位的组织机构，计算机操作系统中的多级文件目录结构等。 树是n(n>=0)个结点的有限集。当n=0时为空树，否则为非空树；在一棵非空树中：（1）有且仅有一个称为根的结点；（2）其余的结点分为m(m>=0)个互不相交的子集T1，T2，T3，„Tm，其中每一个集合本身又是一棵树，并且称为根的子树。显然，树的定义是递归的，树是一种递归结构。 图4.26为一棵树的示意图，它是由根结点AA 和三棵子树T1，T2，T3组成，三棵子树的根结点分 T3 T1 B 别为B，C，D，这三棵子树本身也是树。 C D 树的二元组表示为： TREE=(D,R) E F G D={di | 1≤i≤n,n≥0 di∈elemtype} R={r} T2 其中n表示树中的结点数，n=0时为空树。H I J n>0时为非空树，对于一棵非空树，关系r应满足 图4.26 树的结构 下面条件： （1） 有且仅有一个结点没有直接前驱，该结点为树的根。 （2） 除树根结点外，其余每个结点有且仅有一个直接前驱结点。 （3） 每个结点（包含根结点）可以有任意多个（包含0）直接后继结点。 对于图4.26所示的树，若用二元组表示其关系r可写为： r={ 其中A为根结点，无前驱，后继是B、C、D，其余每个结点各有一个前驱，B的后继是E， C的后继为F、G，F的后继为H、I、J，E、H、I、J、G、D无后继。 下面简述本节中将用到的树的基本术语。 结点的度：一个结点的子树的数目（或每个结点的后继结点数）为结点的度。 树的度：树中度数最大的结点的度为树的度。 叶子结点（终端结点）：度为0的结点为叶子结点。 分支结点（非终端结点）：度不为0的结点为分支结点。 孩子结点和双亲结点：每个结点的直接后继结点或每个结点子树的根结点为该结点的孩子结点。相应的，该结点为其孩子结点的双亲结点。 兄弟结点：具有同一双亲的孩子结点互为兄弟结点。 结点的子孙：以某结点为根的子树中的任一结点均为该结点的子孙。 结点的祖先：从根到该结点所经分支上的所有结点为该结点的祖先。 结点的层次：根结点的层数为1，其余结点的层数为其双亲结点的层数加1。 树的深度：树中结点的最大层数为树的深度。 有序树和无序树：树中结点同层间从左到右有次序排列，不能互换的树称为有序树，否则为无序树。 森林：是m(m≥0)棵互不相交的树的集合。 §4.4.1.2 树的存储结构 树的存储结构根据需要有多种形式，可以顺序存储，也可以链式存储。因为树是多分支非线性表，采用顺序方式存储时，因结点的分支数目不同，操作很不方便。通常树都采用链式存储。每个结点有多个指针域，其中每一个指针指向一棵子树的根结点。每一个结点的格式有两种：同构型和异构型。如图4.27所示。 data chd1 chd2 „ chdd (a) 同结点结构 data m chd1 chd2 „ chdm (b) 异结点结构形 图4.27 树的链式存储结构 所谓异结点结构形是指根据每个结点的度数为每个结点分配指针域，4.27（b）中的m值为该结点的度。此种存储方式虽然节约空间，但操作不方便。 所谓同结点结构形是指每个结点的指针域的个数相同，取树的度数值。4.27（a）中的下标d是树的度。这样的形式运算方便，但由于树中有很多结点的度数小于树的度，使链表中有很多空链域。空间浪费，但操作方便。 假设有一棵具有n个结点的k叉树，则必有n*k个指针域，其中有用的指针域有n-1个，空链域个数为： n*k-(n-1)=n(k-1)+1（个） k值越大，空链域越多。由此可见，k=2的树的空链域较低。所以下面主要讨论二叉树结构。 §4.4.1.3 树的主要运算 树的主要运算有以下几种。 ① 建树：建立一棵树。 ② 求树根：求树的根结点。 ③ 求双亲：求树中某一结点的双亲结点。 ④ 求孩子：求树中某一结点的孩子结点。 ⑤ 插入子树：在树中某一结点上插入一棵子树。 ⑥ 删除子树：删除树中某一结点的一棵子树。 ⑦ 遍历操作：按照某种次序访问树中的每个结点，并且每个结点仅访问一次。 还有其它一些操作，在此不一一列举。 §4.4.2 二叉树的定义及存储 §4.4.2.1 二叉树的定义 二叉树是一种有序树，其特点是树中每个结点至多只有两棵子树，并且，二叉树的子树有左右之分，次序不能任意颠倒。 二叉树的递归定义为：二叉树或者是一棵空树，或者是一棵由一个根结点和两个分别称为左子树和右子树的、互不相交的二叉树所组成。由于左子树和右子树分别是一棵二叉树，则由二叉树的定义，它们也可以为空二叉树。下面给出二叉树的五种基本形态，如图4.28所示： （a） (b) (c) (d) (e) 图4.28二叉树的五种形态 (a) 空二叉树 (b)二叉树只有根结点(c) 右子树为空的二叉树 (d) 左、右子树都存在的二叉树 (e) 左子树为空的二叉树 §4.4.2.2 二叉树的基本操作 与树相同，二叉树的基本操作也有以下几种。 ① 建树：建立一棵二叉树。 ② 求树根：求二叉树的根结点。 ③ 求双亲：求二叉树中某一结点的双亲结点。 ④ 求左孩子：求二叉树中某一结点的左孩子结点。 ⑤ 求右孩子：求二叉树中某一结点的右孩子结点。 ⑥ 插入左（右）子树：在二叉树中某一结点上插入一棵左（右）子树。 ⑦ 删除左（右）子树：删除二叉树中某一结点的左（右）子树。 ⑧ 遍历操作：按照某种次序访问二叉树中的每个结点，并且每个结点仅访问一次。 还有其它一些操作，在此不一一列举。 §4.4.2.3 二叉树的性质 性质1：在二叉树的第i层上最多有2i-1个结点（i≥1）。 利用归纳法证明： i=1时，二叉树上只有一个根结点，显然正确。 设对于所有的j(1≤j 性质2：深度为h的二叉树最多有2h-1个结点(h≥1)。 证明：由性质1知：深度为h的二叉树最多结点数为： 第i层的最大结点数=2i1i1hhi1=2h-1 一棵深度为h且具有2h-1个结点的二叉树称为满二叉树。如图4.29为一棵深度为4的满二叉树示意图。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 图4.29 深度为4的满二叉树 如果对一个满二叉树的结点按从上到下，从左到右进行编号，如图4.29所示，则一个深度为h的满二叉树最大结点的编号为2h-1。若一个二叉树的叶子结点分布在最后两层（其余层均满），且最后一层从右边起连续缺若干个结点，则此二叉树为完全二叉树。如图4.30所示。图4.31为非完全二叉树示意图。 1 1 2 3 2 3 4 5 6 7 4 5 6 8 9 10 7 8 9 10 图4.30 有10个结点的完全二叉树 图4.31 非完全二叉树示意图 性质3：二叉树上叶子结点数等于双分支结点数加1。 证明：用n、n0、n1、n2分别表示二叉树的结点数、度为0的结点数、度为1的结点数 和度为2的结点数，所以有： n= n0+n1+n2 另外，在一棵二叉树中，所有结点的分支数是度为1的结点数加上度为2的结点数的两倍。又知，除根结点外，每一结点向上都有一分支指向其双亲，所以分支数为n-1，分支数加1为结点数，则有： n0+n1+n2= n1+2n2+1 即n0= n2+1 性质4：具有n(n>0)个结点的完全二叉树的深度为log2(n1) 证明：设所求二叉树的深度为h，由完全二叉树的定义可知，它的前h-1层结点数都是满的，第h层可以满，也可以不满。则有如下等式： hh 2h-1-1 在本书中用x表示不大于x的最大整数，用x表示不小于x的最小整数。 性质5：对有n个结点的完全二叉树中的结点按从上到下、从左到右进行编号，则对编号为i(1≤i≤n,n≥1)的结点有： （1） 若i>1，当i为偶数时，i 的双亲结点的编号为i/2；当i为奇数时，i 的双亲结 点的编号为（i-1）/2； （2） 若2*i≤n,则结点i的左孩子结点的编号为2i,否则无左孩子结点，即结点i 为叶子结点； （3） 若2*i+1≤n,则结点i的右孩子结点的编号为2i+1,否则无右孩子结点，即结 点i为叶子结点； 可参考图4.30进行理解。 §4.4.2.4 二叉树的存储结构 同线性表一样，二叉树的存储也分为顺序存储和链表存储。 1． 顺序存储 用一组连续的存储单元存储二叉树中的数据元素称为顺序存储。 顺序存储二叉树时，首先对二叉树中的结点按照满二叉树的形式进行编号，不存在的结点的也要编号，之后将编号为i的结点存储在数组的第i 个分量中。如图4.32为图4.30和图4.31所表示的树的顺序存储结构示意图。 下标 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 （a） 完全二叉树的顺序存储 下标 1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 4 5 6 7 8 9 10 （b）一般二叉树的顺序存储 图4.32二叉树的顺序存储 在二叉树的顺序存储结构中，各结点之间的关系可以通过下标计算出来，因此访问每一个结点及其双亲都很方便，如对于编号为i的结点其双亲结点的编号为i/2；若存在左孩子结点，则其编号为2*i, 若存在右孩子结点，则其编号为2*i+1。 二叉树的顺序存储结构比较适合于满二叉树和完全二叉树，它能够充分利用存储空间，但对于一般的二叉树，特别是对于那些单支结点较多的二叉树来说就不合适，因为将造成太多空间的浪费，因此，对于一般的二叉树一般采用链式存储。 2． 链式存储 在二叉树的链式存储结构中，设计不同的结点结构，就构成不同的链式存储结构。 如果每个结点结构由一个数据域和两个分别指向其左、右子树的指针组成，其结点结构为： lchild data rchild 其中，data表示数据域，用于存储对应的数据元素。lchild和rchild中分别存储左、右孩子结点的存储位置，这种存储方式叫二叉链表。 如果在上述存储结构中再加一个指向其双亲结点的指针域parent，存储结构为： lchild data parent rchild 这种存储方式叫三叉链表。在这种存储结构中，既便于查找每个结点的孩子结点，又能找到其双亲结点，当然也带来存储空间的浪费。设有一二叉树如图4.33所示。则其对应的二叉链表如图4.34和三叉链表结构如图4.35所示。 若一个二叉树有n个结点，采用二叉链表表示，则有n+1个空链域。前面曾讨论过如果有一棵具有n个结点的k叉树，则必有n*（k-1）+1个空链域，空链域越多，空间越浪费。如果能将树转换为二叉树，采用二叉链表存储，则可大大节约存储空间。下面就讨论树与二叉树的转换问题。 A A B ^ C B C ^ D ^ ^ E ^ F ^ D E F ^ G ^ G 图4.34 二叉链表示意图 图4.33 二叉树 A ^ B ^ C ^ D ^ ^ E ^ F ^ ^ G ^ 图4.35 三叉链表示意图 §4.4.3 树、森林与二叉树之间的转换 在以下的几种变换过程中，逆变换也是存在的。在这里只讨论变换方法，不作唯一性证明。 §4.4.3.1 树转换为二叉树 对于一般的树而言，结点的次序不作要求，但为了表示为二叉树，则需要对树中每个结点的孩子结点进行从左到右的排列，称最左边的孩子结点为第一个孩子结点。如图4.36所示。B为A的第一个孩子结点，F为C的第一个孩子结点。将树转换为二叉树的方法是： （1） 在兄弟结点间添加一连线。 （2） 对于每个结点来说，除了第一个孩子结点外，去掉其与其它孩子结点的连线。 （3） 以树根为轴心，将整个树顺时针转45度。旋转之后保留的连线为左孩子连线， 添加的连线为右孩子连线，即原来每个结点的兄弟结点将变为其右孩子结点。 将图4.36的树转换为二叉树的过程用图4.37所示。 A A A B C D B C D B E C E F G H E F G H F D 图4.36 树的结构 （a）旋转前 （b）旋转后 G H 图4.37 由树转换的二叉树 由上述转换过程可知，任何一棵树转换的二叉树其右子树均为空。 实际上，将树转换为二叉树后，在二叉树中，每个结点的左孩子结点为其在树中的第一孩子结点，右孩子结点为其在树中的兄弟结点。 §4.4.3.2森林转换为二叉树 将森林转换为二叉树的方法是： （1） 在每棵树的根结点之间加一连线。 （2） 将森林中的每棵树按上述方法各自转换为一棵二叉树（暂不旋转）。 （3） 以第一棵树根为轴心，将整个树顺时针转45度。 图4.38为上述转换过程的示意图。 由于转换过程的逆过程存在，所以由上述的转换过程可知森林、树和二叉树之间可以互相转换。前面讲过，对于树的链式存储，若采用同结点结构，则浪费了存储空间，若采用异结点结构，又带来了操作的困难，有了上述的转换过程，树的基本操作便可用二叉树的基本操作来实现。 A B A C D A C D C E B B F G H F F G H D G E E H (a) 有3棵树的森林 （b）旋转前 （c）旋转后 图4.38 森林转换的二叉树 §4.4.4 二叉树的遍历 遍历（traversing）是指循某条搜索路线寻访某数据结构中的某个结点，而且每个结点访问且仅访问一次。线性表的遍历很容易实现，只须顺序扫描表中每个结点即可，但由于二叉树是非线形结构，每个结点有两棵子树，因此需要人为设置搜索路径。 二叉树的基本组成如图4.39为： 根 左子树 右子树 图4.39二叉树构成 若能依次访问这三部分，便是访问了整个二叉树。若以D、L、R分别表示访问根结点、遍历左子树、遍历右子树，则二叉树的遍历有以下6种： DLR DRL LDR LRD RDL RLD 在实际操作中我们可规定先左后右，则遍历只有以下3中：DLR、LDR、LRD。按照根的访问次序，将三种遍历分别称为先序遍历、中序遍历和后序遍历。下面分别讨论。 先序遍历二叉树的定义为： 若二叉树空，则空操作；否则 A B E F G H 图4.40 二叉树示意图 C D （1） 访问根结点 （2） 先序遍历左子树 （3） 先序遍历右子树 中序遍历二叉树的定义为： 若二叉树空，则空操作；否则 （1） 中序遍历左子树 （2） 访问根结点 （3） 中序遍历右子树 后序遍历二叉树的定义为： 若二叉树空，则空操作；否则 （1） 后序遍历左子树 （2） 后序遍历右子树 （3） 访问根结点 设有如图4.40所示的二叉树 先序遍历二叉树得到的序列的排列顺序为： <二叉树的根><左子树上所有结点><左子树上所有结点> 因为左、右子树分别为二叉树，分别对其按照先序遍历方法进行遍历可得<左子树上所有结点>和<左子树上所有结点>。同理可得二叉树的中序遍历序列和后序遍历序列。 按照上述三种遍历方法得出的三种遍历序列分别为： 先序序列：ABECFGHD 中序序列：EBAFHGCD 后序序列：EBHGFDCA 下面重点以中序遍历二叉树为例讨论遍历算法。 遍历算法的实现除了要依据上述思路外，还须依据二叉树的存储结构以及所使用的语言。二叉树的存储结构采用二叉链表，二叉链表的C语言描述如下： typedef struct btnode {elemtype data; struct btnode *lchild,*rchild; }BTNODE; 根据中序遍历的定义，中序遍历的递归算法可表示如下： void inorder(BTNODE *t) /* t为二叉树的根结点 */ { if （t!=NULL） { inorder(t->lchild); /* 中序遍历左子树 */ printf(“%根结点的格式符\\n”,t->data); inorder(t->rchild); /* 中序遍历右子树 */ } } 先序和后序遍历的算法类似，在此不一一列举。 利用栈，可以写出二叉树中序遍历的非递归算法。 设s是采用顺序存储结构存储的栈（参考栈一节的定义），则二叉树中序遍历的非递归算法下： void inorder(BTNODE *t) { BTNODE *p; STACK s; s.top= -1; /* 初始化栈为空 */ p=t; while((p!=NULL)||(top!=-1)) { while(p!=NULL) { push(s,p->data); p=p->lchild; } if (top!= -1) { p=pop(s); printf(“%根结点的格式符\\n”,p->data); p=p->rchild; } } } 同理，只要改变对结点的访问位置，就可以很容易的写出二叉树先序遍历的非递归算法。二叉树后序遍历的非递归算法较复杂，有兴趣的话可参考其他的书。 §4.4.5 二叉树的应用 §4.4.5.1哈夫曼树 1． 哈夫曼树 哈夫曼树又称最优树。是一类带权路径最短的树。有着广泛的应用。 下面先介绍几个概念。 路径 从树中一个结点到另一个结点之间的分支就构成这两个结点之间的路径。 路径长度 路径上的分支数目称路径长度。 树的路径长度 从树的根到每一个结点的路径长度之和称树的路径长度。 结点的带权路径长度 该结点到树根之间的路径长度与该结点上权值的乘积。 树的带权路径长度 树中叶子结点的带权路径长度之和。 通常将树的带权路径长度记作： WPL= wli1nii 其中wi 为第i个叶子结点的权值，li 为第i个叶子结点的路径长度。 哈夫曼树（Huffman）又称最优树。它是n个带权叶子结点构成的所有二叉树中，带权路径长度最小的二叉树。因为构造这种树的算法最早是由哈夫曼于1952年提出的，所以称为哈夫曼树。 设以下的三棵二叉树都有5个叶子结点，权值分别为：3、5、9、10、12，如图4.41所示：它们的带权路径长度分别为： (a) WPL=3*3+5*3+9*3+10*3+12*1=93 (b) WPL=3*2+5*3+9*4+10*4+12*1=109 (c) WPL=12*2+10*2+9*2+5*3+3*3=86 其中以(c)为最小，下面我们可以证明，它就是哈夫曼树，即带权路径长度最小的树。 12 12 3 12 10 9 5 9 10 5 3 5 3 10 9 (a) (b) 图4.41具有不同WPL的 二叉树 (c) 构造哈夫曼树的方法是： （1） 根据给定的n个权值（w1,w2,„,wn）构造n棵二叉树的集合 F={T1,T2, „,Tn}，其中每棵二叉树Ti中只有带权为wi的根结点，其左右子树为空。 （2） 在森林F中选取两棵根结点的权值最小的二叉树作为左右子树构造一棵新 的二叉树，新二叉树根结点的权值为其左右子树上根结点的权值之和。 （3） 在森林F中删除这两棵树，同时将新构成的二叉树加入其中。 （4） 重复（2）和（3），直到森林中只剩一棵树为止。 图4.42是5个权值（3，5，9，10，12）的哈夫曼树的构造过程。 8 9 10 12 3 5 3 5 9 10 12 （a） （b） 39 17 8 3 5 9 3 10 12 8 5 17 9 22 10 12 3 8 5 17 9 22 10 12 （c） （d） 图4.42 哈夫曼树的构造过程 （e） 实际操作中，哈夫曼树的应用很广，最佳判定树就是其中的一种。例如要编制一个将百分制成绩改为五分制的程序，如果认为成绩分布是均匀的，则可用图4.43(a)中的二叉树结构来实现。将这种结构称为判定树。但实际情况是学生成绩在各分数段的分布不均匀，设其关系如下表所示。 五分制 不及格 及格 中 良 优 分数段 0----59 60----69 70----79 80----89 90----100 比例 0.10 0.15 0.40 0.30 0.05 为了能使大部分数据通过较少的比较就可得出结果，可以以一组成绩比例作为权值构造哈夫曼树，如图4.43(b)所示的二叉判定树；将每一框中两次比较改为一次，得到图4.43(c) 所示的二叉判定树，依此二叉判定树较容易编制出程序。设现有1000个学生成绩需要运算，按图4.43(a)进行判断，则需要3000次比较，按图4.43(c))进行判断，则仅需要2250次比较。依据图4.43(c)编制的程序的效率比图4.43(a)编的程序的效率高。 实际上以权值（0.05,0.10,0.15,0.30,0.4）为叶子构造的哈夫曼树就是图4.43(b)所示的二叉判定树。 70≤g<80 Y g<60 N Y N 不及格中 80≤g<90 Y g<70 N Y N 0.10 及格 良 g<80 60≤g<70 0.15 Y N Y N 中 及格 g<90 0.40 Y N g<60 Y N 良 优 0.30 不及格 0.05 优 （a） （b） g≥80 Y N g≥70 g<90 Y Y N N 中 g≥60 良 0.40 Y N 优 0.30 0.05 及格 0.15 不及格 0.10 (c) 图4.43 判定树示意图 §4.4.4.2二叉排序树 二叉排序树是一种特殊结构的二叉树，它或者是一棵空树，或者是具有下面特性的二叉树： 20 （1） 若它的左子树非空，则左子树上所有结点的值（或关键字）均小于根结点的值（或关键字）； 15 50 （2） 若它的右子树非空，则右子树上所有结点 的值（或关键字）均大于或等于根结点的值（或关键10 17 30 60 字）； （3） 左、右子树各是一棵二叉排序树。 13 53 若按照中序序列遍历二叉排序树，则可以得到一个由 图4.44 二叉排序树示意图 小到大的有序序列。图4.44是一棵二叉排序树，中序遍历 的序列是：（10，13，15，17，20，30，50，53，60） 为使一个任意序列变成一个有序序列，可以通过将这些序列构成一棵二叉排序树来实现。下面介绍二叉排序树的生成方法。 由给定的数据序列生成二叉排序树的过程是在二叉排序树上插入结点的过程，对一数据序列（R1，R2，„，Rn）： （1） 设R1为二叉排序树的根。 （2） 若R2 图4.45为序列（20，50，30，15，17，10，13）构造二叉排序树的过程。 20 20 20 20 20 50 15 50 15 50 50 30 20 20 30 15 50 17 30 15 10 50 10 17 30 17 30 13 图4.45 二叉排序树构造过程示意图 下面是二叉排序树的生成算法描述。 设每次申请结点都是成功的。 #define N 100 /* N为 二叉排序树的最大结点个数*/ elemtype A[N]; BTNODE *creat() { int i; BTNODE *t, *new; /* t为根结点，new为待插结点*/ BTNODE *p,*q; /* p 为待插位置的前驱结点指针，q为待插位置的结点指针*/ t=( BTNODE *)malloc(sizeof(BTNODE )); t->data=a[0]; t->lchild=NULL; t->rchild=NULL; /* 构造根结点 */ for(i=1;i new->lchild=NULL; new->rchild=NULL; /* 构造结点 */ p=t; while(p!=NULL) /* 寻找插入位置 */ {q=p; if ( (new->data)< (p->data)) p=p->lchild; else p=p->rchild; } if ((new->data)< (q->data)) /* 插入结点 */ q->lchild=new; else q->rchild=new; } } §4.5 图 §4.5.1图的定义及存储结构 §4.5.1.1图的定义 图形结构（简称图）是一种比树更复杂的非线性数据结构，在树型结构中，元素之间存在着明显的分支和层次关系，每个结点都和双亲有联系，又和下层的孩子结点有联系，但同一层的结点之间没联系。在图形结构中，任意两个元素之间都可能有联系。 图的应用也非常广泛，如交通管制问题、工程进度安排等都可归纳为图的问题。 图的二元组表示为： G= ( V , E ) V={vi| 1≤i≤n,n≥1 vi∈elemtype } E={r|r= 图中的数据元素通常称为顶点。其中，V为非空的顶点集合，E为顶点之间关系的集合。若 E F E F （a） 无向图G1 （b）有向图G2 图4.46 图的示意图 下面介绍图的一些常用的术语。 邻接点 在一个无向图中，若存在一条边（vi,vj）,则称vi和vj互为邻接点，边（vi,vj）依附于顶点vi和vj，或者说边（vi,vj）与顶点vi和vj相关联。对于有向图，若存在弧 顶点的度 在无向图中，顶点的度是以该顶点为端点的边的数目。对于有向图，以某顶点为弧头的弧的数目为该顶点的入度；以某顶点为弧尾的弧的数目为该顶点的出度；该顶点的度为出度和入度的和。 有向完全图 若一个有向图有n个顶点，任意两个顶点之间都有一条弧存在，即弧的数目为n(n-1),这种图称为有向完全图。 无向完全图 若一个无向图有n个顶点，任意两个顶点之间都有一条边存在，即边的数目为n(n-1)/2,这种图称为无向完全图。 路径 图中一个顶点v到另一个顶点u之间的路径是一个顶点序列(v,v1,v2,„,vi,u)，并且若此图是有向图，则 简单路径 若一条路径上除开始点和终止点可以相同外，其余顶点都不相同的路径称简单路径。 回路 若一条路径上开始点和终止点相同则称此路径为回路。 路径长度 路径上经过的边或弧的数目叫路径长度。 连通图 若无向图中每一对顶点之间都有路径，则称此图为连通图。 强连通图 若有向图中每一对顶点v和u之间都存在从v到u和从u到v之间的路径，则称此图为强连通图。 网 在一个图中，每条边可以标上具有某种含义的数据，称为权，边上带有权的图称为网。 §4.5.1.2图的基本操作 图通常进行的操作有以下几种： ① 取顶点：取图中的某一顶点。 ② 求邻接点：求图中某一顶点的所有邻接点。 ③ 插入顶点：在图中插入一顶点。 ④ 删除顶点：删除图中某一顶点。 ⑤ 插入边或弧：在图中插入一条边或弧。 ⑥ 删除边或弧：删除图中一条边或弧。 ⑦ 求顶点的度：求图中某一顶点的度（对于有向图，求出入度和出度的和）。 ⑧ 遍历：指从图中某一顶点出发访问图中其余顶点，使每个顶点都被访问且仅访问一次。 §4.5.1.3图的存储 图的存储结构表示有多种，如邻接矩阵、邻接表、十字链表、边集数组等。下面重点介绍邻接矩阵和邻接表。 1． 邻接矩阵 从图的定义可知，图的定义分两部分，一部分为顶点的集合，一部分为顶点关系的集合，在存储时用一维数组存储图的顶点信息（若顶点只有编号而无其它信息，则存储图时不需此数组），用二维数组存储顶点关系的信息，此二维数组叫邻接矩阵。 邻接矩阵是表示顶点之间相邻关系的矩阵。若图有n个顶点，则邻接矩阵是一个n*n阶的方阵。邻接矩阵A的元素规定为： 1 对无向图，（Vi,Vj）或（Vj,Vi）存在 Aij= 对有向图， 对于图4.46中的G1和G2，其邻接矩阵表示分别为图4.47（a）和图4.47(b)。 A B C D E F 0 1 0 1 0 0 A 1 0 1 0 1 0 B A1 = 0 1 0 0 0 1 C 1 0 0 0 0 0 D 0 1 0 0 0 1 E 0 0 1 0 1 0 F (a) A B C D E F 0 1 0 1 0 0 A 0 0 1 0 1 0 B A2 = 0 0 0 0 0 0 C 0 0 0 0 0 0 D 0 0 0 0 0 1 E 0 0 1 0 0 0 F (b) 图4.47 图的邻接矩阵 用邻接矩阵存储网时只需要将矩阵中的1换为相应的权值，将0用一个不可能存在的权值代替即可。图4.48 中网的邻接矩阵表示为图4.49。 ∞ 15 ∞ 17 ∞ ∞ 1 15 17 15 ∞ 6 ∞ 8 ∞ A1 = ∞ 6 ∞ ∞ ∞ 12 2 6 3 4 8 12 17 ∞ ∞ ∞ ∞ ∞ 20 ∞ 8 ∞ ∞ ∞ 20 6 5 ∞ ∞ 12 ∞ 20 ∞ 图4.48 网的示意图 图4.49网的邻接矩阵 当图用邻接矩阵表示后图的某些操作的实现是很方便的，如求某一顶点vi的第一邻接点，只需在第i行找到第1个非零元即可。时间复杂度为O(n)。若求某一顶点vi的度，对于无向图来说，只须统计第i行的非零元个数或第i列的非零元个数（无向图的邻接矩阵是对称的）；对于有向图来说，第i行的非零元个数为该顶点的出度，第i列的非零元个数为该顶点的入度，两者相加为该顶点的度。时间复杂度为O(n)。当图中顶点数确定，插入一条边（vi,vj）只须将矩阵中第i行j列和第j行i列的元素分别改为1或相应的权值；插入一条弧 这种存储方式适用于图中边或弧的数目比较多的情况。当边的数目较少时数组应采用前面介绍的压缩存储方式，也可以用下面介绍的邻接表来存储图。 2． 邻接表 邻接表是图的一种链式存储结构，在邻接表中对图的每个顶点建立一个单链表，第i个单链表中包含第i个顶点的所有邻接点，每一个单链表包含两种结点，头结点和表结点。下面以第i个结点为例进行说明。头结点包含两个域，其中一个存储与顶点vi相关的信息，另一个存储指向vi的第一个邻接点的指针。表结点包含三个域，一是邻接点域，用来存储顶点vi的一个邻接点vj的序号j；二是权域，用于存储边（vi,vj）或弧 链域，用于链接与vi邻接的下一个结点。对于无向图来说，第i个单链表中的表结点数目等于以vi为顶点的边的数目，或者等于顶点vi的度。对于有向图来说，第i个单链表中的表结点数目等于以vi为弧尾的弧的数目，或者等于顶点vi的出度。 表结点和头结点的C语言定义如下： #define N 100 /* 设图中顶点数为N */ struct arcnode {int adjvex; /* 邻接点的序号*/ float info; /* 权值 ，若无权值，则可省去该项 */ struct arcnode *next; } struct headnode {elemtype data; /*顶点信息*/ struct arcnode *firarc; } typedef struct arcnode ANODE; typedef struct headnode ADJLIST; 图4.46中的G1和G2，其邻接表表示分别为图4.50和图4.51所示。 0 A 1 B 2 C 3 D 4 E 5 F 1 0 1 0 ^ 1 2 5 ^ 4 ^ 3 ^ 2 5 ^ 4 ^ 0 A 1 3 ^ 1 B 2 4 ^ 2 C ^ 3 D ^ 4 E 5 ^ 5 F 2 ^ 图4.50 G1的邻接表 图4.51 G2的邻接表 若无向图中有n个顶点e条边，则邻接表需要n个头结点和2e个表结点。在边稀疏的情况下，采用邻接表比采用邻接矩阵节省存储空间。 在无向图的邻接表中，顶点vi的度恰好为第i个链表中的表结点数。 若有向图中有n个顶点e条弧，则邻接表需要n个头结点和e个表结点。在有向图的邻接表中，第i个链表中的结点数为顶点vi的出度。为求顶点vi的入度，需要遍历整个邻接表，在所有链表中其邻接点域的值为i的结点个数为顶点vi的入度。有时为了便于求顶点vi的入度，可以建立一个有向图的逆邻接表，即对每个顶点建立一个链接以vi为头的弧的表。 在邻接表中，容易找到任意一顶点的第一邻接点和下一个邻接点，但要判断任意两个顶点vi和vj之间是否有边相连，则须搜索第i或j个链表，因此，不及邻接矩阵方便。 §4.5.2图的遍历 图的遍历是指从图中某一顶点出发访问图中其余顶点，使每个顶点都被访问且仅访问一次。因为图的任一顶点都可能和其余的顶点相邻接，且可能有回路，稍不注意，就会出现对某顶点的重复访问。为避免这个问题，在图的遍历过程中，记下每个已访问过的结点。为此设一个表示顶点是否访问过的辅助数组visited[N],初始各分量置0，一旦访问则将其改为1，以后对其不再访问。遍历图的方法一般分为两种：深度优先遍历和广度优先遍历。 §4.5.2.1 深度优先遍历 深度优先遍历图的基本思路是： （1） 访问图中的指定起始点v0； （2） 从v0出发，访问一个与v0邻接的顶点w1后，再从w1出发，访问与w1邻接的且未 访问的顶点w2。然后从w2出发，重复上述过程，直到找不到未被访问的顶点为止。 （3） 回退到尚有未被访问过的邻接点的顶点，从该顶点出发，重复上面的步骤，直 到所有被访问过的顶点的邻接点都已访问为止。 图4.46中的G1以邻接表表示为图4.50，从此图中的顶点A（序号为0）出发，深度优先遍历图得出的序列为：012543或ABCFED，从此图中的顶点E出发，深度优先遍历图得出的序列为：EBADCF。从顶点A出发的遍历过程如图4.52所示。 搜索过程 访问顶点 搜索成功走过的边 1）从A出发 A 2）找A的第一个邻接点B B （A，B） 3）从B出发，第一邻接点已被访问，第二邻接点C未被访问 C （B，C） 4）从C出发，第一邻接点已被访问，第二邻接点F未被访问 F （C，F） 5）从F出发，第一邻接点已被访问，第二邻接点E未被访问 E （F，E） 6）从E出发所有邻接点都已访问，回退到顶点F，继续找未被 访问的下一邻接点，因其邻接点均已访问，继续回退到顶点C， 因其邻接点均已访问，继续回退到顶点B，找出未被访问的顶点D （B，D） D。 7）从D出发，所有邻接点都已访问。回退到顶点B，因其邻接 点均已访问，再回退到顶点A，A的邻接点都已访问，遍历结束。 图4.52 深度优先遍历图的过程 将一个连通图深度遍历过程中搜索成功所走过的边和顶点相连，则得到以遍历起始点为根的树，称这棵树为深度优先生成树，如图4.53所示。 A B C D F E 图4.53图G1的深度优先生成树 深度优先遍历在实现过程中，需要设置一个栈，栈中记录刚刚访问过的顶点的序号，找出栈顶元素的第一个未曾访问的邻接点进栈，一旦某一顶点的邻接点均已访问，则将其从栈顶弹出，直到栈空。 以邻接表作为存储结构，深度优先遍历算法如下： #define N 100 /* 图的顶点数 */ void traver_dfs(ADJLIST g[N],int v) { int visited[N], i; STACK s; ANODE *p; for(i=0;i p=g[v].firarc; /* p 为v的第一邻接结点 */ while((p!=NULL)||(top!=-1)) { while(p!=NULL) if (visited[p->adjvex]) p=p->next; else { printf(“%d\\n”,p->adjvex); visited[p->adjvex]=1; push(s,p->adjvex); p=g[p->adjvex].firarc; } if (top!= -1) { v=pop(s); p=g[v]->firarc; p=p->next; } } } §4.5.2.2 广度优先遍历 */ 广度优先遍历是图的另一种遍历方法。其实现思路是： （1） 访问图中的指定起始点v0； （2） 从v0出发，依次访问v0的未被访问的邻接点w1,w2,w3,„,wn。然后依次访问 w1,w2,w3,„,wn的未被访问的邻接点。 （3） 重复上面的第二步，直到所有顶点的邻接点都已访问为止。 图4.46中的G1以邻接表表示为图4.50，从此图中的顶点A（序号为0）出发，广度优先遍历图得出的序列为：013245或ABDCEF，从此图中的顶点E出发，广度优先遍历图得出的序列为：EBFACD。从顶点A出发的遍历过程如图4.54所示。 搜索过程 访问顶点 搜索成功走过的边 1）从A出发 A 2）访问A的所有未被访问的邻接点B，D B，D （A，B） （A，D） 3）从B出发，访问B的所有未被访问的邻接点C，E C，E （B，C） （B，E） 4）从D出发，访问D的所有未被访问的邻接点 无 5）从C出发，访问C的所有未被访问的邻接点F F （C，F） 6）从E出发，访问E的所有未被访问的邻接点 无 7）从F出发，访问F的所有未被访问的邻接点 无 图4.54广度优先遍历图的过程 将一个连通图广度遍历过程中搜索成功所走过的边和顶点相连，则得到以遍历起始点为根的树，称这棵树为广度优先生成树，如图4.55所示。 A B D C E F 图4.55图G1的广度优先生成树 广度优先遍历在实现过程中，需要设置一个队列，队列中记录刚刚访问过的顶点的序号，取出队头元素，将队头元素的所有未曾访问的邻接点进队，重复取队头元素和进队的操作，，直到队空。 以邻接表作为存储结构，广度优先遍历算法如下： #define N 100 /* 图的顶点数 */ void traver_bfs(ADJLIST g[N],int v) { int visited[N], i; QUEUE Q; ANODE *p; for(i=0;i while(Q.rear!=Q.front)) /* 队列未空时 */ { v=delqueue(Q); p=g[v].firarc; while(p!=NULL) { if (!visited[p->adjvex]) { printf(“%d\\n”,p->adjvex); visited[p->adjvex]=1; addqueue(Q,p->adjvex); } p=p->next; } } } §4.6 查找 查找也称为检索，是从大量的数据中找出所需要的数据。查找与人们的日常生活有着密切的关系，如查字典、查电话号码、查阅图书等。查找的方法可以人工进行，也可以用计算机查找。用计算机查找首先要将原始数据整理成线性表，并按照一定的存储结构存储到计算机中去，然后编制算法进行查找。 由此可见，查找是在一个含有众多数据元素的查找表中找出某个特定的数据元素。为了便于讨论，引入“关键字”的概念。关键字是数据元素中某个数据项的值，用它可以标识一个数据元素。若此关键字可以唯一标识一个数据元素，则称此关键字为主关键字，反之称此关键字为次关键字。 查找是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素，若表中存在这样的数据元素，称此查找是成功的；若表中不存在关键字等于给定值的数据元素，称此查找是不成功的。 作为查找对象的表所具有的存储结构不同，其查找方法一般也不同，但无论哪一种方法，其查找过程都是用给定值与关键字按照一定的次序进行比较的过程，比较次数的多少就是相应算法的时间复杂度，它是衡量一个查找算法优劣的重要指标。对于一个查找算法的时间复杂度，既可以采用数量级的形式来表示，也可以采用平均查找长度（Average Search Length，简称ASL）来表示。平均查找长度是在查找成功的情况下的平均比较次数。平均查找长度 的计算公式为： ASL= pci1nii 其中，n为查找表的长度，即表中所含元素的个数，pi为查找第i个元素的概率，若不特别声明，则认为是等概率查找；ci为查找第i个元素所需要的比较次数。 前面曾说过，存储结构不同，其查找方法一般也不同，本节将讨论几种查找方法。 §4.6.1 静态查找 静态查找是在如下的表中进行查找，表中的数据元素类型相同，关键字类型相同，并且关键字可唯一标识数据元素。可用如下的方式定义表： #define N 10000 /* 表中元素的最大可能值 */ struct list {int key; /*为讨论方便，设关键字类型为整型量 */ othertype info; /* 除关键字之外的其它数据项 */ } typedef struct list LIST LIST L[N]; §4.6.1.1 顺序查找 顺序查找是最常用的查找方法，其查找过程为：从第一个元素起，逐个将给定值与数据元素的关键字进行比较，若某个元素的关键字与给定值相等，则认为查找是成功的，否则，查找失败。 顺序查找方法既适合于表以顺序结构存储又适合于表以链式结构存储。在第二章曾介绍过顺序查找算法。 下面讨论改进以后的顺序查找方法。 在改进以后的算法中，为了查找方便，数据元素存储在表中的A[0]……A[N-1]中，待查关键字存储在A[N].key中，表中要多定义一个数据元素。 int Searchlist(LIST A[N+1],int x) { i=0; A[N].key=x; while(A[i].key!=x) i++; if (i= =N) {printf(“not found\\n”); return –1;} else return i; } 此算法中while循环的条件由两个减少为一个，时间复杂度主要取决于while循环，while循环的比较次数不是固定的，与输入的数据有关，当a[0]与x相等时只要进行一次比 较，则T(n)=O(1)，这是最好的情况；当最后一个元素a[n-1]等于x时，需要比较n次才能成功，则T(n)=O(n)，这是最坏的情况；当查找的数据元素是A[i]时需要比较i+1次，考虑到每个元素都有相同的查找概率时，则所需要的平均比较次数为： n11n1PEss =(i1)= 2ni0此时时间复杂度也为O(n)。当数组中没有待查元素x时，则表明查找失败，需要比较n+1 次，即时间复杂度也为O(n)。 §4.6.1.2 折半查找 作为折半查找的表必须是顺序存储的有序表，即表采用顺序结构存储，表中的元素按关键字值递增（或递减）排列。 假设表中的关键字值递增排列，则折半查找的实现方法是：首先取整个有序表A[0]„A[N-1]的中间元素A[mid]（其中mid=(N-1)/2）的关键字同给定值x比较，若相等，则查找成功；否则，若A[mid].key 折半查找的非递归算法为： int binsearch(LIST A[N],int x) {int low=0,high=N-1,mid; while(low<=high) {mid=(low+high)/2; if(x= =a[mid].key) return mid; else if(x< a[mid].key) high=mid-1; else low=mid+1; } return –1; } 例如，有10个元素的有序表，其关键字分别为： 13， 33，36，58，70，75，88，90，96，102 现分别查找58和95 ，其查找过程如图4.56所示，图中括号“[”代表下限low的 位置，中括号“]”代表上限high的位置。 [ 13 33 36 58 70 75 88 90 96 102 ] mid=4 mid=1 13 33 [36 58 ] 70 75 88 90 96 102 mid=2 13 33 36 [ 58 ] 70 75 88 90 96 102 mid=3 (a) 查找58的过程 (4次比较成功) [ 13 33 36 58 70 75 88 90 96 102 ] mid=4 13 33 36 58 70 [ 75 88 90 96 102 ] mid=7 [ 13 33 36 58 ] 70 75 88 90 96 102 折半查找的查找过程可用一棵二 70 叉树来描述，树的根结点为表的中间元素，即只须一次比较就成功的元素，33 90 左右子树分别对应表中除中间元素之 外的前半部分和后半部分，称此二叉12 36 75 96 树为折半查找的判定树。图4.57为描 失败 102 述上述查找过程的判定树。从此图可58 88 以看出，在有序表中折半查找一个关 图4.47 折半查找的判定树 键字的过程，对应着判定树中从根结 点到待查结点的一条路径，同关键字 的比较次数等于路径上的结点数，或者等于待查结点所在的层数。图4.57中根结点的左右子树中的虚线分别代表查找58成功和查找95失败的过程。 折半查找的判定树不仅是一棵有序树，也是一棵与完全二叉树类似的树，即叶子结点分布在最低的两层，所以判定树的高度h和结点数n之间的关系为： h=log2(n1) 树的高度为折半查找成功时的最多比较次数，所以折半查找的时间复杂度为O(log2n)，显然它比顺序查找的速度要快的多。 在等概率情况下，有10个元素的表的平均查找长度 ASL= pci1nii =(1+2*2+4*3+3*4)/10=2.9 折半查找的优点是查找速度快，缺点是，查找前要先对表进行排序，并且表只能采用顺序结构存储，所以它适用于数据相对固定且主要的操作为查找的表。 §4.6.1.3 分块查找 分块查找又称为索引顺序查找，用这种方法查找的表具有如下特点： 若将表中n个数据元素分成m块，第一块中所有数据元素的关键字均小于（或大于）第二块中所有数据元素的关键字，第二块中所有数据元素的关键字均小于（或大于）第三块中所有数据元素的关键字„，第m-1块中所有数据元素的关键字均小于（或大于）第m块中所有数据元素的关键字；每一块中的数据元素的关键字不一定有序。例如有一组关键字为： （15，8，18，4，27，25，38，30，52，47，48，43，79，85，65，66），将这一组数据元素划分为4块，每一块中有4个元素，则此表分块有序，如下： [15，8，18，4]，[27，25，38，30]，[52，47，48，43]，[79，85，65，66] 在此表中进行查找尚需建立索引表，索引表的元素个数为表所分的块数，每一元素有两项内容：关键字项（值为表中每一块元素的最大关键字）和指针项（指示该子表的第一个记录在表中的位置）。可见索引表按关键字有序，这种表的组织方式如下图4.58所示。 27，25，38，30 52，47，48，43 79，85，65，66 15，8，18，4 指针项 1 5 8 13 关键字项 18 38 52 85 图4.58 分块查找示意图 在这种表中查找关键字为k的数据元素的过程为：首先在索引表中查找待查元素所在的块，查找方法用顺序查找或折半查找均可；其次在块中进行顺序查找。 分块查找的平均查找长度为： ASL=ASLB+ASLS=索引表的平均查找长度+块中的平均查找长度 其中ASLB为折半查找的平均查找长度，ASLS为顺序查找的平均查找长度，设每块有s个元素，则可以得到： ASL=log2(n/s+1)+s/2 所以分块查找的平均查找长度介于折半查找和顺序查找之间。 下面对上述三种查找方法进行比较 平均查找长度 表的结构 存储结构 顺序查找 最大 有序表、无序表均可 折半查找 最小 有序表 分块查找 次之 表中元素分块有序 表的结构采用顺序存储、链式存储均可，索引表采用顺序存储查找效率更高 顺序存储、链式存储均可 顺序存储 §4.6.2 动态查找 从上面介绍的三种常用的查找方法可以看到，折半查找的速度最快，但是因为折半查找采用的存储结构是顺序存储，当要在表中插入或删除元素时，需移动大量的元素，这就会增加新的时间开销。当表中需要经常进行插入和删除时，这会降低折半查找效率。若想提高折半查找的效率，插入和删除时又不需移动大量的元素，那么，采用二叉排序树作为查找表的存储结构，就可弥补上述的不足。 根据二叉排序树的定义（参考§4.4.5.2），在二叉排序树中进行查找的思路为： 若二叉排序树不空，将给定的关键字k与二叉排序树根结点的关键字进行比较，若相等则查找成功，否则，若k小20 于根结点的关键字，则k与左子树根结点的关键字进行比 15 50 较，若k大于根结点的关键字，则k与右子树根结点的关键字进行比较，如此递归的进行下去，直到某一次比较相等， 17 30 10 60 则查找成功。若一直比较到树叶都不相等，则查找失败。 设有一组关键字（20，15，10，50，60，30，17，53， 13 53 13）构成的二叉排序树如图4.59所示。 若在此二叉排序树中查找值为17的结点，查找过程为：图4.59 二叉排序树示意图 17与根结点的值20比较，因17<20，故进入根结点的左子 树；17与左子树的根15比较，因17>15，故进入右子树；17与17比较，查找成功。 若在此二叉排序树中查找值为18的结点，查找过程为：18与根结点的值20比较，因18<20，故进入根结点的左子树；18与左子树的根15比较，因18>15，故进入右子树；18与17比较，因18>17，故进入结点17的右子树，但其右子树为空，所以查找失败。 若查找失败后需要将所查元素插入二叉排序树中，则只需要修改一次指针，而不需要移动元素。 从上述的查找过程可以看出，查找成功的过程是走了一条从根结点到所查结点的路径，所需的平均查找长度取决于二叉排序树的深度。 当二叉排序树中任一个结点的左右子树的深度之差的绝对值小于等于1时(此时的二叉排序树称为二叉平衡树)，可以证明，二叉排序树的平均查找长度与折半查找相同，即： ASL≈log2n 关于二叉平衡树的操作及构成方法，有兴趣的读者可参考有关图书。 因为二叉排序树是动态生成的，形态与元素的插入顺序有关，例如，与图4.59相同的一组关键字，其初始顺序为（10，13，15，17，20，30，50，53，60）则构成的二叉排序树如图4.60所示。此时的二叉排序树称为单支树。 10 13 15 17 20 30 50 53 60 图4.60 二叉排序树示意图 显然，在此二叉排序树中查找的平均查找长度与顺序查找相同。 上述图4.59和图4.60两棵树的平均查找长度分别为： ASL=（1+2+2+3+3+3+3+4+4）/9=25/9 ASL=（1+2+3+4+5+6+7+8+9）/9=45/9=5 §4.6.3 哈希查找 哈希查找又称散列查找。 前面介绍的查找方法都是通过比较确定待查元素的位置，哈希查找（hashing search）是一种完全不同的查找方法，它不是通过比较确定待查元素的位置，而是在元素的存储位置和它的关键字K之间建立一个对应关系H，使每个关键字K与结构中的一个位置相对应。因而在查找时，只要根据这个对应关系H找到关键字K的存储位置H(K)，若结构中存在关键字和K相等的记录，则必定在H(K) 这个存储位置上，因此不需要比较就可直接取得所查记录。称这个对应关系H为哈希函数，H(K)的值为哈希地址或散列地址，按这个思想建立的表为哈希表。 下面先举一个哈希表的最简单的例子。例如要建立一个1949年以后出生的人口调查表，此时关键字是年份，哈希函数取关键字减一常数，设常数为1949，则关键字K的存储位置为K-1949，所以哈希函数定义为： H（K）=K-1949 所建的哈希表为： 关键字项 1949 1950 1951 „ 2003 人数 „ „ „ „ „ 地址 0 1 2 „ 54 若要知道2000年出生的人口，则只须在表的第51（2000减去1949）分量中去取即可。 由此可见，哈希函数的设定要分析关键字，只要使得任何关键字由此所得的哈希函数值都能落在表长范围内即可。 但实际情况是，对不同的关键字可能根据哈希函数得到相同的地址值，即有：K1≠K2，而H（K1）=H（K2），这种现象称为冲突，具有相同函数值的不同关键字称为同义词。所以在构造哈希表时还应该为发生冲突的关键字另找存储空间。这一过程称为处理冲突的过程。所以下面要解决的主要问题为如何构造哈希函数和处理冲突。 §4.6.3.1 构造哈希函数的方法 构造哈希函数的目的是使散列地址尽可能均匀地分布在哈希表中，同时要尽可能的简单，以节省计算时间。下面介绍常用的几种方法。 1． 直接定址法 直接定址法是以关键字K本身或关键字加某常数C作为散列地址的方法。对应的哈希函数为： H（K）=K+C 2． 除留余数法 除留余数法是用关键字K除以哈希表长度m所得余数作为散列地址的方法。对应的哈希函数为： H（K）=k mod m /* mod为求余运算 */ 这种方法的关键是选好m，使得每一个关键字K通过该函数计算的地址尽量均匀地分布在哈希表中，从而减少冲突的发生。通常m取一个质数，并且要等于或大于哈希表的长度。 3． 数字分析法 数字分析法是取关键字中某些取值较分散的数字作为散列地址的方法。适用于所有关键字已知的情况。 4． 平方取中法 平方取中法是取关键字平方的中间几位数字作为散列地址的方法。具体取几位取决于哈希表的长度，一个数的平方与数本身的每一位都有关系，所以平方取中法得到的散列地址同关键字的每一位有关，这使得散列地址具有较好的分散性。 5． 折叠法 折叠法是将关键字分成位数相同的几段（最后一位可能不同），段的位数取决于散列地址的位数，然后将它们的叠加和（舍去最高位）作为散列地址的方法。 §4.6.3.2 处理冲突的方法 常用的处理冲突的方法有下面两种。 1． 开放定址法 设有一关键字为K，则哈希地址为D=H（K），若此时位置D的存储单元非空，则有冲突发生，此时将发生冲突的关键字K对应的数据元素在哈希表中存储位置定义为： D1=（D+di）mod m （i=1,2,3, „,k(k≤m-1) 其中di为增量序列，m为哈希表的长度。 根据di的不同取法，将开放定址法分为：线性探测再散列和二次探测再散列。 若di=1，2，3，„，m-1，称为线性探测再散列。 若di=12，-12，22，-22，32，„，-k(k< 2 m)，称为二次探测再散列。 2例如，散列表的存储空间为[0..10]，哈希函数为H(k)=k mod 11，采用线形探测法解决冲突，现给定关键字序列为{11，6，17，1，14，9，22，27，28}，请构造该散列表。 因为： 11 mod 11=0 则11存入第0分量中。 6 mod 11=6 则6存入第6分量中。 17 mod 11=6 发生冲突，下一地址为： （6+1）mod 11=7 则17存入第7分量中。 1 mod 11=1 则1存入第1分量中。 14 mod 11=3 则14存入第3分量中。 9 mod 11=9 则9存入第9分量中。 22 mod 11=0 发生冲突，下一地址为： （0+1）mod 11=1 又发生冲突，下一地址为： （0+2）mod 11=2 则22存入第2分量中。 27 mod 11=5 则27存入第5分量中。 28 mod 11=6 发生冲突，下一地址为： （6+1）mod 11=7 又发生冲突，下一地址为： （6+2）mod 11=8 则28存入第8分量中。 所得哈希表为： 下标 0 1 2 3 4 5 6 7 8 9 10 11 1 22 14 27 6 17 28 9 每个关键字所需的比较次数为（与上面的关键字对应） 1 1 3 1 1 1 2 3 1 注意，以此方式构造的哈希表在做删除时不能简单的直接删除，以免截断其他同义词的 查找路径，所以应设一个特殊的标志，表明该元素已删除。 2． 链地址法 链地址法处理冲突的方法是：将所有关键字为同义词的数据元素存储在同一链表中。 例如，设散列表的存储空间为[0..6]，哈希函数为H(k)=k mod 7，采用链地址法解决冲突，现给定关键字序列为{11，6，17，1，14，9，22，27，28}，请构造该散列表。 散列表的构造如图4.61所示： 0 1 2 3 4 5 6 6 27 null 14 1 9 null 17 null 11 null 28 null 22 null 图4.61链地址法解决冲突构造的散列表 §4.6.3.3哈希查找 在哈希表中进行查找叫哈希查找，哈希查找的过程同建立哈希表一样，给定关键字K，根据造表时给定的哈希函数求出哈希地址，若此地址中无数据元素，则查找不成功；否则，比较该数据元素的关键字与K的值是否相等，若相等，则查找成功，若不等，再根据造表时依据的处理冲突的方法确定“下一地址”，直到哈希表中某个数据元素的关键字等于K或某位置为空为止。 从哈希表的构造过程可见：虽然哈希表在关键字与数据元素的存储位置之间建立了直接关系，但由于“冲突”的产生，使得哈希表的查找过程仍是一个与关键字进行比较的过程， 因此仍需以平均查找长度作为查找效率的量度。查找过程中与关键字的比较次数取决于三个因素：哈希函数、处理冲突的方法、哈希表的装填因子。装填因子定义为： 装填因子= 表中填入的数据元素个数 哈希表的长度直观的看，装填因子越小，发生冲突的可能性越小，装填因子越大，表明表中填入的数据元素越多，发生冲突的可能性越大，则查找时与关键字的比较次数越多。 对于一组相同的关键字，采用不同的哈希函数和处理冲突的方法，其平均查找长度也不一样。如前面的两个例子中，若采用线形探测法解决冲突，则平均查找长度为： ASL= 114（6*1+1*2+2*3）= 99若采用链地址法解决冲突，则平均查找长度为： ASL= 14（6*1+3*2）= 93当然对于一组相同的关键字，采用相同的哈希函数和不同的处理冲突的方法，其平均查 找长度也不一样。 §4.7排序 排序是数据处理领域常用的运算。排序的目的之一是便于查找。 排序就是将一组数据元素按照某个关键字（或关键字的组合）的值的递增或递减的次序排列的过程。设待排序的一组数据元素为（R1，R2，„，Rn），其对应的关键字分别为（K1，K2，„，Kn），须确定一个新的排列p(1)，p(2)， „,p(n),使其相应的关键字满足如下的递增（或递减）关系： Kp(1) ≤Kp(2) ≤„≤Kp(n) 则上述数据元素表成为一个按其关键字线性有序的序列{ Rp(1) ,Rp(2) ,„Rp(n) },这样的运算过程称为排序。 对于一组数据元素来说，可能有多个相同的关键字，若采用的排序方法使得排序后具有相同关键字的数据元素的相对次序不变，则称此方法是稳定的，否则，是不稳定的。例如有一组关键字（43，23，56，12，23，30），其中关键字为23的数据元素有两个，为了区别，后边的加上下画线。现要按照递增的次序排列，若采用的排序方法使得排序后的序列为（12，23，23，30，43，56），则此排序方法可能是稳定的，若采用的排序方法使得排序后的序列为（12，23，23，30，43，56），则此排序方法是不稳定的。 下面介绍几种常用的排序方法，并假设排序时所有数据存放在内存中，称为内排序。若排序过程中需要对外存进行访问，则此种排序称为外排序。 为操作方便起见，数据元素的存储结构采用顺序结构，定义如下： #define N 10000 /* 表中元素的最大可能值 */ struct list {int key; /*为讨论方便，设关键字类型为整型量 */ othertype info; /* 除关键字之外的其它数据项 */ } typedef struct list LIST LIST L[N+1]; /* 其中，数据元素存储在L[1] „L[N]中*/ 不失一般性，所有的排序方法均按照关键字递增排列。 §4.7.1 选择排序 选择排序法的实现过程是：首先找出表中关键字最小的元素，将其与第一个元素进行交换，然后，再在其余元素中找出关键字最小的元素，将其与第二个元素进行交换。依次类推，直到将表中所有关键字按由小到大的顺序排列好为止。 设待排数据元素的关键字为（15，14，22，30，37，15，11），每一趟排序后的序列状态如图4.62所示： 初始状态：[15，14，22，30，37，15，11] 第一趟： [11] [14，22，30，37，15，15] 第二趟： [11，14] [22，30，37，15，15] 第三趟： [11，14，15] [30，37，22，15] 第四趟： [11，14，15，15] [37，22，30] 第五趟： [11，14，15，15，22] [37，30] 第六趟： [11，14，15，15，22，30] [37] 图4.62 选择排序法示意图 算法如下： void select_sort(LIST L[ ],n)/* 注意待排数据元素存储在L[1] „L[n]中*/ { int i,j,k; for(i=1;i 选择排序的时间复杂度为O（n2）,排序方法是不稳定的。 §4.7.2 插入排序 插入排序法是将表看成由已排好序和未排好序的两个部分组成。设表中元素存储在 L[1]，L[2]，„，L[n]中，则初始状态为：已排好序的部分为L[1]，未排好序的部分为L[2]，L[3]，„，L[n]；每一趟从未排好序的表中取出下标最小的元素，将其插入到已排好序的表中，直到未排好序的表中为空。 设待排数据元素的关键字为（15，14，22，30，37，15，11），每一趟插入排序后的序列状态如图4.63所示： 初始状态：[15] [14，22，30，37，15，11] 第一趟： [14，15] [22，30，37，15，11] 第二趟： [14，15，22] [30，37，15，11] 第三趟： [14，15，22，30] [37，15，11] 第四趟： [14，15，22，30，37] [15，11] 第五趟： [14，15，15，22，30，37] [11] 第六趟： [11，14，15，15，22，30，37] 图4.63 插入排序法示意图 算法如下： void insert_sort(LIST L[ ],n)/* 注意待排数据元素存储在L[1] „L[n]中*/ {int i,j; for(i=2;i<=n;i++) { L[0]=L[i]; j=i-1; while(L[0].key 直接插入排序的时间复杂度为O（n2）,排序方法是稳定的。 §4.7.3 冒泡排序 冒泡法排序是一种简单又常用的排序方法。这种方法是每趟将相临的两个元素的关键字俩俩进行比较，若不符合次序，则立即交换，这样关键字大（或小）的元素就象气泡一样逐步升起（后移）。 冒泡法排序的实现过程是从下标为1的元素开始，将相邻的两个数两两进行比较，若满足升序次序，则进行下一次比较，若不满足升序次序，则交换这两个数，直到最后。总的比较次数为n-1次。此时最后的元素为最大数，此为一趟排序。接着进行第二趟排序，方法同前，只是这次最后一个元素不再参与比较，比较次数为n-2次，依次„„。 设待排数据元素的关键字为（18，20，15，32，4，25），第一趟排序后的序列状态如图4.64所示： 18 20 15 32 4 25 18 20 15 32 4 25 18 15 20 32 4 25 18 15 20 32 4 25 18 15 20 4 32 25 18 15 20 4 25 32 最大数 图4.64 一趟排序的过程 算法如下： void bubble_sort(LIST L[ ],n)/* 注意待排数据元素存储在L[1] „L[n]中*/ {int i,j; for(i=1;i if(L[j].key>L[j+1].key) { L[0]=L[j];L[j]=L[j+1];L[j+1]=L[0];} } 实际上，冒泡排序法在实现过程中，当某一趟排序过程中没有元素的“交换”发生，则说明整体已排好序，所以冒泡排序法可改进如下： void bubble_sort(LIST L[ ],int n) { int i,j,CHANGE=1; i=1; while (i if(L[j].key>L[j+1].key) { L[j]↔L[j+1];CHANGE=1;} /*互换L[J]与L[J+1]*/ i++; } } 算法中“交换两个相邻的数”为基本操作。当L中的数据由小到大有序，基本操作的执行次数为0，当L中的数据由大到小有序（逆序）时，也是最坏情况，基本操作的执行次数为n(n-1)/2，则平均复杂度不会超过n(n-1)/2。即平均复杂度为O(n2)。 冒泡排序法为稳定的排序法。 §4.7.4 快速排序 快速排序是目前内部排序中速度较快的一种排序方法，也是冒泡排序的一种改进。它的基本思想是：首先在待排序区间中选取一个元素（通常是第一个元素，若不是，则和第一个元素进行交换）作为比较的基准元素，通过一趟排序将待排元素分割成独立的两部分，其中一部分元素的关键字均比另一部分元素的关键字小，基准元素位于两部分中间；依据同样的方法继续对两部分进行排序，直到整个序列有序。 下面先介绍一趟排序的实现过程。设待排元素存储在L[1] „L[n]中，用i和j分别表示待排区间的上下界，基准元素暂时存储在L[0]中，则首先从j所指位置起向前搜索找到第一个关键字小于基准元素关键字的数据元素，将其值存入i位置的元素中；然后从i所指位置起向后搜索找到第一个关键字大于基准元素关键字的数据元素，将其存入j位置的元素中；重复这两步，直到i等于j为止。 设待排数据元素的关键字为（15，14，22，30，37，15，11），第一趟排序后的序列状态如图4.65所示： 基准元素关键字=15 初始状态： 14 22 30 37 15 11 15 i=1 j =7 一次移动后 11 14 22 30 37 15 11 i=1 j =7 二次移动后 11 14 22 30 37 15 22 i=3 j =7 11 14 15 30 37 15 22 一趟排序后 i=3 j =3 图4.65 插入排序法示意图 一趟排序算法为： int part(LIST L[ ],int i,int j) { int i,j,KEY; L[0]=L[i];KEY=L[0].key; while(i L[i]=L[j]; while(i } 递归形式的快速排序方法为： void Qsort(LIST L[ ],int low,int high) /* low 和high为待排区间的上下界*/ {int m; if(low } 快速排序的平均时间复杂度为O（nlogn）。 当初始数据按关键字基本有序时，快速排序将退化为冒泡排序，时间复杂度为O(n2)。为改进之，通常依据“三者取中”的原则来选取基准元素，即选取L[i]、L[j]和L[(i+j)/2]中其关键字取中值的元素为基准元素，将其与L[i]交换，算法不变。 快速排序需要一个栈空间来实现递归，若每趟排序将数据元素均匀地分割为长度大致相等的两部分，则栈的最大深度≈log2n+1；最坏情况为n，此时基准元素总是在子序列的一端。 快速排序算法是不稳定的。 §4.7.5 归并排序 归并排序是将两个或两个以上的有序表合并为一个新的有序表。无论是顺序存储还是链式存储结构均可。 假设初始表含有n个数据元素，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到+1个长度为2或1 的有序子序列；再两两归并，„，如此重复， 2直到得到一个长度为n的有序表为止，这种方法称为2-路归并排序。 设待排数据元素的关键字为（15，14，22，30，37，15，11），2-路归并排序如图4.66所示： 初始状态： [15] [14] [22] [30] [37] [15] [11] 一趟归并后 [ 14 15 ] [ 22 30 ] [ 15 37 ] [ 11 ] 二趟归并后 [ 14 15 22 30 ] [ 11 15 37 ] 三趟归并后 [11 14 15 15 22 30 37 ] 图4.66 2-路归并排序法示意图 n 2-路归并排序的核心操作是将一维数组中前后两个相邻的有序表归并为一个有序表，一趟归并的算法为： void merge((LIST L[ ],int m,int n ,int k,LIST R[ ]) {int i,j,t; /* 将有序表L[m..n]和L[n+1..k]归并为有序的R[m..k]*/ for(i=m,j=n+1,t=m; i<=n&&j<=k; t++) if (L[i].key<=L[j].key) R[t]=L[i++]; else R[t]=L[j++]; if (i<=n)R[t..k]=L[i..n] else R[t..k]=L[j..k] } 2-路归并排序的递归算法为： void Msort(LIST L[ ], LIST R1[ ],int m,int n) {int t; /* 将L[m..n] 归并为R1[m..n]*/ if(m= =n)R1[m]=L[m]; else {t=(m+n)/2; Msort(L,R2,m,t); Msort(,L,R2,t+1,n); merge(R2,m,t,n,R1); } } 2-路归并排序的运行效率与快速排序是同样数量级，时间复杂度是O（nlog2n），但归并排序占用的内存较多，还需一个与原数组同样大小的辅助数组，这是算法的缺点。 归并排序是一种稳定的排序方法。 下面就几种排序方法进行比较： 排序方法 平均时间复杂度 最坏情况 空间复杂度 是否稳定 选择排序 O(n2) O(n2) O(1) 不稳定 插入排序 O(n2) O(n2) O(1) 稳定 冒泡排序 O(n2) O(n2) O(1) 稳定 快速排序 O(nlog2n) O(n2) O(1) 不稳定 归并排序 O(nlog2n) O(nlog2n) O(n) 稳定 习题 一．填空题 1． 进栈序列是1、2、3、4，进栈过程中可以出栈，则可能的出栈序列有 个，不可能的出栈序列是 。 2． 具有N个元素的顺序存储的循环队列中，假定front和rear分别指向队头元素的前 一位置和队尾元素的位置，则判断队空的和队满的条件分别是 和 。求此队列中元素个数的计算公式为： 。 3． 单链表是 的链式存储结构，链栈和链队分别是 和 的链式存 储结构。 4． 线性表的顺序存储中，元素之间的逻辑关系是通过 决定的，在线性表的 链接存储中，元素之间的逻辑关系是通过 决定的。 5． 深度为5的二叉树至多有结点数为 。 6． 数据结构即数据的逻辑结构包括 、 、 三种类型， 树型结构和图型结构称为 。 二．选择题 1． 有一个10阶对称矩阵，采用压缩存储方式，以行序为主序存储，A[0][0]的地址为 1，则A[7][4]的地址为（ ） A 13 B． 18 C． 33 D． 40 2． 线性表采用链表存储时其存储地址 。 A．必须是连续的 B．部分地址必须是连续的 C．一定是不连续的 D．连续不连续都可以 3． 下列叙述中错误的是 。 A． 串是一种特殊的线性表，其特殊性体现在数据元素是一个字符 B． 栈和队列是两种特殊的线性表，栈的特点是后进先出，队列的特点是先进先出。 C． 线性表的线性存储结构优于链式存储结构 D． 二维数组是其数据元素为线性表的线性表 4． 一棵二叉树的顺序存储结构如题图4-1所示，若中序遍历该二叉树，则遍历次序 为 . A. DBEGACFH B. ABDEGCFH C. DGEBHFCA D. ABCDEFGH A B C D E F G H 题图4-1 5． 设一棵二叉树的顺序存储结构如题图4-2所示，则该二叉树是 . A．完全二叉树 B．满二叉树 C．深度为4 的二叉树 D．深度为3的二叉树 1 2 3 4 5 6 7 题图4-2 6． 设T是Huffman树，它具有6个树叶，且各树叶的权分别为1，2，3，4，5，6。那么该树的非叶子结点的权之和为 。 A．51 B．21 C．30 D．49 7．设有一无向图的邻接矩阵如下所示，则该图所有顶点的度之和为 。 0 1 1 1 0 1 0 1 0 1 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 A．8 B．9 C．10 D．11 8．已知二叉树的后序遍历序列是fedbgca，中序遍历序列是dfebagc，则该二叉树的先序遍历序列是 。 A．defbagc B．abcdgef C．dbaefcg D．abdefcg 9．由三个结点构成的二叉树，共有 种不同的形态。 A．3 B． 4 C． 5 D． 6 10．在一个具有n个顶点的无向图中，要连通全部顶点至少需要 条边 A． n B．n+1 C．n/2 D．n-1 11．对线性表进行折半（二分）查找时，要求线性表必须 。 A．以顺序方式存储 B．以顺序方式存储且数据元素有序 C．以链表方式存储 D．以链表方式存储且数据元素有序 12．顺序查找一个具有n个元素的线性表，其时间复杂度为 ，二分查找一个具有n个元素的线性表，其时间复杂度为 。 2 A． O(n) B． O(log2n) C． O(n) D．O(nlog2n) 13.从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列中的正确位置上，此方法称为 ；从未排序序列中挑选元素，并将其放入已排序序列中的一端，此方法称为 ；依次将每两个相临的有序表合并成一个有序表的排序方法称为 ；当两个元素比较出现反序时就相互交换位置的排序方法称为 ； A．归并排序 B． 选择排序 C．交换排序 D．插入排序 三．简述下面的几个概念：单链表，栈、队列，排序二叉树。 A 四．简述空串和空格串的区别。 五．一棵度为2的树与二叉树有何区别？ B C 六．试分别画出具有3个结点的树和具有3个结点的二叉树 的所有不同形态。 D E F G 图4-3 H 七．已知一二叉树如题图4-3所示， 1． 用二叉链表和顺序存储方式分别存储此二叉树。画出相应的存储结构图。 2． 写出此二叉树的中序、先序、后序遍历序列。 八．已知一无向图如题图4-4所示，请给出该图的 1 1． 每个顶点的度。 2 3 2． 邻接矩阵 4 3． 邻接表 4． 按上述的邻接表写出广度和深度遍历序列。 5 6 九．已知一组数据元素为（46，75，18，54，15，27，42，39， 题图4-4 88，67） 1． 利用直接插入排序方法，写出每次插入后的结果。 2． 利用快速排序方法，写出每趟排序后的结果。 3． 利用2-路归并排序方法，写出每趟归并后的结果。 4． 利用冒泡排序方法，写出每趟排序后的结果。 十．假定一个表为（32，75，63，48，94，25，36，18，70），散列空间为[0..10]， 1． 若采用除留余数法构造表，哈希函数为H（K）=K MOD 11，用线性探测法解决 冲突，试画出哈希表，并求在等概率情况下的平均查找长度。 2． 若采用除留余数法构造表，哈希函数为H（K）=K MOD 11，用链地址法解决冲 突，试画出哈希表，并求在等概率情况下的平均查找长度。 十一． 有8个带权结点，权值为（3，7，8，2，6，10，14，9），试以它们为叶子结点构 造一棵哈夫曼树（要求每个结点左子树的权值小于等于右子树的权值），并计算出带权路径长度。 十二． 一对称阵An*n，若只存储此对称阵的上半三角元，写出以行为主序存储和以列为主 序存储时计算每一元素Aij存储地址的公式。 十三． 算法设计 1． 写出在循环单链表L中查找查找第i个元素的算法：SEARCH（L，i）。 2． 设有如下题图4-3的单链表，链表头指针为H，写一个将链表进行逆转的算法， 逆转以后的链表为题图4-4所示。 a1 a2 an NULL H „ 题图4-3单链表示意图 an an-1 a1 NULL H „ 题图4-4单链表示意图 3． 假定用一个带头结点的循环单链表表示循环队列（循环链队），该队列只设一 个队尾指针，不设头指针，试编写下面的算法： A． 向循环链队中插入一个元素x的算法（入队）。 B． 从循环链队中删除一个结点（出队）。 4． 数组A[N]存放循环队列中的元素，同时设两个变量分别存储队尾元素的位置 和队列中实际元素个数。 A． 写出此队列的队满条件。 B． 写出此队列的出、入队算法。 5． 设LA和LB为两个顺序存储的线性表，且元素按非递减排列，写出算法将其 合并为LC，且LC中的元素也按非递减排列。 6． 已知一个由n个整数组成的线性表，请定义该线性表的一种存储结构，并用C 语言编写算法，实现将n个元素中所有大于等于20的整数放在所有小于等于20的整数之后，要求算法的时间复杂度为O（n）,空间复杂度为O（1）。 7． 编写算法，计算二叉树中叶子结点的数目。 8． 编写一个按层次顺序（同一层自左向右）遍历二叉树的算法。 因篇幅问题不能全部显示，请点此查看更多更全内容