約瑟夫環(huán)課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告

1、<p><b>　　《數(shù)據(jù)結(jié)構(gòu)》</b></p><p><b>　　課程設(shè)計(jì)報(bào)告</b></p><p>　　2011年12月18日</p><p>　　目 錄</p><p>　　1 課程設(shè)計(jì)的目的………………………………………………………………2</p>

2、<p>　　2 需求分析………………………………………………………………………2</p><p>　　3 課程設(shè)計(jì)報(bào)告內(nèi)容……………………………………………………………3</p><p>　　1、概要設(shè)計(jì)……………………………………………………………………3</p><p>　　2、詳細(xì)設(shè)計(jì)……………………………………………………………………3<

3、;/p><p>　　3、調(diào)試分析……………………………………………………………………x</p><p>　　4、用戶手冊(cè)……………………………………………………………………x</p><p>　　5、測(cè)試結(jié)果……………………………………………………………………6</p><p>　　6、程序清單……………………………………………………………………

4、7</p><p>　　4 小結(jié) …………………………………………………………………………10</p><p><b>　　課程設(shè)計(jì)的目的</b></p><p>　　熟練使用C++編寫程序，解決實(shí)際問(wèn)題；</p><p>　　了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力；</p>&

5、lt;p>　　初步掌握軟件開(kāi)發(fā)過(guò)程的問(wèn)題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試等基本方法和技能；</p><p>　　提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問(wèn)題的能力；</p><p><b>　　需求分析</b></p><p><b>　　1、問(wèn)題描述：</b></p><p>　　編號(hào)是

6、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ì)一個(gè)程序來(lái)求出出列順序。</p><p><b>　　2、要求：</b></p>&

7、lt;p>　　利用不帶表頭結(jié)點(diǎn)的單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬此過(guò)程，按照出列的順序輸出各個(gè)人的編號(hào)。</p><p><b>　　3、測(cè)試數(shù)據(jù)：</b></p><p>　　m的初值為20，n=7 ,7個(gè)人的密碼依次為3，1，7，2，4，7，4，首先m=6,則正確的輸出是什么？</p><p>　　輸出形式：建立一個(gè)輸出函數(shù)，將正確的輸出序列

8、</p><p>　　3、課程設(shè)計(jì)報(bào)告內(nèi)容</p><p><b>　　概要設(shè)計(jì)：</b></p><p>　　在理解了題目后，我先想到的是我們所學(xué)的單鏈表，利用單鏈表先建立循環(huán)鏈表進(jìn)行存貯，建立完循環(huán)鏈表后，我將所要編寫的函數(shù)分為了兩塊，一塊是經(jīng)過(guò)學(xué)過(guò)的單鏈表改編的循環(huán)鏈表的基本操作函數(shù)，還有一塊是運(yùn)行約瑟夫環(huán)的函數(shù)。</p>

9、<p><b>　　詳細(xì)設(shè)計(jì)：</b></p><p>　　我先建立一個(gè)結(jié)構(gòu)體，與單鏈表一樣，只是多了一個(gè)存密碼的code域</p><p>　　struct LinkNode</p><p><b>　　{</b></p><p>　　int data; //順序</p>

10、<p>　　int code; //密碼</p><p>　　LinkNode *next; </p><p><b>　　};</b></p><p>　　建立一個(gè)類LinkList ,包含的函數(shù)：</p><p>　　LinkList(); //構(gòu)造函數(shù)</p><

11、p>　　void Creat(const int ); //創(chuàng)建循環(huán)鏈表</p><p>　　int Delete(LinkNode* ); //刪除報(bào)到數(shù)的結(jié)點(diǎn)</p><p>　　int Joseph(int ); // 約瑟夫環(huán)</p><p><b>　　私有成員是</b></p><p

12、>　　LinkNode* head; //指向第一個(gè)結(jié)點(diǎn)的指針</p><p>　　LinkNode* elem; // 同上</p><p>　　int len; //長(zhǎng)度</p><p>　　我定義了一個(gè)elem指針是為了約瑟夫環(huán)里運(yùn)行方便，elem只在約瑟夫環(huán)這個(gè)函數(shù)里用到，其他函數(shù)沒(méi)有特別大的用處。</p><p&

13、gt;　　構(gòu)造函數(shù)與書(shū)上的沒(méi)什么大差別，創(chuàng)建循環(huán)鏈表時(shí)，要考慮幾個(gè)問(wèn)題，一個(gè)是題目要求是不帶頭結(jié)點(diǎn)，所以head指針直接指向了第一個(gè)結(jié)點(diǎn)，我在創(chuàng)建鏈表時(shí)把第一個(gè)結(jié)點(diǎn)初始化data為1，表明這個(gè)結(jié)點(diǎn)是第一個(gè)結(jié)點(diǎn)。具體如下：</p><p>　　void LinkList::Creat(const int number) //number為結(jié)點(diǎn)個(gè)數(shù)，也就是參與的人數(shù)</p><p>

14、<b>　　{ </b></p><p>　　if(number==1) //只有一個(gè)人的情況</p><p><b>　　{</b></p><p>　　head=elem=new LinkNode; </p><p>　　head->data=1; </p

15、><p>　　cout<<"請(qǐng)輸入密碼:"<<endl;</p><p>　　cin>>head->code;</p><p>　　head->next=head;</p><p><b>　　}</b></p><p><b&

16、gt;　　else</b></p><p><b>　　{</b></p><p>　　head=elem=new LinkNode;</p><p>　　head->data=1; </p><p>　　cout<<"請(qǐng)依次輸入各個(gè)密碼:"<<end

17、l;</p><p>　　cin>>head->code;</p><p>　　LinkNode*q=head;</p><p><b>　　q=head;</b></p><p>　　for(int i=1;i<number;i++) //將每個(gè)結(jié)點(diǎn)鏈接上，在鏈接時(shí)填入密碼</p>

18、;<p><b>　　{</b></p><p>　　LinkNode*p=new LinkNode;</p><p>　　p->data=i+1; </p><p>　　cin>>p->code;</p><p>　　q->next=p;</p><

19、;p><b>　　q=p;</b></p><p><b>　　}</b></p><p>　　q->next=head; //構(gòu)成循環(huán)鏈表</p><p><b>　　}</b></p><p>　　len=number;</p><p

20、><b>　　}</b></p><p>　　在構(gòu)建約瑟夫環(huán)的執(zhí)行函數(shù)時(shí)，我首先考慮了遞歸調(diào)用的函數(shù)，原本的這個(gè)程序的所有的都定為elemtype類型的，雖然編譯沒(méi)出錯(cuò)，但是在連接時(shí)發(fā)生了錯(cuò)誤，在老師的指導(dǎo)下改成了具體的int型。</p><p>　　int LinkList::Joseph(int m)</p><p><b>

21、;　　{</b></p><p><b>　　if(len>1)</b></p><p><b>　　{ </b></p><p>　　LinkNode *q;</p><p>　　if(m==1) //在初始報(bào)數(shù)為1的情況下</p><p><

22、b>　　{</b></p><p><b>　　q=elem;</b></p><p>　　int a=q->code; //將選中的結(jié)點(diǎn)的密碼記錄在a中</p><p>　　elem=elem->next;</p><p>　　cout<<Delete(q)<<

23、endl; //Delete函數(shù)是為了將已經(jīng)報(bào)過(guò)數(shù)的人刪除Joseph(a); //用已經(jīng)刪除的結(jié)點(diǎn)的存的密碼作為下一次循環(huán)的報(bào)數(shù)值</p><p><b>　　}</b></p><p>　　else //一般情況下</p><p><b>　　{</b></p><p>　　

24、for(int i=1;i<m;i++)</p><p>　　elem=elem->next; //找到需要出列的結(jié)點(diǎn)</p><p><b>　　q=elem;</b></p><p>　　elem=elem->next; //此處的elem指針指向要?jiǎng)h除的結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，下次遞歸調(diào)用時(shí)從這里開(kāi)始向下循環(huán)報(bào)數(shù)</

25、p><p>　　int a=q->code;</p><p>　　cout<<Delete(q)<<endl;</p><p>　　Joseph(a);</p><p><b>　　}</b></p><p><b>　　}</b></p>

26、;<p>　　else //在只有一個(gè)結(jié)點(diǎn)的情況下</p><p>　　cout<<head->data;</p><p><b>　　}</b></p><p>　　最后還有一個(gè)Delete函數(shù)，在刪除結(jié)點(diǎn)的時(shí)候要考慮幾個(gè)特殊情況，頭尾結(jié)點(diǎn)。刪除第一個(gè)結(jié)點(diǎn)時(shí)，需要將head指針下移，尾結(jié)點(diǎn)的next也要指向

27、第二個(gè)結(jié)點(diǎn)；刪除尾結(jié)點(diǎn)時(shí)，要將尾結(jié)點(diǎn)前的結(jié)點(diǎn)與第一個(gè)結(jié)點(diǎn)相連。在設(shè)計(jì)這個(gè)函數(shù)時(shí)，我只考慮了當(dāng)len大于1的情況，在只剩下一個(gè)結(jié)點(diǎn)時(shí)，不必要?jiǎng)h除，直接輸出data的值即可（在約瑟夫函數(shù)中有寫）。具體函數(shù)如下：</p><p>　　int LinkList::Delete(LinkNode *a) </p><p><b>　　{</b></p><

28、;p>　　if(len>1) //只考慮長(zhǎng)度大于1的情況</p><p><b>　　{</b></p><p>　　if(head==a)</p><p><b>　　{</b></p><p>　　int out=head->data;</p><p>

29、;　　LinkNode* q=head;</p><p>　　while(q->next!=head)</p><p><b>　　{</b></p><p>　　q=q->next;</p><p><b>　　}</b></p><p>　　q->nex

30、t=head->next;</p><p>　　head=head->next;</p><p><b>　　delete a;</b></p><p>　　len--; //用len記錄刪除后的循環(huán)鏈表的長(zhǎng)度</p><p>　　return out;</p><p><

31、b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　LinkNode* q=head;</p><p>　　int out=a->data;</p><p>　　while(q-

32、>next!=a)</p><p><b>　　{</b></p><p>　　q=q->next;</p><p><b>　　}</b></p><p>　　if(a->next=head) .//刪除的是尾結(jié)點(diǎn)時(shí)（不知道為什么我寫程序里總是編譯出現(xiàn)錯(cuò)誤）</p>

33、<p><b>　　{</b></p><p>　　q->next=head; //重新鏈接</p><p><b>　　delete a;</b></p><p><b>　　len--;</b></p><p>　　return out;</p

34、><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　q->next=a->next;</p><p><b>　　delete a;</b&g

35、t;</p><p><b>　　len--;</b></p><p>　　return out;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p&

36、gt;<p><b>　　}</b></p><p><b>　　5、測(cè)試結(jié)果：</b></p><p><b>　　6 程序清單：</b></p><p>　　#include <iostream.h></p><p>　　struct LinkNo

37、de</p><p><b>　　{</b></p><p><b>　　int data;</b></p><p><b>　　int code;</b></p><p>　　LinkNode *next;</p><p><b>　　};&

38、lt;/b></p><p>　　class LinkList</p><p><b>　　{</b></p><p><b>　　public:</b></p><p>　　LinkList(); </p><p>　　void Creat(const i

39、nt );</p><p>　　//~LinkList(); </p><p>　　int Delete(LinkNode* ); </p><p>　　int Joseph(int ); </p><p><b>　　private:</b></p><p>　　LinkNode

40、* head; </p><p>　　LinkNode* elem; </p><p>　　int len; </p><p><b>　　};</b></p><p>　　LinkList::LinkList() </p><p><b>　　{</b>&l

41、t;/p><p>　　head=elem=NULL;</p><p><b>　　len=0;</b></p><p><b>　　}</b></p><p>　　void LinkList::Creat(const int number) </p><p><b

42、>　　{ </b></p><p>　　if(number==1)</p><p><b>　　{</b></p><p>　　head=elem=new LinkNode; </p><p>　　head->data=1; </p><p>　　cout&

43、lt;<"請(qǐng)輸入密碼:"<<endl;</p><p>　　cin>>head->code;</p><p>　　head->next=head;</p><p><b>　　}</b></p><p><b>　　else</b><

44、;/p><p><b>　　{</b></p><p>　　head=elem=new LinkNode;</p><p>　　head->data=1; </p><p>　　cout<<"請(qǐng)依次輸入各個(gè)密碼:"<<endl;</p><p>

45、;　　cin>>head->code;</p><p>　　LinkNode*q=head;</p><p><b>　　q=head;</b></p><p>　　for(int i=1;i<number;i++) </p><p><b>　　{</b></p&

46、gt;<p>　　LinkNode*p=new LinkNode;</p><p>　　p->data=i+1; </p><p>　　cin>>p->code;</p><p>　　q->next=p;</p><p><b>　　q=p;</b></p>

47、<p><b>　　}</b></p><p>　　q->next=head;</p><p><b>　　}</b></p><p>　　len=number;</p><p><b>　　}</b></p><p>　　int L

48、inkList::Delete(LinkNode *a) </p><p><b>　　{</b></p><p><b>　　if(len>1)</b></p><p><b>　　{</b></p><p>　　if(head==a)</p><

49、;p><b>　　{</b></p><p>　　int out=head->data;</p><p>　　LinkNode* q=head;</p><p>　　while(q->next!=head)</p><p><b>　　{</b></p><p&

50、gt;　　q=q->next;</p><p><b>　　}</b></p><p>　　q->next=head->next;</p><p>　　head=head->next;</p><p><b>　　delete a;</b></p><p&

51、gt;<b>　　len--;</b></p><p>　　return out;</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　L

52、inkNode* q=head;</p><p>　　int out=a->data;</p><p>　　while(q->next!=a)</p><p><b>　　{</b></p><p>　　q=q->next;</p><p><b>　　}</b&

53、gt;</p><p>　　q->next=a->next;</p><p><b>　　delete a;</b></p><p><b>　　len--;</b></p><p>　　return out; </p><p><b>　　}<

54、;/b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　int LinkList::Joseph(int m)</p><p><b>　　{</b></p><p><b>　　if

55、(len>1)</b></p><p><b>　　{ </b></p><p>　　LinkNode *q;</p><p><b>　　if(m==1)</b></p><p><b>　　{</b></p><p><b&

56、gt;　　q=elem;</b></p><p>　　int a=q->code;</p><p>　　elem=elem->next;</p><p>　　cout<<Delete(q)<<endl;</p><p>　　Joseph(a);</p><p><b

57、>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　for(int i=1;i<m;i++)</p><p>　　elem=elem->next; </p><p><

58、b>　　q=elem;</b></p><p>　　elem=elem->next;</p><p>　　int a=q->code;</p><p>　　cout<<Delete(q)<<endl;</p><p>　　Joseph(a);</p><p><

59、;b>　　}</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p>　　cout<<head->data;</p><p><b>　　}</b></p><p&g

60、t;　　int main()</p><p><b>　　{</b></p><p>　　int num,code;</p><p>　　cout<<"請(qǐng)輸入人數(shù): ";</p><p>　　cin>>num; </p><p>　　LinkList L

61、; </p><p>　　L.Creat(num);</p><p>　　cout<<"請(qǐng)輸入第一個(gè)上限數(shù): ";</p><p>　　cin>>code;</p><p>　　cout<<"出列順序:"<<endl;</p><p

62、>　　L.Joseph(code);</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p><b>　　4、小結(jié)</b></p><p>　　一、這次課程設(shè)計(jì)的心得體會(huì)通過(guò)實(shí)踐我的收獲如下：</p>

63、<p>　　一開(kāi)始接觸數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)真的挺難的，好多都不會(huì)，不是邏輯方面的問(wèn)題，而是不具備動(dòng)手能力，腦子里總有一團(tuán)火，比如對(duì)于這個(gè)題目，一開(kāi)始有很多的想法，想到了從邏輯上怎么實(shí)現(xiàn)他，要編寫哪些程序，但是一到需要編寫了就開(kāi)始為難了，可以說(shuō)是幾乎不知道從哪里入手，參考了書(shū)本里的程序，仿照他的結(jié)構(gòu)一步一步做下來(lái)，現(xiàn)在對(duì)于單鏈表的各種操作已經(jīng)算是比較熟練了，讓我知道光有理論知識(shí)還遠(yuǎn)遠(yuǎn)不夠，需要多動(dòng)手，寫的多了自然就能手到擒來(lái)。<

64、;/p><p>　　二、根據(jù)我在實(shí)習(xí)中遇到得問(wèn)題，我將在以后的學(xué)習(xí)過(guò)程中注意以下幾點(diǎn)：</p><p>　　1、認(rèn)真上好專業(yè)實(shí)驗(yàn)課，多在實(shí)踐中鍛煉自己。</p><p>　　2、寫程序的過(guò)程中要考慮周到，嚴(yán)密。</p><p>　　3、在做設(shè)計(jì)的時(shí)候要有信心，有耐心，切勿浮躁。</p><p>　　4、認(rèn)真的學(xué)習(xí)課本知識(shí)，