約瑟夫生者死者游戲

1、課程設計報告約瑟夫生者死者游戲學生姓名： 專 業(yè)： 班 級： 學 號: 指導教師： 2017年 3月29日目錄一、實驗題目2二、實驗目的2三、實驗要求2四、實現(xiàn)過程31、總體設計：32、詳細設計：33、調試分析：34、運行結果：35、實驗總結：6五、參考文獻6一、實驗題目約瑟夫生者死者游戲二、實驗目的本次課程設計的主要目的是綜合運用所學的數(shù)據(jù)結構知識解決Jonsepu環(huán)問題，側重對循環(huán)鏈表等相關內(nèi)容的綜合應用，使自己能進一步熟悉掌握數(shù)據(jù)結構的基礎知識，進一步提升自己的解決問題和編程調試能力，為后續(xù)專業(yè)課程的學習打下良好的基礎。三、實驗要求設計要求本游戲的數(shù)學建模如下：假設n個旅客排成一個環(huán)形，

2、依次順序編號1，2，n。從某個指定的第1號開始，沿環(huán)計數(shù)，每數(shù)到第m個人就讓其出列，且從下一個人開始重新計數(shù)，繼續(xù)進行下去。這個過程一直進行到剩下k個旅客為止。本游戲的要求用戶輸入的內(nèi)容包括： 1. 旅客的個數(shù)，也就是n的值； 2. 離開旅客的間隔數(shù)，也就是m的值；3. 所有旅客的序號作為一組數(shù)據(jù)要求存放在某種數(shù)據(jù)結構中。本游戲要求輸出的內(nèi)容是包括1. 離開旅客的序號； 2. 剩余旅客的序號； 四、實現(xiàn)過程1、總體設計：1. 主流程圖：開始輸入總人數(shù)創(chuàng)建鏈表打印鏈表輸入報數(shù)人的位置輸入報的數(shù)字調用踢出人的模塊Out(head,beg,val,huo)結束2. Out函數(shù)流程圖 開始將p指針指向

3、起始報數(shù)的位置剩下的人數(shù)大于輸入留下的人數(shù)否是P指針移動n-3個位置 q指針指向p的下一個結點刪除q指針所指的結點p指針指向q的下一個結點釋放q指針所指向結點的空間Flag+結束2、詳細設計：1.結構體typedef struct Jonse/*定義結構體*/int code;/*編號（分配位置）*/struct Jonse *next;jonse;2.鏈表的構造函數(shù)jonse * Create(int n)/*建立n個節(jié)點的單向循環(huán)鏈表函數(shù)*/Jonse *h,*p;int i;h=(Jonse *)malloc(sizeof(Jonse);/*為頭結點分配空間*/p=h;for(i=1;i

4、<=n;i+)/*建立n個節(jié)點的單向鏈表*/p->code=i;if(i<n)p->next=(Jonse *)malloc(sizeof(Jonse);/*創(chuàng)建新節(jié)點*/p=p->next;p->next=h;/*返回頭結點，完成單向循環(huán)鏈表的建立*/return h;3.輸出鏈表的函數(shù)void ShowList(Jonse *h)/*打印鏈表函數(shù)*/Jonse *p;p=h;doprintf("%dt",p->code);p=p->next;while(p!=h);4.實現(xiàn)將人剔除的函數(shù)void Out(Jonse *h,

5、int i,int d,int s)/*出隊函數(shù)*/int c;c=s;Jonse *p,*q;int k;p=h;for(q=h;q->next!=h;q=q->next);/*初始化鏈表*/for(k=1;k<i;k+)/*次循環(huán)功能：設置好開始報數(shù)的人所在位置*/q=p;p=p->next;while(p!=p->next)/*循環(huán)刪除隊列結點*/for(k=1;k<d;k+)/*數(shù)數(shù)*/q=p;p=p->next;printf("%d ",p->code);/*輸出被踢節(jié)點的位置*/q->next=p->n

6、ext;free(p);/*釋放被踢出的結點*/p=NULL;/*讓p指針賦值為空指針*/p=q->next;flag+;if(num-flag=c)break;printf("n剩余游客的編號:n");/free(p);/*釋放被踢出的結點*/p=NULL;/*讓p指針賦值為空指針*/p = h;doprintf("%d ",p->code);p=p->next;while(p!=h);printf("n");3、調試分析：程序的編寫和調試基本正常。遇到的問題主要是：鏈表的指向的邊界問題。本實驗采用數(shù)據(jù)抽象與模塊化

7、程序設計方法，思路清晰，實驗時調試順利，各模塊具有很好的可重用性，得到了一次良好的程序設計訓練。本實驗算法是使用循環(huán)鏈表的方法，由于這種方法在刪除一個節(jié)點后對其他節(jié)點的位置改動放不大，所以很浪費時間，每次都刪除第m個數(shù)字，都要用O（m）的時間，一共有n個數(shù)字，想要剩下一個，其余都要刪除，那么就要用（n-1）*O（m）的時間，所以算法的時間復雜度為O（mn）。還可以用數(shù)組來實現(xiàn)本實驗，減少時間的浪費。4、運行結果：1. 要求輸入?yún)⑴c者的總人數(shù)：2. 打印出創(chuàng)建好的鏈表，并提示輸入開始報數(shù)的位置：3. 輸入報數(shù)人所在的位置，并提示輸入報數(shù)的最大值：4. 輸入報數(shù)的最大值，并提示輸入留下的人數(shù)： 5

8、. 輸入留下人數(shù)，計算顯示結果：結果為刪除的人所在的位置和留下的人數(shù)：5、實驗總結： 通過本次課程設計的鍛煉，使我對數(shù)據(jù)結構又有了許多新的深刻認識，更深的理解了數(shù)據(jù)結構的難點，并且通過這次課程設計，我把以前認為沒有實際用途的知識轉化為了實際問題來解決，非常有意思，同時也覺得這種學習方法，更好的提高學習的效率，以下就是我做這次課程設計的主要體會： 一方面，在程序設計語言中，每一個數(shù)據(jù)都屬于某種數(shù)據(jù)類型。類型明顯或隱含地規(guī)定了數(shù)據(jù)的取值范圍、存儲方式以及允許進行的運算。另一方面，在程序設計過程中，當需要引入某種新的數(shù)據(jù)結構時，總是借助編程語言所提供的數(shù)據(jù)類型來描述數(shù)據(jù)的存儲結構。同時，做好課程設計

9、更能體現(xiàn)出同學的學習態(tài)度，對于新知識的渴望與追求，能夠反映出同學對自己負責任的態(tài)度。五、參考文獻1 嚴蔚敏，吳偉民，數(shù)據(jù)結構，北京：清華大學出版社，2006年2蘇小紅，C語言程序設計（第3版）2015年六、附錄#include<stdio.h>#include<stdlib.h>typedef struct Jonse/*定義結構體*/int code;/*編號（分配位置）*/struct Jonse *next;jonse;jonse * Create(int n);void ShowList(Jonse *);void Out(Jonse *,int,int,int

10、);int flag,num;/*主函數(shù)*/main()Jonse *head;int val,beg,huo;flag=0;printf("n請輸入游客總人數(shù)：");scanf("%d",&num);head=Create(num);ShowList(head);printf("n請輸入報數(shù)的人所在位置：");scanf("%d",&beg);printf("n請輸入報數(shù)最大值：");scanf("%d",&val);printf("n請輸

11、入留下的人數(shù)：");scanf("%d",&huo);printf("n將被扔下大海的游客的編號：n");Out(head,beg,val,huo);return 0;jonse * Create(int n)/*建立n個節(jié)點的單向循環(huán)鏈表函數(shù)*/Jonse *h,*p;int i;h=(Jonse *)malloc(sizeof(Jonse);/*為頭結點分配空間*/p=h;for(i=1;i<=n;i+)/*建立n個節(jié)點的單向鏈表*/p->code=i;if(i<n)p->next=(Jonse *)mall

12、oc(sizeof(Jonse);/*創(chuàng)建新節(jié)點*/p=p->next;p->next=h;/*返回頭結點，完成單向循環(huán)鏈表的建立*/return h;void ShowList(Jonse *h)/*打印鏈表函數(shù)*/Jonse *p;p=h;doprintf("%dt",p->code);p=p->next;while(p!=h);void Out(Jonse *h,int i,int d,int s)/*出隊函數(shù)*/int c;c=s;Jonse *p,*q;int k;p=h;for(q=h;q->next!=h;q=q->next);/*初始化鏈表*/for(k=1;k<i;k+)/*次循環(huán)功能：設置好開始報數(shù)的人所在位置*/q=p;p=p->next;while(p!=p->next)/*循環(huán)刪除隊列結點*/for(k=1;k<d;k+)/*數(shù)數(shù)*/q=p;p=p->next;printf("%d ",p->code);/*輸出被踢節(jié)點的位置*/q->next=p->next;free(p);/*釋放被踢出的結點*/p=NULL;/*讓p指針賦值為空指針*/p=q