數(shù)據(jù)結(jié)構(gòu)Ⅰ課程設(shè)計(jì)

1、 約瑟夫環(huán)-數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 約瑟夫環(huán)問(wèn)題 日04月01年2014 目 錄 目 錄 . 3 第1章 問(wèn)題描述 . 5 第2章 基本要求 . 5 第3章 概要設(shè)計(jì) . 7 3.1 數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì) . 7 3.2 算法的設(shè)計(jì) . 7 3.3抽象數(shù)據(jù)類(lèi)型的設(shè)計(jì) . 9 第4章 詳細(xì)設(shè)計(jì) . 10 4.1設(shè)計(jì)抽象數(shù)據(jù)類(lèi)型對(duì)應(yīng)的C+類(lèi)的定義 . 10 4.2 設(shè)計(jì)每個(gè)成員函數(shù) . 11 4.3設(shè)計(jì)主函數(shù) . 12 第5章 運(yùn)行與測(cè)試 . 13 5.1程序運(yùn)行環(huán)境 . 13 5.2測(cè)試數(shù)據(jù)及測(cè)試結(jié)果 . 13 5.3程序運(yùn)行結(jié)果截圖 . 13 3 第3章 概要設(shè)計(jì)要設(shè)計(jì) 第6章 總結(jié)與心

2、得 . 17 參考文獻(xiàn) . 18 附錄 程序源代碼 . 19 4 第1章 問(wèn)題描述 第1章 問(wèn)題描述編號(hào)1,2,個(gè)人按照順時(shí)針?lè)较驀蝗γ咳顺钟幸粋€(gè)密碼（正整數(shù)）。一開(kāi)始任選一個(gè)正整數(shù)作為報(bào)數(shù)限從第一個(gè)人開(kāi)始順時(shí)針?lè)较蜷_(kāi)始順序報(bào)數(shù)報(bào)時(shí)停止報(bào)數(shù)。的人出列，將他的密碼作為新值，從在順時(shí)針?lè)较虻南乱粋€(gè)人開(kāi)始重新報(bào)數(shù)，如此下去，直到有人全部出列為止。設(shè)計(jì)一個(gè)程序來(lái)求出出列順序5 第2章 基本要求 第2章 基本要求 1) 建立數(shù)據(jù)模型，確定存儲(chǔ)結(jié)構(gòu)； 2) 對(duì)任意n個(gè)人，密碼為m，實(shí)現(xiàn)約瑟夫環(huán)問(wèn)題； 3) 出圈的順序可以依次輸出。 6 第3章 概要設(shè)計(jì) 第3章 概要設(shè)計(jì) 3.1 數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì) 解決此

3、問(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ù)值則直接輸出，若不能找到，繼續(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 Lnode int pwd;/密碼 int bianhao;/

4、編號(hào) struct Lnode* next; ; （2）采用頭插法構(gòu)造鏈表，由此必須倒著輸入個(gè)人的密碼 和編號(hào)，由此可計(jì)一個(gè)線性表作為緩存暫時(shí)保存?zhèn)€人密碼和編號(hào)。an=pwd。n為編號(hào)，pwd為n的人的密碼。 （3）將上述2中緩存的數(shù)據(jù)從an到a1一次賦給鏈表L： 7 第3章 概要設(shè)計(jì) Lnode *L,*p; L=new Lnode; L-next=NULL; for(i=num;i0;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(num0) for(i=

5、1;inext; if(p-next=NULL) p-next=L-next; Lnode *temp; temp=p-next; coutbianhaonext=temp-next; m=temp-pwd; free(temp); num-; num是用來(lái)控制循環(huán)次數(shù)的變量，值為總?cè)藬?shù)n，每完成一次刪除操。 即每有一個(gè)人出列，num減1。 8 第3章 概要設(shè)計(jì) 循環(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ù)域：編號(hào) 和密碼！ 3.3抽象數(shù)據(jù)類(lèi)型的設(shè)計(jì)

6、采用類(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) ; 9 運(yùn)行與測(cè)試細(xì)設(shè)計(jì) 第5章第4章 詳細(xì)設(shè)計(jì)4.設(shè)計(jì)抽象數(shù)據(jù)類(lèi)型對(duì)應(yīng)C+類(lèi)的定）鏈表節(jié)點(diǎn)設(shè)struct Lnodeint pwd;/密int bianhao;/編struct Lnode* next;將數(shù)據(jù)ana1（運(yùn)用結(jié)點(diǎn)鏈表指針一次賦給Lnode *L,*p;L=new Lnode;L-next=NULL;for(i=num;i0;i-)p=new Lnode;p-pwd=ai-1;p-bianh

7、ao=i;p-next=L-next;L-next=p;）運(yùn)用循環(huán)模擬報(bào)數(shù)過(guò)p= 第5章 運(yùn)行與測(cè)試 while(num0) for(i=1;inext; if(p-next=NULL) p-next=L-next; Lnode *temp; temp=p-next; coutbianhaonext=temp-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í)，輸

8、出這個(gè)結(jié)點(diǎn)的數(shù)據(jù)域，存儲(chǔ)要?jiǎng)h除結(jié)點(diǎn)，直到程序運(yùn)行完畢。 11 第5章 運(yùn)行與測(cè)試 4.3設(shè)計(jì)主函數(shù) 主函數(shù) 定義輸入人數(shù)和密碼 輸入相應(yīng)的初始報(bào)數(shù) 輸入操作完成后，輸出相應(yīng)數(shù)據(jù) 12 第5章 運(yùn)行與測(cè)試 第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ù)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 4 5 ，測(cè)試結(jié)果：6 4 5 7 3 1 2 8 數(shù)據(jù)3：輸入人數(shù)13，初次報(bào)數(shù)9，密碼

9、依次為： 4 6 3 7 9 8 2 3 1 5 7 5 8，測(cè)試結(jié)果：9 10 2 8 13 12 6 11 3 7 4 5 1 5.3程序運(yùn)行結(jié)果截圖 數(shù)據(jù)1：程序清單 13 運(yùn)行與測(cè)試5章 第 3 2 1 5 4 運(yùn)行結(jié)果： 數(shù)據(jù)2：程序清單 14 運(yùn)行與測(cè)試 第5章 6 4 5 7 3 1 2 8 運(yùn)行結(jié)果： 數(shù)據(jù)3：程序清單 15 運(yùn)行與測(cè)試第 5章 9 10 2 8 13 12 6 11 3 7 4 5 1 運(yùn)行結(jié)果： 16 第6章 總結(jié)與心得 第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)真

10、，既然是該你做的事，肯定是你應(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)了我選用參考書(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ì)，

11、培養(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)用。 71 參考文獻(xiàn) 參考文獻(xiàn) 1 胡明，王濤 等著. 數(shù)據(jù)結(jié)構(gòu)（C+版）M. 北京：清華大學(xué)出版社，2011. 2 譚浩強(qiáng) 著. C程序設(shè)計(jì)（第四版）M. 北京：清華大學(xué)出版社，2005. 3 譚浩強(qiáng) 著. C+程序設(shè)計(jì) M. 北京：清華大學(xué)出版社，2004. 81 附錄 附錄 程序源代碼#includeusing namespace std;struct Lnodeint pwd;int bianhao;struct Lnode* next;int main()int i=0;int num,m;潣瑵輸入人數(shù)num;潣瑵輸入初始報(bào):m;潣瑵輸入密:;int a100;for(i=0;iai;Lnode *L,*p;L=new Lnode;L-next=NULL;for(i=num;i0;i-)p=new Lnode;p-pwd=ai-1;p-bianhao=i; 附錄 p-next=L-nex