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

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 實(shí)驗(yàn)結(jié)果與分析5</p&g

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

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

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

6、t;/p><p><b>　　2算法思想描述：</b></p><p><b>　　2.1算法概述：</b></p><p>　　建立一個(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ù)x作為初始報(bào)數(shù)上限值.從定義的那個(gè)頭結(jié)點(diǎn)開始,數(shù)到x,輸出該

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

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

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

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

11、gt;　　passcode（）把josephus()里所儲(chǔ)存到數(shù)組a[i],b[i]的數(shù)據(jù)傳遞到passcode（）,方便在退出josephus()函數(shù)之后還可以再次查看。</p><p>　　about()約瑟夫環(huán)問題的解析說明，增強(qiáng)使用者對(duì)本程序的理解。</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 實(shí)驗(yàn)結(jié)果與分析</b></p><p>　　上述程序在win-TC環(huán)境下加以實(shí)現(xiàn)，經(jīng)過多次的測(cè)試，程序運(yùn)行正確。</p><p>　　4.1實(shí)驗(yàn)測(cè)試中的關(guān)鍵代碼與各模塊測(cè)試結(jié)果的分析與說明

13、</p><p>　　(1)創(chuàng)建一個(gè)彈出式主菜單下面代碼是其設(shè)計(jì)界面的代碼. 文本框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)實(shí)現(xiàn)光標(biāo)的上移和下移,其代碼文本框3所示, 其效果,請(qǐng)對(duì)比圖2和圖3.</p><p><b>　　文本框3</b></p><p>　　(3)在循環(huán)鏈表里輸入數(shù)據(jù),其實(shí)現(xiàn)代碼如文本框4所示,效果如圖4所示.</p>

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

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

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

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

20、將s=q,計(jì)數(shù)計(jì)到count==x后,這時(shí)q指向要輸出的數(shù)據(jù),再將s->next=q->next,再free(q),這樣就可以刪除對(duì)應(yīng)的結(jié)點(diǎn)了.</p><p>　　問題五:因?yàn)関 C++6.0不支持window()這個(gè)函數(shù),無法創(chuàng)建彈出式菜單,需要轉(zhuǎn)移到win-tc下. josephus()函數(shù)在v C++6.0編譯環(huán)境下運(yù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下的&改成二級(jí)指針,便可以在win-tc環(huán)境下使用了.</p><p><b

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

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

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