數(shù)據(jù)結(jié)構(gòu)課程常見問題 -單元28 敢死隊(duì)問題1敢死隊(duì)問題求解解析：?jiǎn)栴}描述有M個(gè)敢死隊(duì)員要炸掉敵人的一碉堡，誰都不想去，排長(zhǎng)決定用輪回?cái)?shù)數(shù)的辦法來決定哪個(gè)戰(zhàn)士去執(zhí)行任務(wù)。如果前一個(gè)戰(zhàn)士沒完成任務(wù)，則要再派一個(gè)戰(zhàn)士上去?，F(xiàn)給每個(gè)戰(zhàn)士編一個(gè)號(hào)，大家圍坐成一圈，隨便從某一個(gè)戰(zhàn)士開始計(jì)數(shù)，當(dāng)數(shù)到5時(shí)，對(duì)應(yīng)的戰(zhàn)士就去執(zhí)行任務(wù)，且此戰(zhàn)士不再參加下一輪計(jì)數(shù)。如果此戰(zhàn)士沒完成任務(wù)，再從下一個(gè)戰(zhàn)士開始數(shù)數(shù)，被數(shù)到第5時(shí)，此戰(zhàn)士接著去執(zhí)行任務(wù)。以此類推，直到任務(wù)完成為止。排長(zhǎng)是不愿意去的，假設(shè)排長(zhǎng)為1號(hào)，請(qǐng)你設(shè)計(jì)一程序，求出從第幾號(hào)戰(zhàn)士開始計(jì)數(shù)才能讓排長(zhǎng)最后一個(gè)留下來而不去執(zhí)行任務(wù)。要求：至少采用兩種不同的數(shù)據(jù)結(jié)構(gòu)的方法實(shí)現(xiàn)。一、單循環(huán)鏈表數(shù)據(jù)結(jié)構(gòu)(一) 需求分析 1.本程序任務(wù)是通過輸入任意隊(duì)伍人數(shù)n和報(bào)數(shù)上限m，輸出使排長(zhǎng)最后一個(gè)執(zhí)行任務(wù)而開始記數(shù)的初始位置。首先輸入隊(duì)伍人數(shù)n，然后輸入報(bào)數(shù)上限m(m<=n),從1號(hào)開始報(bào)數(shù)，當(dāng)達(dá)到報(bào)數(shù)上限時(shí)，那名士兵出列執(zhí)行任務(wù)，從下個(gè)人開始記數(shù)，再次循環(huán)，直到只剩一人，得到其在隊(duì)伍中的位置，記下該位置視為排長(zhǎng)位置，則1號(hào)即可視為最先報(bào)數(shù)的人，通過數(shù)學(xué)計(jì)算即可獲得所求。2.功能模塊和流程： 1）功能模塊該程序功能比較單一，主要是為解決敢死隊(duì)問題而設(shè)計(jì)。通過輸入隊(duì)伍人數(shù)和報(bào)數(shù)上限即可獲得開始報(bào)數(shù)的位置。2）程序流程 （1）構(gòu)造鏈表（2）數(shù)據(jù)輸入（3）執(zhí)行刪除（4）輸出要求數(shù)值（5）結(jié)束3.數(shù)據(jù)測(cè)試：當(dāng) n=10，m=5, 輸出結(jié)果為：要求的位置是：9。(二) 詳細(xì)設(shè)計(jì)1.算法設(shè)計(jì)：本程序其實(shí)質(zhì)是約瑟夫環(huán)問題。從排長(zhǎng)位置即1號(hào)開始報(bào)數(shù)，共有n個(gè)人，達(dá)到報(bào)數(shù)上限m=5的戰(zhàn)士出列，繼續(xù)進(jìn)行報(bào)數(shù)，直到剩余最后一人，記下該位置為k。若將該位置視為排長(zhǎng)位置，則原先的1號(hào)位置即位所有的開始報(bào)數(shù)的位置z。則z=n-k+2。2.以單循環(huán)鏈表為存儲(chǔ)結(jié)構(gòu)，包含三個(gè)模塊： （1）主程序模塊 （2）構(gòu)造鏈表并初始化（3）刪除結(jié)點(diǎn) 3.結(jié)點(diǎn)類型和指針類型typedef struct node int data; struct node *next;LNode;/* 定義結(jié)點(diǎn)類型 */LNode *p;4.每個(gè)模塊的分析（1）主程序模塊：main() LNode *p; int m,n,z,y; do printf(" Please input the people number:n"); scanf ("%d",&n); while (n<=0); do printf(" Please input the excursion:n"); scanf("%d",&m); while (m<=0); if (n=1) printf("the position is: 1"); else p=CREAT(n); y=DELETE(p,m); z=n-y+2; if(z%n=0) /* 排除特殊情況 */ printf ("the position is:n%dn",z); else printf("the position is:n%dn",(n-y+2)%n); /* 通過數(shù)學(xué)思想求得實(shí)驗(yàn)要求情況下的數(shù)值 */ （2）構(gòu)造單循環(huán)鏈表并初始化模塊：LNode* CREAT(int n) /* 創(chuàng)建循環(huán)鏈表 */ LNode *s,*q,*t; int i; if(n!=0) t=q=(LNode *)malloc(sizeof(LNode); q->data=1;/* 生成第一個(gè)結(jié)點(diǎn)并使其data值為1 */ for(i=2;i<=n;i+) s=(LNode *)malloc(sizeof(LNode);/*自動(dòng)生成結(jié)點(diǎn)*/ q->next=s; q->next->data=i;/*給第i個(gè)結(jié)點(diǎn)賦值i*/ q=q->next; q->next=t; /* 生成后續(xù)結(jié)點(diǎn)，并使其data值即為它所在鏈表（隊(duì)伍）中的位置 */ return t;（3）刪除結(jié)點(diǎn)模塊：DELETE (LNode* t,int m)/* 鏈表的刪除 */ LNode *a;int i; while (t->next!=t) for (i=1;i<m-1;i+)/*查找要?jiǎng)h除結(jié)點(diǎn)的前一結(jié)點(diǎn)*/ t=t->next; a=t->next; t->next=a->next; free(a);/*釋放結(jié)點(diǎn)*/ t=t->next; /* while循環(huán)依次刪除被點(diǎn)到的士兵 */ printf("n"); return (t->data);(三) 調(diào)試分析：1.本程序運(yùn)行后的結(jié)果應(yīng)是如下提示：Exit please input '0' Or Go on Please input the tatal of the team:輸入隊(duì)伍總?cè)藬?shù)Please input the excursion:輸入間隔人數(shù)結(jié)果顯示：The wanted position is 選擇的位置2.在程序調(diào)試運(yùn)行的過程中產(chǎn)生了各種各樣的問題，有的是多了空格，有的是拼寫錯(cuò)誤，還有的是少了括號(hào)，類似的問題有很多。解決的辦法是一遍遍嘗試，不斷逐行逐句進(jìn)行修改。例如程序調(diào)試過程中遇到警告：發(fā)現(xiàn)錯(cuò)誤為 if(m=1)后改正為 if(m=1)程序運(yùn)行正確了，運(yùn)行如下：顯示輸出如圖：