約瑟夫環(huán)問(wèn)題課程設(shè)計(jì)報(bào)告成果.doc

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