約瑟夫環(huán)-課程設(shè)計

1、<p>　　目 錄</p><p><b>　　1題目1</b></p><p><b>　　1.1問題描述1</b></p><p><b>　　1.2功能要求1</b></p><p>　　2算法思想描述：1</p><p

2、>　　2.1算法概述：1</p><p>　　2.2算法具體分析2</p><p><b>　　3 程序結(jié)構(gòu)3</b></p><p>　　3.1主函數(shù)流程圖3</p><p>　　3.2 josephus()函數(shù)流程圖4</p><p>　　4 實驗結(jié)果與分析5</p&g

3、t;<p>　　4.1實驗測試中的關(guān)鍵代碼與各模塊測試結(jié)果的分析與說明5</p><p>　　4.2試驗過程中所遇到的問題分析與解決11</p><p>　　5課程設(shè)計總結(jié)12</p><p>　　參 考 文 獻13</p><p><b>　　1題目</b></p><p

4、><b>　　約瑟夫環(huán)</b></p><p><b>　　1.1問題描述</b></p><p>　　編號為1，2… n的n個人按順時針方向圍坐一圈，每人持有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)的上限值m，從第一個人開始按順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)，報m的人出列，將他的密碼作為新的m值，從他的順時針方向上的下

5、一個開始重新從1報數(shù)，如此下去，直至所有人全部出列為止，設(shè)計一個程序求出出列順序。 </p><p><b>　　1.2功能要求</b></p><p>　　A利用單循環(huán)鏈表作為存儲結(jié)構(gòu)模擬此過程；</p><p>　　B鍵盤輸入總?cè)藬?shù)、初始報數(shù)上限值m及各人密碼；</p><p>　　C按照出列順序輸出各人的編號。&l

6、t;/p><p><b>　　2算法思想描述：</b></p><p><b>　　2.1算法概述：</b></p><p>　　建立一個循環(huán)單鏈表,然后輸入要建立結(jié)點的個數(shù),在每個結(jié)點輸入一個密碼,同時按輸入時的順序進行編號:1,2,3,4, ……n.任選一個正整數(shù)x作為初始報數(shù)上限值.從定義的那個頭結(jié)點開始,數(shù)到x,輸出該

7、結(jié)點所儲存的編號和密碼.并將該密碼作為新的x值,同時還將該密碼所在的結(jié)點刪除.如此循環(huán)鏈表還剩最后一個數(shù)據(jù)的時候停止此循環(huán).再將最后一個沒在循環(huán)里面的編號和密碼另外輸出.循環(huán)鏈表如圖1所示:</p><p><b>　　圖2</b></p><p><b>　　2.2算法具體分析</b></p><p>　　window(

8、),switch(),upbar（）, downbar（）,key()這幾個函數(shù)是構(gòu)建本程序菜單所必須的函數(shù).window()用于開窗口,以坐標(biāo)的形式開辟一個窗口,并且可以在窗口里面儲存數(shù)據(jù).switch()創(chuàng)建菜單選項,key()主要用于獲取鍵盤上的字符(包括字母和方向鍵,enter鍵),upbar()和 downbar()實現(xiàn)光條的上移和下移. textbackground()，textcolor()。窗口背景顏色和里面文本顏色的設(shè)

9、置。</p><p>　　InitList()初始化循環(huán)鏈表,開辟一個空間作為頭結(jié)點,并讓L=L->next先讓它指向自己,令鏈表循環(huán)起來. ListInsert()向循環(huán)鏈表里面插入數(shù)據(jù)(包括編號和密碼), DispList()以定義的頭結(jié)點為第一個數(shù),輸出循環(huán)鏈表.</p><p>　　josephus()主要用于解決約瑟夫環(huán)問題,首先調(diào)用InitList()建立循環(huán)鏈表,再調(diào)用

10、ListInsert()插入數(shù)據(jù),再調(diào)用DispList()把儲存的數(shù)據(jù)輸出來.定義兩個指針s和q,再定義count作為計數(shù)器,此時需要任意輸入一個正整數(shù)x作為初始報數(shù)上限值,當(dāng)計數(shù)器count=x時就把該指針?biāo)赶虻臄?shù)據(jù)輸出并把該數(shù)據(jù)賦給x,作為新的報數(shù)上限值.然后刪除該結(jié)點,s和q的主要作用是在把輸出數(shù)據(jù)之后的結(jié)點刪除.如此循環(huán),直到還剩最后一個結(jié)點,同時定義a[i],b[i]用來儲存編號和密碼。</p><p&

11、gt;　　passcode（）把josephus()里所儲存到數(shù)組a[i],b[i]的數(shù)據(jù)傳遞到passcode（）,方便在退出josephus()函數(shù)之后還可以再次查看。</p><p>　　about()約瑟夫環(huán)問題的解析說明，增強使用者對本程序的理解。</p><p><b>　　3 程序結(jié)構(gòu)</b></p><p><b>　

12、　3.1主函數(shù)流程圖</b></p><p>　　3.2 josephus()函數(shù)流程圖</p><p><b>　　4 實驗結(jié)果與分析</b></p><p>　　上述程序在win-TC環(huán)境下加以實現(xiàn)，經(jīng)過多次的測試，程序運行正確。</p><p>　　4.1實驗測試中的關(guān)鍵代碼與各模塊測試結(jié)果的分析與說明

13、</p><p>　　(1)創(chuàng)建一個彈出式主菜單下面代碼是其設(shè)計界面的代碼. 文本框1是界面代碼, 文本框2是獲取鍵盤方向代碼.效果如圖2所示:</p><p><b>　　文本框1</b></p><p><b>　　文本框2</b></p><p><b>　　圖2</b>

14、</p><p><b>　　圖3</b></p><p>　　(2)實現(xiàn)光標(biāo)的上移和下移,其代碼文本框3所示, 其效果,請對比圖2和圖3.</p><p><b>　　文本框3</b></p><p>　　(3)在循環(huán)鏈表里輸入數(shù)據(jù),其實現(xiàn)代碼如文本框4所示,效果如圖4所示.</p>

15、<p><b>　　文本框4</b></p><p><b>　　圖4</b></p><p>　　(4)進入約瑟夫環(huán)問題的數(shù)據(jù)處理.其實現(xiàn)代碼如文本框5所示,效果如圖5所示:</p><p><b>　　文本框5</b></p><p><b>　　圖5

16、</b></p><p>　　(3)查看已儲存的數(shù)據(jù).其代碼如文本框6所示,其效果如圖6所示:</p><p><b>　　文本框6</b></p><p><b>　　圖6</b></p><p>　　(3)查看約瑟夫環(huán)問題的內(nèi)容:其效果如圖7所示:</p><p&

17、gt;<b>　　圖7</b></p><p>　　4.2試驗過程中所遇到的問題分析與解決</p><p>　　問題一:在創(chuàng)建彈出式菜單時,光標(biāo)的上移和下移,無法實現(xiàn).</p><p>　　解決方案:將彈出式菜單的教程重新看了一遍,里面的光標(biāo)上移和下移,都是通過各個坐標(biāo)來實現(xiàn)的,例如window(3,3,29,9);前兩個數(shù)是窗口的左上角的橫坐

18、標(biāo)和豎坐標(biāo),后兩個數(shù)是窗口右下角的坐標(biāo)和豎坐標(biāo).經(jīng)過反復(fù)調(diào)試之后,建了一個小的主菜單.光標(biāo)上移和下移是在同學(xué)的幫助下實現(xiàn)的.因為自己還沒完全理解這個過程的操作.</p><p>　　問題二:在創(chuàng)建循環(huán)鏈表時,沒有在頭結(jié)點儲存數(shù)據(jù),造成在密碼和編號輸出不正確.</p><p>　　解決方案:在輸入數(shù)據(jù)時,從頭結(jié)點開始儲存數(shù)據(jù).</p><p>　　問題三:當(dāng)鏈表被一個

19、個刪除的時候,如果頭結(jié)點被刪除的話,輸出時會出現(xiàn)亂碼.</p><p>　　解決方案:加入一個判斷語句if(q==head),當(dāng)指針指到頭的時候執(zhí)行這一步head=q->next;將頭結(jié)點移到下一個數(shù)據(jù).</p><p>　　問題四:在刪除結(jié)點時,沒有刪除到輸出數(shù)據(jù)那個結(jié)點.</p><p>　　解決方案: 用兩個指針s和q ,當(dāng)計數(shù)count==x-1時,先

20、將s=q,計數(shù)計到count==x后,這時q指向要輸出的數(shù)據(jù),再將s->next=q->next,再free(q),這樣就可以刪除對應(yīng)的結(jié)點了.</p><p>　　問題五:因為v C++6.0不支持window()這個函數(shù),無法創(chuàng)建彈出式菜單,需要轉(zhuǎn)移到win-tc下. josephus()函數(shù)在v C++6.0編譯環(huán)境下運行沒問題,復(fù)制到win-TC下就出現(xiàn)問題,已經(jīng)定義的指針,提示我在還沒定義之

21、前就已經(jīng)使用了.</p><p>　　解決方案: v C++6.0環(huán)境下:</p><p>　　void InitList(LinkList *&L)</p><p><b>　　{</b></p><p>　　L=(LinkList *)malloc(sizeof(LinkList));</p>

22、<p>　　L->next=L;</p><p><b>　　}</b></p><p>　　在win-tc環(huán)境下: </p><p>　　void InitList(LinkList **L)</p><p><b>　　{</b></p><p>　　(

23、*L)=(LinkList *)malloc(sizeof(LinkList));</p><p>　　(*L)->next=*L; </p><p><b>　　}</b></p><p>　　只要把v C++6.0下的&改成二級指針,便可以在win-tc環(huán)境下使用了.</p><p><b

24、>　　5課程設(shè)計總結(jié)</b></p><p>　　兩周的課程設(shè)計將要結(jié)束了,課程設(shè)計彌補了平時學(xué)習(xí)上被遺忘的一些知識,同時也當(dāng)作期末考試復(fù)習(xí)的一部分,約瑟夫環(huán)問題,主要是以鏈表和指針知識為主的編程設(shè)計,此次課程設(shè)計不但加深了自己對鏈表認識,同時也了解了更多關(guān)于鏈表在數(shù)據(jù)結(jié)構(gòu)中的其它應(yīng)用,從雙鏈表,循環(huán)雙鏈表到鏈棧,鏈串.自己都有認真去看了一次.指針方面的知識,在C語言中是極其重要的,之前對于指針

25、的使用一直不怎么熟悉,經(jīng)過這次課程設(shè)計之后,指針的使用,基本上都懂了.還有就是各個函數(shù)之間的傳遞和調(diào)用,運用起來也比較熟悉了,不像以前那樣,不知怎么用.</p><p>　　這次課程設(shè)計的最大缺點就是,菜單的設(shè)計不應(yīng)該選擇彈出式菜單,因為約瑟夫環(huán)這道題目的要求只有三個,把解決約瑟夫環(huán)問題的主函數(shù)做出來之后,發(fā)現(xiàn)代碼比較少,當(dāng)時為了追求代碼的數(shù)量,才選擇了彈出式菜單.不僅花費了不少的時間,而且做出來的菜單也不美觀.

26、雖然在功能上是比其它的菜單好,但是對于修改菜單,菜單界面的修改都是挺麻煩的.</p><p>　　剛開始的時候,由于對題目錯誤的理解,對自己的編程造成了一些影響,里面說到密碼,就想到了密碼應(yīng)該包括英文字母,沒有注意到括號里面的正整數(shù),如果是英文字母的話,難度相對大一些.開始在這個問題上耗了不少時間,后來在同學(xué)的提醒下,把錯誤修改了過來.</p><p>　　這次課程設(shè)計,給了自己很大的幫助