语言链表详解ppt课件.ppt

《语言链表详解ppt课件.ppt》由会员分享，可在线阅读，更多相关《语言链表详解ppt课件.ppt（91页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去第十一章 链表链表详解珍藏版1火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去结构的概念与应用结构的概念与应用2火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去依上图有依上图有7个结点个结点(x1,y1)(x1,y1)(x2,y2)(x2,y2)(x6,y6)(x6,y6)(x7,y7)(x7,y7)3火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸

2、湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去11.7 11.7 用指针处理链表用指针处理链表链表是程序设计中一种重要的动态数据结构，链表是程序设计中一种重要的动态数据结构，它是动态地进行存储分配的一种结构。它是动态地进行存储分配的一种结构。动态性体现为：动态性体现为：n链表中的元素个数可以根据需要增加和减少，不链表中的元素个数可以根据需要增加和减少，不像数组，在声明之后就固定不变；像数组，在声明之后就固定不变；n元素的位置可以变化，即可以从某个位置删除，元素的位置可以变化，即可以从某个位置删除，然后再插入到一个新的地方；然后再插入到一个新的地方；4火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，

3、要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去12491249 A A13561356 B B14751475 C C10211021 D DNullNull1 1、链表中的元素称为、链表中的元素称为“结点结点”，每个结点包括两，每个结点包括两个域：个域：数据域和指针域；数据域和指针域；2 2、单向链表通常由一个头指针（、单向链表通常由一个头指针（head)head)，用于指向，用于指向链表头；链表头；3 3、单向链表有一个尾结点，该结点的指针部分指、单向链表有一个尾结点，该结点的指针部分指向一个空结点向一个空结点(NULL)(NULL)。Head 1249 1356 1475 1

4、021结点里的指针是存放下一个结点的地址5火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去链表中结点的定义链表中结点的定义q链表是由结点构成的，链表是由结点构成的，关键是定义结点关键是定义结点;q链表的结点定义打破了先定义再使用的限制链表的结点定义打破了先定义再使用的限制,即可以用自己定义自己；即可以用自己定义自己；q递归函数的定义也违反了先定义再使用；递归函数的定义也违反了先定义再使用；这是这是C C语言程序设计上的两大特例语言程序设计上的两大特例6火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿

5、毛毯、湿被褥勇敢地冲出去链表的基本操作链表的基本操作对链表的基本操作有：对链表的基本操作有：（1 1）创创建建链链表表是是指指，从从无无到到有有地地建建立立起起一一个个链链表表，即即往往空空链链表表中中依依次次插插入入若若干干结结点点，并并保保持持结结点点之之间的前驱和后继关系。间的前驱和后继关系。（2 2）检索操作检索操作是指，按给定的结点索引号或检索是指，按给定的结点索引号或检索条件，查找某个结点。如果找到指定的结点，则条件，查找某个结点。如果找到指定的结点，则称为检索成功；否则，称为检索失败。称为检索成功；否则，称为检索失败。（3 3）插插入入操操作作是是指指，在在结结点点k ki-1i

6、-1与与k ki i之之间间插插入入一一个个新新的的结结点点k k，使使线线性性表表的的长长度度增增1 1，且且k ki-1i-1与与k ki i的逻辑关系发生如下变化：的逻辑关系发生如下变化：插插入入前前，k ki-1i-1是是k ki i的的前前驱驱，k ki i是是k ki-1i-1的的后后继继；插插入入后后，新插入的结点新插入的结点k k成为成为k ki-1i-1的后继、的后继、k ki i的前驱的前驱.7火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去（4 4）删删除除操操作作是是指指，删删除除结结点点k ki i，使使线线

7、性性表表的的长长度度减减1 1，且且k ki-1i-1、k ki i和和k ki+1i+1之之间间的的逻逻辑辑关关系系发发生生如如下下变变化：化：删除前，删除前，k ki i是是k ki+1i+1的前驱、的前驱、k ki-1i-1的后继；删除后，的后继；删除后，k ki-1i-1成为成为k ki+1i+1的前驱，的前驱，k ki+1i+1成为成为k ki-1i-1的后继的后继.(5)(5)打印输出打印输出8火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去一个指针类型的成员既可指向其它类型的结构体数一个指针类型的成员既可指向其它类型的结

8、构体数据，也可以指向自己所在的结构体类型的数据据，也可以指向自己所在的结构体类型的数据991019910189.589.59910399103909099107991078585numScorenextnext是是struct student类型中的一个成员，类型中的一个成员，它又它又指向指向struct student类型类型的数据。的数据。换名话说：换名话说：next存放下一个结点的地址存放下一个结点的地址9火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去11.7.2 11.7.2 简单链表简单链表#define NULL 0st

9、ruct student long num;float score;struct student *next;main()struct student a,b,c,*head,*p;a.num=99101;a.score=89.5;b.num=99103;b.score=90;c.num=99107;c.score=85;head=&a;a.next=&b;b.next=&c;c.next=NULL;p=head;do printf(%ld%5.1fn,p-num,p-score);p=p-next;while(p!=NULL);建建立立和和输输出出一一个个简简单单链链表表各结点在程序中定义，

10、不是临时开辟的，各结点在程序中定义，不是临时开辟的，始终占有内容始终占有内容不放不放，这种链表称为，这种链表称为“静静态链表态链表”10火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去 11.7.3 11.7.3 处理动态链表所需的函数处理动态链表所需的函数C C 语言使用系统函数语言使用系统函数动态动态开辟和释放存储单元开辟和释放存储单元1.malloc 1.malloc 函数函数 函数原形：函数原形：void*malloc(unsigned int size);void*malloc(unsigned int size);作用：作

11、用：在内存的动态存储区中分配在内存的动态存储区中分配 一个一个 长度为长度为sizesize的连续空间。的连续空间。返回值：返回值：是一个指向分配域起始地址的指针（基本是一个指向分配域起始地址的指针（基本类型类型voidvoid）。）。执行失败：执行失败：返回返回NULLNULL11火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去函数原形函数原形:void*calloc(unsigned n,unsigned size);作用：作用：在内存动态区中分配在内存动态区中分配 n n个个 长度为长度为sizesize的的连续空间。连续空间。

12、函数返回值函数返回值：指向分配域起始地址的指针：指向分配域起始地址的指针执行失败：返回执行失败：返回nullnull主要用途主要用途：为一维数组开辟动态存储空间。：为一维数组开辟动态存储空间。n n 为为数组元素个数，每个元素长度为数组元素个数，每个元素长度为sizesize2.calloc2.calloc 函数函数12火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去3.free 3.free 函数函数函数原形：函数原形：void free(void void free(void*p*p););作用：作用：释放由释放由 p p 指向的

13、内存区。指向的内存区。P:P:是最近一次调用是最近一次调用 calloc calloc 或或 malloc malloc 函数函数时返回的值。时返回的值。free free 函数无返回值函数无返回值动态分配的存储单元在用完后一定要释放，动态分配的存储单元在用完后一定要释放，否则内存会因申请空间过多引起资源不足否则内存会因申请空间过多引起资源不足而出现故障。而出现故障。13火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去结点的动态分配结点的动态分配ANSI C ANSI C 的三个函数的三个函数(头文件头文件 malloc.h)void

14、 malloc.h)void*malloc(unsigned int size)*malloc(unsigned int size)void*calloc(unsigned n,unsigned size)void*calloc(unsigned n,unsigned size)void free(void*p)void free(void*p)C+C+的两个函数的两个函数new new 类型（初值）类型（初值）delete delete 指针变量指针变量 /*/*表示释放数组，可有可无）表示释放数组，可有可无）*/使用使用 new new 的优点：的优点：可以通过对象的大小直接分配，而不管对

15、象的可以通过对象的大小直接分配，而不管对象的具体长度是多少（具体长度是多少（p340 p340 例例14.1014.10）14火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去11.7.4 11.7.4 建立动态链表建立动态链表基本方法基本方法:三个结点（头结点三个结点（头结点headhead、尾结点、尾结点 NULL NULL 和待插入结点和待插入结点 P P）第一步：定义头结点第一步：定义头结点headhead、尾结点、尾结点 p2p2 和待插入结点和待插入结点p1p1，待插入的结点数据部分初始化；，待插入的结点数据部分初始化；第二

16、步：该结点被头结点、尾结点同时指向第二步：该结点被头结点、尾结点同时指向。P1=p2=(struct student*)malloc(LEN);P1=p2=(struct student*)malloc(LEN);头指针部分为空头指针部分为空，head=NULL;head=NULL;第三步：重复申请待插入结点空间，对该结点的数据部第三步：重复申请待插入结点空间，对该结点的数据部分赋值（或输入值），将该结点插入在最前面，或者最分赋值（或输入值），将该结点插入在最前面，或者最后面（书上在尾部插入）后面（书上在尾部插入）.P2-next=P1;P2=P1;P2-next=P1;P2=P1;最后最后:

17、P2-next=NULL;:P2-next=NULL;*head,*p1,*p2*head,*p1,*p2使用使用malloc(LEN)malloc(LEN)P2-next=NULL;15火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去11.7.4 11.7.4 建立动态链表建立动态链表991019910189.589.5headP1p21.任务是开辟结点和输入数据任务是开辟结点和输入数据2.2.并建立前后相链的关系并建立前后相链的关系待插入的结点待插入的结点p1p1数数据部分初始化据部分初始化,该结该结点被头结点点被头结点head、

18、尾结点尾结点p2同时指向同时指向.16火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去图图11.1411.14991019910189.589.5headp299103991039090p1991019910189.589.5headp299103991039090p1(a)(b)p1重复申请待插入重复申请待插入结点空间，对该结结点空间，对该结点的数据部分赋值点的数据部分赋值（或输入值）（或输入值）P2-next P2-next 指向指向p1p1新开辟的结点。新开辟的结点。17火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立

19、断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去图图11.1411.14head991019910189.589.5p1p299103991039090(c)P2P2指向新结指向新结点点p2=p1p2=p118火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去图图11.1511.15991019910189.589.5991019910189.589.5p299107991078585p1head991019910189.589.5991019910189.589.5p299107991078585p1head(a)(b)19火灾袭来

20、时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去 图图11.1611.169910399103909099107991078585p20 00 0p1head991019910189.589.59910399103909099107991078585NULLNULLp20 00 0p1head991019910189.589.520火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去例例11.8 11.8 建立一个有建立一个有3 3名学生数据的单向动态链表名学生数据的单向动态链表#def

21、ine NULL 0#define LEN sizeof(struct student)struct studentlong num;float score;struct student*next;int n;struct student*creat(void)struct student*head;struct student*p1,*p2;n=0;p1=p2=(struct student*)malloc(LEN);scanf(%1d,%f,&p1-num,&p1-score);head=NULL;结构体类型数据的长度，结构体类型数据的长度，sizeofsizeof是是“字节数运算符字节数

22、运算符”定义指针类型的函数。带回链表的起始地址定义指针类型的函数。带回链表的起始地址开辟长度为开辟长度为LENLEN的内存区的内存区P1,p2P1,p2是指向结构体类型数据的指针变是指向结构体类型数据的指针变量，强行转换成结构体类型量，强行转换成结构体类型假设头指向空结点假设头指向空结点21火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去续续while(p1-num!=0)n=n+1;/*n 是结点的个数是结点的个数*/if(n=1)head=p1;else p2-next=p1;p2=p1;p1=(struct student*)m

23、alloc(LEN);scanf(%1d,%f,&p1-num,&p1-score);p2-next=NULL;return(head);/返返回回链链表表的的头头指针指针算法：算法：p1指向新开的结点指向新开的结点:p1=(stuct student*)malloc(LEN);p1的所指向的结点连接在的所指向的结点连接在p2所指向结点后面，用所指向结点后面，用p2-next=p1来实现。来实现。p2 指向链表中最后建立的结点，指向链表中最后建立的结点，:p2=p1;头指针指向头指针指向p1结点结点P1开辟的新结点链到了开辟的新结点链到了p2的后面的后面P1继续开辟新结点继续开辟新结点给新结点

24、赋值此给新结点赋值此22火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去11.7.5 11.7.5 输出链表输出链表链表遍历链表遍历1.1.单向链表总是从头结点开始的；单向链表总是从头结点开始的；2.2.每访问一个结点，就将当前指针向该每访问一个结点，就将当前指针向该结点的下一个结点移动：结点的下一个结点移动：p=p-nextp=p-next;3.3.直至下一结点为空直至下一结点为空 P=NULLP=NULL23火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去图图 11.18

25、11.18headp PPNULLNULL24火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去void print(struct student*head)struct student*p;printf(nNow,These%d records are:n,n);p=head;if(head!=NULL)do printf(%ld%5.lfn,p-num,p-score);p=p-next;while(p!=NULL);25火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去11

26、.7.6 11.7.6 对链表的删除操作对链表的删除操作删除结点原则：删除结点原则：不改变原来的排列顺序，只是从链表中分离开来，不改变原来的排列顺序，只是从链表中分离开来，撤消原来的链接关系。撤消原来的链接关系。两种情况：两种情况：1 1、要删的结点是头指针所指的结点则直接操作；、要删的结点是头指针所指的结点则直接操作；2 2、不是头结点，要依次往下找。、不是头结点，要依次往下找。另外要考虑：空表和找不到要删除的结点另外要考虑：空表和找不到要删除的结点26火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去链表中结点删除链表中结点删除需要

27、由两个临时指针：需要由两个临时指针：P1:P1:判断指向的结点是不是要删除的结点判断指向的结点是不是要删除的结点（用于寻找）；（用于寻找）；P2:P2:始终指向始终指向P1P1的前面一个结点；的前面一个结点；27火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去图图11.1911.19ABDECABDEC(a)(B)28火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去图图11.2011.209910199101headp199103991039910799107NULLNULL

28、（a）(b)9910199101head99103991039910799107NULLNULLp2p1原链表原链表P1指向指向头结点头结点P2指向指向p1指向的结指向的结点。点。P1指指向下移一向下移一个结点。个结点。29火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去图图11.2011.209910199101head99103991039910799107NULLNULLp19910199101head99103991039910799107NULLNULLp2p1(c)(d)经判断后，第经判断后，第1个个结点是要删除的结点是要

29、删除的结点，结点，head指向指向第第2个结点，第个结点，第1个结点脱离。个结点脱离。经经P1P1找到要删找到要删除的结点后使除的结点后使之脱离。之脱离。30火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去struct student*del(struct student*head,long num)struct student *p1,*p2;if(head=NULL)printf(nlist null!n);goto end;p1=head;while(num!=p1-num&p1-next!=NULL)p2=p1;p1=p1-n

30、ext;if(num=p1-num)if(p1=head)head=p1-next;else p2-next=p1-next;printf(delete:%ldn,num);n=n-1;else printf(%ld not been found!n,num);end:return(head);找到了找到了没找到没找到31火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去11.7.7 11.7.7 对链表的插入操作对链表的插入操作插入结点：将一个结点插入到已有的链表中插入结点：将一个结点插入到已有的链表中插入原则：插入原则：1 1、插入

31、操作不应破坏原链接关系、插入操作不应破坏原链接关系2 2、插入的结点应该在它该在的位置、插入的结点应该在它该在的位置实现方法：实现方法：应该有一个插入位置的查找子过程应该有一个插入位置的查找子过程共有三种情况：共有三种情况：1 1、插入的结最小、插入的结最小2 2、插入的结点最大、插入的结点最大3 3、插入的结在中间、插入的结在中间32火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去 操操 作作 分分 析析同删除一样，需要几个临时指针：同删除一样，需要几个临时指针：P0:P0:指向待插的结点指向待插的结点;初始化：初始化：p0=p0=

32、数组数组stu;stu;P1:P1:指向要在指向要在P1P1之前插入结点；初始化之前插入结点；初始化:p1=head;:p1=head;P2:P2:指向要在指向要在P2P2之后插入结点；之后插入结点；插入操作：当符合以下条件时：插入操作：当符合以下条件时：p0-num p0-num 与与 p1-num p1-num 比较找位置比较找位置if(p0if(p0-nump1-num)&(p1-next!=NULL)则插入的结点不在则插入的结点不在p1所指结点之前；指针后移，交给所指结点之前；指针后移，交给p2；p1=p1-next;p2=p1;p1-next;p2=p1;则继续与则继续与 p0 指向

33、的数组去比，直到指向的数组去比，直到（p1-next!=NULL)为止。为止。否则有两种情况发生：否则有两种情况发生：if(head=p1)head=p0;p0-next=p1if(head=p1)head=p0;p0-next=p1插到原来第一个结插到原来第一个结点点之前之前；else p2-next=p0;p0-next=p1;-next=p0;p0-next=p1;插到插到 p2 指向的结点指向的结点之后之后；还有另外一种情况：插到还有另外一种情况：插到最后最后的结点之后；的结点之后；p1-next=p0;p0-next=NULL;-next=p0;p0-next=NULL;33火灾袭来

34、时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去图图11.2211.229910199101headp199103991039910799107NULLNULL（a）9910299102p034火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去图图11.2211.229910199101head99103991039910799107NULLNULL9910299102p0p2p1(b)35火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥

35、勇敢地冲出去struct student insert(struct student*head,struct student*stud)struct student*p0,*p1,*p2;p1=head;p0=stud;if(head=NULL;)head=p0;p0-next=NULL;else while(p0-nump1-num)&(p1-next!=NULL)p2=p1;p1=p1-next;if(p0-numnum)if(head=p1)head=p0;else p2-next=p0;p0-next=p1;else p1-next=p0;p0-next=NULL;n=n+1;retu

36、rn(head);原来的链表是空表原来的链表是空表P0P0指向要插的结点指向要插的结点使使p0p0指向的结点作为头结点指向的结点作为头结点使使p2指向刚才指向刚才p1指向的结点指向的结点插到原来第一个结点之前插到原来第一个结点之前插到插到p2指向的结点之后指向的结点之后插到最后的结点之后插到最后的结点之后链接36火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去5 5head6 610101515null12128 8课堂举例：课堂举例：已有一个如图所示的链表；已有一个如图所示的链表；它是按结点中的整数域从小到大排序的，现在要插它是按结

37、点中的整数域从小到大排序的，现在要插入一个结点，该结点中的数为入一个结点，该结点中的数为1010待插入结点待插入结点此结点已插入链表此结点已插入链表37火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去分析：分析：按三种情况按三种情况1 1、第一种情况，链表还未建成（空链表），待插入结点、第一种情况，链表还未建成（空链表），待插入结点p p实际上是第一个结点。这时必然有实际上是第一个结点。这时必然有head=nullhead=null。只要。只要让头指针指向让头指针指向 p p 就可以了。语句为就可以了。语句为6nullheadphea

38、d=p;p-next=null;2 2、第二种情况，链表已建成，待插入结点、第二种情况，链表已建成，待插入结点 p p 的数据要的数据要比头结点的数据还要小，这时有比头结点的数据还要小，这时有(p-num)num)p-num)num)当然当然p p结点要插在结点要插在headhead结点前。结点前。38火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去6head8512nullheadpp-next=head;head=p;语句为语句为null39火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、

39、湿被褥勇敢地冲出去3 3、第三种情况，链表已建成，待插入结点、第三种情况，链表已建成，待插入结点 p p 的数据比头结点的数据大，需要找到正确的的数据比头结点的数据大，需要找到正确的插入位置。这时，可以借助两个结构指针插入位置。这时，可以借助两个结构指针r r 和和 g g，利用循环比较来找到正确位置。然后，利用循环比较来找到正确位置。然后将结点将结点 p p 插入到链表中正确的位置。插入到链表中正确的位置。参见下面的图示参见下面的图示40火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去6head81213nullp15gr说明：说明

40、：这种情况下，这种情况下，p p 结点已经与链表的第一个结点结点已经与链表的第一个结点比较过了，所以从链表的下一个结点开始比较。比较过了，所以从链表的下一个结点开始比较。138138，继续比较。，继续比较。41火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去6head81213nullp15gr说明：说明：13121312，继续比较。，继续比较。42火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去6head81213p15grnull说明：说明：131513next=p;p-

41、next=g;43火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去/结构结构7.c#include#include/预编译命令预编译命令#include#include/内存空间分配内存空间分配#define null 0#define null 0/定义空指针常量定义空指针常量#define LEN sizeof(struct numST)#define LEN sizeof(struct numST)/定义常量，表示定义常量，表示结构长度结构长度struct numSTstruct numST/结构声明结构声明 int num;i

42、nt num;/整型数整型数struct numST*next;struct numST*next;/numST/numST结构指针结构指针;参考程序参考程序44火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去/被调用函数被调用函数insert()，两个形参分别表示链表和待插入的结点，两个形参分别表示链表和待插入的结点void insert(struct numST*phead,struct numST*p)/函数体开始函数体开始struct numST*q,*r;/定义结构指针定义结构指针q,rif(*phead)=null)/第一

43、种情况第一种情况，链表为空，链表为空*phead=p;/链表头指向链表头指向preturn;/完成插入操作，返回完成插入操作，返回else/链表不为空链表不为空/第二种情况第二种情况，p结点结点num值小于链表头结点的值小于链表头结点的num值值if(*phead)-num p-num)/将将p结点插到链表头部结点插到链表头部 p-next=*phead;/将将p的的next指针指向链表头指针指向链表头(*phead)*phead=p;/将链表头赋值为将链表头赋值为p return;/返回返回45火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇

44、敢地冲出去/第三种情况第三种情况，循环查找正确位置，循环查找正确位置r=*phead;/r赋值为链表头赋值为链表头q=(*phead)-next;/q赋值为链表的下一个结点赋值为链表的下一个结点while(q!=null)/利用循环查找正确位置利用循环查找正确位置/判断当前结点判断当前结点num是否小于是否小于p结点的结点的numif(q-num num)r=q;/r赋值为赋值为q，即指向，即指向q所指的结点所指的结点q=q-next;/q指向链表中相邻的下一个结点指向链表中相邻的下一个结点else/找到了正确的位置找到了正确的位置break;/退出循环退出循环/将将p结点插入正确的位置结点插

45、入正确的位置r-next=p;p-next=q;46火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去/被调用函数，形参为被调用函数，形参为ST结构指针结构指针，用于输出链表内容，用于输出链表内容void print(struct numST*head)int k=0;/整型变量，用于计数整型变量，用于计数struct numST*r;/声明声明r为为ST结构指针结构指针r=head;/r赋值为赋值为head，即指向，即指向链表头链表头 while(r!=null)/当型循环，链表指针不为空当型循环，链表指针不为空则继续则继续/循环体开

46、始循环体开始k=k+1;/计数加计数加1printf(%d%dn,k,r-num);r=r-next;/取链表中相邻的下一个结点取链表中相邻的下一个结点/循环体结束循环体结束47火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去void main()/主函数开始主函数开始/函数体开始函数体开始struct numST*head,*p;/ST型结构指针型结构指针head=null;/分配两个分配两个ST结构的内存空间，用于构造链表结构的内存空间，用于构造链表head=(struct numST*)malloc(LEN);head-next

47、=(struct numST*)malloc(LEN);/为链表中的两个结点中的为链表中的两个结点中的num赋值为赋值为5和和10head-num=5;head-next-num=10;head-next-next=null;/链表尾赋值为空链表尾赋值为空/构造一个结点构造一个结点p，用于插入链表，用于插入链表p=(struct numST*)malloc(LEN);p-num=8;p-next=null;insert(&head,p);/调用调用create函数建立链表，函数建立链表，print(head);/调用调用print函数，输出链表内容函数，输出链表内容/主函数结束主函数结束48火

48、灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去说明：说明：函数函数insert()的第一个形参为的第一个形参为struct numST*类型，即类型，即“指针的指针指针的指针”。调用时送入的实参是。调用时送入的实参是链表头指针的地址，即程序中的链表头指针的地址，即程序中的&head。这样对。这样对head的修改才会在函数返回后仍有效。如果形参的修改才会在函数返回后仍有效。如果形参为为struct numST*，则传入的为指针，当函数返回，则传入的为指针，当函数返回后，后，head无法改变。无法改变。49火灾袭来时要迅速疏散逃生，不可蜂

49、拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去11.8 11.8 共用体共用体 构造类型之二构造类型之二联合联合在同一存储单元里，根据需要放不同类型的数据，在同一存储单元里，根据需要放不同类型的数据，使用覆盖技术。使用覆盖技术。50火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去11.8.1 11.8.1 概念概念单元起始地址：单元起始地址：1000 1000。三个变量（数据）占用同。三个变量（数据）占用同一单元：一单元：1000 1000 1003 1003浮点型（浮点型（4 byte）字符型（字符型（

50、1 byte）整型（整型（2Byte）51火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去共用体变量的定义共用体变量的定义格式（一般形式）：格式（一般形式）：union union 联合类型名联合类型名 成员列表成员列表 变量列表；变量列表；11.8.2 11.8.2 共用体变量的引用方式共用体变量的引用方式同结构类型变量的引用格式：同结构类型变量的引用格式：变量名变量名.成员名成员名52火灾袭来时要迅速疏散逃生，不可蜂拥而出或留恋财物，要当机立断，披上浸湿的衣服或裹上湿毛毯、湿被褥勇敢地冲出去格式与结构类型的定义和变量声明形式格式与