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

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