数据结构课程设计 猴子选大王

数据结构

题目：n只猴子要选大王，选举办法如下：所有猴子按1,2,3……n编号围成一圈，从第一圈开始顺序1，2……m报数，凡报到m号的退出圈外，如此循环报数，直到圈内只剩一只猴子时，这只猴子就是大王。

利用单向循环链表存储结构模拟此过程，输出选出的大王编号。 程序：#include <stdio.h>

#include <stdlib.h>

#define n 19

#define m 4

typedef struct monkey

{

int num;

struct monkey *next;

} Monkey,*LINK;

void main()

{

LINK p,head,p2;

int i;

head=p=p2=(LINK)malloc(sizeof(Monkey));

for(i=1;i<n;i++)

{

p=(LINK)malloc(sizeof(Monkey));

p2->next=p;

p2=p;

}

p2->next=head;

p=head;

printf("对猴子进行编号！\n");

for(i=1;i<=n;i++)

{

p->num=i;

printf("%d号猴子：%d\n",p->num,p->num);

p=p->next;

}

i=0;

p=head;

while(1)

{

i++;

printf("%d号猴子报：%d\n",p->num,i);if(p->next==p) break;

if(i==m)

{

i=0;

printf("%d号猴被淘汰\n",p->num);

数据结构

printf("\n");

p2->next=p->next;

p=p2->next;

continue;

}

else

{

if(i==m-1) p2=p;

p=p->next;

}

}

printf("胜出:%d",p->num);

}

#include <stdio.h>

#include <stdlib.h>

#define n 19

#define m 4

typedef struct monkey

{

int num;

struct monkey *next;

} Monkey,*LINK;

void main()

{

LINK p,head,p2;

int i;

head=p=p2=(LINK)malloc(sizeof(Monkey));//三个指针指向同一块内存

for(i=1;i<n;i++)

{

p=(LINK)malloc(sizeof(Monkey));

p2->next=p;

p2=p;

}

数据结构

p2->next=head;//把链表的首尾相连

p=head;//p指向了第一个结点

printf("对猴子进行编号！\n");

for(i=1;i<=n;i++)

{

p->num=i;//从第一个结点到最后一个结点依次给猴子编号

printf("%d号猴子：%d\n",p->num,p->num);

p=p->next;

}//循环结束，p指向了最后一个结点

i=0;

p=head;//再把p指向第一个结点

while(1)

{

i++;

printf("%d号猴子报：%d\n",p->num,i);

if(p->next==p)

break;//此为while循环的出口

if(i==m)//if语句中是删除结点的过程

{

i=0;

printf("%d号猴被淘汰\n",p->num);

printf("\n");

p2->next=p->next;//在此删除结点p

p=p2->next;//p指向它的下一个结点

continue;

}

else

{

if(i==m-1)

p2=p;//保存将要退出结点的前一个结点（存到p2中）

p=p->next;

}

}

printf("胜出:%d",p->num);//最后剩下的结点就是获胜的结点

}

数据结构

current=head; /*使current指向循环链表的最后一个结点*/

这一句明明是current指向头结点为什么注释是那样？

程序如下：

struct listNode{

int data;

struct listNode *link;

};

typedef struct listNode LISTNODE;

typedef LISTNODE * LISTNODEPTR;/*LISTNODEPTR：指向LISTNODE指针*/

/*创建循环链表，容纳n个猴子。返回指向链表头结点的指针*/

LISTNODEPTR createList(int m)

{

LISTNODEPTR head=NULL,tail,current;

int i;

for(i=1;i<=m;i++){

current=(LISTNODEPTR)malloc(sizeof(LISTNODE));

current->data=i;

current->link=NULL;

if(head==NULL){/*若是作为头结点*/

head=current;

tail=current;

}

else{/*将结点追加到链表末尾*/

tail->link=current;

tail=current;

}

}

tail->link=head;/*形成循环链表*/

return head;

}

void selectKing(LISTNODEPTR head,int n)/*n>=2*/

{

LISTNODEPTR prePtr=NULL,current;

int i;

i=0;

/*使current指向循环链表的最后一个结点*/

current=head;

while(current->link!=head)

数据结构

current=current->link;

while(current!=current->link){ /*往后数一个猴子*/

prePtr=current;

current=current->link;

i++;

/*若数到n，则淘汰current指向的猴子*/

if(i%n==0){

/*从head指向链表中拆下current指向的结点*/

prePtr->link=current->link;

current->link=NULL;

current=prePtr;

}

}

printf("大王的编号是：%d\n",current->data); free(current);

}

数据结构——猴子选大王

(2007-03-15 10:31:57)

转载

[题目] 第1.1猴子选大王问题

一：实验内容：

M只猴子要选大王，选举办法如下：所有猴子按1，2……n编号围成一圈，从第一号开始顺序1,2……m,凡是报m号的退出圈外，如此循环报数直到圈内只剩一只猴子时这只猴子就是大王。

二：实验要求：

利用单向循环链表模拟此过程，输出选出的大王编号。

三：程序的设计思想：

（1） 问题分析：“猴子选大王”问题是约瑟夫环问题的一个特例。由于本题目的数据元素个数不可知，所以可使用链表来动态的分配内存空间。而该问题又是一个不断的循环问题所以用循环链表来实现。

数据结构

（2） 总体设计：首先生成一个空链表，并给n个结点分配空间，让单链表的表尾指针指向头结点则生成一个带有n个结点的循环单链表。再给每只猴子建立顺序的编号。现从第一个结点开始报数，依次顺序查找出报数为m的待出列的结点（猴子）通过q->next=p->next删除该结点后继续运行否则让q成为p的前驱指针。最后当p->next==p时停止运行，得到p所指向的结点即为猴子选出大王的编号。

四：提供测试结果：

定义 n=8, m=3,测试结果如下：

对猴子进行编号！

1号猴子：1

2号猴子：2

3号猴子：3

4号猴子：4

5号猴子：5

6号猴子：6

7号猴子：7

8号猴子：8

1号猴子报：1

2号猴子报：2

3号猴子报：3

3号猴被淘汰

4号猴子报：1

5号猴子报：2

6号猴子报：3

6号猴被淘汰

7号猴子报：1

8号猴子 …… 此处隐藏：4890字，全部文档内容请下载后查看。喜欢就下载吧 ……