小猴VS猴王
i am the king of monkeies
问题描述
一群猴子都有编号，编号是1,2，„„m，这群猴
子按照顺序围坐成一圈，从第一个开始数，每数到第
n个，该猴子就要离开此圈，这样依次数下来，直到 圈中只剩下最后一只猴子，则该猴子为大王。
我们选择用一个循环链表来完成
该设计，设计一个猴子的结构体,

直至剩下最 后一个链表
单链表的删除
为了删除第i个猴子Mi，必须找到猴子的存储地址。 该存储地址是在其直接前趋结点Mi-1的next域中，因 此，必须首先找到Mi-1的存储位置p，然后令p– 图解 >next指向Mi的直接后继结点，即把Mi从中赶出。
算法设计与实现
1. 对每一个猴子进行编号 2. 3. 每数到n便删除该猴子，当循环单链表只剩一个时， 主函数 r=q=(listnode *)malloc(sizeof(listnode)); int main() 输出该编号 for(i=1;i<=n-1;i++) for(i=1;i<n;i++){ { { p=(listnode*)malloc(sizeof(listnode)); linklist r; for(j=1;j<=k-1;j++) p=p->next; q->data=i; int n,k; q=p->next; q->next=p; linklist initring(int n,linklist r); p->next=q->next; q=p; linklist deletedeath(int n,int k,linklist r); if(i % 10==0) } free(q); void outring(int n,linklist r); } p->data=n; printf("请输入猴子总数m："); printf("\n"); p->next=r; scanf("%d",&n); r=p;return r; } r=p; printf("请输入n："); void outring(int n,linklist r) scanf("%d",&k); { int i; r=initring(n,r); listnode *p; r=deletedeath(n,k,r); p=r; printf("猴子大王："); outring(n,r); printf("%4d\n",p->data);
}
答案输出：
电子商务132 数据结构设计 天王组合
猴子选大王
• 附录：源程序代码
#include <stdio.h> #include <stdlib.h> typedef struct node { int data; struct node *next; }listnode; typedef listnode *linklist; linklist initring(int n,linklist r) { listnode *p,*q; int i; r=q=(listnode *)malloc(sizeof(listnode)); for(i=1;i<n;i++){ p=(listnode*)malloc(sizeof(listnode)); q->data=i; q->next=p; q=p; } p->data=n; p->next=r; r=p; return r; } linklist deletedeath(int n,int k,linklist r) { int i,j; listnode *p,*q; p=r； for(i=1;i<=n-1;i++)
算法分析
结点的数据域为猴子的 编号，指针域指向下一个 猴子。报数实际上是计数 ，只要设一个计数器就可 以了。当计数器由 0 变化到 n 时，删除该结点，计数器 回 0 继续计数 ( 或者用求余 运算 ) 。直到链表中剩下一 个结点（大王）。
图解 链式存储
猴子编号 M
第N个猴子 遗憾离开
删除部分 链表
并开辟空间用来存储猴子结构，生
成了一个猴子结构的循环链表。
输入 m=30, n=3
输出 29是 大王
问题实现
输入数据：猴子总数m，出局数字n.
输出数据：猴子的出队序列和猴子大王的 编号
问题分析
• (1) 输入m和n，m是猴子的总个数，n是小于m的正 整数数。 • (2) 把m只猴子编上好“1，2，3……m”然后按照 1--m的顺序围坐一圈，从第1开始数，每数到第n个 ，该猴子就要离开此圈，这样依次下来，直到圈中 只剩下最后一只猴子，则该猴子为大王。 • (3) 输出最后剩下的那只猴子的编号，这猴子就是大 王。 • (4) 对结果进行分析。
{ for(j=1;j<=k-1;j++) p=p->next; q=p->next; p->next=q->next; if(i % 10==0) free(q); } printf("\n"); r=p;return r; } void outring(int n,linklist r) { int i; listnode *p; p=r; printf("猴子大王："); printf("%4d\n",p->data); } int main() { linklist r; int n,k; linklist initring(int n,linklist r); inklist deletedeath(int n,int k,linklist r); void outring(int n,linklist r); printf("请输入猴子总数m："); scanf("%d",&n); printf("请输入n："); scanf("%d",&k); r=initring(n,r); r=deletedeath(n,k,r); outring(n,r); }