用C编写程序猴子选大王.docx
《用C编写程序猴子选大王.docx》由会员分享，可在线阅读，更多相关《用C编写程序猴子选大王.docx（24页珍藏版）》请在冰点文库上搜索。
用C编写程序猴子选大王
湖南人文科技学院计算机系
课程设计说明书
课程名称：
数据结构
课程代码：
题目：
猴子选大王
年级/专业/班：
06级计算机科学与技术专业一班
学生姓名：
学号:
06408109064081020640810706408122
06408103
指导教
师：
刘
刚
常
开题时
间：
2008
年
6月16
日
完成时
间：
2008
年
6月29
日
.3.
、设计目的与任务
1、总体设计5
2、详细设计8
3、程序清单14
4、程序调试与体会2.2....
5、运行结果23....
四、结论24....
五、致谢24....
六、参考文献25....
摘要
本文首先介绍顺序表和链表并作以比较，我们分别使用循环队列和循环链表来解决猴子选大王的问题，程序使用了C语言编写，有很少一部分函数是用C++编写的，有比较详细的中文注释并在VC++下调试运行通过。
整个程序使用中文界面，并有相应的提示信息，便于操作和程序运行。
关键词：
循环队列；循环链表；存储结构
Abstract
Thispaperdetailsthediffereneeofsequeneelistandlinklist.Werespectively
usequeueandcircularqueueandcircularlinkedlisttosolvetheseekelectedking
ofthemonkeyproblem.TheprocedurewritewithCIanguage，averysmallpart
functionisusedbytheC++,andhaschineseexplanatorynote.What'smore,itwas
debuggedinVC++debuggerandrunverywell.Thewholeprocedure,withChineseinterfaceandthecorrespondinghints,isconvenienttorunandeasytobeoperated.
storagestructure
Keywords:
circularqueue；circularlinkedlist
《数据结构》课程设计
猴子选大王
一、弓I言
数据结构是一门非常重要的基础学科，但是实验内容大都不能很好的和实际应用结合起来。
从而让很多学生认为学习数据结构并没有很大的作用。
但本实验运用数据结构的知识，很好的解决了一个对于人脑来说比较烦琐的实际问题。
链表是一种以链式结构存储的线性表，特点是数据元素可以用任意的存储单元存储，
线性表中逻辑上相邻的两元素存储空间可以是不连续的。
同时为了表示逻辑关系，每个
数据元素除了存放自身的数据信息外还要存储一个指示其直接后继的信息。
队列是一种先进先出的线性表。
它只允许在的表的一端进行插入，而在另一端删除元素。
循环队列是队列的顺序表示和实现。
从时间上考虑顺序表中插入和删除元素的时间复杂度为0（N）,查找
元素的时间复杂度为0
（1）;而链表中插入和删除元素的时间复杂度为0
（1）,查找元素的时间复杂度为0（N）。
而链表中除了存放自身的数据信息外，还要存放后继结点的地址信息，存储密度不高。
本设计分别通过一个顺序存储结构和一个链表存储结构，再加适当函数与改变，就简
明的解决了猴子选大王这个实际问题，其中顺序存储结构我们使用的是循环队列。
依次按要求淘汰猴子一直到找到猴王，并依次显示被淘汰猴子的编号，输出猴王的编号。
该程序具有一定的通俗性与实用性，其他类似的算法均可借鉴和参考使用。
该程序清单详细具体、全面，为了使组员之间能够很好的理解各自完成的程序，促进组员之间的沟通，我们在程
序中添加了较多的注释和说明，具有很强的可读性。
二、设计目的与任务
1、本课程设计的目的
1）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能并培养学生进行规范化软件设计的能力。
2）训练学生灵活应用所学数据结构的基本知识，熟练的完成问题分析、算法设计、编写程序，求解出指定的问题；
3）提高综合运用所学的理论知识和方法独立分析和解决问题的能力；
4）训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知
识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。
5）使学生会使用各种计算机资料和有关参考资料，提高学生进行程序设计基本能力。
2、本课程设计的任务
问题描述：
1）分别使用顺序和链表二种存储结构
2）功能实现：
一群猴子都有编号，编号是1，2,3...m，这群猴子（m个）按照
1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。
输入数据：
输入m,n。
其中m,n为整数，*m
输出形式：
依次显示离开圈的猴子编号，并且输出为大王的猴子编号。
三、设计方案
1、总体设计
1）使用顺序存储结构实现
我们选择的是使用一个循环队列来完成这个设计。
定义并构造一个空循环队列，把猴子按照1到m的顺序依次进入该队列，再按题目要求把被淘汰的猴子踢出队列，使用两个循环把被淘汰猴子的编号和猴王的编号分别输出。
本设计使用循环队列求解猴子选大王的问题，程序中定义的数据结构如下:
定义一个循环队列typedefstructSqQueue
进队列intEnQueue（SqQueue&Q,QEIemTypee）
出队列intDeQueue（SqQueue&Q,QEIemType&e）
主程序包含模块：
typedefstructSqQueue
{//定义一个循环队列
}SqQueue;
intInitQueue（SqQueue&Q）
{II初始化}
intEnQueue（SqQueue&Q,QEIemTypee）
{II进队列
}//EnQueue（）end
intDeQueue（SqQueue&Q,QEIemType&e）
{II出队列}IIDeQueue（）end
intQueueLength（SqQueueQ）
{II返回Q的元素个数，即队列的长度}IIQueueLength（）end
voidexit（）
{}
voidChange（SqQueue&Q）
{II选大王}
voidmain（）
{SqQueueQ;
InitQueue（Q）;
Change（Q）;
}
2）使用链表存储结构实现
我们选择用一个循环链表来完成该设计，设计一个猴子的结构体，并开辟空间用来存
储猴子结构，生成了一个猴子结构的循环链表，对链表中的猴子进行编号，报号到n的
猴子被淘汰，最后剩下的猴子为猴王，把依次被淘汰的猴子和猴王输出。
本设计使用循环链表求解猴子选大王的问题，程序中定义的数据结构如下：
设计一个猴子的结构体typedefstructmonkey
开辟空间用来存储猴子结构head=p=p2=（LINK）malloc（sizeof（Monkey））
开辟新空间用来存各个猴子结构p=（LINK）malloc（sizeof（Monkey））
把链表变成循环链表p2->next=head
报号为n的猴子被淘汰，最后剩下的是猴王，输出被淘汰的猴子和猴王
while
（1）
{
if（i==m）{printf（"%d号猴被淘汰\n",p->num）}
else{//没有报到m的继续报数}
printf（"猴王的编号为:
%d",p->num）;}
3）菜单选择函数程序
intmenu_select（）//
{
intx;
printf（"
\t\t
1使用顺序表\n"）;
printf（"
\t\t
2使用链表\n"）;
printf（"
\t\t
请选择：
"）;
2、详细设计
1）使用顺序存储结构实现
（1）输入m,n.m是猴子的总个数，n是小于m的正整数数。
⑵把m只猴子编上好“1，2，3••…m”然后按照1--m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。
（3）输出最后剩下的那只猴子的编号，这猴子就是大王。
（4）对结果进行分析
本程序设计中所包括的函数如下：
typedefintQEIemType;
typedefstructSqQueue//定义一个循环队列
{、、、、、、、、、、、、、、、、、、、、、、、、、、、、、
}SqQueue;
intInitQueue（SqQueue&Q）//初始化
{、、、、、、、、、、、、、、、、、、、、、、、、、、、、、
}
intEnQueue（SqQueue&Q,QElemTypee）//进队列
}〃EnQueue（）end
intDeQueue（SqQueue&Q,QEIemType&e）
//出队列
{、、、、、、、、、、、、、、、、、、、、、、、、、、、、、
}〃DeQueue（）end
intQueueLength（SqQueueQ）//返回Q的元素个数，即队列的长度
{、、、、、、、、、、、、、、、、、、、、、、、、、、、、、
}//QueueLength（）end
voidexit（）
{
}
voidChange（SqQueue&Q）//选大王
{
intn,m;
inte;
coutvv"输入猴子总数：
"；
cin>>m;
for（intj=1;j<=m;j++）
EnQueue（Q,j）;
coutvv"从第1个开始数，每数到第n个，该猴子将离开此圈"<cout«"请输入n:
"<cin>>n;
coutvv"被淘汰猴子的顺序为:
";
if（nwhile（QueueLength（Q）!
=1）
//当只剩下一个元素时循环结束，依次输出被淘汰猴子
编号
{
for（inti=0;i{
e=DeQueue（Q,e）;
EnQueue（Q,e）;
}
e=DeQueue（Q,e）;
cout«e;
}
while（Q.front!
=Q.rear）//循环到最后找出猴王
{
for（inti=0;i{
e=DeQueue（Q,e）;
EnQueue（Q,e）;
}
e=DeQueue（Q,e）;
}
coutvv"猴王是编号为"vvevv"的猴子"<Change（Q）;
voidmain（）
{
SqQueueQ;
InitQueue（Q）;
Change（Q）;
}
2）使用链表存储结构实现
（1）设计一个猴子的结构体,typedefstructmonkey
（2）输入m,n.m是猴子的总个数，n是小于m的正整数数。
（3）开辟空间用来存储猴子结构，生成了个猴子结构的链表，并使其循环
head=p=p2=（LINK）malloc（sizeof（Monkey））;
for（i=1;i{
p=（LINK）malloc（sizeof（Monkey））;
p2->next=p;
p2=p;
}
p2->next=head;
}
（4）找出所有被淘汰的猴子编号和猴王的编号，并将其输出。
while
（1）
i++；if（p->next==p）
break;
if（i==n）
{
i=0;
p2->next=p->next;
printf（"%d",p->num）;
p=p2->next;
}else
{
if（i==n-1）p2=p;
p=p->next;
}
}
printf（"猴王的编号为:
%d\n",p->num）;
}
3）主菜单选择程序和主函数
intmenu_select（）//菜单选择函数程序
intx;
printf（"
\t\t
猴子选大王系统\n"）;
printf（"
\t\t
1使用顺序表\n"）;
printf（"
\t\t
2使用链表\n"）;
printf（"
\t\t
请选择：
"）;
for（;;）
{
seanf（"%d",&x）;
if（x<=0||x>2）
printf（"\n\t输入错误，重选1-2:
"）;
else
break;
returnx;
}
}
voidmain（）
{
switch（menu_select（））
{
case1:
SqQueueQ;
InitQueue（Q）;
Change（Q）;
break;
return;
case2:
monkey（）;
break;
return;
}
}
3、程序清单
#include
#include
#include
#include
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT10
#defineMAXQSIZE100
#defineOK1
#defineERROR0
typedefintQElemType;
typedefstructSqQueue//定义一个循环队列
{QElemType*base;
intfront;
intrear;
}SqQueue;
intInitQueue（SqQueue&Q）//构造一个空队列Q
{Q.base=（QEIemType*）malloc（MAXQSIZE*sizeof（QEIemType））;if（!
Q.base）
returnERROR;//存储分配失败
Q.front=Q.rear=0;
returnOK;
}
intEnQueue（SqQueue&Q,QElemTypee）//进队列
{if（（Q.rear+1）%MAXQSIZE==Q.front）
returnERROR;//队列满
Q.base[Q.rear]=e;
Q.rear=（Q.rea叶1）%MAXQSIZE;
returnOK;
}〃EnQueue（）end
intDeQueue（SqQueue&Q,QElemType&e）//出队列
{if（Q.front==Q.rear）
returnERROR;
e=Q.base[Q.front];
Q.front=（Q.front+1）%MAXQSIZE;
returne;
}〃DeQueue（）end
intQueueLength（SqQueueQ）//返回Q的元素个数，即队列的长度
{
return（Q.rear-Q.front+MAXQSIZE）%MAXQSIZE;}//QueueLength（）
endvoidexit（）
{
}
voidChange（SqQueue&Q）//选大王
{
intn,m;
inte;
coutvv"输入猴子总数：
"；
cin>>m;
for（intj=1；j<=m;j++）
EnQueue（Q,j）;
cout«"请输入n:
"<cin>>n;
coutvv"被淘汰猴子的顺序为
if（nwhile（QueueLength（Q）!
=1）//当只剩下一个元素时循环结束，依次输出被淘汰的猴
子编号
{
for（inti=0;i{
e=DeQueue（Q,e）;
EnQueue（Q,e）;
}
e=DeQueue（Q,e）;
cout«e;
}
while（Q.front!
=Q.rear）//循环到最后找出猴王
{
for（inti=0;i{
e=DeQueue（Q,e）;
EnQueue（Q,e）;
e=DeQueue（Q,e）;
}
coutvv"猴王是编号为"vvevv"的猴子"<Change（Q）;
}
}
typedefstructmonkey//设计一个猴子的结构体，该结构体用monkey表示
//link表示该结构体的指针
{
intnum;//它的号码
structmonkey*next;//下个猴子的地址指针
}Monkey,*LINK;
voidmonkey（）
{
intn,m;
printf（"请输入猴子总数m的值:
\n"）;
scanf（"%d",&m）;
printf（"请输入n的值:
\n"）;
scanf（"%d",&n）;
printf（"被淘汰猴子的顺序为:
"）;
LINKp,head,p2;//定义了三个猴子结构的指针
inti;
head=p=p2=（LINK）malloc（sizeof（Monkey））;//开辟空间用来存储猴子结构
for（i=1;i{
p=（LINK）malloc（sizeof（Monkey））;//开辟新空间用来存各个猴子结构
p2->next=p;
p2=p;
}
p2->next=head;〃这步很重要，这样链表变成循环链表了，也就是说链表到了结
//尾它的下个地址就是链表头了如此不停循环下去，就是个圆
p=head;
for（i=1;i<=m;i++）
{
p->num=i;//对猴子编号
p=p->next;//指针指向下个猴子
}//所有猴子编号结束
i=0;
p=head;//又将p指向了链表的头
while
（1）
{
i++;
if（p->next==p）〃这是结束条件，你想自己的下一个就是自己本身了，是不是说
//明只剩下自己了，也就是大王了break;
if（i==n）//如果这一个报到了数n
{
i=0;//再次从1开始报数，因为以后要执行i++语句
p2->next=p->next;//将该猴子从链表中拿下
printf（"%d",p->num）;//这个号码的猴子要被淘汰
p=p2->next;//指针指向下一个猴子
}
else//没有报到m的继续报数
{
if（i==n-1）p2=p;
p=p->next;
}
}
printf（"猴王的编号为:
%d\n",p->num）;
intmenu_select（）//菜单选择函数程序
intx;
printf（"
\t\t
猴子选大王系统\n"）;
printf（"
\t\t
1使用顺序表\n"）;
printf（"
\t\t
2使用链表\n"）;
printf（"
\t\t
请选择：
"）;
for（;;）
{
scanf（"%d",&x）;
if（x<=0||x>2）
printf（"\n\t输入错误，重选1-2:
"）;
else
break;
returnx;
}
}
voidmain（）
{
switch（menu_select（））
{
case1:
SqQueueQ;
InitQueue（Q）;
Change（Q）;
break;
return;
case2:
monkey（）;
break;
return;
}
}
4、程序调试与体会
程序调试的步骤：
1）调试各个模块函数，并测试模块间参数的传递与调用。
2）调试主函数和对其他模块函数的调用，并检验最后的输出结果。
本程序还算比较简单，用链表存储结构不是很复杂，在使用循环链表的程序中最主要的是定义一个结构体，然后构造一个循环链表并为其在结构体中开辟存储空间。
但是真正的程序中还要考虑各种限制条件，这就给调试过程带来一些问题，例如在出队列的过程中,
可能队列已经为空队列，就要给出该队列为空队列此信息的提示，还有在使用循环队列的程序中我们刚开始只能输出猴王的编号，却不能输出各个被淘汰猴子的编号，后来才发现是循环控制的不对，在使用循环链表的程序中我们刚开始调试根本不出结果，后来发现是在编号和循环函数之前没返回链表的表头。
通过本次课程设计，我们学到了很多东西：
首先，平时在学理论知识时觉得很简单容易的知识，实践起来并不是那么容易。
比如
最基础的构造结构体，要完全不出错的用自己的语言输到屏幕上，却要求对相关知识的掌
握熟练到一定程度。
又如，循环的次数不能多也不能少，否则就会导致输出结果不是所需的。
其次，只有理论知识没实践经验是不可能成为一名出色的软件设计师的。
理论是实践的基础，实践是对所学知识的巩固与提高，只有理论与实践相结合才能真正掌握知识。
再次，我们还懂得了团结精神的重要性。
设计思路是最重要的，只有大家讨论出来的
设计思路才是清晰的，这是程序设计成功的关键。
在本次程序设计过程中，大家共同努力，分工合作，一起到图书馆找资料，找范文，并在网上搜索了大量的资料，共同学习，使得我们共同进步。
一个人的力量是有限的，但团结的力量是无穷的。
在竞争如此激烈的当今社会，这些东西都是终生实用的，为我们以后的工作和学习奠定了基础。
最后，这次程序设计提炼了我们的心理素质。
设计过程是一个考验人耐心的过程，不能有丝毫的急躁，马虎。
在不影响试验的前提下可以加快进度。
必须要有耐心，要有坚持的毅力。
程序需要反复调试，其过程很可能相当烦琐，而且在程序调试出来后写报告书也是一个很繁琐的过程，有时花很长时间写出来的报告书还是需要重写，那时心中未免有点灰心，有时还特别想放弃，此时更加需要静下心，查找原因。
5、运行结果
主菜单函数运行结果如图1所示，主菜单函数是一个选择函数
ul"D:
\Pro|[EasFilesWebusYDOO
图1有两种选择，输入你要选择的一项
使用顺序表程序运行结果如图2所示，输入选择1，输入猴子总数和n的值
图2猴子总数为6，n为2，依次被淘汰的猴子是24631号，猴王为5号
使用链表程序运行结果如图3所示，输入选择2，输入猴子总数和n的值
图3猴子总数为9，n为4，依次被淘汰的猴子是48396572号，猴王为1号
四、结论
经过将近两周的数据结构课程设计，我们分别使用循环链表和循环队列的一些基本操
作终于完成实现猴子选大王的设计，猴子选大
升级会员 