清华大学数据结构讲义_软件开发

PPT 内容

1. 数据结构计算机系
2. 第一章绪论1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示与实现 1.4 算法和算法分 1.4.1 算法 1.4.2 算法设计的要求 1.4.3 算法效率的度量 1.4.4 算法的存储空间的需求
3. 第一章绪论计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：信息的表示信息的处理而信息的表示和组又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。
4. 1.1什么是数据结构众所周知，计算机的程序是对信息进行加工处理。在大多数情况下，这些信息并不是没有组织，信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容。那么，什么是数据结构呢？先看以下几个例子。例1、电话号码查询系统设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排： (a1，b1)(a2，b2)…(an，bn) 其中ai，bi(i=1，2…n) 分别表示某人的名字和对应的电话号码要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。
5. 算法的设计，依赖于计算机如何存储人的名字和对应的电话号码，或者说依赖于名字和其电话号码的结构。数据的结构，直接影响算法的选择和效率。上述的问题是一种数据结构问题。可将名字和对应的电话号码设计成：二维数组、表结构、向量。假定名字和其电话号码逻辑上已安排成N元向量的形式，它的每个元素是一个数对(ai，bi)， 1≤i≤n 数据结构还要提供每种结构类型所定义的各种运算的算法。
6. 例2、图书馆的书目检索系统自动化问题例3、教师资料档案管理系统例4、多叉路口交通灯的管理问题 P3 通过以上几例可以直接地认为：数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。
7. 1.2 基本概念和术语数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素(Data Element):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。数据对象(Data Object)：是性质相同的数据元素的集合。是数据的一个子集。数据结构(Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合。
8. 数据结构主要指逻辑结构和物理结构数据之间的相互关系称为逻辑结构。通常分为四类基本结构：一、集合结构中的数据元素除了同属于一种类型外，别无其它关系。二、线性结构结构中的数据元素之间存在一对一的关系。三、树型结构结构中的数据元素之间存在一对多的关系。四、图状结构或网状结构结构中的数据元素之间存在多对多的关系。
9. 数据结构的形式定义为：数据结构是一个二元组： Data-Structure=(D，S) 其中：D是数据元素的有限集，S是D上关系的有限集。例复数的数据结构定义如下： Complex=(C，R) 其中：C是含两个实数的集合﹛C1，C2﹜，分别表示复数的实部和虚部。R={P}，P是定义在集合上的一种关系{〈C1，C2〉}。数据结构在计算机中的表示称为数据的物理结构，又称为存储结构。
10. 数据对象可以是有限的，也可以是无限的。　数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。抽象数据类型：一个数学模型以及定义在该模型上的一组操作。　　抽象数据类型实际上就是对该数据结构的定义。因为它定义了一个数据的逻辑结构以及在此结构上的一组算法。　　用三元组描述如下：　　　（Ｄ，Ｓ，Ｐ）
11. 数据结构在计算机中有两种不同的表示方法：顺序表示和非顺序表示由此得出两种不同的存储结构：顺序存储结构和链式存储结构顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。链式存储结构：在每一个数据元素中增加一个存放地址的指针（），用此指针来表示数据元素之间的逻辑关系。
12. 数据类型：在一种程序设计语言中，变量所具有的数据种类。例1、在FORTRAN语言中，变量的数据类型有整型、实型、和复数型例2、在C语言中数据类型：基本类型和构造类型基本类型：整型、浮点型、字符型构造类型：数组、结构、联合、指针、枚举型、自定义数据对象：某种数据类型元素的集合。例3、整数的数据对象是{…-3，-2，-1，0，1，2，3，…} 英文字符类型的数据对象是{A，B，C，D，E，F，…}
13. 1.3 抽象数据类型的表示和实现 P11
14. 1.4 算法和算法分析算法：是对特定问题求解步骤的一种描述算法是指令的有限序列，其中每一条指令表示一个或多个操作。算法具有以下五个特性：（1）有穷性一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。（2）确定性算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。（3）可行性一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。
15. 4）输入一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。 5）输出一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。 1.4.2 算法设计的要求评价一个好的算法有以下几个标准: (1) 正确性(Correctness ) 算法应满足具体问题的需求。 (2)可读性(Readability) 算法应该好读。以有利于阅读者对程序的理解。 (3)健状性(Robustness) 算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产年莫名其妙的输出结果。
16. (4)效率与存储量需求效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。 1.4.3 算法效率的度量对一个算法要作出全面的分析可分成两用人才个阶段进行，即事先分析和事后测试事先分析求出该算法的一个时间界限函数事后测试收集此算法的执行时间和实际占用空间的统计资料。定义：如果存在两个正常数c和n0，对于所有的n≧n0，有︱f(n) ︳≦c｜g(n) ︳则记作 f(n)=O(g(n))　　
17. 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，算法的时间量度记作 T(n)=O(f(n)) 称作算法的渐近时间复杂度。例１、for(I=1，I<=n;++I) for(j=1;j<=n;++j) { c[I][j]=0; for(k=1;k<=n;++k) c[I][j]+=a[I][k]*b[k][j]; }
18. 由于是一个三重循环，每个循环从1到n，则总次数为: n×n×n=n3 　时间复杂度为T(n)=O(n3) 频度：是指该语句重复执行的次数例２ {++x;s=0;} 将x自增看成是基本操作，则语句频度为１，即时间复杂度为Ｏ(1) 如果将s=0也看成是基本操作，则语句频度为２，其时间复杂度仍为Ｏ(1)，即常量阶。例３、for(I=1;I<=n;++I) {++x;s+=x;} 语句频度为：2n　其时间复杂度为：O(n) 即时间复杂度为线性阶。
19. 例４、for(I=1;I<=n;++I) 　　　　for(j=1;j<=n;++j) {++x;s+=x;} 语句频度为：2n2 　其时间复杂度为：O(n2) 即时间复杂度为平方阶。定理：若A(n)=a m n m +a m-1 n m-1 +…+a1n+a0是一个m次多项式，则A(n)=O(n m) 　　　　　　　　证略。例５for(i=2;i<=n;++I) for(j=2;j<=i-1;++j) {++x;a[i，j]=x;}
20. 语句频度为： 1+2+3+…+n-2=(1+n-2) ×(n-2)/2 =(n-1)(n-2)/2 =n2-3n+2 ∴时间复杂度为O(n2) 即此算法的时间复杂度为平方阶. 一个算法时间为O(1)的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为O(n2)的算法则由一个二次多项式来限界。
21. 以下六种计算算法时间的多项式是最常用的。其关系为： O(1)
22. 有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。例如： Void bubble-sort(int a[]，int n) for(I=n-1;change=TURE;I>1 && change;--I) { change=false; for(j=0;ja[j+1]) { a[j] ←→a[j+1]; change=TURE} } 最好情况：0次
23. 最坏情况：1+2+3+…+n-1 =n(n-1)/2 平均时间复杂度为:O(n2) 1.4.4算法的存储空间需求空间复杂度:算法所需存储空间的度量，记作: S(n)=O(f(n)) 其中n为问题的规模(或大小)
24. 第二章线性表2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表 2.4 一元多项式的表示及相加
25. 2.1 线性表的逻辑结构线性表(Linear List) ：由n(n≧)个数据元素(结点)a1，a2， …an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表，常常将非空的线性表(n>0)记作： (a1，a2，…an) 这里的数据元素ai(1≦i≦n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。例1、26个英文字母组成的字母表（A，B，C、…、Z）例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况。（6，17，28，50，92，188）
26. 例3、学生健康情况登记表如下：姓名学号性别年龄健康情况王小林790631 男 18 健康陈红790632 女 20 一般刘建平790633 男 21 健康张立立790634 男 17 神经衰弱 …….. ……..…….……. …….
27. 例4、一副扑克的点数（2，3，4，…，J，Q，K，A）从以上例子可看出线性表的逻辑特征是：在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2；有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋a n-1；其余的内部结点ai(2≦i≦n-1)都有且仅有一个直接前趋a i-1和一个直接后继a i+1。线性表是一种典型的线性结构。数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。抽象数据类型的定义为：P19
28. 算法2.1 例2-1 利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=A∪B。 void union(List &La，List Lb) { La-len=listlength(La); Lb-len=listlength(Lb); for(I=1;I<=lb-len;I++) { getelem(lb，I，e); if(!locateelem(la，e，equal))listinsert(la，++la-en，e) } }
29. 算法2.2 例2-2 巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。此问题的算法如下：
30. void mergelist(list la，list lb，list &lc) initlist(lc); I=j=1;k=0; la-len=listlength(la); lb-len=listlength(lb); while((I<=la-len)&&(j<=lb-len)){
31. getelem(la，I，ai);getelem(lb，j，bj); if(ai<=bj){listinsert(lc，++k，ai);++I;} else{listinsert(lc，++k，bj);++j;} } while(I<=la-len){ getelem((la，I++，ai);listinsert(lc，++k，ai); } while(j<=lb-len){ getelem((lb，j++，bj);listinsert(lc，++k，bi); } }
32. 2.2 线性表的顺序存储结构 2.2.1 线性表把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第I+1个数据元素的存储位置LOC( a i+1)和第i个数据元素的存储位置LOC(a I )之间满足下列关系： LOC(a i+1)=LOC(a i)+l 线性表的第i个数据元素ai的存储位置为： LOC(ai)=LOC(a1)+(I-1)*l
33. 由于C语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。又因为除了用数组来存储线性表的元素之外，顺序表还应该用一个变量来表示线性表的长度属性，所以我们用结构类型来定义顺序表类型。 # define ListSize 100 typedef int DataType; typedef struc{ DataType data[ListSize]; int length; } Sqlist;
34. 2.2.2 顺序表上实现的基本操作在顺序表存储结构中，很容易实现线性表的一些操作，如线性表的构造、第i个元素的访问。注意：C语言中的数组下标从“0”开始，因此，若L是Sqlist类型的顺序表，则表中第i个元素是l.data[I-1]。以下主要讨论线性表的插入和删除两种运算。 1、插入线性表的插入运算是指在表的第I(1≦i≦n+1个位置上，插入一个新结点x，
35. 使长度为n的线性表 (a1，…a i-1，ai，…，an) 变成长度为n+1的线性表 (a1，…a i-1，x，ai，…，an) 算法2.3 Void InsertList(Sqlist*L，DataType x，int I) { int j; if(I<1 || I>l.length+1) printf(“Position error”); return ERROR
36. if(l.length>=ListSize) printf(“overflow”); exit(overflow); for(j=l.length-1;j>=I-1;j--) l.data[j+1]=l.data[j]; l.data[I-1]=x; l.length++; }
37. 现在分析算法的复杂度。这里的问题规模是表的长度，设它的值为。该算法的时间主要化费在循环的结点后移语句上，该语句的执行次数（即移动结点的次数）是。由此可看出，所需移动结点的次数不仅依赖于表的长度，而且还与插入位置有关。当时，由于循环变量的终值大于初值，结点后移语句将不进行；这是最好情况，其时间复杂度O（1）；当=1时，结点后移语句将循环执行n次，需移动表中所有结点，这是最坏情况，
38. 其时间复杂度为O（n）。由于插入可能在表中任何位置上进行，因此需分析算法的平均复杂度在长度为n的线性表中第i个位置上插入一个结点，令Eis(n)表示移动结点的期望值（即移动的平均次数），则在第i个位置上插入一个结点的移动次数为n-I+1。故 Eis(n)= pi(n-I+1) 不失一般性，假设在表中任何位置(1≦i≦n+1)上插入结点的机会是均等的，则 p1=p2=p3=…=p n+1=1/(n+1) 因此，在等概率插入的情况下， Eis(n)= (n-I+1)/(n+1)=n/2
39. 也就是说，在顺序表上做插入运算，平均要移动表上一半结点。当表长 n较大时，算法的效率相当低。虽然Eis(n)中n的的系数较小，但就数量级而言，它仍然是线性阶的。因此算法的平均时间复杂度为O(n)。 2、删除线性表的删除运算是指将表的第i(1≦i≦n)结点删除，使长度为n的线性表： (a1，…a i-1，ai，a i+1…，an) 变成长度为n-1的线性表 (a1，…a i-1，a i+1，…，an)
40. Void deleteList(Sqlist*L，int I) { int j; if(I<1 || I>l.length) printf(“Position error”); return ERROR for(j=i;j<=l.length-1;j++) l.data[j-1]=l.data[j]; l.length--; }
41. 该算法的时间分析与插入算法相似，结点的移动次数也是由表长n和位置i决定。若I=n，则由于循环变量的初值大于终值，前移语句将不执行，无需移动结点；若I=1，则前移语句将循环执行n-1次，需移动表中除开始结点外的所有结点。这两种情况下算法的时间复杂度分别为O(1)和O(n)。删除算法的平均性能分析与插入算法相似。在长度为n的线性表中删除一个结点，令Ede(n)表示所需移动结点的平均次数，删除表中第i个结点的移动次数为n-i，故 Ede(n)= pi(n-I) 式中，pi表示删除表中第i个结点的概率。在等
42. 概率的假设下， p1=p2=p3=…=pn=1/n 由此可得： Ede(n)= (n-I)/n=(n-1)/2 即在顺序表上做删除运算，平均要移动表中约一半的结点，平均时间复杂度也是O(n)。 2.3 线性表的链式表示和实现线性表的顺序表示的特点是用物理位置上的邻接关系来表示结点间的逻辑关系，这一特点使我们可以随机存取表中的任一结点，但它也使得
43. 插入和删除操作会移动大量的结点.为避免大量结点的移动，我们介绍线性表的另一种存储方式，链式存储结构，简称为链表(Linked List)。 2.3.1 线性链表链表是指用一组任意的存储单元来依次存放线性表的结点，这组存储单元即可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息，这个信息称为指针(pointer)或链(link)。这两部分组成了链表中的结点结构：
44. 其中：data域是数据域，用来存放结点的值。next是指针域（亦称链域），用来存放结点的直接后继的地址（或位置）。链表正是通过每个结点的链域将线性表的n个结点按其逻辑次序链接在一起的。由于上述链表的每一个结只有一个链域，故将这种链表称为单链表（Single Linked)。显然，单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。同时，由于终端结点无后继，故终端结点的指针域为空，即null（图示中也可用^表示)。例1、线性表:(bat，cat，eat，fat，hat，jat，lat，mat) datalink
45. 的单链表示意图如下： …… 110 …… 130 135 …… 160 头指针 head 165 170 …… 200 205 …………………hat200…….……cat135eat170….……matNullbat130fat110…………jat205lat160………… 165
46. headbat cat eat mat ^ …单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。例如：若头指针名是head，则把链表称为表head。用C语言描述的单链表如下：Typedef char datatype;Typedef struct node{ datatype data; struct node *next; }listnode;
47. typedef listnode *linklist; listnode *p; linklist head; 注意区分指针变量和结点变量这两个不同的概念。 P为动态变量，它是通过标准函数生成的，即 p=(listnode*)malloc(sizeof(listnode)); 函数malloc分配了一个类型为listnode的结点变量的空间，并将其首地址放入指针变量p中。一旦p所指的结点变量不再需要了，又可通过标准函数 free(p) 释放所指的结点变量空间。
48. 指针变量P和（其值为结点地址）和结点变量*P之间的关系。
49. 一、建立单链表假设线性表中结点的数据类型是字符，我们逐个输入这些字符型的结点，并以换行符‘\n’为输入结束标记。动态地建立单链表的常用方法有如下两种： 1、头插法建表该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。
50. linklist createlistf(void) { char ch; linklist head; listnode *p; head=null; ch=getchar( ); while (ch!=‵\n′{ p=(listnode*)malloc(sizeof(listnode)); p–>data=ch; p–>next=head;
51. head=p; ch=getchar( ); } return (head); }
52. listlink createlist(int n) { int data; linklist head; listnode *p head=null; for(i=n;i>0;--i){ p=(listnode*)malloc(sizeof(listnode)); scanf((〝%d〞，&p–>data); p–>next=head; head=p; }
53. return(head); } 2、尾插法建表头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。例：
54. linklist creater( ) { char ch; linklist head; listnode *p，*r; //(， *head;) head=NULL;r=NULL; while((ch=getchar( )!=‵\n′){ p=(listnode *)malloc(sizeof(listnode)); p–>data=ch; if(head=NULL) head=p; else
55. r–>next=p; r=p; } if (r!=NULL) r–>next=NULL; return(head); } 说明：第一个生成的结点是开始结点，将开始结点插入到空表中，是在当前链表的第一个位置上插入，该位置上的插入操作和链表中其它位置上的插入操作处理是不一样的，原因是开始结点的位置是存放在头指针（指针变量）中，
56. 而其余结点的位置是在其前趋结点的指针域中。算法中的第一个if语句就是用来对第一个位置上的插入操作做特殊处理。算法中的第二个if语句的作用是为了分别处理空表和非空表两种不同的情况，若读入的第一个字符就是结束标志符，则链表head是空表，尾指针r亦为空，结点*r不存在；否则链表head非空，最后一个尾结点*r是终端结点，应将其指针域置空。如果我们在链表的开始结点之前附加一个结点，并称它为头结点，那么会带来以下两个优点： a、由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就
57. 和在表的其它位置上的操作一致，无需进行特殊处理； b、无论链表是否为空，其头指针是指向头结点在的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。其算法如下： linklist createlistr1( ){ char ch; linklist head=(linklist)malloc(sizeof(listnode)); listnode *p，*r
58. r=head; while((ch=getchar( ))!=‵\n′{ p=(listnode*)malloc(sizeof(listnode)); p–>data=ch; p–>next=p; r=p; } r–>next=NULL; return(head); }
59. 上述算法里动态申请新结点空间时未加错误处理，可作下列处理： p=(listnode*)malloc(sizeof(listnode)) if(p==NULL) error(〝No space for node can be obtained〞); return ERROR; 以上算法的时间复杂度均为O(n)。
60. 二、查找运算 1、按序号查找在链表中，即使知道被访问结点的序号i，也不能象顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，顺链域next逐个结点往下搜索，直到搜索到第i个结点为止。因此，链表不是随机存取结构。设单链表的长度为n，要查找表中第i个结点，仅当1≦i≦n时，i的值是合法的。但有时需要找头结点的位置，故我们将头结点看做是第0 个结点，其算法如下：
61. Listnode * getnode(linklist head ， int i) { int j; listnode * p; p=head;j=0; while(p–>next && jnext; j++; } if (i==j) return p;
62. else return NULL; } 2、按值查找按值查找是在链表中，查找是否有结点值等于给定值key的结点，若有的话，则返回首次找到的其值为key的结点的存储位置；否则返回NULL。查找过程从开始结点出发，顺着链表逐个将结点的值和给定值key作比较。其算法如下：
63. Listnode * locatenode(linklist head，int key) { listnode * p=head–>next; while( p && p–>data!=key) p=p–>next; return p; } 该算法的执行时间亦与输入实例中的的取值key有关，其平均时间复杂度的分析类似于按序号查找，也为O(n)。
64. 三、插入运算插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，我们必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点*p，并令结点*p的指针域指向新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化，插入过程如：
65. 具体算法如下： void insertnode(linklist head，datetype x，int i) { listnode * p，*q; p=getnode(head，i-1); if(p==NULL) error(〝position error〞); q=(listnode *)malloc(sizeof(listnode)); q–>data=x; q–>next=p–next; p–>next=q; }
66. 设链表的长度为n，合法的插入位置是1≦i≦n+1。注意当i=1时，getnode找到的是头结点，当 i=n+1时，getnode找到的是结点an。因此，用i-1做实参调用getnode时可完成插入位置的合法性检查。算法的时间主要耗费在查找操作getnode上，故时间复杂度亦为O(n)。四、删除运算删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点a a i-1的指针域next中，所以我们必须首先找到
67. a i-1的存储位置p。然后令p–>next指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间，将其归还给“存储池”。此过程为：
68. 具体算法如下： void deletelist(linklist head， int i) { listnode * p， *r; p=getnode(head，i-1); if(p= =NULL || p–>next= =NULL) return ERROR; r=p–>next; p–>next=r–>next; free( r ) ; }
69. 设单链表的长度为n，则删去第i个结点仅当1≦i≦n时是合法的。注意，当i=n+1时，虽然被删结点不存在，但其前趋结点却存在，它是终端结点。因此被删结点的直接前趋*p存在并不意味着被删结点就一定存在，仅当*p存在（即p!=NULL）且*p不是终端结点（即p–>next!=NULL）时，才能确定被删结点存在。显然此算法的时间复杂度也是O(n)。从上面的讨论可以看出，链表上实现插入和删除运算，无须移动结点，仅需修改指针。
70. 2.3.2 循环链表循环链表时一种头尾相接的链表。其特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。单循环链表：在单链表中，将终端结点的指针域NULL改为指向表头结点的或开始结点，就得到了单链形式的循环链表，并简单称为单循环链表。为了使空表和非空表的处理一致，循环链表中也可设置一个头结点。这样，空循环链表仅有一个自成循环的头结点表示。如下图所示：
71. a1 an ….head⑴ 非空表⑵ 空表在用头指针表示的单链表中，找开始结点a1的时间是O(1)，然而要找到终端结点an，则需从头指针开始遍历整个链表，其时间是O(n)
72. 在很多实际问题中，表的操作常常是在表的首尾位置上进行，此时头指针表示的单循环链表就显得不够方便.如果改用尾指针rear来表示单循环链表，则查找开始结点a1和终端结点an都很方便，它们的存储位置分别是(rear–>next) —>next和rear，显然，查找时间都是O(1)。因此，实际中多采用尾指针表示单循环链表。由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或p—>next是否为空，而是判断它们是否等于某一指定指针，如头指什或尾指针等。
73. 例、在链表上实现将两个线性表(a1，a2，a3，…an)和(b1，b2，b3，…bn)链接成一个线性表的运算。 linklist connect(linklist heada，linklist headb) { linklist p=heada—>next; heada—>next=(headb—next)—>next free(headb—>next); headb—>next=p; return(headb); }
74. 2.3.3双链表双向链表(Double linked list):在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样就形成的链表中有两个方向不同的链，故称为双向链表。形式描述为： typedef struct dlistnode{ datatype data; struc dlistnode *prior，*next; }dlistnode; typedef dlistnode * dlinklist; dlinklist head;
75. 和单链表类似，双链表一般也是由头指针唯一确定的，增加头指针也能使双链表上的某些运算变得方便，将头结点和尾结点链接起来也能构成循环链表，并称之为双向链表。设指针p指向某一结点，则双向链表结构的对称性可用下式描述： (p—>prior)—>next=p=(p—>next)—>prior 即结点*p的存储位置既存放在其前趋结点*(p—>prior)的直接后继指针域中，也存放在它的后继结点*(p—>next)的直接前趋指针域中。
76. 双向链表的前插操作算法如下： void dinsertbefor(dlistnode *p，datatype x) { dlistnode *q=malloc(sizeof(dlistnode)); q—>data=x; q—>prior=p—>prior; q—>next=p; p—>prior—>next=q; p—>prior=q; }
77. void ddeletenode(dlistnode *p) { p–>prior–>next=p–>next; p–>next–>prior=p–>prior; free(p); } 注意：与单链表的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。上述两个算是法的时间复杂度均为O(1)。
78. 第三章栈和队列3.1 栈 3.1.1 抽象数据类型栈的定义 3.1.2 栈的表示和实现 3.2 栈的应用举例 3.2.1 数制转换 3.2.2 括号匹配的检验 3.2.4 行编辑程序 3.2.5 迷宫求解 3.2.5 表达式求值
79. 3.1.1 栈 3.1.1 栈的定义及基本运算栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。假设栈S=(a1，a2，a3，…an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，…an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。
80. 3.1.2 顺序栈由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量top
81. 例、一叠书或一叠盘子。栈的抽象数据类型的定义如下：P44 a n a n-1 a2 a1……栈顶栈底
82. top7 6 5 4 3 2 1 -1
83. 来指示当前栈顶的位置，通常称top为栈顶指针。因此，顺序栈的类型定义只需将顺序表的类型定义中的长度属性改为top即可。顺序栈的类型定义如下： # define StackSize 100 typedef char datatype; typedef struct { datatype data[stacksize]; int top; }seqstack;
84. 设S是SeqStack类型的指针变量。若栈底位置在向量的低端，即s–>data[0]是栈底元素，那么栈顶指针s–>top是正向增加的，即进栈时需将s–>top加1，退栈时需将s–>top 减1。因此，s–>top<0表示空栈， s–>top =stacksize-1表示栈满。当栈满时再做进栈运算必定产生空间溢出，简称“上溢”;当栈空时再做退栈运算也将产生溢出，简称“下溢”。上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。
85. 3、判断栈满 int stackfull(seqstack *s) { return(s–>top==stacksize-1); } 4、进栈 void push(seqstack *s，datatype x) { if (stackfull(s)) error(“stack overflow”); s–>data[++s–>top]=x; }
86. 1、置空栈 void initstack(seqstack *s) { s–>top=-1; } 2、判断栈空 int stackempty(seqstack *s) { return(s–>top==-1); }
87. 5、退栈 datatype pop(seqstack *s) { if(stackempty(s)) error(“stack underflow”); x=s–>data[top]; s–>top--; return(x) //return(s–>data[s–>top--]); }
88. 6、取栈顶元素 Datatype stacktop(seqstack *s) { if(stackempty(s) error(“stack is enpty”); return s–>data[s–>top]; }
89. 3.1.3 链栈栈的链式存储结构称为链栈，它是运算是受限的单链表，克插入和删除操作仅限制在表头位置上进行.由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。链栈的类型说明如下： typedef struct stacknode{ datatype data struct stacknode *next }stacknode;
90. Void initstack(seqstack *p) { p–>top=null; } int stackempty(linkstack *p) { return p–>top==null; }
91. Void push(linkstack *p,datatype x) { stacknode *q q=(stacknode*)malloc(sizeof(stacknode)); q–>data=x; q–>next=p–>top; p–>top=p; }
92. Datatype pop(linkstack *p) { datatype x; stacknode *q=p–>top; if(stackempty(p) error(“stack underflow.”); x=q–>data; p–>top=q–>next; free(q); return x; }
93. datatype stack top(linkstack *p) { if(stackempty(p)) error(“stack is empty.”); return p–>top–>data; }
94. 3.2 栈的应用举例由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。以下是几个栈应用的例子。 3.2.1 数制转换十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理: N=(n div d)*d+n mod d ( 其中:div为整除运算,mod为求余运算) 例如 (1348)10=(2504)8，其运算过程如下：
95. n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2
96. void conversion( ) { initstack(s); scanf (“%”,n); while(n){ push(s,n%8); n=n/8; } while(! Stackempty(s)){ pop(s,e); printf(“%d”,e); } }
97. 3.2.2 括号匹配的检验假设表达式中充许括号嵌套,则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例：（（）（）（（））） 3.2.3 行编辑程序在编辑程序中，设立一个输入缓冲区，用于接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入错误，并在发现有误时可以及时更正。
98. 行编辑程序算法如下: void lineedit( ){ initstack(s); ch=gether( ); while(ch!=eof){ while(ch!=eof && ch!=‘\n’){ switch(ch){ case ‘#’ : pop(s,c); case ‘@’ : clearstack(s); default : push(s,ch); }
99. ch=getchar( ); } clearstack(s); if(ch!=eof) ch=gethar( ); } destroystack(s); }
100. 3.2.4 迷宫求解入口出口
101. 3.4 队列 3.4.1 抽象数据类型队列的定义队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。　　例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。　　当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,…an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,…an ，也就是说队列的修改是依先进先出的原则进行的。
102. 下图是队列的示意图：　　　　　　　　　　　 a1　a2　…　an 　　　　　　　出队入队队头队尾队列的抽象数据定义见书Ｐ593.4.2 循环队列－队列的顺序表示和实现　　队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表，和顺序表一样，顺序队列也是必须用一个向量空间来存放当前队
103. 列中的元素。由于队列的队头和队尾的位置是变化的，因而要设两个指针和分别指示队头和队尾元素在队列中的位置，它们的初始值地队列初始化时均应置为０。入队时将新元素插入所指的位置，然后将加１。出队时，删去所指的元素，然后将加１并返回被删元素。由此可见，当头尾指针相等时队列为空。在非空队列里，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一位置。　０　１　２　３ 0 1 2 3　Front rearabcFront rear (a)队列初始为空　　　　　　（b）A,B,C入队
104. 　０　１　２　３　　　０　１　２　３ b c front rear front rear （c) a出队 (d) b,c出队，队为空和栈类似，队列中亦有上溢和下溢现象。此外，顺序队列中还存在“假上溢”现象。因为在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现象称为假上溢。
105. 为充分利用向量空间。克服上述假上溢现象的方法是将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量，存储在其中的队列称为循环队列（Circular Queue)。在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（QueueSize-1）时，其加1操作的结果是指向向量的下界0。这种循环意义下的加1操作可以描述为： if(I+1==QueueSize) i=0; else i++; 利用模运算可简化为： i=(i+1)%QueueSize
106. 显然，因为循环队列元素的空间可以被利用，除非向量空间真的被队列元素全部占用，否则不会上溢。因此，除一些简单的应用外，真正实用的顺序队列是循环队列。如图所示：由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，我们无法通过front=rear来判断队列“空”还是“满”。解决此问题的方法至少有三种：其一是另设一个布尔变量以匹别队列的空和满；其二是少用一个元素的空间，约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）；
107. 其三是使用一个计数器记录队列中元素的总数（实际上是队列长度）。下面我们用第三种方法实现循环队列上的六种基本操作，为此先给出循环队列的类型定义。 #define QueueSize 100 typedef char DataType; typedef Struct{ int front; int rear; int count; datatype data[queuesize] }cirqueue;
108. （1）置空队 void initqueue(cirqueue *q){ q–>front=q–>rear=0; q–>count=0; } （2）判断队空 int queueempty(cirqueue *q) { return q–>count==0; } （3）判断队满 int queuefull(cirqueue *q){ return q–>count==queuesize; }
109. （4）入队 void enqueue(cirqueue *q,datatype x) { if(queuefull(q)) error(“queue overflow”); q–>count++; q–data[q–rear]=x; q–rear=(q–rear+1)%queuesize; }
110. （5）出队 datatype dequeue(cirqueue *q) { datatype temp; if(queueempty(q)) error(“queue underflow”); temp=q–>data[q–>front]; q–>count--; q–front=(q–>front+1)%queuesize; return temp; }
111. （6）取头指针 datatype queuefront(cirqueue *q) { if(queueempty(q)) error(“queue is empty.”); return q–>data[q–>front]; }
112. 3.4.3 链队列队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。于是，一个链队列由一个头指针唯一确定。和顺序队列类似，我们也是将这两个指针封装在一起，将链队列的类型LinkQueue定义为一个结构类型： typedef struct queuenode{ datatype data; struct queuenode *next; }queuenode;
113. typedef struct{ queuenode *front; queuenode *rear; }linkqueue; 下面给出链队列上实现的基本运算： void initqueue(linkqueue *q) { q–>front=q–>rear=null; }
114. int queueempty(linkqueue *q) { return q–>front==null &&q–>rear==null; } void enqueue(linkqueue *q,datatype x) { queuenode *p p=(queuenode * )malloc(sizeof(queuenode)); p–>data=x; p–next=null; if(queueempty(q)) q–>front=q–>rear=p;
115. else{ q–>rear–>next=p; q–rear=p; } } Datatype dequeue(linkqueue *q) { datatype x; queuenode *p
116. if(queueempty(q)) error(“queue underflow”); p=q–>front; x=p–>data; q–>front=p–>next; if(q–>rear==p) q–rear=null; free(p); return x; }
117. datatype queuefront(linkqueue *q) { if(queueempty(q)) error(“queue is empty.”); return q–>front–>data; } 注意：在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。
118. 习题 1、设将整数以万计、2、3、4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下有问题：（1）若入栈次序为push(1)，pop()，push(2，push(3)，pop()，pop( )，push(4)，pop( )，则出栈的数字序列为什么？（2）能否得到出栈序列车员423和平共处五项原则432？并说明为什么不能得到或如何得到。（3）请分析1、2、3、4的24种排列中，哪些序列可以通过相应的入出栈得到。 2、链栈中为何不设头指针？ 3、循环队列的优点是什么？如何判断它的空和满？
119. 4、设长度为n的链队列用单循环链表表示，若只设头指针，则怎样进行入队和出队操作；若只设尾指针呢？ 5、利用栈的基本操作，写一个返回栈s中结点个数的算法int stacksize(seqstack s)，并说明s为何不用作为指针参数？ 6、利用栈的基本操作，写一个将栈中所有结点均删除算法，并说明S为何要作为指针参数？ 7、用第二种方法，即少用一个元素空间的方法来区别循环队列的队空和队满，试设计置空队、判队空、判队满、出队、入队及取队头元素等六个基本操作。
120. 8、假设循环队列只设rear和quelen来分别指示队尾元素的位置和队中元素的个数，试给出判断此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头指针。 9、指出下列程序段的功能是什么？ (1) void demo1(seqstack *s){ int I;arr[64];n=0; while (!stackempty(s)) arr[n++]=pos(s); for(I=0;
121. while(! Stackempty(s)) if(I=pop(s)!=m) push(t,I); While(! Stackempty(t)) { i=pop(t); push(s,I); } }
122. 第四章串4.1 串类型的定义 4.2 串的表示和实现 4.2.1 定长顺序存储表示 4.2.2 堆分配存储表示 4.2.3 串的块链存储表示
123. 4.1 串类型的定义一、串和基本概念串(String)是零个或多个字符组成的有限序列。一般记作S=“a1a2a3…an”，其中S 是串名，双引号括起来的字符序列是串值；ai(1≦i≦n)可以是字母、数字或其它字符；串中所包含的字符个数称为该串的长度。长度为零的串称为空串(Empty String)，它不包含任何字符。通常将仅由一个或多个空格组成的串称为空白串(Blank String) 注意：空串和空白串的不同，例如“ ”和“”分别表示长度为1的空白串和长度为0的空串。
124. 串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为子串在主串中的序号（或位置）。例如，设A和B分别为 A=“This is a string” B=“is” 则B是A的子串，A为主串。B在A中出现了两次，其中首次出现所对应的主串位置是3。因此，称B在A中的序号（或位置）为3 特别地，空串是任意串的子串，任意串是其自身的子串。通常在程序中使用的串可分为两种：串变量和串常量。串常量和整常数、实常数一样，在
125. 程序中只能被引用但不能不能改变其值，即只能读不能写。通常串常量是由直接量来表示的，例如语句Error(“overflow”)中“overflow”是直接量。但有的语言允许对串常量命名，以使程序易读、易写。如C++中，可定义 const char path[]=“dir/bin/appl”; 这里path是一个串常量，对它只能读不能写。串变量和其它类型的变量一样，其取值是可以改变的。二、串的抽象数据定义串的抽象数据类型定义台书P71
126. 三、串的基本操作对于串的基本操作，许多高级语言均提供了相应的运算或标准库函数来实现。下面仅介绍几种在C语言中常用的串运算，其它的串操作见的文件。定义下列几个变量： char s1[20]=“dirtreeformat”,s2[20]=“file.mem”; char s3[30],*p; int result; 求串长(length) int strlen(char s); //求串的长度例如：printf(“%d”,strlen(s1)); 输出13
127. （2）串复制(copy) char *strcpy(char to,char from); 该函数将串from复制到串to中，并且返回一个指向串to的开始处的指针。例如：strcpy(s3,s1); //s3=“dirtreeformat” (3)联接(concatenation) char strcat(char to,char from) 该函数将串from复制到串to的末尾，并且返回一个指向串to的开始处的指针。例如：strcat(s3,”/”) strcat(s3,s2); //s3=“dirtreeformat/file.mem”
128. (4)串比较（compare) int strcmp(chars1,char s2); 该函数比较串s1和串s2的大小，当返回值小于0，等于0或大于0时分别表示s1s2 例如：result=strcmp(“baker”,”Baker”) result>0 result=strcmp(“12”,”12”); result=0 result=strcmp(“Joe”,”Joseph”); result<0 （5）字符定位(index) char strchr(char s,char c); 该函数是找c在字符串中第一次出现的位置，若找到则返回该位置，否则返回NULL。例如：p=strchr(s2,”.”); p 指向“file”之后的位置 if(p) strcpy(p,”.cpp”); s2=“file.cpp”
129. 上述串的操作是最基本的，其中后四个还有变种形式：strncpy，strncat，strncmp，strnchr。串的其余操作可由这些基本操作组合而成。例1、求子串求子串的过程即为复制字符序列的过程，将串S中的第pos个字符开始长度为len的字符复制到串T中。 void substr(string sub,string s,int pos,int len) { if(pos<0 || pos>strlen(s)-1 || len<0) error(“parameter error”) strncpy(sub,&s[pos],len); }
130. 例2、串的定位index(s,t,pos) 在主串中取从第i个字符起、长度和串T相等的子串和T比较，若相等，则求得函数值为i，否则值增1直至S中不存在和串T相等的子串为止。
131. int index(string s,string t,int pos){ if(pos>0){ n=strlen(s); m=strlen(t); i=pos; while(i
132. 4.2 串的表现和实现因为串是特殊的线性表，故其存储结构与线性表的存储结构类似。只不过由于组成串的结点是单个字符。串有三种机内表示方法，下面分别介绍。 4.2.1定长顺序存储表示定长顺序存储表示,也称为静态存储分配的顺应表。它是用一组连续的存储单元来存放串中的字符序列。所谓定长顺序存储结构，是直接使用定长的字符数组来定义，数组的上界预先给出： #define maxstrlen 256 typedef char sstring[maxstrlen]; sstring s; //s是一个可容纳255个字符的顺序串。
133. 一般可使用一个不会出现在串中的特殊字符在串值的尾部来表示串的结束。例如，C语言中以字符‵\0′表示串值的终结，这就是为什么在上述定义中，串空间最大值maxstrlen为256，但最多只能存放255个字符的原因，因为必须留一个字节来存放‵\0′字符。若不设终结符，可用一个整数来表示串的长度，那么该长度减1的位置就是串值的最后一个字符的位置。此时顺序串的类型定义和顺序表类似： typedef struct{ char ch[maxstrlen]; int length; }sstring; //其优点是涉及到串长操作时速度快。
134. 4.2.2堆分配存储表示这种存储表示的特点是，仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配而得。所以也称为动态存储分配的顺序表。在C语言中，利用和等动态存储管理函数，来根据实际需要动态分配和释放字符数组空间。这样定义的顺序串类型也有两种形式。 typedef char *string; //c中的串库相当于此类型定义 typedef struct{ char *ch; int length; }hsring;
135. status sinsert(hstring s,int pos,hstring t){ if(pos<1 || pos>s.length+1) return error; if(t.length){ if(!(s.ch=(char*)realloc(s.ch,(s.length+t.length)*sizeof(char))) exit(overflow); for(i=s.length-1;i>pos-1;--i) s.ch[I+t.length]=s.ch[i]; s.ch[pos-1..pos+t.length-2]=t.ch[0..t.length-1];
136. s.length+=t.length; } return ok; }
137. int strlen(hstring s){ return s.length; } status clearstring(hstring s){ if(s.ch){free(s.ch);s.ch=NULL;} s.length=0; }
138. status strassign(hstring t,char *chars){ //生成一个其值等于串常量chars的串t if(t.ch) free(t.ch); for(i=0,(c=chars;c;++i),++c); if(!i) { t.ch=null; t.length=0; } else{ if(!(t.ch=(char *)malloc(I*sizeof(char)))) exit(overflow);
139. t.ch[0..i-1]=chars[0..i-1]; t.length=i; } }
140. int strcmp(hstring s,hstring t){ for(i=0;i
141. status concat(hstring t,hstring s1,hstring s2){ if(!(t.ch)=(char*)malloc(s1.length+s2.length)*sizeof(char))) exit(overflow); t.ch[0..s1.length-1]=s1.ch[0..s1.length-1]; t.length=s1.length+s2.length; t.ch[s1.length..t.length-1]=s2.ch[0..s2.length-1]; }
142. Status substr(hstring sub,hstring s,int pos,int len){ if(pos<1 || pos>s.length || len<0 || len>s.length-pos+1) return error; if(sub.ch) free(sub.ch); if(!len){ sub.ch=null; sub.length=0; }
143. else{ sub.ch=(char *)malloc(len*sizeof(char)); sub.ch[0..len-1]=s[pos-1..pos+len-2]; s.length=len; } }
144. 4.2.3 串的链式存储结构顺序串上的插入和删除操作不方便，需要移动大量的字符。因此，我们可用单链表方式来存储串值，串的这种链式存储结构简称为链串。 typedef struct node{ char data; struct node *next; }lstring; 一个链串由头指针唯一确定。这种结构便于进行插入和删除运算，但存储空间利用率太低。
145. 为了提高存储密度，可使每个结点存放多个字符。通常将结点数据域存放的字符个数定义为结点的大小，显然，当结点大小大于 1时，串的长度不一定正好是结点的整数倍，因此要用特殊字符来填充最后一个结点，以表示串的终结。对于结点大小不为1的链串，其类型定为义只需对上述的结点类型做简单的修改即可。 #define nodesize 80 typedef struct node{ char data[nodesize]; struct node *next; }lstring;
146. 4.3 串的模式匹配算法子串定位运算又称为模式匹配(Pattern Matching)或串匹配(String Matching)，此运算的应用在非常广泛。例如，在文本编辑程序中，我们经常要查找某一特定单词在文本中出现的位置。显然，解此问题的有效算法能极大地提高文本编辑程序的响应性能。在串匹配中，一般将主串称为目标串，子串称之为模式串。设S为目标串，T为模式串，且不妨设： S=“s0s1s2…sn-1” T=“t0t1…tm-1” 串的匹配实际上是对于合法的位置0≦i≦n-m依次将目标串中的子串s[i..i+m-1]和模式串t[0..m-1]进行比较，若s[i..i+m-1]=t[0..m-1]，
147. 则称从位置i开始的匹配成功，亦称模式t在目标s中出现；若s[i..i+m-1] ≠t[0..m-1]，，则称从位置i开始的匹配失败。上述的位置i又称为位移，当s[i..i+m-1]=t[0..m-1]时，i称为有效位移；当s[i..i+m-1] ≠t[0..m-1]时，i称为无效位移。这样，串匹配问题可简化为是找出某给定模式T在一给定目标T中首次出现的有效位移。串匹配的算法很多，这里我们只讨论一种最简单的称为朴素的串匹配算法。其基本思想是用一个循环来依次检查n-m+1个合法的位移i(0≦i≦n-m)是否为有效位移， ≠
148. 其算法段为： for(i=0;i<=n-m;i++){ if(S[i..i+m-1]=T[0..m-1] return i; 下面以第二种定长的顺序串类型作为存储结构，给出具体的串匹配算法。 int index(sstring s,sstring t,int pos){ int i,j,k; int m=s.length; int n=t.length; for(i=0;i<=n-m;i++){ j=0;k=i;
149. while(j
150. 链串上的子串定位算法用结点大小为1的单链表做串的存储结构时，实现朴素的匹配算法很简单。只是现在的位移是结点地址而非整数，且单链表中没有存储长度信息。若匹配成功，则返回有效位移所指的结点地址，否则返回空指针。具体算法如下： lstring *lindex(lstring s,lstring t){ lstring *shift,*q,*p; shift=S; q=shift;p=t;
151. while(q && p){ if(q->data==p->data){ q=q->next; p=p->next; } else{ shift=shift->next; q=shift; p=t; } }
152. if(p==null) return shift; else return null; }
153. 第五章数组和广义表5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.3.1 特殊矩阵 5.3.2 稀疏矩阵 5.4 广义表的定义 5.5 广义表的存储结构
154. 数组和广义表可看成是一种特殊的线性表，其特殊在于，表中的数所元素本身也是一种线性表。 5.1 数组的定义数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供使用的数据类型。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。多维数组是向量的推广。例如，二维数组： a11 a12 … a1n a21 a22 … a2n … … … … am1 am2 … amn Amn=
155. 可以看成是由个行向量组成的向量，也可以看成是个列向量组成的向量。在C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型，也就是说， typedef elemtype array2[m][n]; 等价于： typedef elemtype array1[n]; typedef array1 array2[m]; 同理，一个维数组类型可以定义为其数据元素为维数组类型的一维序组类型。数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。
156. 5.2 数组的顺序表示和实现由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。又由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。
157. 通常有两种顺序存储方式： ⑴行优先顺序——将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。以二维数组为例，按行优先顺序存储的线性序列为： a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,amn 在PASCAL、C语言中，数组就是按行优先顺序存储的。 ⑵列优先顺序——将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后，A的m*n个元素按列优先顺序存储的线性序列为： a11,a21,…,am1,a12,a22,…am2,……,an1,an2,…,anm 在FORTRAN语言中，数组就是按列优先顺序存储的。
158. 以上规则可以推广到多维数组的情况：优先顺序可规定为先排最右的下标，从右到左，最后排最左下标：列优先顺序与此相反，先排最左下标，从左向右，最后排最右下标。按上述两种方式顺序存储的序组，只要知道开始结点的存放地址（即基地址），维数和每维的上、下界，以及每个数组元素所占用的单元数，就可以将数组元素的存放地址表示为其下标的线性函数。因此，数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。
159. 例如，二维数组Amn按“行优先顺序”存储在内存中，假设每个元素占用d个存储单元。元素aij的存储地址应是数组的基地址加上排在aij前面的元素所占用的单元数。因为aij位于第i行、第j列，前面i-1行一共有(i-1) ×n个元素，第i行上aij前面又有j-1个元素，故它前面一共有(i-1) ×n+j-1个元素，因此，aij的地址计算函数为： LOC(aij)=LOC(a11)+[(i-1)*n+j-1]*d 同样，三维数组Aijk按“行优先顺序”存储，其地址计算函数为： LOC(aijk)=LOC(a111)+[(i-1)*n*p+(j-1)*p +(k-1)]*d
160. 上述讨论均是假设数组各维的下界是不是1，更一般的二维数组是A[c1..d1,c2..d2]，这里c1,c2不一定是1。aij前一共有i-c1行，二维数组一共有d2-c2+1列，故这i-c1行共有(i-c1)*(d2-c2+1)个元素，第i行上aij前一共有j-c2个元素，因此，aij的地址计算函数为： LOC(aij)=LOC(ac1c2)+[(i-c1)*(d2-c2+1)+j-c2)]*d 例如，在C语言中，数组各维下标的下界是0，因此在C语言中，二维数组的地址计算公式为： LOC(aij)=LOC(a00)+(i*(d2+1)+j)*d
161. 5.3 矩阵的压缩存储在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编制程序时，简单而又自然的方法，就是将一个矩阵描述为一个二维数组。矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单，并且存储的密度为1。但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，看起来存储密度仍为1，但实际上占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费，为了节省存储空间，我们可以对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。
162. 5.3.1特殊矩阵所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特殊矩阵的压缩存储。 1、对称矩阵在一个n阶方阵A中，若元素满足下述性质： aij=aji 0≦i,j≦n-1 则称A为对称矩阵。如图5.1便是一个5阶对称矩阵。对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。不失一般性，我们按“行优先
163. 顺序”存储主对角线（包括对角线）以下的元素，其存储形式如图所示： 1 5 1 3 7 a00 5 0 8 0 0 a10 a 11 1 8 9 2 6 a20 a21 a23 3 0 2 5 1 ……………….. 7 0 6 1 3 an-1 0 a n-1 1 a n-1 2 …a n-1 n-1 图 5.1 对称矩阵在这个下三角矩阵中，第i行恰有i+1个元素，元素总数为： (i+1)=n(n+1)/2 因此，我们可以按图中箭头所指的次序将这些元素存放在一个向量sa[0..n(n+1)/2-1]中。为了便于访问对称矩阵A中的元素，我们必须在aij和sa[k]
164. 之间找一个对应关系。若i≧j，则ai j在下三角形中。 ai j之前的i行（从第0行到第i-1行）一共有1+2+…+i=i(i+1)/2个元素，在第i行上， ai j之前恰有j个元素（即ai0,ai1,ai2,…,aij-1），因此有： k=i*(i+1)/2+j 0≦k
165. 因此，aij的地址可用下列式计算： LOC(aij)=LOC(sa[k]) =LOC(sa[0])+k*d=LOC(sa[0]+[I*(I+1)/2+J]*d 有了上述的下标交换关系，对于任意给定一组下标 (i，j)，均可在sa[k]中找到矩阵元素aij，反之，对所有的k=0,1,2,…n(n-1)/2-1，都能确定sa[k]中的元素在矩阵中的位置(i,j)。由此，称sa[n(n+1)/2]为阶对称矩阵A的压缩存储，见下图： k=0 1 2 3 n(n-1)/2 n(n-1)/2-1 例如a21和a12均存储在 sa[4]中，这是因为 k=I*(I+1)/2+J=2*(2+1)/2+1=4 a00a10a11a20……an-1 0…… an-1,n-1
166. 2、三角矩阵以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵如图所示，它的下三角（不包括主对角线）中的元素均为常数。下三角矩阵正好相反，它的主对角线上方均为常数，如图所示。在大多数情况下，三角矩阵常数为零。 a00 a01 … a 0 n-1 a00 c … c c a11 … a 1 n-1 a10 a11 … c ………………….. …………….. c c … a n-1 n-1 an-1 0 an-1 1 … an-1 n-1 (a)上三角矩阵 (b)下三角矩阵图5.2 三角矩阵
167. 三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到向量sa[0..n(n+1)/2]中，其中c存放在向量的最后一个分量中，上三角矩阵中，主对角线之上的第p行(0≦pj k=
168. 下三角矩阵的存储和对称矩阵类似，sa[k]和aij对应关系是： i(i+1)/2+j i≧j n(n+1)/2 i>j 3、对角矩阵对角矩阵中，所有的非零元素集中在以主对角线为了中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。下图给出了一个三对角矩阵， a00 a01 a10 a11 a12 a21 a22 a23 …. ….. …. 图5.3 对角矩阵 an-2 n-3 an-2 n-2 an-2 n-1 an-1 n-2 an-1 n-1k=
169. 非零元素仅出现在主对角(aii,0≦i≦n-1上，紧邻主对角线上面的那条对角线上(aii+1,0≦i≦n-2)和紧邻主对角线下面的那条对角线上(ai+1 i,0≦i≦n-2)。显然，当∣i-j∣>1时，元素aij=0。由此可知，一个k对角矩阵(k为奇数)A是满足下述条件的矩阵：若∣i-j∣>(k-1)/2 ，则元素 aij=0。对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。
170. 在三对角矩阵里附满足条件i=0，j=0、1，或i=n-1j=n-2、n-1或1
171. LOC(i,j)=LOC(0,0)+[3*i-1+(j-i+1)]*d =LOC(0,0)+(2i+j)*d 上例中，a34对应着sa[10]。 k=2*i+j=2*3+4=10 a21对应着sa[5] k=2*2+1=5 由此，我们称sa[0..3*n-2]是阶三对角带状矩阵A的压缩存储表示。
172. 上述的各种特殊矩阵，其非零元素的分布都是有规律的，因此总能找到一种方法将它们压缩存储到一个向量中，并且一般都能找到矩阵中的元素与该向量的对应关系，通过这个关系，仍能对矩阵的元素进行随机存取。 5.3.2 稀疏矩阵什么是稀疏矩阵？简单说，设矩阵A中有s个非零元素，若s远远小于矩阵元素的总数（即s≦m×n），则称A为稀疏矩阵。
173. 精确点，设在的矩阵A中，有s个非零元素。令 e=s/(m*n)，称e为矩阵的稀疏因子。通常认为e≦0.05时称之为稀疏矩阵。在存储稀疏矩阵时，为了节省存储单元，很自然地想到使用压缩存储方法。但由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须同时记下它所在的行和列的位置（i,j)。反之，一个三元组(i,j,aij)唯一确定了矩阵A的一个非零元。因此，稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。
174. 例如，下列三元组表 ((1,2,12)(1,3,9),(3,1,- 3),(3,6,14),(4,3,24), (5,2,18),(6,1,15),(6,4,-7)) 加上(6,7)这一对行、列值便可作为下列矩阵M的另一种描述。而由上述三元组表的不同表示方法可引出稀疏矩阵不同的压缩存储方法。 0 12 9 0 0 0 0 0 0 -3 0 0 15 0 0 0 0 0 0 0 12 0 0 0 18 0 -3 0 0 0 0 14 0 9 0 0 24 0 0 0 0 24 0 0 0 0 0 0 0 0 0 –7 0 18 0 0 0 0 0 0 0 14 0 0 0 15 0 0 –7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 图5.4 稀疏矩阵M和TM=T=
175. 一、三元组顺序表假设以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方法——三元顺序表。 #define maxsize 10000 typedef int datatype; typedef struct{ int i,j; datatype v; }triple;
176. typedef struct{ triple data[maxsize]; int m,n,t; }tripletable; 设A为tripletable型的结构变量，图5.4中所示的稀疏矩阵的三元组的表示如下： i j v 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7
177. 下面以矩阵的转置为例，说明在这种压缩存储结构上如何实现矩阵的运算。一个m×n的矩阵A，它的转置B是一个n×m的矩阵，且a[i][j]=b[j][i]，0≦i≦m，0≦j≦n，即A的行是B的列，A的列是B的行。将A转置为B，就是将A的三元组表a.data置换为表B的三元组表b.data，如果只是简单地交换a.data中i和j的内容，那么得到的b.data将是一个按列优先顺序存储的稀疏矩阵B，要得到按行优先顺序存储的b.data，就必须重新排列三元组的顺序。由于A的列是B的行，因此，按a.data的列序转置，所得到的转置矩阵B的三元组表b.data必定是按行优先存放的。
178. 按这种方法设计的算法，其基本思想是：对A中的每一列 col(0≦col≦n-1)，通过从头至尾扫描三元表a.data，找出所有列号等于col的那些三元组，将它们的行号和列号互换后依次放入b.data中，即可得到B的按行优先的压缩存储表示。 i j v 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14
179. Void transmatrix(tripletable a,tripletable b) { int p q col; b.m=a.n; b.n=a.m; b.t=a.t; if(b.t<=0) printf(“A=0\n”); q=0;
180. for(col=1;col<=a.n;col++) for(p=0;p<=a.t;p++) if(a.data[p].j==col){ b.data[q].i=a.data[p].j; b.data[q].j=a.data[p].i; b.data[q].v=a.data[p].v; q++; } }
181. 分析这个算法，主要的工作是在p和col的两个循环中完成的，故算法的时间复杂度为O(n*t)，即矩阵的列数和非零元的个数的乘积成正比。而一般传统矩阵的转置算法为： for(col=0;col<=n-1;++col) for(row=0;row<=m;++row) t[col][row]=m[row][col]; 其时间复杂度为O(n*m)。当非零元素的个数t和m*n同数量级时，算法transmatrix的时间复杂度为O(n*n2)。
182. 三元组顺序表虽然节省了存储空间，但时间复杂度比一般矩阵转置的算法还要复杂，同时还有可能增加算是法的难度。因此，此算法仅适用于t<=m*n的情况。下面给出另外一种称之为快速转置的算法，其算法思想为：对A扫描一次，按A第二列提供的列号一次确定位置装入B的一个三元组。具体实施如下：一遍扫描先确定三元组的位置关系，二次扫描由位置关系装入三元组。可见，位置关系是此种算法的关键。
183. 为了预先确定矩阵M中的每一列的第一个非零元素在数组B中应有的位置，需要先求得矩阵M中的每一列中非零元素的个数。因为：矩阵M中第一列的第一个非零元素在数组B中应有的位置等于前一列第一个非零元素的位置加上前列非零元素的个数。为此，需要设置两个一维数组num[0..n]和cpot[0..n] num[0..n]：统计M中每列非零元素的个数，num[col]的值可以由A的第二列求得。
184. cpot[0..n]：由递推关系得出M中的每列第一个非零元素在B中的位置。算法通过cpot数组建立位置对应关系： cpot[1]=1 cpot[col]=cpot[col-1]+num[col-1] 2<=cpl<=a.n 例如：图5.4中的矩阵M和相应的三元组A可以求得num[col]和 cpot[col]的值如下： col 1 2 3 4 5 6 7 num[col] 2 2 2 1 0 1 0 cpot[col] 1 3 5 7 8 8 9
185. 1 2 vq…A i j v第一列元素个数第二列元素个数第三列元素个数numcpotq=cpot[col]2 1 vpp
186. 快速转置算法如下： void fasttranstri(tritupletable b,tritupletable a){ int p,q,col,k; int num[0..a.n],copt[0..a.n]; b.m=a.n; b.n=a.m; b.t=a.t; if(b.t<=0) printf(“a=0”\n); for(col=1;col<=a.u;++col) num[col]=0; for(k=1;k<=a.t;++k) ++num[a.data[k].j];
187. cpot[0]=1; for(col=2;col<=a.t;++col) cpot[col]=cpot[col-1]+num[col-1]; for(p=1;p<=a.t;++p){ col=a.data[p].j; q=cpot[col]; b.data[q].i=a.data[p].j; b.data[q].j=a.data[p].i; b.data[q].v=a.data[p].v; ++cpot[col]; } } }
188. 二、带行表的三元组有时为了方便某些矩阵运算，我们在按行优先存储的三元组中，加入一个行表来记录稀疏矩阵中每行的非零元素在三元组表中的起始位置。当将行表作为三元组表的一个新增属性加以描述时，我们就得到了稀疏矩阵的另一种顺序存储结构：带行表的三元组表。其类型描述如下：
189. #define maxrow 100 typedef struct{ triple data[maxsize]; int rpos[maxrow]; int n,m,t; }rtripletable 下面讨论两个稀疏矩阵相乘的例子，容易看出这种表示方法的优越性。
190. 两个矩阵相乘的经典算法也是大家所熟悉的。若设 Q=M*N 其中，M是m1*n1矩阵，N是m2*n2矩阵。当n1=m2时有： for(i=1;i<=m1;++i) for(j=1;j<=n2;++j){ q[i][j]=0 for(k=1;k<=n1;++k) q[i][j]+=m[i][k]*n[k][j]; } 此算法的复杂度为O(m1*n1*n2)。
191. 当M和N是稀疏矩阵并用三元组表存储结构时，就不能套用上述算法。假设M和N分别为： 0 0 5 0 -1 0 0 2 0 0 0M= 0 2 1 0 -2 4 0 0N=则Q=M*N为： 0 6 -1 0 0 4Q=
192. 它们的三元组、和分别为： i j v i j v i j v 1 1 3 1 2 2 1 2 6 1 4 5 2 1 1 2 1 -1 3 2 -1 3 1 -2 3 2 4 3 1 2 3 2 4 q.data m.data n.data
193. 稀疏矩阵相乘的基本思想是：对于M中每个元素M，找到N 中所有满足条件的元素，求得和的乘积，而从式得知，乘积矩阵Q中每个元素的值是个累加和，这个乘积只是中的一部分。为了便于操作，应对每个元素设一累加和的变量，其初值为零，然后扫描数组M，求得相应元素的乘积并累加到适当的求累计和的变量上。
194. void multsmatrix( rtripletable a, rtripletable b, rtripletable c){ if(a.n!=b.m){ printf(“error\n”); exit(0); } c.m=a.m; c.n=b.n; c.t=0; if(a.t*b.t!=0){ for(arow=1;arow<=a.m;++arow){ ctemp[arow]=0;
195. c.rpos[arow]=c.t+1; for(p=a.rops[arow];p
196. for(ccol=1;ccol<=c.n;++ccol) if(ctemp[ccol]){ if(++c.t>maxsize) exit(0); c.data[c.t]={arow,ccol,ctemp[ccol]}; } } } }
197. 5.4 广义表的定义广义表（Lists，又称列表）是线性表的推广。在第2章中，我们把线性表定义为n>=0个元素a1,a2,a3,…,an的有限序列。线性表的元素仅限于原子项，原子是作为结构上不可分割的成分，它可以是一个数或一个结构，若放松对表元素的这种限制，容许它们具有其自身结构，这样就产生了广义表的概念。广义表是n(n>=0)个元素a1,a2,a3,…,an的有限序列，其中ai或者是原子项，或者是一个广义表。通常记作LS=（a1,a2,a3,…,an)。LS是广义表的名字，n为它的长度。若ai是广义表，则称它为LS的子表。
198. 第六章树和二叉树6.1 树的定义和基本概念 6.2 二叉树 6.2.1 树的定义和基本术语 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构 6.3 遍历二叉树 6.3.1 遍历二叉树 6.3.2 线索二叉树 6.4 树和森林 6.4.1 树的存储结构 6.4.2 森林与二叉树的转换
199. 通常用圆括号将广义表括起来，用逗号分隔其中的元素。为了区别原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。若广义表 LS（n>=1)非空，则a1是LS的表头，其余元素组成的表(a1,a2,…an)称为LS的表尾。显然广义表是递归定义的，这是因为在定义广义表时又用到了广义表的概念。广义表的例子如下：（1）A=（）——A是一个空表，其长度为零。（2）B=（e）——表B只有一个原子e，B的长度为1。（3）C=（a,(b,c,d))——表C的长度为2，两个元素分别为原子a和子表(b,c,d)。（4）D=（A，B，C）——表D的长度为3，三个元素都是广义表。显然，将子表的值代入后，则有
200. D=(( ),(e),(a,(b,c,d)))。（5）E=（E）——这是一个递归的表，它的长度为2， E相当于一个无限的广义表E=(a,(a,(a,(a,…)))). 从上述定义和例子可推出广义表的三个重要结论：（1）广义表的元素可以是子表，而子表的元素还可以是子表，。由此，广义表是一个多层次的结构，可以用图形象地表示。P108 （2）广义表可为其它表所共享。例如在上述例（4）中，广义表A，B，C为D的子表，则在D中可以不必列出子表的值，而是通过子表的名称来引用。（3）广义表的递归性。综上所述，广义表不仅是线性表的推广，也是树的推广。
201. 由表头、表尾的定义可知：任何一个非空广义表其表头可能是广义表，也可能是广义表，而其表尾必定是广义表。 gethead(B)=e gettail(B)=( ) gethead(D)=A gettail(D)=(B,C) 由于（B，C）为非空广义表，则可继续分解得到： gethead(B,C)=B gettail(B,C)=(C) 注意广义表（）和( ( ) )不同。前者是长度为0的空表，对其不能做求表头的和表尾的运算；而后者是长度为1 的非空表（只不过该表中唯一的一个元素是空表）。对其可进行分解，得到表头和表尾均为空表（）。
202. 5.5 广义表的存储结构由于广义表(a1,a2,a3,…an)中的数据元素可以具有不同的结构，（或是原子，或是广义表），因此，难以用顺序存储结构表示，通常采用链式存储结构，每个数据元素可用一个结点表示。由于广义表中有两种数据元素，原子或广义表，因此，需要两种结构的结点：一种是表结点，一种是原子结点。下面介绍两种广义表的链式存储结构。 1、表结点由三个域组成：标志域、指示表头的指针域和指示表尾的指针域；而原子域只需两个域：标志域和值域。表结点原子结点 tag=1 hp tp tag=0 atom
203. 其类型定义如下： typedef enum{ATOM,LIST}elemtag; typedeg struct glnode{ elemtag tag; union{ atomtype atom; struct { struct glnode *hp,*tp; }ptr; }; } *glist; 例见书P109。
204. 2、表结点由三个域组成：标志域、指示表头的指针域和指示表尾的指针域；原子结点的三个域为：标志域、值域和指示表尾的指针域。 tag=1hptp tag=0atomtp表结点原子结点其类型定义如下： typedef enum{atom,list}elemtag; Typedef struct glnode{ elemtag tag; union{ atomtype atom; struct glnode *hp; };
205. struct glnode *tp; } *glist; 例见书P110
206. 第六章树和二叉树6.1 树的定义和基本概念 6.2 二叉树 6.2.1 树的定义和基本术语 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构 6.3 遍历二叉树 6.3.1 遍历二叉树 6.3.2 线索二叉树 6.4 树和森林 6.4.1 树的存储结构 6.4.2 森林与二叉树的转换
207. 6.4.3树和森林的遍历 6.6 赫夫曼树及其应用 6.6.1 最优二叉树（赫夫曼树） 6.6.2 赫夫曼编码
208. 树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界国是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程。等等。 6.1 树的定义和基本术语定义：树(Tree)是n(n>=0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：（1）有且仅有一个特定的称为根(Root)的结点；
209. (2)其余的结点可分为m(m>=0)个互不相交的子集T1,T2,T3…Tm，其中每个子集又是一棵树，并称其为子树(Subtree)。
210. 6.2 二叉树二叉树在树结构的应用中起着非常重要的作用，因为对二叉树的许多操作算法简单，而任何树都可以与二叉树相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。 6.2.1 二叉树的定义定义：二叉树是由n(n>=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。这也是一个递归定义。二叉树可以是空集合，根可以有空的左子树或空的右子树。二查树不是树的特殊情况，它们是两个概念。
211. 二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。图6.8列出二差树的5种基本形态，图6.8(C) 和图6.8（d）是不同的两棵二叉树。 (a) 空二叉树AABABACB (b) 根和空的左右子树 (c) 根和左子树(d) 根和右子树 (e) 根和左右子树图6.8 二叉树的5种形式
212. 6.2.2 二叉树的性质二叉树具有下列重要性质：性质1：在二叉树的第i层上至多有2i-1个结点(i>=1)。采用归纳法证明此性质。当i=1时，只有一个根结点，2i-1=20 =1,命题成立。现在假定多所有的j，1<=j
213. 性质2：深度为k的二叉树至多有2k－1个结点（k>=1). 深度为k的二叉树的最大的结点时为二叉树中每层上的最大结点数之和，由性质1得到每层上的最大结点数，： EkI=1（第i层上的最大结点数）= EkI=12i-1=2k –1 性质3：对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0＝n2＋1。设二叉树中度为1的结点数为n1，二叉树中总结点数为N，因为二叉树中所有结点均小于或等于2，所以有：N＝n0＋n1＋n2 (6-1) 再看二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设B为二叉树中的分支总数，则有：N＝B＋1。
214. 由于这些分支都是由度为1和2的结点射出的，所有有： B＝n1+2*n2 N＝B＋1＝n1＋2×n2＋1 （6－2) 由式（6－1）和（6－2）得到： n0+n1+n2=n1+2*n2+1 n0＝n2＋1 下面介绍两种特殊形态的二叉树：满二叉树和完全二叉树。一棵深度为k且由2k-1个结点的二叉树称为满二叉树。图6.9就是一棵满二叉树，对结点进行了顺序编号。
215. 如果深度为k、由n个结点的二叉树中个结点能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应， 2453671图6.9 满二叉树
216. 12345612345712367(a)完全二叉树(b)非完全二叉树( c)非完全二叉树图6.10 完全二叉树则称这样的二叉树为完全二叉树，图6..10（b）、 c）是2棵非完全二叉树。满二叉树是完全二叉树的特例。
217. 完全二叉树的特点是：（1)所有的叶结点都出现在第k层或k－1层。（2）错任一结点，如果其右子树的最大层次为1，则其左子树的最大层次为1或l＋1。性质4：具有n个结点的完全二叉树的深度为[log2n]＋1。符号【x】表示不大于x的最大整数。假设此二叉树的深度为k，则根据性质2及完全二叉树的定义得到：2k-1－1
218. 性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到第【log2n】+1层，每层从左到右),则对任一结点i（1<=i<=n),有：（1）如果i＝1，则结点i无双亲，是二叉树的根；如果i>1，则其双亲是结点【i/2】。（2）如果2i>n，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i。（3）如果2i＋1>n，则结点i无右孩子；否则，其右孩子是结点2i＋1。
219. [I/2]iI+12i2i+12(I+1)2i+3I+12(I+1)2i+3i2i2i+1图6.11 完全二叉树中结点I和i+1(a)I和i+1结点在同一层 (b)I和i+1结点不在同一层如图6.11所示为完全二叉树上结点及其左右好在结点之间的关系。
220. 在此过程中，可以从（2）和（3）推出（1），所以先证明（2）和（3）。对于i＝1，由完全二叉树的定义，其左孩子是结点2，若2>n，即不存在结点2，此是，结点i无孩子。结点i的由孩子也只能是结点3，若结点3不存在，即3>n，此时结点i无右孩子。对于i>1，可分为两种情况：（1）设第j（1<=j<=[log2n])层的第一个结点的编号为i，由二叉树的性质2和定义知i＝2j-1 结点i的左孩子必定为的j＋1层的第一个结点，其编号为2j＝2×2j-1＝2i。如果2i>n，则无左孩子：
221. 其右孩子必定为第j＋1层的第二个结点，编号为2i＋1。若2i+1>n，则无右孩子。（2）假设第j（1<=j<=[log2n])层上的某个结点编号为i（2e(j-1)<=i<=2ej-1),且2i＋11时，如果i为左孩子，即2×（i/2)=i,则i/2是i的双亲；如果i为右孩子，i＝2p+1,i的双亲应为p，p＝（i－1）/2=[i/2]. 证毕。
222. 6.2.3 二叉树的存储结构 1.顺序存储结构它是用一组连续的存储单元存储二叉树的数据元素。因此，必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，用编号的方法： #define max-tree-size 100 Typedef telemtype sqbitree[max-tree-size]; Sqbitree bt 从树根起，自上层至下层，每层自左至右的给所有结点编号缺点是有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为H且只有H个结点的右单支树确需要2h-1个结点存储空间。而且，若经常需要插入与删除树中结点时，顺序存储方式不是很好！
223. ABCDEFGHIJKL 1 2 3 4 5 6 7 8 9 10 11 12完全二叉树abcdefghijkl
224. ABCDEFGØØØØØ 表示该处没有元素存在仅仅为了好理解ABCDEØØØØFG一般二叉树
225. 顺序存储结构的算法： Status CreateBiTree(BiTree *T) { scanf(&ch); if(ch= =") T=NULL; else{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) exit(OVERFLOW); T–>data=ch; CreateBiTree(T–>lchild); CreateBiTree(T–>rchildd); } return OK; }
226. （2）二叉链表法存储二叉树经常用二叉链表法 A^BC^D^E^F^^G^^H^lchildDatarchild
227. 二叉树的二叉链表存储表示 Typedef struct BiTNode { TelemType data; struct BiTNode *lchild,*rchild; } BiTNode,*BiTree; 有时也可用数组的下标来模拟指针,即开辟三个一维数组Data ,lchild,rchild 分别存储结点的元素及其左,右指针域;
228. 6.3 遍历二叉树和线索二叉树 6.3.1遍历二叉树在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就引入了遍历二叉树的问题，即如何按某条搜索路径巡访树中的每一个结点，使得每一个结点均被访问一次，而且仅被访问一次。遍历对线性结构是容易解决的，而二叉树是非线性的，因而需要寻找一种规律，以便使二叉树上的结点能排列在一个线性队列上，从而便于遍历。 bca(根结点)(右子树)(左子树)由二叉树的递归定义，二叉树的三个基本组成单元是：根结点、左子树和右子树。
229. 假如以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，遍历整个二叉树则有DLR、LDR、LRD、 DRL、RDL、RLD六种遍历方案。若规定先左后右，则只有前三种情况，分别规定为： DLR——先（根）序遍历， LDR——中（根）序遍历， LRD——后（根）序遍历。 1、先序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。 2、中序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；
230. （3）中序遍历右子树。 3、后序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。
231. 例如图（1）所示的二叉树表达式 (a+b*(c-d)-e/f) 若先序遍历此二叉树,按访问结点的先后次序将结点排列起来,其先序序列为： -+a*b-cd/ef 按中序遍历,其中序序列为： a+b*c-d-e/f 按后序遍历,其后序序列为： abcd-*+ef/- 人喜欢中缀形式的算术表达式,对于计算机,使用后缀易于求值图（1）－＋*a/b-dcfe
232. TREENODE *creat_tree() { TREENODE *t; char c; c=getchar(); if(c= =‘#’) return(NULL); else{ t=(TREENODE *)malloc(sizeof(TREENODE)) t – >data=c; t –>lchild=create_tree(); t –>rchild=create –tree(); } return(t); }
233. 中序遍历算法: #include #include #define NULL 0 Typedef struct node{ char data; struct node *lchild,*rchild; }TREENODE; TREENODE *root; TREENODE *creat_tree(); Void inorder(TREENODE *); Void inorder(TREENODE *p) { if(p!=NULL)
234. { inorder(p–>lchild); printf(“%c”,p–>data) inorder(p–>rchild); } }
235. （3）三叉链表其它见书P127 lchilddataparentrchild
236. 线索二叉树：当以二叉链表作为存储结构时,只能找到结点的左右孩子的信息,而不能在结点的任一序列的前驱与后继信息,这种信息只有在遍历的动态过程中才能得到,为了能保存所需的信息,可增加标志域; 其中: 0 lchild 域指示结点的左孩子 ltag={ 1 lchild 域指示结点的前驱 0 rchild 域指示结点的右孩子 rtag={ 1 rchild 域指示结点的后驱以这种结构构成的二叉链表作为二叉树的存储结构,叫做线索链表,其中指向结点前驱与后继的指针叫做线索.加上线索的二叉树称之为线索二叉树 lchildltagdatartagrchild
237. 二叉树的二叉线索存储表示: Typedef enum{Link,Thread}PointerTag; Link= =0:指针,Thread= =1:线索 Typedef struct BiThrNode{ TelemType data; struct BiTreeNode *lchild,*rchild; PointerTag LTag, Rtag; }BiTreeNode,*BiThrTree; 模仿线性表的存储结构,在二叉树的线索链表上也添加一个头结点,令其lchild域的指针指向二叉树的根结点,其rchild域的指针指向中序遍历时访问的最后一个结点;同时,令二叉树中序序列中的第一个结点lchild域指针的和最后一个结点rchild域的指针均指向头结点;就像为二叉树建立了一个双向线索链表, 就好比人在一个圆圈上走路,有可能存在好走的可能性.
238. Status InorderTraverse_Thr(BiThrTree T,status(*visit)(TElemType)){ //T指向头结点,头结点的lchild左链指向根结点 //中序遍历二叉线索树的非递归算法,对每个数据元素调用 //函数Visit P=T–>lchild; while(p!=T){ while(p –>LTag = =Link) p=p –>lchild; if(!visit(p –>data)) return error; while(p –>RTag = =Thread&&p –>rchild!=T) { p=p –>rchild; Visit(p –>data); } p= p–>rchild; } return OK; }//InorderTraverse_Thr
239. P134 : Status InorderThreading(BiThrTree &Thrt,BiThrTree T){ if(!(Thrt =(BiThrTree)malloc(sizeof(BiThrNode)))) exit(OVERFLOW); Thrt –>LTag =Link; Thrt –>RTag =Thread; Thrt –>rchild=Thrt; if(!T) Thrt –>lchild=Thrt; else{ Thrt –>lchild=T; pre=Thrt; InThrTreading(T); pre –>rchild=Thrt; pre –> RTag =Thread; Thrt –>rchild=pre; } return OK; }//InorderThreading
240. Void InThreading(BiThrTree p) { if(p){ InThreading(p –>lchild); if(!p –>lchild) {p –> LRag =Thread; p –>lchild=pre;} if(!pre –>rchild) {pre –>rchild){pre –>RRag =Thread;pre –>rchild=p;} pre=p; InThreading(p –>rchild); } } 在线索树上插入一棵左子树(Ins_lchild)和删除一棵左子(Del_lchild)

清华大学数据结构讲义

landman

贡献于2016-04-08

清华大学数据结构讲义

PPT 内容

PPT 图集

相关PPT