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

数据结构加里森的任务实验报告题目：加里森的任务需求分析程序所能实现的功能：功能有三（由功能键判定）。1）根据输入的（n，x，y），通过程序显示每轮派出去执行任务的战士的编号，直至只剩一人的情况，判断是否编号为1的加里森能否最终留下；2）根据输入的n值，找出从（n，1，1）到（n，n，n）满足条件的三元数对；3）退出程序。2，输入以及输出输入输出限制：n为大于等于2的正整数，x为大于等于1小于等于n的正整数，y为大于等于1的正整数（题干没有明确限制，默认小于等于n）；输入输出形式：对于功能一，输入符合要求的n，x，y，输出每轮派出的战士编号，yes/no表示加里森能否最后留下；对于功能二，输入符合要求的n，输出从（n，1，1）到（n，n，n）满足条件的三元数对；对于功能三，输出“程序已停止”。3，正确的输入输出范例一：正确的输入输出范例二：正确的输入输出范例三：错误的输入输出范例一：错误的输入输出范例二：概要设计本程序主要实现了两个功能。功能一思路，先判断输入的n，x，y是否合理，如合理，则将编号1-n存入一个循环链表，头指针移到编号x时开始计数，指针向后移动y-1次，输出当前指针所存节点的编号，即为该轮被淘汰的战士编号，然后再把该节点删除，指针后移一位重新计数，重复上述操作，直至只留下一个节点为止。若最后一个节点编号为1，则加里森留下；否则未留下。功能二思路，先判断输入的n是否合理，如合理，则构建二重for循环(i,j,1<=i<=n,1<=j<=n)列举从（n，1,1）到（n，n，n）所有可能的nxy组合并进行判断，一旦符合则输出该组合。直至循环完毕。判断方法有两种，第一种类似功能一，第二种利用约瑟夫环公式法。数据结构类型的定义：typedefstructLink{intnum;structLink*next;}link;主程序流程：intmain(){ intchoice,t; intn,x,y; printf("功能选择:\n"); printf("1，自拟数据验证程序正确性（n，x，y已知，验证1号能否留下）\n"); printf("2，输出符合条件的（n，x，y）组合（n已知）\n"); printf("0，退出程序\n"); printf("请选择功能:"); scanf("%d",&choice); if(choice==1){ printf("请输入n，x，y："); scanf("%d%d%d",&n,&x,&y); t=fanwei1(n,x,y); }if(choice==2){printf("请输入n："); scanf("%d",&n); t=fanwei2(n); } if(choice==1&&t==1) judge(n,x,y); if(choice==2&&t==1) { inti,j; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { if(Cleanjudge(n,i,j)==1)//也可调用Rejudge printf("(%d,%d,%d)",n,i,j); } printf("\n"); } }//可调用函数judge，Cleanjudge,Rejudge if(choice==0) printf("程序已停止");}程序模块之间的调用关系:Main函数先调用fanwei1函数或fanwei2函数判断输入是否合法，功能一接着调用judge函数，功能二接着调用Cleanjudge函数或Rejudge函数。（judge函数和Cleanjudge函数中都调用了creatLinkList函数）详细设计1）//创建循环链表的函数voidcreatLinkList(link*p,intn){link*temp=p;link*head=p;//记录起点for(inti=1;i<=n;i++){link*a=(link*)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*)malloc(sizeof(link));creatLinkList(p,n);link*pre=p;p=p->next;//pre为p的上一位previouwhile(p->num!=x){pre=p;p=p->next;}//寻找起点intm=1;//当前数到的数，起点开始叫号，此时m为1while(n>1)//最后一位时必被淘汰，所以不用数{if(m==y){m=0;pre->next=p->next;//上一位跳过了p现所在的节点n--;//人数少一个cout<<p->num<<"->";//输出被淘汰的人}m++;pre=p;p=p->next;}cout<<p->num<<endl;//输出最后淘汰的人if(p->num==1)cout<<"Yes"<<endl;elsecout<<"No"<<endl;//输出最后结果}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=1;while(n>1)//最后一位时必被淘汰，所以不用数{if(m==y){m=0;pre->next=p->next;n--;}m++;pre=p;p=p->next;}if(p->num==1)return1;elsereturn0;}4）功能与cleanjudge相同，思路不同intRejudge(intn,intx,inty){//recursion递归的方式判断是否可以if(n==1)return1;//最后剩下一个必为1intk=y%n;x=(x-1+k)%n;//计算谁被淘汰if(x==1)return0;//如果是1被淘汰则返回零if(x==0)x=1;//如果是0被淘汰则即是n被淘汰，则此时下一个开始数的人是1//例如1245中，4被淘汰了，原本是第三个位置，淘汰后成了125，下个叫号的人是5，位置仍是第三，所以x不变returnRejudge(n-1,x,y);//人数减一，后边人的序号变化不影响1号的位置，此题只求1是否被淘汰}5）intfanwei1(intn,intx,inty)//选项1，判断n，x，y的范围{ if(n>=2) { if(x<=n&&x>=1) { if(y>=1) return1; else { printf("数据不正常，重新输入"); return0; } } else { printf("数据不正常,重新输入"); return0; } } else { printf("数据不正常,重新输入"); return0; }}6）intfanwei2(intn)//选项2，判断n的范围{ if(n>=2) return1; else { printf("数据不正常,重新输入"); return0; }}函数调用关系图MMainFanwei1/fanwei2Judge/CleanjudgecreatLinkList调试分析报告时空分析creatLinkList函数o(n)judge函数o(n)Cleanjudge函数o(n)Rejudge函数o(1)Mai