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

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

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

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

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

5、de->num值，將該結(jié)點中的data中數(shù)作為新密碼開始下一個步的開始，將該結(jié)點從鏈表中刪除，并釋放該結(jié)點的空間。重復(fù)此過程，直到剩下最后一個結(jié)點，就直接將該結(jié)點中的num值輸出，刪除該結(jié)點，并釋放該結(jié)點的空間。輸出的num值即為約瑟夫中人的編號。</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、個結(jié)構(gòu)體用來儲存學(xué)生的編號和所攜帶的密碼</p><p>　　for(i=1;i<=n;i++)</p><p><b>　　{</b></p><p>　　printf("輸入第%d號同學(xué)的密碼:",i);</p><p>　　scanf("%d",&j);//輸入

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

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

10、過程中給結(jié)點的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ù)結(jié)束</p><p>

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

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

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

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

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

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

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

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

22、lt;/p><p>　　scanf("%d",&m);//輸入初始報數(shù)上限</p><p>　　if(m<=0)printf("輸入錯誤");//初始報數(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號同學(xué)的密碼:",i);</p><p>　　scanf("%d",&j);//輸入學(xué)生所帶密碼</p><p>　　p1->next=(listnode*)mall

24、oc(sizeof(listnode));//建立一個新的空間，并將它的地址賦給p1->next</p><p>　　p1=p1->next;</p><p>　　p1->data=j;</p><p>　　p1->num=i;//對結(jié)點的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ù)結(jié)束</p><p><b>　　{</b></p><p>　　p1=p1->next;</p><p><b>　　k++;</b></p><p>　　}//報數(shù)過程中將指針p1指向下一位</p><p>　　p2=p1-&

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

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