重庆交通大学信息科学与工程学
院
综合性设计性实验报告
专业：
课程名称：《C语言程序设计》
题目：数组和链表的操作
班级：
设计者：学号：
指导教师：
完成时间：2014年6月16日
重庆交通大学信息科学与工程学院综合性设计性实验任务
书
重庆交通大学信息学院综合性设计性实验评分表
数组和链表的操作——猴子选大王程序
设计报告
一、系统的功能需求及分析
功能：
一群猴子共有m只，编号为1，2，……m，围坐一圈，从第1号猴子开始依次报数，数到n的猴子退出，然后从退出的下一只猴子继续从1开始报数，依次循环，直到圈内剩下一只猴子为止，该编号的猴子就是所选出的大王。
分析：
用数组实现：
先对数组进行初始化，然后将报到要删除的那个数字的猴子编号赋值为-1，每赋值一次，猴子数减一，再重新报数。当猴子数只有一只的时候，输出猴子编号不为-1的那个编号。
用链表实现：
先建立一个无头节点的单向循环的链表，然后将报到要删除的那个数字的猴子编号删除，以此循环，直到一个节点的下一个指向自己，最后输出猴子编号。
二、设计说明
(一) 用数组实现
1、数组的初始化
for(i=0;ia[i]=i+1;
2、算法流程图及说明
(二) 用链表实现
1、节点的定义
struct monkey
{
int a;
struct monkey *next;
}*p,*q,*p1,*q1,*p2;
2、链表的建立
for (int i=0;i{
p=(struct monkey *)malloc(sizeof(struct monkey));
p->a=i+1;
p->next=NULL;
if (i==0)
{
head=p;
q=head;
}
else
{
q->next=p;
q=q->next;
}
}
q->next=head;
p2=head;
p1=head;
3、算法流程图及说明
三、主要代码
(一) 用数组实现
#include
void main()
{
int a[10000];
int m,n,x,b,i;
printf("请输入猴子的只数:");
scanf("%d",&m);
printf("请输入要删除的猴子编号:");
scanf("%d",&n);
for(i=0;ia[i]=i+1;
b=m;
x=0;
for(i=0;b!=1;i++)
{
if(a[i%m+1]!=-1)
{
x++;
}
if(x==n && a[i%m+1]!=-1)
{
a[i%m+1]=-1;
b--;
x=0;
}
}
for(i=1;i<=m;i++)
if(a[i]!=-1)
printf("猴子大王编号为:%d\n",i);
}
(二) 用链表实现
#include
#include
struct monkey
{
int a;
struct monkey *next;
}*p,*q,*p1,*q1,*p2;
void main()
{
struct monkey *head;
int m,n;
printf("请输入猴子的只数:");
scanf("%d",&m);
printf("请输入想删除猴子的编号:");
scanf("%d",&n);
for (int i=0;i{
p=(struct monkey *)malloc(sizeof(struct monkey));
p->a=i+1;
p->next=NULL;
if (i==0)
{
head=p;
q=head;
}
else
{
q->next=p;
q=q->next;
}
}
q->next=head;
p2=head;
p1=head;
for (i=1;;i++)
{
if (i==n-1)
{
q1=p1->next;
p1->next=q1->next;
free(q1);
i=0;
}
p1=p1->next;
if (p1->next==p1) break;
}
printf("猴子大王的编号为%d\n",p1->a);
}
四、系统功能测试
功能：一群猴子共有m只，编号为1，2，……m，围坐一圈，从第1号猴子开始依次报数，数到n的猴子退出，然后从退出的下一只猴子继续从1开始报数，依次循环，直到圈内剩下一只猴子为止，该编号的猴子就是所选出的大王。
下面四张图片是运行结果的截图，前两张是用数组方法做的，一组数据为m=5，n=3;另一组数据为m=15,n=7;后两张是链表做的，测试数据同数组一样，运行结果也一样。
