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

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

2、得 . 17 參考文獻 . 18 附錄 程序源代碼 . 19 4 第1章 問題描述 第1章 問題描述編號1,2,個人按照順時針方向圍坐一圈每人持有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)限從第一個人開始順時針方向開始順序報數(shù)報時停止報數(shù)。的人出列，將他的密碼作為新值，從在順時針方向的下一個人開始重新報數(shù)，如此下去，直到有人全部出列為止。設(shè)計一個程序來求出出列順序5 第2章 基本要求 第2章 基本要求 1) 建立數(shù)據(jù)模型，確定存儲結(jié)構(gòu)； 2) 對任意n個人，密碼為m，實現(xiàn)約瑟夫環(huán)問題； 3) 出圈的順序可以依次輸出。 6 第3章 概要設(shè)計 第3章 概要設(shè)計 3.1 數(shù)據(jù)結(jié)構(gòu)的設(shè)計 解決此

3、問題需要用到單鏈表的數(shù)據(jù)結(jié)構(gòu)。約瑟夫環(huán)問題，從確定的初報數(shù)開始進行，順著這一方向向前如此循環(huán)，若能找到新的密碼m所對應的數(shù)值則直接輸出，若不能找到，繼續(xù)向下依次尋找，直到找到密碼m所對應的數(shù)值，再輸出，如此循環(huán)。約瑟夫環(huán)問題中的數(shù)據(jù)是人所在的位置，而這種數(shù)據(jù)存在“第一元素、最后元素”，并且存在唯一的前驅(qū)和后繼，完全符合單鏈表的特點。 很顯然，這需要應用單循環(huán)鏈表的知識。 單鏈表的基本思想就是用指針表示結(jié)點之間的邏輯關(guān)系，要確定指針變量p，結(jié)點p，指針p和L。 3.2 算法的設(shè)計 按照模塊進行劃分： （1）鏈表節(jié)點設(shè)計 struct Lnode int pwd;/密碼 int bianhao;/

4、編號 struct Lnode* next; ; （2）采用頭插法構(gòu)造鏈表，由此必須倒著輸入個人的密碼 和編號，由此可計一個線性表作為緩存暫時保存?zhèn)€人密碼和編號。an=pwd。n為編號，pwd為n的人的密碼。 （3）將上述2中緩存的數(shù)據(jù)從an到a1一次賦給鏈表L： 7 第3章 概要設(shè)計 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)模擬報數(shù)的過程 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是用來控制循環(huán)次數(shù)的變量，值為總?cè)藬?shù)n，每完成一次刪除操。 即每有一個人出列，num減1。 8 第3章 概要設(shè)計 循環(huán)中設(shè)置了中間變量temp用來存儲要刪除的結(jié)點的指針，以保證刪除操 作不會導致鏈表指針無法找到下一結(jié)點。結(jié)束后free掉temp。 （5）刪除結(jié)點，即找到出列對象的同時輸出這個結(jié)點的數(shù)據(jù)域：編號 和密碼！ 3.3抽象數(shù)據(jù)類型的設(shè)計

6、采用類C語言定義相關(guān)的數(shù)據(jù)類型 struct Lnode int pwd; /每個人持有的密碼 int bianhao; /人員編號 struct Lnode* next; /指向下一個結(jié)點 ; 9 運行與測試細設(shè)計 第5章第4章 詳細設(shè)計4.設(shè)計抽象數(shù)據(jù)類型對應C+類的定）鏈表節(jié)點設(shè)struct Lnodeint pwd;/密int bianhao;/編struct Lnode* next;將數(shù)據(jù)ana1（運用結(jié)點鏈表指針一次賦給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;）運用循環(huán)模擬報數(shù)過p= 第5章 運行與測試 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è)計每個成員函數(shù) int pwd; int bianhao; struct Lnode* next; 將密碼和編號存入程序中，通過結(jié)點指針對所需的數(shù)據(jù)進行調(diào)用。 Lnode *temp 找到出列對象的同時，輸

8、出這個結(jié)點的數(shù)據(jù)域，存儲要刪除結(jié)點，直到程序運行完畢。 11 第5章 運行與測試 4.3設(shè)計主函數(shù) 主函數(shù) 定義輸入人數(shù)和密碼 輸入相應的初始報數(shù) 輸入操作完成后，輸出相應數(shù)據(jù) 12 第5章 運行與測試 第5章 運行與測試 5.1程序運行環(huán)境 Windows 7系統(tǒng)下 在VC+6.0 開發(fā)平臺進行程序的運行與測試。 5.2測試數(shù)據(jù)及測試結(jié)果 數(shù)據(jù)1：輸入人數(shù)5，初次報數(shù)3，密碼依次為： 2 6 8 4 7，測試結(jié)果：3 2 1 5 4 數(shù)據(jù)2：輸入人數(shù)8，初次報數(shù)6，密碼依次為： 3 4 8 7 1 6 4 5 ，測試結(jié)果：6 4 5 7 3 1 2 8 數(shù)據(jù)3：輸入人數(shù)13，初次報數(shù)9，密碼

9、依次為： 4 6 3 7 9 8 2 3 1 5 7 5 8，測試結(jié)果：9 10 2 8 13 12 6 11 3 7 4 5 1 5.3程序運行結(jié)果截圖 數(shù)據(jù)1：程序清單 13 運行與測試5章 第 3 2 1 5 4 運行結(jié)果： 數(shù)據(jù)2：程序清單 14 運行與測試 第5章 6 4 5 7 3 1 2 8 運行結(jié)果： 數(shù)據(jù)3：程序清單 15 運行與測試第 5章 9 10 2 8 13 12 6 11 3 7 4 5 1 運行結(jié)果： 16 第6章 總結(jié)與心得 第6章 總結(jié)與心得 我的這次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計的題目是約瑟夫環(huán)問題，通過對該題目的設(shè)計，使我加深了對數(shù)據(jù)結(jié)構(gòu)的理解 。做什么事情，都要對認真

10、，既然是該你做的事，肯定是你應該有這個能力，即使能力不夠，也是應該借這個機會來培養(yǎng)。所以放心大膽地做，對自己有信心，就有動力。有人說，世上的事就怕認真二字。確實，做什么，只是認真地去做，踏踏實實，戒躁戒躁，靜靜地思考，慢慢地進步，真的是天下無難事。這就是我這次課程設(shè)計中得到的最大的體會，受益匪淺。 通過課程設(shè)計我的收獲如下： 1、鞏固和加深了對數(shù)據(jù)結(jié)構(gòu)的理解，提高綜合運用本課程所學知識的能力。 2、培養(yǎng)了我選用參考書，查閱手冊及文獻資料的能力。培養(yǎng)獨立思考，深入研究，分析問題、解決問題的能力。 3、通過實際編譯系統(tǒng)的分析設(shè)計、編程調(diào)試，掌握應用軟件的分析方法和工程設(shè)計方法。 4、通過課程設(shè)計，

11、培養(yǎng)了我嚴肅認真的工作作風，逐步建立正確的生產(chǎn)觀念、經(jīng)濟觀念和全局觀念。 根據(jù)我在課程設(shè)計中遇到得問題，我將在以后的學習過程中注意以下幾點： 1、認真上好專業(yè)實驗課，多在實踐中鍛煉自己。 2、寫程序的過程中要考慮周到，嚴密。 3、認真的學習課本知識，并在此基礎(chǔ)上學會靈活運用。 71 參考文獻 參考文獻 1 胡明，王濤 等著. 數(shù)據(jù)結(jié)構(gòu)（C+版）M. 北京：清華大學出版社，2011. 2 譚浩強 著. C程序設(shè)計（第四版）M. 北京：清華大學出版社，2005. 3 譚浩強 著. C+程序設(shè)計 M. 北京：清華大學出版社，2004. 81 附錄 附錄 程序源代碼#includeusing namespace std;struct Lnodeint pwd;int bianhao;struct Lnode* next;int main()int i=0;int num,m;潣瑵輸入人數(shù)num;潣瑵輸入初始報: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