數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 約瑟夫（Joseph）環(huán)

《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 約瑟夫（Joseph）環(huán)》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 約瑟夫（Joseph）環(huán)（14頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、 課程設(shè)計(jì)說(shuō)明書(shū) NO.14 約瑟夫（Joseph）環(huán) 1.課程設(shè)計(jì)的目的 本次課程設(shè)計(jì)通過(guò)設(shè)計(jì)一完整的程序，可以掌握數(shù)據(jù)結(jié)構(gòu)的應(yīng)用、算法的編寫(xiě)、類(lèi)C語(yǔ)言的算法轉(zhuǎn)換成C程序并用TC上機(jī)調(diào)試的基本方法。應(yīng)用對(duì)數(shù)據(jù)結(jié)構(gòu)理論學(xué)習(xí)，通過(guò)上機(jī)實(shí)踐的方式將理論知識(shí)與實(shí)踐更好的結(jié)合起來(lái)，鞏固所學(xué)知識(shí)。 數(shù)據(jù)結(jié)構(gòu)是實(shí)踐性很強(qiáng)的課程，課程設(shè)計(jì)是加強(qiáng)學(xué)生實(shí)踐能力的一個(gè)有力手段。本次課程設(shè)計(jì)的目的就是要達(dá)到理論與實(shí)際的應(yīng)用相結(jié)合學(xué)會(huì)數(shù)據(jù)的組織方法，能把現(xiàn)實(shí)世界中的實(shí)際問(wèn)題在計(jì)算機(jī)內(nèi)部表現(xiàn)出來(lái)，能夠提高學(xué)生的思維能力和

2、專(zhuān)業(yè)素質(zhì)的提高，對(duì)學(xué)生基本程序設(shè)計(jì)素質(zhì)的培養(yǎng)和為以后工作打下了堅(jiān)實(shí)的基礎(chǔ)。 本次課程設(shè)計(jì)是利用利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)解決Joseph環(huán)問(wèn)題，編號(hào)是1，2，……,n的n個(gè)人按照順時(shí)針?lè)较驀蝗?，每個(gè)人只有一個(gè)密碼（正整數(shù)）。一開(kāi)始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m,從第一個(gè)仍開(kāi)始順時(shí)針?lè)较蜃?開(kāi)始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針?lè)较虻南乱粋€(gè)人開(kāi)始重新從1報(bào)數(shù)，如此下去，直到所有人全部出列為止，本次課程設(shè)計(jì)將設(shè)計(jì)一個(gè)程序來(lái)求出出列順序。 2.設(shè)計(jì)方案論證 2.1設(shè)計(jì)思路及方法 為了記錄退出的人的先后順序，采用一個(gè)順序表進(jìn)行存儲(chǔ)。程序結(jié)束

3、后再輸出依次退出的人的編號(hào)順序。由于只記錄各個(gè)結(jié)點(diǎn)的data值就可以。最后通過(guò)函數(shù)調(diào)用來(lái)輸出順序。第一步是定義結(jié)構(gòu)變量結(jié)點(diǎn)linklist，并在該結(jié)點(diǎn)下定義結(jié)點(diǎn)的元素域:data,password，指針域:lLink和rLink。然后建立一個(gè)由n個(gè)鏈結(jié)點(diǎn)，有表頭結(jié)點(diǎn)的單向循環(huán)鏈表。并由構(gòu)造函數(shù)對(duì)結(jié)點(diǎn)賦值，由隨機(jī)函數(shù)rand()產(chǎn)生每個(gè)結(jié)點(diǎn)的password。由于每個(gè)結(jié)點(diǎn)的password是由隨機(jī)函數(shù)產(chǎn)生的，也就是每個(gè)結(jié)點(diǎn)的password是后知的，所以在一開(kāi)始人為地指定一個(gè)結(jié)點(diǎn)的順序，由此結(jié)點(diǎn)開(kāi)始報(bào)數(shù)。報(bào)password個(gè)數(shù)后，報(bào)到的那個(gè)結(jié)點(diǎn)被刪除，它的password被記錄下，由它的下一個(gè)結(jié)

4、點(diǎn)開(kāi)始逆方向報(bào)數(shù)………如此循環(huán)，直到循環(huán)鏈表里只剩下一個(gè)結(jié)點(diǎn)，那就是問(wèn)題所求的結(jié)果。具體到問(wèn)題上，還需要?jiǎng)?chuàng)建一個(gè)Joseph類(lèi)，由構(gòu)造函數(shù)來(lái)初始化，輸入所有的人數(shù)，也就是表長(zhǎng)，然后指定由第幾個(gè)人開(kāi)始報(bào)數(shù)。在Joseph類(lèi)中定義一個(gè)GetWinner()函數(shù)，由它來(lái)實(shí)現(xiàn)獲得最后的勝利者。并在該類(lèi)中設(shè)置一個(gè)判斷語(yǔ)句來(lái)確定先由順時(shí)針報(bào)數(shù)并淘汰了一個(gè)人之后，再按逆時(shí)針順序報(bào)數(shù)，如此交替進(jìn)行。 創(chuàng)建一個(gè)空單向循環(huán)鏈表，單向循環(huán)鏈表和每個(gè)結(jié)點(diǎn)包括三個(gè)域:Element， lLink,rLink.其中element為元素域，rLink域?yàn)橹赶蚝罄^結(jié)點(diǎn)的指針，新增的lLink域用以指向前驅(qū)結(jié)點(diǎn)。單向鏈表帶

5、表頭結(jié)點(diǎn)，并且也可以構(gòu)成單向循環(huán)鏈表。此時(shí)，表頭結(jié)點(diǎn)的rLink，lLink分別指向雙向循環(huán)鏈表的頭結(jié)點(diǎn)(或表頭結(jié)點(diǎn))和尾結(jié)點(diǎn)。 一個(gè)結(jié)點(diǎn)的lLink域的指針指向它左邊結(jié)點(diǎn)的后部，這并不意味著該結(jié)點(diǎn)的lLink域保存的仍是該左邊結(jié)點(diǎn)存儲(chǔ)塊的起始地址。在此處，指針指向某個(gè)結(jié)點(diǎn)任何部分都是等價(jià)的，都是指該存儲(chǔ)塊的起始位置。 每當(dāng)結(jié)點(diǎn)計(jì)數(shù)到某一結(jié)點(diǎn)時(shí)，將他的前驅(qū)結(jié)點(diǎn)接到他的后繼結(jié)點(diǎn)，然后將他的密碼值password賦給計(jì)數(shù)變量，再將此結(jié)點(diǎn)刪除。如此循環(huán)下去，直到最后變?yōu)榭盏膯窝h(huán)鏈表為止。 由于當(dāng)某個(gè)人退出圓圈后，報(bào)數(shù)的工作要從下一個(gè)人開(kāi)始繼續(xù)，剩下的人仍然是圍成一個(gè)圓圈的，可以使用循環(huán)表，由

6、于退出圓圈的工作對(duì)應(yīng)著表中結(jié)點(diǎn)的刪除操作，對(duì)于這種刪除操作頻繁的情況，選用效率較高的鏈表結(jié)構(gòu)，為了程序指針每一次都指向一個(gè)具體的代表一個(gè)人的結(jié)點(diǎn)而不需要判斷，鏈表不帶頭結(jié)點(diǎn)。所以，對(duì)于所有人圍成的圓圈所對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)采用一個(gè)不帶頭結(jié)點(diǎn)的循環(huán)鏈表來(lái)描述。設(shè)頭指針為front，front始終指向頭結(jié)點(diǎn)，并定義指針current記錄當(dāng)前的結(jié)點(diǎn)。并根據(jù)具體情況移動(dòng)（順逆時(shí)針）。 開(kāi)始 輸入m,n m>0,n>0的整數(shù) 結(jié)束 輸出p→No p→next=>p i++ ii p→password=>m

7、 輸出p→No (m%n)==0?n:m%n=>m 2.2系統(tǒng)流程圖 建立含n個(gè)結(jié)點(diǎn)的鏈表且用head指向第一個(gè)元素，結(jié)點(diǎn)數(shù)據(jù)域包含password、No、以及指向下一結(jié)點(diǎn)的指針 head=>p n≥2 刪除p所指向結(jié)點(diǎn)， n- - 圖1.系統(tǒng)流程圖 2.3算法設(shè)計(jì)舉例 （1）利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬此過(guò)程，因?yàn)檠h(huán)鏈表最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一人環(huán)

8、，剛好和題中的“n個(gè)人按照順時(shí)針?lè)较驀蝗Γ總€(gè)人只有一個(gè)密碼（正整數(shù)）”內(nèi)容要求一致，而且，循環(huán)鏈表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)，利用這一優(yōu)點(diǎn)可較容易地找出報(bào)數(shù)的人及下一個(gè)報(bào)數(shù)的人，最后按照出列的順序用一個(gè)for語(yǔ)句實(shí)現(xiàn)。 joseph環(huán)的組成成員由密碼（password）和序號(hào)(No)組成，循環(huán)鏈表的存儲(chǔ)結(jié)構(gòu)如下： typedef struct LNode { int password; //密碼 int No; //序號(hào) struct LNode *next; //下一成員指針 }member; //組成成員結(jié)構(gòu)體 （2）定義結(jié)構(gòu)體類(lèi)型，其中

9、password為密碼，No為序號(hào)，將兩者均定義為整型，LNode *next為下一成員指針，具體算法如下： typedef struct LNode { int password; int No; struct LNode *next; }member; typedef int stat

10、us; （3）主函數(shù)模塊算法 程序main中調(diào)用了CreateList_Circle函數(shù)，創(chuàng)建了循環(huán)鏈表，還調(diào)用了OutNode函數(shù)實(shí)現(xiàn)了輸出。首先定義人數(shù)n，頭指針即首員地址和遍歷指針均為空，當(dāng)輸入人數(shù)小于等于0時(shí)，輸出“重新輸入”字樣，如果輸入數(shù)大于0則創(chuàng)建循環(huán)鏈表，返回頭指針。當(dāng)m小于等于0時(shí)也提示重新輸入，把head 附給q ，尋找出列成員，化簡(jiǎn)m值，k從1到m-1指向出列成員，然后修改m,刪除鏈表的出列成員，成員數(shù)自減。 具體算法如下： status main() { int n,m; member *head=N

11、ULL,*q=NULL; while (n<=0) printf ("n must be positive, please enter again:\n"); if(!CreateList_Circle(&head,n)) return OVERFLOW; while (m<=0) printf ("m must be positive, please enter again:\n"); p=head; ，

12、 while (n>=2) { int k; m=(m%n==0)?n:m%n; for (k=1;inext; m=p->password; OutNode(&q); n--; } return OK; } 3.設(shè)結(jié)果與分析

13、 3.1需求與分析 約瑟夫環(huán)問(wèn)題是一個(gè)古老的數(shù)學(xué)問(wèn)題，本次課題要求用程序語(yǔ)言的方式解決數(shù)學(xué)問(wèn)題。此問(wèn)題僅使用單循環(huán)鏈表就可以很方便解決此問(wèn)題 在建立單向循環(huán)鏈表時(shí)，因?yàn)榧s瑟夫環(huán)的大小由輸入決定。為方便操作，我們將每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域的值定為生成結(jié)點(diǎn)時(shí)的順序號(hào)和每個(gè)人持有的密碼。進(jìn)行操作時(shí)，用一個(gè)指針current指向當(dāng)前的結(jié)點(diǎn)，指針front始終指向頭結(jié)點(diǎn)。然后建立雙向循環(huán)鏈表，因?yàn)槊總€(gè)人的密碼是通過(guò)rand()函數(shù)隨機(jī)生成的，所以指定第一個(gè)人的順序號(hào)，找到結(jié)點(diǎn)，不斷地從鏈表中刪除鏈結(jié)點(diǎn)，直到鏈表剩下最后一個(gè)結(jié)點(diǎn)，通過(guò)一系列的循環(huán)就可以解決改進(jìn)約瑟夫環(huán)問(wèn)題。 3.2調(diào)試過(guò)程與分析 這次的課

14、程設(shè)計(jì)的代碼很冗長(zhǎng)，所以等有了解題思路后，把代碼都寫(xiě)上后難免會(huì)有很多錯(cuò)誤。當(dāng)?shù)谝淮伟颜麄€(gè)程序?qū)懞煤筮\(yùn)行，出現(xiàn)了很多錯(cuò)誤。不過(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)手。 在隨機(jī)設(shè)置每個(gè)結(jié)點(diǎn)的password時(shí)也曾是個(gè)問(wèn)題，因?yàn)槲易龅碾S機(jī)函數(shù)一直都用不好，要不是每次

15、隨到的都是一樣的，要么就是每次隨到的數(shù)都很大，后來(lái)通過(guò)老師的耐心講解才得以解決。 在調(diào)試的過(guò)程中，類(lèi)的優(yōu)勢(shì)很明顯，能很簡(jiǎn)單的把問(wèn)題解決，而不需要使用的其他的一些比較復(fù)雜的方法。 3.3運(yùn)行結(jié)果 3.3.1運(yùn)行程序結(jié)果 在visuar C++中運(yùn)行該程序并進(jìn)行調(diào)試，然后能夠正確輸出。 圖2.程序運(yùn)行圖 3.3.2檢測(cè)程序的可行性 （1）測(cè)試數(shù)據(jù)：m的初值為20，n=7 ,7個(gè)人的密碼依次為3，1，7，2，4，7，4。 圖3.輸入數(shù)據(jù)結(jié)果圖 （2）測(cè)試數(shù)據(jù)：m的初值

16、為20，n=7 ,7個(gè)人的密碼依次為3，1，7，2，4，7，4。運(yùn)行并輸出結(jié)果。 圖4.運(yùn)行結(jié)果圖 （3）輸入數(shù)據(jù)：建立輸入處理輸入數(shù)據(jù)，輸入m的初值為6，輸入每個(gè)人的密碼，建立單循環(huán)鏈表，輸出正確的序列。 圖5.運(yùn)行結(jié)果圖 當(dāng)程序運(yùn)行的時(shí)候會(huì)出現(xiàn)如上圖所示的提示，要求使用者輸入程序中所需的輸入總?cè)藬?shù)，使用者只需輸入自己所想的總?cè)藬?shù)，系統(tǒng)便會(huì)隨機(jī)產(chǎn)生每個(gè)人對(duì)應(yīng)的密碼，同時(shí)隨機(jī)產(chǎn)生第一次的報(bào)數(shù)上限值。最后系統(tǒng)會(huì)給出出列的次序，最后產(chǎn)生的編號(hào)便是此次游戲的獲勝者。使用者還可按下任意鍵，進(jìn)行下一次的游戲。 4.設(shè)計(jì)體會(huì)

17、 為期一周的課程設(shè)計(jì)快結(jié)束了，通過(guò)這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)，我感受最深的就是對(duì)于循環(huán)鏈表的使用，可以說(shuō)對(duì)循環(huán)鏈表有了比以前更進(jìn)一步的認(rèn)識(shí)，以前只是一知半解的，如果只給個(gè)題目自己根本不能把程序完整地編寫(xiě)出來(lái)，所以這次課程設(shè)計(jì)最大的收獲就在于對(duì)循環(huán)鏈表有了一定的理解，包括其中的一系列操作，如建立一個(gè)循環(huán)鏈表，刪除鏈表中的一個(gè)結(jié)點(diǎn)，增加一個(gè)結(jié)點(diǎn)等。 在這次課程設(shè)計(jì)過(guò)程中需要我們一邊設(shè)計(jì)一邊探索，這這個(gè)過(guò)程當(dāng)中我發(fā)現(xiàn)自己在數(shù)據(jù)結(jié)構(gòu)方面知識(shí)掌握不夠深入，對(duì)一些基本概念不能很好的理解，對(duì)一些數(shù)據(jù)結(jié)構(gòu)不能夠熟練的進(jìn)行上機(jī)實(shí)現(xiàn)，這是自己比較薄弱的。學(xué)好基礎(chǔ)知識(shí)是理論付諸實(shí)踐的前提，這樣理論和實(shí)踐才能充分地結(jié)合起

18、來(lái)。在以后的學(xué)習(xí)中，我還要努力改正，充分利用上機(jī)實(shí)驗(yàn)的機(jī)會(huì)提高自己。在程序的輸入的時(shí)候，因?yàn)樽约簩?duì)鍵盤(pán)的不熟練，代碼又很多很繁瑣，常常會(huì)產(chǎn)生放棄的念頭，從中我也感受到只有堅(jiān)持到底，勝利才會(huì)出現(xiàn)。 課程設(shè)計(jì)是培養(yǎng)我們綜合運(yùn)用所學(xué)知識(shí)，發(fā)現(xiàn)、提出、分析和解決實(shí)際問(wèn)題，鍛煉實(shí)踐能力的重要環(huán)節(jié),是對(duì)我們實(shí)際工作能力的具體訓(xùn)練和考察過(guò)程.在調(diào)試程序的時(shí)候我也有所體會(huì)，雖然約瑟夫環(huán)問(wèn)題不是很難，但調(diào)試的時(shí)候還是會(huì)出現(xiàn)很多錯(cuò)誤，因此我們不能認(rèn)為容易就不認(rèn)真對(duì)待。在以后的學(xué)習(xí)中，要能不斷發(fā)現(xiàn)問(wèn)題，提出問(wèn)題，解決問(wèn)題，從不足之處出發(fā)，在不斷學(xué)習(xí)中提高自己。 4. 參考文獻(xiàn) [1]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（

19、C語(yǔ)言版）[M].北京：清華大學(xué)出版社，2007.4：144-149 [2]蘇仕華.數(shù)據(jù)結(jié)構(gòu)與算分析[M].安徽：中國(guó)科學(xué)技術(shù)大學(xué)出版社，2004.1：94-98 [3]朱若愚.數(shù)據(jù)結(jié)構(gòu)[M].北京:電子郵電出版社,2006.1:41-65 [4]徐孝凱.數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)明教程.北京:清華大學(xué)出版社,2006.4:102-115 [5]耿國(guó)華.數(shù)據(jù)結(jié)構(gòu)-C語(yǔ)言描述[M]北京:高等教育出版社,2005.1:182-187 [6]孫輝吳,潤(rùn)秀語(yǔ).C言程序設(shè)計(jì)教程[M]北京:北京郵電出版社,2004.10:166-172 [7]許秀林,董楊琴.程序設(shè)計(jì)基礎(chǔ)教程（C語(yǔ)言與數(shù)據(jù)結(jié)構(gòu)）[M]北京:中

20、國(guó)電力出版社,2005.9:250-256 [8]王曙燕.C語(yǔ)言課程設(shè)計(jì)[M]北京:科學(xué)出版社,2005.2:159-165 附錄：源代碼 typedef struct LNode { int password; //密碼 int No; //序號(hào) struct LNode *next; //下一成員指針 }member; //組成成員結(jié)構(gòu)體 typedef int status; #define OVERFLOW -2 #define OK 1 #define ERROR 0 #include

21、.h> #include status CreateList_Circle(member **,int); status DeleteNode(member **); status main() { int n,m; member *head=NULL,*p=NULL; //頭指針即首成員地址，遍歷指針p printf ("請(qǐng)輸入人數(shù):\n"); scanf ("%d",&n); //總成員數(shù) while (n<=0) { printf ("n must be positive, please enter again:\n");

22、 scanf ("%d",&n); } if(!CreateList_Circle(&head,n)) //創(chuàng)建循環(huán)鏈表，返回頭指針head return OVERFLOW; printf ("請(qǐng)輸入m的值:\n"); scanf ("%d",&m); //初始值m while (m<=0) { printf ("m must be positive, please enter again:\n"); scanf ("%d",&m); } printf ("\nThe order is:\n"); p=head; whil

23、e (n>=2) //尋找出列成員 { int i; m=(m%n==0)?n:m%n; //化簡(jiǎn)m值 for (i=1;inext; //p指向出列成員 printf ("%d\n",p->No); //輸出出列成員序號(hào) m=p->password; //修改m DeleteNode(&p); //刪除鏈表中的出列成員 n--; //成員數(shù)自減 } printf ("%d\n",p->No); //輸出最后一個(gè)成員序號(hào) return OK; } status CreateLis

24、t_Circle(member **p_head,int n) {//此算法創(chuàng)建一個(gè)無(wú)頭結(jié)點(diǎn)的循環(huán)鏈表，結(jié)點(diǎn)數(shù)n,*p_head返回鏈表頭指針即首結(jié)點(diǎn)地址 int i; member *tail,*p; *p_head=(member *)malloc(sizeof(member)); if (!(*p_head)) return OVERFLOW; (*p_head)->No=1; //儲(chǔ)存成員一序號(hào) printf ("請(qǐng)輸入密碼. 1:\n"); scanf ("%d",&(*p_head)->password); //儲(chǔ)存成員一密碼 tail=*

25、p_head; tail->next=NULL; for (i=2;iNo=i; //儲(chǔ)存成員序號(hào) printf ("請(qǐng)輸入密碼. %d:\n",i); scanf("%d",&(p->password)); //儲(chǔ)存成員密碼 tail->next=p; tail=p; } tail->next=*p_head; return OK; } status DeleteNode(member **pp) { //此算法刪除鏈表中的結(jié)點(diǎn)*pp,操作實(shí)質(zhì)是將*pp下一結(jié)點(diǎn)復(fù)制到*pp后將其free member *temp; (*pp)->password=((*pp)->next)->password; (*pp)->No=((*pp)->next)->No; temp=(*pp)->next; (*pp)->next=(*pp)->next->next; free(temp); return OK;} 沈 陽(yáng) 大 學(xué)