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

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

3、輸入更新鏈表確定n值構建鏈表2. 2系統功能解析（1）構建約瑟夫鏈表：使整個游戲在鏈表中運行，使得結點在刪除時不需要移動大量的結點;（2）確定n的值：進而使鏈具化體，從而可以構建一個具體的鏈表;（3）更新鏈表：對剔除結點后的鏈表進行重新連接，有構成了一個新的鏈表，使得循環繼續進行;（4）輸入：輸入n的值進行鏈表具體化，輸入間隔值m，使得間隔被確定，程序得以有效正確的進行；（5）輸出：輸出要剔除的結點的數值;3、系統的設計3.1 josphu鏈表的實現 Josphu鏈表鏈式表示和實現約瑟夫（Josephu）問題：已知N個人圍坐在一張圓桌周圍（不妨以1,2，N對每一個人依次編號），現在先從序號為K

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

5、的一維數組來實現循環隊列。如果用戶的應用程序中設有循環隊列，則必須為它設定一個最大隊列長度；若用戶無法預估所用隊列的最大長度，則宜采用鏈隊列。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("輸入總人數n和報數上限 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值創建列表計數刪除結點連接鏈表結束I<=n/23.5流程圖說明 開始進入程序，先確定n的值，然后，根據n得知建立鏈表，然后數數，確定輸出的位置，輸出數，更新鏈表，如果剩下的數小于等于n/2,則停止程序，否則繼續計數進行循環直至結束程序。4、程序具體運行結果4.1先編譯，編譯無錯后運行4.2輸入總人數和報數上限5、總結經過這次集中上機的實驗，從開始選題到自己上手還是編寫程序的過程中，我學會了很多的東西，一個軟件系統框架應建立在數據之上，而不是建立在操作之上。一個含抽象數據類型的軟件模塊應包含定義、表示、實現三個部分。本實驗設計就是建立在“定義、表示、實現”的基礎上完成的。同時，做好課程設計更能體現出同學的學習態度，對于新知識的渴望與追求，能夠反映出同學對自己負責任的決心，這點讓我感受頗深。另外，據結構的知識和算法總是模棱兩可的經過這次練習