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

課程設(shè)計(jì)說(shuō)明書(shū) NO.14 約瑟夫（Joseph）環(huán)1.課程設(shè)計(jì)的目的本次課程設(shè)計(jì)通過(guò)設(shè)計(jì)一完整的程序，可以掌握數(shù)據(jù)結(jié)構(gòu)的應(yīng)用、算法的編寫、類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é)生的思維能力和專業(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é)束后再輸出依次退出的人的編號(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é)點(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類，由構(gòu)造函數(shù)來(lái)初始化，輸入所有的人數(shù)，也就是表長(zhǎng)，然后指定由第幾個(gè)人開(kāi)始報(bào)數(shù)。在Joseph類中定義一個(gè)GetWinner()函數(shù)，由它來(lái)實(shí)現(xiàn)獲得最后的勝利者。并在該類中設(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)。單向鏈表帶表頭結(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)表，由于退出圓圈的工作對(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,nm>0,n>0的整數(shù)結(jié)束輸出pNopnext=>p i+ i<m 1=>ippassword=>m 輸出pNo(m%n)=0?n:m%n=>m2.2系統(tǒng)流程圖建立含n個(gè)結(jié)點(diǎn)的鏈表且用head指向第一個(gè)元素，結(jié)點(diǎn)數(shù)據(jù)域包含password、No、以及指向下一結(jié)點(diǎn)的指針 head=>p n2刪除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)，剛好和題中的“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)體類型，其中password為密碼，No為序號(hào)，將兩者均定義為整型，LNode *next為下一成員指針，具體算法如下： typedef struct LNode int password; int No; struct LNode *next; member; typedef int status; （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=NULL,*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; ， while (n>=2) int k; m=(m%n=0)?n:m%n; for (k=1;i<m;k+) p=p->next; m=p->password; OutNode(&q); n-; return OK; 3.設(shè)結(jié)果與分析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ò)程與分析這次的課程設(shè)計(jì)的代碼很冗長(zhǎng)，所以等有了解題思路后，把代碼都寫上后難免會(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ù)一直都用不好，要不是每次隨到的都是一樣的，要么就是每次隨到的數(shù)都很大，后來(lái)通過(guò)老師的耐心講解才得以解決。在調(diào)試的過(guò)程中，類的優(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的初值為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ì)為期一周的課程設(shè)計(jì)快結(jié)束了，通過(guò)這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)，我感受最深的就是對(duì)于循環(huán)鏈表的使用，可以說(shuō)對(duì)循環(huán)鏈表有了比以前更進(jìn)一步的認(rèn)識(shí)，以前只是一知半解的，如果只給個(gè)題目自己根本不能把程序完整地編寫出來(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é)合起來(lái)。在以后的學(xué)習(xí)中，我還要努力改正，充分利用上機(jī)實(shí)驗(yàn)的機(jī)會(huì)提高自己。在程序的輸入的時(shí)候，因?yàn)樽约簩?duì)鍵盤的不熟練，代碼又很多很繁瑣，常常會(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)（C語(yǔ)言版）M.北京：清華大學(xué)出版社，2007.4：144-1492蘇仕華.數(shù)據(jù)結(jié)構(gòu)與算分析M.安徽：中國(guó)科學(xué)技術(shù)大學(xué)出版社，2004.1：94-983朱若愚.數(shù)據(jù)結(jié)構(gòu)M.北京:電子郵電出版社,2006.1:41-654徐孝凱.數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)明教程.北京:清華大學(xué)出版社,2006.4:102-1155耿國(guó)華.數(shù)據(jù)結(jié)構(gòu)-C語(yǔ)言描述M北京:高等教育出版社,2005.1:182-1876孫輝吳,潤(rùn)秀語(yǔ).C言程序設(shè)計(jì)教程M北京:北京郵電出版社,2004.10:166-1727許秀林,董楊琴.程序設(shè)計(jì)基礎(chǔ)教程（C語(yǔ)言與數(shù)據(jù)結(jié)構(gòu)）M北京:中國(guó)電力出版社,2005.9:250-2568王曙燕.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 <stdio.h>#include <stdlib.h>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"); 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; while (n>=2) /尋找出列成員 int i; m=(m%n=0)?n:m%n; /化簡(jiǎn)m值 for (i=1;i<m;i+) p=p->next; /p指向出列成員 printf ("%dn",p->No); /輸出出列成員序號(hào) m=p->password; /修改m DeleteNode(&p); /刪除鏈表中的出列成員 n-; /成員數(shù)自減 printf ("%dn",p->No); /輸出最后一個(gè)成員序號(hào) return OK;status CreateList_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=*p_head; tail->next=NULL; for (i=2;i<n+1;i+) p=(member *)malloc(sizeof(member); if (!p) return OVERFLOW; p->No=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é)