數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告-- joseph環(huán)程序設(shè)計

1、<p>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告</p><p>　　題目： Joseph環(huán)程序設(shè)計 </p><p>　　學(xué) 院： 軟件學(xué)院 </p><p>　　姓 名： ****** </p><p>　　學(xué) 號

2、： 2010**** </p><p>　　專 業(yè)： 軟件工程 </p><p>　　年 級： </p><p>　　指導(dǎo)教師： </p><p>　　

3、二0一一 年 12 月</p><p>　　題目概要：joseph環(huán)</p><p>　　任務(wù)：編號是1，2，……,n的n個人按照順時針方向圍坐一圈，每個人只有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)上限值m,從第一個仍開始順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼作為新的m值，從他在順時針方向的下一個人開始重新從1報數(shù)，如此下去，直到所有人全部出列

4、為止。設(shè)計一個程序來求出出列順序?！　∫螅豪脝蜗蜓h(huán)鏈表存儲結(jié)構(gòu)模擬此過程，按照出列的順序輸出各個人的編號。測試數(shù)據(jù)：　　m的初值為20，n=7 ,7個人的密碼依次為3，1，7，2，4，7，4，首先m=6,則正確的輸出是什么？　　要求： 輸入數(shù)據(jù)：建立輸入處理輸入數(shù)據(jù)，輸入m的初值，n ，輸入每個人的密碼，建立單循環(huán)鏈表。　　輸出形式：建立一個輸出函數(shù)，將正確的輸出序列　　</p><p>

5、　　一、    需求分析1. 輸入的形式和輸入值的范圍    本程序中，輸入報數(shù)上限值m和人數(shù)上限l，密碼，均限定為正整數(shù)，輸入的形式為一個以“回車符”為結(jié)束標(biāo)志的正整數(shù)。2. 輸出的形式    從屏幕顯示出列順序。3. 程序功能    提供用戶從鍵盤輸入，Joseph約瑟夫環(huán)的必要數(shù)據(jù)，并顯示出列順序。

6、4. 測試數(shù)據(jù)（1）輸入20,7輸出0 0 3 7 4 0 7 4 4</p><p>　　二、    概要設(shè)計</p><p>　　利用單向循環(huán)鏈表存儲結(jié)構(gòu)模擬此過程，因為循環(huán)鏈表最后一個結(jié)點的指針域指向頭結(jié)點，整個鏈表形成一人環(huán)，剛好和題中的“n個人按照順時針方向圍坐一圈，每個人只有一個密碼（正整數(shù)）”內(nèi)容要求一致，而且，循環(huán)鏈表中任一結(jié)點出發(fā)均

7、可找到表中其他結(jié)點，利用這一優(yōu)點可較容易地找出報數(shù)的人及下一個報數(shù)的人，最后按照出列的順序用一個for語句實現(xiàn)。</p><p>　　joseph環(huán)的組成成員由密碼（password）和序號(No)組成，循環(huán)鏈表的存儲結(jié)構(gòu)如下：</p><p>　　typedef struct LNode</p><p><b>　　{</b></p&g

8、t;<p>　　int password; //密碼</p><p>　　int No; //序號 </p><p>　　struct LNode *next; //下一成員指針</p><p>　　}member; //組成成員結(jié)構(gòu)體</p><p>　　三、    詳細(xì)設(shè)計typ

9、edef struct LNode</p><p><b>　　{</b></p><p>　　int password; //密碼</p><p>　　int No; //序號 </p><p>　　struct LNode *next; //下一成員指針</p><p>　　}me

10、mber; //組成成員結(jié)構(gòu)體</p><p>　　typedef int status;</p><p>　　#define OVERFLOW -2 </p><p>　　#define OK 1 </p><p>　　#define ERROR 0</p><p>　　#include <

11、stdio.h></p><p>　　#include <stdlib.h></p><p>　　status CreateList_Circle(member **,int);</p><p>　　status DeleteNode(member **);</p><p>　　status main()</p>

12、<p><b>　　{</b></p><p><b>　　int n,m;</b></p><p>　　member *head=NULL,*p=NULL; //頭指針即首成員地址，遍歷指針p</p><p>　　printf ("Please enter number of people:\n

13、");</p><p>　　scanf ("%d",&n); //總成員數(shù)</p><p>　　while (n<=0)</p><p><b>　　{</b></p><p>　　printf ("n must be positive, please enter

14、again:\n");</p><p>　　scanf ("%d",&n);</p><p><b>　　}</b></p><p>　　if(!CreateList_Circle(&head,n)) //創(chuàng)建循環(huán)鏈表，返回頭指針head</p><p>　　return

15、OVERFLOW; </p><p>　　printf ("Please enter initial m:\n");</p><p>　　scanf ("%d",&m); //初始值m</p><p>　　while (m<=0)</p><p><b>　　{</b&g

16、t;</p><p>　　printf ("m must be positive, please enter again:\n");</p><p>　　scanf ("%d",&m);</p><p><b>　　} </b></p><p>　　printf (&quo

17、t;\nThe order is:\n");</p><p><b>　　p=head;</b></p><p>　　while (n>=2) //尋找出列成員</p><p><b>　　{</b></p><p><b>　　int i;</b></

18、p><p>　　m=(m%n==0)?n:m%n; //化簡m值</p><p>　　for (i=1;i<m;i++) </p><p>　　p=p->next; //p指向出列成員</p><p>　　printf ("%d\n",p->No); //輸出出列成員序號</p><

19、;p>　　m=p->password; //修改m</p><p>　　DeleteNode(&p); //刪除鏈表中的出列成員</p><p>　　n--; //成員數(shù)自減</p><p><b>　　}</b></p><p>　　printf ("%d\n",p->

20、;No); //輸出最后一個成員序號</p><p>　　return OK;</p><p><b>　　}</b></p><p>　　status CreateList_Circle(member **p_head,int n)</p><p><b>　　{</b></p>

21、<p>　　//此算法創(chuàng)建一個無頭結(jié)點的循環(huán)鏈表，結(jié)點數(shù)n,*p_head返回鏈表頭指針即首結(jié)點地址</p><p><b>　　int i;</b></p><p>　　member *tail,*p;</p><p>　　*p_head=(member *)malloc(sizeof(member));</p>&l

22、t;p>　　if (!(*p_head)) return OVERFLOW;</p><p>　　(*p_head)->No=1; //儲存成員一序號</p><p>　　printf ("Please enter password of No. 1:\n"); </p><p>　　scanf ("%d",&

23、amp;(*p_head)->password); //儲存成員一密碼</p><p>　　tail=*p_head;</p><p>　　tail->next=NULL;</p><p>　　for (i=2;i<n+1;i++)</p><p><b>　　{</b></p><

24、;p>　　p=(member *)malloc(sizeof(member));</p><p>　　if (!p) return OVERFLOW;</p><p>　　p->No=i; //儲存成員序號</p><p>　　printf ("Please enter password of No. %d:\n",i);</

25、p><p>　　scanf("%d",&(p->password)); //儲存成員密碼</p><p>　　tail->next=p;</p><p><b>　　tail=p;</b></p><p><b>　　}</b></p><p

26、>　　tail->next=*p_head;</p><p>　　return OK;</p><p><b>　　}</b></p><p>　　status DeleteNode(member **pp)</p><p><b>　　{</b></p><p>

27、;　　//此算法刪除鏈表中的結(jié)點*pp,操作實質(zhì)是將*pp下一結(jié)點復(fù)制到*pp后將其free</p><p>　　member *temp;</p><p>　　(*pp)->password=((*pp)->next)->password;</p><p>　　(*pp)->No=((*pp)->next)->No;</p

28、><p>　　temp=(*pp)->next;</p><p>　　(*pp)->next=(*pp)->next->next;</p><p>　　free(temp);</p><p>　　return OK;</p><p><b>　　}</b></p>

29、<p>　　四、    調(diào)試分析1．此程序的時間復(fù)雜度是O(m*n)。</p><p>　　2．本次設(shè)計主要用到了循環(huán)鏈表的相關(guān)知識，求joseph環(huán)的問題。調(diào)試過程中，一開始沒有想到“指向指針數(shù)據(jù)的指針變量”，使得問題一直沒有明朗。</p><p>　　3．是否需要化簡m值的語句：m=(m%n==0)?n:m%n;可根據(jù)m與總成員數(shù)的值的大小來

30、判斷。</p><p>　　當(dāng)m〈=n時，則此步是可以刪除的；</p><p>　　當(dāng)m>n時，則此步最好不刪除，特別是當(dāng)輸入的m值很大，則化簡m值的操作是很必要。</p><p>　　4. 遇到的問題主要是：指針的指向的邊界問題，但根據(jù)運(yùn)行程序時的出錯提示，很快也就解決了。</p><p>　　五、   

31、 測試結(jié)果測試數(shù)據(jù)：m初值：20；n：7； </p><p>　　7個人的密碼依次為3，1，7，2，4，7，4；</p><p><b>　　六、總結(jié)</b></p><p>　　在此次實訓(xùn)中，對于這次的數(shù)據(jù)結(jié)構(gòu)作業(yè)感覺到了好大的壓力。我選擇的是第一個題目—Joseph環(huán)。過程中，感覺平時所學(xué)的知識都丟到了九天云外，完全無力了。不過在詢問其他