《数据结构》 课程设计报告
设计题目 班 级 姓 名 学 号 指导教师 日 期 猴子选大王 2012年6月25日
计算机与信息工程系
《数据结构》课程设计评阅表
设计题目 班级 答辩评语： 姓名 猴子选大王 学号 总结报告评语： 功能实现 答辩效果 设计报告 创 新 总 分
一、引言
1、目的
(1)本次程序程序设计的主要目的是解决变相的“约瑟夫环”问题---猴子大王。从而使复杂的甄选工作变得明朗简单化。同样，这种解决问题的思想还可以运用到其他具有类似问题的领域，达到一点窥面的效果。 2、课程设计要求
针对本次猴子数为m，循环数为n的猴子选大王问题，要求如下： （1）基本要求：输入数据m，n为整数。
（2）输出形式：中文提示按照m个猴子，数n个数的方法，输出为大王的猴子几号，建立一个函数来实现此功能。
（3）实现方案：使用循环单链表。 3、课程设计实验环境：C语言 4、意义
培养我们的数据抽象能力。利用单向循环链表模拟此过程，输出选出的大王编号。通过本课程设计，可加深我们对链表的了解，对今后的学习有很大帮助。 5、功能实现
全程序以数据结构（C语言）中的循环单链表为主要的设计支柱，利用了C语言简洁紧凑、灵活方便，语法限制不太严格，程序设计自由度大，生成目标代码质量高，程序执行效率高等方面的优点。循环单链表是单链表的另一种形式，其结构特点是链表中最后一个结点的指针域不再是结束标记，而是指向整个链表的第一个结点，从而使链表形成一个环，基于这样的特点，它适合处理具有环形结构的数据元素序列。在程序代码的编写中，运用了结构体类型（struct Node），动态申请内存空间函数malloc（），释放动态申请内存空间函数free（）等类型，同时也具有多种循环、条件语句控制程序流向，如：嵌套if else语句，多重for循环语句，还有链表中结点指针（p->next），从而使程序完全结构化。这样编写出的完整程序代码可以实现“猴子选大王”功能，输入猴子的数目m，循环数n，对m个猴子进行编号，通过嵌套if else语句，for语句，一遍一遍的循环，判断，删除，直到只剩下最后一个猴子，即大王。这样就可以实现所需的基本功能了。
二、设计过程
1、头文件说明 ① #include
此程序主要以C语言为编写语言，因此在程序中要用到系统提供的标准库函数中的输入，输出函数，例如：scanf()函数,printf()函数。所以必须在程序开头一行写上#include
例如，程序中用到的相关函数就有printf(\；scanf(\；等。
② #include
在这个程序中，用到的主要是数据结构中的循环单链表方面的相关知识。我们把由一个数据元素域及一个或若干个指针域组成的结构体称为一个结点。而在单链表中的每个结点，实在需要时才向系统申请的，也就是所谓的动态内存空间申请。动态申请的内存空间，当不再需要时，必须由申请者自己释放。C语言提供了动态申请内存空间的函数malloc（）和动态释放内存空间的函数free（）。这些函数都包含在头文件malloc.h中。所以也必须在程序开头写上#include
这一句就是申请占用字节个数为sizeof(monkey)的monkey类型的一个结点，并且让head，q，p三个指针同时指向这个结点。 ③ typedef int DataType;
我们都知道，没有实际含义的数据元素称作抽象数据元素。在设计时遇到抽象数据元素，我们将用DataType表示该抽象数据元素的数据类型；而当软件设计问题具体确定时，抽象数据元素的数据类型将被具体的数据类型所取代。在本程序中，要求线性表的数据类型为int类型，可以通过重新定义抽象数据元素为int类型，来确定该抽象数据元素的数据类型。即相应的C语句为typedef int DataType; 2、结构体说明 typedef struct Node {
DataType data; struct Node *next; }monkey; //定义结点
我们把由一个数据元素域及一个或若干个指针域组成的结构体称为一个结点，其中数据域用来存放数据，指针域用来构造数据元素之间的关联关系。
所以函数中定义了单链表的结构体struct Node，其中data域用来存放数据素，next域用来存放一个结点的指针。monkey是struct Node类型的变量。且链表的结点结构如下图所示
data next
3、main()函数说明 void main() {
monkey *head,*p,*q,*s;
int m,n,i;
printf(\请输入猴子的总数:\scanf(\printf(\
printf(\请输入周期数:\scanf(\printf(\
printf(\对猴子进行编号:\\n\\n\
head=q=p=(monkey *)malloc(sizeof(monkey)); for(i=1;i q=(monkey *)malloc(sizeof(monkey)); q->data=i; p->next=q;//使链表循环起来 p=q; printf(\第%d位猴子的编号是:%d\\n\ } q->next=head; head->data=m; p=head; q=p->next; printf(\第%d位猴子的编号是:%d\\n\printf(\if(m==1) printf(\猴子大王的编号是:1\\n\ else if(m!=1) {