C语言程序设计ppt-第10章-02

1、C语言程序设计The C Programming Language华中科技大学计算机学院曹计昌7/23/20221华中科技大学计算机学院*10.7 联 合 10.7.1 联合类型的定义 与结构类似，联合类型也是一种构造类型。一个联合类型中包含有多个成员，这些成员共享共同的存储区域，但这些成员并不同时存在;联合存储区域的大小由各个成员中所占字节数最大的成员决定;在任何时刻，各个成员中只能有一个成员拥有该存储。 除了用关键字union取代struct之外，联合类型的定义、联合变量的声明、以及联合成员的引用在语法上与结构完全相同。 7/23/20222华中科技大学计算机学院如果有3个不同数据类型（c

2、har, short, long ）的变量要分时共用一个共同的存储区域，则可以定义如下的联合类型： union chlcharc;shorth;longl;这里chl是所定义的联合类型的联合名（tag） , 它与union一起形成一个union chl的联合类型。c、h、l是联合类型的成员。 7/23/20223华中科技大学计算机学院10.7.2 联合变量的声明、初始化及联合成员的引用 定义了union chl的联合类型后，可以通过：union chl u;来声明一个union chl类型的变量。也可以在定义union chl联合类型的同时来声明相应的联合变量。如：union chlchar

3、c;short h;long l;v=9;它在定义union chl联合类型的同时声明了联合类型的变量v，并且对其进行了初始化。在不产生二义的情况下，往往简称联合类型的变量为联合。7/23/20224华中科技大学计算机学院联合变量的声明、初始化值得注意的是，联合变量的初始化与结构的初始化在形式上相同，都应该用花括号界定初值，但联合是一种特殊形式的构造类型的数据，在同一时刻它只拥有其中的一个成员。因此，初始化时只能对联合的第1个成员进行初始化。换言之，初值表中只能包含与第1个成员数据类型相同的一个初值。如上面例子中的v=9。也可以：union chl v=9,w=a;7/23/20225华中科技

4、大学计算机学院例10.12 通过例子对联合的特性进行进一步分析。#include stdio.hunion chl charc; shorth; longl;void show(union chl *pu);void show_memoy(union chl *pu); 7/23/20226华中科技大学计算机学院void main(void) union chl u; printf(size of u is %dn,sizeof(u); u.l=0 x31323334L; show(&u); show_memoy(&u); u.h=0 x3638; show(&u); show_memoy(&

5、u);7/23/20227华中科技大学计算机学院void show(union chl *pu) printf(char format: %cn,(*pu).c); printf(int format: %hxn,pu-h); printf(long format: %lxn,(*pu).l);void show_memoy(union chl *pu) char *p=(char *)pu; int i=0; while(i”操作符来引用联合成员。从u.l，(*pu).c，pu-h三个表达式中可以归纳出对联合成员的引用形式为：（1）联合变量名.成员名。（2）(*指向联合变量的指针).成员名。

6、（3）指向联合变量的指针-成员名。例如：u.c 或(*pu).c 或pu-c 都表示引用联合成员c，类型是char。u.h 或(*pu).h 或pu-h 都表示引用联合成员h，类型是short。u.l 或(*pu).l 或pu-l 都表示引用联合成员c，类型是long。而u.c=a，(*pu).h=0 x3839，以及pu-l=0 x31323334L分别表示对联合u的成员c、h、l的赋值操作。 7/23/202212华中科技大学计算机学院4) 共享存储的特点在main函数中，u.l=0 x31323334L;赋值语句产生的存储可由表10-3描述，各字节的地址由高向低，依次存放0 x31、0

7、x32、0 x33、0 x34，联合u由成员l使用。由show函数和相应的运行结果可以看出，此时如果按照(*pu).c解释，输出的只是共享存储的低字节的内容0 x34或字符4。如果按照,pu-h解释，输出的只是共享存储的低端2个字节的内容0 x33和0 x34。执行u.h=0 x3638;语句之后，联合u由成员h使用。该语句修改了共享存储低端2个字节的内容，但是高端2个字节的内容没有变化。 7/23/202213华中科技大学计算机学院5) 相容性操作联合中允许存储不同类型的数据，对某个时刻存储的数据，其所允许的操作也有所不同，有些操作对该类型的数据是相容的，但有些操作却不相容（得不到正确结果）

8、。由于语法上合法，编译器对这种情况不会报错，但运算的结果却不正确。假如在union chl中增加一个成员（其它都不变），如：float f;则在show函数中，如果执行语句为：printf(float format: %fn,pu-f);则得到是不正确的结果0.00，而其他语句中操作却是相容的。 7/23/202214华中科技大学计算机学院*10.8 字段结构由多个相邻的二进制位可以组成结构或者联合中的整型或无符号整型成员，这些个相邻的二进制位被称为字段（bit field），对应的成员称为结构或联合的字段成员，以字段为成员的结构称为字段结构。组成字段的二进制位的数目成为该字段的宽度，它是一个

9、非负的整型常量表达式。字段结构在操作系统，编译程序，嵌入式系统的C语言编程方面使用较多。例如，stdio.h中关于文件状态成员flags的取值就规定了1为读状态，2为写状态，4为缓冲数据状态等等。这些数据都是一些值很小的整数，没有必要用int或char变量来存储每一个值。通常对若干个特征中的每个特征按照取值的大小分配合适的二进制位，然后将它们组织成为字段封装到一个int或char变量中。这样就可以通过字段名对相应的二进制位或位串进行操作，而不必采用前面章节介绍的位运算。 7/23/202215华中科技大学计算机学院10.8.1 字段结构类型的定义字段结构也属于构造类型，因此要先定义字段结构类型

10、，再声明字段结构变量，然后再对字段结构变量中的成员进行操作。考虑十字路口的交通灯 .颜色枚举类型的声明如下：enum color OFF=0,RED=1,YELLOW=2,GREEN=3; 7/23/202216华中科技大学计算机学院struct traffic_lightunsigned short int east:2;/* 东组灯状态字段 */unsigned short int south:2;/* 南组灯状态字段 */unsigned short int west:2;/* 西组灯状态字段 */unsigned short int north:2;/* 北组灯状态字段 */unsig

11、ned short int reserve:8; /* 保留字段 */unsigned short int east_on:4; /* 东组灯开通时间 */unsigned short int south_on:4;/* 南组灯开通时间 */unsigned short int west_on:4;/* 西组灯开通时间 */unsigned short int north_on:4;/* 北组灯开通时间 */; 4组交通灯的字段结构类型的声明7/23/202217华中科技大学计算机学院4组交通灯的字段结构类型的简略形式声明 struct traffic_lightunsigned short

12、int east:2,south:2,west:2,north:2,reserve:8;unsigned short int east_on:4,south_on:4,west_on:4,north_on:4;上面声明了一个struct traffic_light的字段结构类型，east、south、north_on为它的字段成员，字段成员往往也简称为字段。冒号后面的整数说明了成员的字段宽度，字段宽度是一个非负的整型常量表达式。上面定义中，其中字段宽度为2的四个成员用unsigned char更加简练，但Turbo C中不支持unsigned char，因此用unsigned short in

13、t。7/23/202218华中科技大学计算机学院10.8.2 字段结构类型变量的声明及成员的引用 可以先定义字段结构类型，再声明字段结构类型的变量。如：struct traffic_light Jiedaokou;它声明了struct traffic_light的字段结构类型变量Jiedaokou。同时，还可以在声明字段结构类型的变量的同时对其进行初始化。如：struct traffic_light Jiedaokou=0,0,0,0,0,0,0,0,0;它将east、north_on这9个字段成员都初始化为0。 7/23/202219华中科技大学计算机学院也可以在定义字段结构类型的同时声明字

14、段结构变量并对其成员进行初始化。如： struct traffic_lightunsigned short int east:2,south:2,west:2,north:2,reserve:8;unsigned short int east_on:4,south_on:4,west_on:4,north_on:4; Jiedaokou=0,0,0,0,0,0,0,0,0,*p=&Jiedaokou;字段就是一个小整数，它可以出现在其它整数可以出现的任何地方。字段在参与运算时被自动转换为int或unsigned int类型的整数。对一个字段结构中成员的引用与对一般结构变量中结构成员的引用方法相

15、同，有“.”和“-”两种。如：Jiedaokou.west，Jiedaokou.west_on，p-north，p-north_on等。 7/23/202220华中科技大学计算机学院例10.13 字段结构变量的成员引用举例。 void main(void)struct traffic_light Jiedaokou=0,0,0,0,0,0,0,0,0;Jiedaokou.west=GREEN;Jiedaokou.west_on=5;printf(Jiedaokou.west=%ut,Jiedaokou.west);printf(Jiedaokou.west_on=%un,Jiedaokou.w

16、est_on);printf(Jiedaokou.east=%ut,Jiedaokou.east);printf(Jiedaokou.east_on=%un,Jiedaokou.east_on);程序的运行结果如下：Jiedaokou.west=3 Jiedaokou.west_on=5Jiedaokou.east=0 Jiedaokou.east_on=0 7/23/202221华中科技大学计算机学院字段成员的宽度问题由于字段成员表示整数的范围有限，在对字段成员赋值时不要超出了它表示数的范围。如果超出了它表示数的范围，则数的高位部分将被丢弃。如Jiedaokou.west_on的宽度为4，它

17、能够表示数的范围是015。如果执行Jiedaokou.west_on=17（即0 x11 或00010001B），编译时不会报错，如果再执行：printf(Jiedaokou.west_on=%un,Jiedaokou.west_on);其输出为1。高位“1”被丢弃。 7/23/202222华中科技大学计算机学院可以通过指向字段结构变量的指针来操纵字段结构变量的成员。 如:struct traffic_light Jiedaokou=0,0,0,0,0,0,0,0,0,*p=&Jiedaokou;它声明了一个struct traffic_light类型的字段结构指针p，并且使p指向了字段结构变

18、量Jiedaokou。而p-north=RED;p-north_on=6;分别表示通过指针p引用Jiedaokou的成员north和north_on，并通过赋值操作对这些成员进行赋值。下面的语句则是输出相应的结果：printf(Jiedaokou.north=%ut,p-north);printf(Jiedaokou.north_on=%un,p-north_on);7/23/202223华中科技大学计算机学院10.8.3 字段结构与联合的应用本节通过一个例子说明如何访问一个16位字中的高低字节和各二进制位。例子中将字段byte0和byte1的宽度定义为8，用以表示一个16位字中的高字节和低字

19、节;将字段b0b15宽度定义为1，用以表示一个16位字中的各个二进制位。并且用联合使一个短整型变量、2个字节字段与16个位字段共享共同的存储。 7/23/202224华中科技大学计算机学院例10.14 用字段和联合访问一个16位字中的高低字节和各二进制位的应用举例。#include stdio.h#define CHAR_BIT 8struct w16_bytes unsigned short byte0:8,byte1:8; /* byte0为低字节,byte1为高字节 */ ;struct w16_bits unsigned short b0:1,b1:1,b2:1,b3:1,b4:1,b

20、5:1,b6:1,b7:1, b8:1,b9:1,b10:1,b11:1,b12:1,b13:1,b14:1,b15:1; ;7/23/202225华中科技大学计算机学院union w16 /* 短整型变量、结构成员byte、结构成员bit共享共同的存储 */ shorti; struct w16_bytesbyte; struct w16_bitsbit; ;void main(void) union w16w=0;/* i为0；byte0和byte1也为0；b0至b15皆为0 */ void bit_print(short); w.bit.b9=1; /* 相当于byte1为2 */ w.

21、bit.b10=1; /* 相当于byte1为6 */ w.byte.byte0=b; printf(w.i=0 x%xn,w.i); /* 按整型解释、输出共享存储的内容 */ bit_print(w.i); /* 从高到低，逐位输出共享存储的各bit值 */ 7/23/202226华中科技大学计算机学院void bit_print(short num) int i,shift=sizeof(short)*CHAR_BIT; int mask=1(shift-1); /* 掩码mask的最高位为1，其余15位为0* / for(i=1;i=shift;i+) putchar(num & ma

22、sk) = 0)? 0: 1); /* num最高位为1，输出1 */ num=1; /* num左移1位；等价于：num = num1 */ if(i%CHAR_BIT=0 & ishift) /* 每输出8位后，输出空格 */ putchar( ); putchar(n); 7/23/202227华中科技大学计算机学院程序中mask最高位为1，其余15位为0，通常称为掩码，将它与短整型变量作按位与运算用以测试短整型变量的最高位是0还是1。在bit_print函数中的for循环中，每循环一次，通过num=1将次高位移至最高位。w.bit.b9=1和w.bit.b10=1将i的高字节设成6，w

23、.byte.byte0=b将i的低字节设成62（b的ASCII码）。bit_print函数将num在内存中的值以二进制位的方式输出。程序的运行结果如下：w.i=0 x66200000110 01100010 7/23/202228华中科技大学计算机学院*10.9 动态存储分配 10.9.1 静态数据结构和动态数据结构到目前为止，教材中介绍的各种基本类型和导出类型的数据结构都是静态数据结构。静态数据结构指在变量声明时建立的数据结构。在变量声明时变量的存储分配也确定了，并且在程序的执行过程中不能改变。动态数据结构是在程序运行过程中通过调用系统提供的动态存储分配函数，向系统申请存储而逐步建立起来的。

24、在程序运行过程中，动态数据结构所占存储的大小可以根据需要调节，使用完毕时可以通过释放操作将所获得的存储交还给系统供再次分配。由于系统提供的动态存储分配函数的返回值是指向分配存储的起始地址的指针，因此动态数据对象没有名字，对动态数据对象的访问只能通过指针进行。 7/23/202229华中科技大学计算机学院10.9.2 C的动态存储分配函数动态存储分配函数是C的标准函数，函数的原型声明在头文件中给出。使用动态存储分配函数必须先使用#include 编译预处理命令。C提供下列与动态存储分配相关的函数。void * malloc(size_t size);void * calloc(size_t n,

25、 size_t size);void * realloc(void * p_block, size_t size);void free(void * p_block);其中，size_t表示unsigned int，即无符号整型。它是在中通过typedef unsigned size_t;定义的。 7/23/202230华中科技大学计算机学院1) malloc函数的功能 malloc函数的原型为：void * malloc(size_t size);malloc函数的功能是向系统申请分配size个字节大小的存储。如果分配成功，返回新分配存储区域的首地址；如果分配失败（如内存容量不够），返回NU

26、LL。新分配存储区域未被初始化。例如，下面的代码片断就利用了malloc函数动态创建一个有6个元素的整型数组。int i,*p;p=(int *)malloc(6*sizeof(int);if(p) for(i=0;inum时，s2指向字符指针(p+i)-num。因此，(*s2)就是(p+i)-num。(*s2)=(char *)malloc(len*sizeof(char)+1);等价于：(p+i)-num =(char *)malloc(len*sizeof(char)+1);只有将s2声明为双重字符针，才能够使主函数中的(p+i)-num和(p+i)-name指向在dynamic_inp

27、ut函数中动态分配的存储区域。7/23/202238华中科技大学计算机学院void main(void)int n,i;struct c_score_tab *p;printf(input the number of students please!n);scanf(%d,&n);getchar(); /* getchar用于读结束scanf输入的回车符 */p=(struct c_score_tab *)malloc(n*sizeof(struct c_score_tab);assert(p);for(i=0;inumdynamic_input(input name!n,&(p+i)-nam

28、e); printf(input score!n);scanf(%d,&(*(p+i).c); /* 输入C语言课程成绩 */getchar();printf(n);for(i=0;inum,(p+i)-name,(p+i)-c);printf(n);free(p); /* 释放成绩单占据的存储 */7/23/202239华中科技大学计算机学院*10.11 链 表链表是一种常用的动态数据结构，它由一系列包含数据域和指针域的结点组成。如果结点的指针域中只包含一个指向后一个结点指针，这种链表称为单向链表。如果结点的指针域包含两个指针，且一个指向前一个结点，另一个指向后一个结点，这种链表称为双向链表

29、。如果结点的指针域包含两个指针，且一个指向后一个结点，另一个指向另外一个链表，这种链表称为十字交叉链表。 7/23/202240华中科技大学计算机学院10.11.1 自引用结构如果一个结构类型中包含一个该结构类型的指针，称该结构类型为自引用结构类型，对应的结构变量称为自引用结构变量，自引用结构变量常常简称为自引用结构。自引用结构的指针成员是一个指向该自引用结构的指针。因此，关于自引用结构的定义也可以表示为：如果一个结构中包含一个指向该结构自身的指针，该结构称为自引用结构。 7/23/202241华中科技大学计算机学院自引用结构struct s_list int data; struct s_l

30、ist *next; node1=1,NULL;由于struct s_list结构类型中，next是指向struct s_list结构类型变量的指针（称为指向自身的指针），因此struct s_list结构类型是自引用结构类型。而node1是自引用结构变量（自引用结构）。 7/23/202242华中科技大学计算机学院自引用结构变量（自引用结构）执行下面语句：struct s_list node2,node3;node2.data=2;node3.data=3;node2.next=node3.next=NULL;则node1,node2,node3的存储结构如图所示。 node1 node2

31、node37/23/202243华中科技大学计算机学院例10.16 以自引用结构node1、node2和node3为“结点”构建“链表”。 #include stdio.hstruct s_listint data;struct s_list *next; node1=1,NULL;void main(void)struct s_list node2,node3;struct s_list *head=NULL,*p;node2.data=2;node3.data=3;node2.next=node3.next= NULL;head=&node1; node1.next=&node2; nod

32、e2.next=&node3; p=head; printf(%pt%pn,&head, head);while(p) printf(%pt%dt%pn, p,p-data,p-nextp=p-next; 7/23/202244华中科技大学计算机学院程序中head称为头指针，head=&node1使head指向了node1；node1.next=&node2使node1指向了node2；node2.next=&node3使node2指向了node3。p称为遍历指针, p=p-next使p指向了下一个自引用结构。对“结点”和“链表”加一个引号，表明上面程序创建的各个自引用结构之间的指向关系与实际

33、链表一致，但存储分配是静态而不是动态的。程序的运行结果如下：FFD4 01940194 1 FFCCFFCC 2 FFD0FFD0 3 00007/23/202245华中科技大学计算机学院10.11.2 动态创建结点可以通过（结点指针类型）malloc(sizeof(结点类型)的方式来动态创建结点。如：p=(struct s_list *)malloc(sizeof(struct s_list)它通过动态存储分配创建一个struct s_list的自引用结构变量作为结点，并将返回值的类型强制转换为自引用结构类型的指针并赋给指针p。 7/23/202246华中科技大学计算机学院例1017 从头指

34、针开始,动态创建三个结点，并使用头指针head访问后继三个结点。相关解释以注释的方式给出。 struct s_listint data;struct s_list *next; ;void main(void)struct s_list *head=NULL,*p;head=(struct s_list *) malloc(sizeof(struct s_list);head-data=1;head-next=(struct s_list *) malloc(sizeof(struct s_list);head-next-data=2;head-next-next=(struct s_list

35、 *) malloc(sizeof(struct s_list);head-next-next-data=3;head-next-next-next=NULL;p=head;while(p)printf(%pt%dt%pn, p,p-data,p-next);p=p-next; 7/23/202247华中科技大学计算机学院10.11.3 单向链表在单向链表中，结点的指针域中只包含一个指向其自身的指针，用于指向后继结点。头指针指向链表中称为链头的第一个结点，从第一个结点开始，每个结点的指针成员都指向其后继结点，最后一个称为链尾的结点的指针域为空指针NULL。struct s_list结构中由于数

36、据域内只有一个整型数据，以此为结点构成的链表一般都称为整数链表。设所讨论的结点为当前结点，则它前面的一个结点称为直接前驱结点（简称前驱）；它后面的一个结点称为直接后继结点（简称后继）。 7/23/202248华中科技大学计算机学院例10.18 给定一批整数，以0作为结束标志且不作为结点，将其建成一个先进先出的链表，先进先出链表的指头指针始终指向最先创建的结点（链头），先建结点指向后建结点，后建结点始终是尾结点。结点自引用结构类型的声明和创建链表函数原型的声明如下：#include stdio.h#include stdlib.h“struct s_list int data; /* 数据域 *

37、/struct s_list *next; /* 指针域 */ ;void create_list_v1(struct s_list *headp,int *p); 7/23/202249华中科技大学计算机学院1用循环方式建立先进先出链表建立一个非空先进先出链表相关算法步骤如下：（1）声明头指针，尾指针。struct s_list * loc_head=NULL,*tail; （2）创建第一个结点。包括：（2-1）给第一个结点动态分配存储并使头指针指向第一个结点。loc_head=(struct s_list *)malloc(sizeof(struct s_list);（2-2）给第一个结点

38、的数据域中成员赋值。loc_head-data=*p+;（2-3）使尾指针也指向第一个结点。tail=loc_head;（3）循环建立后续结点（3-1）如果没遇到结束标志0，进行下列操作：（3-1-1）给后继结点动态分配存储并使前驱结点的指针指向后继结点。tail-next=(struct s_list *)malloc(sizeof(struct s_list);（3-1-2）使尾指针指向新建立的后继结点tail=tail-next;（3-1-3）给后继结点的数据域中成员赋值。tail-data=*p+;（3-1-4）转（3-1）（4）给尾结点（最后一个结点）的指针赋NULL值。tail-n

39、ext=NULL;7/23/202250华中科技大学计算机学院根据算法步骤设计的创建链表函数的如下:void create_list_v1(struct s_list *headp,int *p)struct s_list * loc_head=NULL,*tail;if(p0=0) /* 相当于*p=0 */;else /* loc_head指向动态分配的第一个结点 */loc_head=(struct s_list *)malloc(sizeof(struct s_list);loc_head-data=*p+; /* 对数据域赋值 */tail=loc_head; /* tail指向第一

40、个结点 */while(*p) /* tail所指结点的指针域指向动态创建的结点 */tail-next=(struct s_list *)malloc(sizeof(struct s_list);tail=tail-next; /* tail指向新创建的结点 */tail-data=*p+; /* 向新创建的结点的数据域赋值 */tail-next=NULL; /* 对指针域赋NULL值 */*headp=loc_head; /* 使头指针headp指向新创建的链表 */ 其中，headp是指向链表头指针的指针，类型是struct s_list *headp，为双重指针，它指向的是main函

41、数中的head。*headp即main函数中的head，*headp=loc_head使main函数中的头指针head指向新创建的链表。7/23/202251华中科技大学计算机学院在main函数中调用create_list_v1 void main(void)struct s_list *head=NULL,*p;int s=1,2,3,4,5,6,7,8,0; /* 0为结束标记 */create_list_v1(&head,s); /* 创建新链表 */p=head; /*遍历指针p指向链头 */while(p)printf(%dt,p-data); p=p-next; /*遍历指针p指向

42、下一结点 */printf(n); 7/23/202252华中科技大学计算机学院遍历链表的算法步骤 （1）初始化，使遍历指针p指向头结点。 p=head;（2）如果链表非空（即遍历指针p非空，p！=NULL）（2-1）输出结点数据域中成员的值。printf(%dt,p-data);（2-2）使遍历指针p指向下一个结点。p=p-next;（2-3）转（2）main函数中给出了根据算法步骤设计的程序。 7/23/202253华中科技大学计算机学院2用递归方式建立先进先出链表struct s_list *create_list_v2(int *);struct s_list *create_list

43、_v2(int *p)struct s_list * loc_head=NULL;if(p0=0) /* 遇到结束标记，返回NULL */return NULL;else /* loc_head指向新创建的结点 */loc_head=(struct s_list *)malloc(sizeof(struct s_list);loc_head-data=*p; /* 对新创建结点的数据域赋值 */ loc_head-next=create_list_v2(p+1); /* 递归创建下一结点 */return loc_head; /* 返回链头地址 */ 7/23/202254华中科技大学计算机学

44、院create_list_v2是一个struct s_list类型的指针函数，即，它返回值的类型是struct s_list *。它递归的建立链表中的各个结点，当遇到结束标志时（p0=0），该次调用返回NULL值，而NULL值将作为前一次调用中所建立结点指针域的值.注意：由于递归调用时用p+1做实参，p0即*p，最后一次必然引用s8，即0。如果p0不为0，则建立结点，给结点的数据域中成员赋值，递归调用建立下一个结点，并将建立下一个结点操作的地址返回赋给结点的指针域。递归调用将后继结点的地址返回并赋给前驱结点的指针域。另外，只要将前面main函数进行修改，将create_list_v1(&hea

45、d,s);语句改为：head=create_list_v2(s);则main函数就可以完成对create_list_v2的调用，得到与1中完全相同的结果。 7/23/202255华中科技大学计算机学院10.11.4 链表的相关操作链表的相关操作包括：创建链表;遍历链表;在链表中插入一个结点;删除链表中的一个结点;同类型链表的归并;链表的排序等。 7/23/202256华中科技大学计算机学院1遍历链表遍历链表可以进一步分为遍历链表，输出链表中各个结点的数据域成员；遍历链表，统计链表中结点的数目；遍历链表，查找链表中符合条件的某个结点等。其中输出链表中各个结点的数据域成员已经介绍。7/23/202

46、257华中科技大学计算机学院例10.19 用循环遍历的方式统计链表中结点的数目（即链表的长度）。int count_nodes(struct s_list * head)struct s_list * p=head;int num=0;while(p)num+;p=p-next;return num; 7/23/202258华中科技大学计算机学院例10.20 用递归遍历的方式统计链表中结点的数目。int count_nodes_recursive(struct s_list * head)struct s_list * p=head;if(p) return (1+count_nodes_re

47、cursive(p-next);elsereturn 0;7/23/202259华中科技大学计算机学院例10.21 用递归方式查找链表中数据成员值与形参n相同的结点。如果有，返回该结点的地址，如果没有，返回NULL。 struct s_list * find_nodes_recursive(struct s_list * head,int n)struct s_list * p=head;if(p) /* 链表非空，查找 */if(p-data=n &p!=NULL)return p; /* 找到，返回该结点的地址 */elsefind_nodes_recursive(p-next,n);/*

48、 递归查找 */else return NULL; 7/23/202260华中科技大学计算机学院2插入结点在链表中插入一个结点的操作是指在链中满足给定条件结点（即插入点）的前或后加入一个新的结点。 因此，首先要根据给定条件遍历链表，确定插入点的位置.插入点的位置可能是链头、链尾、或者链中。插入方式有将加入结点作为插入点的新后继结点和插入点的新前驱结点两种。本节按照先进先出链的规定，将加入结点作为插入点的新后继结点。至于将加入结点作为插入点的新前驱结点的插入方法请读者自行考虑。如果插入点是链尾，插入方法与建立先进先出链的方法相同。如果插入点是链头或链中，则需要两个遍历指针，一个是指向插入点的遍历

49、指针current，另一个是指向插入点后继结点的遍历指针after。设新结点由other指针所指，它将插入在current和after所指结点之间。插入前结点间的指向关系如图10.3所示。7/23/202261华中科技大学计算机学院插入前结点间的指向关系如图10.3所示则 操作为： other-next=after; 操作为： current-next=other;插入后结点间的指向关系如图10.4所示。7/23/202262华中科技大学计算机学院例10.22 在链表中数据成员的值与形参n相等的结点后面插入一个新的结点，给结点的数据成员赋值，并返回插入点的地址。struct s_list *

50、insert_nodes(struct s_list * head,int n)struct s_list * current=head,*after,*other;while(current-data!=n¤t!=NULL)current=current-next;if(!current) return NULL;after=current-next; other = (struct s_list *) malloc(sizeof(struct s_list);scanf(%d,&other-data); if(after)other-next=after; current-ne

51、xt=other; elseother-next=NULL; current-next=other; return current; 7/23/202263华中科技大学计算机学院3删除结点删除结点的操作是插入结点操作的逆操作。假设链表如图10.5，且要删除current指针指向的结点，则删除该结点就是要将该结点从链表中孤立出来，形成图10.6的链表。同时要释放被删除结点的存储。图中after指针仅为示意用，程序中不必用after指针。7/23/202264华中科技大学计算机学院删除结点示意图 7/23/202265华中科技大学计算机学院删除结点算法描述删除结点就是使该结点的前驱结点指向其后继结

52、点。为此需要指向被删除结点的遍历指针current和指向被删除结点的前驱结点的遍历指针prior。结点间的指向关系为：删除前：prior-next=current; 即:prior-next指向被删结点。删除后：prior-next=after;或 prior-next= current-next; 或 prior-next= prior-next-next;即:prior-next指向被删结点的后继结点。 7/23/202266华中科技大学计算机学院例10.23 写一个函数，查找链表中数据成员的值与形参n相等的结点，如果找到，删除该结点，并返回插入点的地址；如果没有找到，返回NULL。 st

53、ruct s_list * delete_nodes(struct s_list *headp,int n)struct s_list * current=*headp,*prior=*headp;while(current-data!=n ¤t)/* 查找数据成员值与形参n相等的结点 */prior=current; /* prior指向当前结点 */current=current-next; /* current指向下一结点 */if(!current) /* 没有符合条件的结点 */return NULL;if(current=*headp) /* 被删结点是链头*/*hea

54、dp=current-next;else /* 被删结点不是链头 */prior-next= current-next;free(current); /* 释放被删结点的存储 */return current; 7/23/202267华中科技大学计算机学院4归并链表对于非空链表A、B,将链表B归并到链表A指将链表A的链尾指向链表B的链头所形成的一个新的链表。因此，首先要遍历链表A找到其链尾，然后将链表B的头指针值赋给链表A链尾的指针域即可。具体编程实现时，仍然要声明两个遍历指针current和prior，prior仍然是指向current指针所指结点的前驱结点。这样，在遍历链表的过程中，当cu

55、rrent为空时，prior则指向的是链尾。 7/23/202268华中科技大学计算机学院例10.24 写一个函数，对两个链表进行归并。void concatenate_lists(struct s_list *headA,struct s_list *headB)struct s_list * current=headA,*prior;while(current)prior=current;current=current-next;prior-next=headB;调用concatenate_lists函数做归并操作时，必须用两个链表的头指针作为实参。 7/23/202269华中科技大学计算

56、机学院5链表排序链表排序是指将链表的结点按某个数据域从小到大（升序）或从大到小（降序）的顺序连接。链表排序算法的思路与数组排序类似，链表中的结点类似于数组中的元素，但数组中元素的存储是连续的，可以用下标索引，而链表中各结点在存储方面并不连续，因此链表的结点只能用指针引用。排序中对链表结点的交换有两种方法，一种是交换结点的数据域，不改变结点间的指向关系。另一种是改变结点的连接实现结点的交换，操作较为复杂。在数据域较为简单的情况下，多采用交换结点的数据域的方法进行链表排序。7/23/202270华中科技大学计算机学院例10.25 写一个函数，采用交换结点数据域的方法实现对链表的升序排序。 void sort_lists(struct s_list *head);void sort_lists(struct s_list *head)struct s_list *p1=head,*p2;int len=0,i,j,t;while(p1) /* 计算链表的长度 */len+;p1=p1-next;for(i=0,p1=head;inext)for(j=i+1,p2=p1-next;jnext)if(p1-data p2-data)t=p1-data; /* 交换数据域 */p1-data=p2-data;p2-data=t; 7/23/202271华中科技大学计算机学院如果采用冒泡