猴子选大王C语言课程设计

PAGEPAGE1课程设计课程设计报告样本数据结构课程设计报告题目：猴子选大王院（系）：计算机工程学院专业：计算机科学与技术班级：嵌入式109（1）学生：指导教师：寇海洲孙成富邱军林殷路2010年12月目录一、设计目的 1二、设计内容 1三、程序设计步骤 1四、调试分析 5五、测试结果 5六、课程设计小结： 6一、设计目的1、能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，分析并正确确定数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。2、提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。3、初步掌握软件开发过程中问题分析、系统设计、程序编码、测试等基本方法和技能。4、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。5、培养根据选题需要选择学习书籍，查阅文献资料的自学能力。二、设计内容1、系统名称：猴子选大王按照规定的要求，选出最后的一只猴子，为大王。2、要求：一堆有编号的猴子，编号为1，2，3……m，这群猴子（m个）按照1-m的顺序围坐一圈，从第一开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中剩下最后一只猴子，则该猴子为大王。三、程序设计步骤1）功能分析说明图：2）采用主要的数据结构类型。采用了链表的存储方式，属于链接存储结构。for(i=1;i<n;i++)//建立链表的存储结构{ p=(LINK)malloc(sizeof(Monkey)); p2->next=p; p2=p;}以下是用于存储结点的结构体的定义:typedefstructmonkey{ intnum;structmonkey*next;}Monkey,*LINK;基本算法：这个算法的主要流程为：从控制台读取猴子的数量和报数的最大数——>对猴子进行编号，并用链表来存储——>让链表中的猴子进行报数，对于报数为m的猴子则从链表中删除——>当链表中只剩下一个报数后则停止这个过程，这最后一个猴子即选出来的大王。以下为为猴子建立链表： for(i=1;i<n;i++)//建立链表的存储结构 { p=(LINK)malloc(sizeof(Monkey)); p2->next=p; p2=p;}以下为猴子进行编号：for(i=1;i<=n;i++)//对猴子进行编号 { p->num=i; //printf("%d号猴子：%d\n",p->num,p->num); p=p->next;}以下为最主要的算法过程，是通过一个While循环来控制的，是让猴子报数的过程，并删除报数为m的猴子：while(1) { i++; //当链表只剩最后一个元素了则跳出循环，此时报数已完成 printf("%d号猴子报：%d\n",p->num,i);if(p->next==p)break; if(i==m) { i=0; printf("%d号猴被淘汰\n",p->num); printf("\n"); p2->next=p->next; p=p2->next; continue; } else { if(i==m-1)p2=p; p=p->next; }}3）详细设计：#include<stdio.h>#include<stdlib.h>intn=2;intm=1;typedefstructmonkey{ intnum; structmonkey*next;}Monkey,*LINK;voidmain(){ printf("请输入一个整数（猴子数量）："); scanf("%d",&n); printf("请输入一个小于猴子数量的整数（报数的最大数）："); scanf("%d",&m); LINKp,head,p2; inti; head=p=p2=(LINK)malloc(sizeof(Monkey)); for(i=1;i<n;i++)//建立链表的存储结构 { p=(LINK)malloc(sizeof(Monkey)); p2->next=p; p2=p; } p2->next=head; p=head; //printf("对猴子进行编号！\n"); for(i=1;i<=n;i++)//对猴子进行编号 { p->num=i; //printf("%d号猴子：%d\n",p->num,p->num); p=p->next; } i=0; p=head; while(1) { i++; //当链表只剩最后一个元素了则跳出循环，此时报数已完成 printf("%d号猴子报：%d\n",p->num,i);if(p->next==p)break; if(i==m) { i=0; printf("%d号猴被淘汰\n",p->num); printf("\n"); p2->next=p->next; p=p2->next; continue; } else { if(i==m-1)p2=p; p=p->next; } } printf("胜出:%d",p->num);}四、调试分析调试的过程中，对程序做了几点改进，增加了程序的容错能力，不论用户输入什么内容，程序都能安全检查。这个算法主要考察了对数据存储方式的处理和循环判断的处理。我在这里用了链表的存储方式。五、测试结果 调试得到输出结果如图： 当输入n为6，m为4时的运行结果：六、课程设计小结：猴子选大王是一个数据结构很古老很经典的问题，融知识性和娱乐性为一体，能让人产生较大兴趣，因此编写程序实现之是一件很有意义的事。为编写这个程序的代码及写课程设计报告，我们花了两周的时间，下面说说我们在这期间的感悟。在课程设计中，首先要看清问题，将问题要求理解透彻，在构思要如何实现，要用到哪些函数，要用什么算法，在课程构思中选算法是一个很重要的概念，只有确定用这么算法后才能接下来的工作，将流程图画在纸上，再依次编写代码，在程序设计中，编写代码只是一个方面，调试才是关键。它是一个相当繁琐的过程，有许多新的问题需要被解决，但同时它也是一个比较重要的过程，因为在程序调试过程中，你会学到很多新的东西，从而增加你编程的经验。通过本次实习，温固了数据结构的相关知识，加深对课内所学的有关数据的逻辑结构和存储表示、数据结构的选择和应用、算法的设计和时空效率分析等课程