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