數據結構約瑟夫環(huán)的課程設計報告

1、<p><b>　　數學與計算機學院</b></p><p><b>　　數據結構課程設計</b></p><p><b>　　設計題目：約瑟夫環(huán)</b></p><p><b>　　一．選題背景：</b></p><p>　　題目：約瑟夫環(huán)問

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

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

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

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

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

10、過程中給結點的num和data成員賦值</p><p><b>　　do</b></p><p><b>　　{</b></p><p><b>　　k=1;</b></p><p>　　while(k!=m)//當k==m時一輪報數結束</p><p>

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

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

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

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

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

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

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

18、題，解決問題，從不足之處出發(fā)，在不斷學習中提高自己。</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("輸入總人數:");</p><p>　　scanf("%d",&n);//輸入總人數</p><p>　　printf("輸入報數上限m:");&

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

23、=n;i++)</p><p><b>　　{</b></p><p>　　printf("輸入第%d號同學的密碼:",i);</p><p>　　scanf("%d",&j);//輸入學生所帶密碼</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;//對結點的num和data成員賦值</p><p>　　p1->next=head-

25、>next;//構成單循環(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)//當k==m時一輪報數結束</p><p><b>　　{</b></p><p>　　p1=p1->next;</p><p><b>　　k++;</b></p><p>　　}//報數過程中將指針p1指向下一位</p><p>　　p2=p1-&

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

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