約瑟夫環(huán)課程設計實驗報告

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：11 大小：131.50KB 人氣指數(shù)：12 舉報 版權申訴

已閱讀1頁，還剩10頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權，請進行舉報或認領

文檔簡介

1、　　《數(shù)據(jù)結(jié)構(gòu)》　　課程設計報告　　2011年12月18日　　目錄　　1 課程設計的目的………………………………………………………………2

2、　　2 需求分析………………………………………………………………………2　　3 課程設計報告內(nèi)容……………………………………………………………3　　1、概要設計……………………………………………………………………3　　2、詳細設計……………………………………………………………………3<

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

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

5、lt;p>　　初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設計、程序編碼、測試等基本方法和技能；　　提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力；　　需求分析　　1、問題描述：　　編號是

6、1，2，……,n的n個人按照順時針方向圍坐一圈，每個人只有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)上限值m,從第一個仍開始順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼作為新的m值，從他在順時針方向的下一個人開始重新從1報數(shù)，如此下去，直到所有人全部出列為止。設計一個程序來求出出列順序。　　2、要求：&

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

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

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

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

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

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

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

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

15、>　　cout<<"請輸入密碼:"<<endl;　　cin>>head->code;　　head->next=head;　　}<b&

16、gt;　　else　　{　　head=elem=new LinkNode;　　head->data=1; 　　cout<<"請依次輸入各個密碼:"<<end

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

37、de　　{　　int data;　　int code;　　LinkNode *next;　　};&

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

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

40、* head; 　　LinkNode* elem; 　　int len; 　　};　　LinkList::LinkList() 　　{&l

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

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

43、lt;<"請輸入密碼:"<<endl;　　cin>>head->code;　　head->next=head;　　}　　else<

44、;/p>　　{　　head=elem=new LinkNode;　　head->data=1; 　　cout<<"請依次輸入各個密碼:"<<endl;

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

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

47、　　}　　q->next=head;　　}　　len=number;　　}　　int L

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

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

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

51、gt;　　len--;　　return out;　　}　　else　　{　　L

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

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

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

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

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

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

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

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

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

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

62、>　　L.Joseph(code);　　return 0;　　}　　4、小結(jié)　　一、這次課程設計的心得體會通過實踐我的收獲如下：

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

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

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責。
6. 下載文件中如有侵權或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

約瑟夫環(huán)課程設計實驗報告

文檔簡介

溫馨提示

最新文檔

評論

約瑟夫環(huán)課程設計實驗報告

文檔簡介

溫馨提示

最新文檔

評論

免費下載