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

1、<p><b>　　數(shù)學(xué)與計(jì)算機(jī)學(xué)院</b></p><p><b>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)</b></p><p><b>　　設(shè)計(jì)題目：約瑟夫環(huán)</b></p><p><b>　　一．選題背景：</b></p><p>　　題目：約瑟夫環(huán)問

2、題描述：編號(hào)為1,2，…..，n的n個(gè)人按順時(shí)針方向圍坐圈，每個(gè)人持有一個(gè)密碼（正整數(shù)）。一開始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m，從第一個(gè)人開始按順時(shí)針方向自1開始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針方向上的下一個(gè)人開始重新重新從1報(bào)數(shù)，如此下去，直至所有人全部出列為止?；疽螅孩?建立模型，確定存儲(chǔ)結(jié)構(gòu)； ⑵ 對(duì)任意 n個(gè)人，密碼為 m ，實(shí)現(xiàn)約瑟夫環(huán)問題；⑶ 出圈的順序可以依次輸出

3、，也可以用一個(gè)數(shù)組存儲(chǔ)。設(shè)計(jì)指導(dǎo)思想：首先，設(shè)計(jì)實(shí)現(xiàn)約瑟夫環(huán)問題的存儲(chǔ)結(jié)構(gòu)。由于約瑟夫環(huán)問題本身具有循環(huán)性質(zhì)，考慮采用循環(huán)鏈表，為了統(tǒng)一對(duì)表中任意結(jié)點(diǎn)的操作，循環(huán)鏈表不帶頭結(jié)點(diǎn)。   其次，建立一個(gè)不帶頭結(jié)點(diǎn)的循環(huán)鏈表并由頭指針 first 指示。 最后，設(shè)計(jì)約瑟夫環(huán)問題的算法。下面給出偽代碼描述，操作示意圖如圖 2-1 所示。</p><p><b>　　二．方案論證：<

4、/b></p><p>　　本方案通過建立單循環(huán)鏈表模擬了約瑟夫問題；首先，建立一個(gè)結(jié)構(gòu)體node，然后給他開辟一個(gè)儲(chǔ)存空間；利用頭指針head標(biāo)記鏈表，利用尾指針向后移將建立的結(jié)點(diǎn)連接成我們需要的單循環(huán)鏈表，過程如下：約瑟夫問題中的人數(shù)個(gè)數(shù)即為鏈表的長(zhǎng)度，鏈表中node->num 編號(hào)n，node->data為每個(gè)人的密碼。建立單循環(huán)鏈表后，通過初始報(bào)數(shù)上限找到出列的結(jié)點(diǎn)，輸出該結(jié)點(diǎn)的no

5、de->num值，將該結(jié)點(diǎn)中的data中數(shù)作為新密碼開始下一個(gè)步的開始，將該結(jié)點(diǎn)從鏈表中刪除，并釋放該結(jié)點(diǎn)的空間。重復(fù)此過程，直到剩下最后一個(gè)結(jié)點(diǎn)，就直接將該結(jié)點(diǎn)中的num值輸出，刪除該結(jié)點(diǎn)，并釋放該結(jié)點(diǎn)的空間。輸出的num值即為約瑟夫中人的編號(hào)。</p><p><b>　　三．過程論述：</b></p><p>　　typedef struct node&l

6、t;/p><p><b>　　{</b></p><p><b>　　int data;</b></p><p><b>　　int num;</b></p><p>　　struct node *next;</p><p>　　}listnode;定義一

7、個(gè)結(jié)構(gòu)體用來儲(chǔ)存學(xué)生的編號(hào)和所攜帶的密碼</p><p>　　for(i=1;i<=n;i++)</p><p><b>　　{</b></p><p>　　printf("輸入第%d號(hào)同學(xué)的密碼:",i);</p><p>　　scanf("%d",&j);//輸入

8、學(xué)生所帶密碼</p><p>　　p1->next=(listnode*)malloc(sizeof(listnode));//建立一個(gè)新的空間，并將它的地址賦給p1->next</p><p>　　p1=p1->next;</p><p>　　p1->data=j;</p><p>　　p1->num=i;//

9、對(duì)結(jié)點(diǎn)的num和data成員賦值</p><p>　　p1->next=head->next;//構(gòu)成單循環(huán)鏈表</p><p>　　}定義指針p1，然后建立一個(gè)新結(jié)點(diǎn)并將p1->next指向它的地址，然后將這個(gè)地址賦給p1，最后將head->next賦給p1->next,構(gòu)成一個(gè)單循環(huán)鏈表，并不斷在尾部插入新的結(jié)點(diǎn)，直至所有人都進(jìn)入循環(huán)鏈表中，而且在循環(huán)的

10、過程中給結(jié)點(diǎn)的num和data成員賦值</p><p><b>　　do</b></p><p><b>　　{</b></p><p><b>　　k=1;</b></p><p>　　while(k!=m)//當(dāng)k==m時(shí)一輪報(bào)數(shù)結(jié)束</p><p>

11、;<b>　　{</b></p><p>　　p1=p1->next;</p><p><b>　　k++;</b></p><p>　　}//報(bào)數(shù)過程中將指針p1指向下一位</p><p>　　p2=p1->next;</p><p>　　p1->next

12、=p2->next;//將報(bào)m的人的結(jié)點(diǎn)從鏈表中刪去</p><p>　　printf("編號(hào)為%d的人出列，他的密碼%d作為新的m值\n",p2->num,p2->data);//報(bào)數(shù)為m的人出列</p><p>　　m=p2->data;//報(bào)數(shù)為m的人的密碼作為新的m值</p><p>　　free(p2);//釋放

13、報(bào)m的人的結(jié)點(diǎn)</p><p>　　}while(p1->next!=p1);//當(dāng)p1->next指向的地址是它自己的地址，所有報(bào)數(shù)結(jié)束定義指針p1用以循環(huán)鏈表，定義變量k計(jì)數(shù)，指針p1每移動(dòng)一次，k加1，直到k==m時(shí)，輸出指針p1所指向的節(jié)點(diǎn)序號(hào)，也就是令這個(gè)“人”出列，p2指向該節(jié)點(diǎn)上一節(jié)點(diǎn)，令上一節(jié)點(diǎn)next域指向該節(jié)點(diǎn)下一節(jié)點(diǎn)，然后刪除該節(jié)點(diǎn)，令頭節(jié)點(diǎn)p1指向該節(jié)點(diǎn)下一節(jié)點(diǎn)作為再次報(bào)數(shù)初

14、始“人”，再令k歸1，繼續(xù)循環(huán)。知道p1->next= =p1時(shí)，表示所有“人”出列完畢，刪除最后的節(jié)點(diǎn)后跳出循環(huán)</p><p><b>　　四．結(jié)果分析：</b></p><p>　　測(cè)試數(shù)據(jù)：n=4, 4個(gè)人的密碼依次為4, 3，8, 6, 首先m=6輸出結(jié)果：</p><p>　　測(cè)試數(shù)據(jù)：n=7，7個(gè)人的密碼依次為3，1，

15、7，2，48，4，首先m=20</p><p>　　輸出結(jié)果： </p><p><b>　　五．課程設(shè)計(jì)總結(jié)：</b></p><p>　　為期一周的課程設(shè)計(jì)快結(jié)束了，通過這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)，我感受最深的就是對(duì)于循環(huán)鏈表的使用，可以說對(duì)循環(huán)鏈表有了比以前更進(jìn)一步的認(rèn)識(shí)，以前只是一知半解的，如果只給個(gè)

16、題目自己根本不能把程序完整地編寫出來，所以這次課程設(shè)計(jì)最大的收獲就在于對(duì)循環(huán)鏈表有了一定的理解，包括其中的一系列操作，如建立一個(gè)循環(huán)鏈表，刪除鏈表中的一個(gè)結(jié)點(diǎn)，增加一個(gè)結(jié)點(diǎn)等。</p><p>　　在這次課程設(shè)計(jì)過程中需要我們一邊設(shè)計(jì)一邊探索，這這個(gè)過程當(dāng)中我發(fā)現(xiàn)自己在數(shù)據(jù)結(jié)構(gòu)方面知識(shí)掌握不夠深入，對(duì)一些基本概念不能很好的理解，對(duì)一些數(shù)據(jù)結(jié)構(gòu)不能夠熟練的進(jìn)行上機(jī)實(shí)現(xiàn)，這是自己比較薄弱的。學(xué)好基礎(chǔ)知識(shí)是理論付諸實(shí)踐

17、的前提，這樣理論和實(shí)踐才能充分地結(jié)合起來。在以后的學(xué)習(xí)中，我還要努力改正，充分利用上機(jī)實(shí)驗(yàn)的機(jī)會(huì)提高自己。在程序的輸入的時(shí)候，因?yàn)樽约簩?duì)鍵盤的不熟練，代碼又很多很繁瑣，常常會(huì)產(chǎn)生放棄的念頭，從中我也感受到只有堅(jiān)持到底，勝利才會(huì)出現(xiàn)。</p><p>　　在調(diào)試程序的時(shí)候我也有所體會(huì)，雖然約瑟夫環(huán)問題不是很難，但調(diào)試的時(shí)候還是會(huì)出現(xiàn)很多錯(cuò)誤，因此我們不能認(rèn)為容易就不認(rèn)真對(duì)待。在以后的學(xué)習(xí)中，要能不斷發(fā)現(xiàn)問題，提出問

18、題，解決問題，從不足之處出發(fā)，在不斷學(xué)習(xí)中提高自己。</p><p>　　六．附錄：完整程序代碼</p><p>　　#include<stdio.h></p><p>　　#include<stdlib.h></p><p>　　typedef struct node</p><p><

19、b>　　{</b></p><p><b>　　int data;</b></p><p><b>　　int num;</b></p><p>　　struct node *next;</p><p>　　}listnode;</p><p>　　type

20、def listnode *linklist;</p><p>　　void main()</p><p><b>　　{</b></p><p>　　int n,m,i,j,k;</p><p>　　linklist head=(listnode*)malloc(sizeof(listnode));//開辟一個(gè)空間，

21、并將它的起始地址賦給頭指針head</p><p>　　listnode *p1,*p2;</p><p>　　printf("輸入總?cè)藬?shù):");</p><p>　　scanf("%d",&n);//輸入總?cè)藬?shù)</p><p>　　printf("輸入報(bào)數(shù)上限m:");&

22、lt;/p><p>　　scanf("%d",&m);//輸入初始報(bào)數(shù)上限</p><p>　　if(m<=0)printf("輸入錯(cuò)誤");//初始報(bào)數(shù)上限必須大于0</p><p>　　p1=head;//將頭指針head所指地址賦給p1</p><p>　　for(i=1;i<

23、=n;i++)</p><p><b>　　{</b></p><p>　　printf("輸入第%d號(hào)同學(xué)的密碼:",i);</p><p>　　scanf("%d",&j);//輸入學(xué)生所帶密碼</p><p>　　p1->next=(listnode*)mall

24、oc(sizeof(listnode));//建立一個(gè)新的空間，并將它的地址賦給p1->next</p><p>　　p1=p1->next;</p><p>　　p1->data=j;</p><p>　　p1->num=i;//對(duì)結(jié)點(diǎn)的num和data成員賦值</p><p>　　p1->next=head-

25、>next;//構(gòu)成單循環(huán)鏈表</p><p><b>　　}</b></p><p><b>　　do</b></p><p><b>　　{</b></p><p><b>　　k=1;</b></p><p>　　whi

26、le(k!=m)//當(dāng)k==m時(shí)一輪報(bào)數(shù)結(jié)束</p><p><b>　　{</b></p><p>　　p1=p1->next;</p><p><b>　　k++;</b></p><p>　　}//報(bào)數(shù)過程中將指針p1指向下一位</p><p>　　p2=p1-&

27、gt;next;</p><p>　　p1->next=p2->next;//將報(bào)m的人的結(jié)點(diǎn)從鏈表中刪去</p><p>　　printf("編號(hào)為%d的人出列，他的密碼%d作為新的m值\n",p2->num,p2->data);//報(bào)數(shù)為m的人出列</p><p>　　m=p2->data;//報(bào)數(shù)為m的人的密碼

28、作為新的m值</p><p>　　free(p2);//釋放報(bào)m的人的結(jié)點(diǎn)</p><p>　　}while(p1->next!=p1);//當(dāng)p1->next指向的地址是它自己的地址，所有報(bào)數(shù)結(jié)束</p><p>　　printf("編號(hào)為%d的人出列，至此所有人出列完畢\n",p1->num);//至此所有人出列完畢<