敢死队问题课程设计报告

数据结构课程设计题目：《敢死队问题》作者：***院(系)：信息工程学院专业：信息管理与信息系统指导教师：***日期：2013年11月26日2/11目录第一章绪论……………………………………………………………3第二章需求分析………………………………………………………4第三章详细设计………………………………………………………4第四章调试分析………………………………………………………7第五章测试结果………………………………………………………8第六章源程序代码……………………………………………………8第七章实验总结………………………………………………………10第八章参考文献………………………………………………………113/11第一章绪论课程设计时实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个发面，是一门独立于课程之外的独立课程。课程设计时让同学们对所学的课程更全面的学习和应用，可以理解和掌握课程的相关知识。《数据结构》是一门重要的专业基础课，是计算机理论和应用的核心基础课程。数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风等方面受到比较系统和严格的训练。在这次的课程设计中我选择的题目是敢死队问题。加强版的约瑟夫环问题（用户输入N,M值，从1至N开始顺序循环数数，每数到M输出该值，直到全部输出，最后输出的一个获胜），增加了保证1号安全这一条件限制。并且模拟各个开始位置，队员死亡的顺序，以及最后的获胜者。课程设计的目的的意义：加深对循环队列和数组的理解，以及对循环队列和数组的实际应用，加强自己的动手操作能力，增加对课程的兴趣，而不是枯燥的看课本。课程设计—《敢死队问题》描述有n个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。排长是不愿意去的，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。4/11第二章需求分析1.本程序任务是通过输入任意队伍人数n和报数上限m，输出使排长最后一个执行任务而开始记数的初始位置。首先输入队伍人数n，然后输入报数上限m(m=n)。比如从1号开始报数，当达到报数上限时，那名士兵出列执行任务，从下个人开始记数，再次循环，直到只剩一人，得到其在队伍中的位置，记下该位置视为排长位置，则1号即可视为最先报数的人，通过数学计算即可获得所求。2.功能模块和流程：1）功能模块该程序功能比较单一，主要是为解决敢死队问题而设计。通过输入队伍人数和报数上限即可获得开始报数的位置。2）程序流程（1）构造链表（2）数据输入（3）执行删除（4）输出要求数值（5）结束3.数据测试：当n=10，m=5,输出结果为：要求的位置是：9。第三章详细设计1.算法设计：本程序其实质是约瑟夫环问题。从排长位置即1号开始报数，共有n个人，达到报数上限m=5的战士出列，继续进行报数，直到剩余最后一人，记下该位置为k。若将该位置视为排长位置，则原先的1号位置即位所有的开始报数的位置z。则z=n-k+2。2.以单循环链表为存储结构，包含三个模块：（1）主程序模块（2）构造链表并初始化（3）删除结点5/113.结点类型和指针类型typedefstructnode{intdata;structnode*next;}LNode;/*定义结点类型*/LNode*p;4.每个模块的分析（1）主程序模块：main(){LNode*p;开始声明类型定义变量并初始化初始化单链表循环模块输入敢死队员总数剩下的队员数1?队员报数报数值=死亡数?队员出列输出结果否是否6/11intm,n,z,y;do{printf(Pleaseinputthepeoplenumber:\n);scanf(%d,&n);}while(n=0);do{printf(Pleaseinputtheexcursion:\n);scanf(%d,&m);}while(m=0);if(n==1)printf(thepositionis:1);else{p=CREAT(n);y=DELETE(p,m);z=n-y+2;if(z%n==0)/*排除特殊情况*/printf(thepositionis:\n%d\n,z);elseprintf(thepositionis:\n%d\n,(n-y+2)%n);}/*通过数学思想求得实验要求情况下的数值*/}（2）构造单循环链表并初始化模块：LNode*CREAT(intn)/*创建循环链表*/{LNode*s,*q,*t;inti;if(n!=0){t=q=(LNode*)malloc(sizeof(LNode));q-data=1;/*生成第一个结点并使其data值为1*/for(i=2;i=n;i++){s=(LNode*)malloc(sizeof(LNode));/*自动生成结点*/q-next=s;q-next-data=i;/*给第i个结点赋值i*/q=q-next;}q-next=t;}/*生成后续结点，并使其data值即为它所在链表（队伍）中的位置*/7/11returnt;}（3）删除结点模块：DELETE(LNode*t,intm)/*链表的删除*/{LNode*a;inti;while(t-next!=t){for(i=1;im-1;i++)/*查找要删除结点的前一结点*/t=t-next;a=t-next;t-next=a-next;free(a);/*释放结点*/t=t-next;}/*while循环依次删除被点到的士兵*/printf(\n);return(t-data);}第四章调试分析1.本程序运行后的结果应是如下提示：Exitpleaseinput'0'OrGoonPleaseinputthetataloftheteam:输入队伍总人数Pleaseinputtheexcursion:输入间隔人数结果显示：Thewantedpositionis输出选择的位置2.①在设计生成循环单链表时，考虑到程序结果需要士兵的位序，故将每个结点的data值设置为他们在队列中的位置，方便返回。②在删除单链表时，如果在报数时直接数到出列士兵则不方便链表的删除，可设置im-1找到出列士兵的前一位执行如下：for(i=1;im-1;i++)/*查找要删除结点的前一结点*/t=t-next;a=t-next;t-next=a-next;8/11free(a);/*释放结点*/t=t-next;③．在程序设计前，如果按原题所设，则需设队长为第一位，再分别测试从第几个开始才能符合条件。现在改变思想，通过数学思想：单循环链表本身是一个循环体，可先求出当从第一个出发的话，求出每隔m个出去一个最后是谁未出列，然后再设置它为链头，求出当他为队首时从第几个开始方能使其不出列。(n-y+2)%n即可实现这功能！第五章测试结果第六章源程序代码#includestdio.h//头文件#includemalloc.h#includestdlib.h#includeconio.htypedefstructnode//定义结构体链表{intdata;structnode*next;}LNode;/*定义结点类型*/LNode*CREAT(intn)/*创建循环链表*/{LNode*s,*q,*t;9/11inti;if(n!=0){t=q=(LNode*)malloc(sizeof(LNode));//生成第一个结点q-data=1;/*使其data值为1*/for(i=2;i=n;i++){s=(LNode*)malloc(sizeof(LNode));/*自动生成结点*/q-next=s;//把q的节点指向sq-next-data=i;/*给第i个结点赋值i*/q=q-next;//q指向的结点向后移一位}q-next=t;}/*生成后续结点，并使其data值即为它所在链表（队伍）中的位置*/returnt;//返回头结点，形成循环链表}intDELETE(LNode*t,intm)/*链表的删除*/{LNode*a;inti;while(t-next!=t)//while循环依次删除被点到的士兵{for(i=1;im-1;i++)/*查找要删除结点的前一结点*/t=t-next;a=t-next;t-next=a-next;//执行删除操作，删除数据free(a);/*释放结点*/t=t-next;}printf(\n);return(t-data);//返回t的值}main(){LNode*p;intm,n,z,y;printf(Exitpleaseinput'0'OrGoon...\nPleaseinputthetataloftheteam:);scanf(%d,&n);/*输入队员总数*/10/11while(n!=0)/*当队员总数等于0时退出*/{do{printf(Pleaseinputtheexcursion:);/*输入偏移数*/scanf(%d,&m);}while(m=0);if(m==1)printf(Thewantedpositionis1th.\n);else{p=CREAT(n);//创建循环链表py=DELETE(p,m);//选出去炸碉堡的人调用删除函数z=n-y+2;if(z%n==0)/*排除特殊情况*/printf(Thewantedpositionis%dth:\n,z);elseprintf(Thewantedpositionis%dth:\n,(n-y+2)%n);}/*通过数学思想求得实验要求情况下的数值*/printf(Exitpleaseinput'0'OrGoon...\nPleaseinputthetataloftheteam:);scanf(%d,&n);/*输入敢死队员总数*/}}第七章实验总结通过这次课程设计我又学到了很多东西,如程序的模块化设计思想，同时也加深了对数据结构这门课程的理解和学会了如何在实际中应用数据结构。在做程序之前，觉得敢死队这个问题，很难解决。在通过自己一次次的画图，推算结果时，明白了该程序的主要思路。本程序其实质是约瑟夫环问题，在明白程序的实质后开始，选择数据的存储结构类型，最开始想到的是循环队列，但是队列是在队头进行出队列操作，队尾入队列，不能进行任意删除元素的操作，没有多想就放弃了。最后选择了运用循环单链表来实现问题的解决。以前总是不清楚数据结构它有什么用途。通过这此课程设计，明白我们所学的虽然只是课本知识，但很多时候，我们可以利用所学的来解决生活中碰到的一些问题。同一个问题往往可以用不同的方法来解决。通过实际操作，学会分析问题，解决问题，开发了自己的逻辑思维能力。深刻体会到“没11/11有做不到的，只有想不到的”，“实践是检验真理的标准”。这次选取的题目比较简单，程序量也比较小，所以完成起来相对容易一些，通过一次一次的调试修正，感觉自己也进步了不少。第八章参考文献1.谭浩强《c程序设计》2.李业丽，郑良斌《数据机构（c）实验教程》