數(shù)據(jù)結(jié)構(gòu)約瑟夫生者死者游戲課程設(shè)計

1、 數(shù)據(jù)機構(gòu)課程設(shè)計選題名稱: 約瑟夫生者死者游戲 系（院）: 信息工程系專 業(yè): 信息管理與信息系統(tǒng)班 級: 1430602 姓 名: 程宜興 學(xué) 號: 201430060209指導(dǎo)教師: 童懷水 2016年4月9日目錄1、需求分析32、系統(tǒng)功能43、系統(tǒng)設(shè)計54、程序具體運行結(jié)果105、總結(jié)121、需求分析1.1課程設(shè)計目的課程設(shè)計目的是為學(xué)生提供了一個既動手又動腦，獨立實踐的機會，將課本上的理論知識和實際有機的結(jié)合起來，鍛煉學(xué)生的分析解決實際問題的能力。提高學(xué)生適應(yīng)實際，實踐編程的能力。通過實踐讓學(xué)生理論和實際操作相結(jié)合，更好的理解書面知識，并在鞏固的基礎(chǔ)上融會所學(xué)認識。1.2課程設(shè)計要求

2、約瑟夫生死游戲：30個人圍成一個圈由第一個人數(shù)起，依次報數(shù)，數(shù)到第九個人，便把他剔除，然后再從他的下一個人數(shù)起，數(shù)到第九個人，再將他剔除剩下15個乘客為止，問那些位置是被扔下大海的位置。我們的設(shè)計目標(biāo)是可以輸入任意的位置和剩下的乘客。1.3課程設(shè)計目標(biāo)與總體方案 實驗設(shè)計的目標(biāo)是運用循環(huán)鏈表來解決Josephu環(huán)問題，其中運用了許多鏈表中的基本操作使改程序能不只解決一個Josephu的簡單鏈表，其中的Josephu函數(shù)則是用于，運用C+程序編寫程序，實現(xiàn)隊列的建立、插入和刪除基本功能，在程序設(shè)計成功的基礎(chǔ)上，進一步深化理解隊列的作用和實現(xiàn)原理。2、系統(tǒng)的功能2.1系統(tǒng)功能說明約瑟夫生死游戲輸出

3、輸入更新鏈表確定n值構(gòu)建鏈表2. 2系統(tǒng)功能解析（1）構(gòu)建約瑟夫鏈表：使整個游戲在鏈表中運行，使得結(jié)點在刪除時不需要移動大量的結(jié)點;（2）確定n的值：進而使鏈具化體，從而可以構(gòu)建一個具體的鏈表;（3）更新鏈表：對剔除結(jié)點后的鏈表進行重新連接，有構(gòu)成了一個新的鏈表，使得循環(huán)繼續(xù)進行;（4）輸入：輸入n的值進行鏈表具體化，輸入間隔值m，使得間隔被確定，程序得以有效正確的進行；（5）輸出：輸出要剔除的結(jié)點的數(shù)值;3、系統(tǒng)的設(shè)計3.1 josphu鏈表的實現(xiàn) Josphu鏈表鏈?zhǔn)奖硎竞蛯崿F(xiàn)約瑟夫（Josephu）問題：已知N個人圍坐在一張圓桌周圍（不妨以1,2，N對每一個人依次編號），現(xiàn)在先從序號為K

4、的人開始報數(shù)，數(shù)到m的那個人出列,他的下一個人又從1開始數(shù)，報數(shù)到m的人出列直到所有人都出出列為止。給出出列的順序。3.2循環(huán)鏈表 表示和實現(xiàn)和順序棧相似，在隊列的順序存儲結(jié)構(gòu)中，除了用一組地址連續(xù)的存儲單元依次存放從隊列頭到隊列尾的元素之外，尚需附設(shè)兩個指針front和rear分別指示隊列頭元素及隊列尾元素的位置。為了C語言中描述方便起 在此我們約定，初始化建空隊列時front=rear=0,每當(dāng)插入新的隊列尾元素時，“尾指針增1”；每當(dāng)刪除隊列頭元素時，“頭指針增1”。因此，在非空隊列中，頭指針始終指向隊列頭元素，而尾指針始終指向隊列尾元素的下一個位置從上述分析可見，在C+中不能用動態(tài)分配

5、的一維數(shù)組來實現(xiàn)循環(huán)隊列。如果用戶的應(yīng)用程序中設(shè)有循環(huán)隊列，則必須為它設(shè)定一個最大隊列長度；若用戶無法預(yù)估所用隊列的最大長度，則宜采用鏈隊列。3.3程序的代碼#include<stdio.h>#include<stdlib.h>typedef struct node int data; struct node*next;ListNode,*LinkList;void main()LinkList R=NULL;int n,k;LinkList InitRing(int n ,LinkList R);LinkList DeleteDeath(int n,int k,Lin

6、kList R);void OutRing(int n ,LinkList R);printf("輸入總?cè)藬?shù)n和報數(shù)上限 k：");scanf("%d%d",&n,&k);R=InitRing(n,R);R=DeleteDeath(n,k,R);OutRing(n,R);LinkList InitRing(int n ,LinkList R)ListNode *p,*q;int i ;R=q=(ListNode *)malloc(sizeof(ListNode);for(i=1;i<n;i+)p=(ListNode *)malloc

7、(sizeof(ListNode);q->data=i;q->next=p;q=p;p->data=n;p->next=R;R=p;return R; LinkList DeleteDeath(int n ,int k ,LinkList R) int i ,j ; ListNode *p,*q; p=R; printf("拋入大海者的編號如下：n"); for(i=1;i<=n/2;i+) for(j=1;j<=k-1;j+) p=p->next; q=p->next; p->next=q->next; prin

8、tf("%4d",q->data); if(i%10=0)printf("n"); free(q); printf("n");R=p;return R; void OutRing(int n ,LinkList R) int i ; ListNode *p; p=R; printf("幸存者編號如下:n"); for(i=1;i<=(n+1)/2;i+,p=p->next) printf("%4d",p->data); if(i % 10=0)printf("n

9、"); printf("n"); 開始3.4程序的流程圖輸入n,m值創(chuàng)建列表計數(shù)刪除結(jié)點連接鏈表結(jié)束I<=n/23.5流程圖說明 開始進入程序，先確定n的值，然后，根據(jù)n得知建立鏈表，然后數(shù)數(shù)，確定輸出的位置，輸出數(shù)，更新鏈表，如果剩下的數(shù)小于等于n/2,則停止程序，否則繼續(xù)計數(shù)進行循環(huán)直至結(jié)束程序。4、程序具體運行結(jié)果4.1先編譯，編譯無錯后運行4.2輸入總?cè)藬?shù)和報數(shù)上限5、總結(jié)經(jīng)過這次集中上機的實驗，從開始選題到自己上手還是編寫程序的過程中，我學(xué)會了很多的東西，一個軟件系統(tǒng)框架應(yīng)建立在數(shù)據(jù)之上，而不是建立在操作之上。一個含抽象數(shù)據(jù)類型的軟件模塊應(yīng)包含定義、表示、實現(xiàn)三個部分。本實驗設(shè)計就是建立在“定義、表示、實現(xiàn)”的基礎(chǔ)上完成的。同時，做好課程設(shè)計更能體現(xiàn)出同學(xué)的學(xué)習(xí)態(tài)度，對于新知識的渴望與追求，能夠反映出同學(xué)對自己負責(zé)任的決心，這點讓我感受頗深。另外，據(jù)結(jié)構(gòu)的知識和算法總是模棱兩可的經(jīng)過這次練習(xí)