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

LULIANG UNIVERSITY

数据结构课程设计

题 目: 猴子选大王

系 别: 计算机科学与技术系
专业年级: 软件工程1502班
姓 名:
学 号:
指导教师:

2016年11月25日

目 录
一、设计任务与要求 1
1.1 总体目标与任务要求 1
1.2 题目选择与目的意义 1
1.3 所选题目的主要工作 1
二、需求分析 2
2.1 用户需求分析 1
2.2 功能需求分析 2
三、概要设计 2
四、详细设计（源代码） 3
五、调试分析 9
六、运行结果分析 10
七、收获与体会 12
八、主要参考资料 13

《数据结构课程设计》
一、设计任务与要求
1.1 总体目标与任务要求
一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。
输入数据：输入m,n m,n 为整数，n<m
输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号 ，建立一个函数来实现此功能

1.2 题目选择与目的意义
完成此系统，需要综合运用数据结构课程中学到的几种典型数据结构，以及程序设计语言（C语言），自行实现一个较为完整的应用系统的设计与开发。通过课程设计，自己通过系统分析、系统设计、编程调试，写实验报告等环节，进一步掌握应用系统设计的方法和步骤，灵活运用并深刻理解典型数据结构在软件开发中的应用。学会将知识应用于实际的方法，提高分析和解决问题的能力，增加综合能力。
1.3 所选题目的主要工作
一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。
二、需求分析
2.1 用户需求分析
用户使用此程序所要完成的工作主要为：查询所有航线信息、查看已订票客户信息、查询航线、办理订票业务、办理退票业务。通过此系统可以方便的进行上述工作。
每条航线所涉及的信息有：终点站名、航班号、飞行时间、票价、乘员定额、余票量。
已订票的客户名单信息包括姓名、订票量、舱位等级（1，2或3）。
等候替补的客户名单信息包括姓名、所需票量。
查询航线功能可以根据旅客提出的终点站名输出航班号、飞行时间、票价、乘员定额、余票量。
订票业务功能根据客户提出的要求（航班号、订票数额）查询该航班票额情况，若尚有余票，则为客户办理订票手续，输出座位号；若已满员或余票额少于定票额，则需重新询问客户要求。若需要，可登记排队候补购票。
退票业务功能根据客户提供的情况（航班号、姓名）为客户办理退票手续，然后查询该航班是否有人排队候补，首先询问排在第一的客户，若所退票额能满足他的要求，则为他办理订票手续，否则依次询问其他排队候补的客户。
2.2 功能需求分析
问题定义：一堆猴子都有编号，编号是1，2，3…n,这群猴子（n
个）按照1-n的顺序围坐一圈，从第1个开始数，每数到第m个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。m，n键盘输入，且m<n，输出为大王猴子的号数。问题分析：根据任务描述可知，编号是1，2，3…n的一群猴子按照1-n的顺序围坐一圈，因此可以用指针指向数组的方法给数组赋值，输入n值和m值，为保证m<n，用一个while( )语句实现，如果输错，报错，再输入。用for循环实现猴子编号。从1开始数到m的猴子出列，即用指针移动查找法将计数器数到m的指针指向的内容变为0，用for循环，直到只有一个元素不为0时，最后不为0的元素的值即为大王。实现这个程序功能需3个模块，一个模块用数组指针实现猴子编号，一个模块用指针移动查找法实现猴子出局，最后主模块将前两个模块要用到的函数，数组定义。具体步骤如下：
第一步 建立数组，填入猴子编号及猴子出局时报的数
第二步 从第一个猴子报数
第三步 数到m让指针指向元素变为0 
第四步  继续报数，重复第三步
三、概要设计

四、详细设计（源代码）
#include<stdio.h>
#include<malloc.h>
int m,n;
typedef int DataType;
typedef struct LNode {
DataType data;
struct LNode *next;
} monkey;//定义结点
void Link_solve()
{ int i;
int a=m;
int count=1;//统计次数
monkey *head,*p,*q,*s;
head=q=p=(monkey *)malloc(sizeof(monkey));
printf("\n**** 对猴子进行编号：****\n");
for(i=1;i<m;i++)//为猴子形成链表
{
q=(monkey *)malloc(sizeof(monkey));
q->data=i;
p->next=q;//使链表循环起来
p=q;
printf("第%d位猴子的编号是：%d\n",i,i);
}
printf("第%d位猴子的编号是：%d\n",i,i);
q->next=head;
head->data=m;
p=head;
q=p->next;
printf("\n");
if(m==1)
printf("\n按照1个猴子，猴子大王的编号是:1\n");

else if(m!=1)
{
if(n==1)
{
for(i=1;i<m;i++)
printf("第%d次，要删除的猴子号为:%d\n",i,i);
printf("\n按照%d个猴子，数1个数\n猴子大王的编号是:%d \n",m,m);
}
else
{
for(i=1;i<n;i++)
{
p=p->next;
q=q->next;
if(i==n-1)
{
printf("第%d次,要删除的猴子号为:%d\n",count++,q->data);
s=q;
q=q->next;//q即为被点到的猴子
p->next=q;//删除q结点
free(s);//释放内存
i=0;//计数器清零，重新开始计数
a--;
}
if(a==1)
break;
}
printf("\n按照%d个猴子，数%d个数\n猴子大王的编号是:%d \n",m,n,q->data); //此时的结点就是大王
}
}
}
void Array_solve()
{
int a[1000];//定义一个较大的数组存储数据
int x,count=1,y,i;
printf("\n**** 对猴子进行编号：****\n");
for(i=0;i<m;i++){
a[i]=1;
printf("\n第%d位猴子的编号是：%d",i+1,i+1);
}
printf("\n\n"); x=0;//令x初始值为零
y=m;
for(i=0;y!=1;i++)// 执行循环，淘汰的猴子值为0，直到只剩一只猴子，即为猴王
{ if(a[i%m]!=0)
x++;//计数加1
if(x==n&&a[i%m]!=0)
{
a[i%m]=0;
x=0;
printf("第%d次，要删除的猴子号为：%d\n",count++,i%m+1);
y--;//当前的猴子数减1
}
}
for(i=0;i<m;i++) //输出值不为0的猴子，即猴王
if(a[i]!=0)
printf("\n按照%d个猴子，数%d个数\n猴子大王的编号是:%d \n",m,n,i+1);
}
void main()
{
int select;
int x;
for(x=0;x<19;x++)
{
printf("==");
}
printf("\n");
printf("\t猴子选王问题求解\t\n");
for(x=0;x<19;x++)
{
printf("==");
}
printf("\n\n");
printf("* 请输入猴子的总数 m : ");
scanf("%d",&m);
printf("\n");
printf("* 请输入周期数 n : ");
do
{
scanf("%d",&n);
printf("\n");
if(m<n)
printf("m应该大于n，请重新输入n：");
}while(m<n);
printf("===== 请选择 : =====\n\n");
printf("**** 1.链表处理 ****\n");
printf("**** 2.数组处理 ****\n\n");
scanf("%d",&select);
switch(select)
{ case 1 : Link_solve();//调用链表
break;
case 2 : Array_solve();//调用数组
break;
defult:
break;
}
}
五、调试分析
1）输入猴子数与出局时报的数
   9 5 
   第6个猴子是大王
2）输入猴子数与出局时报的数
   5 3 
   第5个猴子是大王

3)输入猴子数与出局时报的数
   6 8     
输入数据有误，请重新输入!    
输入猴子数与出局时报的数
   7 7    
第2个猴子是大王  
4）输入猴子数与出局时报的数 
   145 145    
第94个猴子是大王 
5）输入猴子数与出局时报的数 
   5 1 
   第6个猴子是大王
六、运行结果分析

七、收获与体会
在课程设计中，首先要看清问题，将问题要求理解透彻，在构思要如何实现，要用到哪些函数，要用什么算法，在课程构思中选算法是一个很重要的概念，只有确定用这么算法后才能接下来的工作，将流程图画在纸上，再依次编写代码，在程序设计中，编写代码只是一个方面，调试才是关键。它是一个相当繁琐的过程，有许多新的问题需要被解决，但同时它也是一个比较重要的过程，因为在程序调试过程中，你会学到很多新的东西，从而增加你编程的经验。通过本次实习，温固了数据结构的相关知识，加深对课内所学的有关数据的逻辑结构和存储表示、数据结构的选择和应用、算法的设计和时空效率分析等课程基本内容的理解，进一步熟悉了VC++编程环境，巩固并提高了分析问题、解决实际问题的能力。

八、主要参考资料
1、严蔚敏、吴伟民，数据结构C语言版，清华大学出版社，1997年4月
2、夏涛，C语言程序设计，北京邮电大学出版社，2007年3月
3、谭浩强，C程序设计（第三版），清华大学出版社，2006年2月
4、百度：百度知道，百度文库

指导教师签字：

2016年 12月11日目 录
第一章 总论 1
第一节 项目背景 1
第二节 项目概况 2
第二章 项目建设必要性 5
第三章 市场分析与建设规模 7
第一节 汽车市场需求分析 7
第二节 市场预测 12
第三节 项目产品市场分析 13
第四节 建设规模 16
第四章 场址选择 17
第一节 场址所在位置现状 17
第二节 场址建设条件 17
第五章 技术方案、设备方案、工程方案 22
第一节 技术方案 22
第二节 设备方案 28
第三节 工程方案 33
第六章 原材料、燃料供应 38
第七章 总图布置与公用辅助工程 39
第一节 总图布置 39
第二节 公用辅助工程 43
第八章 环境影响评价 52
第一节 环境保护设计依据 52
第二节 项目建设和生产对环境的影响 52
第三节 环境保护措施 54
第四节 环境影响评价 56
第九章 劳动安全卫生与消防 57
第一节 劳动安全卫生 57
第二节 消防 64
第十章 节能与节能措施 67
第一节 项目概况 67
第二节 项目综合能耗 69
第三节 节约及合理利用能源的主要措施 71
第十一章 项目实施进度与人力资源配置 76
第一节 建设工期 76
第一节 项目实施进度 76
第二节 生产组织与人员培训 79
第十二章 投资估算与资金筹措 82
第一节 建设投资估算 82
第二节 总投资估算 86
第三节 资金筹措 86
第十四章 财务效益分析 88
第一节 财务评价基础数据与参数选取 88
第二节 销售收入及销售税金估算 89
第三节 成本费用估算 89
第四节 财务评价 91
第五节 不确定性分析 93
第十三章 风险分析 95
第十四章 结论与建议 97
第一节 研究结论 97
第二节 建议 97

15