计算机软件及应用链表c++课件

1、第11章 链表第1页，共88页。教学目标链表的概念建立链表中指针的运用插入删除结点的思路与双指针作用建立循环链表的思路第2页，共88页。 链表属于动态数据结构，可以类比成一“环”接一“环”的链条，这里每一“环”视作一个结点，结点串在起形成链表。第3页，共88页。11.1 举例说明链表的概念第4页，共88页。【任务11.1】某电视台希望王小二同学为他们编一个程序。该程序可以将节目串在一起，形成一份有序的节目预告。节目列表有如下三项1、节目名称包括新闻联播（CCTV News）祖国各地（Motherland）体育之窗（Sports）学校见闻（College）电影展播（Movie）2、节目主持人（D

2、irector）3、播放时间长度（Time）第5页，共88页。我们可以将每一个节目单独放在一个结构里，用一个指针把两个结构连在一起，一天的节目形成一条链表。用一个所谓的头指针 head 指向链表的第一个结点。如下图所示节目2节目nNULLhead头指针节目1下面的程序是建立链表的过程。第6页，共88页。11.2 建立链表的过程第7页，共88页。/*/* 程 序 名：11_1.cpp */* 作 者：wuwh */* 编制时间：2002年11月26日 */* 主要功能：链表 */*#include using namespace std;struct ActList/ 定义一个名为 ActLis

3、t 结构char ActName20;/ 节目名为字符数组char director20; / 主持人为字符数组int Mtime;/ 节目长度为分钟ActList *next;/ 指向 ActList 结构的指针;第8页，共88页。ActList *head; / 链头指针ActList *Create() / 定义一个指向 AcitList 结构 /的指针函数，名为 Create ActList *p=NULL; / 指针，指向个待插入的结点 ActList *q=NULL; / 指针，用于在其后插入结点 head = NULL; / 一开始链表为空 int Time; / 节目时长，如为

4、0则退出第9页，共88页。/ 以下是给新结点输入节目信息cout Time;while(Time != 0) / 当该节目的时长不为0时，将其/ 纳入链表中 p = new ActList;/ 分配内存空间给p结点 p-Mtime = Time; / 让Time赋给p结点的结 构成员Mtime cout p-ActName; / 输入节目名称 cout p-director; / 输入主持人第10页，共88页。 if (head = NULL) / head为空，要插入第一个 head = p; / 结点，让头指针指向结点p else / 否则不是头结点，应将p结点 q-next = p; /

5、 插入到q结点的后面 q = p; / q指向当前最后一个结点 cout Time;/ 输入下一个节目时长 / 一旦跳出while循环，说明有一个节目时长为0if (head != NULL)q-next = NULL; / 让q所指的最后一个结点的指针域为空说明这已是链尾了return(head);/ 返回头指针第11页，共88页。void displayList(ActList *head) cout 显示节目列表n; while(head != NULL)/ 当指针head不空，则输出 cout Mtime endl ActName endl director endl next; 第1

6、2页，共88页。int main( )/ 主函数开始 / 调用子函数displaList() / 调用时的实参为Create()函数的返回值 displayList( Create() ); return 0;/ 主函数结束第13页，共88页。说明1、先从主函数说起主函数只有一条语句 displayList(Create( );这是调用子函数 displayList，该子函数的形参为 ActList *head 是一个指向 ActList 结构的名为 head 的指针变量。在主函数调用 displayList 时所用的实际参数来自运行 Create( ) 函数的返回值。从 Create( )

7、的定义ActList *Create( )看出 Create( ) 函数的返回值应该是一个指向 ActList 的指针。主函数在调用子函数时，又遇到该函数的实参又是调用另一个函数之后的返回值。看起来的确显得复杂，但是我们耐心分析之后，感到并不难。第14页，共88页。2、程序开头为结构定义。在这里我们称这样的一个结构为一个结点。这个结点包含两个域：数据域和指针域int MTime;char ActName20; 数据域char director20ActList *next; 指针域结 点数据域中装有节目的信息，而指针域装的是指向另一个结点的地址。显然这是为形成链表而专门设置的。第15页，共88

8、页。3、在定义 Create 函数之前，先定义了一个指向结构的头指针 head，即ActList *head;4、定义 Create函数，该函数可返回指向 ActList 结构的指针，即ActList *Create( )分析这个函数的功能可分如下4块第16页，共88页。 定义ActList *p = NULL;ActList *q = NULL;head = NULL;int Time;定义了两个指向结构 ActList 的指针 p 和 q，并初始化为空，即未指向任何地址。同时让头指针 head 也为空。再定义一个临时变量 Time，是一个整型数。第17页，共88页。 提示“输入节目时长”，

9、之后用键盘输入，用了下面两句：cout Time;这部分程序语句是为下面的 while 循环做准备的。如果 Time 不为 0，才做下面的内容。第18页，共88页。 while( Time != 0 ) 循环在当循环的循环体内完成建立链表的过程。首先给 p 结点分配内存空间。这个内存空间的大小要根据 p 结点的定义（p 结点是 ActList 结构）来确定。接着下面就是几个赋值语句p-MTime = Time;cout p-ActName;/ 用键盘输入节目名称cout p-director;/ 用键盘输入主持人第19页，共88页。接着是一个分支语句if (head=NULL) head=p;

10、这是说如果头指针为空，表示链表还是空的，这时 p 结点就是第一个结点。让 head 指向 p 结点。之后让 q=p; 这是让 q 指向刚进入链表的结点，让 p 再去指向待加入的结点。如果 p 结点已不是第一个结点了，head 必不为 NULL，因此要走 else 分支，即else q-next = p;第20页，共88页。将此时的 p 结点放到 q 所指向的结点后面。之后让 q=p; 即让 q 指向刚进入链表的结点，腾出 p 去指向下一个待加入的结点。接下来输入下一个节目时长，cout Time;至此，while 语句的循环体结束。当 Time 值不为0，就会有结点加入链表，继续执行循环体。一

11、旦 Time 为 0，则会跳出 while 循环。第21页，共88页。执行两条语句if (head != NULL) q-next = NULL;return (head);第一条是说，如果 head 不空说明链表已建成，这时 q 一定是最后一个结点，将该结点的指针域置成空，以表明它是链尾。第22页，共88页。第二条 return (head); 将这条链表的头指针 head 返回。这件事意味着执行完 Create函数后得到 head 指针所指向的地址，这个地址就是链表中的第一个结点的地址。这时对主函数而言displayList( Create( ) ) 就是dispalyList( head

12、 )调用 dsplayList(head) 就会将整个链表从头至尾输出。第23页，共88页。1、定义 ActList 结构，结构中包含数据域和指针域。将一个结构看作一个结点。2、定义一个指向结构的指针 head，准备用来指向链表的第一个结点。3、定义一个指向ActList 结构的指针函数，起名为 Create 函数，该函数返回的是创建好的链的头指针 head。下面是 Create 函数所要做的事情： 定义指向 ActList 结构的两个指针 p 和 q，定义后立即初始化为 NULL，即不指向任何地址。再让头指针 head 为 NULL，也是不指向任何地址，表示该链表尚未建立，一个结点也没有。然

13、后定义一个中间变量“节目时长 Time”，当 Time 为 0 时，建立链表的过程应该结束。建立链表的过程可归纳为如下三个步骤第24页，共88页。 下面程序的构思是，只要 Time 不为 0，就要构建链表。构建的思路是将一个一个的结点加至链表里来。首先给 p 找一个能够指向的内存空间，我们说这是给 p 结点分配一片内存空间。如下图建立链表的过程可归纳为如下三个步骤p第25页，共88页。 然后，通过键盘往这个空间中装入与节目有关的信息。装完之后判断一下 head 为空否，如为空则 p 结点为第一个结点，让 head 指向 p 结点就完成了有一个结点的链表。之后让 q 赋值为 p，即使让 q 指针

14、去指向刚加入链表的结点，将 p 指针腾出来去做下一个结点的工作。headpq图 链表的第一个结点建成第26页，共88页。当 Time 不为 0，p 又被分配了内存空间，形成了第二个结点，装入节目信息后，判断 head 不再为空，说明前面已有结点在链表中，这时要将第二个结点放到 q 所指向的结点的后面。执行 q-next = p 之后就完成了。之后再将 q 指针移到第二个结点上，将 p 指针腾出来去做下一个结点的工作。headpq第27页，共88页。指针移到第二个结点上，将 p 指针腾出来去做下一个结点的工作。headq第三个结点加入链表的过程为headqp第28页，共88页。最末一个结点连至链

15、表的尾部之后，要在 q 指针所指向的最后一个机诶但的指针域加上一个 NULL，表示这里是链尾了，后面再也不连结点了。headqNULL第29页，共88页。练 习1、按下表顺序输入某班的一个学习小组的成员表：姓名赵达钱亮孙参李思周芜武陆郑琪出生年月19831983198319821983198319821329546将学习小组形成一个链表，每人一个结点。结点中有4个成员：姓名、出生年、出生月、指针。建成链表后输出该链表。第30页，共88页。链表结点的插入第31页，共88页。链表结点的插入原则： 插入操作不应破坏原链接关系 插入的结点应该在它该在的位置。应该有一个插入位置的查找子过程第32页，共8

16、8页。5head61015null128先看下面一个简单的例子：已有一个如图所示的链表。它是按结点中的整数域从小到大排序的。现在要插入一个结点，该节点中的数为10。待插入结点此结点已插入链表第33页，共88页。/*/* 程 序 名：7_20.cpp */* 作 者：wuwh */* 编制时间：2002年12月3日 */* 主要功能：链表插入结点 */*#include / 预编译命令struct numST/ 结构声明int num;/ 整型数numST *next;/ numST结构指针;参考程序第34页，共88页。/ 被调用函数insert()，两个形参分别表示链表和待插入的结点void

17、insert ( numST *&pHead, numST *pNode)/ 函数体开始struct numST *q,*r;/ 定义结构指针q,r/ 第一种情况，链表为空if (pHead=NULL)pHead = pNode;/ 链表头指向pNodereturn;/ 完成插入操作，返回/ 链表不为空/ 第二种情况，pNode结点num值小于等于链表头结点的num值/ 则将pNode结点插到链表头部if ( pNode-num num ) pNode-next = pHead;/ 将pNode的next指针指向链表头 pHeadpHead = pNode;/ 将链表头赋值为pNoderetu

18、rn;/ 返回第35页，共88页。/ 第三种情况，循环查找正确位置r = pHead;/ r赋值为链表头q = pHead-next;/ q赋值为链表的下一个结点while (q!=NULL) / 利用循环查找正确位置/ 判断pNode结点的num是否大于当前结点numif (pNode-num q-num)r = q;/ r赋值为q，即指向q所指的结点q = q-next;/ q指向链表中相邻的下一个结点else/ 找到了正确的位置break;/ 退出循环/ 将pNode结点插入正确的位置r-next = pNode;pNode-next = q;第36页，共88页。/ 被调用函数，形参为n

19、umST结构指针，用于输出链表内容void print(numST *pHead)int k=0;/ 整型变量，用于计数numST *r=pHead;/ 声明 r 为 numST 结构指针，/ 并赋值为pHead，即指向链表头while(r != NULL)/ 当型循环，链表指针不为空则继续/ 循环体开始cout.width(2);/ 设置输出的序号 k 所占的宽度k = k+1;cout k : num next;/ 取链表中相邻的下一个结点/ 循环体结束/ 函数体结束第37页，共88页。void main()/ 主函数开始/ 函数体开始numST *pMHead=NULL;/ numST

20、型结构指针，链表头numST *pMNode=NULL;/ numST 型结构指针，要插入的结点/ 两个指针均初始化为空/ 分配 3 个 numST 结构的内存空间，用于构造链表pMHead = new numST;pMHead-next = new numST;pMHead-next-next = new numST;/ 为链表中的3个结点中的num赋值为5、10和15pMHead-num = 5;pMHead-next-num = 10;pMHead-next-next-num = 15;pMHead-next-next-next = NULL; / 链表尾赋值为空/ 构造一个结点p，用于

21、插入链表pMNode = new numST;pMNode-num = 12;pMNode-next = NULL;insert(pMHead, pMNode);/ 调用insert函数将结点pMNode插入链表print(pMHead);/ 调用print函数，输出链表内容/ 与 new 对应，用 delete 释放空间 / 主函数结束第38页，共88页。1、定义两个 numST 型结构指针*pMHead，*pMNode，并初始化 pMHead 和 pMNode 为 NULL;2、分配 3 个 numST 结构的内存空间，用于构造链表（1）pMHead = new numST;（2）pMHe

22、ad-next = new numST;（3）pMHead-next-next = new numST;先看主函数pMHead这 3 个 numST 结构的内存空间如上图所示。pMHead-nextpMHead-next-next第39页，共88页。下面用赋值语句往这 3 个空间中放 num 数据。最后的一个结点为队尾，在其指针域存放 NULL。（4）pMHead-num=5;（5）pMHead-next-num=10;（6）pMHead-next-next-num=15;（7）pMHead-next-next-next=NULL;做了这4条之后形成了一条链表如下：5pMHead1015NUL

23、L该链表的头结点由 pMHead 所指向。第40页，共88页。3、构造一个结点 pMNode，在 pMNode 结点的数据域放 12，再插入链表（1）pMNode = new numST;（2）pMNode-num = 12;（3）pMNode-next = NULL;4、调用 insert 函数来插入 pMNode 结点。语句为 insert(pMHead, pMNode);意思是以将 pMNode 插入到以 pMHead 为队头的链表中。但这里在调用时，用 pMHead作为实参，传递的是引用，而非传值。所以在函数体内对pHead的修改，就等价于对pMHead的操作。第41页，共88页。这里

24、要讲传值和传引用的区别（1）如果是传值调用主程序中的调用语句为 insert(pMHead, pMNode);被调用函数为void insert( munST *pHead, numST*pNode);pMHeadpMNode实际参数形式参数pNodepHead第42页，共88页。当着实际参数 pMHead 赋给了形式参数 pHead之后，pHead 就指向了已经存在了的链表，见下图。51015NULLpHead这时原来的主函数中的头指针 pMHead 就不再起作用了，而是子函数中的 pHead 起作用。假如现在 pNode 中的结点数据为 4 小于 5，应该将 pNode 插入到 pHead

25、 所指向的结点前，如下图pMHead第43页，共88页。5pMHead1015NULLpHead被调用函数无法改变主函数的 pMHead。虽然在子函数内 pHead 被修改，指向了含有四个结点的链表头，但当函数返回后，主函数中的 pMHead 仍然指向链表后面的三个结点，新插入的结点并没有包含进去。所以要想将新的插入到最前面的结点包含进去，就必须用传址或传引用。4pHead第44页，共88页。（2）如果是传引用调用主程序中的调用语句为 insert(pMHead, pMNode);被调用函数为void insert(munST *&pHead, numST *pNode);先看 numST *

26、&pHead 是说声明 pHead 为 numST 结构指针的引用，即pHead 是“指向 numST 结构的指针”的引用。第45页，共88页。 主程序中的实参为链表头指针 pMHead 的引用，传给被调用函数的 pHead，在子函数中对 pHead 的操作就等价于对 pMHead 的操作。pMHead(pHead)*pMHead第46页，共88页。在主函数中 pMHead为头指针，在被调用的子函数中 pHead 为头指针。pHead 和 pMHead 是同一个单元，只不过分别叫不同的名罢了。当然在子函数中无论插入什么结点都会让 pHead 指向链表的头。自然返回到主函数后，pMHead也会是

27、指向同一链表的头。从这个例子中读者可以领会到传引用调用与传值调用的区别。5、这样在子函数做插入结点的过程中，头指针的改变也能反映到主函数中来。调用 print 函数，从 pMHead 开始输出整个链表的内容。第47页，共88页。下面我们来研究 insert 函数前提是主程序已将两个实参传给了 insert 函数的两个形参，这时 pHead 是 pMHead 的引用，指向链表头，pNode 所指向的就是待插入的一个结点。事先定义两个结构指针 q 和 r。第48页，共88页。第一种情况：pHead=NULL说明主程序传过来的头指针为空，即链表为空，一个结点都不存在。这时待插入的 pNode 结点就

28、是链表中的第一个结点。只要执行如下两条语句即可pHead = pNode; / 将表头指针指向p结点return; / 返回主程序在主程序中必然头指针 pMHead 指向 pMNode 结点。第49页，共88页。第二种情况：pNode 结点的 num 值小于等于链表头结点的 num 值，即 pNode-num num 这时要将 pNode 结点插入到头结点的前面，要执行如下三条语句pNode-next=pHead; / 在 pNode 结点的指针域/ 赋以头结点的地址值pHead=pNode;/ 将头结点指针 pHead/ 指向 pNode 结点return;/ 返回主程序第50页，共88页。

29、这种情况如下图（演示）5pHead10415NULLpNodeNULL第51页，共88页。第三种情况：前两种情况，无论遇到哪一种，都会返回主程序。只要不返回就是这第三种情况，即 pNode 结点的 num 大于等于头指针所指向的结点的 num 值。这时肯定地说 pNode 结点要插入到头结点之后，究竟要插到哪里需要找到应该插入的位置。我们设指针 r 和指针 q，分别指向相邻的两个结点，r 在前 q 在后。第52页，共88页。当着满足r-num num num时，pNode 就插在 r 与 q 之间。（演示）5pHead1012pNode15NULLNULLqr第53页，共88页。一开始让 r=

30、pHead，让 q=pHead-next(1) 当指针 q 为空指针时，说明原链表中只有一个结点，即 r 指向的结点，这时只要将 pNode 结点接在 r 之后即可。执行r-next=pNode;pNode-next=q;第54页，共88页。(2) 如果 q!=NULL，说明起码有两个结点在链表中，接着要判 pNode 结点的 num 值是否大于 q 结点的 num 值。如果是大，则说明 pNode 应插在 q 之后而不是之前，这时让 r 和 q 指针同时后移一步，即r=q;q=q-next;第55页，共88页。执行(2)在 q!=NULL 的情况下，如果 pNode-num num说明这时找

31、到了正确的插入位置，退出 while 循环，将 pNode 结点插入到 r 后，q 前即可。使用的语句为在下面我们画出该算法的结构框图r-next=pNode;pNode-next=q;第56页，共88页。第57页，共88页。作业1、按下表顺序输入某班的一个学习小组的成员表希望你将学习小组形成一个链表，每人一个结点。结点中有四个成员：姓名、出生年、出生月。指针。在链表中生日大者在前，小者在后。建成链表后输出该链表。姓名赵达钱亮孙参李思周芜武陆郑琪出 年生 月19831983198319821983198319821329546第58页，共88页。2、一年后钱亮同学调至其它学习小组，希望你编程从

32、原链表中删除钱亮所在结点，之后输出该链表。提示：原链表如下：李思19829head武陆19834赵达19831孙参19832钱亮19833郑琪19826周芜19835NULL查找待删除的结点的位置，要从链头找起。(1)如果是链头结点，即有 head-name = 待删者 name这时只要做 head=head-next; 即可(2)如果不是链头结点，要设两个指针 r 和 q，初始时让r=head; q=head-next;第59页，共88页。(3)只要 q!=NULL，就比较 q-name 是否为待删者的name？如果是则让 r-next=q-next; 如不是，就让 r 与 q 同时后移一步

33、，即 r=q; q=q-next; 然后转向(3)(4)如果发现 q 已是NULL，又未找到待删结点，则输出该人不在这个表中的信息。在原链表中一旦查到钱亮所在结点位置 q，让r-next = q-next;意味着将孙参所在结点指向钱亮的指针，不再指向钱亮，而指向武陆第60页，共88页。11.3.2 链表结点的删除void del(numST *&pHead,int num) numST *p = NULL,*q = NULL; /第一种情况，链表空 if(pHead = NULL) /链表为空，直接返回 return; /第二种情况，链表不空，但删除的是链表头 p = pHead; if( p

34、-num = num) /要删除的是链表头 pHead = p-next;/链表头指向下一个结点 delete p; /删除结点并释放空间 return; 第61页，共88页。 /第三种情况，链表非空且删除的不是表头结点， /需要从表头起查找要删除结点 q = p-next; while (q!=NULL) if(q-num = num)/q结点就是要删除的结点 p-next = q-next;/将q结点从链表中去掉 delete q; /删除结点并释放空间 return; if(q-numnum) /不存在要删除的结点 return ; p = q; q = q-next; /while /

35、del第62页，共88页。作业1、按下表顺序输入某班的一个学习小组的成员表希望你将学习小组形成一个链表，每人一个结点。结点中有四个成员：姓名、出生年、出生月。指针。在链表中生日大者在前，小者在后。建成链表后输出该链表。姓名赵达钱亮孙参李思周芜武陆郑琪出 年生 月19831983198319821983198319821329546第63页，共88页。2、一年后钱亮同学调至其它学习小组，希望你编程从原链表中删除钱亮所在结点，之后输出该链表。提示：原链表如下：李思19829head武陆19834赵达19831孙参19832钱亮19833郑琪19826周芜19835NULL查找待删除的结点的位置，要

36、从链头找起。(1)如果是链头结点，即有 head-name = 待删者 name这时只要做 head=head-next; 即可(2)如果不是链头结点，要设两个指针 r 和 q，初始时让r=head; q=head-next;第64页，共88页。(3)只要 q!=NULL，就比较 q-name 是否为待删者的name？如果是则让 r-next=q-next; 如不是，就让 r 与 q 同时后移一步，即 r=q; q=q-next; 然后转向(3)(4)如果发现 q 已是NULL，又未找到待删结点，则输出该人不在这个表中的信息。在原链表中一旦查到钱亮所在结点位置 q，让r-next = q-ne

37、xt;意味着将孙参所在结点指向钱亮的指针，不再指向钱亮，而指向武陆第65页，共88页。11.4 循 环 链 表第66页，共88页。任务11.2 猴子选大王。n 只猴子围成一圈，顺时针方向从 1 到 n 编号。之后从 1 号开始沿顺时针方向让猴子从 1，2，m 依次报数，凡报到 m 的猴子，都让其出圈，取消候选资格。然后不停地按顺时针方向逐一让报出 m 者出圈，最后剩下一个就是猴王。第67页，共88页。起始位置猴 王123456783615284猴子被淘汰的顺序演示：n=8, m=3第68页，共88页。说明：如图 1 所示有 8 只猴子围成一圈，m=3。从 1# 猴的位置开始，顺时针 1 至 3

38、 报数，第一个出圈的是 3#；第二个出圈的是 6#，第 3 个出圈的是 1#；第 4 个出圈的是 5#；第 5 个是 2#，第 6 个是 8#；第 7 个是 4#。最后剩下一个是 7#，它就是猴王。我们用循环链表来模拟这个选择过程。第69页，共88页。1、定义一个名为 mon 的结构struct monint num;/ 整数，表示猴子的编号mon *next;/ 指针，指向相邻的下一只猴子;2、将链表的头指针 head 定义为全局变量。mon *head;3、主函数用键盘输入猴子数 n，输入数 m，调用函数 create 建立一个循环链表，模拟众猴围成一圈的情况。该函数的实参为 n。调用函数

39、 select，模拟 1 至 m 报数，让 n-1 只猴子逐一出列的过程。即在具有n个结点的循环链表按报数 m 删除结点的过程。该函数的实参为 m，最后输出猴王的编号。第70页，共88页。4、建立循环链表的函数 create(int nn)其中nn为形式参数。要从编号 1 到编号 nn。思路是（1）先做第1个结点，让其中的数据域 p-num 赋值为 1，让指针域赋值为 NULL。之后让链头指针 head 指向第 1 个结点。利用指针 q 记住这个结点，以便让指针p去生成下面的结点。（2）利用一个计数循环结构，做出第 2 个结点到第 nn 个结点。并将相邻结点一个接一个链接到一起。（3）最后一个

40、结点要和头结点用下一语句链接到一起tail = q; tail-next = head;headtailq第71页，共88页。5、删结点的函数 select( int mm )mm为形式参数，从 1 至 mm 报数，凡报到 mm 者删除其所在的结点。设计两个指针 p 和 q。一开始让 q 指向链表的尾部 q = tail。让 p 指向 q 的下一个结点。开始时让 p 指向 1# 猴所在的结点。用一个累加器x，初始时 x = 0，从 1# 猴所在结点开始让 x= x+1 =1，如果 mm 是 1 的话，1# 猴所在的 p 结点就要被删除。有四条语句：第72页，共88页。cout“被删掉的猴子号为

41、”numnext = p-next;delete p;p=NULL;1head28tailqp演示空指针第73页，共88页。这里 delete p 是释放 p 结点所占用的内存空间的语句。如果 mm 不是 1 而是 3，程序会在 do-while 循环中，让 x 加两次 1，q 和 p 一起移动两次，p 指向 3#所在结点，q 指向 2# 所在结点，之后仍然用上述四条语句删去 3# 所在的结点。1head28qp34q演示第74页，共88页。这个do-while循环的退出条件是 q= q-next。即当只剩下一个结点时才退出循环。当然猴王非其莫属了。这时，让头指针 head 指向 q，head

42、 是全局变量，在主程序最后输出猴王时要用 head-num。参考程序如下：7headq第75页，共88页。/*/* 程 序 名：7_22.cpp */* 作 者：wuwh */* 编制时间：2002年12月11日 */* 主要功能：猴子选大王 */*#include / 预编译命令struct monkey/ 结构声明int num;/ 整型数, 用于记录猴子号monkey *next;/ monkey结构指针;monkey *head, *tail;/ monkey结构指针，全局变量第76页，共88页。void create(int nn)/ 被调用函数 / 函数体开始 int i; / 整

43、型变量i，用于计数monkey *p,*q; / 声明monkey结构指针 / 为p分配内存空间p=new monkey;p-num=1; / 初始化p结点num域为1p-next=NULL; / 初始化p结点next域为空head=p; / 链表头指针head赋值为pq=p;/ q赋值为p第77页，共88页。for(i=2;inum=i;/ 初始化p结点num域为i，表 示猴子号q-next=p;/ 将p结点加到链表尾部q=p;/ 让q指向链表尾部结点p-next=NULL;/ 链表尾部指向空/ 循环体结束tail = q;/ 链表尾tail-next=head;/ 链表尾部指向链表头/ 函

44、数体结束第78页，共88页。/ 被调用函数select，mm表示结点删除间隔void select(int mm)/ 函数体开始int x=0; / 声明整型值x，并初始化为0monkey *p,*q; / 声明结构指针p，qq=tail;/ q赋值为tail，指向循环链表尾部 do/ 直到型循环，用于循环删除指定间隔的结点/ 循环体开始p=q-next;/ p赋值为q相邻的下一个结点x=x+1;/ x加1if(x % mm=0)/ x是否整除mm，/ 表示是否跳过指定间隔/ 输出被删掉的猴子号cout 被删掉的猴子号为 num next=p-next;/ 删除此结点delete p;/ 释放空间p=NULL;/ p赋值为空else q=p;/ q指向相邻的下一个结点pwhile(q!=q-next);/ 剩余结点数不为1，则继续循环head = q;/ head指向结点q，q为链表中剩余的一个结点/ 函数体结束第79页，共88页。do/ 直到型循环，用于循环删除指定间隔的结点 p=q-next;/ p赋值为q相邻的下一个结点