循环链表实例(猴子选大王).pptVIP

* * * 循 环 链 表 * 循环链表 例：猴子选大王。n只猴子围成一圈，顺时针方向从1到n编号。之后从1号开始沿顺时针方向让猴子从1，2，…，m依次报数，凡报到m的猴子，都让其出圈，取消候选资格。然后不停地按顺时针方向逐一让报出m者出圈，最后剩下一个就是猴王。 * 起始位置 猴 王 1 2 3 4 5 6 7 8 3 6 1 5 2 8 4 猴子被淘汰的顺序 演示：n=8, m=3 * 说明： 如图1所示有8只猴子围成一圈，m=3。从1#猴的位置开始，顺时针1至3报数，第一个出圈的是3#；第二个出圈的是6#，第3个出圈的是1#；第4个出圈的是5#；第5个是2#，第6个是8#；第7个是4#。最后剩下一个是7#，它就是猴王。 我们用循环链表来模拟这个选择过程。 * 1、定义一个名为mon的结构struct mon{ int num; // 整数，表示猴子的编号 struct mon *next; // 指针，指向相邻的下一只猴子} 2、将链表的头指针head定义为全局变量。struct mon*head; 3、主函数用键盘输入猴子数n，输入数m，调用函数create建立一个循环链表，模拟众猴围成一圈的情况。该函数的实参为n。调用函数select，模拟1至m报数，让n-1只猴子逐一出列的过程。即在具有n个结点的循环链表按报数m删除结点的过程。该函数的实参为m，最后输出猴王的编号。 * 4、建立循环链表的函数create(int nn)其中nn为形式参数。要从编号1到编号nn。思路是 （1）先做第1个结点，让其中的数据域p-num赋值为1，让指针域赋值为null。之后让链头指针head指向第1个结点。利用指针q记住这个结点，以便让指针p去生成下面的结点。 （2）利用一个计数循环结构，做出第2个结点到第nn个结点。并将相邻结点一个接一个链接到一起。 （3）最后一个结点要和头结点用下一语句链接到一起 tail = q; tail-next = head; head tail q * 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的话，1#猴所在的p结点就要被删除。有三条语句 printf(“被删掉的猴子号为%d号\n”,p-num); q-next = p-next; free(p); 1 head 2 8 tail q p 演示 * 这里free(p)是释放p结点所占用的内存空间的语句。如果mm不是1而是3，程序会在do-while循环中，让x加两次1，q和p一起移动两次，p指向3#所在结点，q指向2#所在结点，之后仍然用上述三条语句删去3#所在的结点。 1 head 2 8 q p 3 4 q p p q 演示 * 这个do-while循环的退出条件是q==q-next。即当只剩下一个结点时才退出循环。当然猴王非其莫属了。这时，让头指针head指向q，head是全局变量，在主程序最后输出猴王时要用head-num。 参考程序如下： 7 head q * #include stdio.h // 预编译命令 #include malloc.h // 内存空间分配 #define null 0 // 定义空指针常量 // 定义常量，表示结构长度 #define LEN sizeof(struct mon) struct mon // 结构声明 { int num; // 整型数，用于记录猴子号 struct mon *next; // mon结构指针 }; struct mon *head, *tail; // mon结构指针，全局变量 * void create(int nn) // 被调用函数 { // 函数体开始 int i; // 整型变量i，用于计数 struct mon *p,*q; // 声明mon结构指针p，q // 为p分配内存空间p=(struct mon *) malloc(LEN); p-num=1; // 初始化p结点num域为1 p-next=null; // 初始化p结点next域为空 head=p; // 链表头指针head赋值为p q=p; // q赋值为p * * *