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

数据结构加里森的任务实验报告题目：加里森的任务一，需求分析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表示加里森能否最后留下；对于功能二，输入符合要求的n,输出从（n,bD到（n,n,n）满足条件的三元数对；对于功能三，输出“程序已停止”。3,正确的输入输出范例一:qS3CAU""VeWSDsktopXJR侬栩内曲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请按任意健继续正确的输入输出范例二:正确的输入输出范例三:错误的输入输出范例一:错误的输入输出范例二:VenovoBMkt叩JR3BW3M一次实验券,e×e才能选择:1,生燧堪验i程序正确性(n.X,y¾¾D.睑证1号能否留下)2.皤毛加咨条侔曲(n,X,y)组合(n)0.鼬粒序中魅璃：2请输入n；X做豫求正常,或新输入ocessexitedafter7.852secondswithreturnvalue0点按任意键继续二，概要设计本程序主要实现了两个功能。1) 功能一思路，先判断输入的n,X,y是否合理，如合理，则将编号1-n存入一个循环链表，头指针移到编号X时开始计数，指针向后移动y-1次，输出当前指针所存节点的编号，即为该轮被淘汰的战士编号，然后再把该节点删除，指针后移一位重新计数，重复上述操作，直至只留下一个节点为止。若最后一个节点编号为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）;printfl,自拟数据验证程序正确性（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)(inti,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) 创建循环链表的函数voidCreatLinkList(link*p,intn)link*temp=p;link*head=p;/记录起点for(inti=l;i<=n;i+÷)link*a=(1ink*)malloc(sizeof(link);a->num=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的上位previouwhile(p->num!=x)pre=p;p=p->next;寻找起点int=l;当前数到的数，起点开始叫号，此时m为1while(nl)最后一位时必被淘汰，所以不用数if(m=y)m=0;pre->next=p->next;上一位跳过了P现所在的节点n一;人数少一个CoUt<Xp->num<<->；输出被淘汰的人)m+;pre=p;p=p->next;)cout<<p->num<<endl;输出最后淘汰的人if(p->num=l)cout<<z,Yeszz<<endl;elseCOUt<XNo<Xendl;/输出最后结果)3) intCleanjudge(intn,intx,inty)这是无输出的判断，返回1为是，0为否(link*p=(link*)malloc(sizeof(link);CreatLinkList(p,n);link*pre=p;p=p->next;while(p->num!=x)pre=p;p=p->next;intm=l;while(nl)最后一位时必被淘汰，所以不用数!if(m=y)m=0;pre->next=p->next;n;)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不变returnRejudge(n-l,x,y);/人数减一,后边人的序号变化不影响1号的位置，此题只求1是否被淘汰5) intfanweil(intn,intx,inty)选项1,判断n,x,y的范围if(n>=2)if(x<=n&&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,时空分析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->7->13->2->10->18->8->20->12->6->5->11->17->3->16Processexitedafter49.61secondswithreturnvalue0请按任意健继续.当用户输入2时，要求输入符合条件的n,输完按回车即可83 SUMVenov0De5kt°p»®mM一次实囊ffl<W务e×uX当用户输入。时BCUser1lenovoDesktopSQBaM-ZX5UB三4M½S.exe-X功能选择曾以欲堪验程序正确性(n.X.y已和,验证1号能否留下)R，瘠£餐皆繇的(n,X,y)组合(nBfl)0.1R1+*三修施功露：0障序由¥工*rocessexitedafter4.61secondswithreturnvalue0官技任竟梃继续.六，测试结果S3CUserslenovoDe5ktopJHB8IS-J).；_.口，尊敬敬损奥可程序正确性(n,X,y已知，验证1号能否曾下)2,鲁罐古条触(n,X,y)组合(n己知)O三请输入n，x»y三2010514->19->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,13,2)20,15,5)(20,15,15)20,16,9)(20,16,17)20,17,18)20,19,7)(20,19,10),20,20,20)ocssexitedafter10.27secondswithreturnvalue0清按任意破继续