数据结构加里森的任务实验报告.docx

《数据结构加里森的任务实验报告.docx》由会员分享，可在线阅读，更多相关《数据结构加里森的任务实验报告.docx（17页珍藏版）》请在优知文库上搜索。

1、数据结构加里森的任务实验报告题目：加里森的任务一，需求分析1, 程序所能实现的功能：功能有三（由功能键判定）。1）根据输入的（n,X,y）,通过程序显示每轮派出去执行任务的战士的编号，直至只剩一人的情况，判断是否编号为1的加里森能否最终留下；2）根据输入的n值，找出从（n,1,1）到（n,n,n）满足条件的三元数对；3）退出程序。2,输入以及输出1） 输入输出限制：n为大于等于2的正整数，X为大于等于1小于等于11的正整数，y为大于等于1的正整数（题干没有明确限制，默认小于等于n）；2） 输入输出形式:对于功能一，输入符合要求的n,X,y,输出每轮派出的战士编号，yes/no表示加里森能否最后

2、留下；对于功能二，输入符合要求的n,输出从（n,bD到（n,n,n）满足条件的三元数对；对于功能三，输出“程序已停止”。3,正确的输入输出范例一:qS3CAUVeWSDsktopXJR侬栩内曲M里拗务MR1 .前爆振骏年程序正确性（n,X,汜知，验证1号能否留下）2 .tW三ffi（n,X,y）组合（n已知）至窗却能：1谓输入n,X,y2010514-19-4-9-15-l-7-13-2-10-18-8-20-12-6-5-ll-17-3-16Processexitedafter49.61secondswithreturnvalue0请按任意健继续正确的输入输出范例二:正确的输入输出范例三:错

3、误的输入输出范例一:错误的输入输出范例二:VenovoBMkt叩JR3BW3M一次实验券,ee才能选择:1,生燧堪验i程序正确性(n.X,yD.睑证1号能否留下)2.皤毛加咨条侔曲(n,X,y)组合(n)0.鼬粒序中魅璃：2请输入n；X做豫求正常,或新输入ocessexitedafter7.852secondswithreturnvalue0点按任意键继续二，概要设计本程序主要实现了两个功能。1) 功能一思路，先判断输入的n,X,y是否合理，如合理，则将编号1-n存入一个循环链表，头指针移到编号X时开始计数，指针向后移动y-1次，输出当前指针所存节点的编号，即为该轮被淘汰的战士编号，然后再把该

4、节点删除，指针后移一位重新计数，重复上述操作，直至只留下一个节点为止。若最后一个节点编号为1,则加里森留下；否则未留下。2) 功能二思路，先判断输入的n是否合理，如合理，则构建二重for循环(i,j,l=i=n,l=j=n)列举从(n,1,1)到(n,n,n)所有可能的nxy组合并进行判断，一旦符合则输出该组合。直至循环完毕。判断方法有两种，第一种类似功能一，第二种利用约瑟夫环公式法。数据结构类型的定义：typedefstructLinkintnum;structLink*next;link;主程序流程：intmainOintchoice,t;intn,x,y;Printf（功能选择：n）;p

5、rintfl,自拟数据验证程序正确性（n,x,y已知，验证1号能否留下）n）；printf（zz2,输出符合条件的（n,x,y）组合（n已知）n）；printf（zz0,退出程序n）;Printf（请选择功能：）；scanf（%d,&choice）;if（choice=l）:Printf（请输入n,x,y：）；scanf（/,%d%d%d，&n,&x,&y）;t=fanweil(n,x,y);if(choice=2):Printf(请输入n：)；scanf(d，&n);t=fanwei2(n);)if(choice=l&t=l)judge(n,x,y);if(choice=2&t=l)(int

6、i,j;for(i=l;i=n;i+)for(j=l;j=n;j+)if(Cleanjudge(n,i,j)=l)/也可调用Rejudgeprintf(%d,%d,%d)，n,i,j);)可调用函数judge,Cleanjudge,Rejudgeif(choice=0)Printf(程序已停止)；程序模块之间的调用关系：Main函数先调用fanweil函数或fanwei2函数判断输入是否合法，功能一接着调用judge函数，功能二接着调用Cleanjudge函数或Rejudge函数。(judge函数和CIeanjUdge函数中都调用了CreatLinkList函数)三，详细设计1) 创建循环链表

7、的函数voidCreatLinkList(link*p,intn)link*temp=p;link*head=p;/记录起点for(inti=l;inum=i;a-next=NULL;temp-next=a;temp=temp-next;if(i=n)a-next=head-next;尾接头，使得循环)2) voidjudge(intn,intx,inty)这个是带输出淘汰过程的判断(/n：人数，X：起点，y：数字link*p=(link*)malIoc(sizeof(link);CreatLinkList(p,n);link*pre=p;p=p-next;/pre为P的上位previouwh

8、ile(p-num!=x)pre=p;p=p-next;寻找起点int=l;当前数到的数，起点开始叫号，此时m为1while(nl)最后一位时必被淘汰，所以不用数if(m=y)m=0;pre-next=p-next;上一位跳过了P现所在的节点n一;人数少一个CoUtnum；输出被淘汰的人)m+;pre=p;p=p-next;)coutnumnum=l)coutz,Yeszzendl;elseCOUtXNonext;while(p-num!=x)pre=p;p=p-next;intm=l;while(nl)最后一位时必被淘汰，所以不用数!if(m=y)m=0;pre-next=p-next;n;

9、)m+;pre=p;p=p-next;)if(p-num=l)return1;elsereturn0;)4)功能与CleanjUdge相同，思路不同intRejudge(intn,intx,inty)recursion递归的方式判断是否可以if(n=l)return1;最后剩下一个必为1intk=y%n;x=(-l+k)%n;计算谁被淘汰if(x=l)return0;如果是1被淘汰则返回零if(x=0)x=l;如果是0被淘汰则即是n被淘汰，则此时下一个开始数的人是1例如1245中，4被淘汰了，原本是第三个位置，淘汰后成了125,下个叫号的人是5,位置仍是第三，所以X不变returnRejudg

10、e(n-l,x,y);/人数减一,后边人的序号变化不影响1号的位置，此题只求1是否被淘汰5) intfanweil(intn,intx,inty)选项1,判断n,x,y的范围if(n=2)if(x=l)if(y=l)return1;Printf(数据不正常，重新输入)；return0;)else!Printf(数据不正常,重新输入)；return0;)else(Printf(数据不正常,重新输入)；return0;)6) intfanwei2(intn)选项2,判断n的范围(if(n=2)return1;Printf(数据不正常,重新输入);return0;函数调用关系图四，调试分析报告1,时

11、空分析CreatLinkList函数o(n)judge函数o(n)Cleanjudge函数o(n)RejUdge函数o(l)Main函数o(n2)刚开始拿到题目没有理解题意，感觉完全没有条件，后来经过分析讨论，发现11,X,y有一定限制，而且自拟程序的功能具有多样性，程序编写过程中有些因粗心产生的小问题，但都及时解决了。五，用户使用说明打开程序会出现以下界面用户根据需要输入1,2,O即可当用户输入1时，要求输入符合条件的n,X,y,输入完按回车即可11SlCU5erse11ovoDesktopS3BWM-口，脚敢损奥可程序正确性（n,X,y已知，验证1号能否曾下）114-19-4-9-15-l

12、-7-13-2-10-18-8-20-12-6-5-11-17-3-16Processexitedafter49.61secondswithreturnvalue0请按任意健继续.当用户输入2时，要求输入符合条件的n,输完按回车即可83 SUMVenov0De5ktpmM一次实囊ffl19-4-9-15-l-7-13-2-10-18-8-20-12-6-5-ll-17-3-163Tocessexitedafter49.61secondswithrturnvalue0清按任意健旌续.能选择.1.笛嫁塔验评程序正确性(n,X.yO.验证1号能否留下)2,喻田餐苔条侔曲(n,X,y)组合(n已知)傅田程序金裤懒：2活输入m20(20,1,8)(20,1,16)(20,2,1)(20,2,3)(20,2,6),5,4)(20,5,13),7,11)20,11,12)(20,11,14)(20,11,19)：20,