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

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

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

3、二0一一 年 12 月</p><p>　　題目概要：joseph環(huán)</p><p>　　任務(wù)：編號(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ù)，如此下去，直到所有人全部出列

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

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

6、4. 測(cè)試數(shù)據(jù)（1）輸入20,7輸出0 0 3 7 4 0 7 4 4</p><p>　　二、    概要設(shè)計(jì)</p><p>　　利用單向循環(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ā)均

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

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

9、edef struct LNode</p><p><b>　　{</b></p><p>　　int password; //密碼</p><p>　　int No; //序號(hào) </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; //化簡(jiǎn)m值</p><p>　　for (i=1;i<m;i++) </p><p>　　p=p->next; //p指向出列成員</p><p>　　printf ("%d\n",p->No); //輸出出列成員序號(hào)</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); //輸出最后一個(gè)成員序號(hào)</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)建一個(gè)無(wú)頭結(jié)點(diǎn)的循環(huán)鏈表，結(jié)點(diǎn)數(shù)n,*p_head返回鏈表頭指針即首結(jié)點(diǎn)地址</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; //儲(chǔ)存成員一序號(hào)</p><p>　　printf ("Please enter password of No. 1:\n"); </p><p>　　scanf ("%d",&

23、amp;(*p_head)->password); //儲(chǔ)存成員一密碼</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; //儲(chǔ)存成員序號(hào)</p><p>　　printf ("Please enter password of No. %d:\n",i);</

25、p><p>　　scanf("%d",&(p->password)); //儲(chǔ)存成員密碼</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é)點(diǎn)*pp,操作實(shí)質(zhì)是將*pp下一結(jié)點(diǎn)復(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．此程序的時(shí)間復(fù)雜度是O(m*n)。</p><p>　　2．本次設(shè)計(jì)主要用到了循環(huán)鏈表的相關(guān)知識(shí)，求joseph環(huán)的問(wèn)題。調(diào)試過(guò)程中，一開(kāi)始沒(méi)有想到“指向指針數(shù)據(jù)的指針變量”，使得問(wèn)題一直沒(méi)有明朗。</p><p>　　3．是否需要化簡(jiǎn)m值的語(yǔ)句：m=(m%n==0)?n:m%n;可根據(jù)m與總成員數(shù)的值的大小來(lái)

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

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