C语言链表详解PPT

《C语言链表详解PPT》由会员分享，可在线阅读，更多相关《C语言链表详解PPT（91页珍藏版）》请在金锄头文库上搜索。

1、第十一章 链表链表详解珍藏版1结构的概念与应用结构的概念与应用2依上图有依上图有7个结点个结点(x1,y1)(x1,y1)(x2,y2)(x2,y2)(x6,y6)(x6,y6)(x7,y7)(x7,y7)311.7 用指用指针处理理链表表链表是程序表是程序设计中一种重要的中一种重要的动态数据数据结构，构，它是它是动态地地进行存行存储分配的一种分配的一种结构。构。动态性体现为：动态性体现为：n链表中的元素个数可以根据需要增加和减少，不链表中的元素个数可以根据需要增加和减少，不像数组，在声明之后就固定不变；像数组，在声明之后就固定不变；n元素的位置可以变化，即可以从某个位置删除，元素的位置可以变

2、化，即可以从某个位置删除，然后再插入到一个新的地方；然后再插入到一个新的地方；412491249 A A13561356 B B14751475 C C10211021 D DNullNull1 1、链表中的元素称为、链表中的元素称为“结点结点”，每个结点包括两，每个结点包括两个域：个域：数据域和指针域；数据域和指针域；2 2、单向链表通常由一个头指针（、单向链表通常由一个头指针（head)head)，用于指向，用于指向链表头；链表头；3 3、单向链表有一个尾结点，该结点的指针部分指、单向链表有一个尾结点，该结点的指针部分指向一个空结点向一个空结点(NULL) (NULL) 。Head 124

3、9 1356 1475 1021结点里的指针是存放下一个结点的地址5链表中表中结点的定点的定义q链表是由表是由结点构成的，点构成的， 关关键是定是定义结点点;q链表的表的结点定点定义打破了先定打破了先定义再使用的限制再使用的限制,即可以用自己定即可以用自己定义自己；自己；q递归函数的定函数的定义也也违反了先定反了先定义再使用；再使用；这是是C语言程序言程序设计上的两大特例上的两大特例6链表的基本操作表的基本操作对链表的基本操作有：表的基本操作有：（1）创建建链表表是是指指，从从无无到到有有地地建建立立起起一一个个链表表，即即往往空空链表表中中依依次次插插入入若若干干结点点，并并保保持持结点点之

4、之间的前的前驱和后和后继关系。关系。（2）检索操作索操作是指，按是指，按给定的定的结点索引号或点索引号或检索索条件，条件，查找某个找某个结点。如果找到指定的点。如果找到指定的结点，点，则称称为检索成功；否索成功；否则，称，称为检索失索失败。（3）插插入入操操作作是是指指，在在结点点ki-1与与ki之之间插插入入一一个个新新的的结点点k，使使线性性表表的的长度度增增1，且且ki-1与与ki的的逻辑关系关系发生如下生如下变化：化：插插入入前前，ki-1是是ki的的前前驱，ki是是ki-1的的后后继；插插入入后后，新插入的新插入的结点点k成成为ki-1的后的后继、ki的前的前驱.7（4）删除除操操作

5、作是是指指，删除除结点点ki，使使线性性表表的的长度度减减1，且且ki-1、ki和和ki+1之之间的的逻辑关关系系发生生如如下下变化：化：删除前，除前，ki是是ki+1的前的前驱、ki-1的后的后继；删除后，除后，ki-1成成为ki+1的前的前驱，ki+1成成为ki-1的后的后继.(5)打印打印输出出8一个指一个指针类型的成型的成员既可指向其它既可指向其它类型的型的结构体数构体数据，也可以指向自己所在的据，也可以指向自己所在的结构体构体类型的数据型的数据991019910189.589.59910399103909099107991078585numScorenextnext是是struct

6、student类型中的一个成员，类型中的一个成员，它又它又指向指向struct student类型类型的数据。的数据。换名话说：换名话说：next存放下一个结点的地址存放下一个结点的地址911.7.2 简单链表表#define NULL 0struct 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

7、; 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 11.7.3 处理理动态链表所需的函数表所需的函数C C 语言使用系统函数语言使用系统函数动态动态开辟和释放存储单元开辟和释放存储单元1.malloc 1.mall

8、oc 函数函数 函数原形：函数原形：void *malloc(unsigned int size);void *malloc(unsigned int size);作用：作用：在内存的动态存储区中分配在内存的动态存储区中分配 一个一个 长度为长度为sizesize的连续空间。的连续空间。返回值：返回值：是一个指向分配域起始地址的指针（基本是一个指向分配域起始地址的指针（基本类型类型voidvoid）。）。执行失败：执行失败：返回返回NULLNULL11函数原形函数原形:void *calloc(unsigned n,unsigned size);作用：作用：在内存在内存动态区中分配区中分配 n

9、个个 长度度为size的的连续空空间。函数返回函数返回值：指向分配域起始地址的指：指向分配域起始地址的指针执行失行失败：返回：返回null主要用途主要用途：为一一维数数组开辟开辟动态存存储空空间。n 为数数组元素个数，每个元素元素个数，每个元素长度度为size2. calloc2. calloc 函数函数123. free 函数函数函数原形：函数原形： void free(void *p);作用：作用：释放由放由 p 指向的内存区。指向的内存区。P:是最近一次是最近一次调用用 calloc 或或 malloc 函数函数时返回的返回的值。free 函数无返回函数无返回值动态分配的存分配的存储单元

10、在用完后一定要元在用完后一定要释放，放，否否则内存会因申内存会因申请空空间过多引起多引起资源不足源不足而出而出现故障。故障。13结点的点的动态分配分配ANSI C 的三个函数的三个函数(头文件文件 malloc.h) void *malloc(unsigned int size)void *calloc(unsigned n, unsigned size)void free(void *p)C+ 的两个函数的两个函数new 类型（初型（初值） delete 指指针变量量/* 表示表示释放数放数组，可有可无），可有可无）* */使用使用 new 的的优点：点：可以通可以通过对象的大小直接分配，而

11、不管象的大小直接分配，而不管对象的象的具体具体长度是多少（度是多少（p340 例例14.10）1411.7.4 建立建立动态链表表基本方法基本方法: 三个三个结点（点（头结点点head、尾、尾结点点 NULL 和待插入和待插入结点点 P）第一步：定第一步：定义头结点点head、尾、尾结点点 p2 和待插入和待插入结点点p1，待插入的，待插入的结点数据部分初始化；点数据部分初始化；第二步：第二步：该结点被点被头结点、尾点、尾结点同点同时指向指向。P1=p2=(struct student*)malloc(LEN);头指指针部分部分为空空，head=NULL; 第三步：重复申第三步：重复申请待插入

12、待插入结点空点空间，对该结点的数据部点的数据部分分赋值（或（或输入入值），将），将该结点插入在最前面，或者最点插入在最前面，或者最后面（后面（书上在尾部插入）上在尾部插入）. P2-next=P1; P2=P1; 最后最后:P2-next=NULL;*head,*p1,*p2*head,*p1,*p2使用使用malloc(LEN)malloc(LEN)P2-next=NULL;1511.7.4 建立建立动态链表表991019910189.589.5headP1p21. .任务是开辟结点和输入数据任务是开辟结点和输入数据2.2.并建立前后相链的关系并建立前后相链的关系待插入的结点待插入的结点p1

13、p1数数据部分初始化据部分初始化, ,该结该结点被头结点点被头结点head、尾结点尾结点p2同时指向同时指向.16图11.14991019910189.589.5headp299103991039090p1991019910189.589.5headp299103991039090p1(a)(b)p1重复申请待插入重复申请待插入结点空间，对该结结点空间，对该结点的数据部分赋值点的数据部分赋值（或输入值）（或输入值）P2-next P2-next 指向指向p1p1新开辟的结点。新开辟的结点。17图11.14head991019910189.589.5p1p299103991039090(c)P2

14、P2指向新结指向新结点点p2=p1p2=p118图11.15991019910189.589.5991019910189.589.5p299107991078585p1head991019910189.589.5991019910189.589.5p299107991078585p1head(a)(b)19 图11.169910399103909099107991078585p20 00 0p1head991019910189.589.59910399103909099107991078585NULLNULLp20 00 0p1head991019910189.589.520例例11.8 建立

15、一个有建立一个有3名学生数据的名学生数据的单向向动态链表表#define 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

16、;结构体类型数据的长度，结构体类型数据的长度，sizeofsizeof是是“字节数运算符字节数运算符”定义指针类型的函数。带回链表的起始地址定义指针类型的函数。带回链表的起始地址开辟长度为开辟长度为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*)mal

17、loc(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继续开辟新结点继续开辟新结点给新

18、结点赋值此给新结点赋值此2211.7.5 输出出链表表链表遍表遍历1.单向向链表表总是从是从头结点开始的；点开始的；2.每每访问一个一个结点，就将当前指点，就将当前指针向向该结点的下一个点的下一个结点移点移动：p=p-next;3.直至下一直至下一结点点为空空P=NULL23图 11.18headp PPNULLNULL24void 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,

19、p - num,p - score); p=p - next; while(p!=NULL); 2511.7.6 对链表的表的删除操作除操作删除除结点原点原则：不改不改变原来的排列原来的排列顺序，只是从序，只是从链表中分离开来，表中分离开来，撤消原来的撤消原来的链接关系。接关系。两种情况：两种情况：1、要、要删的的结点是点是头指指针所指的所指的结点点则直接操作；直接操作；2、不是、不是头结点，要依次往下找。点，要依次往下找。另外要考另外要考虑：空表和找不到要：空表和找不到要删除的除的结点点26链表中表中结点点删除除需要由两个需要由两个临时指指针：P1: 判断指向的判断指向的结点是不是要点是不是

20、要删除的除的结点点（用于（用于寻找）；找）；P2: 始始终指向指向P1的前面一个的前面一个结点；点；27图11.19ABDECABDEC(a) (B)28图11.209910199101headp199103991039910799107NULLNULL（a）(b)9910199101head99103991039910799107NULLNULLp2p1原链表原链表P1指向指向头结点头结点P2指向指向p1指向的结指向的结点。点。P1指指向下移一向下移一个结点。个结点。29图11.209910199101head99103991039910799107NULLNULLp19910199101h

21、ead99103991039910799107NULLNULLp2p1(c)(d)经判断后，第经判断后，第1个个结点是要删除的结点是要删除的结点，结点，head指向指向第第2个结点，第个结点，第1个结点脱离。个结点脱离。经经P1P1找到要删找到要删除的结点后使除的结点后使之脱离。之脱离。30struct 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

22、-next!=NULL) p2=p1; p1=p1-next; 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); 找到了找到了没找到没找到3111.7.7 对链表的插入操作表的插入操作插入插入结点：将一个点：将一个结点插入到已有的点插入到已有的链表中表中插入原插入原则：1、插入操作不、插入操作不应破坏原破坏原链接关系接关系2、插入的、插入的结

23、点点应该在它在它该在的位置在的位置实现方法：方法：应该有一个插入位置的有一个插入位置的查找子找子过程程共有三种情况：共有三种情况：1、插入的、插入的结最小最小2、插入的、插入的结点最大点最大3、插入的、插入的结在中在中间32 操操作作分分析析同同删除一除一样，需要几个，需要几个临时指指针：P0: 指向待插的指向待插的结点点;初始化：初始化：p0=数数组stu;P1: 指向要在指向要在P1之前插入之前插入结点；初始化点；初始化: p1=head;P2: 指向要在指向要在P2之后插入之后插入结点；点；插入操作：当符合以下条件插入操作：当符合以下条件时：p0-num 与与 p1-num 比比较找位找

24、位置置if(p0-nump1-num)&(p1-next!=NULL) 则插入的结点不在则插入的结点不在p1所指结点之前；指针后移，交给所指结点之前；指针后移，交给p2； p1= p1-next; p2=p1;则继续与则继续与 p0 指向的数组去比，直到指向的数组去比，直到（p1-next!=NULL)为止。为止。否否则有两种情况有两种情况发生：生：if(head=p1) head=p0;p0-next=p1插到原来第一个插到原来第一个结点点之前之前；else p2-next=p0;p0-next=p1; 插到插到 p2 指向的结点指向的结点之后之后；还有另外一种情况：插到还有另外一种情况：插

25、到最后最后的结点之后；的结点之后；p1-next=p0;p0-next=NULL;33图11.229910199101headp199103991039910799107NULLNULL（a）9910299102p034图11.229910199101head99103991039910799107NULLNULL9910299102p0p2p1(b)35struct student insert(struct student *head,struct student *stud) struct student *p0,*p1,*p2; p1=head; p0=stud; if( head=N

26、ULL; ) 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; return(head); 原来的链表是空表原来的链表是空表P0P0指向要插的结点指向要插的结点使使p0p0指向的结点作为头结点指向的结点作为头结点使使p2指向刚才指向刚才p1指向的结点指向的结点插到原来第一个结点

27、之前插到原来第一个结点之前插到插到p2指向的结点之后指向的结点之后插到最后的结点之后插到最后的结点之后链接365 5head6 610101515null12128 8课堂举例：课堂举例：已有一个如图所示的链表；已有一个如图所示的链表；它是按结点中的整数域从小到大排序的，现在要插它是按结点中的整数域从小到大排序的，现在要插入一个结点，该结点中的数为入一个结点，该结点中的数为1010待插入结点待插入结点此结点已插入链表此结点已插入链表37分析：分析：按三种情况按三种情况1 1、第一种情况，链表还未建成（空链表），待插入结点、第一种情况，链表还未建成（空链表），待插入结点p p实际上是第一个结点。

28、这时必然有实际上是第一个结点。这时必然有head=nullhead=null。只要。只要让头指针指向让头指针指向 p p 就可以了。语句为就可以了。语句为6nullheadphead = p;p-next = null;2 2、第二种情况，链表已建成，待插入结点、第二种情况，链表已建成，待插入结点 p p 的数据要的数据要比头结点的数据还要小，这时有比头结点的数据还要小，这时有( (p-num )num)p-num )num)当然当然p p结点要插在结点要插在headhead结点前。结点前。386head8512nullheadpp-next=head;head=p;语句为语句为null393

29、 3、第三种情况，链表已建成，待插入结点、第三种情况，链表已建成，待插入结点 p p 的数据比头结点的数据大，需要找到正确的的数据比头结点的数据大，需要找到正确的插入位置。这时，可以借助两个结构指针插入位置。这时，可以借助两个结构指针r r 和和 g g，利用循环比较来找到正确位置。然后，利用循环比较来找到正确位置。然后将结点将结点 p p 插入到链表中正确的位置。插入到链表中正确的位置。参见下面的图示参见下面的图示406head81213nullp15gr说明：说明：这种情况下，这种情况下，p p 结点已经与链表的第一个结点结点已经与链表的第一个结点比较过了，所以从链表的下一个结点开始比较。

30、比较过了，所以从链表的下一个结点开始比较。138138，继续比较。，继续比较。416head81213nullp15gr说明：说明：13121312，继续比较。，继续比较。426head81213p15grnull说明：说明：131513next = p;p-next = g;43/ 结构结构7.c#include #include / / 预编译命令预编译命令#include #include / / 内存空间分配内存空间分配#define null 0#define null 0/ / 定义空指针常定义空指针常量量#define LEN sizeof(struct numST)#defin

31、e LEN sizeof(struct numST)/ / 定义常量，定义常量，表示结构长度表示结构长度struct numSTstruct numST/ / 结构声明结构声明 int num;int num;/ / 整型数整型数struct numST *next;struct numST *next;/ numST/ numST结构指针结构指针;参考程序参考程序44/ 被调用函数被调用函数insert()，两个形参分别表示链表和待插入的结点，两个形参分别表示链表和待插入的结点void insert (struct numST *phead, struct numST *p)/ 函数体开始函

32、数体开始struct numST *q,*r;/ 定义结构指针定义结构指针q,rif (*phead)=null)/ 第一种情况第一种情况，链表为空，链表为空*phead = p;/ 链表头指向链表头指向preturn;/ 完成插入操作，返回完成插入操作，返回else/ 链表不为空链表不为空/ 第二种情况第二种情况，p结点结点num值小于链表头结点的值小于链表头结点的num值值if ( (*phead)-num p-num) / 将将p结点插到链表头部结点插到链表头部 p-next = *phead;/ 将将p的的next指针指向链表头指针指向链表头(*phead) *phead = p;/

33、将链表头赋值为将链表头赋值为p return;/ 返回返回45/ 第三种情况第三种情况，循环查找正确位置，循环查找正确位置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/

34、找到了正确的位置找到了正确的位置break;/ 退出循环退出循环/ 将将p结点插入正确的位置结点插入正确的位置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)/ 当型循环，链表指针不为空当型循环，链表指针不为空则

35、继续则继续/ 循环体开始循环体开始k=k+1;/ 计数加计数加1printf(%d %dn,k,r-num); r=r-next;/ 取链表中相邻的下一个结点取链表中相邻的下一个结点/ 循环体结束循环体结束47void main()/ 主函数开始主函数开始/ 函数体开始函数体开始struct numST *head, *p;/ ST型结构指针型结构指针head = null;/ 分配两个分配两个ST结构的内存空间，用于构造链表结构的内存空间，用于构造链表head = (struct numST *) malloc(LEN);head-next = (struct numST *) malloc

36、(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说

37、明：说明：函数函数insert()的第一个形参为的第一个形参为struct numST*类型，即类型，即“指针的指针指针的指针”。调用时送入的实参是。调用时送入的实参是链表头指针的地址，即程序中的链表头指针的地址，即程序中的&head。这样对。这样对head的修改才会在函数返回后仍有效。如果形参的修改才会在函数返回后仍有效。如果形参为为struct numST*，则传入的为指针，当函数返回，则传入的为指针，当函数返回后，后，head无法改变。无法改变。4911.8 11.8 共用体共用体 构造类型之二构造类型之二联合联合在同一存储单元里，根据需要放不同类型的数据，在同一存储单元里，根据需要放不

38、同类型的数据，使用覆盖技术。使用覆盖技术。5011.8.1 概念概念单元起始地址：元起始地址：1000 。三个。三个变量（数据）占用同量（数据）占用同一一单元：元：1000 1003浮点型（浮点型（4 byte）字符型（字符型（1 byte）整型（整型（2Byte）51共用体共用体变量的定量的定义格式（一般形式）：格式（一般形式）：union 联合合类型名型名 成成员列表列表 变量列表；量列表；11.8.2 11.8.2 共用体变量的引用方式共用体变量的引用方式同结构类型变量的引用格式：同结构类型变量的引用格式： 变量名变量名. .成员名成员名52格式与格式与结构构类型的定型的定义和和变量声明

39、形式量声明形式上上类似，但似，但实质上有区上有区别：1.1.结构构类型的型的长度度=各成各成员的的长度和；各度和；各成成员占独立的存占独立的存储单元，不共享；元，不共享；2.2.联合合类型的型的长度度为成成员中中长度的最大者，度的最大者，各成各成员共享共享长度最大的存度最大的存储单元；元；5311.8.3 共用体共用体类型数据的特点型数据的特点54struct int num; char name10; char sex; char job; union int class; char position10; category; person2;main() int n,i; for(i=0;

40、i2 ;i+); scanf(%d，%s，%c，%c”, &personi.num,personi.name,&personi.sex,&personi.job);55 if(personi.job=s) scanf(%d,&personi.category.class); else if(personi.job=t) scanf(%s,personi.category.position); else printf(input error!); printf(n); printf(no. name sex job class/positionn);for(i=0;iSun、Sat最大。最大。（

41、4）枚枚举元元素素的的值也也是是可可以以人人为改改变的的：在在定定义时由由程程序指定。序指定。例例如如，如如果果enum weekdays Sun=, Mon ,Tue, Wed, Thu, Fri, Sat；则Sun=，Mon=，从从Tue=2开始，依次增。开始，依次增。60/*file1.c文件文件1*/main() extern enter-string(char str80); extern delete-string(char str,char ch); extern print-string(char str); char c; char str80; enter_string(s

42、tr); scanf(%c,&c); delete_string(str,c); print_string(str);/* file2.c 文件文件2*/#includeenter_string(char str80)gets(str);61for(i=0;i2;i+) if(personi.job=s) printf(%-6d %-10s %-3c %-3c %-6dn,personi.num,personi.name,personi. sex,personi.job,personi.category.class); else printf(%-6d %-10s %-3c %-3c %-6s

43、n,personi.num,personi.name,personi. sex,personi.job,personi.category.position); 6211.10 用用typedef 为类型定型定义新名字新名字 除可直接使用提供的除可直接使用提供的标准准类型和自定型和自定义的的类型型（结构、共用、枚构、共用、枚举）外，也可使用）外，也可使用typedef定定义已有已有类型的型的别名。名。该别名与名与标准准类型名一型名一样，可用来定，可用来定义相相应的的变量。量。定定义已有已有类型型别名的方法如下：名的方法如下：（1）按定）按定义变量的方法，写出定量的方法，写出定义体；体；（2）将）

44、将变量名量名换成成别名；名；（3）在定）在定义体最前面加上体最前面加上typedef。 6311.10 用用typeded 为类型定型定义新名字新名字任何已有的任何已有的类型可以重新命名型可以重新命名typedef long integer; /将将 long 重新命名重新命名为 integer，使得，使得 integer 和和 long 同等使用同等使用 可以和新可以和新类型定型定义一起定一起定义名字名字typedef int ARR10 ; / 定定义了一个数了一个数组名名 ARR，它是具有，它是具有10个元素的整型个元素的整型数数组类型型typedef struct int num;fl

45、oat score; S; /*定定义结构体构体别名名为S*/STUDENT stu1;64讨论：typedef 和和 #define说明明：（1）用用typedef只只是是给已已有有类型型增增加加个个别名名，并并不不能能创造造个个新新的的类型型。就就如如同同人人一一样，除除学学名名外外，可可以以再再取取一一个个小小名名（或或雅雅号号），但但并并不能不能创造出另一个人来。造出另一个人来。（2）typedef与与#define有有相相似似之之处，但但二二者者是是不不同同的的：前前者者是是由由编译器器在在编译时处理理的的；后后者者是是由由编译预处理理器器在在编译预处理理时处理理的的，而且只能作而且

46、只能作简单的字符串替的字符串替换。65struct TMint x,y; / 结构结构TM的成员，的成员，x,y为整数型为整数型struct TM next / 结构结构TM的成员，属的成员，属TM型型下面的表是马的跳步方案，从左下角跳到右上角下面的表是马的跳步方案，从左下角跳到右上角结点n1n2n3n4n5n6n7xy00122443647284结构体与共体例子668 84 4NULLNULLNULL为空地址为空地址下面是形成链表的一个参考程序下面是形成链表的一个参考程序2 24 4&n41 12 2&n30 00 0&n2&n1head67/ 结构结构1.c#include / 预编译命令

47、预编译命令#define null 0/ 定义空指针常量定义空指针常量struct TM/ 定义结构定义结构TMint x,y;/ 整型变量整型变量x,ystruct TM next;/ 指向指向TM结构的指针结构的指针;void main()/ 主函数主函数/ 主函数开始主函数开始 int i;/ 声明整型变量声明整型变量 / 声明声明TM结构结构n1n7,结构指针结构指针head,p struct TM n1,n2,n3,n4,n5,n6,n7, head, p; 68 / 分别对分别对TM结构结构n1n7中的中的x,y赋赋值值 n1.x=0;n1.y=0; n2.x=1;n2.y=2;

48、n3.x=2;n3.y=4; n4.x=4;n4.y=4; n5.x=6;n5.y=4; n6.x=7;n6.y=2; n7.x=8;n7.y=4; / head赋值为赋值为n1，即，即head指向指向n1 head=&n1; / n1n7构成链表构成链表 n1.next=&n2; n2.next=&n3; n3.next=&n4; n4.next=&n5; n5.next=&n6; n6.next=&n7; / n7的的next指针赋值为空指针指针赋值为空指针 n7.next=null;69p=head;p=head;/ p/ p赋值为赋值为headhead，即，即p p指向指向headhe

49、ad所指的所指的内容内容i=1;i=1;/ i/ i赋值为赋值为1 1dodo/ / 直到型循环直到型循环 / / 循环体开始循环体开始/ / 输出结点信息输出结点信息printf(printf(结点结点%d: x=%d, y=%dn,i,p-x,p-%d: x=%d, y=%dn,i,p-x,p-y);y); p=p-next;p=p-next;/ p/ p指向下一个结指向下一个结点点 i=i+1;i=i+1;/ / 计数加计数加1 1 while(p!=null); while(p!=null);/ / 未到达链表尾部，则未到达链表尾部，则继续循环继续循环 / / 主函数结束主函数结束70

50、用结构数组，利用键盘输入结点中的数据。重用结构数组，利用键盘输入结点中的数据。重点看点看scanf(scanf(“%d%d”,&a);,&a);ni.x=a;ni.x=a;结构数组，数组中的元素为结构类型的数据，结构数组，数组中的元素为结构类型的数据，如如n8n8/ 结构结构2.c#include / 预编译命令预编译命令#define null 0/ 定义空指针常量定义空指针常量struct TM/ 定义定义TM结构结构int x,y;/ 整型变量整型变量x,ystruct TM *next;/ 指向指向TM结构的指针结构的指针;71void main()/ 主函数主函数/ 主函数开始主函数

51、开始 int i,a,b;/ 声明整型变量声明整型变量i,a,b / 声明声明TM型结构数组型结构数组n8，TM结构指针结构指针head,p struct TM n8,*head,*p; for(i=1;i=7;i=i+1)/ 循环循环/ 循环体开始循环体开始 printf(输入输入n%d的的xn,i); / 提示输入第提示输入第i个结构的个结构的x值值 scanf(%d,&a);/ 输入输入a ni.x=a;/ 将将a的值赋给结构的值赋给结构ni的元素的元素x printf(输入输入n%d的的yn,i); / 提示输入第提示输入第i个结构的个结构的y值值 scanf(%d,&b);/ 输入输

52、入b ni.y=b;/ 将将b的值赋给结构的值赋给结构ni的元素的元素y/ 循环体结束循环体结束72head=&n1;/ 链表头部指向链表头部指向n1for(i=1;ix,p-y); p=p-next;/ p指向相邻的下一个结点指向相邻的下一个结点 i=i+1;/ 计数计数i加加1 while(p!=null);/ 未到链表尾部，则继续循环未到链表尾部，则继续循环/ 主函数结束主函数结束73下面的程序与上面的程序区别仅在下面的程序与上面的程序区别仅在scanf(“%d”,&(ni.x);去替换去替换scanf(“%d”,&a);ni.x=a;/ 结构结构3.c#include / 预编译命令预

53、编译命令#define null 0/ 定义空指针常量定义空指针常量struct TM/ 定义定义TM结构结构int x,y;/ 整型变量整型变量x,ystruct TM *next;/ 指向指向TM结构的指针结构的指针;74void main()/ 主函数主函数/ 主函数开始主函数开始 int i,a,b;/ 声明整型变量声明整型变量i,a,b / 声明声明TM型结构数组型结构数组n8，TM结构指针结构指针head,p struct TM n8,*head,*p; for(i=1;i=7;i=i+1)/ 循环循环/ 循环体开始循环体开始 printf(输入输入n%d的的xn,i); / 提示

54、输入第提示输入第i个结构的个结构的x值值 scanf(%d,&(ni.x);/ 输入输入ni.x printf(输入输入n%d的的yn,i); / 提示输入第提示输入第i个结构的个结构的y值值 scanf(%d,&(ni.y);/ 输入输入ni.y/ 循环体结束循环体结束75head=&n1;/ 链表头部指向链表头部指向n1for(i=1;inum赋值为赋值为1，让，让指针域赋值为指针域赋值为null。之后让链头指针。之后让链头指针head指向第指向第1个结点。个结点。利用指针利用指针q记住这个结点，以便让指针记住这个结点，以便让指针p去生成下面的结点。去生成下面的结点。（2）利用一个计数循环

55、结构，做出第）利用一个计数循环结构，做出第2个结点到第个结点到第nn个结点。个结点。并将相邻结点一个接一个链接到一起。并将相邻结点一个接一个链接到一起。（3）最后一个结点要和头结点用下一语句链接到一起）最后一个结点要和头结点用下一语句链接到一起tail = q; tail-next = head;headtailq835、删结点的函数、删结点的函数select(int mm)mm为形式参数，从为形式参数，从1至至m报数，凡报到报数，凡报到mm者删除其者删除其所在的结点。所在的结点。设计两个指针设计两个指针p和和q。一开始让。一开始让q指向链表的尾部指向链表的尾部q=tail。让让p指向指向q的

56、下一个结点。开始时让的下一个结点。开始时让p指向指向1#猴所在的结点。猴所在的结点。用一个累加器用一个累加器x，初始时，初始时x=0，从，从1#猴所在结点开始让猴所在结点开始让x=x+1=1，如果，如果mm是是1的话，的话，1#猴所在的猴所在的p结点就要被删结点就要被删除。有三条语句除。有三条语句printf(“被删掉的猴子号为被删掉的猴子号为%d号号n”,p-num);q-next = p-next;free(p);1 1head2 28 8tailqp演示演示84这里这里free(p)是释放是释放p结点所占用的内存空间的语句。结点所占用的内存空间的语句。如果如果mm不是不是1而是而是3，程

57、序会在，程序会在do-while循环中，循环中，让让x加两次加两次1，q和和p一起移动两次，一起移动两次，p指向指向3#所在结所在结点，点，q指向指向2#所在结点，之后仍然用上述三条语句所在结点，之后仍然用上述三条语句删去删去3#所在的结点。所在的结点。1 1head2 28 8qp3 34 4q ppq演示演示85这个这个do-while循环的退出条件是循环的退出条件是q=q-next。即当只。即当只剩下一个结点时才退出循环。当然猴王非其莫属了。剩下一个结点时才退出循环。当然猴王非其莫属了。这时，让头指针这时，让头指针head指向指向q，head是全局变量，在是全局变量，在主程序最后输出猴王

58、时要用主程序最后输出猴王时要用head-num。参考程序如下：参考程序如下：7 7headq86#include / 预编译命令预编译命令#include / 内存空间分配内存空间分配#define null 0/ 定义空指针常量定义空指针常量/ 定义常量，表示结构长度定义常量，表示结构长度#define LEN sizeof(struct mon)struct mon/ 结构声明结构声明int num;/ 整型数，用于记录猴子号整型数，用于记录猴子号struct mon *next;/ mon结构指针结构指针;struct mon *head, *tail;/ mon结构指针，全局变量结构指

59、针，全局变量87void create(int nn)/ 被调用函数被调用函数/ 函数体开始函数体开始 int i;/ 整型变量整型变量i，用于计数，用于计数struct mon *p,*q;/ 声明声明mon结构指针结构指针p，q/ 为为p分配内存空间分配内存空间p=(struct mon *) malloc(LEN);p-num=1;/ 初始化初始化p结点结点num域为域为1p-next=null;/ 初始化初始化p结点结点next域为空域为空head=p;/ 链表头指针链表头指针head赋值为赋值为pq=p;/ q赋值为赋值为p88for(i=2;inum=i; / 初始化初始化p结点结

60、点num域为域为i，表示猴子号，表示猴子号q-next=p;/ 将将p结点加到链表尾部结点加到链表尾部q=p;/ 让让q指向链表尾部结点指向链表尾部结点p-next=null;/ 链表尾部指向空链表尾部指向空/ 循环体结束循环体结束tail = q;/ 链表尾链表尾tail-next=head;/ 链表尾部指向链表头，链表尾部指向链表头，/ 形成循环链表形成循环链表/ 函数体结束函数体结束89/ 被调用函数被调用函数select，mm表示结点删除间隔表示结点删除间隔void select(int mm)/ 函数体开始函数体开始int x=0;/ 声明整型值声明整型值x，并初始化为，并初始化为0

61、struct mon *p,*q;/ 声明结构指针声明结构指针p，qq=tail;/ q赋值为赋值为tail，指向循环链表尾部，指向循环链表尾部 do/ 直到型循环，用于循环删除指定间隔的结点直到型循环，用于循环删除指定间隔的结点/ 循环体开始循环体开始p=q-next;/ p赋值为赋值为q相邻的下一个结点相邻的下一个结点x=x+1;/ x加加1if(x % mm=0)/ x是否整除是否整除mm，/ 表示是否跳过指定间隔表示是否跳过指定间隔/ 输出被删掉的猴子号输出被删掉的猴子号printf(被删掉的猴子号为被删掉的猴子号为%d号号n,p-num);q-next=p-next;/ 删除此结点删

62、除此结点free(p);/ 释放空间释放空间else q=p;/ q指向相邻的下一个结点指向相邻的下一个结点pwhile(q!=q-next);/ 剩余结点数不为剩余结点数不为1，则继续循环，则继续循环head = q;/ head指向结点指向结点q，q为链表中剩余一个结点为链表中剩余一个结点/ 函数体结束函数体结束90void main()/ 主函数开始主函数开始/ 函数体开始函数体开始int n,m;/ 声明整型变量声明整型变量n,mhead = null;/ 初始化初始化head为空为空 printf(请输入猴子数请输入猴子数n); / 提示信息提示信息scanf(%d,&n);/ 输入待插入结点数据输入待插入结点数据printf(请输入间隔请输入间隔mn); / 提示信息提示信息scanf(%d,&m);/ 输入间隔输入间隔 create(n);/ 调用函数调用函数create建立循环链表建立循环链表select(m);/ 调用函数调用函数select，找出剩下的猴，找出剩下的猴子子printf(猴王是猴王是%d号号n,head-num); / 输出猴王输出猴王/ 函数体结束函数体结束91