數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告---約瑟夫環(huán)

1、<p>　　課 程 設(shè) 計(jì) 報(bào) 告</p><p>　　課程設(shè)計(jì)名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)</p><p>　　課程設(shè)計(jì)題目：約瑟夫環(huán)</p><p><b>　　院（系）：電信學(xué)院</b></p><p>　　專 業(yè)：計(jì)算機(jī)應(yīng)用科學(xué)</p><p><b>　　目 錄

2、</b></p><p>　　1 課程設(shè)計(jì)介紹1</p><p>　　1.1 課程設(shè)計(jì)內(nèi)容1</p><p>　　1.2 課程設(shè)計(jì)要求1</p><p>　　2 課程設(shè)計(jì)原理2</p><p>　　2.1 課設(shè)題目粗略分析2</p><p>　　2.2 原理圖介紹3&

3、lt;/p><p>　　2.2.1 功能模塊圖3</p><p>　　2.2.2 流程圖分析4</p><p>　　3 數(shù)據(jù)結(jié)構(gòu)分析7</p><p>　　3.1 存儲(chǔ)結(jié)構(gòu)................................................................................7&l

4、t;/p><p>　　3.2 算法描述7</p><p>　　4 調(diào)試與分析9</p><p>　　4.1 調(diào)試過程9</p><p>　　4.2 程序執(zhí)行過程10</p><p><b>　　參考文獻(xiàn)15</b></p><p>　　附 錄（關(guān)鍵部分程序清單）

5、16</p><p><b>　　1 課程設(shè)計(jì)介紹</b></p><p>　　1.1 課程設(shè)計(jì)內(nèi)容</p><p>　　設(shè)計(jì)程序，系統(tǒng)主要功能如下：</p><p>　　編號(hào)為1，2，…，n的n個(gè)人按順時(shí)針方向圍坐一圈，每人持有一個(gè)密碼（正整數(shù)）。開始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m，從第一個(gè)人開始按順時(shí)針方向自1開

6、始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針方向上的下一個(gè)人開始重新從1報(bào)數(shù)，如此下去，直至所有人全部出列為止。試設(shè)計(jì)一個(gè)程序求出出列順序。</p><p>　　1.2 課程設(shè)計(jì)要求</p><p>　　1.參考相應(yīng)的資料，獨(dú)立完成課程設(shè)計(jì)任務(wù)書。</p><p>　　2.交規(guī)范課程設(shè)計(jì)報(bào)告和軟件代碼。</p>&l

7、t;p><b>　　2 課程設(shè)計(jì)原理</b></p><p>　　2.1 課設(shè)題目粗略分析</p><p>　　根據(jù)課設(shè)題目要求，擬將整體程序分為四大模塊。此四個(gè)模塊相互獨(dú)立，沒有嵌套調(diào)用的情況，以下是四個(gè)模塊的大體分析：</p><p>　　main()函數(shù)是主要的控制函數(shù)，main()函數(shù)主要負(fù)責(zé)存儲(chǔ)用戶輸入的基本數(shù)據(jù)以及調(diào)用其他子

8、函數(shù)模塊，在main()函數(shù)中還存在一個(gè)比較小的函數(shù)模塊exit(0),該函數(shù)模塊負(fù)責(zé)終止程序運(yùn)行，另外還有兩個(gè)子函數(shù)模塊，分別是random()函數(shù)模塊與solid()函數(shù)模塊，這兩個(gè)函數(shù)模塊分別各自負(fù)責(zé)自己所要處理的數(shù)據(jù)以及輸出功能；</p><p>　　在程序運(yùn)行之后，在程序主界面出現(xiàn)之后，當(dāng)用戶自己輸入了自己想要實(shí)現(xiàn)的功能模塊所在的數(shù)字選項(xiàng)后，立即進(jìn)入主函數(shù)模塊之中，當(dāng)用戶輸入了所有的必要數(shù)據(jù)之后，按照用

9、戶選定的數(shù)字選項(xiàng)所要實(shí)現(xiàn)的功能調(diào)用相應(yīng)的子函數(shù)；</p><p>　　如果用戶選擇的是系統(tǒng)隨機(jī)產(chǎn)生密碼的選項(xiàng)，則main()函數(shù)就調(diào)用random()子函數(shù)模塊，在random()函數(shù)模塊中，將會(huì)隨機(jī)產(chǎn)生各個(gè)參與者的密碼，并且同時(shí)建立鏈表來存儲(chǔ)、處理這些數(shù)據(jù)，在完成了所有的操作之后，random()函數(shù)就將輸出結(jié)果，反之，如果用戶選擇的是用戶自己輸入密碼的選項(xiàng)，則main()函數(shù)就調(diào)用solid()函數(shù)模塊，在s

10、olid()函數(shù)模塊中，將會(huì)提醒用戶自己一個(gè)個(gè)的輸入每個(gè)參與者的密碼，與此同時(shí)建立鏈表來存儲(chǔ)、處理這些數(shù)據(jù)，在完成了所有的操作之后，solid()函數(shù)就將輸出結(jié)果。</p><p><b>　　2.2 原理圖介紹</b></p><p>　　2.2.1 功能模塊圖</p><p>　　圖2.1 功能模塊圖</p><p>

11、;　　2.2.2 流程圖分析</p><p>　　1.如圖2.2，random()函數(shù)的執(zhí)行過程如下；</p><p><b>　　N</b></p><p><b>　　Y</b></p><p>　　圖2.2 random()函數(shù)流程圖</p><p>　　2.如圖2.3

12、，solid()函數(shù)的執(zhí)行過程如下；</p><p><b>　　N</b></p><p><b>　　Y</b></p><p>　　圖2.3 solid()函數(shù)流程圖</p><p>　　3.如圖2.4，main()函數(shù)的執(zhí)行過程如下。</p><p><b>

13、;　　N</b></p><p><b>　　Y</b></p><p>　　圖2.4 main()函數(shù)流程圖</p><p>　　3 數(shù)據(jù)結(jié)構(gòu)分析 </p><p>　　3.1 存儲(chǔ)結(jié)構(gòu) num codenext</p><p>　　圖3.1 數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)&l

14、t;/p><p><b>　　3.2 算法描述</b></p><p>　　1. 用戶輸入數(shù)據(jù)；</p><p>　　while(scanf("%d",&p)!=EOF)</p><p><b>　　{</b></p><p><b>　　

15、if(p==1)</b></p><p><b>　　random();</b></p><p>　　else if(p==2)</p><p><b>　　solid();</b></p><p><b>　　else</b></p><p&g

16、t;<b>　　exit(0);</b></p><p>　　printf("*************************歡迎進(jìn)入約瑟夫環(huán)問題求解系統(tǒng)*************************\n \n");</p><p>　　printf("1.按照系統(tǒng)隨機(jī)給出的密碼進(jìn)行 2.按照自己輸入的密碼進(jìn)行 3.退出該系

17、統(tǒng)\n\n");</p><p>　　printf("********************請(qǐng)輸入您要實(shí)現(xiàn)的功能模塊所在的數(shù)字選項(xiàng)!********************\n\n");</p><p><b>　　}</b></p><p>　　random()函數(shù)隨機(jī)產(chǎn)生各個(gè)參與者的密碼，用戶在此函數(shù)中輸入第

18、一個(gè)要報(bào)的數(shù)，此函數(shù)之后會(huì)排好各個(gè)參與者的出列順序；</p><p>　　or(i=1;i<=n;i++) </p><p>　　{ key=rand()%100;</p><p>　　printf("第%d個(gè)人的密碼:%d\n",i,key); </p><p><b>　　s=p; </b>

19、;</p><p>　　p=(list *)malloc(sizeof(list)); //創(chuàng)建新的結(jié)點(diǎn).</p><p>　　s->next=p; </p><p>　　p->num=i; </p><p>　　p->code=key; </p><p><b>　　} </b>

20、;</p><p>　　p->next=head->next; </p><p><b>　　p=head; </b></p><p>　　head=head->next; </p><p>　　free(p); //釋放頭結(jié)點(diǎn).</p><p><b>　　p=hea

21、d;</b></p><p><b>　　do{ </b></p><p>　　printf("\n第%d號(hào)成員的密碼為:%d",p->num,p->code); //輸出鏈表.</p><p>　　p=p->next; </p><p>　　}while(p!=head

22、); </p><p>　　printf("\n\n輸入第一個(gè)報(bào)的數(shù):\n"); </p><p>　　scanf("%d",&key);</p><p>　　3. solid()函數(shù)提示用戶輸入各個(gè)參與者的密碼及第一個(gè)要報(bào)的數(shù)，并且排好各個(gè)參與者的出列順序。</p><p>　　for(i=1

23、;i<=n;i++) </p><p>　　{ scanf("%d",&key);</p><p>　　printf("第%d個(gè)人的密碼:%d\n",i,key);</p><p><b>　　s=p; </b></p><p>　　p=(list *)malloc(

24、sizeof(list)); //創(chuàng)建新的結(jié)點(diǎn).</p><p>　　s->next=p; </p><p>　　p->num=i; </p><p>　　p->code=key; </p><p>　　printf("請(qǐng)輸入密碼:");</p><p><b>　　}

25、</b></p><p>　　p->next=head->next; </p><p><b>　　p=head; </b></p><p>　　head=head->next; </p><p>　　free(p); //釋放頭結(jié)點(diǎn).</p><p><b&g

26、t;　　p=head;</b></p><p><b>　　do{ </b></p><p>　　printf("\n第%d號(hào)成員的密碼為:%d",p->num,p->code); //輸出鏈表.</p><p>　　p=p->next; </p><p>　　}whil

27、e(p!=head); </p><p>　　printf("\n\n輸入第一個(gè)報(bào)的數(shù):\n"); </p><p>　　scanf("%d",&key);</p><p><b>　　}</b></p><p><b>　　4 調(diào)試與分析</b>&

28、lt;/p><p><b>　　4.1 調(diào)試過程</b></p><p>　　在調(diào)試程序是主要遇到一下幾類問題：</p><p>　　1.調(diào)試過程中,曾出現(xiàn)過缺少分號(hào)、括號(hào)之類的錯(cuò)誤,還出現(xiàn)過運(yùn)算順序顛倒，致使運(yùn)算出現(xiàn)了錯(cuò)誤，在經(jīng)過仔細(xì)的檢查并且向人請(qǐng)教,終于得出了正確結(jié)果.這次的課程設(shè)計(jì)的代碼比較冗長(zhǎng)，所以等有了解題思路后，把代碼都寫上后難免會(huì)有

29、很多錯(cuò)誤。當(dāng)?shù)谝淮伟颜麄€(gè)程序?qū)懞煤筮\(yùn)行，出現(xiàn)了很多錯(cuò)誤。不過經(jīng)過一點(diǎn)點(diǎn)的改正，錯(cuò)誤也慢慢地變少。這也說明做事要認(rèn)真，尤其做計(jì)算機(jī)這方面工作的時(shí)候，因?yàn)橛?jì)算機(jī)不容許一點(diǎn)點(diǎn)的錯(cuò)誤，有了一點(diǎn)小錯(cuò)誤和有一個(gè)大錯(cuò)誤在計(jì)算機(jī)看來都是一樣的，都不會(huì)得到結(jié)果。有些小錯(cuò)誤，比如說少了個(gè)分號(hào)，變量忘了定義，數(shù)據(jù)溢出等都是些小錯(cuò)誤，但也不能松懈。因?yàn)橐⒁獾牡胤胶芏啵?jīng)過多次嘗試，問題也就自然而然的解決了，而且以后遇到這方面的問題都會(huì)覺得比較得心應(yīng)手。<

30、;/p><p>　　2.在隨機(jī)設(shè)置每個(gè)結(jié)點(diǎn)的key時(shí)也曾是個(gè)問題，因?yàn)槲易龅碾S機(jī)函數(shù)一直都用不好，要不是每次隨到的都是一樣的，要么就是每次隨到的數(shù)都很大，后來通過學(xué)長(zhǎng)的耐心講解才得以解決。在調(diào)試的過程中，類的優(yōu)勢(shì)很明顯，能很簡(jiǎn)單的把問題解決，而不需要使用的其他的一些比較復(fù)雜的方法。</p><p>　　4.2 程序執(zhí)行過程</p><p>　　*************

31、************歡迎進(jìn)入約瑟夫環(huán)問題求解系統(tǒng)*************************系統(tǒng)使用說明：</p><p>　　1. 進(jìn)入程序主界面后，會(huì)出現(xiàn)三個(gè)選項(xiàng)，按1則是隨系統(tǒng)隨機(jī)產(chǎn)生的密碼進(jìn)行該問題求解，按2則是隨用戶自己輸入的密碼進(jìn)行該問題求解，按3則是退出系統(tǒng)；</p><p>　　2. 選定了進(jìn)行方式后，輸入該問題所涉及的總?cè)藬?shù)，如果用戶按了1，則隨機(jī)產(chǎn)生密碼，用戶

32、則只再需要輸入第一個(gè)人要報(bào)的數(shù)即可，如果用戶按了2，則是用戶自己手動(dòng)輸入密碼，輸入完了所有人的密碼后，之后再輸入第一個(gè)人要報(bào)的數(shù)；</p><p>　　3. 隨著程序的運(yùn)行，結(jié)果就會(huì)隨之出來，隨后進(jìn)入下一次該問題求解進(jìn)程，直到用戶自己選擇退出該程序，該程序才會(huì)結(jié)束。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1] 嚴(yán)蔚

33、敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社，2007.</p><p>　　[2] 張長(zhǎng)海，陳娟.C程序設(shè)計(jì)[M].北京：高等教育出版社，2004. </p><p>　　[3] 譚浩強(qiáng).C程序設(shè)計(jì)[M].北京：清華大學(xué)出版社，2005.</p><p>　　[4] 《數(shù)據(jù)結(jié)構(gòu)》（用面向?qū)ο蠓椒ㄅcC++描述），殷人昆等，清華大學(xué)出版社。</p>

34、<p>　　[5] 《算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題精解和實(shí)驗(yàn)指導(dǎo)》，寧正元等，清華大學(xué)出版社。</p><p>　　[6] 張乃孝,裘宗燕.數(shù)據(jù)結(jié)構(gòu)C++與面向?qū)ο蟮耐緩?北京：高等教育出版社，1998</p><p>　　[7] 周云靜．?dāng)?shù)據(jù)結(jié)構(gòu)習(xí)題解析與上機(jī)指導(dǎo)．北京：冶金工業(yè)出版社，2004</p><p>　　[8] 陳慧南．?dāng)?shù)據(jù)結(jié)構(gòu)—C++語(yǔ)言描述．北京：

35、人民郵電出版社，2005</p><p>　　[9] 嚴(yán)蔚敏，吳偉民．?dāng)?shù)據(jù)結(jié)構(gòu)．北京：清華大學(xué)出版社，1997</p><p>　　附 錄（關(guān)鍵部分程序清單）</p><p><b>　　程序代碼</b></p><p>　　#include<stdio.h></p><p>　　

36、#include<stdlib.h></p><p>　　struct list </p><p><b>　　{ </b></p><p>　　int num,code; </p><p>　　struct list *next; </p><p><b>　　}; <

37、;/b></p><p>　　int main() </p><p><b>　　{ </b></p><p>　　void random();</p><p>　　void solid();</p><p><b>　　int p;</b></p>&l

38、t;p>　　printf("*************************歡迎進(jìn)入約瑟夫環(huán)問題求解系統(tǒng)*************************\n \n");</p><p>　　printf("1.按照系統(tǒng)隨機(jī)給出的密碼進(jìn)行 2.按照自己輸入的密碼進(jìn)行 3.退出該系統(tǒng)\n\n");</p><p>　　printf(&q

39、uot;********************請(qǐng)輸入您要實(shí)現(xiàn)的功能模塊所在的數(shù)字選項(xiàng)!********************\n\n");</p><p>　　while(scanf("%d",&p)!=EOF)</p><p><b>　　{</b></p><p><b>　　if(p==

40、1)</b></p><p><b>　　random();</b></p><p>　　else if(p==2)</p><p><b>　　solid();</b></p><p><b>　　else</b></p><p><

41、b>　　exit(0);</b></p><p>　　printf("*************************歡迎進(jìn)入約瑟夫環(huán)問題求解系統(tǒng)*************************\n \n");</p><p>　　printf("1.按照系統(tǒng)隨機(jī)給出的密碼進(jìn)行 2.按照自己輸入的密碼進(jìn)行 3.退出該系統(tǒng)\n\n&

42、quot;);</p><p>　　printf("********************請(qǐng)輸入您要實(shí)現(xiàn)的功能模塊所在的數(shù)字選項(xiàng)!********************\n\n");</p><p><b>　　}</b></p><p><b>　　return 0;</b></p>

43、<p><b>　　}</b></p><p>　　void random()</p><p><b>　　{</b></p><p>　　int i,j,m=1;</p><p>　　int key; // 密碼.</p><p>　　int n; //人數(shù) .

44、</p><p>　　list *p,*s,*head;</p><p>　　head=(list *)malloc(sizeof(list)); //為頭結(jié)點(diǎn)分配空間.</p><p><b>　　p=head; </b></p><p>　　printf("輸入人的總個(gè)數(shù):\n"); </p

45、><p>　　scanf("%d",&n); </p><p>　　for(i=1;i<=n;i++) </p><p>　　{ key=rand()%100;</p><p>　　printf("第%d個(gè)人的密碼:%d\n",i,key); </p><p><

46、;b>　　s=p; </b></p><p>　　p=(list *)malloc(sizeof(list)); //創(chuàng)建新的結(jié)點(diǎn).</p><p>　　s->next=p; </p><p>　　p->num=i; </p><p>　　p->code=key; </p><p>

47、<b>　　} </b></p><p>　　p->next=head->next; </p><p><b>　　p=head; </b></p><p>　　head=head->next; </p><p>　　free(p); //釋放頭結(jié)點(diǎn).</p><

48、;p><b>　　p=head;</b></p><p><b>　　do{ </b></p><p>　　printf("\n第%d號(hào)成員的密碼為:%d",p->num,p->code); //輸出鏈表.</p><p>　　p=p->next; </p><

49、;p>　　}while(p!=head); </p><p>　　printf("\n\n輸入第一個(gè)報(bào)的數(shù):\n"); </p><p>　　scanf("%d",&key);</p><p>　　printf("\n出列順序?yàn)?\n"); </p><p><

50、b>　　do </b></p><p>　　{ j=1; p=head;</p><p>　　while(j<key) { </p><p><b>　　s=p; </b></p><p>　　p=p->next; </p><p><b>　　j++;

51、 </b></p><p><b>　　} //報(bào)數(shù)過程.</b></p><p>　　i=p->num; </p><p>　　key=p->code; </p><p>　　printf("%d:第%d號(hào)成員出列\(zhòng)n",m,i); </p><p>

52、;<b>　　m++; </b></p><p>　　s->next=p->next; </p><p>　　head=p->next; //重新定義head,下次循環(huán)的開始結(jié)點(diǎn).</p><p>　　free(p);// 釋放已出列的結(jié)點(diǎn). </p><p>　　n--; //人數(shù)減一.</p&

53、gt;<p>　　}while(n>0);</p><p><b>　　}</b></p><p>　　void solid()</p><p><b>　　{</b></p><p>　　int i,j,m=1;</p><p>　　int key; /

54、/ 密碼.</p><p>　　int n; //人數(shù) .</p><p>　　list *p,*s,*head;</p><p>　　head=(list *)malloc(sizeof(list)); //為頭結(jié)點(diǎn)分配空間.</p><p><b>　　p=head; </b></p><p>

55、;　　printf("輸入人的總個(gè)數(shù):\n"); </p><p>　　scanf("%d",&n); </p><p>　　printf("請(qǐng)輸入密碼:");</p><p>　　for(i=1;i<=n;i++) </p><p>　　{ scanf("%

56、d",&key);</p><p>　　printf("第%d個(gè)人的密碼:%d\n",i,key);</p><p><b>　　s=p; </b></p><p>　　p=(list *)malloc(sizeof(list)); //創(chuàng)建新的結(jié)點(diǎn).</p><p>　　s->

57、;next=p; </p><p>　　p->num=i; </p><p>　　p->code=key; </p><p>　　printf("請(qǐng)輸入密碼:");</p><p><b>　　} </b></p><p>　　p->next=head->

58、;next; </p><p><b>　　p=head; </b></p><p>　　head=head->next; </p><p>　　free(p); //釋放頭結(jié)點(diǎn).</p><p><b>　　p=head;</b></p><p><b>　

59、　do{ </b></p><p>　　printf("\n第%d號(hào)成員的密碼為:%d",p->num,p->code); //輸出鏈表.</p><p>　　p=p->next; </p><p>　　}while(p!=head); </p><p>　　printf("\n\n

60、輸入第一個(gè)報(bào)的數(shù):\n"); </p><p>　　scanf("%d",&key);</p><p>　　printf("\n出列順序?yàn)?\n"); </p><p><b>　　do </b></p><p>　　{ j=1; p=head;</p

61、><p>　　while(j<key) { </p><p><b>　　s=p; </b></p><p>　　p=p->next; </p><p><b>　　j++; </b></p><p><b>　　} //報(bào)數(shù)過程.</b><

62、;/p><p>　　i=p->num; </p><p>　　key=p->code; </p><p>　　printf("%d:第%d號(hào)成員出列\(zhòng)n",m,i); </p><p><b>　　m++;</b></p><p>　　s->next=p->

63、;next; </p><p>　　head=p->next; //重新定義head,下次循環(huán)的開始結(jié)點(diǎn).</p><p>　　free(p);// 釋放已出列的結(jié)點(diǎn). </p><p>　　n--; //人數(shù)減一.</p><p>　　}while(n>0);</p><p><b>　　}&l