數(shù)據(jù)結構課程設計--- 約瑟夫（joseph）環(huán)

1、<p>　　約瑟夫（Joseph）環(huán)</p><p><b>　　1.課程設計的目的</b></p><p>　　本次課程設計通過設計一完整的程序，可以掌握數(shù)據(jù)結構的應用、算法的編寫、類C語言的算法轉換成C程序并用TC上機調試的基本方法。應用對數(shù)據(jù)結構理論學習，通過上機實踐的方式將理論知識與實踐更好的結合起來，鞏固所學知識。</p><p

2、>　　數(shù)據(jù)結構是實踐性很強的課程，課程設計是加強學生實踐能力的一個有力手段。本次課程設計的目的就是要達到理論與實際的應用相結合學會數(shù)據(jù)的組織方法，能把現(xiàn)實世界中的實際問題在計算機內(nèi)部表現(xiàn)出來，能夠提高學生的思維能力和專業(yè)素質的提高，對學生基本程序設計素質的培養(yǎng)和為以后工作打下了堅實的基礎。</p><p>　　本次課程設計是利用利用單向循環(huán)鏈表存儲結構解決Joseph環(huán)問題，編號是1，2，……,n的n個人按

3、照順時針方向圍坐一圈，每個人只有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)上限值m,從第一個仍開始順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼作為新的m值，從他在順時針方向的下一個人開始重新從1報數(shù)，如此下去，直到所有人全部出列為止，本次課程設計將設計一個程序來求出出列順序。</p><p><b>　　2.設計方案論證</b></p><

4、p>　　2.1設計思路及方法</p><p>　　為了記錄退出的人的先后順序，采用一個順序表進行存儲。程序結束后再輸出依次退出的人的編號順序。由于只記錄各個結點的data值就可以。最后通過函數(shù)調用來輸出順序。第一步是定義結構變量結點linklist，并在該結點下定義結點的元素域:data,password，指針域:lLink和rLink。然后建立一個由n個鏈結點，有表頭結點的單向循環(huán)鏈表。并由構造函數(shù)對結點

5、賦值，由隨機函數(shù)rand()產(chǎn)生每個結點的password。由于每個結點的password是由隨機函數(shù)產(chǎn)生的，也就是每個結點的password是后知的，所以在一開始人為地指定一個結點的順序，由此結點開始報數(shù)。報password個數(shù)后，報到的那個結點被刪除，它的password被記錄下，由它的下一個結點開始逆方向報數(shù)………如此循環(huán)，直到循環(huán)鏈表里只剩下一個結點，那就是問題所求的結果。具體到問題上，還需要創(chuàng)建一個Joseph類，由構造函數(shù)來

6、初始化，輸入所有的人數(shù)，也就是表長，然后指定由第幾個人開始報數(shù)。在Joseph類中定義一個GetWinner()函數(shù)，由它來實現(xiàn)獲得最后的勝利者。并在該類中設置一個判斷語句來確定先由順時針報數(shù)并淘汰了</p><p>　　創(chuàng)建一個空單向循環(huán)鏈表，單向循環(huán)鏈表和每個結點包括三個域:Element，</p><p>　　lLink,rLink.其中element為元素域，rLink域為指向后繼

7、結點的指針，新增的lLink域用以指向前驅結點。單向鏈表帶表頭結點，并且也可以構成單向循環(huán)鏈表。此時，表頭結點的rLink，lLink分別指向雙向循環(huán)鏈表的頭結點(或表頭結點)和尾結點。</p><p>　　一個結點的lLink域的指針指向它左邊結點的后部，這并不意味著該結點的lLink域保存的仍是該左邊結點存儲塊的起始地址。在此處，指針指向某個結點任何部分都是等價的，都是指該存儲塊的起始位置。</p>

8、;<p>　　每當結點計數(shù)到某一結點時，將他的前驅結點接到他的后繼結點，然后將他的密碼值password賦給計數(shù)變量，再將此結點刪除。如此循環(huán)下去，直到最后變?yōu)榭盏膯窝h(huán)鏈表為止。</p><p>　　由于當某個人退出圓圈后，報數(shù)的工作要從下一個人開始繼續(xù)，剩下的人仍然是圍成一個圓圈的，可以使用循環(huán)表，由于退出圓圈的工作對應著表中結點的刪除操作，對于這種刪除操作頻繁的情況，選用效率較高的鏈表結構，為

9、了程序指針每一次都指向一個具體的代表一個人的結點而不需要判斷，鏈表不帶頭結點。所以，對于所有人圍成的圓圈所對應的數(shù)據(jù)結構采用一個不帶頭結點的循環(huán)鏈表來描述。設頭指針為front，front始終指向頭結點，并定義指針current記錄當前的結點。并根據(jù)具體情況移動（順逆時針）。</p><p><b>　　2.2系統(tǒng)流程圖</b></p><p><b>　　

10、圖1.系統(tǒng)流程圖</b></p><p><b>　　2.3算法設計舉例</b></p><p>　?。?）利用單向循環(huán)鏈表存儲結構模擬此過程，因為循環(huán)鏈表最后一個結點的指針域指向頭結點，整個鏈表形成一人環(huán)，剛好和題中的“n個人按照順時針方向圍坐一圈，每個人只有一個密碼（正整數(shù)）”內(nèi)容要求一致，而且，循環(huán)鏈表中任一結點出發(fā)均可找到表中其他結點，利用這一優(yōu)點

11、可較容易地找出報數(shù)的人及下一個報數(shù)的人，最后按照出列的順序用一個for語句實現(xiàn)。</p><p>　　joseph環(huán)的組成成員由密碼（password）和序號(No)組成，循環(huán)鏈表的存儲結構如下：</p><p>　　typedef struct LNode</p><p><b>　　{</b></p><p>　　i

12、nt password; //密碼</p><p>　　int No; //序號 </p><p>　　struct LNode *next; //下一成員指針</p><p>　　}member; //組成成員結構體</p><p>　　（2）定義結構體類型，其中password為密碼，No為序號，將兩者均定義為整型，LNod

13、e *next為下一成員指針，具體算法如下：</p><p>　　typedef struct LNode { int password; int No; struct LNode *next;

14、 }member; typedef int status; </p><p>　?。?）主函數(shù)模塊算法 </p><p>　　程序main中調用了CreateList_Circle函數(shù)，創(chuàng)建了循環(huán)鏈表，還調用了OutNode函數(shù)實現(xiàn)了輸出。首先定義人數(shù)n，頭指針即首員地址和遍歷指針均為空，當輸入人數(shù)小于等于0時，輸出“重新輸入”字樣，如果輸入數(shù)大

15、于0則創(chuàng)建循環(huán)鏈表，返回頭指針。當m小于等于0時也提示重新輸入，把head 附給q ，尋找出列成員，化簡m值，k從1到m-1指向出列成員，然后修改m,刪除鏈表的出列成員，成員數(shù)自減。</p><p><b>　　具體算法如下：</b></p><p>　　status main() </p><p>　　{ int n,

16、m; member *head=NULL,*q=NULL; while (n<=0) printf ("n must be positive, please enter again:\n"); if(!CreateList_Circle(&head,n)) return OVERFLO

17、W; while (m<=0) printf ("m must be positive, please enter again:\n"); p=head; ， while (n>=2) { int k; m=(m%n==0

18、)?n:m%n; </p><p>　　for (k=1;i<m;k++) p=p->next; m=p->password; OutNode(&q); n--; } return OK;

19、 } </p><p><b>　　3.設結果與分析</b></p><p><b>　　3.1需求與分析</b></p><p>　　約瑟夫環(huán)問題是一個古老的數(shù)學問題，本次課題要求用程序語言的方式解決數(shù)學問題。此問題僅使用單循環(huán)鏈表就可以很方便解決此問題</p><p>　　在建立單向循環(huán)鏈表

20、時，因為約瑟夫環(huán)的大小由輸入決定。為方便操作，我們將每個結點的數(shù)據(jù)域的值定為生成結點時的順序號和每個人持有的密碼。進行操作時，用一個指針current指向當前的結點，指針front始終指向頭結點。然后建立雙向循環(huán)鏈表，因為每個人的密碼是通過rand()函數(shù)隨機生成的，所以指定第一個人的順序號，找到結點，不斷地從鏈表中刪除鏈結點，直到鏈表剩下最后一個結點，通過一系列的循環(huán)就可以解決改進約瑟夫環(huán)問題。</p><p>

21、;　　3.2調試過程與分析</p><p>　　這次的課程設計的代碼很冗長，所以等有了解題思路后，把代碼都寫上后難免會有很多錯誤。當?shù)谝淮伟颜麄€程序寫好后運行，出現(xiàn)了很多錯誤。不過經(jīng)過一點點的改正，錯誤也慢慢地變少。這也說明做事要認真，尤其做計算機這方面工作的時候，因為計算機不容許不一點點的錯誤，有了一點小錯誤和有一個大錯誤在計算機看來都是一樣的，都不會得不到結果。有些小錯誤，比如說少了個分號，變量忘了定義，數(shù)據(jù)

22、溢出等都是些小錯誤，但也不能松懈。因為要注意的地方很多，經(jīng)過多次嘗試，問題也就自然而然的解決了，而且以后遇到這方面的問題都會覺得比較得心應手。</p><p>　　在隨機設置每個結點的password時也曾是個問題，因為我做的隨機函數(shù)一直都用不好，要不是每次隨到的都是一樣的，要么就是每次隨到的數(shù)都很大，后來通過老師的耐心講解才得以解決。</p><p>　　在調試的過程中，類的優(yōu)勢很明顯，

23、能很簡單的把問題解決，而不需要使用的其他的一些比較復雜的方法。</p><p><b>　　3.3運行結果</b></p><p>　　3.3.1運行程序結果</p><p>　　在visuar C++中運行該程序并進行調試，然后能夠正確輸出。</p><p><b>　　圖2.程序運行圖</b>&

24、lt;/p><p>　　3.3.2檢測程序的可行性</p><p>　?。?）測試數(shù)據(jù)：m的初值為20，n=7 ,7個人的密碼依次為3，1，7，2，4，7，4。</p><p>　　圖3.輸入數(shù)據(jù)結果圖</p><p>　?。?）測試數(shù)據(jù)：m的初值為20，n=7 ,7個人的密碼依次為3，1，7，2，4，7，4。運行并輸出結果。</p>

25、<p><b>　　圖4.運行結果圖</b></p><p>　　（3）輸入數(shù)據(jù)：建立輸入處理輸入數(shù)據(jù)，輸入m的初值為6，輸入每個人的密碼，建立單循環(huán)鏈表，輸出正確的序列。</p><p><b>　　圖5.運行結果圖</b></p><p>　　當程序運行的時候會出現(xiàn)如上圖所示的提示，要求使用者輸入程序中所

26、需的輸入總人數(shù)，使用者只需輸入自己所想的總人數(shù)，系統(tǒng)便會隨機產(chǎn)生每個人對應的密碼，同時隨機產(chǎn)生第一次的報數(shù)上限值。最后系統(tǒng)會給出出列的次序，最后產(chǎn)生的編號便是此次游戲的獲勝者。使用者還可按下任意鍵，進行下一次的游戲。</p><p><b>　　4.設計體會</b></p><p>　　為期一周的課程設計快結束了，通過這次數(shù)據(jù)結構課程設計，我感受最深的就是對于循環(huán)鏈表

27、的使用，可以說對循環(huán)鏈表有了比以前更進一步的認識，以前只是一知半解的，如果只給個題目自己根本不能把程序完整地編寫出來，所以這次課程設計最大的收獲就在于對循環(huán)鏈表有了一定的理解，包括其中的一系列操作，如建立一個循環(huán)鏈表，刪除鏈表中的一個結點，增加一個結點等。</p><p>　　在這次課程設計過程中需要我們一邊設計一邊探索，這這個過程當中我發(fā)現(xiàn)自己在數(shù)據(jù)結構方面知識掌握不夠深入，對一些基本概念不能很好的理解，對一些

28、數(shù)據(jù)結構不能夠熟練的進行上機實現(xiàn)，這是自己比較薄弱的。學好基礎知識是理論付諸實踐的前提，這樣理論和實踐才能充分地結合起來。在以后的學習中，我還要努力改正，充分利用上機實驗的機會提高自己。在程序的輸入的時候，因為自己對鍵盤的不熟練，代碼又很多很繁瑣，常常會產(chǎn)生放棄的念頭，從中我也感受到只有堅持到底，勝利才會出現(xiàn)。</p><p>　　課程設計是培養(yǎng)我們綜合運用所學知識，發(fā)現(xiàn)、提出、分析和解決實際問題，鍛煉實踐能力的

29、重要環(huán)節(jié),是對我們實際工作能力的具體訓練和考察過程.在調試程序的時候我也有所體會，雖然約瑟夫環(huán)問題不是很難，但調試的時候還是會出現(xiàn)很多錯誤，因此我們不能認為容易就不認真對待。在以后的學習中，要能不斷發(fā)現(xiàn)問題，提出問題，解決問題，從不足之處出發(fā)，在不斷學習中提高自己。</p><p><b>　　參考文獻</b></p><p>　　[1]嚴蔚敏，吳偉民.數(shù)據(jù)結構（C語

30、言版）[M].北京：清華大學出版社，2007.4：144-149</p><p>　　[2]蘇仕華.數(shù)據(jù)結構與算分析[M].安徽：中國科學技術大學出版社，2004.1：94-98</p><p>　　[3]朱若愚.數(shù)據(jù)結構[M].北京:電子郵電出版社,2006.1:41-65</p><p>　　[4]徐孝凱.數(shù)據(jù)結構簡明教程.北京:清華大學出版社,2006.4:1

31、02-115</p><p>　　[5]耿國華.數(shù)據(jù)結構-C語言描述[M]北京:高等教育出版社,2005.1:182-187</p><p>　　[6]孫輝吳,潤秀語.C言程序設計教程[M]北京:北京郵電出版社,2004.10:166-172</p><p>　　[7]許秀林,董楊琴.程序設計基礎教程（C語言與數(shù)據(jù)結構）[M]北京:中國電力出版社,2005.9:25

32、0-256</p><p>　　[8]王曙燕.C語言課程設計[M]北京:科學出版社,2005.2:159-165</p><p><b>　　附錄：源代碼</b></p><p>　　typedef struct LNode</p><p><b>　　{</b></p><p&

33、gt;　　int password; //密碼</p><p>　　int No; //序號 </p><p>　　struct LNode *next; //下一成員指針</p><p>　　}member; //組成成員結構體</p><p>　　typedef int status;</p><p>

34、;　　#define OVERFLOW -2 </p><p>　　#define OK 1 </p><p>　　#define ERROR 0</p><p>　　#include <stdio.h></p><p>　　#include <stdlib.h></p><p&g

35、t;　　status CreateList_Circle(member **,int);</p><p>　　status DeleteNode(member **);</p><p>　　status main()</p><p><b>　　{</b></p><p><b>　　int n,m;</

36、b></p><p>　　member *head=NULL,*p=NULL; //頭指針即首成員地址，遍歷指針p</p><p>　　printf ("請輸入人數(shù):\n");</p><p>　　scanf ("%d",&n); //總成員數(shù)</p><p>　　while (n&l

37、t;=0)</p><p><b>　　{</b></p><p>　　printf ("n must be positive, please enter again:\n");</p><p>　　scanf ("%d",&n);</p><p><b>　　}

38、</b></p><p>　　if(!CreateList_Circle(&head,n)) //創(chuàng)建循環(huán)鏈表，返回頭指針head</p><p>　　return OVERFLOW; </p><p>　　printf ("請輸入m的值:\n");</p><p>　　scanf ("%d

39、",&m); //初始值m</p><p>　　while (m<=0)</p><p><b>　　{</b></p><p>　　printf ("m must be positive, please enter again:\n");</p><p>　　scanf (

40、"%d",&m);</p><p><b>　　} </b></p><p>　　printf ("\nThe order is:\n");</p><p><b>　　p=head;</b></p><p>　　while (n>=2) //

41、尋找出列成員</p><p><b>　　{</b></p><p><b>　　int i;</b></p><p>　　m=(m%n==0)?n:m%n; //化簡m值</p><p>　　for (i=1;i<m;i++) </p><p>　　p=p->

42、;next; //p指向出列成員</p><p>　　printf ("%d\n",p->No); //輸出出列成員序號</p><p>　　m=p->password; //修改m</p><p>　　DeleteNode(&p); //刪除鏈表中的出列成員</p><p>　　n--; /

43、/成員數(shù)自減</p><p><b>　　}</b></p><p>　　printf ("%d\n",p->No); //輸出最后一個成員序號</p><p>　　return OK;</p><p><b>　　}</b></p><p>　　

44、status CreateList_Circle(member **p_head,int n)</p><p>　　{//此算法創(chuàng)建一個無頭結點的循環(huán)鏈表，結點數(shù)n,*p_head返回鏈表頭指針即首結點地址</p><p><b>　　int i;</b></p><p>　　member *tail,*p;</p><p&

45、gt;　　*p_head=(member *)malloc(sizeof(member));</p><p>　　if (!(*p_head)) return OVERFLOW;</p><p>　　(*p_head)->No=1; //儲存成員一序號</p><p>　　printf ("請輸入密碼. 1:\n"); </p&g

46、t;<p>　　scanf ("%d",&(*p_head)->password); //儲存成員一密碼</p><p>　　tail=*p_head;</p><p>　　tail->next=NULL;</p><p>　　for (i=2;i<n+1;i++)</p><p>

47、;<b>　　{</b></p><p>　　p=(member *)malloc(sizeof(member));</p><p>　　if (!p) return OVERFLOW;</p><p>　　p->No=i; //儲存成員序號</p><p>　　printf ("請輸入密碼. %d:\

48、n",i);</p><p>　　scanf("%d",&(p->password)); //儲存成員密碼</p><p>　　tail->next=p;</p><p><b>　　tail=p;</b></p><p><b>　　}</b>&

49、lt;/p><p>　　tail->next=*p_head;</p><p>　　return OK;</p><p><b>　　}</b></p><p>　　status DeleteNode(member **pp)</p><p><b>　　{</b><

50、/p><p>　　//此算法刪除鏈表中的結點*pp,操作實質是將*pp下一結點復制到*pp后將其free</p><p>　　member *temp;</p><p>　　(*pp)->password=((*pp)->next)->password;</p><p>　　(*pp)->No=((*pp)->nex