約瑟夫環(huán)問題課程設(shè)計報告成果.doc

計算機(jī)學(xué)院網(wǎng)絡(luò)工程專業(yè)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計題 目： 排序系統(tǒng)設(shè)計（約瑟夫環(huán)問題） 班 級： 網(wǎng)工10101班 姓 名： 羅源 學(xué) 號 201017030128 同組人姓名： 房鴻朝 起 迄 日 期: 2010年12月26日 課程設(shè)計地點(diǎn): E3-A513 指導(dǎo)教師： 徐曉蓉 完成日期：2011年12月評閱意見：成績評定： 評閱人： 日期： 摘要：約瑟夫問題是由古羅馬著名的史學(xué)家Josephus提出的問題演變而來，所以通常稱為Josephus問題。改進(jìn)約瑟夫問題的描述是：編號為1，2，n的n個人按順時針方向圍坐一圈, 每人有一個密碼Ki（整數(shù)），留作其出圈后應(yīng)報到Ki后出圈。報數(shù)方法采用順時針報數(shù)和逆時針報數(shù)交替進(jìn)行，初始密碼可任意確定。求最后剩下的人的編號。這個就是約瑟夫環(huán)問題的實(shí)際場景，后來老師要求我們對要求中的每人所持有的密碼以及第一次的報數(shù)上限值要用隨機(jī)數(shù)產(chǎn)生。因此約瑟夫環(huán)問題如果采用雙向循環(huán)鏈表則能很好的解決。循環(huán)鏈表的數(shù)據(jù)結(jié)構(gòu)，就是將一個鏈表的尾元素指針指向隊(duì)首元素。 p-link=head解決問題的核心步驟：先建立一個具有n個鏈結(jié)點(diǎn)，無頭結(jié)點(diǎn)的循環(huán)鏈表，然后確定第一個報數(shù)人的位置，并不斷地從鏈表中刪除鏈結(jié)點(diǎn)，直到鏈表為空。123 45N 圖示目錄1.需要分析41.1功能分析41.2設(shè)計平臺42.概要設(shè)計52.1算法概述52.2算法具體分析52.3結(jié)構(gòu)體Node62.4函數(shù)流程圖63.詳細(xì)設(shè)計與實(shí)現(xiàn)83.1創(chuàng)建節(jié)點(diǎn)Node83.2創(chuàng)建單循環(huán)鏈表83.3查找并刪除節(jié)點(diǎn)83.4菜單及清屏函數(shù)94.調(diào)試與操作說明94.1調(diào)試情況94.2操作說明10總結(jié)13致謝14參考文獻(xiàn)14附錄15第1章.需要分析1.1功能分析本次選做的課程設(shè)計是改進(jìn)約瑟夫(Joseph)環(huán)問題。我選擇了和房鴻朝兩個人來完成本次課程設(shè)計的作業(yè)。約瑟夫環(huán)問題是一個古老的數(shù)學(xué)問題，本次課題要求用程序語言的方式解決數(shù)學(xué)問題。此問題僅使用單循環(huán)鏈表就可以解決此問題。 問題描述：編號為1，2 n的n個人按順時針方向圍坐一圈，每人持有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)的上限值m，從第一個人開始按順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)，報m的人出列，將他的密碼作為新的m值，從他的順時針方向上的下一個開始重新從1報數(shù)，如此下去，直至所有人全部出列為止，設(shè)計一個程序求出出列順序。 功能要求：A利用單循環(huán)鏈表作為存儲結(jié)構(gòu)模擬此過程；B鍵盤輸入總?cè)藬?shù)、初始報數(shù)上限值m及各人密碼；C按照出列順序輸出各人的編號。 1.2設(shè)計平臺 Windows2000以上操作系統(tǒng)；Microsoft Visual C+ 6.0 第2章.概要設(shè)計21算法概述建立一個循環(huán)單鏈表,然后輸入要建立結(jié)點(diǎn)的個數(shù),在每個結(jié)點(diǎn)輸入一個密碼,同時按輸入時的順序進(jìn)行編號:1,2,3,4, n.任選一個正整數(shù)m0作為初始報數(shù)上限值.從定義的那個頭結(jié)點(diǎn)開始,數(shù)到m0,輸出該結(jié)點(diǎn)所儲存的編號和密碼.并將該密碼作為新的m0值,同時還將該密碼所在的結(jié)點(diǎn)刪除.如此循環(huán)鏈表還剩最后一個數(shù)據(jù)的時候停止此循環(huán).再將最后一個沒在循環(huán)里面的編號和密碼另外輸出.循環(huán)鏈表如圖1所示: 圖1循環(huán)單鏈表的創(chuàng)建2.2算法具體分析 （1） 這幾個函數(shù)是構(gòu)建本程序菜單所必須的函數(shù)（2） creat()初始化循環(huán)鏈表,開辟一個空間作為頭結(jié)點(diǎn),并讓H先讓它指向自己,令鏈表循環(huán)起來. 利用for循環(huán)和s=(Linklist)malloc(sizeof(Node);向循環(huán)鏈表里面插入數(shù)據(jù)(包括編號和密碼)。（3） search()主要用于解決約瑟夫環(huán)問題,首先調(diào)用creat()建立的循環(huán)鏈表,定義兩個指針prep和p,再定義count作為計數(shù)器,此時需要任意輸入一個正整數(shù)m0作為初始報數(shù)上限值,當(dāng)計數(shù)器count=x時就把該指針?biāo)赶虻臄?shù)據(jù)輸出并把該數(shù)據(jù)賦給x,作為新的報數(shù)上限值.然后刪除該結(jié)點(diǎn),pre和p的主要作用是在把輸出數(shù)據(jù)之后的結(jié)點(diǎn)刪除.如此循環(huán),直到還剩最后一個結(jié)點(diǎn). （4） 菜單2選項(xiàng)用于約瑟夫環(huán)問題的解析說明，增強(qiáng)使用者對本程序的理解。 2.3結(jié)構(gòu)體Node 主要功能是創(chuàng)建結(jié)點(diǎn)，每個結(jié)點(diǎn)數(shù)值域包括data,cipher,還有指示前驅(qū)結(jié)點(diǎn)的指針H,和指示后繼結(jié)點(diǎn)的指針s 2.4函數(shù)流程圖2.4.1 主函數(shù)流程圖開始等待進(jìn)入welcome 菜單菜單選擇約瑟夫環(huán)問題約瑟夫環(huán)解釋退出程序清屏函數(shù) 相關(guān)函數(shù) 結(jié)束程序 2.4.1 解決約瑟夫環(huán)問題相關(guān)函數(shù)流程圖進(jìn)入約瑟夫環(huán)系統(tǒng)輸入數(shù)據(jù)創(chuàng)建循環(huán)鏈表查找和刪除相應(yīng)元素依次輸出出列順序清屏操作總菜單第3章.詳細(xì)設(shè)計與實(shí)現(xiàn)3.1創(chuàng)建節(jié)點(diǎn)Node鏈表都是由一個個結(jié)點(diǎn)組成，由于結(jié)點(diǎn)的不同，組成的鏈表也不同。由于每一個結(jié)點(diǎn)有一個密碼和一個序號，所以可以將結(jié)點(diǎn)結(jié)構(gòu)體定義為：（如圖3.1）編號 密碼 nexttypedef struct Node int m;/密碼int n;/序號struct Node *next; Node,*Linklist; 圖3.1（節(jié)點(diǎn)） 3.2創(chuàng)建單循環(huán)鏈表 創(chuàng)建一個空單循環(huán)鏈表，雙向循環(huán)鏈表和每個結(jié)點(diǎn)包括兩個域:元素域和指針域。形成單循環(huán)鏈表的原理：定義三個指針變量H,r,s,三指針開始全部指向頭結(jié)點(diǎn)，在插入操作開始后，H不變?nèi)灾赶蝾^結(jié)點(diǎn)，s指針在插入過程中始終指向新插入的節(jié)點(diǎn)，而r指針緊隨其后，用于將新插入的節(jié)點(diǎn)和前一個節(jié)點(diǎn)連接起來，最后通過r指向頭指針H，來完成環(huán)的操作。關(guān)鍵代碼實(shí)現(xiàn)如下：if(H=NULL) H=s，r=H;/從鏈表的第一個節(jié)點(diǎn)插入else r-next=s，r=s;/r后移/鏈表的其余節(jié)點(diǎn)插入結(jié)束for循環(huán)后結(jié)成環(huán)的操作：r-next=H;/*生成循環(huán)單鏈表*/return H;3.3查找并刪除節(jié)點(diǎn) 每當(dāng)結(jié)點(diǎn)計數(shù)到某一結(jié)點(diǎn)時，將他的前驅(qū)結(jié)點(diǎn)接到他的后繼結(jié)點(diǎn)，然后將他的密碼值cipher賦給計數(shù)變量，再將此結(jié)點(diǎn)刪除。如此循環(huán)下去，直到最后變?yōu)榭盏膯窝h(huán)鏈表為止。函數(shù)通過代碼：p=H; pre=p; p=p-next;pre-next=p-next; p=pre-next;來刪除當(dāng)前的那個結(jié)點(diǎn)q，通過循環(huán)來一次次刪除當(dāng)前的結(jié)點(diǎn)，直到鏈表中剩下最后一個結(jié)點(diǎn)。 3.4菜單及清屏函數(shù)菜單：通過兩個while循環(huán)建立菜單，一個while嵌套在另一個里面，第一個循環(huán)為永循環(huán)除非碰到break結(jié)束循環(huán)，第二個while通過一個chooseflag的真假值來判斷循環(huán)是否繼續(xù)執(zhí)行下去。Choose的值加上IF語句實(shí)現(xiàn)選項(xiàng)。清屏：建立一個清屏函數(shù)的關(guān)鍵在于可由于人的需要判斷是否做出清屏操作，靠的是簡單的IF語句和系統(tǒng)自帶清屏函數(shù)組合而成。關(guān)鍵語句如下：int inquiry;if(inquiry =1)system(cls); 第4章.調(diào)試與操作說明 4.1調(diào)試情況在首次運(yùn)行時出現(xiàn)過一些小的問題，由于程序的復(fù)雜難度不大，所以解決起來并不會出現(xiàn)太大的問題不過經(jīng)過一點(diǎn)點(diǎn)的改正，錯誤也慢慢地變少。這也說明做事要認(rèn)真，尤其做計算機(jī)這方面工作的時候，因?yàn)橛嬎銠C(jī)不容許不一點(diǎn)點(diǎn)的錯誤，有了一點(diǎn)小錯誤和有一個大錯誤在計算機(jī)看來都是一樣的，都不會得不到結(jié)果。有些小錯誤，比如說少了個分號，變量忘了定義，數(shù)據(jù)溢出等都是些小錯誤，但也不能松懈。因?yàn)橐⒁獾牡胤胶芏?，?jīng)過多次嘗試，問題也就自然而然的解決了，而且以后遇到這方面的問題都會覺得比較得心應(yīng)手。出現(xiàn)可被編譯器解決的問題容易找出，但出現(xiàn)運(yùn)行計算過程中的錯誤就得仔細(xì)分析函數(shù)步驟的錯誤，我們在運(yùn)行過程中曾出現(xiàn)過由于累計報數(shù)人數(shù)計數(shù)器count未被歸1，而造出出列順序的錯誤，但是只要你細(xì)心觀察也一定能解決這些看起來很簡單卻不易于被發(fā)現(xiàn)的問題。測試數(shù)據(jù)如下三組：（經(jīng)計算均為正確值）13，5，2（4） 出列順序?yàn)?，2，32. 2，6，3，4，8（2） 出列順序?yàn)?2，4，5，3，13. 3，1，7，2，4，7，4（20） 出列順序?yàn)?6，7，4，1，5，3，24.2操作說明 4.2.1菜單界面（顯示系統(tǒng)時間）4.2.2進(jìn)入并實(shí)現(xiàn)約瑟夫環(huán)問題界面（附帶清屏函數(shù)） 4.2.3進(jìn)入2了解約瑟夫環(huán)問題界面（附帶清屏函數(shù)）4.2.4 不執(zhí)行清屏操作時的界面4.2.4選擇3 退出程序的界面 總結(jié) -心得體會一周的課程設(shè)計將要結(jié)束了,課程設(shè)計彌補(bǔ)了平時學(xué)習(xí)上被遺忘的一些知識,同時也當(dāng)作期末考試復(fù)習(xí)的一部分,約瑟夫環(huán)問題,主要是以鏈表和指針知識為主的編程設(shè)計,此次課程設(shè)計不但加深了自己對鏈表認(rèn)識,同時也了解了更多關(guān)于鏈表在數(shù)據(jù)結(jié)構(gòu)中的其它應(yīng)用,從雙鏈表,循環(huán)雙鏈表到鏈棧,鏈串.自己都有認(rèn)真去看了一次.指針方面的知識,在C語言中是極其重要的,之前對于指針的使用一直不怎么熟悉,經(jīng)過這次課程設(shè)計之后,指針的使用,基本上都懂了.還有就是各個函數(shù)之間的傳遞和調(diào)用,運(yùn)用起來也比較熟悉了,不像以前那樣,不知怎么用. 這次課程設(shè)計的最大缺點(diǎn)就是,菜單的設(shè)計不應(yīng)該選擇彈出式菜單,因?yàn)榧s瑟夫環(huán)這道題目的要求只有三個,把解決約瑟夫環(huán)問題的主函數(shù)做出來之后,發(fā)現(xiàn)代碼比較少,當(dāng)時為了追求代碼的數(shù)量,才選擇了彈出式菜單.不僅花費(fèi)了不少的時間,而且做出來的菜單也不美觀.雖然在功能上是比其它的菜單好,但是對于修改菜單,菜單界面的修改都是挺麻煩的. 剛開始的時候,由于對題目錯誤的理解,對自己的編程造成了一些影響,里面說到密碼,就想到了密碼應(yīng)該包括英文字母,沒有注意到括號里面的正整數(shù),如果是英文字母的話,難度相對大一些.開始在這個問題上耗了不少時間,后來在同學(xué)的提醒下,把錯誤修改了過來. 這次課程設(shè)計,給了自己很大的幫助,只是一道題目涉及的內(nèi)容有點(diǎn)少,一道題目只涉及到一兩個知識點(diǎn),如果題目能夠涉及到,樹,圖,棧,隊(duì)列,串,這些數(shù)據(jù)結(jié)構(gòu)中的重要知識點(diǎn),這樣對我們的能力培養(yǎng)會更好一點(diǎn). 致謝這次的課程設(shè)計，我們兩人一個小組去完成我們自己的課程，但是還是得到了來自很多方面的幫助。在此首先要感謝淮陰工學(xué)院計算機(jī)工程系提供給我這次實(shí)踐的機(jī)會，讓我們有機(jī)會貼近現(xiàn)實(shí)，感受成功的喜悅；其次要感謝實(shí)驗(yàn)機(jī)房的老師提供優(yōu)良的實(shí)驗(yàn)設(shè)備供我們做實(shí)驗(yàn)，正是這種良好的實(shí)驗(yàn)環(huán)境讓我們整個實(shí)驗(yàn)過程心情都非常愉快。只有在真正實(shí)戰(zhàn)的時候才會發(fā)現(xiàn)書到用時方恨少的真諦。有時感覺自己那么一次次舉手請教，可問題又那么幼稚簡單。最后也要感謝同學(xué)們的幫助，有了他們的支持使我遇到任何困難都不是一個人在戰(zhàn)斗。感謝所有在我課程設(shè)計過程中幫助過我的人！ 參考文獻(xiàn)1 C程序設(shè)計 （第三版） 譚浩強(qiáng) 著 清華大學(xué)出版社2 數(shù)據(jù)結(jié)構(gòu) （C語言版） 嚴(yán)蔚敏 著 清華大學(xué)出版社3 C+面向?qū)ο蟪绦蛟O(shè)計教程 陳維興 林小茶 著 清華大學(xué)出版社 附錄程序源代碼：#include #include #include#include #include#define NULL 0typedef struct Node int m;/密碼int n;/序號struct Node *next;Node,*Linklist;Linklist create(int z) /生成循環(huán)單鏈表并返回,z為總?cè)藬?shù) int i,mm;Linklist H,r,s;H=NULL;printf(請按順序依次為每個人添加密碼：);for(i=1;in=i;s-m=mm;printf(%d號的密碼%d,i,s-m);if(H=NULL)/從鏈表的第一個節(jié)點(diǎn)插入 H=s;r=H;else/鏈表的其余節(jié)點(diǎn)插入 r-next=s;r=s;/r后移/for結(jié)束r-next=H;/*生成循環(huán)單鏈表*/return H;void search(Linklist H,int m0,int z)/用循環(huán)鏈表實(shí)現(xiàn)報數(shù)問題 int count=1;/count為累計報數(shù)人數(shù)計數(shù)器 int num=0;/num為標(biāo)記出列人數(shù)計數(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 inquiry;printf(請問需要清除上一次操作記錄嗎（1.清屏/2.不清屏）.?n);scanf(%d,&inquiry);if(inquiry =1)system(cls);void text()int m0,z,i, choose,k=1; /k用來阻止第一次進(jìn)入程序清屏操作Linklist H; bool chooseFlag=false;while(1)if(k!=1)clean();k+;while(!chooseFlag)printf( 歡迎進(jìn)入約瑟夫環(huán)問題系統(tǒng) n);printf( * 1.輸入約瑟夫環(huán)數(shù)據(jù) * n);printf( * 2.什么是約瑟夫環(huán) * n);printf( * 3.退出系統(tǒng) * n);printf(. n);printf(請輸入相應(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(