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

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

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

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

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

5、的一維數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列。如果用戶的應(yīng)用程序中設(shè)有循環(huán)隊(duì)列，則必須為它設(shè)定一個(gè)最大隊(duì)列長(zhǎng)度；若用戶無(wú)法預(yù)估所用隊(duì)列的最大長(zhǎng)度，則宜采用鏈隊(duì)列。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和報(bào)數(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("拋入大海者的編號(hào)如下：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("幸存者編號(hào)如下: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"); 開(kāi)始3.4程序的流程圖輸入n,m值創(chuàng)建列表計(jì)數(shù)刪除結(jié)點(diǎn)連接鏈表結(jié)束I<=n/23.5流程圖說(shuō)明 開(kāi)始進(jìn)入程序，先確定n的值，然后，根據(jù)n得知建立鏈表，然后數(shù)數(shù)，確定輸出的位置，輸出數(shù)，更新鏈表，如果剩下的數(shù)小于等于n/2,則停止程序，否則繼續(xù)計(jì)數(shù)進(jìn)行循環(huán)直至結(jié)束程序。4、程序具體運(yùn)行結(jié)果4.1先編譯，編譯無(wú)錯(cuò)后運(yùn)行4.2輸入總?cè)藬?shù)和報(bào)數(shù)上限5、總結(jié)經(jīng)過(guò)這次集中上機(jī)的實(shí)驗(yàn)，從開(kāi)始選題到自己上手還是編寫(xiě)程序的過(guò)程中，我學(xué)會(huì)了很多的東西，一個(gè)軟件系統(tǒng)框架應(yīng)建立在數(shù)據(jù)之上，而不是建立在操作之上。一個(gè)含抽象數(shù)據(jù)類型的軟件模塊應(yīng)包含定義、表示、實(shí)現(xiàn)三個(gè)部分。本實(shí)驗(yàn)設(shè)計(jì)就是建立在“定義、表示、實(shí)現(xiàn)”的基礎(chǔ)上完成的。同時(shí)，做好課程設(shè)計(jì)更能體現(xiàn)出同學(xué)的學(xué)習(xí)態(tài)度，對(duì)于新知識(shí)的渴望與追求，能夠反映出同學(xué)對(duì)自己負(fù)責(zé)任的決心，這點(diǎn)讓我感受頗深。另外，據(jù)結(jié)構(gòu)的知識(shí)和算法總是模棱兩可的經(jīng)過(guò)這次練習(xí)