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