语言链表详解ppt课件.ppt

《语言链表详解ppt课件.ppt》由会员分享，可在线阅读，更多相关《语言链表详解ppt课件.ppt（91页珍藏版）》请在三一办公上搜索。

1、1,第十一章 链表链表详解珍藏版,2,例：跳马。依下图将每一步跳马之后的位置(x,y)放到一个“结点”里，再用“链子穿起来”，形成一条链，相邻两结点间用一个指针将两者连到一起。,结构的概念与应用,3,依上图有7个结点,为了表示这种既有数据又有指针的情况，引入结构这种数据类型。,4,11.7 用指针处理链表,链表是程序设计中一种重要的动态数据结构，它是动态地进行存储分配的一种结构。,动态性体现为：链表中的元素个数可以根据需要增加和减少，不像数组，在声明之后就固定不变；元素的位置可以变化，即可以从某个位置删除，然后再插入到一个新的地方；,5,1、链表中的元素称为“结点”，每个结点包括两个域：数据域

2、和指针域；2、单向链表通常由一个头指针（head)，用于指向链表头；3、单向链表有一个尾结点，该结点的指针部分指向一个空结点(NULL) 。,Head 1249 1356 1475 1021,结点里的指针是存放下一个结点的地址,6,链表中结点的定义,链表是由结点构成的， 关键是定义结点;链表的结点定义打破了先定义再使用的限制,即可以用自己定义自己；递归函数的定义也违反了先定义再使用；这是C语言程序设计上的两大特例,7,链表的基本操作,对链表的基本操作有：（1）创建链表是指，从无到有地建立起一个链表，即往空链表中依次插入若干结点，并保持结点之间的前驱和后继关系。（2）检索操作是指，按给定的结点索

3、引号或检索条件，查找某个结点。如果找到指定的结点，则称为检索成功；否则，称为检索失败。（3）插入操作是指，在结点ki-1与ki之间插入一个新的结点k，使线性表的长度增1，且ki-1与ki的逻辑关系发生如下变化：插入前，ki-1是ki的前驱，ki是ki-1的后继；插入后，新插入的结点k成为ki-1的后继、ki的前驱.,8,（4）删除操作是指，删除结点ki，使线性表的长度减1，且ki-1、ki和ki+1之间的逻辑关系发生如下变化：删除前，ki是ki+1的前驱、ki-1的后继；删除后，ki-1成为ki+1的前驱，ki+1成为ki-1的后继.(5)打印输出,9,一个指针类型的成员既可指向其它类型的结构

4、体数据，也可以指向自己所在的结构体类型的数据,numScorenext,next是struct student类型中的一个成员，它又指向struct student类型的数据。换名话说：next存放下一个结点的地址,10,11.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=9

5、9107 ; c.score=85; head= ,例11.7,建立和输出一个简单链表,各结点在程序中定义，不是临时开辟的，始终占有内容不放，这种链表称为“静态链表”,11,11.7.3 处理动态链表所需的函数,C 语言使用系统函数动态开辟和释放存储单元,1.malloc 函数,函数原形：void *malloc(unsigned int size);作用：在内存的动态存储区中分配 一个 长度为size的连续空间。返回值：是一个指向分配域起始地址的指针（基本类型void）。执行失败：返回NULL,12,函数原形:void *calloc(unsigned n,unsigned size);作用

6、：在内存动态区中分配 n个 长度为size的连续空间。函数返回值：指向分配域起始地址的指针执行失败：返回null主要用途：为一维数组开辟动态存储空间。n 为数组元素个数，每个元素长度为size,2. calloc 函数,13,3. free 函数,函数原形： void free(void *p);作用：释放由 p 指向的内存区。P:是最近一次调用 calloc 或 malloc 函数时返回的值。free 函数无返回值动态分配的存储单元在用完后一定要释放，否则内存会因申请空间过多引起资源不足而出现故障。,14,结点的动态分配,ANSI C 的三个函数(头文件 malloc.h) void *ma

7、lloc(unsigned int size)void *calloc(unsigned n, unsigned size)void free(void *p)C+ 的两个函数new 类型（初值） delete 指针变量 /* 表示释放数组，可有可无）*/使用 new 的优点：可以通过对象的大小直接分配，而不管对象的具体长度是多少（p340 例14.10）,15,11.7.4 建立动态链表,基本方法: 三个结点（头结点head、尾结点 NULL 和待插入结点 P）第一步：定义头结点head、尾结点 p2 和待插入结点p1，待插入的结点数据部分初始化；第二步：该结点被头结点、尾结点同时指向。P1

8、=p2=(struct student*)malloc(LEN);头指针部分为空，head=NULL; 第三步：重复申请待插入结点空间，对该结点的数据部分赋值（或输入值），将该结点插入在最前面，或者最后面（书上在尾部插入）. P2-next=P1; P2=P1; 最后:P2-next=NULL;,*head,*p1,*p2,使用malloc(LEN),P2-next=NULL;,16,11.7.4 建立动态链表,head,P1p2,1.任务是开辟结点和输入数据2.并建立前后相链的关系,待插入的结点p1数据部分初始化,该结点被头结点head、尾结点p2同时指向.,17,图11.14,head,p

9、2,p1,head,p2,p1,(a),(b),1重复申请待插入结点空间，对该结点的数据部分赋值（或输入值）,P2-next 指向p1新开辟的结点。,18,图11.14,head,p1,p2,(c),P2指向新结点p2=p1,19,图11.15,p2,p1,head,p2,p1,head,(a),(b),20,图11.16,p2,p1,head,p2,p1,head,21,例11.8 建立一个有3名学生数据的单向动态链表,#define NULL 0#define LEN sizeof(struct student)struct studentlong num; float score; st

10、ruct 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,结构体类型数据的长度，sizeof是“字节数运算符”,定义指针类型的函数。带回链表的起始地址,开辟长度为LEN的内存区,P1,p2是指向结构体类型数据的指针变量，强行转换成结构体类型,假设头指向空结点,22,续,while(p1-num!=0) n=n+1; /*n 是结点的个数*/ if

11、(n=1)head=p1; else p2-next=p1; p2=p1; p1=(struct student*)malloc(LEN); scanf(%1d,%f, /返回链表的头指针,算法：p1指向新开的结点: p1=(stuct student*)malloc(LEN);p1的所指向的结点连接在p2所指向结点后面，用p2-next=p1来实现。p2 指向链表中最后建立的结点，: p2=p1;,头指针指向p1结点,P1开辟的新结点链到了p2的后面,P1继续开辟新结点,给新结点赋值此,23,11.7.5 输出链表,链表遍历1.单向链表总是从头结点开始的；2.每访问一个结点，就将当前指针向该

12、结点的下一个结点移动： p=p-next;3.直至下一结点为空 P=NULL,24,图 11.18,head,p,P,P,25,例题 9,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); ,26,11.7.6 对链表的删除操作,删除结点原则：不改变原来的排列顺序，只是从链表中分离

13、开来，撤消原来的链接关系。两种情况：1、要删的结点是头指针所指的结点则直接操作；2、不是头结点，要依次往下找。另外要考虑：空表和找不到要删除的结点,27,链表中结点删除,需要由两个临时指针：P1: 判断指向的结点是不是要删除的结点（用于寻找）；P2: 始终指向P1的前面一个结点；,28,图11.19,(a),(B),29,图11.20,head,p1,（a）,(b),head,p2,p1,原链表P1指向头结点,P2指向p1指向的结点。P1指向下移一个结点。,30,图11.20,head,p1,head,p2,p1,(c),(d),经判断后，第1个结点是要删除的结点，head指向第2个结点，第1

14、个结点脱离。,经P1找到要删除的结点后使之脱离。,31,例 题 10,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 ,找到了,没找到,32,11.7.7 对链表的插入操作,插入结点：将一个结点插入到已有的链表中插入原则：1、插入操作不应破坏原链接关系2、插入的结点应该在它该在的位置实现方法： 应该有一个插入位置的查找子过程共有三种情况：1、

15、插入的结最小2、插入的结点最大3、插入的结在中间,33,操 作 分 析,同删除一样，需要几个临时指针：P0: 指向待插的结点;初始化：p0=数组stu;P1: 指向要在P1之前插入结点；初始化: p1=head;P2: 指向要在P2之后插入结点；插入操作：当符合以下条件时：p0-num 与 p1-num 比较找位置if(p0-nump1-num),34,图11.22,head,p1,（a）,p0,35,图11.22,p1,(b),36,例 题 11,struct student insert(struct student *head,struct student *stud) struct s

16、tudent *p0,*p1,*p2; p1=head; p0=stud; if( head=NULL; ) head=p0;p0-next=NULL; else while( p0-nump1-num) ,原来的链表是空表,P0指向要插的结点,使p0指向的结点作为头结点,使p2指向刚才p1指向的结点,插到原来第一个结点之前,插到p2指向的结点之后,插到最后的结点之后,链接,37,head,课堂举例：已有一个如图所示的链表；它是按结点中的整数域从小到大排序的，现在要插入一个结点，该结点中的数为10,待插入结点,此结点已插入链表,38,分析：按三种情况1、第一种情况，链表还未建成（空链表），待插

17、入结点p实际上是第一个结点。这时必然有head=null。只要让头指针指向 p 就可以了。语句为,headp,head = p;p-next = null;,2、第二种情况，链表已建成，待插入结点 p 的数据要比头结点的数据还要小，这时有(p-num )num)当然p结点要插在head结点前。,39,head,head,p,p-next=head;head=p;,语句为,null,40,3、第三种情况，链表已建成，待插入结点 p 的数据比头结点的数据大，需要找到正确的插入位置。这时，可以借助两个结构指针r 和 g，利用循环比较来找到正确位置。然后将结点 p 插入到链表中正确的位置。参见下面的图

18、示,41,head,p,g,r,说明：这种情况下，p 结点已经与链表的第一个结点比较过了，所以从链表的下一个结点开始比较。138，继续比较。,42,head,p,g,r,说明：1312，继续比较。,43,head,p,g,r,null,说明：1315，找到了正确的插入位置，则插入结点 p;语句为：,rnext = p;p-next = g;,44,/ 结构7.c#include / 预编译命令#include / 内存空间分配#define null 0/ 定义空指针常量#define LEN sizeof(struct numST)/ 定义常量，表示结构长度struct numST/ 结构声

19、明int num;/ 整型数struct numST *next;/ numST结构指针;,参考程序,45,/ 被调用函数insert()，两个形参分别表示链表和待插入的结点void insert (struct numST *phead, struct numST *p)/ 函数体开始struct numST *q,*r;/ 定义结构指针q,rif (*phead)=null)/ 第一种情况，链表为空*phead = p;/ 链表头指向preturn;/ 完成插入操作，返回else/ 链表不为空/ 第二种情况，p结点num值小于链表头结点的num值if ( (*phead)-num p-nu

20、m) / 将p结点插到链表头部 p-next = *phead;/ 将p的next指针指向链表头(*phead) *phead = p;/ 将链表头赋值为p return;/ 返回,46,/ 第三种情况，循环查找正确位置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;/ 退出

21、循环/ 将p结点插入正确的位置r-next = p;p-next = q;,47,/ 被调用函数，形参为ST结构指针，用于输出链表内容void print(struct numST *head) int k=0;/ 整型变量，用于计数struct numST * r;/ 声明r为ST结构指针r=head;/ r赋值为head，即指向链表头while(r != null)/ 当型循环，链表指针不为空则继续/ 循环体开始k=k+1;/ 计数加1printf(%d %dn,k,r-num); r=r-next;/ 取链表中相邻的下一个结点/ 循环体结束,48,void main()/ 主函数开始/

22、函数体开始struct numST *head, *p;/ ST型结构指针head = null;/ 分配两个ST结构的内存空间，用于构造链表head = (struct numST *) malloc(LEN);head-next = (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

23、 = null;insert(/ 调用print函数，输出链表内容/ 主函数结束,49,说明：函数insert()的第一个形参为struct numST*类型，即“指针的指针”。调用时送入的实参是链表头指针的地址，即程序中的&head。这样对head的修改才会在函数返回后仍有效。如果形参为struct numST*，则传入的为指针，当函数返回后，head无法改变。,50,11.8 共用体 构造类型之二联合,在同一存储单元里，根据需要放不同类型的数据，使用覆盖技术。,51,11.8.1 概念,单元起始地址：1000 。三个变量（数据）占用同一单元：1000 1003,52,共用体变量的定义,格式

24、（一般形式）： union 联合类型名 成员列表 变量列表；,11.8.2 共用体变量的引用方式,同结构类型变量的引用格式： 变量名.成员名,53,格式与结构类型的定义和变量声明形式上类似，但实质上有区别：,结构类型的长度=各成员的长度和；各成员占独立的存储单元，不共享；联合类型的长度为成员中长度的最大者，各成员共享长度最大的存储单元；,54,11.8.3 共用体类型数据的特点,虽然同一内存单元内可以存放不同类型（同一地址）、不同长度的数据，但任一时刻，只有一种类型数据（最后赋值的）起作用；其它的都没有意义；不能对共用体变量整体赋值，也不能对其初始化。共用变量不可作为函数的参数，但可以通过指针

25、指向；共用体类型可以和结构类型/数组类型互为基类型；p289,55,例 题 12,struct int num; char name10; char sex; char job; union int class; char position10; category; person2;main() int n,i; for(i=0;i2 ;i+); scanf(%d，%s，%c，%c”, ,56,if(personi.job=s) scanf(%d, ,续,57,枚举类型 -构造类型之三,58,11.9 枚举类型,枚举类型是指能将类型所包含的值一一列举出来。枚举值称为枚举常量定义枚举类型的关键字

26、是 enum。其类型的定义以及变量的声明同结构类型和联合类型；,声明格式：enum weekday(sum,mon,tue,wed,thu,fri,sat);定义变量：enum weekday workday,week_end;,59,关于枚举类型变量,在C 编译中，对枚举元素按常量处理；对枚举型变量的赋值（枚举型变量的取值）只能取该变量所属枚举类型的枚举常量值；一个整数不能直接赋给一个枚举变量。进行强制性转换；,60,说 明（1）枚举型仅适应于取值有限的数据。例如，根据现行的历法规定，周天，年个月。（2）取值表中的值称为枚举元素，其含义由程序解释。例如，不是因为写成“Sun”就自动代表“星期

27、天”。事实上， 枚举元素用什么表示都可以。（3）枚举元素作为常量是有值的定义时的顺序号（从开始），所以枚举元素可以进行比较，比较规则是：序号大者为大！例如，上例中的Sun=0、Mon=1、Sat=6，所以MonSun、Sat最大。（4）枚举元素的值也是可以人为改变的：在定义时由程序指定。例如，如果enum weekdays Sun=, Mon ,Tue, Wed, Thu, Fri, Sat；则Sun=，Mon=，从Tue=2开始，依次增。,61,例 题 13,/*file1.c文件1*/main() extern enter-string(char str80); extern delete

28、-string(char str,char ch); extern print-string(char str); char c; char str80; enter_string(str); scanf(%c,62,续,for(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 %-6sn,personi.

29、num,personi.name,personi. sex,personi.job,personi.category.position); ,63,11.10 用typedef 为类型定义新名字,除可直接使用提供的标准类型和自定义的类型（结构、共用、枚举）外，也可使用typedef定义已有类型的别名。该别名与标准类型名一样，可用来定义相应的变量。定义已有类型别名的方法如下： （1）按定义变量的方法，写出定义体； （2）将变量名换成别名； （3）在定义体最前面加上typedef。,64,11.10 用typeded 为类型定义新名字,任何已有的类型可以重新命名typedef long integ

30、er; /将 long 重新命名为 integer，使得 integer 和 long 同等使用 可以和新类型定义一起定义名字typedef int ARR10 ; / 定义了一个数组名 ARR，它是具有10个元素的整型数组类型typedef struct int num;float score; S; /*定义结构体别名为S*/STUDENT stu1;,65,讨论：typedef 和 #define,说明：（1）用typedef只是给已有类型增加个别名，并不能创造个新的类型。就如同人一样，除学名外，可以再取一个小名（或雅号），但并不能创造出另一个人来。（2）typedef与#define有

31、相似之处，但二者是不同的：前者是由编译器在编译时处理的；后者是由编译预处理器在编译预处理时处理的，而且只能作简单的字符串替换。,66,struct TMint x,y; / 结构TM的成员，x,y为整数型struct TM next / 结构TM的成员，属TM型,下面的表是马的跳步方案，从左下角跳到右上角,结构体与共体例子,67,NULL为空地址下面是形成链表的一个参考程序,&n1,head,68,/ 结构1.c#include / 预编译命令#define null 0/ 定义空指针常量struct TM/ 定义结构TMint x,y;/ 整型变量x,ystruct TM next;/ 指向

32、TM结构的指针;void main()/ 主函数/ 主函数开始 int i;/ 声明整型变量 / 声明TM结构n1n7,结构指针head,p struct TM n1,n2,n3,n4,n5,n6,n7, head, p;,69,/ 分别对TM结构n1n7中的x,y赋值 n1.x=0;n1.y=0; n2.x=1;n2.y=2; 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=,/ n1n7构成链表 n1.next=,70,=head;/

33、p赋值为head，即p指向head所指的内容i=1;/ i赋值为1do/ 直到型循环/ 循环体开始/ 输出结点信息printf(结点%d: x=%d, y=%dn,i,p-x,p-y); p=p-next;/ p指向下一个结点 i=i+1;/ 计数加1 while(p!=null);/ 未到达链表尾部，则继续循环/ 主函数结束,71,用结构数组，利用键盘输入结点中的数据。重点看scanf(“%d”,结构数组，数组中的元素为结构类型的数据，如n8,/ 结构2.c#include / 预编译命令#define null 0/ 定义空指针常量struct TM/ 定义TM结构int x,y;/ 整型

34、变量x,ystruct TM *next;/ 指向TM结构的指针;,72,void 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);/ 提示输入第i个结构的x值 scanf(%d,/ 将b的值赋给结构ni的元素y/ 循环体结束,73,head=/ 未到链表尾部，则继续循环/ 主函数结束,74,下面的程序与上面的程序区别仅在scanf(“%d”,/ 结构3.c#i

35、nclude / 预编译命令#define null 0/ 定义空指针常量struct TM/ 定义TM结构int x,y;/ 整型变量x,ystruct TM *next;/ 指向TM结构的指针;,75,void 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);/ 提示输入第i个结构的x值 scanf(%d,/ 输入ni.y/ 循环体结束,76,head=/

36、未到达链表尾部，则继续循环/ 主函数结束,77,任 务,我们要作一张登记表，登记排队求职信息，包括：姓名、年龄、性别、电话四个参数。希望便于管理，即可以插入和删除，这时可用队列，采用结构类型变量。struct STchar name20;/ 字符串，姓名int age;/ 整数，年龄char sex;/ 字符，性别long num;/ 电话号码struct ST *next;/ ST结构的指针;/ 注意，这里必须有分号,78,循 环 链 表,79,循环链表,例：猴子选大王。n只猴子围成一圈，顺时针方向从1到n编号。之后从1号开始沿顺时针方向让猴子从1，2，m依次报数，凡报到m的猴子，都让其出圈

37、，取消候选资格。然后不停地按顺时针方向逐一让报出m者出圈，最后剩下一个就是猴王。,80,起始位置,猴 王,1,2,3,4,5,6,7,8,3,6,1,5,2,8,4,猴子被淘汰的顺序,演示：n=8, m=3,81,说明：如图1所示有8只猴子围成一圈，m=3。从1#猴的位置开始，顺时针1至3报数，第一个出圈的是3#；第二个出圈的是6#，第3个出圈的是1#；第4个出圈的是5#；第5个是2#，第6个是8#；第7个是4#。最后剩下一个是7#，它就是猴王。我们用循环链表来模拟这个选择过程。,82,1、定义一个名为mon的结构struct monint num;/ 整数，表示猴子的编号struct mon

38、 *next;/ 指针，指向相邻的下一只猴子2、将链表的头指针head定义为全局变量。struct mon*head;3、主函数用键盘输入猴子数n，输入数m，调用函数create建立一个循环链表，模拟众猴围成一圈的情况。该函数的实参为n。调用函数select，模拟1至m报数，让n-1只猴子逐一出列的过程。即在具有n个结点的循环链表按报数m删除结点的过程。该函数的实参为m，最后输出猴王的编号。,83,4、建立循环链表的函数create(int nn)其中nn为形式参数。要从编号1到编号nn。思路是（1）先做第1个结点，让其中的数据域p-num赋值为1，让指针域赋值为null。之后让链头指针hea

39、d指向第1个结点。利用指针q记住这个结点，以便让指针p去生成下面的结点。（2）利用一个计数循环结构，做出第2个结点到第nn个结点。并将相邻结点一个接一个链接到一起。（3）最后一个结点要和头结点用下一语句链接到一起tail = q; tail-next = head;,head,tail,q,84,5、删结点的函数select(int mm)mm为形式参数，从1至m报数，凡报到mm者删除其所在的结点。设计两个指针p和q。一开始让q指向链表的尾部q=tail。让p指向q的下一个结点。开始时让p指向1#猴所在的结点。用一个累加器x，初始时x=0，从1#猴所在结点开始让x=x+1=1，如果mm是1的话

40、，1#猴所在的p结点就要被删除。有三条语句printf(“被删掉的猴子号为%d号n”,p-num);q-next = p-next;free(p);,head,tail,q,p,演示,85,这里free(p)是释放p结点所占用的内存空间的语句。如果mm不是1而是3，程序会在do-while循环中，让x加两次1，q和p一起移动两次，p指向3#所在结点，q指向2#所在结点，之后仍然用上述三条语句删去3#所在的结点。,head,q,p,q,p,p,q,演示,86,这个do-while循环的退出条件是q=q-next。即当只剩下一个结点时才退出循环。当然猴王非其莫属了。这时，让头指针head指向q，h

41、ead是全局变量，在主程序最后输出猴王时要用head-num。,参考程序如下：,head,q,87,#include / 预编译命令#include / 内存空间分配#define null 0/ 定义空指针常量/ 定义常量，表示结构长度#define LEN sizeof(struct mon)struct mon/ 结构声明int num;/ 整型数，用于记录猴子号struct mon *next;/ mon结构指针;struct mon *head, *tail;/ mon结构指针，全局变量,88,void create(int nn)/ 被调用函数/ 函数体开始 int i;/ 整型变

42、量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赋值为p,89,for(i=2;inum=i;/ 初始化p结点num域为i，表示猴子号q-next=p;/ 将p结点加到链表尾部q=p;/ 让q指向链表尾部结点p-next=null;/ 链表尾部指向空/ 循环体结束tail = q;/ 链表尾tail-next=head;/ 链表尾部指向

43、链表头，/ 形成循环链表/ 函数体结束,90,/ 被调用函数select，mm表示结点删除间隔void select(int mm)/ 函数体开始int x=0;/ 声明整型值x，并初始化为0struct 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;/ 删除此结点free(p);/ 释放空间else q=p;/ q指向相邻的下一个结点pwhile(q!=q-next);/ 剩余结点数不为1，则继续循环head = q;/ head指向结点q，q为链表中剩余一个结点/ 函数体结束,91,void main()/ 主函数开始/ 函数体开始int n,m;/ 声明整型变量n,mhead = null;/ 初始化head为空printf(请输入猴子数n);/ 提示信息scanf(%d, / 输出猴王/ 函数体结束,