數(shù)據(jù)結(jié)構(gòu)加里森的任務(wù)實(shí)驗(yàn)報(bào)告

數(shù)據(jù)結(jié)構(gòu)加里森的任務(wù)實(shí)驗(yàn)報(bào)告題目：加里森的任務(wù)需求分析程序所能實(shí)現(xiàn)的功能：功能有三（由功能鍵判定）。1）根據(jù)輸入的（n，x，y），通過程序顯示每輪派出去執(zhí)行任務(wù)的戰(zhàn)士的編號(hào)，直至只剩一人的情況，判斷是否編號(hào)為1的加里森能否最終留下；2）根據(jù)輸入的n值，找出從（n，1，1）到（n，n，n）滿足條件的三元數(shù)對(duì)；3）退出程序。2，輸入以及輸出輸入輸出限制：n為大于等于2的正整數(shù)，x為大于等于1小于等于n的正整數(shù)，y為大于等于1的正整數(shù)（題干沒有明確限制，默認(rèn)小于等于n）；輸入輸出形式：對(duì)于功能一，輸入符合要求的n，x，y，輸出每輪派出的戰(zhàn)士編號(hào)，yes/no表示加里森能否最后留下；對(duì)于功能二，輸入符合要求的n，輸出從（n，1，1）到（n，n，n）滿足條件的三元數(shù)對(duì)；對(duì)于功能三，輸出“程序已停止”。3，正確的輸入輸出范例一：正確的輸入輸出范例二：正確的輸入輸出范例三：錯(cuò)誤的輸入輸出范例一：錯(cuò)誤的輸入輸出范例二：概要設(shè)計(jì)本程序主要實(shí)現(xiàn)了兩個(gè)功能。功能一思路，先判斷輸入的n，x，y是否合理，如合理，則將編號(hào)1-n存入一個(gè)循環(huán)鏈表，頭指針移到編號(hào)x時(shí)開始計(jì)數(shù)，指針向后移動(dòng)y-1次，輸出當(dāng)前指針?biāo)婀?jié)點(diǎn)的編號(hào)，即為該輪被淘汰的戰(zhàn)士編號(hào)，然后再把該節(jié)點(diǎn)刪除，指針后移一位重新計(jì)數(shù)，重復(fù)上述操作，直至只留下一個(gè)節(jié)點(diǎn)為止。若最后一個(gè)節(jié)點(diǎn)編號(hào)為1，則加里森留下；否則未留下。功能二思路，先判斷輸入的n是否合理，如合理，則構(gòu)建二重for循環(huán)(i,j,1<=i<=n,1<=j<=n)列舉從（n，1,1）到（n，n，n）所有可能的nxy組合并進(jìn)行判斷，一旦符合則輸出該組合。直至循環(huán)完畢。判斷方法有兩種，第一種類似功能一，第二種利用約瑟夫環(huán)公式法。數(shù)據(jù)結(jié)構(gòu)類型的定義：typedefstructLink{intnum;structLink*next;}link;主程序流程：intmain(){ intchoice,t; intn,x,y; printf("功能選擇:\n"); printf("1，自擬數(shù)據(jù)驗(yàn)證程序正確性（n，x，y已知，驗(yàn)證1號(hào)能否留下）\n"); printf("2，輸出符合條件的（n，x，y）組合（n已知）\n"); printf("0，退出程序\n"); printf("請(qǐng)選擇功能:"); scanf("%d",&choice); if(choice==1){ printf("請(qǐng)輸入n，x，y："); scanf("%d%d%d",&n,&x,&y); t=fanwei1(n,x,y); }if(choice==2){printf("請(qǐng)輸入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)//也可調(diào)用Rejudge printf("(%d,%d,%d)",n,i,j); } printf("\n"); } }//可調(diào)用函數(shù)judge，Cleanjudge,Rejudge if(choice==0) printf("程序已停止");}程序模塊之間的調(diào)用關(guān)系:Main函數(shù)先調(diào)用fanwei1函數(shù)或fanwei2函數(shù)判斷輸入是否合法，功能一接著調(diào)用judge函數(shù)，功能二接著調(diào)用Cleanjudge函數(shù)或Rejudge函數(shù)。（judge函數(shù)和Cleanjudge函數(shù)中都調(diào)用了creatLinkList函數(shù)）詳細(xì)設(shè)計(jì)1）//創(chuàng)建循環(huán)鏈表的函數(shù)voidcreatLinkList(link*p,intn){link*temp=p;link*head=p;//記錄起點(diǎn)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;//尾接頭，使得循環(huán)}}2）voidjudge(intn,intx,inty)//這個(gè)是帶輸出淘汰過程的判斷{//n：人數(shù)，x：起點(diǎn)，y：數(shù)字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;}//尋找起點(diǎn)intm=1;//當(dāng)前數(shù)到的數(shù)，起點(diǎn)開始叫號(hào)，此時(shí)m為1while(n>1)//最后一位時(shí)必被淘汰，所以不用數(shù){if(m==y){m=0;pre->next=p->next;//上一位跳過了p現(xiàn)所在的節(jié)點(diǎn)n--;//人數(shù)少一個(gè)cout<<p->num<<"->";//輸出被淘汰的人}m++;pre=p;p=p->next;}cout<<p->num<<endl;//輸出最后淘汰的人if(p->num==1)cout<<"Yes"<<endl;elsecout<<"No"<<endl;//輸出最后結(jié)果}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)//最后一位時(shí)必被淘汰，所以不用數(shù){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;//最后剩下一個(gè)必為1intk=y%n;x=(x-1+k)%n;//計(jì)算誰(shuí)被淘汰if(x==1)return0;//如果是1被淘汰則返回零if(x==0)x=1;//如果是0被淘汰則即是n被淘汰，則此時(shí)下一個(gè)開始數(shù)的人是1//例如1245中，4被淘汰了，原本是第三個(gè)位置，淘汰后成了125，下個(gè)叫號(hào)的人是5，位置仍是第三，所以x不變r(jià)eturnRejudge(n-1,x,y);//人數(shù)減一，后邊人的序號(hào)變化不影響1號(hào)的位置，此題只求1是否被淘汰}5）intfanwei1(intn,intx,inty)//選項(xiàng)1，判斷n，x，y的范圍{ if(n>=2) { if(x<=n&&x>=1) { if(y>=1) return1; else { printf("數(shù)據(jù)不正常，重新輸入"); return0; } } else { printf("數(shù)據(jù)不正常,重新輸入"); return0; } } else { printf("數(shù)據(jù)不正常,重新輸入"); return0; }}6）intfanwei2(intn)//選項(xiàng)2，判斷n的范圍{ if(n>=2) return1; else { printf("數(shù)據(jù)不正常,重新輸入"); return0; }}函數(shù)調(diào)用關(guān)系圖MMainFanwei1/fanwei2Judge/CleanjudgecreatLinkList調(diào)試分析報(bào)告時(shí)空分析creatLinkList函數(shù)o(n)judge函數(shù)o(n)Cleanjudge函數(shù)o(n)Rejudge函數(shù)o(1)Mai