数据结构（C语言描述）课件素材

数据结构（C语言描述）课件素材 使用该课件素材注意事项：1. 该课件素材只允许与清华大学出版社出版的、徐孝凯等编著的数据结构（C语言描述）一书配套使用；2. 只限于教师本人备课和用于课堂面授教学；3. 除清华大学出版社和作者本人有权赠送给他人使用外，任何人不得转赠他人使用；4. 不允许直接或间接使用该课件素材出版相应的文字、网络、音像等教材（课件），不允许侵犯作者所享有的著作权和清华大学出版社所享有的版权，违者必究。5. 要求清华大学出版社和作者赠送该课件素材时，要主动提供姓名、单位、联系电话、任课专业、学生人数等信息，以便加强联系和交流；若以后制作有针对此书的好课件，还可以推广使用，甚至正式出版。6. 清华大学出版社和作者只通过电子邮件或当面拷贝提供该课件素材给教师，不允许挂到网络上使用。第一章 绪论 1.1 基本概念数据(data)是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的抽象描述。数据元素(data element)简称元素，它是一个数据整体中相对独立的单位。数据记录(data record)简称记录，它是数据处理领域组织数据的基本单位，数据中的每个数据元素在许多应用场合被组织成记录的结构。数据处理(data processing)是指对数据进行查找、插入、删除、合并、拆分、排序、统计、计算、转换、输入、输出、传送等的操作过程。数据结构(data structure)是指数据以及相互之间的联系。二元组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 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)是对数据的取值范围、数据元素之间的结构以及允许施加操作的一种综合描述。数组的数据结构可描述如下： 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*)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个特性：有穷性：一个算法必须在执行有穷步之后结束。确定性：算法中的每一步都必须具有确切的含义，无二义性。可行性：算法中的每一步都必须是可行的，也就是说，每一步都能够通过手工或机器可以接受的有限次操作在有限时间内实现。输入：一个算法可以有0个、1个或多个输入量，在算法被执行之前提供给算法。输出：一个算法执行结束后至少要有一个输出量，它是利用算法对输入量进行运算和处理的结果。 1.2 算法描述 算法就是解决特定问题的方法，该方法可以借助各种工具描述出来。如从n个整数元素中查找出最大值，若用流程图描述则如图1-6所示。 图1-6 求n个元素中的最大值 若采用文字描述，则如下列步骤所示：（1） 给n个元素a1an输入数值；（2） 把第一个元素a1赋给用于保存最大值元素的变量x；（3） 把表示下标的变量i赋初值2；（4） 如果ix则将ai赋给x，否则不改变x的值，这使得x始终保存着当前比较过的所有元素的最大值；（6） 使下标i增1，以指示下一个元素；（7） 转向第（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,&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），它是一个算法运行时间的相对量度。一个算法的运行时间是指在计算机上从开始到结束运行所花费的时间，它大致等于计算机执行一种简单操作(如赋值、比较、计算、转向、返回、输入、输出等)所需的时间与算法中进行简单操作次数的乘积。因为执行一种简单操作所需的时间随机器而异，它是由机器本身硬软件环境决定的，与算法无关，所以我们只讨论影响运行时间的另一个因素算法中进行简单操作的次数。 算法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 矩阵相加 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: ; 把分解后的每一条简单语句的执行次数加起来，就得到了算法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次 /其中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中顺序查找其值等于给定值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)，则线性表的一般表示为： (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 对应的逻辑图如图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 TraverseList(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) 向有序线性表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.2 线性表的顺序存储结构和操作实现 2.2.1 线性表的顺序存储 在定义一个线性表的顺序存储类型时，需要定义一个数组来存储线性表中的所有元素和定义一个整型变量来存储线性表的长度。假定数组用listMaxSize表示，整型变量用size 表示，则元素类型为ElemType的线性表的顺序存储类型可描述为： ElemType listMaxSize; int size; 为了便于进行线性表的操作，可以把用于存储线性表元素的数组和存储线性表长度的变量同时说明在一个记录类型中，假定该记录类型用List表示，则定义如下： struct List ElemType listMaxSize; int size; ; 若要对存储线性表的数组空间采用动态分配，并且其数组长度能够按需要增加，则可以定义出如下的List类型： struct List ElemType *list; /*存线性表元素的动态存储空间的指针*/ int size; /*存线性表长度*/ int MaxSize; /*存list数组长度，亦即所能存储线性表的最大长度*/ ; 当初始化此类型的一个线性表时，要使list指针指向大小为MaxSize的动态数组空间。 2.2.2 顺序存储下的线性表的操作实现 1. 初始化线性表L，即进行动态存储空间分配并置L为一个空表 void InitList(struct List *L,int 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); /*释放存储空间*/ 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) againMalloc(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-list=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位置的元素止，使每一个元素均后移一个存储位置，把下标为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; 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。 算法描述为： 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. 从线性表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);exit(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的第一个元素*/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表示值域，用来存储一个元素，p1,p2,.,pm(m1)均为指针域，每个指针域的值为其对应的后继元素或前驱元素所在结点（以后简称为后继结点或前驱结点）的存储位置。通过结点的指针域（又称为链域）可以访问到对应的后继结点或前驱结点，该后继结点或前驱结点称为指针域（链域）所指向（链接）的结点。若一个结点中的某个指针域不需要指向任何结点，则令它的值为空，用常量NULL表示，NULL在stdio.h中被定义为具有void*类型的整数0。 2.3.2 线性表的链接存储 设一个线性表为： A=(a1,a2,ai,ai+1,an) 若分别用单链表和双链表表示，则对应的存储结构示意图分别如图2-6(a)和(b)所示。 图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; struct sNode* next; ; 单链表中的结点既可以来自静态或动态产生的独立结点(如以上两个程序所示)，也可以来自静态或动态产生的数组中的元素(结点)，若来自数组中的元素，则next域指向的是后继结点所在的下标，所以它应被定义为整数类型。假定用aNode表示数组中结点的类型，则对应的定义如下： struct aNode /*作为单链表结点的数组元素的类型*/ ElemType data; int next; ; 由数组元素构造单链表的所属数组类型可定义为： typedef struct aNode ALinkListMaxSize; 2.3.5 双向链表中的结点类型和插入与删除操作 对于双向链表也可进行以上对单链表那样的类似讨论，若双向链表采用独立结点构成，则结点类型可定义为： 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分别是具有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)为插入完成后的链接情况。 图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 带表头附加结点的线性链表 2.3.7 循环链表 2.4 线性表操作在单链表上的实现 5. 返回单链表中第pos个结点中的元素，若pos超出范围，则停止程序运行 要访问单链表中的第pos个结点，必须从表头开始依次访问过该结点之前的所有结点，然后才能够访问到该结点。也就是说，对于单链表，只能一个接着一个结点的顺序存取，而不能够随机访问任意一个结点。 该算法分为以下三步： (1) 检查pos值是否小于1，若是则中止程序运行； (2) 从表头起依次统计扫描得到的每个结点，若扫描到第pos个结点则退出统计； (3) 返回扫描到的第pos个结点的值，或者当不存在第pos个结点时，则退出运行。 ElemType 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 InsertPosList(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=NULL) 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) 从表头开始顺序查找新元素的插入位置，在查找过程中必须保留当前结点的前驱结点的指针，以便插入新结点时使用； (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域*/ /*把新结点插入到表头*/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) /*初始化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*/ e