11信计2012-2013（一）
数据结构课程设计
设计题目猴子选大王
设计时间2012.12.31 至2013.1.6
学生姓名张政伟
学生学号20110402124
所在班级11精算
指导教师刘风华
徐州工程学院数学与物理科学学院
一、需求分析
问题定义：一堆猴子都有编号，编号是1，2，3…n,这群猴子（n个）按照1-n 的顺序围坐一圈，从第1个开始数，每数到第m个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。m，n键盘输入，且m问题分析：根据任务描述可知，编号是1，2，3…n的一群猴子按照1-n的顺序围坐一圈，因此可以用指针指向数组的方法给数组赋值，输入n值和m值，为保证m第一步建立数组，填入猴子编号及猴子出局时报的数
第二步从第一个猴子报数
第三步数到m让指针指向元素变为0
第四步继续报数，重复第三步
二、概要设计
程序流程图
三、详细设计
#include
#include //使用calloc()函数
void FindKing_pointer(int,int,int*);//移动指针法找大王void Initialize(int,int*);//初始化数组整形和指针型int main()
{
int m,n,*ptr;
printf("输入猴子数与出局时报的数\n");
scanf("%d %d",&n,&m);
{
printf("输入数据有误，请重新输入!\n");
printf("输入猴子数与出局时报的数\n");
scanf("%d %d",&n,&m);
}
ptr=(int *)calloc(n,sizeof(int));
Initialize(n,ptr);
FindKing_pointer(m,n,ptr);
free(ptr);
return 0;
}
/*
在数组中依次填入1,2,3,4,…
*/
void Initialize(int n,int *ptr)
{
int i;
for(i=0;iptr[i]=i+1;
}
/*
循环一次指针向后移一位,所指元素不为0时计数器加1.
移动指针,当计数器数到m时将指针所指元素设为0.
*/
void FindKing_pointer(int m,int n,int *ptr)
{
int i,count,*ptr2;
count=n-1; //count=0时终止循环就是只剩一个猴子时
ptr2=ptr; // 移动ptr2进行查找开始时ptr为多少
//calloc()为指针类型的元素分配内存时，元素被初始化为空指针for(i=0;count!=0;ptr2++)
{
if(ptr2==ptr+n)
ptr2=ptr;
/*指针所指元素不为0时计数器加1.*/
if(*ptr2!=0)
i++;
/*计数器数到m时将指针所指元素设为0*/
if(i==m)
{
count--; //用于终止循环
}
}
/*最后不为0的元素的值即为大王的编号*/
for(ptr2=ptr;;ptr2++)
{
if(*ptr2!=0)
{
printf("第%d个猴子是大王\n",*ptr2);
break;
}
}
}
/*思想是猴子围坐一圈，有N个猴子，开始数数，数到第M个猴子，该猴子就出列，
然后再从该猴子的下一个猴子开始数到第M个猴子，直到只剩下一个猴子时。该猴子就是所要选得大王*/
四、调试分析
1）输入猴子数与出局时报的数
9 5
第6个猴子是大王
2）输入猴子数与出局时报的数
5 3
第5个猴子是大王
3) 输入猴子数与出局时报的数
6 8
输入数据有误，请重新输入!
输入猴子数与出局时报的数
7 7
第2个猴子是大王
4）输入猴子数与出局时报的数
145 145
第94个猴子是大王
5）输入猴子数与出局时报的数
5 1
第6个猴子是大王
五、结果分析
六、设计总结
在课程设计中，首先要看清问题，将问题要求理解透彻，在构思要如何实现，要用到哪些函数，要用什么算法，在课程构思中选算法是一个很重要的概念，只有确定用这么算法后才能接下来的工作，将流程图画在纸上，再依次编写代码，在程序设计中，编写代码只是一个方面，调试才是关键。它是一个相当繁琐的过程，有许多新的问题需要被解决，但同时它也是一个比较重要的过程，因为在程序调试过程中，你会学到很多新的东西，从而增加你编程的经验。通过本次实习，温固了数据结构的相关知识，加深对课内所学的有关数据的逻辑结构和存储表示、数据结构的选择和应用、算法的设计和时空效率分析等课程基本内容的理解，进一步熟悉了VC++编程环境，巩固并提高了分析问题、解决实际问题的能力。
