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

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題 目： 排序系統(tǒng)設(shè)計(jì)（約瑟夫環(huán)問(wèn)題） 班 級(jí)： 網(wǎng)工10101班 姓 名： 房鴻朝 學(xué) 號(hào) 201017030127 同組人姓名： 起 迄 日 期: 2010年12月26日 課程設(shè)計(jì)地點(diǎn): e3-a513 指導(dǎo)教師： 評(píng)閱意見(jiàn)：成績(jī)?cè)u(píng)定：評(píng)閱人： 日期：完成日期：2011年12月摘要： 功能：設(shè)編號(hào)為1，2，3，n的n(n0)個(gè)人按順時(shí)針?lè)较驀蝗Γ總€(gè)人持有一個(gè)正整數(shù)密碼。開始時(shí)任選一個(gè)正整數(shù)做為報(bào)數(shù)上限m，從第一個(gè)人開始順時(shí)針?lè)较蜃?起順序報(bào)數(shù)，報(bào)到m是停止報(bào)數(shù)，報(bào)m的人出列，將他的密碼作為新的m值，從他的下一個(gè)人開始重新從1報(bào)數(shù)。如此下去，直到所有人全部出列為止。令n

2、最大值取30。要求設(shè)計(jì)一個(gè)程序模擬此過(guò)程，求出出列編號(hào)序列。目 錄1需求分析21.1功能分析21.2設(shè)計(jì)平臺(tái)22概要設(shè)計(jì)22.1創(chuàng)建循環(huán)單鏈表create()22.2輸出查找search()32.3異常處理及屏幕清理clean()33程序設(shè)計(jì)主要流程43.1程序?qū)崿F(xiàn)流程圖44調(diào)試與操作說(shuō)明44.1調(diào)試情況44.2操作說(shuō)明5總 結(jié)7致 謝8附 錄9參 考 文 獻(xiàn)13=1=1 需求分析 1.1 功能分析 本次選做的課程設(shè)計(jì)是改進(jìn)約瑟夫(joseph)環(huán)問(wèn)題。我選擇了和羅源兩個(gè)人來(lái)完成本次課程設(shè)計(jì)的作業(yè)。約瑟夫環(huán)問(wèn)題是一個(gè)古老的數(shù)學(xué)問(wèn)題，本次課題要求用程序語(yǔ)言的方式解決數(shù)學(xué)問(wèn)題。此問(wèn)題僅使用單循環(huán)鏈

3、表就可以解決此問(wèn)題。在建立單向循環(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è)人的密碼是通過(guò)scanf()函數(shù)輸入隨機(jī)生成的，所以指定第一個(gè)人的順序號(hào)，找到結(jié)點(diǎn)，不斷地從鏈表中刪除鏈結(jié)點(diǎn)，直到鏈表剩下最后一個(gè)結(jié)點(diǎn)，通過(guò)一系列的循環(huán)就可以解決改進(jìn)約瑟夫環(huán)問(wèn)題。1.2設(shè)計(jì)平臺(tái)windows2007操作系統(tǒng)；microsoft visual c+ 6.0；2概要設(shè)計(jì)已知n個(gè)人（以編號(hào)1，2，3.n分別表示）圍成一圈。從編號(hào)為1的人開始報(bào)數(shù)，

4、數(shù)到m的那個(gè)人出列；他的下一個(gè)人又從1開始報(bào)數(shù)，數(shù)到m的那個(gè)人又出列；依此規(guī)律重復(fù)下去，直到一圈的人全部出列。這個(gè)就是約瑟夫環(huán)問(wèn)題的實(shí)際場(chǎng)景，有一種是要通過(guò)輸入n,m,k三個(gè)正整數(shù)，來(lái)求出列的序列。這個(gè)問(wèn)題采用的是典型的循環(huán)鏈表的數(shù)據(jù)結(jié)構(gòu)，就是將一個(gè)鏈表的尾元素指針指向隊(duì)首元素。r-next=h。解決問(wèn)題的核心步驟：首先建立一個(gè)具有n個(gè)鏈結(jié)點(diǎn)，無(wú)頭結(jié)點(diǎn)的循環(huán)鏈表。然后確定第1個(gè)報(bào)數(shù)人的位置。最后不斷地從鏈表中刪除鏈結(jié)點(diǎn)，直到鏈表為空。本課程設(shè)計(jì)主要采用了結(jié)構(gòu)體，程序中包含了兩個(gè)只要函數(shù)：create（）；search（）；2.1 創(chuàng)建循環(huán)單鏈表create（）dtypeef struct no

5、de 定義一個(gè)結(jié)構(gòu)體，m為密碼，n為序號(hào)（總?cè)藬?shù)）。=2=定義h=null創(chuàng)建一個(gè)沒(méi)有頭結(jié)點(diǎn)的單向循環(huán)鏈表，并采for(i=1;i=h時(shí)創(chuàng)建單向循環(huán)鏈表成功，并返回h的值作為總?cè)藬?shù)。單項(xiàng)循環(huán)鏈表示意圖： 每當(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)鏈表為止。2.2 輸出查找search（）用循環(huán)鏈表實(shí)現(xiàn)報(bào)數(shù)問(wèn)題,利用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)起，按

6、該人的密碼為m實(shí)現(xiàn)對(duì)總個(gè)鏈表的輸出，指針沒(méi)報(bào)數(shù)一次則后移一個(gè)節(jié)點(diǎn)。實(shí)現(xiàn)代碼：pre-next=p-next;printf(%d ,p-n);m0=p-m;free(p); p=pre-next; 2.3異常處理及屏幕清理clean() system(cls); 對(duì)上次輸入的及運(yùn)行結(jié)果是否進(jìn)行屏幕清理工作。使程序運(yùn)行界面不至于太過(guò)混亂，也可以將第二次的實(shí)驗(yàn)結(jié)果和先前的實(shí)驗(yàn)結(jié)果進(jìn)行比較從而可以發(fā)現(xiàn)程序是否出現(xiàn)運(yùn)行錯(cuò)誤，便于檢查和修改。=3=3. 程序設(shè)計(jì)主要流程3.1 程序?qū)崿F(xiàn)流程圖（圖3-1）主菜單1.輸入約瑟夫環(huán)2.顯示約瑟夫環(huán)問(wèn)題的描述3.結(jié)束界面是否執(zhí)行清屏（1=y，2=n）？1.清屏進(jìn)入

7、2.不清屏進(jìn)入 圖3-1 程序?qū)崿F(xiàn)流程圖 4調(diào)試與操作說(shuō)明4.1調(diào)試情況這次的課程設(shè)計(jì)的代碼很冗長(zhǎng)，所以等有了解題思路后，把代碼都寫上后難免會(huì)有很多錯(cuò)誤。當(dāng)?shù)谝淮伟颜麄€(gè)程序?qū)懞煤筮\(yùn)行，出現(xiàn)了很多錯(cuò)誤。如賦值語(yǔ)句h=null沒(méi)有定義，從而形成帶空頭結(jié)點(diǎn)的單鏈表，以及在操作r指針后移找出m時(shí)，沒(méi)對(duì)r當(dāng)時(shí)的值進(jìn)行釋放從而導(dǎo)致下個(gè)輸出出現(xiàn)錯(cuò)誤。不過(guò)經(jīng)過(guò)一點(diǎn)點(diǎn)的改正，錯(cuò)誤也慢慢地變少。這也說(shuō)明做事要認(rèn)真，尤其做計(jì)算機(jī)這方面工作的時(shí)候，因?yàn)橛?jì)算機(jī)不容許不一點(diǎn)點(diǎn)的錯(cuò)誤，有了一點(diǎn)小錯(cuò)誤和有一個(gè)大錯(cuò)誤在計(jì)算機(jī)看來(lái)都是一樣的，都不會(huì)得不到結(jié)果。有些小錯(cuò)誤，比如說(shuō)少了個(gè)分號(hào)，變量忘了定義，數(shù)據(jù)溢出等都是些小錯(cuò)誤，但

8、也不能松懈。因?yàn)橐⒁獾牡胤胶芏啵?jīng)過(guò)多次嘗試，問(wèn)題也就自然而然的解決了，而且以后遇到這方面的問(wèn)題都會(huì)覺(jué)得比較得心應(yīng)手。在調(diào)試的過(guò)程中，結(jié)構(gòu)體的優(yōu)勢(shì)很明顯，能很簡(jiǎn)單的把問(wèn)題解決，而不需要使用的其他的一些比較復(fù)雜的方法。=4=4.2操作說(shuō)明生成界面如圖4-1，4-2，4-3,4-4,4-5所示； 圖 4-1 主菜單圖4-2輸入約瑟夫環(huán)=5=當(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)行下一次的操作。圖4-3顯示約瑟夫環(huán)問(wèn)題圖4-4退出程

9、序=6=圖4-5 當(dāng)輸入人數(shù)超過(guò)最大數(shù)總 結(jié)為期一周的課程設(shè)計(jì)快結(jié)束了，通過(guò)這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)，我感受最深的就是對(duì)于循環(huán)鏈表的使用，可以說(shuō)對(duì)循環(huán)鏈表有了比以前更進(jìn)一步的認(rèn)識(shí)，以前只是一知半解的，如果只給個(gè)題目自己根本不能把程序完整地編寫出來(lái)，所以這次課程設(shè)計(jì)最大的收獲就在于對(duì)循環(huán)鏈表有了一定的理解，包括其中的一系列操作，如建立一個(gè)循環(huán)鏈表，刪除鏈表中的一個(gè)結(jié)點(diǎn)，增加一個(gè)結(jié)點(diǎn)等。在這次課程設(shè)計(jì)過(guò)程中需要我們一邊設(shè)計(jì)一邊探索，這這個(gè)過(guò)程當(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í)踐

10、的前提，這樣理論和實(shí)踐才能充分地結(jié)合起來(lái)。在以后的學(xué)習(xí)中，我還要努力改正，充分利用上機(jī)實(shí)驗(yàn)的機(jī)會(huì)提高自己。在程序的輸入的時(shí)候，因?yàn)樽约簩?duì)鍵盤的不熟練，代碼又很多很繁瑣，常常會(huì)產(chǎn)生放棄的念頭，從中我也=7=感受到只有堅(jiān)持到底，勝利才會(huì)出現(xiàn)。在調(diào)試程序的時(shí)候我也有所體會(huì)，雖然約瑟夫環(huán)問(wèn)題不是很難，但調(diào)試的時(shí)候還是會(huì)出現(xiàn)很多錯(cuò)誤，因此我們不能認(rèn)為容易就不認(rèn)真對(duì)待。在以后的學(xué)習(xí)中，要能不斷發(fā)現(xiàn)問(wèn)題，提出問(wèn)題，解決問(wèn)題，從不足之處出發(fā)，在不斷學(xué)習(xí)中提高自己。 致謝這次的課程設(shè)計(jì)，我們兩人一個(gè)小組去完成我們自己的課程.，讓我們有機(jī)會(huì)貼近現(xiàn)實(shí)，感受成功的喜悅；其次要感謝實(shí)驗(yàn)機(jī)房的老師提供優(yōu)良的實(shí)驗(yàn)設(shè)備供我們

11、做實(shí)驗(yàn)，正是這種良好的實(shí)驗(yàn)環(huán)境讓我們整個(gè)實(shí)驗(yàn)過(guò)程心情都非常愉快。再次要感謝指導(dǎo)老師們的辛勤指導(dǎo)，每當(dāng)我們遇到疑難問(wèn)題時(shí)，是他們一次次不厭其煩的解釋和悉心的指導(dǎo)，我們才能闖過(guò)一個(gè)個(gè)難關(guān)，到達(dá)勝利的彼岸，是他們給我們提供了一次寶貴的檢驗(yàn)自己機(jī)會(huì)。只有在真正實(shí)戰(zhàn)的時(shí)候才會(huì)發(fā)現(xiàn)書到用時(shí)方恨少的真諦。有時(shí)感覺(jué)自己那么一次次舉手請(qǐng)教，可問(wèn)題又那么幼稚簡(jiǎn)單。老師是那么的耐心與不厭其煩，直到我們點(diǎn)頭說(shuō)懂得的時(shí)候老師才離開。最后也要感謝同學(xué)們的幫助，感謝所有在我課程設(shè)計(jì)過(guò)程中幫助過(guò)我的人！=8=附 錄#include #include #include#include #include#define null

12、0typedef struct node int m;/密碼int n;/序號(hào)struct node *next;node,*linklist;linklist create(int z) /生成循環(huán)單鏈表并返回,z為總?cè)藬?shù) int i,mm;linklist h,r,s;h=null;printf(output the code:);for(i=1;in=i;s-m=mm;printf(%d號(hào)的密碼%d,i,s-m);if(h=null)/從鏈表的第一個(gè)節(jié)點(diǎn)插入 h=s;r=h;else/鏈表的其余節(jié)點(diǎn)插入 r-next=s;r=s;/r后移/for結(jié)束r-next=h;/*生成循環(huán)單鏈表*

13、/=9=return h;void search(linklist h,int m0,int z)/用循環(huán)鏈表實(shí)現(xiàn)報(bào)數(shù)問(wèn)題 int count=1;/count為累計(jì)報(bào)數(shù)人數(shù)計(jì)數(shù)器int num=0;/num為標(biāo)記出列人數(shù)計(jì)數(shù)器linklist pre,p;p=h;printf(出列的順序?yàn)?);while(numnext;while(countnext=p-next;printf(%d ,p-n);m0=p-m;free(p);p=pre-next;count=1;num+;/while結(jié)束void clean()int system(const char *string);int inqu

14、iry;printf(請(qǐng)問(wèn)需要清除上一次操作記錄嗎（1.清屏/2.不清屏）.?n);scanf(%d,&inquiry);if(inquiry =1)system(cls);void text()int m0,z,i, choose,k=1; /k用來(lái)阻止第一次進(jìn)入程序清屏操作linklist h; bool chooseflag=false;while(1)=10=if(k!=1)clean();k+;while(!chooseflag)printf( 歡迎進(jìn)入約瑟夫環(huán)問(wèn)題系統(tǒng) n);printf( * 1.輸入約瑟夫環(huán)數(shù)據(jù) * n);printf( * 2.什么是約瑟夫環(huán) * n);pri

15、ntf( * 3.退出系統(tǒng) * n);printf( . n);printf(請(qǐng)輸入相應(yīng)的數(shù)字進(jìn)行選擇: ); scanf(%d,&choose);for(i=1;i=4;i+)if(choose=i) chooseflag=true; break;else chooseflag=false;if(!chooseflag) printf(error input!n); /end while(!chooseflag)if(choose=1) /if 開始printf(input how many people in it:);/z為總?cè)藬?shù)scanf(%d,&z);if(z=30)h=create

16、(z);/函數(shù)調(diào)用printf(ninput the start code m0=);scanf(%d,&m0);search(h,m0,z);printf(nnn);else printf(超過(guò)最大輸入人數(shù)n); break;=11=else if(choose=2)printf(n約瑟夫環(huán)問(wèn)題：設(shè)有n個(gè)人，其編號(hào)分別為1，2，3，n，安裝編號(hào)順序順時(shí)針圍坐一圈。選定一個(gè)正整數(shù)m，從第一個(gè)人開始順時(shí)針報(bào)數(shù)，報(bào)到m時(shí)，則此人出列，然后從他的下一個(gè)人從1重新報(bào)數(shù)，依此類推，直到所有人全部出列為止，求出列的順序。nn);else if(choose=3)printf(程序結(jié)束n);break;elseprintf(錯(cuò)誤!n);/end ifchooseflag=0;/end while(1)void main() time_t timer ;/*時(shí)間*/struct tm *ptrtime;/*指向struct tm的指針*/ timer = time( null ) ;/*調(diào)用time()函數(shù)獲取當(dāng)前時(shí)間*/ptrtime = localtime( &timer ) ;/*調(diào)用localtime()函數(shù)將獲得的系統(tǒng)時(shí)間轉(zhuǎn)化為指向struct tm的指針指向的結(jié)構(gòu)體*/ printf( 系統(tǒng)時(shí)間: %s,asc