数据结构(C语言描述)课件素材

1、数据结构（C语言描述）课件素材 使用该课件素材注意事项：该课件素材只允许与清华大学出版社出版的、徐孝凯等编著的数据结构（C语言描述）一书配套使用；只限于教师本人备课和用于课堂面授教学；除清华大学出版社和作者本人有权赠送给他人使用外，任何人不得转赠他人使用；不允许直接或间接使用该课件素材出版相应的文字、网络、音像等教材（课件），不允许侵犯作者所享有的著作权和清华大学出版社所享有的版权，违者必究。要求清华大学出版社和作者赠送该课件素材时，要主动提供姓名、单位、联系电话、任课专业、学生人数等信息，以便加强联系和交流；若以后制作有针对此书的好课件，还可以推广使用，甚至正式出版。清华大学出版社和作者只通

2、过电子邮件或当面拷贝提供该课件素材给教师，不允许挂到网络上使用。第一章 绪论 1.1 基本概念数据(data)是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的抽象描述。数据元素(data element)简称元素，它是一个数据整体中相对独立的单位。数据记录(data record)简称记录，它是数据处理领域组织数据的基本单位，数据中的每个数据元素在许多应用场合被组织成记录的结构。数据处理(data processing)是指对数据进行查找、插入、删除、合并、拆分、排序、统计、计算、转换、输入、输出、传送等的操作过程。数据结构(data structure)是指数据以

3、及相互之间的联系。二元组B=(K,R) B代表一种数据结构，它由数据元素的集合K和K上二元关系的集合R所组成。其中 K=ki | 1in, n0 R=rj | 1jm, m0 例1-1 一种数据结构set=(K,R)，其中 K=01,02,03,04,05,06,07,08,09,10 R= 例1-2 一种数据结构linearity=(K,R)，其中 K=01,02,03,04,05,06,07,08,09,10 R=, ,对应的图形如图1-1所示。 图1-1 数据的线性结构示意图 例1-3 一种数据结构tree=(K,R)，其中 K=01,02,03,04,05,06,07,08,09,10

4、 R=, , 对应的图形如图1-2所示。 图1-2 数据的树形结构示意图 例1-4 一种数据结构graph=(K,R)，其中 K=01,02,03,04,05,06,07 R=, , 对应的图形如图1-3所示。 图1-3 数据的图形结构示意图 图1-4 图1-3的等价表示 例1-5 一种数据结构B=(K,R),其中 K=k1,k2,k3,k4,k5,k6 R=r1,r2 r1=, r2=, 若用实线表示关系r1,虚线表示关系r2,则对应的图形如图1-5所示。 图1-5 带有两个关系的一种数据结构示意图 数据类型(data type)是对数据的取值范围、数据元素之间的结构以及允许施加操作的一种综

5、合描述。数组的数据结构可描述如下： array=(A,R)，其中 A=a0 | 0in-1,n1 R= | 0in-2如对于一维数组an，则每个元素ai的存储位置的首字节地址为： Loc(ai)=LOC(a0)+i*L （0in-1） 对于一个二维数组bmn，每一行元素bi的存储位置（即存储该行n个元素的首字节地址）为： LOC(bi)=LOC(b00)+i*RS (0im-1) 对于三维或更高维数组，其每个元素的存储位置的首字节地址也容易计算出来。如对于三维数组cpmn，其相应的一维数组元素、二维数组元素和三维数组元素的存储位置（即首字节地址）的计算公式分别如下： LOC(ck)=(char

6、*)c+k*m*n*L (0kp-1) LOC(cki)=(char*)c+k*m*n*L+i*n*L (0kp-1,0im-1) LOC(ckij)=(char*)c+k*m*n*L+i*n*L+j*L (0kp-1,0im-1,0jn-1) 数据对象(data object)简称对象，它属于一种数据类型中的具体值，可以用常量或变量表示出来。算法(algorithm)就是解决特定问题的方法。描述一个算法可以采用文字叙述，也可以采用传统流程图、N-S图或PAD图等，但要在计算机上实现，则最终必须采用一种程序设计语言进行描述，即编写为程序。作为一个算法应具备以下5个特性：有穷性：一个算法必须在执

7、行有穷步之后结束。确定性：算法中的每一步都必须具有确切的含义，无二义性。可行性：算法中的每一步都必须是可行的，也就是说，每一步都能够通过手工或机器可以接受的有限次操作在有限时间内实现。输入：一个算法可以有0个、1个或多个输入量，在算法被执行之前提供给算法。输出：一个算法执行结束后至少要有一个输出量，它是利用算法对输入量进行运算和处理的结果。 1.2 算法描述 算法就是解决特定问题的方法，该方法可以借助各种工具描述出来。如从n个整数元素中查找出最大值，若用流程图描述则如图1-6所示。 图1-6 求n个元素中的最大值 若采用文字描述，则如下列步骤所示：给n个元素a1an输入数值；把第一个元素a1赋

8、给用于保存最大值元素的变量x；把表示下标的变量i赋初值2；如果ix则将ai赋给x，否则不改变x的值，这使得x始终保存着当前比较过的所有元素的最大值；使下标i增1，以指示下一个元素；转向第（4）步继续执行。 若要使一个算法在计算机上实现，则最终必须采用一种程序设计语言进行描述。如对于上述算法，采用C语言描述如下： /*程序1-1.c*/ #include #define N 8 /*定义N常量为整数8*/ void main(void) int i, x, aN; /*用a0aN-1保存a1aN元素*/ printf(请输入%d个整数：,N); for(i=0; iN; i+) scanf(%d

9、,&ai); x=a0; /*把第一个元素a0的值赋给x*/ i=1; /*把第二个元素a1的下标1赋给i*/while(ix) x=ai; i+; printf(%d个整数中的最大值为：%dn,N,x); 1.3 算法评价 1. 正确性2. 健壮性 3. 可读性 4. 简单性 5. 时间复杂度 时间复杂度（time complexity）又称计算复杂度（computational complexity），它是一个算法运行时间的相对量度。一个算法的运行时间是指在计算机上从开始到结束运行所花费的时间，它大致等于计算机执行一种简单操作(如赋值、比较、计算、转向、返回、输入、输出等)所需的时间与算法

10、中进行简单操作次数的乘积。因为执行一种简单操作所需的时间随机器而异，它是由机器本身硬软件环境决定的，与算法无关，所以我们只讨论影响运行时间的另一个因素算法中进行简单操作的次数。 算法1-1 累加求和 int Sum(int b,int n) int s=0,i; for(i=0;i=n) goto mark2; /n+1次 s+=bi; /n次 i+; /n次 goto mark1; /n次 mark2:return s; 把第2条语句分解后的每一条简单语句的执行次数加起来，就得到了它包含的简单操作的次数，即为4n+2。因此，算法1-1的时间复杂度为： f(n)=4n+4 算法1-2 矩阵相加

11、 void MatrixAdd(int aMSMS, int bMSMS, int cMSMS, int n) /*实现矩阵an,n和bn,n的加法，其和存入cn,n中， MS为大于等于n的常量。*/ int i,j; for(i=0;in;i+) for(j=0;j=n) goto mark4; /n+1次 j=0; /n次 mark2: if (j=n) goto mark3; /n(n+1)次 cij=aij+bij; /n*n次 j+; /n*n次 goto mark2; /n*n次 mark3: i+; /n次 goto mark1; /n次 mark4: ; 把分解后的每一条简单语

12、句的执行次数加起来，就得到了算法1-2所包含的简单操作的次数。因此，算法1-2的时间复杂度为： f(n)=4n2+5n+2 算法1-3 简单选择排序 void SelectSort(int b,int n) int i,j,k,x; for(i=0;in-1;i+) k=i; for(j=i+1;jn;j+) if(bj=n-1) goto mark4; /n次 k=i; /n-1次 j=i+1; /n-1次mark2: if(j=n) goto mark3; /(n-i)=(n+2)(n-1)/2次 /其中i=0,1,.,n-2 if(bjbk) k=j; /(n-i-1)=n(n-1)/2

13、次 /其中i=0,1,.,n-2 j+; /n(n-1)/2次 goto mark2; /n(n-1)/2次 mark3: x=bi; /n-1次 bi=bk; /n-1次 bk=x; /n-1次 i+; /n-1次 goto mark1; /n-1次 mark4: ; 把分解后的每一条简单语句的执行次数加起来，就得到了算法1-3所包含的简单操作的次数。算法1-3的时间复杂度为： f(n)=2n2+7n-7 O(log2n)O(n)O(n*log2n)O(n2)O(n3)O(2n)O(n!) 一个算法的时间复杂度还可以具体分为最好、最差（又称最坏）和平均三种情况讨论。下面结合从一维数组an中顺

14、序查找其值等于给定值key的元素的算法进行说明。 int SequenceSearch(int a, int n, int key) /*若查找成功则返回元素的下标值，否则返回-1*/ int i; for(int i=0; in; i+) if(ai=key) return i; return -1; 6. 空间复杂度第二章 线性表 2.1 线性表的定义和操作 线性表(linear list)是具有相同属性的数据元素的一个有限序列。该序列中所含元素的个数叫做线性表的长度，用n表示，n0。当n=0时，表示线性表是一个空表，即表中不包含任何元素。设序列中第i个元素为ai(1in)，则线性表的一般

15、表示为： (a1,a2,ai,ai+1,an) 其中a1为线性表的第一个元素，又称为表头元素，a2为第二个元素，an为最后一个元素，又称为表尾元素。 一个线性表可以用一个标识符来命名，如用L命名上面的线性表，则 L=(a1,a2,ai,ai+1,an) 线性表中的元素在逻辑上是先后有序的，即第i个元素ai是第i-1个元素ai-1的后继，是第i+1个元素ai+1的前驱，其中第一个元素a1只有后继没有前驱，最后一个元素an只有前驱没有后继。所以线性表是一种线性结构，用二元组表示为： linear_list=(A,R), 其中 A=ai|1in, n0, aiElemType R=|1in-1 对应

16、的逻辑图如图2-1所示。 图2-1 线性表的逻辑结构示意图 (1) 初始化线性表L，即置L为一个空表 void InitList(L) (2) 清除线性表L中的所有元素，使之成为一个空表 void ClearList(L) (3) 返回线性表L的长度，若L为空则返回0 int SizeList(L) (4) 判断线性表L是否为空，若为空则返回1，否则返回0 int EmptyList(L) (5) 返回线性表L中第pos个元素的值，若pos超出范围，则停止程序运行 ElemType GetElem(L,pos) (6) 顺序扫描（即遍历）输出线性表L中的每个元素 void TraverseLi

17、st(L) (7) 从线性表L中查找其值与x相等的元素，若查找成功则返回其位置，否则返回-1 int FindList(L,x) (8) 把线性表L中第pos个元素的值修改为x的值，若修改成功返回1，否则返回0 int UpdatePosList(L,pos,x) (9) 向线性表L的表头插入元素x void InsertFirstList(L,x) (10) 向线性表L的表尾插入元素x void InsertLastList(L,x) (11) 向线性表L中第pos个元素位置插入元素x，若插入成功返回1，否则返回0 int InsertPosList(L,pos,x) (12) 向有序线性表

18、L中插入元素x，使得插入后仍然有序 void InsertOrderList(L,x) (13) 从线性表L中删除表头元素并返回它，若删除失败则停止程序运行 ElemType DeleteFirstList(L) (14) 从线性表L中删除表尾元素并返回它，若删除失败则停止程序运行 ElemType DeleteLastList(L) (15) 从线性表L中删除第pos个元素并返回它，若删除失败则停止程序运行 ElemType DeletePosList(L,pos) (16) 从线性表L中删除值为x的第一个元素，若删除成功返回1否则返回0 int DeleteValueList(L,x) 2

19、.2 线性表的顺序存储结构和操作实现 2.2.1 线性表的顺序存储 在定义一个线性表的顺序存储类型时，需要定义一个数组来存储线性表中的所有元素和定义一个整型变量来存储线性表的长度。假定数组用listMaxSize表示，整型变量用size 表示，则元素类型为ElemType的线性表的顺序存储类型可描述为： ElemType listMaxSize; int size; 为了便于进行线性表的操作，可以把用于存储线性表元素的数组和存储线性表长度的变量同时说明在一个记录类型中，假定该记录类型用List表示，则定义如下： struct List ElemType listMaxSize; int siz

20、e; ; 若要对存储线性表的数组空间采用动态分配，并且其数组长度能够按需要增加，则可以定义出如下的List类型： struct List ElemType *list; /*存线性表元素的动态存储空间的指针*/ int size; /*存线性表长度*/ int MaxSize; /*存list数组长度，亦即所能存储线性表的最大长度*/ ; 当初始化此类型的一个线性表时，要使list指针指向大小为MaxSize的动态数组空间。 2.2.2 顺序存储下的线性表的操作实现 1. 初始化线性表L，即进行动态存储空间分配并置L为一个空表 void InitList(struct List *L,int

21、ms) /*检查ms是否有效，若无效则退出运行*/ if(msMaxSize=ms; /*动态存储空间分配，若分配失败则退出运行*/ L-list=malloc(ms*sizeof(ElemType); if(!L-list) printf(动态存储分配失败!n); exit(1); /*执行此函数则中止程序运行，此函数在stdlib.h中有定义*/ /*初始置线性表为空*/ L-size=0; 2. 清除线性表L中的所有元素，释放动态存储空间，使之成为一个空表 void ClearList(struct List *L) if(L-list!=NULL) free(L-list); /*释放

22、存储空间*/ L-list=0; L-size=L-MaxSize=0; 9. 向线性表L的表头插入元素x 该操作过程分为以下四步： (1) 检查线性表的存储空间是否已被占满，若是则重新分配更大的动态存储空间； (2) 从表尾元素向前至表头元素止，使每一个元素均后移一个存储位置，把下标为0的位置空出，以便插入新元素； (3) 将新元素写入到表头，即下标为0的位置； (4) 修改线性表的长度，使其增1。 用C语言描述如下： void InsertFirstList(struct List *L, ElemType x) int i; if(L-size=L-MaxSize) againMallo

23、c(L); /*调用此函数重新分配更大的存储空间*/ for(i=L-size-1; i=0; i-) L-listi+1=L-listi; L-list0=x; L-size+; 下面给出againMalloc的函数定义： void againMalloc(struct List *L)ElemType *p=realloc(L-list, 2*L-MaxSize*sizeof(ElemType); /*空间扩展为原来的2倍，并由p指针所指向，原内容被 自动拷贝到p所指向的存储空间中*/ if(!p) /*分配失败退出运行*/ printf(存储空间用完!n); exit(1); L-lis

24、t=p; /*使list指向新线性表空间*/ L-MaxSize=2*L-MaxSize; /*把线性表空间大小修改为新的长度*/ 向顺序存储的线性表的表头插入一个元素时，需要移动线性表中的所有元素，所有算法的时间复杂度为O(n)，n表示线性表长度。 11. 向线性表L中第pos个元素位置插入元素x，若插入成功返回1，否则返回0 该操作过程分为以下六步： (1) 检查pos值是否越界，即posn+1是否成立（n为线性表长度），若是则无法插入，表明插入失败，应返回0； (2) 检查线性表的存储空间是否已被占满，若是则重新分配更大的动态存储空间； (3) 从表尾元素向前至下标为pos-1位置的元素

25、止，使每一个元素均后移一个存储位置，把下标为pos-1的位置空出，以便插入新元素； (4) 将新元素写入到第pos个元素位置，即下标为pos-1的位置； (5) 修改线性表的长度，使其增1； (6) 返回1表示插入成功。 算法描述如下： int InsertPosList(struct List *L, int pos, ElemType x) int i; if(posL-size+1) /*若pos越界则插入失败*/ return 0; if(L-size=L-MaxSize) /*重新分配更大的存储空间*/ againMalloc(L);for(i=L-size-1; i=pos-1;

26、i-) L-listi+1=L-listi; L-listpos-1=x; L-size+;return 1; 12. 向有序线性表L中插入元素x，使得插入后仍然有序 有序线性表是指按元素值从小到大顺序排列的线性表，如（23,36,45,49,56,73,80）就是一个有序线性表。向有序线性表中插入一个新元素后要保证仍然是有序的，需要进行的插入过程为： (1) 检查表空间是否用完，若是则分配更大的存储空间； (2) 采用顺序查找的方法查找出x的插入位置； (3) 从表尾到插入位置止，把所有位置上的元素均后移一个位置； (4) 把新元素写入到空出的位置上； (5) 线性表的长度增1。 算法描述为

27、： void InsertOrderList(struct List *L, ElemType x) int i,j; /*若数组空间用完则重新分配更大的存储空间*/ if(L-size=L-MaxSize) againMalloc(L); /*顺序查找出x的插入位置*/for(i=0; isize; i+) if(xlisti) break; /*从表尾到下标i元素依次后移一个位置，把i位置空出*/ for(j=L-size-1; j=i; j-)L-listj+1=L-listj; /*把x值赋给下标为i的元素*/L-listi=x; /*线性表长度增1*/L-size+; 15. 从线性

28、表L中删除第pos个元素并返回它，若删除失败则停止程序运行 删除过程如下： (1) 检查pos的值是否有效，若无效则退出程序运行； (2) 把第pos个元素的值暂时保存起来，以便删除后返回；(3) 从第pos+1个元素位置开始至表尾元素止，依次前移每个元素； (4) 使线性表的长度减1； (5) 返回被暂时保存的原第pos个元素的值。 用C语言描述如下： ElemType DeletePosList(struct List *L, int pos) ElemType temp; int i;if(posL-size) /*pos越界则删除失败*/ printf(pos值越界，不能删除!n);e

29、xit(1); temp=L-listpos-1;for(i=pos; isize; i+) L-listi-1=L-listi; L-size-; return temp; 在这个算法中，运行时间主要花费在第(3)步前移n-pos个元素的操作上。若删除任一位置上元素的概率都相同，即均为1/n，则每次删除一个元素的平均移动元素次数为，所以该算法的时间复杂度为O(n)。 16. 从线性表L中删除值为x的第一个元素，若删除成功返回1否则返回0 int DeleteValueList(struct List *L, ElemType x) int i,j; /*从线性表中顺序查找出值为x的第一个元素

30、*/for(i=0; isize; i+)if(L-listi=x) break; /*若查找失败,表明不存在值为x的元素,应返回0*/if(i=L-size) return 0; /*删除值为x的元素L-listi*/for(j=i+1; jsize; j+) L-listj-1=L-listj; /*线性表长度减1*/L-size-; /*删除成功返回1*/return 1; 2.3 线性表的链接存储 2.3.1 链接存储的概念在链接存储中，每个存储结点不仅含有所存元素本身的信息，而且含有元素之间逻辑关系的信息，其存储结点（简称结点）的结构为： dataP1p2.pm 其中data表示值域

31、，用来存储一个元素，p1,p2,.,pm(m1)均为指针域，每个指针域的值为其对应的后继元素或前驱元素所在结点（以后简称为后继结点或前驱结点）的存储位置。通过结点的指针域（又称为链域）可以访问到对应的后继结点或前驱结点，该后继结点或前驱结点称为指针域（链域）所指向（链接）的结点。若一个结点中的某个指针域不需要指向任何结点，则令它的值为空，用常量NULL表示，NULL在stdio.h中被定义为具有void*类型的整数0。 2.3.2 线性表的链接存储 设一个线性表为： A=(a1,a2,ai,ai+1,an) 若分别用单链表和双链表表示，则对应的存储结构示意图分别如图2-6(a)和(b)所示。

32、图2-6 线性表的链接存储结构示意图 2.3.3 在单链表上的插入和删除操作 (1) 将a结点指针域的值q（即指向后继c结点的指针）赋给b结点的指针域； (2) 将指向b结点的指针（即指针变量s的值）赋给a结点的指针域。 图2-7 在单链表中插入结点的示意图 (1) 将x结点指针域的值q（即指向后继y结点的指针）赋给一个临时指针变量s，以便处理和回收该结点； (2) 将y结点的指针域的值r(即指向后继z结点的指针)赋给x结点的指针域。 图2-8 从单链表中删除结点的示意图 2.3.4 单链表中的结点类型 struct sNode /*定义单链表结点类型*/ ElemType data; str

33、uct sNode* next; ; 单链表中的结点既可以来自静态或动态产生的独立结点(如以上两个程序所示)，也可以来自静态或动态产生的数组中的元素(结点)，若来自数组中的元素，则next域指向的是后继结点所在的下标，所以它应被定义为整数类型。假定用aNode表示数组中结点的类型，则对应的定义如下： struct aNode /*作为单链表结点的数组元素的类型*/ ElemType data; int next; ; 由数组元素构造单链表的所属数组类型可定义为： typedef struct aNode ALinkListMaxSize; 2.3.5 双向链表中的结点类型和插入与删除操作 对于

34、双向链表也可进行以上对单链表那样的类似讨论，若双向链表采用独立结点构成，则结点类型可定义为： struct dNode ElemType data; struct dNode* left; struct dNode* right; ; 若双向链表采用数组中的元素结点构成，则结点类型可定义为： struct adNode ElemType data; int left; int right; ; 其中dNode和adNode为结点类型标识符，该类型包含有三个域：数值域(data)，左指针域(left)和右指针域(right)，left域用于指向前驱结点，right域用于指向后继结点。 设p和q分

35、别是具有dNode*类型的指针变量，若在双向链表中p结点之后插入一个q结点，则需要修改四个指针域的值，操作步骤为： (1) 使p结点的后继结点成为q结点的后继结点； q-right=p-right;(2) 若p结点有后继结点则使q结点成为该结点的前驱结点。 if(p-right) p-right-left=q;(3) 使p结点成为q结点的前驱结点。 q-left=p;(4) 使q结点成为p结点的后继结点。 p-right=q; 插入过程的示意图如图2-10所示，其中图2-10(a)为插入前的状态，图2-10(b)为插入过程中指针链接的情况，每个箭头指针上标出了所对应的操作步骤，图2-10(c)

36、为插入完成后的链接情况。 图2-10 在双向链表中插入结点的示意图 若要删除双向链表中p指针所指向的结点，并假定p结点前后都存在着结点，则只需要修改两个指针，其操作步骤为： (1) 修改p结点的前驱结点的右指针，使之指向p结点的后继结点。 p-left-right=p-right; (2) 修改p结点的后继结点的左指针域，使之指向p结点的前驱结点。 p-right-left=p-left; 删除过程的示意图如图2-11所示，其中图2-11(a)为删除前的状态，图2-11(b)为删除过程中指针链接的情况，图2-11(c)为删除完成后的链接表。 图2-11 在双向链表中删除结点的示意图 2.3.6

37、 带表头附加结点的线性链表 2.3.7 循环链表 2.4 线性表操作在单链表上的实现 5. 返回单链表中第pos个结点中的元素，若pos超出范围，则停止程序运行 要访问单链表中的第pos个结点，必须从表头开始依次访问过该结点之前的所有结点，然后才能够访问到该结点。也就是说，对于单链表，只能一个接着一个结点的顺序存取，而不能够随机访问任意一个结点。 该算法分为以下三步： (1) 检查pos值是否小于1，若是则中止程序运行； (2) 从表头起依次统计扫描得到的每个结点，若扫描到第pos个结点则退出统计； (3) 返回扫描到的第pos个结点的值，或者当不存在第pos个结点时，则退出运行。 ElemT

38、ype GetElem(struct sNode* HL, int pos) int i=0; /*统计已遍历的结点数*/ if(posnext; if(HL!=NULL) return HL-data; else printf(pos值非法，退出运行!n); exit(1); 11. 向单链表中第pos个结点位置插入元素为x的结点，若插入成功返回1，否则返回0 此算法首先需要对pos小于等于0的情况进行处理，接着从单链表中查找出第pos个结点，它由cp指针所指向，而ap指针指向其前驱结点，然后产生一个值为x的新结点，最后把该结点插入到表头（当ap为空时）或其他相应位置。 int Insert

39、PosList(struct sNode* HL, int pos, ElemType x) int i=0; struct sNode *newp;struct sNode* cp=*HL, *ap=NULL; /*对pos值小于等于0的情况进行处理*/if(posnext; /*产生新结点，若分配失败，则停止插入*/ newp=malloc(sizeof(struct sNode); if(newp=NULL) printf(内存动态空间用完，无法插入!n); return 0; /*把x的值赋给新结点的data域*/ newp-data=x; /*把新结点插入到表头*/if(ap=NUL

40、L) newp-next=cp; /*或改为newp-next=*HL*/*HL=newp; /*把新结点插入到ap和cp之间*/else newp-next=cp;ap-next=newp; /*插入成功返回1*/return 1; 12. 向有序单链表中插入元素x结点，使得插入后仍然有序 有序单链表就是结点的值按照链接关系从小到大排列的单链表。此插入过程为： (1) 为新元素动态分配结点并赋值； (2) 若单链表为空或者新元素小于表头结点的值，则应把新元素结点插入到表头并返回； (3) 从表头开始顺序查找新元素的插入位置，在查找过程中必须保留当前结点的前驱结点的指针，以便插入新结点时使用；

41、 (4) 在插入位置上完成插入操作，即把新结点插入到当前结点和其前驱结点之间。 void InsertOrderList(struct sNode* HL, ElemType x) /*把单链表的表头指针赋给cp，把空赋给ap*/struct sNode* cp=*HL, *ap=NULL; /*建立新结点*/ struct sNode *newp; newp=malloc(sizeof(struct sNode); if(newp=NULL) printf(内存动态空间用完，退出运行!n); exit(1);newp-data=x; /*把x的值赋给新结点的data域*/ /*把新结点插入到

42、表头*/if(cp=NULL | xdata) newp-next=cp;*HL=newp;return; /*顺序查找出x结点的插入位置*/ while(cp!=NULL) if(xdata) break; else ap=cp; cp=cp-next; /*把x结点插入到ap和cp之间*/ newp-next=cp;ap-next=newp; 16. 从单链表中删除值为x的第一个结点，若删除成功则返回1否则返回0 此算法首先查找值为x的第一个结点，然后分为表头或非表头结点的不同情况进行不同处理。int DeleteValueList(struct sNode* HL, ElemType x

43、) /*初始化cp和ap指针，使cp指向表头结点，使ap为空*/struct sNode* cp=*HL; struct sNode* ap=NULL; /*从单链表中查找值为x的结点，找到后由cp指向该结点，由ap指向其前驱结点*/while(cp!=NULL) if(cp-data=x) break;ap=cp; cp=cp-next; /*若查找失败，即单链表中不存在值为x的结点,则返回0*/if(cp=NULL) return 0; /*对删除的是表头或非表头分别进行处理*/if(ap=NULL) *HL=(*HL)-next; /*或改为*HL=cp-next*/ else ap-n

44、ext=cp-next; /*回收被删除的结点*/free(cp); /*返回1表示删除成功*/return 1;第三章 稀疏矩阵和广义表 3.1 稀疏矩阵 3.1.1 稀疏矩阵的定义 为了说明什么是稀疏矩阵，首先要知道什么是矩阵。矩阵（matrix）是一个具有m行n列的数表，共包含有mn个数(元素)，每个元素处在确定行和列的交点位置上，都与一对行号和列号唯一对应。当一个矩阵中的行数和列数相同时，即m=n时则称为n阶矩阵或方阵。如图3-1(a)就是一个34的矩阵，它包含3行、4列，具有12个元素，每个元素都对应着唯一的行号和列号，如第1行与第1列交点位置上的元素5对应的行号和列号均为1，第2行

45、与第4列交点位置上的元素9对应的行号和列号分别为2和4。 图3-1 矩阵和稀疏矩阵 稀疏矩阵（sparse matrix）是矩阵中的一种特殊情况，其非零元素的个数远远小于零元素的个数。如图3-1(b)就是一个56的稀疏矩阵，该矩阵中共有30个元素，其中非零元素为7个，占元素总数的7/30。在实际应用中，稀疏矩阵一般都比较大，非零元素所占的比例都比较小。如对于一个100100的稀疏矩阵，若非零元素的个数为200，则非零元素占总元素个数的比例仅为1/50。 2. 稀疏矩阵的三元组线性表表示 在计算机中存储矩阵的一般方法是采用二维数组，其优点是可以随机地访问每一个元素，因而能够较容易地实现矩阵的各种

46、运算，如转置运算、加法运算、乘法运算等。但对于稀疏矩阵来说，采用二维数组的存储方法既浪费大量的存储单元用来存放零元素，又要在运算中花费大量的时间来进行零元素的无效计算，显然是不可取的。一种较好的方法是：只考虑存储占元素中极少数的非零元素。 对于稀疏矩阵中的每个非零元素，可用它所在的行号、列号以及元素值这三元组(i,j,aij)来表示。若把所有的三元组按照行号为主序（即为主关键字）、列号为辅序（即为次关键字，当行号相同时再考虑列号次序）进行排列，则就构成了一个表示稀疏矩阵的三元组线性表。图3-1(b)稀疏矩阵所对应的三元组线性表表示为： (1,1,3),(1,4,5),(2,3,-2),(3,1

47、,1),(3,3,4),(3,5,6),(5,3,-1) 稀疏矩阵采用三元组线性表表示后，可以使用顺序或链接方式存储，从而比采用二维数组存储要大大地节省存储空间。 3. 稀疏矩阵的运算概述 对稀疏矩阵的运算与对一般用二维数组所表示的矩阵的运算相同，通常为求一个稀疏矩阵的转置，计算两个矩阵的和，计算两个矩阵的乘积等。一个矩阵的转置结果仍是一个矩阵，该矩阵中的第i行与第j列交点位置上的元素等于被转置矩阵中第j行与第i列交点位置上的元素。两个矩阵的和仍然是一个矩阵，该矩阵中的第i行第j列位置上的元素等于两个相加矩阵中对应位置上的元素之和。两个相乘矩阵的乘积仍然是一个矩阵，该矩阵中的第i行第j列位置上

48、的元素等于第一个乘数矩阵中的第i行与第二个乘数矩阵中的第j列上对应元素乘积之累加和。假定第一个乘数矩阵为Amn，第二个乘数矩阵为Bnp，乘积结果矩阵为Cmp，则C中任一元素Cij等于，其中1im，1jp。 下面给出对稀疏矩阵的一些典型运算(操作)，假定用M表示一个采用三元组线性表存储的稀疏矩阵，其存储类型用标识符Matrix表示。 (1) 初始化稀疏矩阵M，使它成为不含任何元素的空矩阵 void InitMatrix(Matrix M) (2) 根据稀疏矩阵的三元组线性表建立稀疏矩阵的存储结构 void InlutMatrix(Matrix M) (3) 按照一定格式输出稀疏矩阵 void O

49、utputMatrix(Matrix M) (4) 返回稀疏矩阵M的转置矩阵 Matrix TransposedMatrix(Matrix M) (5) 返回稀疏矩阵M1和M2之和，要求两个矩阵的行、列数均分别相同 Matrix AddMatrix(Matrix M1, Matrix M2) (6) 返回稀疏矩阵M1和M2之乘积，要求M1的列数等于M2的行数 Matrix MultiplyMatrix(Matrix M1, Matrix M2) 3.1.2 稀疏矩阵的存储结构 1. 顺序存储 稀疏矩阵的顺序存储就是对其相应的三元组线性表进行顺序存储。假定每个非零元素的三元组用如下记录结构定义：

50、 struct Triple int row, col; ElemType val; ; 其中row和col用来分别存储元素的行号和列号，val用来存储元素值。 一个稀疏矩阵的顺序存储类型定义如下： struct SMatrix int m, n, t; struct Triple smMaxTerms+1; ; 其中m,n和t域分别用来存储稀疏矩阵的行数、列数和非零元素的个数，sm数组域用来顺序存储每个三元组元素，假定下标为0的元素sm0不用，从下标为1起使用。MaxTerms为一个事先定义的全局常量，其值要大于等于非零元素的个数t，由它决定sm数组的大小。例如，若用SMatrix类型的对象

51、存储图3-1(b)所示的稀疏矩阵，则m,n和t域的值应分别为5,6和7，sm数组中的内容如图3-2所示。 下标 row col val 1 1 3 1 4 5 2 3-2 3 1 1 3 3 4 3 5 6 5 3-1 1 2 3 4 5 6 7 MaxTerms 图3-2 稀疏矩阵的顺序存储结构 2. 链接存储 稀疏矩阵的链接存储就是对其相应的三元组线性表进行链接存储。下面介绍两种链接存储方法。带行指针向量的链接存储在这种链接存储中，需要把具有相同行号的三元组结点按照列号从小到大的顺序链接成一个单链表，每个三元组结点的类型可定义为： struct TripleNode int row, co

52、l; /*存储行号和列号*/ ElemType val; /*存储元素值*/ struct TripleNode* next; /*指向同一行的下一个结点*/ ; 稀疏矩阵中的每一行对应一个单链表，每一个单链表都有一个表头指针，为了把它们保存起来，便于访问每一个单链表，需要使用一个行指针向量（即一维数组），该向量中的第i个分量（即对应数组中下标为i的元素）用来存储稀疏矩阵中第i行所对应的单链表的表头指针。带行指针向量的链接存储类型定义如下： struct LMatrix int m, n, t; struct TripleNode* lmMaxRows+1; ; 其中，m、n和t分别用来保存稀

53、疏矩阵的行数、列数和非零元素的个数，lm向量用来存储m个行单链表的表头指针，第i行单链表的表头指针存于第i分量lmi中，而第0分量lm0未用，MaxRows为全局变量，其值要大于等于所存储矩阵的行数。 例如，若利用LMatrix类型的对象存储图3-1(b)所示的稀疏矩阵，则链接存储结构如图3-3所示，其中每个单链表中的结点由动态分配链接而成。 图3-3 带行指针向量的链接存储结构 3.1.3 稀疏矩阵的运算 1. 初始化运算 稀疏矩阵的存储类型不同，其初始化过程也不同，对于SMatrix类型的对象，初始化过程为： void InitMatrix1(struct SMatrix* M) M-m=

54、0; M-n=0; M-t=0; 对于LMatrix类型的对象，其初始化如下： void InitMatrix2(struct LMatrix* M) int i;M-m=0; M-n=0; M-t=0; for(i=1; ilmi=NULL; 对于CLMatrix类型的对象，初始化过程为： void InitMatrix3(struct CLMatrix* M) int i;M-m=0; M-n=0; M-t=0; for(i=1; irmi=NULL; for(i=1; icmi=NULL; 2. 稀疏矩阵的建立 稀疏矩阵的建立假定采用键盘输入，输入时应按照对应三元组线性表中三元组排列的次

55、序进行，可以每行输入一个三元组，行号、列号和元素值之间用空格分开，最后以按下回车键结束，当输入完所有三元组后，以输入一个特殊的三元组(0,0,0)结束整个输入过程。若稀疏矩阵采用SMatrix类型存储，则相应的输入算法为： void InputMatrix1(struct SMatrix* M, int m, int n) /*m和n分别表示稀疏矩阵的行数和列数*/ int k=0; int row, col;ElemType val; M-m=m; M-n=n; printf(输入每个三元组:n);scanf(%d %d %d,&row,&col,&val); while(row!=0) k

56、+; M-smk.row=row; M-smk.col=col; M-smk.val=val; scanf(%d %d %d,&row,&col,&val); M-t=k; 若稀疏矩阵采用十字链接存储，则相应的输入算法如下： void InputMatrix3(struct CLMatrix* M, int m, int n) int k=0; int row, col;ElemType val; M-m=m; M-n=n; printf(输入每个三元组:n);scanf(%d %d %d,&row,&col,&val); while(row!=0) struct CrossNode *cp,

57、 *newp; k+; /*得到和建立一个新结点*/ newp=malloc(sizeof(struct CrossNode); newp-row=row; newp-col=col; newp-val=val; newp-right=newp-down=NULL; /*把新结点链接到所在行单链表的末尾*/ cp=M-rmrow; if(cp=NULL) M-rmrow=newp; else while(cp-right!=NULL) cp=cp-right; cp-right=newp; /*把新结点链接到所在列单链表的末尾*/ cp=M-cmcol; if(cp=NULL) M-cmcol

58、=newp; else while(cp-down!=NULL) cp=cp-down; cp-down=newp; /*输入下一个三元组*/ scanf(%d %d %d,&row,&col,&val); M-t=k; 3.2 广义表 广义表的定义 广义表（generalized list）简称表，它是线性表的推广。一个广义表是n(n0)个元素的一个序列，当n=0时则称为空表。在一个非空的广义表中，其元素可以是某一确定类型的对象(这种元素被称做单元素)，也可以是由单元素构成的表(这种元素可相对地被称做子表或表元素)。显然，广义表的定义是递归的，广义表是一种递归的数据结构。 设ai为广义表的第

59、i个元素，则广义表的一般表示与线性表相同： (a1,a2,ai,ai+1,an) 其中n表示广义表的长度，即广义表中所含元素的个数，n0。 同线性表一样，也可以用一个标识符来命名一个广义表，如用LS命名上面的广义表，则为： LS=(a1,a2,ai,ai+1,an) 在广义表的讨论中，为了把单元素同表元素区别开来，一般用小写字母表示单元素，用大写字母表示表，如： A=( ) B=(e) C=(a,(b,c,d) D=(A,B,C)=(),(e),(a,(b,c,d) E=(a,(a,b),(a,b),c) 其中A是一个空表，其长度为0；B是一个只含有单元素e的表，其长度为1；C中有两个元素，一

60、个是单元素a，另一个是表元素(b,c,d)，C的长度为2；D中有三个元素，其中每个元素又都是一个表，D的长度为3；E中只含有一个元素，该元素是一个表，该表中包含有三个元素，其中后两个元素又都是表。 把每个表的名字（若有的话）写在其表的前面也是一种表示广义表的方法，对于上面的五个广义表可相应地表示为： A( ) B(e) C(a,(b,c,d) D(A( ),B(e),C(a,(b,c,d) E(a,(a,b),(a,b),c) 若用圆圈和方框分别表示表（表元素）和单元素，并用线段把表和它的元素（元素结点应在其表结点的下方）连接起来，则可得到一个广义表的图形表示。如上面五个广义表的图形表示如图3