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

1、<p>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告</p><p><b>　　約</b></p><p><b>　　瑟</b></p><p><b>　　夫</b></p><p><b>　　環(huán)</b></p><p><b&

2、gt;　　目 錄</b></p><p>　　1.設(shè)計題目（約瑟夫環(huán)）</p><p>　　2.運行環(huán)境（軟、硬件環(huán)境）</p><p><b>　　3.需求分析</b></p><p><b>　　4.概要設(shè)計</b></p><p><b

3、>　　1)抽象數(shù)據(jù)類型</b></p><p>　　2)算法設(shè)計的思想</p><p>　　3)程序總體及主要算法的流程圖</p><p>　　5.源代碼（帶詳細注釋）</p><p><b>　　6.運行結(jié)果分析</b></p><p>　　7.收獲、體會及意見&l

4、t;/p><p><b>　　設(shè)計題目</b></p><p>　　約瑟夫環(huán)，編號為1，2···n的n個人按順時針方向圍坐一圈，每人持有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)的上限值m，從第一個人開始按順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)，報m的人出列，將他的密碼作為新的m值，從他的順時針方向的下一個開始重新從1報數(shù)，如此下

5、去，直至所有的人全部出列為止，設(shè)計一個程序求出出列順序。</p><p><b>　　運行環(huán)境</b></p><p><b>　　DevC++</b></p><p><b>　　需求分析</b></p><p>　　使用單循環(huán)鏈表作為儲存結(jié)構(gòu)，并模擬該過程;</p&g

6、t;<p>　　從鍵盤輸入開始時的總?cè)藬?shù)、初始報數(shù)上限值m及每個人的密碼；</p><p>　　按照出列順序輸出各人的編號。</p><p><b>　　概要設(shè)計</b></p><p><b>　　抽象數(shù)據(jù)類型</b></p><p>　　struct node</p>

7、<p><b>　　{</b></p><p><b>　　int mm;</b></p><p><b>　　int num;</b></p><p>　　struct node *next;</p><p><b>　　};</b><

8、/p><p>　　typedef struct node Linklist;</p><p>　　Linklist *createlist(Linklist *L) //根據(jù)人數(shù)創(chuàng)建鏈表</p><p><b>　　{ </b></p><p><b>　　int t;</b></p>

9、;<p>　　Linklist *p,*q;</p><p>　　printf("請輸入總?cè)藬?shù) : ");</p><p>　　scanf("%d",&num);</p><p>　　printf("請輸入初始上限值 : "); </p><p>　　scanf

10、("%d",&m);</p><p>　　for(t=1;t<=num;t++)</p><p><b>　　{</b></p><p>　　p=(node*)malloc(sizeof(node));</p><p>　　printf("請輸入第%d個人的密碼 : "

11、;,t);</p><p>　　scanf("%d",&p->mm);</p><p><b>　　p->num=t;</b></p><p>　　if(L==NULL)</p><p><b>　　L=q=p;</b></p><p>

12、;<b>　　else </b></p><p><b>　　{</b></p><p>　　q->next=p;</p><p><b>　　q=p;</b></p><p><b>　　}</b></p><p><

13、b>　　}</b></p><p>　　p->next=L;</p><p><b>　　return L;</b></p><p><b>　　}</b></p><p><b>　　算法設(shè)計的思想</b></p><p>　　

14、程序執(zhí)行的命令包括：</p><p><b>　?。?）構(gòu)造鏈表；</b></p><p><b>　?。?）輸入數(shù)據(jù)；</b></p><p>　?。?）執(zhí)行報數(shù)，儲存出列人的序號，刪除出列人的信息以及把出列人的密碼賦給m；</p><p><b>　　（4）結(jié)束。</b>&

15、lt;/p><p>　　本程序應(yīng)包括三個模塊：</p><p>　?。?）信息錄入（構(gòu)造鏈表）模塊。此模塊將對數(shù)據(jù)進行初始化，構(gòu)造鏈表，并錄入數(shù)據(jù)以便后續(xù)程序的使用。</p><p>　?。?）結(jié)果輸出模塊。此模塊將根據(jù)前面所輸入的數(shù)據(jù)對數(shù)據(jù)進行處理，輸出報數(shù)號碼，刪除報數(shù)節(jié)點，并繼續(xù)進行處理。</p><p>　?。?）主程序模塊。此模塊實現(xiàn)整

16、個程序的進入和退出，及各種初始化處理。</p><p>　　程序總體及主要算法的流程圖</p><p>　　1．此部分為createlist函數(shù)。首先初始化變量，再輸出提示性語句，等待用戶輸入數(shù)據(jù)，將總?cè)藬?shù)和初始上限值分別存入num和m。以num為上限值建立單循環(huán)鏈表，最后返回L。 </p><p>　　2．此部分為printlist函數(shù)部分。定義變量temp=m，

17、從第一個人開始進行報數(shù)，指針q和p指向第一個人L，當q->next=p時，q=q->next;否則當q->next!=q時—temp，直到—temp！=0時輸出p所指向的節(jié)點的num；重復(fù)以上處理直到q->next!=q為假時結(jié)束該函數(shù)。 </p><p>　　3．此部分為主程序部分。分別調(diào)用函數(shù)createlist和printlist，所有人輸出，程序結(jié)束。并通過while循環(huán)對程序進行

18、重復(fù)使用。</p><p><b>　　源代碼</b></p><p>　　#include<stdio.h></p><p>　　#include<malloc.h></p><p>　　int m=0,num=0;</p><p>　　struct node</p

19、><p><b>　　{</b></p><p><b>　　int mm;</b></p><p><b>　　int num;</b></p><p>　　struct node *next;</p><p><b>　　};</b>

20、;</p><p>　　typedef struct node Linklist;</p><p>　　Linklist *createlist(Linklist *L) //根據(jù)人數(shù)創(chuàng)建鏈表</p><p><b>　　{ </b></p><p><b>　　int t;</b><

21、/p><p>　　Linklist *p,*q;</p><p>　　printf("請輸入總?cè)藬?shù) : ");</p><p>　　scanf("%d",&num);</p><p>　　printf("請輸入初始上限值 : "); </p><p>　　

22、scanf("%d",&m);</p><p>　　for(t=1;t<=num;t++)</p><p><b>　　{</b></p><p>　　p=(node*)malloc(sizeof(node));</p><p>　　printf("請輸入第%d個人的密碼 :

23、",t);</p><p>　　scanf("%d",&p->mm);</p><p><b>　　p->num=t;</b></p><p>　　if(L==NULL)</p><p><b>　　L=q=p;</b></p><

24、;p><b>　　else </b></p><p><b>　　{</b></p><p>　　q->next=p;</p><p><b>　　q=p;</b></p><p><b>　　}</b></p><p>

25、;<b>　　}</b></p><p>　　p->next=L;</p><p><b>　　return L;</b></p><p><b>　　}</b></p><p>　　void printlist(Linklist *L) //輸

26、出鏈表</p><p><b>　　{ </b></p><p>　　int temp=m;</p><p>　　Linklist *p,*q;</p><p>　　printf("出列順序是: \n");</p><p><b>　　p=q=L;</b>

27、</p><p>　　while(q->next!=p)</p><p>　　q=q->next;</p><p>　　while(q->next!=q)</p><p><b>　　{</b></p><p>　　while(--temp)</p><p&g

28、t;<b>　　{</b></p><p><b>　　q=p;</b></p><p>　　p=p->next;</p><p><b>　　}</b></p><p>　　printf("%d ",p->num);</p>&l

29、t;p>　　temp=p->mm;</p><p>　　q->next=p->next;</p><p><b>　　free(p);</b></p><p>　　p=q->next ;</p><p><b>　　}</b></p><p>　

30、　printf("%d\n",q->num); //輸出最后一個結(jié)點</p><p><b>　　return;</b></p><p><b>　　}</b></p><p>　　int main()</p><p><b>　　{int s=1;</b

31、></p><p>　　while(s!=0){</p><p>　　Linklist *L=NULL;</p><p>　　L=createlist(L);</p><p>　　printlist(L);</p><p>　　printf("繼續(xù)？（1.yes or 0.no）");<

32、/p><p>　　scanf("%d",&s);</p><p>　　printf("************************\n");}</p><p>　　printf("謝謝使用!\n");</p><p><b>　　return 0;</b>

33、;</p><p><b>　　}</b></p><p><b>　　運行結(jié)果分析</b></p><p><b>　　輸入總?cè)藬?shù)：5</b></p><p><b>　　輸入上限值：2</b></p><p>　　輸入第一個人的

34、密碼：1</p><p>　　輸入第二個人的密碼：2</p><p>　　輸入第三個人的密碼：3</p><p>　　輸入第四個人的密碼：4</p><p>　　輸入第五個人的密碼：5</p><p><b>　　出列順序是：</b></p><p><b>　　

35、2 4 5 1 3</b></p><p>　　繼續(xù)（1.yes or 0.no）？1</p><p>　　*********************</p><p><b>　　輸入總?cè)藬?shù)：3</b></p><p><b>　　輸入上限值：4</b></p><p

36、>　　輸入第一個人的密碼：1</p><p>　　輸入第二個人的密碼：2</p><p>　　輸入第三個人的密碼：3</p><p><b>　　出列順序是：</b></p><p><b>　　1 2 3</b></p><p>　　繼續(xù)（1.yes or 0.no）

37、？0</p><p>　　*********************</p><p><b>　　謝謝使用！</b></p><p><b>　　運行時的界面顯示</b></p><p><b>　　收獲、體會及意見</b></p><p>　　通過本次

38、課程設(shè)計使我更加清楚了自己的水平以及以后要努力的方向。本次課程設(shè)計涉及到的范圍很廣，讓本人能夠比較系統(tǒng)的對C語言和數(shù)據(jù)結(jié)構(gòu)進行一次整理和復(fù)習(xí)。同時有了很多的體會和經(jīng)驗。</p><p>　　我的課設(shè)的題目是約瑟夫環(huán)，根據(jù)題目的內(nèi)容與要求，首先得到的是用單鏈表作為全體人數(shù)與每個人的密碼的存儲結(jié)構(gòu)。設(shè)置結(jié)構(gòu)體指針，并定義了兩個指針類型的指針p與q；并編寫了兩個函數(shù)，鏈表構(gòu)造函數(shù)和輸出函數(shù)。</p>&l