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

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

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

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

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

5、;　　1.1功能分析2</b></p><p><b>　　1.2設(shè)計(jì)平臺(tái)2</b></p><p><b>　　2概要設(shè)計(jì)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è)計(jì)主要流程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>　　參 考 文 獻(xiàn)13</p><p><b>

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

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

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

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

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

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

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

15、>　　用循環(huán)鏈表實(shí)現(xiàn)報(bào)數(shù)問題,利用count累計(jì)報(bào)數(shù)人數(shù)，num為標(biāo)記出列人數(shù)計(jì)數(shù)器。當(dāng)隨機(jī)輸入初始密碼m0時(shí)即從第一個(gè)人報(bào)起，到第m時(shí)取出m并顯示，在釋放該指針指向m的值，從刪除位的下一個(gè)人開始報(bào)起，按該人的密碼為m實(shí)現(xiàn)對(duì)總個(gè)鏈表的輸出，指針沒報(bào)數(shù)一次則后移一個(gè)節(jié)點(diǎn)。</p><p>　　實(shí)現(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"); 對(duì)上次輸入的及運(yùn)行結(jié)果是否進(jìn)行屏幕清理工作。使程序運(yùn)行界面不至于太過混亂，也可以將第二次的實(shí)驗(yàn)結(jié)果和先前的實(shí)驗(yàn)結(jié)果進(jìn)行比較從而可以發(fā)現(xiàn)程序是否出現(xiàn)運(yùn)行錯(cuò)誤，便于檢查和修改。&l

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

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

20、使用的其他的一些比較復(fù)雜的方法。</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>　　當(dāng)程序運(yùn)行的時(shí)候會(huì)出現(xiàn)如上圖所示的提示，要求使用者輸入程序中所需的輸入總?cè)藬?shù)，使用者只需輸入自己所想的總?cè)藬?shù)，便可以隨機(jī)輸入每個(gè)人對(duì)應(yīng)的密碼。最后系統(tǒng)會(huì)給出出列的次序。使用者還可進(jìn)行選擇是否記錄上次數(shù)據(jù)，進(jìn)行下一次的操作。</p>

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

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

24、邊探索，這這個(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í)踐的前提，這樣理論和實(shí)踐才能充分地結(jié)合起來。在以后的學(xué)習(xí)中，我還要努力改正，充分利用上機(jī)實(shí)驗(yàn)的機(jī)會(huì)提高自己。在程序的輸入的時(shí)候，因?yàn)樽约簩?duì)鍵盤的不熟練，代碼又很多很繁瑣，常常會(huì)產(chǎn)生放棄的念頭，從中我也</p><p><b>　

25、　=7==</b></p><p>　　感受到只有堅(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)問題，提出問題，解決問題，從不足之處出發(fā)，在不斷學(xué)習(xí)中提高自己。 </p><p><b>　　致

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

27、檢驗(yàn)自己機(jī)會(huì)。只有在真正實(shí)戰(zhàn)的時(shí)候才會(huì)發(fā)現(xiàn)書到用時(shí)方恨少的真諦。有時(shí)感覺自己那么一次次舉手請(qǐng)教，可問題又那么幼稚簡單。老師是那么的耐心與不厭其煩，直到我們點(diǎn)頭說懂得的時(shí)候老師才離開。。最后也要感謝同學(xué)們的幫助，感謝所有在我課程設(shè)計(jì)過程中幫助過我的人！</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;//序號(hào)</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號(hào)的密碼%d",i,s->m);</p><p>　　if(H==NULL)//從鏈表的第一個(gè)節(jié)點(diǎn)插入</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é)點(diǎn)插入</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)鏈表實(shí)現(xiàn)報(bào)

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

38、quot;出列的順序?yàn)?");</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("請(qǐng)問需要清除上一次操作記錄嗎（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用來阻止第一次進(jìn)入程序清屏操作</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(" ……………………歡迎進(jìn)入約瑟夫環(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("請(qǐng)輸入相應(yīng)的數(shù)字進(jìn)行選擇: "); </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個(gè)人，其編號(hào)分別為1，2，3，…，n，安裝編號(hào)順序順時(shí)針圍坐一圈。選定一個(gè)正整數(shù)m，從第一個(gè)人開始順時(shí)針報(bào)數(shù)，</p><p>　　報(bào)到m時(shí)，則此人出列，然后

56、從他的下一個(gè)人從1重新報(bào)數(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;錯(cuò)誤!\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 ;/*時(shí)間*/</p><p>　　struct tm *ptrtime;/*指向struct tm的指針*/</p><p>　　timer = time( NULL ) ;/*調(diào)用time()函數(shù)獲取當(dāng)前時(shí)間*/</p>

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

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

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