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

1、<p><b>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計</b></p><p>　　題 目： 排序系統(tǒng)設(shè)計（約瑟夫環(huán)問題） </p><p>　　班 級： </p><p>　　姓 名： 學 號 <

2、;/p><p>　　同組人姓名： </p><p>　　起 迄 日 期: 2010年12月26日 　　　　 　　　　　　　　　 </p><p>　　課程設(shè)計地點: E3-A513　 　　　　　　　　　　　　　　 </p><p>　　指導教師：

3、 </p><p>　　完成日期：2011年12月</p><p><b>　　摘要：</b></p><p>　　功能：設(shè)編號為1，2，3，……，n的n(n>0)個人按順時針方向圍坐一圈，每個人持有一個正整數(shù)密碼。開始時任選一個正整數(shù)做為報數(shù)上限m，從第一個人開始順時針方向自1起順序報

4、數(shù)，報到m是停止報數(shù)，報m的人出列，將他的密碼作為新的m值，從他的下一個人開始重新從1報數(shù)。如此下去，直到所有人全部出列為止。令n最大值取30。要求設(shè)計一個程序模擬此過程，求出出列編號序列。</p><p><b>　　目 錄</b></p><p><b>　　1需求分析2</b></p><p><b>

5、;　　1.1功能分析2</b></p><p><b>　　1.2設(shè)計平臺2</b></p><p><b>　　2概要設(shè)計2</b></p><p>　　2.1創(chuàng)建循環(huán)單鏈表create()2</p><p>　　2.2輸出查找search()3</p><

6、;p>　　2.3異常處理及屏幕清理clean()3</p><p>　　3程序設(shè)計主要流程4</p><p>　　3.1程序?qū)崿F(xiàn)流程圖4</p><p>　　4調(diào)試與操作說明4</p><p><b>　　4.1調(diào)試情況4</b></p><p><b>　　4.2操作說

7、明5</b></p><p><b>　　總 結(jié)7</b></p><p><b>　　致 謝8</b></p><p><b>　　附 錄9</b></p><p>　　參 考 文 獻13</p><p><b>

8、;　　==1==</b></p><p><b>　　1． 需求分析</b></p><p><b>　　1.1 功能分析 </b></p><p>　　本次選做的課程設(shè)計是改進約瑟夫(Joseph)環(huán)問題。我選擇了和羅源兩個人來完成本次課程設(shè)計的作業(yè)。約瑟夫環(huán)問題是一個古老的數(shù)學問題，本次課題要求用程序語言的

9、方式解決數(shù)學問題。此問題僅使用單循環(huán)鏈表就可以解決此問題。</p><p>　　在建立單向循環(huán)鏈表時，因為約瑟夫環(huán)的大小由輸入決定。為方便操作，我們將每個結(jié)點的數(shù)據(jù)域的值定為生成結(jié)點時的順序號和每個人持有的密碼。進行操作時，用一個指針r指向當前的結(jié)點，指針H指向頭結(jié)點。然后建立單向循環(huán)鏈表，因為每個人的密碼是通過scanf()函數(shù)輸入隨機生成的，所以指定第一個人的順序號，找到結(jié)點，不斷地從鏈表中刪除鏈結(jié)點，直到鏈

10、表剩下最后一個結(jié)點，通過一系列的循環(huán)就可以解決改進約瑟夫環(huán)問題。</p><p><b>　　1.2設(shè)計平臺</b></p><p>　　Windows2007操作系統(tǒng)；Microsoft Visual C++ 6.0；</p><p><b>　　2．概要設(shè)計</b></p><p>　　已知n個

11、人（以編號1，2，3...n分別表示）圍成一圈。從編號為1的人開始報數(shù)，數(shù)到m的那個人出列；他的下一個人又從1開始報數(shù)，數(shù)到m的那個人又出列；依此規(guī)律重復下去，直到一圈的人全部出列。這個就是約瑟夫環(huán)問題的實際場景，有一種是要通過輸入n,m,k三個正整數(shù)，來求出列的序列。這個問題采用的是典型的循環(huán)鏈表的數(shù)據(jù)結(jié)構(gòu)，就是將一個鏈表的尾元素指針指向隊首元素。r->next=H。解決問題的核心步驟：首先建立一個具有n個鏈結(jié)點，無頭結(jié)點的循環(huán)

12、鏈表。然后確定第1個報數(shù)人的位置。最后不斷地從鏈表中刪除鏈結(jié)點，直到鏈表為空。</p><p>　　本課程設(shè)計主要采用了結(jié)構(gòu)體，程序中包含了兩個只要函數(shù)：create（）；search（）；</p><p>　　2.1 創(chuàng)建循環(huán)單鏈表create（）</p><p>　　dtypeef struct Node 定義一個結(jié)構(gòu)體，m為密碼，n為序號（總?cè)藬?shù)）。</

13、p><p><b>　　==2==</b></p><p>　　定義H=NULL創(chuàng)建一個沒有頭結(jié)點的單向循環(huán)鏈表，并采for(i=1;i<=z;i++)</p><p>　　隨機輸入密碼，在每次輸入密碼后，自動生成新的鏈表存儲空間s=(Linklist)malloc(sizeof(Node));當前指針r后移，并釋放r的值。直到r->=

14、H時創(chuàng)建單向循環(huán)鏈表成功，并返回H的值作為總?cè)藬?shù)。</p><p>　　單項循環(huán)鏈表示意圖：</p><p>　　每當結(jié)點計數(shù)到某一結(jié)點時，將他的前驅(qū)結(jié)點接到他的后繼結(jié)點，然后將他的密碼值password賦給計數(shù)變量，再將此結(jié)點刪除。如此循環(huán)下去，直到最后變?yōu)榭盏膯窝h(huán)鏈表為止。</p><p>　　2.2 輸出查找search（）</p><p

15、>　　用循環(huán)鏈表實現(xiàn)報數(shù)問題,利用count累計報數(shù)人數(shù)，num為標記出列人數(shù)計數(shù)器。當隨機輸入初始密碼m0時即從第一個人報起，到第m時取出m并顯示，在釋放該指針指向m的值，從刪除位的下一個人開始報起，按該人的密碼為m實現(xiàn)對總個鏈表的輸出，指針沒報數(shù)一次則后移一個節(jié)點。</p><p>　　實現(xiàn)代碼：pre->next=p->next;printf("%d ",p->

16、;n);m0=p->m;free(p); p=pre->next;</p><p>　　2.3異常處理及屏幕清理clean() </p><p>　　system("cls"); 對上次輸入的及運行結(jié)果是否進行屏幕清理工作。使程序運行界面不至于太過混亂，也可以將第二次的實驗結(jié)果和先前的實驗結(jié)果進行比較從而可以發(fā)現(xiàn)程序是否出現(xiàn)運行錯誤，便于檢查和修改。&l

17、t;/p><p><b>　　==3==</b></p><p>　　3. 程序設(shè)計主要流程</p><p>　　3.1 程序?qū)崿F(xiàn)流程圖（圖3-1）</p><p>　　圖3-1 程序?qū)崿F(xiàn)流程圖 </p><p><b>　　4．調(diào)試與操作說明</b></p>

18、<p><b>　　4.1調(diào)試情況</b></p><p>　　這次的課程設(shè)計的代碼很冗長，所以等有了解題思路后，把代碼都寫上后難免會有很多錯誤。當?shù)谝淮伟颜麄€程序?qū)懞煤筮\行，出現(xiàn)了很多錯誤。如賦值語句H=NULL沒有定義，從而形成帶空頭結(jié)點的單鏈表，以及在操作r指針后移找出m時，沒對r當時的值進行釋放從而導致下個輸出出現(xiàn)錯誤。不過經(jīng)過一點點的改正，錯誤也慢慢地變少。這也說明做事要

19、認真，尤其做計算機這方面工作的時候，因為計算機不容許不一點點的錯誤，有了一點小錯誤和有一個大錯誤在計算機看來都是一樣的，都不會得不到結(jié)果。有些小錯誤，比如說少了個分號，變量忘了定義，數(shù)據(jù)溢出等都是些小錯誤，但也不能松懈。因為要注意的地方很多，經(jīng)過多次嘗試，問題也就自然而然的解決了，而且以后遇到這方面的問題都會覺得比較得心應(yīng)手。</p><p>　　在調(diào)試的過程中，結(jié)構(gòu)體的優(yōu)勢很明顯，能很簡單的把問題解決，而不需要

20、使用的其他的一些比較復雜的方法。</p><p><b>　　==4==</b></p><p><b>　　4.2操作說明</b></p><p>　　生成界面如圖4-1，4-2，4-3,4-4,4-5所示；</p><p><b>　　圖 4-1 主菜單</b></p

21、><p>　　圖4-2輸入約瑟夫環(huán)</p><p><b>　　==5==</b></p><p>　　當程序運行的時候會出現(xiàn)如上圖所示的提示，要求使用者輸入程序中所需的輸入總?cè)藬?shù)，使用者只需輸入自己所想的總?cè)藬?shù)，便可以隨機輸入每個人對應(yīng)的密碼。最后系統(tǒng)會給出出列的次序。使用者還可進行選擇是否記錄上次數(shù)據(jù)，進行下一次的操作。</p>

22、<p>　　圖4-3顯示約瑟夫環(huán)問題</p><p><b>　　圖4-4退出程序</b></p><p><b>　　==6==</b></p><p>　　圖4-5 當輸入人數(shù)超過最大數(shù)</p><p><b>　　總 結(jié)</b></p>&l

23、t;p>　　為期一周的課程設(shè)計快結(jié)束了，通過這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計，我感受最深的就是對于循環(huán)鏈表的使用，可以說對循環(huán)鏈表有了比以前更進一步的認識，以前只是一知半解的，如果只給個題目自己根本不能把程序完整地編寫出來，所以這次課程設(shè)計最大的收獲就在于對循環(huán)鏈表有了一定的理解，包括其中的一系列操作，如建立一個循環(huán)鏈表，刪除鏈表中的一個結(jié)點，增加一個結(jié)點等。</p><p>　　在這次課程設(shè)計過程中需要我們一邊設(shè)計一

24、邊探索，這這個過程當中我發(fā)現(xiàn)自己在數(shù)據(jù)結(jié)構(gòu)方面知識掌握不夠深入，對一些基本概念不能很好的理解，對一些數(shù)據(jù)結(jié)構(gòu)不能夠熟練的進行上機實現(xiàn)，這是自己比較薄弱的。學好基礎(chǔ)知識是理論付諸實踐的前提，這樣理論和實踐才能充分地結(jié)合起來。在以后的學習中，我還要努力改正，充分利用上機實驗的機會提高自己。在程序的輸入的時候，因為自己對鍵盤的不熟練，代碼又很多很繁瑣，常常會產(chǎn)生放棄的念頭，從中我也</p><p><b>　

25、　=7==</b></p><p>　　感受到只有堅持到底，勝利才會出現(xiàn)。</p><p>　　在調(diào)試程序的時候我也有所體會，雖然約瑟夫環(huán)問題不是很難，但調(diào)試的時候還是會出現(xiàn)很多錯誤，因此我們不能認為容易就不認真對待。在以后的學習中，要能不斷發(fā)現(xiàn)問題，提出問題，解決問題，從不足之處出發(fā)，在不斷學習中提高自己。 </p><p><b>　　致

26、謝</b></p><p>　　這次的課程設(shè)計，我們兩人一個小組去完成我們自己的課程.，讓我們有機會貼近現(xiàn)實，感受成功的喜悅；其次要感謝實驗機房的老師提供優(yōu)良的實驗設(shè)備供我們做實驗，正是這種良好的實驗環(huán)境讓我們整個實驗過程心情都非常愉快。再次要感謝指導老師們的辛勤指導，每當我們遇到疑難問題時，是他們一次次不厭其煩的解釋和悉心的指導，我們才能闖過一個個難關(guān)，到達勝利的彼岸，是他們給我們提供了一次寶貴的

27、檢驗自己機會。只有在真正實戰(zhàn)的時候才會發(fā)現(xiàn)書到用時方恨少的真諦。有時感覺自己那么一次次舉手請教，可問題又那么幼稚簡單。老師是那么的耐心與不厭其煩，直到我們點頭說懂得的時候老師才離開。。最后也要感謝同學們的幫助，感謝所有在我課程設(shè)計過程中幫助過我的人！</p><p><b>　　==8==</b></p><p><b>　　附 錄</b>

28、</p><p>　　#include <stdio.h></p><p>　　#include <malloc.h></p><p>　　#include<conio.h></p><p>　　#include <stdlib.h></p><p>　　#include

29、<ctime></p><p>　　#define NULL 0</p><p>　　typedef struct Node</p><p><b>　　{ </b></p><p>　　int m;//密碼</p><p>　　int n;//序號</p><p&

30、gt;　　struct Node *next;</p><p>　　}Node,*Linklist;</p><p>　　Linklist create(int z) //生成循環(huán)單鏈表并返回,z為總?cè)藬?shù)</p><p><b>　　{ </b></p><p><b>　　int i,mm;</b&g

31、t;</p><p>　　Linklist H,r,s;</p><p><b>　　H=NULL;</b></p><p>　　printf("Output the code:");</p><p>　　for(i=1;i<=z;i++)</p><p><b&g

32、t;　　{ </b></p><p>　　printf("\ninput cipher=");</p><p>　　scanf("%d",&mm);</p><p>　　s=(Linklist)malloc(sizeof(Node));</p><p><b>　　s-&

33、gt;n=i;</b></p><p><b>　　s->m=mm;</b></p><p>　　printf("%d號的密碼%d",i,s->m);</p><p>　　if(H==NULL)//從鏈表的第一個節(jié)點插入</p><p><b>　　{ </

34、b></p><p><b>　　H=s;</b></p><p><b>　　r=H;</b></p><p><b>　　}</b></p><p>　　else//鏈表的其余節(jié)點插入</p><p><b>　　{ </b&

35、gt;</p><p>　　r->next=s;</p><p><b>　　r=s;//r后移</b></p><p><b>　　}</b></p><p><b>　　}//for結(jié)束</b></p><p>　　r->next=H;/

36、*生成循環(huán)單鏈表*/</p><p><b>　　==9==</b></p><p><b>　　return H;</b></p><p><b>　　}</b></p><p>　　void search(Linklist H,int m0,int z)//用循環(huán)鏈表實現(xiàn)報

37、數(shù)問題</p><p>　　{ int count=1;//count為累計報數(shù)人數(shù)計數(shù)器</p><p>　　int num=0;//num為標記出列人數(shù)計數(shù)器</p><p>　　Linklist pre,p;</p><p><b>　　p=H;</b></p><p>　　printf(&

38、quot;出列的順序為:");</p><p>　　while(num<z)</p><p><b>　　{ </b></p><p><b>　　do{</b></p><p><b>　　count++;</b></p><p>&

39、lt;b>　　pre=p;</b></p><p>　　p=p->next;</p><p><b>　　}</b></p><p>　　while(count<m0);</p><p>　　pre->next=p->next;</p><p>　　pri

40、ntf("%d ",p->n);</p><p><b>　　m0=p->m;</b></p><p><b>　　free(p);</b></p><p>　　p=pre->next;</p><p><b>　　count=1;</b>

41、;</p><p><b>　　num++;</b></p><p>　　}//while結(jié)束</p><p><b>　　}</b></p><p>　　void clean()</p><p><b>　　{</b></p><p

42、>　　int system(const char *string);</p><p>　　int inquiry;</p><p>　　printf("請問需要清除上一次操作記錄嗎（1.清屏/2.不清屏）...?\n");</p><p>　　scanf("%d",&inquiry);</p>&

43、lt;p>　　if(inquiry ==1)</p><p>　　system("cls");</p><p><b>　　}</b></p><p>　　void text()</p><p><b>　　{</b></p><p>　　int

44、 m0,z,i, choose,k=1; //k用來阻止第一次進入程序清屏操作</p><p>　　Linklist H; </p><p>　　bool chooseFlag=false;</p><p><b>　　while(1)</b></p><p><b>　　{</b></p&

45、gt;<p><b>　　==10==</b></p><p><b>　　if(k!=1)</b></p><p><b>　　clean();</b></p><p><b>　　k++;</b></p><p>　　while(!cho

46、oseFlag)</p><p><b>　　{</b></p><p>　　printf(" ……………………歡迎進入約瑟夫環(huán)問題系統(tǒng)…………………… \n");</p><p>　　printf(" * 1.輸入約瑟夫環(huán)數(shù)據(jù)

47、 * \n");</p><p>　　printf(" * 2.什么是約瑟夫環(huán) * \n");</p><p>　　printf(" * 3.退出系統(tǒng) * \n");printf(" ....................

48、.................................... \n");</p><p>　　printf("請輸入相應(yīng)的數(shù)字進行選擇: "); </p><p>　　scanf("%d",&choose);</p><p>　　

49、for(i=1;i<=4;i++)</p><p><b>　　{</b></p><p>　　if(choose==i) { chooseFlag=true; break;</p><p><b>　　}</b></p><p>　　else chooseFlag=false;</p&

50、gt;<p><b>　　}</b></p><p>　　if(!chooseFlag) printf("Error Input!\n");</p><p>　　} //end while(!chooseFlag)</p><p>　　if(choose==1) //if 開始</p><

51、p><b>　　{</b></p><p>　　printf("Input how many people in it:");//z為總?cè)藬?shù)</p><p>　　scanf("%d",&z);</p><p><b>　　if(z<=30)</b></p&g

52、t;<p><b>　　{</b></p><p>　　H=create(z);//函數(shù)調(diào)用</p><p>　　printf("\nInput the start code m0=");</p><p>　　scanf("%d",&m0);</p><p>

53、　　search(H,m0,z);</p><p>　　printf("\n\n\n");</p><p><b>　　}</b></p><p><b>　　else </b></p><p><b>　　{</b></p><p>

54、;　　printf("超過最大輸入人數(shù)\n"); </p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　==11==</b><

55、;/p><p>　　else if(choose==2)</p><p><b>　　{</b></p><p>　　printf("\n約瑟夫環(huán)問題：設(shè)有n個人，其編號分別為1，2，3，…，n，安裝編號順序順時針圍坐一圈。選定一個正整數(shù)m，從第一個人開始順時針報數(shù)，</p><p>　　報到m時，則此人出列，然后

56、從他的下一個人從1重新報數(shù)，依此類推，直到所有人全部出列為止，求出列的順序。\n\n");</p><p><b>　　}</b></p><p>　　else if(choose==3)</p><p><b>　　{</b></p><p>　　printf("程序結(jié)束\n&

57、quot;);</p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　printf(&qu

58、ot;錯誤!\n");</p><p><b>　　}//end if</b></p><p>　　chooseFlag=0;</p><p>　　}//end while(1)</p><p><b>　　}</b></p><p>　　void main()&l

59、t;/p><p><b>　　{</b></p><p>　　time_t timer ;/*時間*/</p><p>　　struct tm *ptrtime;/*指向struct tm的指針*/</p><p>　　timer = time( NULL ) ;/*調(diào)用time()函數(shù)獲取當前時間*/</p>

60、<p>　　ptrtime = localtime( &timer ) ;/*調(diào)用localtime()函數(shù)將獲得的系統(tǒng)時間轉(zhuǎn)化為指向struct tm的指針指向的結(jié)構(gòu)體*/</p><p>　　printf(" 系統(tǒng)時間: %s",asctime( ptrtime ) ) ;/*用asctime()將結(jié)構(gòu)體轉(zhuǎn)化為字符串輸出*/&

61、lt;/p><p><b>　　text();}</b></p><p><b>　　==12==</b></p><p><b>　　參 考 文 獻</b></p><p>　　1張乃孝,裘宗燕.數(shù)據(jù)結(jié)構(gòu)C++與面向?qū)ο蟮耐緩?北京：高等教育出版社，1998</p>

62、<p>　　2 周云靜．數(shù)據(jù)結(jié)構(gòu)習題解析與上機指導．北京：冶金工業(yè)出版社，2004</p><p>　　3 陳慧南．數(shù)據(jù)結(jié)構(gòu)—C++語言描述．北京：人民郵電出版社，2005</p><p>　　4 嚴蔚敏，吳偉民．數(shù)據(jù)結(jié)構(gòu)．北京：清華大學出版社，1997</p><p>　　5 Adam Drozdek．數(shù)據(jù)結(jié)構(gòu)與算法．北京：清華大學出版社，2006&l