數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--- 約瑟夫環(huán)問(wèn)題

1、<p>　　《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)檔案</p><p>　　題 目： 約瑟夫環(huán)問(wèn)題 </p><p>　　學(xué) 院： 信息學(xué)院 </p><p>　　專 業(yè)： 網(wǎng)絡(luò)工程 </p><p>　　姓 名：

2、 </p><p>　　學(xué) 號(hào)： </p><p>　　班 級(jí) </p><p>　　指導(dǎo)教師： </p><p>　　職 稱： 講 師

3、 </p><p>　　完成日期： 2012年12月 </p><p><b>　　摘 要</b></p><p>　　約瑟夫環(huán)問(wèn)題是由古羅馬著名的史學(xué)家Josephus提出的問(wèn)題演變而來(lái)，所以通常稱為Josephus問(wèn)題。改進(jìn)約瑟夫環(huán)問(wèn)題的描述是：編號(hào)為1，2，…，n的n個(gè)人按順時(shí)針?lè)较驀蝗?

4、每人有一個(gè)密碼K（整數(shù)），留作其出圈后應(yīng)報(bào)到K后出圈。報(bào)數(shù)方法采用順時(shí)針報(bào)數(shù)和逆時(shí)針報(bào)數(shù)交替進(jìn)行，初始密碼可任意確定。求最后剩下的人的編號(hào)。這個(gè)就是約瑟夫環(huán)問(wèn)題的實(shí)際場(chǎng)景。約瑟夫環(huán)問(wèn)題如果采用單循環(huán)鏈表則能很好的解決。循環(huán)鏈表的數(shù)據(jù)結(jié)構(gòu)，就是將一個(gè)鏈表的尾元素指針指向隊(duì)首元素。 p->link=head解決問(wèn)題的核心步驟是：先建立一個(gè)具有n個(gè)鏈結(jié)點(diǎn)，無(wú)頭結(jié)點(diǎn)的循環(huán)鏈表，然后確定第一個(gè)報(bào)數(shù)人的位置，并不斷地從鏈表中刪除鏈結(jié)點(diǎn)，直到鏈

5、表為空。</p><p>　　【關(guān)鍵詞】約瑟夫環(huán)；單循環(huán)鏈表；數(shù)據(jù)結(jié)構(gòu)；刪除結(jié)點(diǎn)</p><p><b>　　Abstract</b></p><p>　　Josephus ring problem is evolved by the question that raised by Josephus,the famous historican

6、of ancient Rome.SO it always be called Josephus Problem.The description of improving Josephus problem is :people was numbered 1,2,3,...,n sitted as a clockwise direction around circle,each with a password of K(integer),r

7、eserved for the ring should be reported K out of the ring .The report adapted the method that changed alternately with the clockwise and anticlockwise, the initial password can be deter</p><p>　　[Keywords] J

8、oseph ring; circular linked list; data structure; deleting node</p><p><b>　　目 錄</b></p><p><b>　　前言1</b></p><p>　　第一章 問(wèn)題分析2</p><p>　　第二章 邏輯

9、設(shè)計(jì)4</p><p>　　2.1 循環(huán)鏈表抽象數(shù)據(jù)類型定義4</p><p>　　2.2本程序包含的模塊設(shè)計(jì)4</p><p>　　第三章 詳細(xì)設(shè)計(jì)6</p><p><b>　　3.1 主函數(shù)6</b></p><p>　　3.2 鏈表的創(chuàng)建7</p><p&

10、gt;　　3.3 出隊(duì)處理9</p><p>　　3.4 約瑟夫環(huán)說(shuō)明模塊10</p><p>　　3.5菜單模塊10</p><p>　　第四章 程序調(diào)試與測(cè)試11</p><p><b>　　第五章 結(jié)論14</b></p><p><b>　　參考文獻(xiàn)15</b&

11、gt;</p><p><b>　　致謝16</b></p><p><b>　　附錄17</b></p><p><b>　　前 言</b></p><p>　　數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作的學(xué)科。該課程設(shè)計(jì)的目

12、的是通過(guò)課程設(shè)計(jì)的綜合訓(xùn)練，以培養(yǎng)分析和編程等實(shí)際動(dòng)手能力，是系統(tǒng)掌握數(shù)據(jù)結(jié)構(gòu)這門課程的主要內(nèi)容。</p><p>　　本次課程設(shè)計(jì)的內(nèi)容是用單循環(huán)鏈表模擬約瑟夫環(huán)問(wèn)題，循環(huán)鏈表是一種首尾相接的鏈表，其特點(diǎn)是無(wú)須增加存儲(chǔ)容量，僅對(duì)表的鏈接方式稍作改變，使表處理更加靈活。約瑟夫環(huán)問(wèn)題就是用單循環(huán)鏈表處理的一個(gè)實(shí)際應(yīng)用。通過(guò)這個(gè)設(shè)計(jì)實(shí)例，了解單鏈表和單循環(huán)鏈表的相同與不同之處，進(jìn)一步加深對(duì)鏈表結(jié)構(gòu)類型及鏈表操作的理解

13、。</p><p>　　通過(guò)該課程設(shè)計(jì)，能運(yùn)用所學(xué)知識(shí)，上機(jī)解決一些實(shí)際問(wèn)題，了解并初步掌握設(shè)計(jì)，實(shí)現(xiàn)較大程序的完整過(guò)程，包括系統(tǒng)分析、編碼設(shè)計(jì)、系統(tǒng)集成、以及調(diào)試分析，熟練掌握數(shù)據(jù)結(jié)構(gòu)的選擇、設(shè)計(jì)、實(shí)現(xiàn)以及操作方法，為進(jìn)一步的應(yīng)用開(kāi)發(fā)打好基礎(chǔ)。</p><p><b>　　第一章 問(wèn)題分析</b></p><p>　　約瑟夫環(huán)問(wèn)題描述的是：設(shè)

14、編號(hào)為1，2，…，n的n（n>0）個(gè)人按順時(shí)針?lè)较驀蝗?，每個(gè)人持有一個(gè)正整數(shù)密碼。開(kāi)始時(shí)選擇一個(gè)正整數(shù)作為報(bào)數(shù)上限m，從第一個(gè)人開(kāi)始順時(shí)針?lè)较蜃?起按順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)，報(bào)m的人出圈，將他的密碼作為新的m值，從他的順時(shí)針?lè)较蛏系南乱粋€(gè)人起重新從1報(bào)數(shù)。如此下去，直到所有人都出圈為止。令n最大值為100。要求設(shè)計(jì)一個(gè)程序模擬此過(guò)程，求出出圈的編號(hào)序列。具體描述如圖1和圖2所示：</p><p>　

15、　圖1 約瑟夫環(huán)問(wèn)題圖解</p><p>　　圖2 約瑟夫環(huán)原理演示圖</p><p><b>　　第二章 邏輯設(shè)計(jì)</b></p><p>　　2.1 循環(huán)鏈表抽象數(shù)據(jù)類型定義</p><p>　　typedef struct LNode//定義單循環(huán)鏈表中結(jié)點(diǎn)的結(jié)構(gòu) </p><p><

16、;b>　　{</b></p><p>　　int num;//編號(hào) </p><p>　　int pwd;//password</p><p>　　struct LNode *next;//指向下一結(jié)點(diǎn)的指針</p><p><b>　　}LNode;</b></p><p>　

17、　2.2本程序包含的模塊設(shè)計(jì)</p><p><b>　?。?）構(gòu)造結(jié)點(diǎn)模塊</b></p><p>　　LNode *createNode(int m_num,int m_pwd)</p><p><b>　　{</b></p><p><b>　　LNode *p;</b>

18、</p><p>　　p=(LNode *)malloc(sizeof(LNode));//生成一個(gè)結(jié)點(diǎn) </p><p>　　p->num=m_num;//把實(shí)參賦給相應(yīng)的數(shù)據(jù)域</p><p>　　p->pwd=m_pwd;</p><p>　　p->next=NULL;//指針域?yàn)榭?lt;/p><p&

19、gt;　　return p; </p><p><b>　　}</b></p><p><b>　?。?）創(chuàng)建鏈表模塊</b></p><p>　　void createList(LNode *ppHead,int n)</p><p><b>　?。?）出隊(duì)處理模塊</b>&

20、lt;/p><p>　　void jose(LNode *ppHead,int m_pwd)</p><p>　?。?）約瑟夫環(huán)說(shuō)明輸出模塊</p><p>　　void instruction()</p><p><b>　?。?）菜單模塊</b></p><p>　　void menu()<

21、/p><p><b>　?。?）主函數(shù)模塊</b></p><p>　　int main（）</p><p>　　函數(shù)的調(diào)用關(guān)系圖如圖3所示：</p><p>　　圖3 約瑟夫環(huán)函數(shù)調(diào)用關(guān)系圖</p><p><b>　　第三章 詳細(xì)設(shè)計(jì)</b></p><

22、p><b>　　3.1 主函數(shù)</b></p><p>　　圖4 主函數(shù)數(shù)據(jù)流程圖</p><p>　　根據(jù)圖4，主函數(shù)程序如下：</p><p>　　int main()</p><p><b>　　{ </b></p><p>　　int n,m,x;</p

23、><p>　　LNode *ppHead=NULL;</p><p><b>　　menu();</b></p><p><b>　　for(;;)</b></p><p><b>　　{ </b></p><p>　　printf("\n請(qǐng)選擇

24、要執(zhí)行的操作：");</p><p>　　scanf("%d",&x);</p><p>　　system("cls");</p><p><b>　　switch(x)</b></p><p><b>　　{</b></p>

25、<p>　　case 1: </p><p>　　printf("**********************************************\n");</p><p>　　printf("約瑟夫環(huán):\n"); </p><p>

26、　　printf(" 編號(hào)為1,2,3,4…,n的n個(gè)人按順時(shí)針?lè)较驀蝗?每人持有一個(gè)密碼(正整數(shù)).一開(kāi)始任選一個(gè)正整數(shù)作為報(bào)數(shù)的上限值m,從第一個(gè)人開(kāi)始按順時(shí)針?lè)较蜃?開(kāi)始按順序報(bào)數(shù),報(bào)到m時(shí)停止.報(bào)m的人出列，將他的密碼m作為新的m值,從他的順時(shí)針?lè)较蛏系南乱蝗碎_(kāi)始重新從1報(bào)數(shù),如此下去,直到所有人全部出列為止.編程打印出列順序.\n");</p><p>　　printf(&qu

27、ot;**********************************************\n"); </p><p><b>　　main();</b></p><p><b>　　break;</b></p><p><b>　　case 2:</b></p>&l

28、t;p>　　printf("請(qǐng)輸入總?cè)藬?shù)n：\n");</p><p>　　scanf("%d",&n);</p><p>　　printf("請(qǐng)輸入開(kāi)始上限數(shù)m:");</p><p>　　scanf("%d",&m);</p><p>　

29、　createList(&ppHead,n); </p><p>　　printf("\n");</p><p>　　printf("出隊(duì)順序：\n");</p><p>　　jose(ppHead,m);</p><p>　　printf("\n約瑟夫環(huán)游戲結(jié)束!\n");

30、</p><p><b>　　main();</b></p><p><b>　　break;</b></p><p><b>　　case 0:</b></p><p><b>　　exit(0);</b></p><p><

31、;b>　　default:</b></p><p>　　system("cls");</p><p>　　printf("\n您選擇的操作有誤，請(qǐng)重新選擇...\n ");</p><p><b>　　main();</b></p><p><b>　

32、　}</b></p><p><b>　　}</b></p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p><b>　　3.2 鏈表的創(chuàng)建</b></p><p>

33、;　　圖5 創(chuàng)建鏈表函數(shù)的數(shù)據(jù)流程圖</p><p>　　/*創(chuàng)建單向循環(huán)鏈表ppHead，參加人數(shù)個(gè)數(shù)為n，并輸入每人的密碼值，若建立失敗則生成頭結(jié)點(diǎn)，讓cur指向他，若建立成功則插入結(jié)點(diǎn)P，cur指向的數(shù)據(jù)元素為p,后續(xù)為"空"的結(jié)點(diǎn)，再把P插入循環(huán)鏈表ppHead中*/</p><p>　　根據(jù)圖5，創(chuàng)建鏈表函數(shù)程序如下：</p><p>

34、　　void createList(LNode **ppHead,int n)</p><p><b>　　{</b></p><p>　　int i,m_pwd;</p><p>　　LNode *p,*cur;//cur:浮標(biāo)指針</p><p>　　for(i=1;i<=n;i++)</p>&

35、lt;p><b>　　{ </b></p><p>　　printf("輸入第%d個(gè)人的密碼：",i);</p><p>　　scanf("%d",&m_pwd);//輸入持有密碼 </p><p>　　p=createNode(i,m_pwd);//調(diào)用構(gòu)造結(jié)點(diǎn)函數(shù)</p>

36、<p>　　if(*ppHead==NULL)//如果頭結(jié)點(diǎn)為空 </p><p>　　{ *ppHead=cur=p;//生成頭結(jié)點(diǎn)，讓cur指向他 </p><p>　　cur->next=*ppHead;//cur的指針域指向自身 </p><p><b>　　}</b></p><p>　　e

37、lse//如果不為空，則插入結(jié)點(diǎn) </p><p>　　{ p->next = cur->next;</p><p>　　cur->next = p;</p><p>　　cur= p;//cur指向新插入結(jié)點(diǎn)</p><p><b>　　} </b></p><p><

38、;b>　　} </b></p><p>　　printf("完成創(chuàng)建！\n"); //提示鏈表創(chuàng)建完成 </p><p><b>　　}</b></p><p><b>　　3.3 出隊(duì)處理</b></p><p>　　圖6 出對(duì)函數(shù)的數(shù)據(jù)流程圖</p&g

39、t;<p>　　/*p指向要?jiǎng)h除結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)，ppHead指向要?jiǎng)h除的結(jié)點(diǎn)，使p=ppHead，ppHead再指向要?jiǎng)h除結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，使p和ppHead鏈接，輸出p指向結(jié)點(diǎn)的編號(hào)和密碼值，釋放ppHead，如此循環(huán)，直至把所有結(jié)點(diǎn)都打印和刪除為止！*/</p><p>　　根據(jù)圖6，出隊(duì)函數(shù)程序如下：</p><p>　　void jose(LNode *ppHead

40、,int m_pwd)</p><p><b>　　{</b></p><p><b>　　int i,j;</b></p><p>　　LNode *p;//定義指針變量</p><p>　　for(i=1;p!=ppHead;i++)</p><p><b>　

41、　{ </b></p><p>　　for(j=1;j<m_pwd;++j) </p><p><b>　　{</b></p><p>　　p=ppHead;//p賦值為ppHead，p指向要?jiǎng)h除結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)</p><p>　　ppHead=ppHead->next;//ppHead指向下

42、一個(gè)元素</p><p><b>　　}</b></p><p>　　p->next = ppHead->next;//p結(jié)點(diǎn)與頭結(jié)點(diǎn)鏈接</p><p>　　i=ppHead->pwd;//i賦值為ppHead->pwd</p><p>　　j=ppHead->num;//j賦值為ppHe

43、ad->num，j為要?jiǎng)h除的密碼值</p><p>　　printf("第%d個(gè)人出列，密碼：%d\n",j,i); </p><p>　　m_pwd=ppHead->pwd;//m_pwd賦值為ppHead->pwd</p><p>　　free(ppHead);//釋放頭結(jié)點(diǎn)</p><p>　　pp

44、Head=p->next;//ppHead重新賦值給p->next,即釋放前的ppHead->pwd指針//刪除報(bào)數(shù)結(jié)點(diǎn) </p><p><b>　　}</b></p><p>　　i=ppHead->pwd;//i賦值為ppHead->pwd</p><p>　　j=ppHead->num;//j賦值為p

45、pHead->num</p><p>　　printf("最后一個(gè)出列是%d號(hào)，密碼是:%d\n",j,i); </p><p>　　free(ppHead);//釋放頭結(jié)點(diǎn)</p><p><b>　　}</b></p><p>　　3.4 約瑟夫環(huán)說(shuō)明模塊</p><p&

46、gt;　　void instruction()</p><p><b>　　{ </b></p><p>　　printf("**********************************************\n"); </p><p>　　printf("約瑟夫環(huán):\n"); </p

47、><p>　　printf(" 編號(hào)為1,2,3,4…,n的n個(gè)人按順時(shí)針?lè)较驀蝗?每人持有一個(gè)密碼(正整數(shù)).一開(kāi)始任選一個(gè)正整數(shù)作為報(bào)數(shù)的上限值m,從第一個(gè)人開(kāi)始按順時(shí)針?lè)较蜃?開(kāi)始按順序報(bào)數(shù),報(bào)到m時(shí)停止.報(bào)m的人出列，將他的密碼m作為新的m值,從他的順時(shí)針?lè)较蛏系南乱蝗碎_(kāi)始重新從1報(bào)數(shù),如此下去,直到所有人全部出列為止.編程打印出列順序.\n"); </p><

48、;p>　　printf("**********************************************\n"); </p><p><b>　　}</b></p><p><b>　　3.5菜單模塊</b></p><p>　　void menu()</p><

49、p><b>　　{</b></p><p>　　printf("*****************約瑟夫環(huán)***********************\n");</p><p>　　printf("\n");

50、 </p><p>　　printf(" [1]約瑟夫環(huán)問(wèn)題的闡述 \n"); </p><p>　　printf(" [2]按要求求解約瑟夫環(huán) \n");

51、</p><p>　　printf(" [0]退出 \n"); </p><p>　　printf("**************** 歡迎使用！*********************\n");</p><p

52、><b>　　}</b></p><p>　　第四章 程序調(diào)試與測(cè)試</p><p>　　1. 調(diào)用模塊時(shí)，結(jié)點(diǎn)結(jié)構(gòu)的調(diào)用與其他模塊產(chǎn)生沖突，導(dǎo)致每一行都出現(xiàn)兩個(gè)錯(cuò)誤，加入子函數(shù)的聲明后，錯(cuò)誤消失。</p><p>　　2. 剛開(kāi)始時(shí)忽略了一些變量參數(shù)的標(biāo)識(shí)，如："&"和“*”，使調(diào)試程序時(shí)費(fèi)時(shí)不少。今后應(yīng)重視

53、確定參數(shù)的變量和賦值屬性的區(qū)分和標(biāo)識(shí)。</p><p>　　3. 本次課程設(shè)計(jì)采用數(shù)據(jù)抽象的程序設(shè)計(jì)方法，將程序劃分為三個(gè)結(jié)構(gòu)：元素結(jié)點(diǎn)、單向循環(huán)鏈表，主控制模塊。思路較為清晰，實(shí)現(xiàn)調(diào)用順利。 經(jīng)過(guò)本次實(shí)驗(yàn)，使我對(duì)數(shù)據(jù)結(jié)構(gòu)這門課程有了進(jìn)一步的了解，每一個(gè)程序經(jīng)過(guò)問(wèn)題分析、概要設(shè)計(jì)、詳細(xì)設(shè)計(jì)之后，思路清晰呈現(xiàn)，程序也很快就出來(lái)了，最后經(jīng)過(guò)調(diào)試、運(yùn)行，又有了新的體驗(yàn)。</p><p><

54、b>　　<測(cè)試用例></b></p><p>　　這是一個(gè)使用循環(huán)鏈表的經(jīng)典問(wèn)題。本程序開(kāi)始運(yùn)行界面如圖7所示：</p><p>　　圖7 約瑟夫環(huán)開(kāi)始運(yùn)行界面</p><p>　　選擇1進(jìn)入約瑟夫環(huán)問(wèn)題闡述，如圖8所示：</p><p>　　圖8 約瑟夫環(huán)問(wèn)題闡述</p><p>　　

55、①選擇2，輸入下列數(shù)據(jù)測(cè)試，測(cè)試結(jié)果如圖9所示：</p><p><b>　　請(qǐng)輸入總?cè)藬?shù)n：8</b></p><p>　　請(qǐng)輸入開(kāi)始上限數(shù)m：9</p><p>　　請(qǐng)依次輸入每個(gè)人的密碼：9 3 7 9 12 6 11 10 13</p><p>　　出隊(duì)順序：1 4 3 8 2 5 7 6 </p>

56、<p>　　圖9 約瑟夫環(huán)測(cè)試1</p><p>　?、谶x擇2，輸入下列數(shù)據(jù)測(cè)試，測(cè)試結(jié)果如圖10所示：</p><p><b>　　請(qǐng)輸入總?cè)藬?shù)n：6</b></p><p>　　請(qǐng)輸入開(kāi)始上限數(shù)m：16</p><p>　　請(qǐng)依次輸入每個(gè)人的密碼：32 5 6 9 8 7 </p><

57、p>　　出隊(duì)順序：4 2 3 1 6 5</p><p>　　圖10 約瑟夫環(huán)測(cè)試2</p><p>　?、劾^續(xù)選擇2，輸入下列數(shù)據(jù)測(cè)試，測(cè)試結(jié)果如圖11所示：</p><p><b>　　請(qǐng)輸入總?cè)藬?shù)n：7</b></p><p>　　請(qǐng)輸入開(kāi)始上限數(shù)m：20</p><p>　　請(qǐng)依次輸

58、入每個(gè)人的密碼：2 4 6 3 8 4 0 </p><p>　　出隊(duì)順序：6 3 4 1 5 2 7</p><p>　　圖11 約瑟夫環(huán)測(cè)試3</p><p><b>　　第五章 結(jié)論</b></p><p>　　我這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)的題目是:約瑟夫環(huán)問(wèn)題。通過(guò)對(duì)該題目的設(shè)計(jì),我加深了對(duì)數(shù)據(jù)結(jié)構(gòu)及存儲(chǔ)結(jié)構(gòu)的理解,進(jìn)

59、一步地理解和掌握了課本中所學(xué)的各種數(shù)據(jù)結(jié)構(gòu)，尤其是對(duì)單循環(huán)鏈表的基本運(yùn)算的實(shí)現(xiàn),學(xué)會(huì)了如何把學(xué)到的知識(shí)用于解決實(shí)際問(wèn)題,鍛煉了自己動(dòng)手的能力。</p><p>　　通過(guò)這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)，我感受最深的就是對(duì)于循環(huán)鏈表的使用，可以說(shuō)對(duì)循環(huán)鏈表有了比以前更進(jìn)一步的認(rèn)識(shí)，以前只是一知半解的，如果只給個(gè)題目，自己根本不能把程序完整地編寫出來(lái)，所以這次課程設(shè)計(jì)最大的收獲就在于對(duì)循環(huán)鏈表有了一定的理解，包括其中的一系列操作

60、，如建立一個(gè)循環(huán)鏈表，刪除鏈表中的一個(gè)結(jié)點(diǎn)，增加一個(gè)結(jié)點(diǎn)等。</p><p>　　兩周的課程設(shè)計(jì)很短暫，但其間的內(nèi)容是很充實(shí)的，在其中我學(xué)習(xí)到了很多平時(shí)書本中無(wú)法學(xué)到的東西，積累了經(jīng)驗(yàn)，鍛煉了自己分析問(wèn)題，解決問(wèn)題的能力。總而言之這兩周中我學(xué)到很多，受益匪淺。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1] 嚴(yán)蔚敏，吳

61、偉民 著.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）[M].北京：清華大學(xué)出版社，1997.</p><p>　　[2] 嚴(yán)蔚敏，吳偉民 著.數(shù)據(jù)結(jié)構(gòu)題集（C語(yǔ)言版）[M].北京：清華大學(xué)出版社，1997.</p><p>　　[3] William Ford,William Topp 著. DATA STRUCTURE WITH C++ [M].北京：清華大學(xué)出版社，1996 .</p><

62、;p>　　[4] 譚浩強(qiáng) 著. C語(yǔ)言程序設(shè)計(jì)[M].北京： 清華大學(xué)出版社，2000.</p><p>　　[5] 周云靜 著．?dāng)?shù)據(jù)結(jié)構(gòu)習(xí)題解析與上機(jī)指導(dǎo)[M]．北京：冶金工業(yè)出版社，2004.</p><p>　　[6] 陳慧南 著．?dāng)?shù)據(jù)結(jié)構(gòu)—C++語(yǔ)言描述[M]．北京：人民郵電出版社，2005.</p><p>　　[7] Adam Drozdek 著．

63、數(shù)據(jù)結(jié)構(gòu)與算法[M]．北京：清華大學(xué)出版社，2006.</p><p>　　[8] 徐孝凱 著．?dāng)?shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)[M]．北京：中央廣播電視大學(xué)出版社，2001.</p><p><b>　　致 謝</b></p><p>　　這次的課程設(shè)計(jì)，我們四人一小組完成自己所選的課題，但是還是得到了來(lái)自很多方面的幫助。在此首先要感謝學(xué)院提供給我這次實(shí)踐

64、的機(jī)會(huì)，讓我們有機(jī)會(huì)貼近現(xiàn)實(shí)，感受成功的喜悅；其次要感謝實(shí)驗(yàn)機(jī)房的老師提供優(yōu)良的實(shí)驗(yàn)設(shè)備供我們做課程設(shè)計(jì)，正是這種良好的課程設(shè)計(jì)的環(huán)境讓我們整個(gè)課程設(shè)計(jì)過(guò)程心情都非常愉快。再次要感謝指導(dǎo)老師的辛勤指導(dǎo)，每當(dāng)我們遇到疑難問(wèn)題時(shí)，是他一次次不厭其煩地解釋和悉心地指導(dǎo)，我們才能闖過(guò)一個(gè)個(gè)難關(guān)，到達(dá)勝利的彼岸，是他給我們提供了一次寶貴的檢驗(yàn)自己的機(jī)會(huì)。最后也要感謝同伴們的幫助，有了他們的支持使我遇到任何困難都覺(jué)得不是一個(gè)人在戰(zhàn)斗。感謝所有在課程

65、設(shè)計(jì)過(guò)程中幫助過(guò)我的人！</p><p><b>　　附 錄</b></p><p><b>　　源代碼：</b></p><p>　　#include <stdio.h>//輸入輸出函數(shù)頭文件</p><p>　　#include <stdlib.h>//字符串轉(zhuǎn)短整

66、形函數(shù)的頭文件</p><p>　　typedef struct LNode//定義單循環(huán)鏈表中結(jié)點(diǎn)的結(jié)構(gòu) </p><p>　　{ int num;//編號(hào) </p><p>　　int pwd;//password</p><p>　　struct LNode *next;//指向下一結(jié)點(diǎn)的指針</p><p>

67、<b>　　}LNode;</b></p><p><b>　　/*構(gòu)造結(jié)點(diǎn)*/</b></p><p>　　LNode *createNode(int m_num,int m_pwd)</p><p>　　{ LNode *p;</p><p>　　p=(LNode *)malloc(sizeo

68、f(LNode));//生成一個(gè)結(jié)點(diǎn) </p><p>　　p->num=m_num;//把實(shí)參賦給相應(yīng)的數(shù)據(jù)域</p><p>　　p->pwd=m_pwd;</p><p>　　p->next=NULL;//指針域?yàn)榭?lt;/p><p>　　return p; </p><p><b>　

69、　} </b></p><p>　　/*創(chuàng)建循環(huán)鏈表*/</p><p>　　void createList(LNode **ppHead,int n)</p><p>　　{/*創(chuàng)建單向循環(huán)鏈表ppHead，人數(shù)個(gè)數(shù)為n，并輸入每個(gè)人的密碼值，若建立失敗則生成頭結(jié)點(diǎn)，讓cur指向他，若建立成功則插入結(jié)點(diǎn)P，cur指</p><p&g

70、t;　　向的數(shù)據(jù)元素為p,后續(xù)為"空"的結(jié)點(diǎn)，再把P插入循環(huán)鏈表ppHead中*/</p><p>　　int i,m_pwd;</p><p>　　LNode *p,*cur;//cur:浮標(biāo)指針</p><p>　　for(i=1;i<=n;i++)</p><p>　　{ printf("輸入第%d

71、個(gè)人的密碼：",i);</p><p>　　scanf("%d",&m_pwd);//輸入持有密碼 </p><p>　　p=createNode(i,m_pwd);//調(diào)用構(gòu)造結(jié)點(diǎn)函數(shù)</p><p>　　if(*ppHead==NULL)//如果頭結(jié)點(diǎn)為空 </p><p>　　{ *ppHead=

72、cur=p;//生成頭結(jié)點(diǎn)，讓cur指向他 </p><p>　　cur->next=*ppHead;//cur的指針域指向自身 </p><p><b>　　}</b></p><p>　　else//如果不為空，則插入結(jié)點(diǎn) </p><p>　　{ p->next = cur->next;<

73、/p><p>　　cur->next = p;</p><p>　　cur= p;//cur指向新插入結(jié)點(diǎn)</p><p><b>　　} </b></p><p><b>　　} </b></p><p>　　printf("完成創(chuàng)建！\n"); /

74、/提示鏈表創(chuàng)建完成 </p><p><b>　　} </b></p><p><b>　　/*出隊(duì)處理*/</b></p><p>　　void jose(LNode *ppHead,int m_pwd)</p><p>　　{/*p指向要?jiǎng)h除結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)，ppHead指向要?jiǎng)h除的結(jié)點(diǎn)，使p=

75、ppHead，ppHead再指向要?jiǎng)h除結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，使p和ppHead鏈接，輸出p指向結(jié)點(diǎn)的編號(hào)和密碼值，釋放ppHead，如此循環(huán)，直至把所有結(jié)點(diǎn)都打印和刪除為止！*/</p><p><b>　　int i,j;</b></p><p>　　LNode *p;//定義指針變量</p><p>　　for(i=1;p!=ppHead;i+

76、+)</p><p>　　{ for(j=1;j<m_pwd;++j)</p><p>　　{ p=ppHead;//p賦值為ppHead，p指向要?jiǎng)h除結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)</p><p>　　ppHead=ppHead->next;//ppHead指向下一個(gè)元素</p><p><b>　　} </b>&l

77、t;/p><p>　　p->next = ppHead->next;//p結(jié)點(diǎn)與頭結(jié)點(diǎn)鏈接</p><p>　　i=ppHead->pwd;//i賦值為ppHead->pwd</p><p>　　j=ppHead->num;//j賦值為ppHead->num，j為要?jiǎng)h除的密碼值</p><p>　　printf

78、("第%d個(gè)人出列，密碼：%d\n",j,i); </p><p>　　m_pwd=ppHead->pwd;//m_pwd賦值為ppHead->pwd</p><p>　　free(ppHead);//釋放頭結(jié)點(diǎn)</p><p>　　ppHead=p->next;//ppHead重新賦值給p->next,即釋放前的ppHe

79、ad->pwd指針//刪除報(bào)數(shù)結(jié)點(diǎn) </p><p><b>　　}</b></p><p>　　i=ppHead->pwd;//i賦值為ppHead->pwd</p><p>　　j=ppHead->num;//j賦值為ppHead->num</p><p>　　printf("

80、最后一個(gè)出列是%d號(hào)，密碼是:%d\n",j,i); </p><p>　　free(ppHead);//釋放頭結(jié)點(diǎn)</p><p><b>　　}</b></p><p>　　void instruction()</p><p>　　{ printf("*********************

81、**************************\n"); </p><p>　　printf("約瑟夫環(huán):\n"); </p><p>　　printf(" 編號(hào)為1,2,3,4…,n的n個(gè)人按順時(shí)針?lè)较驀蝗?每人持有一個(gè)密碼(正整數(shù)).一開(kāi)始任選一個(gè)正整數(shù)作為報(bào)數(shù)的上限值m,從第一個(gè)人開(kāi)始按順時(shí)針?lè)较蜃?開(kāi)始順序報(bào)數(shù),報(bào)到時(shí)停止.報(bào)

82、m的人出列，將他的密碼m作為新的m值,從他在順時(shí)針?lè)较蛏系南乱蝗碎_(kāi)始重新從1報(bào)數(shù),如此下去, 直到所有人全部出列為止.編程打印出列順序.\n"); </p><p>　　printf("***********************************************\n"); </p><p><b>

83、　　}</b></p><p>　　void menu()</p><p>　　{ printf("****************約瑟夫環(huán)*************************\n");</p><p>　　printf("\n");</p><p>　　printf(

84、" [1]約瑟夫環(huán)問(wèn)題的闡述 \n");</p><p>　　printf(" [2]按要求求解約瑟夫環(huán) \n");</p><p>　　printf(" [0]退出

85、 \n");</p><p>　　printf("****************歡迎使用！**********************\n");</p><p><b>　　} </b></p><p><b>　　/*主函數(shù)模塊*/</b></p><p>

86、　　int main()</p><p>　　{ int n,m,x;</p><p>　　LNode *ppHead=NULL;</p><p><b>　　menu();</b></p><p><b>　　for(;;)</b></p><p>　　{ print

87、f("\n請(qǐng)選擇要執(zhí)行的操作：");</p><p>　　scanf("%d",&x);</p><p>　　system("cls");</p><p><b>　　switch(x)</b></p><p>　　{ case 1:</p>

88、;<p>　　printf("*****************************************\n"); </p><p>　　printf("約瑟夫環(huán):\n"); </p><p>　　printf(" 編號(hào)為1,2,3,4…,n的n個(gè)人按順時(shí)針?lè)较驀蝗?每人持有一個(gè)密碼(正整數(shù)).一開(kāi)始任選一個(gè)

89、正整數(shù)作為報(bào)數(shù)的上限值m,從第一個(gè)人開(kāi)始按順時(shí)針?lè)较蜃?開(kāi)始順序報(bào)數(shù),報(bào)到m時(shí)停止.報(bào)m的人出列，將他的密碼m作為新的m值,從他在順時(shí)針?lè)较蛏系南乱蝗碎_(kāi)始重新從1報(bào)數(shù),如此下去, 直到所有人全部出列為止.編程打印出列順序.\n");

90、</p><p>　　printf("****************************************\n"); </p><p><b>　　main(); </b></p><p><b>　　break;</

91、b></p><p><b>　　case 2:</b></p><p>　　printf("\n請(qǐng)輸入總?cè)藬?shù)n：");</p><p>　　scanf("%d",&n);</p><p>　　printf("請(qǐng)輸入開(kāi)始上限數(shù)m：");</p

92、><p>　　scanf("%d",&m);</p><p>　　createList(&ppHead,n); </p><p>　　printf("\n");</p><p>　　printf("出隊(duì)順序：\n");</p><p>　　jose

93、(ppHead,m);</p><p>　　printf("\n約瑟夫環(huán)游戲結(jié)束!\n");</p><p><b>　　main();</b></p><p><b>　　break;</b></p><p><b>　　case 0:</b></p

94、><p><b>　　exit(0);</b></p><p><b>　　default:</b></p><p>　　system("cls");</p><p>　　printf("\n您選擇的操作有誤，請(qǐng)重新選擇...\n\n\n");</p>

95、<p><b>　　main();</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　return 0;</b></p><p><b>　　} </b&g