《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 約瑟夫（Joseph）環(huán)》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 約瑟夫（Joseph）環(huán)（14頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、 課程設(shè)計說明書 NO.14 約瑟夫（Joseph）環(huán)1.課程設(shè)計的目的本次課程設(shè)計通過設(shè)計一完整的程序，可以掌握數(shù)據(jù)結(jié)構(gòu)的應(yīng)用、算法的編寫、類C語言的算法轉(zhuǎn)換成C程序并用TC上機調(diào)試的基本方法。應(yīng)用對數(shù)據(jù)結(jié)構(gòu)理論學習，通過上機實踐的方式將理論知識與實踐更好的結(jié)合起來，鞏固所學知識。 數(shù)據(jù)結(jié)構(gòu)是實踐性很強的課程，課程設(shè)計是加強學生實踐能力的一個有力手段。本次課程設(shè)計的目的就是要達到理論與實際的應(yīng)用相結(jié)合學會數(shù)據(jù)的組織方法，能把現(xiàn)實世界中的實際問題在計算機內(nèi)部表現(xiàn)出來，能夠提高學生的思維能力和專業(yè)素質(zhì)的提高，對學生基本程序設(shè)計素質(zhì)的培養(yǎng)和為以后工作打下了堅實的基礎(chǔ)。 本次課程設(shè)計是利用利用單向循
2、環(huán)鏈表存儲結(jié)構(gòu)解決Joseph環(huán)問題，編號是1，2，,n的n個人按照順時針方向圍坐一圈，每個人只有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)上限值m,從第一個仍開始順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼作為新的m值，從他在順時針方向的下一個人開始重新從1報數(shù)，如此下去，直到所有人全部出列為止，本次課程設(shè)計將設(shè)計一個程序來求出出列順序。2.設(shè)計方案論證2.1設(shè)計思路及方法 為了記錄退出的人的先后順序，采用一個順序表進行存儲。程序結(jié)束后再輸出依次退出的人的編號順序。由于只記錄各個結(jié)點的data值就可以。最后通過函數(shù)調(diào)用來輸出順序。第一步是定義結(jié)構(gòu)變量結(jié)點lin
3、klist，并在該結(jié)點下定義結(jié)點的元素域:data,password，指針域:lLink和rLink。然后建立一個由n個鏈結(jié)點，有表頭結(jié)點的單向循環(huán)鏈表。并由構(gòu)造函數(shù)對結(jié)點賦值，由隨機函數(shù)rand()產(chǎn)生每個結(jié)點的password。由于每個結(jié)點的password是由隨機函數(shù)產(chǎn)生的，也就是每個結(jié)點的password是后知的，所以在一開始人為地指定一個結(jié)點的順序，由此結(jié)點開始報數(shù)。報password個數(shù)后，報到的那個結(jié)點被刪除，它的password被記錄下，由它的下一個結(jié)點開始逆方向報數(shù)如此循環(huán)，直到循環(huán)鏈表里只剩下一個結(jié)點，那就是問題所求的結(jié)果。具體到問題上，還需要創(chuàng)建一個Joseph類，由構(gòu)造
4、函數(shù)來初始化，輸入所有的人數(shù)，也就是表長，然后指定由第幾個人開始報數(shù)。在Joseph類中定義一個GetWinner()函數(shù)，由它來實現(xiàn)獲得最后的勝利者。并在該類中設(shè)置一個判斷語句來確定先由順時針報數(shù)并淘汰了一個人之后，再按逆時針順序報數(shù)，如此交替進行。創(chuàng)建一個空單向循環(huán)鏈表，單向循環(huán)鏈表和每個結(jié)點包括三個域:Element，lLink,rLink.其中element為元素域，rLink域為指向后繼結(jié)點的指針，新增的lLink域用以指向前驅(qū)結(jié)點。單向鏈表帶表頭結(jié)點，并且也可以構(gòu)成單向循環(huán)鏈表。此時，表頭結(jié)點的rLink，lLink分別指向雙向循環(huán)鏈表的頭結(jié)點(或表頭結(jié)點)和尾結(jié)點。一個結(jié)點的lL
5、ink域的指針指向它左邊結(jié)點的后部，這并不意味著該結(jié)點的lLink域保存的仍是該左邊結(jié)點存儲塊的起始地址。在此處，指針指向某個結(jié)點任何部分都是等價的，都是指該存儲塊的起始位置。每當結(jié)點計數(shù)到某一結(jié)點時，將他的前驅(qū)結(jié)點接到他的后繼結(jié)點，然后將他的密碼值password賦給計數(shù)變量，再將此結(jié)點刪除。如此循環(huán)下去，直到最后變?yōu)榭盏膯窝h(huán)鏈表為止。由于當某個人退出圓圈后，報數(shù)的工作要從下一個人開始繼續(xù)，剩下的人仍然是圍成一個圓圈的，可以使用循環(huán)表，由于退出圓圈的工作對應(yīng)著表中結(jié)點的刪除操作，對于這種刪除操作頻繁的情況，選用效率較高的鏈表結(jié)構(gòu)，為了程序指針每一次都指向一個具體的代表一個人的結(jié)點而不需要判
6、斷，鏈表不帶頭結(jié)點。所以，對于所有人圍成的圓圈所對應(yīng)的數(shù)據(jù)結(jié)構(gòu)采用一個不帶頭結(jié)點的循環(huán)鏈表來描述。設(shè)頭指針為front，front始終指向頭結(jié)點，并定義指針current記錄當前的結(jié)點。并根據(jù)具體情況移動（順逆時針）。 開始輸入m,nm0,n0的整數(shù)結(jié)束輸出pNopnext=p i+ iippassword=m 輸出pNo(m%n)=0?n:m%n=m2.2系統(tǒng)流程圖建立含n個結(jié)點的鏈表且用head指向第一個元素，結(jié)點數(shù)據(jù)域包含password、No、以及指向下一結(jié)點的指針 head=p n2刪除p所指向結(jié)點， n- - 圖1.系統(tǒng)流程圖2.3算法設(shè)計舉例（1）利用單向循環(huán)鏈表存儲結(jié)構(gòu)模擬此過
7、程，因為循環(huán)鏈表最后一個結(jié)點的指針域指向頭結(jié)點，整個鏈表形成一人環(huán)，剛好和題中的“n個人按照順時針方向圍坐一圈，每個人只有一個密碼（正整數(shù)）”內(nèi)容要求一致，而且，循環(huán)鏈表中任一結(jié)點出發(fā)均可找到表中其他結(jié)點，利用這一優(yōu)點可較容易地找出報數(shù)的人及下一個報數(shù)的人，最后按照出列的順序用一個for語句實現(xiàn)。joseph環(huán)的組成成員由密碼（password）和序號(No)組成，循環(huán)鏈表的存儲結(jié)構(gòu)如下：typedef struct LNode int password; /密碼 int No; /序號 struct LNode *next; /下一成員指針member; /組成成員結(jié)構(gòu)體（2）定義結(jié)構(gòu)體類型
8、，其中password為密碼，No為序號，將兩者均定義為整型，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ù)實現(xiàn)了輸出。首先定義人數(shù)n，頭指針即首員地址和遍歷指針均為空，當輸入人數(shù)小于等于0時，輸出“重新輸入”字樣，如果輸入數(shù)大于0則創(chuàng)建循環(huán)鏈表，返回頭指針。當m小于等于0時也提示重新
9、輸入，把head 附給q ，尋找出列成員，化簡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=2) int k; m=(m%n=0)?n:m%n; for (k=1;inext; m=p-password; OutN
10、ode(&q); n-; return OK; 3.設(shè)結(jié)果與分析3.1需求與分析約瑟夫環(huán)問題是一個古老的數(shù)學問題，本次課題要求用程序語言的方式解決數(shù)學問題。此問題僅使用單循環(huán)鏈表就可以很方便解決此問題在建立單向循環(huán)鏈表時，因為約瑟夫環(huán)的大小由輸入決定。為方便操作，我們將每個結(jié)點的數(shù)據(jù)域的值定為生成結(jié)點時的順序號和每個人持有的密碼。進行操作時，用一個指針current指向當前的結(jié)點，指針front始終指向頭結(jié)點。然后建立雙向循環(huán)鏈表，因為每個人的密碼是通過rand()函數(shù)隨機生成的，所以指定第一個人的順序號，找到結(jié)點，不斷地從鏈表中刪除鏈結(jié)點，直到鏈表剩下最后一個結(jié)點，通過一系列的循環(huán)就可以解決
11、改進約瑟夫環(huán)問題。3.2調(diào)試過程與分析這次的課程設(shè)計的代碼很冗長，所以等有了解題思路后，把代碼都寫上后難免會有很多錯誤。當?shù)谝淮伟颜麄€程序?qū)懞煤筮\行，出現(xiàn)了很多錯誤。不過經(jīng)過一點點的改正，錯誤也慢慢地變少。這也說明做事要認真，尤其做計算機這方面工作的時候，因為計算機不容許不一點點的錯誤，有了一點小錯誤和有一個大錯誤在計算機看來都是一樣的，都不會得不到結(jié)果。有些小錯誤，比如說少了個分號，變量忘了定義，數(shù)據(jù)溢出等都是些小錯誤，但也不能松懈。因為要注意的地方很多，經(jīng)過多次嘗試，問題也就自然而然的解決了，而且以后遇到這方面的問題都會覺得比較得心應(yīng)手。在隨機設(shè)置每個結(jié)點的password時也曾是個問題，
12、因為我做的隨機函數(shù)一直都用不好，要不是每次隨到的都是一樣的，要么就是每次隨到的數(shù)都很大，后來通過老師的耐心講解才得以解決。在調(diào)試的過程中，類的優(yōu)勢很明顯，能很簡單的把問題解決，而不需要使用的其他的一些比較復(fù)雜的方法。3.3運行結(jié)果3.3.1運行程序結(jié)果 在visuar C+中運行該程序并進行調(diào)試，然后能夠正確輸出。 圖2.程序運行圖3.3.2檢測程序的可行性 （1）測試數(shù)據(jù)：m的初值為20，n=7 ,7個人的密碼依次為3，1，7，2，4，7，4。圖3.輸入數(shù)據(jù)結(jié)果圖（2）測試數(shù)據(jù)：m的初值為20，n=7 ,7個人的密碼依次為3，1，7，2，4，7，4。運行并輸出結(jié)果。 圖4.運行結(jié)果圖（3）輸
13、入數(shù)據(jù)：建立輸入處理輸入數(shù)據(jù)，輸入m的初值為6，輸入每個人的密碼，建立單循環(huán)鏈表，輸出正確的序列。圖5.運行結(jié)果圖當程序運行的時候會出現(xiàn)如上圖所示的提示，要求使用者輸入程序中所需的輸入總?cè)藬?shù)，使用者只需輸入自己所想的總?cè)藬?shù)，系統(tǒng)便會隨機產(chǎn)生每個人對應(yīng)的密碼，同時隨機產(chǎn)生第一次的報數(shù)上限值。最后系統(tǒng)會給出出列的次序，最后產(chǎn)生的編號便是此次游戲的獲勝者。使用者還可按下任意鍵，進行下一次的游戲。4.設(shè)計體會為期一周的課程設(shè)計快結(jié)束了，通過這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計，我感受最深的就是對于循環(huán)鏈表的使用，可以說對循環(huán)鏈表有了比以前更進一步的認識，以前只是一知半解的，如果只給個題目自己根本不能把程序完整地編寫出
14、來，所以這次課程設(shè)計最大的收獲就在于對循環(huán)鏈表有了一定的理解，包括其中的一系列操作，如建立一個循環(huán)鏈表，刪除鏈表中的一個結(jié)點，增加一個結(jié)點等。在這次課程設(shè)計過程中需要我們一邊設(shè)計一邊探索，這這個過程當中我發(fā)現(xiàn)自己在數(shù)據(jù)結(jié)構(gòu)方面知識掌握不夠深入，對一些基本概念不能很好的理解，對一些數(shù)據(jù)結(jié)構(gòu)不能夠熟練的進行上機實現(xiàn)，這是自己比較薄弱的。學好基礎(chǔ)知識是理論付諸實踐的前提，這樣理論和實踐才能充分地結(jié)合起來。在以后的學習中，我還要努力改正，充分利用上機實驗的機會提高自己。在程序的輸入的時候，因為自己對鍵盤的不熟練，代碼又很多很繁瑣，常常會產(chǎn)生放棄的念頭，從中我也感受到只有堅持到底，勝利才會出現(xiàn)。課程設(shè)計
15、是培養(yǎng)我們綜合運用所學知識，發(fā)現(xiàn)、提出、分析和解決實際問題，鍛煉實踐能力的重要環(huán)節(jié),是對我們實際工作能力的具體訓練和考察過程.在調(diào)試程序的時候我也有所體會，雖然約瑟夫環(huán)問題不是很難，但調(diào)試的時候還是會出現(xiàn)很多錯誤，因此我們不能認為容易就不認真對待。在以后的學習中，要能不斷發(fā)現(xiàn)問題，提出問題，解決問題，從不足之處出發(fā)，在不斷學習中提高自己。4. 參考文獻1嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）M.北京：清華大學出版社，2007.4：144-1492蘇仕華.數(shù)據(jù)結(jié)構(gòu)與算分析M.安徽：中國科學技術(shù)大學出版社，2004.1：94-983朱若愚.數(shù)據(jù)結(jié)構(gòu)M.北京:電子郵電出版社,2006.1:41-654
16、徐孝凱.數(shù)據(jù)結(jié)構(gòu)簡明教程.北京:清華大學出版社,2006.4:102-1155耿國華.數(shù)據(jù)結(jié)構(gòu)-C語言描述M北京:高等教育出版社,2005.1:182-1876孫輝吳,潤秀語.C言程序設(shè)計教程M北京:北京郵電出版社,2004.10:166-1727許秀林,董楊琴.程序設(shè)計基礎(chǔ)教程（C語言與數(shù)據(jù)結(jié)構(gòu)）M北京:中國電力出版社,2005.9:250-2568王曙燕.C語言課程設(shè)計M北京:科學出版社,2005.2:159-165附錄：源代碼typedef struct LNode int password; /密碼 int No; /序號 struct LNode *next; /下一成員指針memb
17、er; /組成成員結(jié)構(gòu)體typedef int status;#define OVERFLOW -2 #define OK 1 #define ERROR 0#include #include status CreateList_Circle(member *,int);status DeleteNode(member *);status main() int n,m; member *head=NULL,*p=NULL; /頭指針即首成員地址，遍歷指針p printf (請輸入人數(shù):n); scanf (%d,&n); /總成員數(shù) while (n=0) printf (n must be
18、positive, please enter again:n); scanf (%d,&n); if(!CreateList_Circle(&head,n) /創(chuàng)建循環(huán)鏈表，返回頭指針head return OVERFLOW; printf (請輸入m的值:n); scanf (%d,&m); /初始值m while (m=2) /尋找出列成員 int i; m=(m%n=0)?n:m%n; /化簡m值 for (i=1;inext; /p指向出列成員 printf (%dn,p-No); /輸出出列成員序號 m=p-password; /修改m DeleteNode(&p); /刪除鏈表中的
19、出列成員 n-; /成員數(shù)自減 printf (%dn,p-No); /輸出最后一個成員序號 return OK;status CreateList_Circle(member *p_head,int n)/此算法創(chuàng)建一個無頭結(jié)點的循環(huán)鏈表，結(jié)點數(shù)n,*p_head返回鏈表頭指針即首結(jié)點地址 int i; member *tail,*p; *p_head=(member *)malloc(sizeof(member); if (!(*p_head) return OVERFLOW; (*p_head)-No=1; /儲存成員一序號 printf (請輸入密碼. 1:n); scanf (%d,
20、&(*p_head)-password); /儲存成員一密碼 tail=*p_head; tail-next=NULL; for (i=2;iNo=i; /儲存成員序號 printf (請輸入密碼. %d:n,i); scanf(%d,&(p-password); /儲存成員密碼 tail-next=p; tail=p; tail-next=*p_head; return OK;status DeleteNode(member *pp) /此算法刪除鏈表中的結(jié)點*pp,操作實質(zhì)是將*pp下一結(jié)點復(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;沈 陽 大 學
數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 約瑟夫（Joseph）環(huán)
