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

1、標(biāo)準(zhǔn)文檔實(shí)用文案數(shù)據(jù)結(jié)構(gòu)I課程設(shè)計(jì)約瑟夫環(huán)問(wèn)題2014年01月04日實(shí)用文案目錄目錄 2第1章問(wèn)題描述 3第2章基本要求 3第3章概要設(shè)計(jì) 53.1 數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì) 53.2 算法的設(shè)計(jì) 53.3 抽象數(shù)據(jù)類(lèi)型的設(shè)計(jì) 7第4章詳細(xì)設(shè)計(jì) 84.1 設(shè)計(jì)抽象數(shù)據(jù)類(lèi)型對(duì)應(yīng)的 C+我的定義 84.2 設(shè)計(jì)每個(gè)成員函數(shù) 94.3 設(shè)計(jì)主函數(shù) 10第5章運(yùn)行與測(cè)試 115.1 程序運(yùn)行環(huán)境 115.2 測(cè)試數(shù)據(jù)及測(cè)試結(jié)果 115.3 程序運(yùn)行結(jié)果截圖 11第6章總結(jié)與心得 15參考文獻(xiàn) 16附錄程序源代碼 17標(biāo)準(zhǔn)文檔實(shí)用文案第1章問(wèn)題描述編號(hào)是1,2,3n的n個(gè)人按照順時(shí)針?lè)较驀蝗?，?個(gè)人持有一個(gè)

2、密碼（正整數(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)求出出列順序。標(biāo)準(zhǔn)文檔實(shí)用文案第2章基本要求1）建立數(shù)據(jù)模型，確定存儲(chǔ)結(jié)構(gòu)；2）對(duì)任意n個(gè)人，密碼為m實(shí)現(xiàn)約瑟夫環(huán)問(wèn)題;3）出圈的順序可以依次輸出。標(biāo)準(zhǔn)文檔實(shí)用文案第3章概要設(shè)計(jì)3.1 數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)解決此問(wèn)題需要用到單鏈表的數(shù)據(jù)結(jié)構(gòu)。約瑟夫環(huán)問(wèn)題，從 確定的初報(bào)數(shù)開(kāi)始進(jìn)行，順著這一方向向前如此循環(huán)，若能找到 新的密碼m所對(duì)應(yīng)的數(shù)值則直接輸出，

3、若不能找到，繼續(xù)向下依 次尋找，直到找到密碼 m所對(duì)應(yīng)的數(shù)值，再輸出，如此循環(huán)。約 瑟夫環(huán)問(wèn)題中的數(shù)據(jù)是人所在的位置，而這種數(shù)據(jù)存在“第一元 素、最后元素”，并且存在唯一的前驅(qū)和后繼，完全符合單鏈表 的特點(diǎn)。很顯然，這需要應(yīng)用單循環(huán)鏈表的知識(shí)。單鏈表的基本思想就是用指針表示結(jié)點(diǎn)之間的邏輯關(guān)系，要 確定指針變量p,結(jié)點(diǎn)p,指針p和L。3.2 算法的設(shè)計(jì)按照模塊進(jìn)行劃分：(1)鏈表節(jié)點(diǎn)設(shè)計(jì)struct Lnodeint pwd;/ 密碼int bianhao;/ 編號(hào)struct Lnode* next;(2)采用頭插法構(gòu)造鏈表，由此必須倒著輸入個(gè)人的密碼 和編號(hào)，由此可計(jì)一個(gè)線(xiàn)性表作為緩存暫時(shí)保

4、存?zhèn)€人密碼和 編號(hào)。an=pwd o n為編號(hào)，pwd為n的人的密碼。(3)將上述2中緩存的數(shù)據(jù)從an到a1 一次賦給鏈表L：標(biāo)準(zhǔn)文檔實(shí)用文案Lnode *L,*p;L=new Lnode;L->next=NULL;for(i=num;i>0;i-)p=new Lnode;p->pwd=ai-1;p->bianhao=i;p->next=L->next;L->next=p;(4)用循環(huán)模擬報(bào)數(shù)的過(guò)程p=L ；while(num>0)for(i=1;i<m;i+)p=p->next;if(p->next=NULL)p->ne

5、xt=L->next;Lnode *temp;temp=p->next;cout<<temp->bianhao<<" n"p->next=temp->next;m=temp->pwd;free(temp);num-;num 是用來(lái)控制循環(huán)次數(shù)的變量，值為總?cè)藬?shù)n,每完成一次刪除操。即每有一個(gè)人 出列，num減1。標(biāo)準(zhǔn)文檔實(shí)用文案循環(huán)中設(shè)置了中間變量temp用來(lái)存儲(chǔ)要?jiǎng)h除的結(jié)點(diǎn)的指 針，以保證刪除操作不會(huì)導(dǎo)致鏈表指針無(wú)法找到下一結(jié)點(diǎn)。結(jié)束后 free掉temp。(5)刪除結(jié)點(diǎn)，即找到出列對(duì)象的同時(shí)輸出這個(gè)結(jié)點(diǎn)的數(shù)據(jù)域

6、：編號(hào)和密碼！3.3 抽象數(shù)據(jù)類(lèi)型的設(shè)計(jì)采用類(lèi)C語(yǔ)言定義相關(guān)的數(shù)據(jù)類(lèi)型struct Lnode(int pwd; /每個(gè)人持有的密碼int bianhao; /人員編號(hào)struct Lnode* next; /指向下一個(gè)結(jié)點(diǎn);標(biāo)準(zhǔn)文檔實(shí)用文案第4章詳細(xì)設(shè)計(jì)4.1設(shè)計(jì)抽象數(shù)據(jù)類(lèi)型對(duì)應(yīng)的C+鎂的定義(1)鏈表節(jié)點(diǎn)設(shè)計(jì)密他編號(hào)struct Lnodeint pwd;/int bianhao;/struct Lnode* next;(2)將數(shù)據(jù)從an到a1(運(yùn)用結(jié)點(diǎn)、鏈表指針)一次賦給鏈表L:Lnode *L,*p; L=new Lnode; L->next=NULL; for(i=num;i&

7、gt;0;i-) p=new Lnode; p->pwd=ai-1; p->bianhao=i; p->next=L->next; L->next=p;(3)運(yùn)用循環(huán)模擬報(bào)數(shù)過(guò)程p=L ；標(biāo)準(zhǔn)文檔實(shí)用文案while(num>0)for(i=1;i<m;i+)p=p->next;if(p->next=NULL)p->next=L->next;Lnode *temp;temp=p->next;cout<<temp->bianhao<<" n"p->next=temp-&g

8、t;next;m=temp->pwd;free(temp);num-;4.2 設(shè)計(jì)每個(gè)成員函數(shù)int pwd;int bianhao;struct Lnode* next;將密碼和編號(hào)存入程序中，通過(guò)結(jié)點(diǎn)指針對(duì)所需的數(shù)據(jù)進(jìn)行 調(diào)用。Lnode *temp找到出列對(duì)象的同時(shí)，輸出這個(gè)結(jié)點(diǎn)的數(shù)據(jù)域，存儲(chǔ)要?jiǎng)h除 結(jié)點(diǎn)，直到程序運(yùn)行完畢。標(biāo)準(zhǔn)文檔實(shí)用文案4.3 設(shè)計(jì)主函數(shù)主函數(shù)（定義輸入人數(shù)和密碼輸入相應(yīng)的初始報(bào)數(shù)輸入操作完成后，輸出相應(yīng)數(shù)據(jù)）標(biāo)準(zhǔn)文檔實(shí)用文案第5章運(yùn)行與測(cè)試5.1 程序運(yùn)行環(huán)境Windows 7系統(tǒng)下 在VC+6.0開(kāi)發(fā)平臺(tái)進(jìn)行程序的運(yùn)行與測(cè) 試。5.2 測(cè)試數(shù)據(jù)及測(cè)試結(jié)果數(shù)據(jù)

9、1：輸入人數(shù)5,初次報(bào)數(shù)3,密碼依次為：2 6 8 4 7 ，測(cè) 試結(jié)果：3 2 1 5 4數(shù)據(jù)2:輸入人數(shù)8,初次報(bào)數(shù)6,密碼依次為：3 4 8 7 1 6 45.3 ,測(cè)試結(jié)果：6 4 5 7 3 1 2 8數(shù)據(jù)3:輸入人數(shù)13,初次報(bào)數(shù)9,密碼依次為：4 6 3 7 9 8 23 1 5 7 5 8 ，測(cè)試結(jié)果：9 10 2 8 13 12 6 11 3 7 4 5 15.3程序運(yùn)行結(jié)果截圖數(shù)據(jù)1:程序清單標(biāo)準(zhǔn)文檔實(shí)用文案運(yùn)行結(jié)果：3 2 1 5 4數(shù)據(jù)2:程序清單標(biāo)準(zhǔn)文檔實(shí)用文案運(yùn)行結(jié)果：6 4 5 7 3 1 2 8數(shù)據(jù)3:程序清單標(biāo)準(zhǔn)文檔實(shí)用文案運(yùn)行結(jié)果：9 10 2 8 13 1

10、2 6 11 3 7 4 5 1標(biāo)準(zhǔn)文檔實(shí)用文案第6章總結(jié)與心得我的這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)的題目是約瑟夫環(huán)問(wèn)題，通 過(guò)對(duì)該題目的設(shè)計(jì)，使我加深了對(duì)數(shù)據(jù)結(jié)構(gòu)的理解。做什么事情，都要對(duì)認(rèn)真，既然是該你做的事，肯定是你應(yīng)該有這個(gè)能力， 即使能力不夠，也是應(yīng)該借這個(gè)機(jī)會(huì)來(lái)培養(yǎng)。所以放心大膽地做， 對(duì)自己有信心，就有動(dòng)力。有人說(shuō)，世上的事就怕認(rèn)真二字。確 實(shí)，做什么，只是認(rèn)真地去做，踏踏實(shí)實(shí)，戒躁戒躁，靜靜地思 考，慢慢地進(jìn)步，真的是天下無(wú)難事。這就是我這次課程設(shè)計(jì)中 得到的最大的體會(huì)，受益匪淺。通過(guò)課程設(shè)計(jì)我的收獲如下：1、鞏固和加深了對(duì)數(shù)據(jù)結(jié)構(gòu)的理解，提高綜合運(yùn)用本課程所學(xué)知識(shí)的能力。2、培養(yǎng)了我選用

11、參考書(shū)，查閱手冊(cè)及文獻(xiàn)資料的能力。培養(yǎng) 獨(dú)立思考，深入研究，分析問(wèn)題、解決問(wèn)題的能力。3、通過(guò)實(shí)際編譯系統(tǒng)的分析設(shè)計(jì)、編程調(diào)試，掌握應(yīng)用軟件的分析方法和工程設(shè)計(jì)方法。4、通過(guò)課程設(shè)計(jì)，培養(yǎng)了我嚴(yán)肅認(rèn)真的工作作風(fēng)，逐步建立 正確的生產(chǎn)觀念、經(jīng)濟(jì)觀念和全局觀念。根據(jù)我在課程設(shè)計(jì)中遇到得問(wèn)題，我將在以后的學(xué)習(xí)過(guò)程中注意以下幾點(diǎn)：1、認(rèn)真上好專(zhuān)業(yè)實(shí)驗(yàn)課，多在實(shí)踐中鍛煉自己。2、寫(xiě)程序的過(guò)程中要考慮周到，嚴(yán)密。3 、認(rèn)真的學(xué)習(xí)課本知識(shí)，并在此基礎(chǔ)上學(xué)會(huì)靈活運(yùn)用。標(biāo)準(zhǔn)文檔實(shí)用文案參考文獻(xiàn)1胡明，王濤 等著.數(shù)據(jù)結(jié)構(gòu)（C+誠(chéng)）M.北京：清華大 學(xué)出版社，2011.2譚浩強(qiáng) 著.C程序設(shè)計(jì)（第四版）M.北京：

12、清華大學(xué)出 版社，2005.3譚浩強(qiáng) 著.C+程序設(shè)計(jì)M.北京：清華大學(xué)出版社， 2004.標(biāo)準(zhǔn)文檔實(shí)用文案附錄程序源代碼#include<iostream>using namespace std;struct Lnodeint pwd;int bianhao;struct Lnode* next;int main()int i=0;int num,m;cout<<"輸入人數(shù)："<<"n"cin>>num;cout<<"輸入初始報(bào)數(shù)："<<"n"

13、;cin>>m;cout<<"輸入密碼："<<"n"int a100;for(i=0;i<num;i+)cin>>ai;Lnode *L,*p;L=new Lnode;L->next=NULL;for(i=num;i>0;i-)p=new Lnode;p->pwd=ai-1;p->bianhao=i;標(biāo)準(zhǔn)文檔實(shí)用文案p->next=L->next;L->next=p;)P=L；while(num>0)for(i=1;i<m;i+)p=p->next;if(p->nex