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

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

2、密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù) 上限值m從第一個人開始順時針方向自1開始順序報數(shù)，報到 m時停止報數(shù)。報m的人出列，將他的密碼作為新的 m值，從他 在順時針方向的下一個人開始重新從 1報數(shù)，如此下去，直到所 有人全部出列為止。設(shè)計一個程序來求出出列順序。標(biāo)準(zhǔn)文檔實用文案第2章基本要求1）建立數(shù)據(jù)模型，確定存儲結(jié)構(gòu)；2）對任意n個人，密碼為m實現(xiàn)約瑟夫環(huán)問題;3）出圈的順序可以依次輸出。標(biāo)準(zhǔn)文檔實用文案第3章概要設(shè)計3.1 數(shù)據(jù)結(jié)構(gòu)的設(shè)計解決此問題需要用到單鏈表的數(shù)據(jù)結(jié)構(gòu)。約瑟夫環(huán)問題，從 確定的初報數(shù)開始進(jìn)行，順著這一方向向前如此循環(huán)，若能找到 新的密碼m所對應(yīng)的數(shù)值則直接輸出，

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

4、存?zhèn)€人密碼和 編號。an=pwd o n為編號，pwd為n的人的密碼。(3)將上述2中緩存的數(shù)據(jù)從an到a1 一次賦給鏈表L：標(biāo)準(zhǔn)文檔實用文案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)模擬報數(shù)的過程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 是用來控制循環(huán)次數(shù)的變量，值為總?cè)藬?shù)n,每完成一次刪除操。即每有一個人 出列，num減1。標(biāo)準(zhǔn)文檔實用文案循環(huán)中設(shè)置了中間變量temp用來存儲要刪除的結(jié)點的指 針，以保證刪除操作不會導(dǎo)致鏈表指針無法找到下一結(jié)點。結(jié)束后 free掉temp。(5)刪除結(jié)點，即找到出列對象的同時輸出這個結(jié)點的數(shù)據(jù)域

6、：編號和密碼！3.3 抽象數(shù)據(jù)類型的設(shè)計采用類C語言定義相關(guān)的數(shù)據(jù)類型struct Lnode(int pwd; /每個人持有的密碼int bianhao; /人員編號struct Lnode* next; /指向下一個結(jié)點;標(biāo)準(zhǔn)文檔實用文案第4章詳細(xì)設(shè)計4.1設(shè)計抽象數(shù)據(jù)類型對應(yīng)的C+鎂的定義(1)鏈表節(jié)點設(shè)計密他編號struct Lnodeint pwd;/int bianhao;/struct Lnode* next;(2)將數(shù)據(jù)從an到a1(運用結(jié)點、鏈表指針)一次賦給鏈表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)運用循環(huán)模擬報數(shù)過程p=L ；標(biāo)準(zhǔn)文檔實用文案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è)計每個成員函數(shù)int pwd;int bianhao;struct Lnode* next;將密碼和編號存入程序中，通過結(jié)點指針對所需的數(shù)據(jù)進(jìn)行 調(diào)用。Lnode *temp找到出列對象的同時，輸出這個結(jié)點的數(shù)據(jù)域，存儲要刪除 結(jié)點，直到程序運行完畢。標(biāo)準(zhǔn)文檔實用文案4.3 設(shè)計主函數(shù)主函數(shù)（定義輸入人數(shù)和密碼輸入相應(yīng)的初始報數(shù)輸入操作完成后，輸出相應(yīng)數(shù)據(jù)）標(biāo)準(zhǔn)文檔實用文案第5章運行與測試5.1 程序運行環(huán)境Windows 7系統(tǒng)下 在VC+6.0開發(fā)平臺進(jìn)行程序的運行與測 試。5.2 測試數(shù)據(jù)及測試結(jié)果數(shù)據(jù)

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

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

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

12、清華大學(xué)出 版社，2005.3譚浩強 著.C+程序設(shè)計M.北京：清華大學(xué)出版社， 2004.標(biāo)準(zhǔn)文檔實用文案附錄程序源代碼#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<<"輸入初始報數(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)文檔實用文案p->next=L->next;L->next=p;)P=L；while(num>0)for(i=1;i<m;i+)p=p->next;if(p->nex