選猴王數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

1、<p>　　計(jì)科專業(yè)數(shù)據(jù)結(jié)構(gòu)A課程設(shè)計(jì)</p><p><b>　　選猴王</b></p><p>　　作 者 姓 名： </p><p>　　專業(yè)、班級(jí) ： </p><p>　　學(xué) 號(hào) ：

2、 </p><p>　　指 導(dǎo) 教 師： </p><p>　　完 成 日 期： 2013年11月17日 </p><p><b>　　目 錄</b></p><p><b>　

3、　題 目 描 述1</b></p><p><b>　　1、算法思想2</b></p><p><b>　　2、詳細(xì)設(shè)計(jì)2</b></p><p><b>　　4 調(diào)試分析4</b></p><p>　　5 用戶使用說明5</p><p

4、><b>　　6課程設(shè)計(jì)總結(jié)6</b></p><p><b>　　參 考 文 獻(xiàn)7</b></p><p><b>　　題 目 描 述</b></p><p>　　任務(wù)：一堆猴子都有編號(hào)，編號(hào)是1，2，3 ...m ,這群猴子（m個(gè)）按照1-m的順序圍坐一圈，從第1開始數(shù)，每數(shù)到第N個(gè)，該

5、猴子就要離開此圈，這樣依次下來，直到圈中只剩下最后一只猴子，則該猴子為大王?！　?要求：</p><p>　　輸入數(shù)據(jù)：輸入m,n m,n 為整數(shù)，n<m</p><p>　　輸出形式：中文提示按照m個(gè)猴子，數(shù)n 個(gè)數(shù)的方法，輸出為大王的猴子是幾號(hào) ，建立一個(gè)函數(shù)來實(shí)現(xiàn)此功能</p><p><b>　　1、算法思想</b><

6、/p><p>　　將表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)，構(gòu)造循環(huán)鏈表 ‘*L’。由此，從表中任意一個(gè)結(jié)點(diǎn)開始，都可以遍歷全表。再用一個(gè)for循環(huán)來實(shí)現(xiàn)從第1開始數(shù)，第數(shù)到第N個(gè)，該猴子就要離開此圈。如果鏈表不空的話，用’a’指向開始結(jié)點(diǎn)，往后數(shù)到第N個(gè)結(jié)點(diǎn)，就把第N-1個(gè)結(jié)點(diǎn)與第N+1個(gè)結(jié)點(diǎn)鏈在一起，即實(shí)現(xiàn)了刪除第N個(gè)結(jié)點(diǎn)。如此反復(fù)，直到L的后繼結(jié)點(diǎn)是它自己，即圈中只剩最后一只猴子，那么這只猴子就

7、是大王。</p><p><b>　　2、詳細(xì)設(shè)計(jì)</b></p><p>　　1）、猴子的存放采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，利用循環(huán)鏈表來實(shí)現(xiàn)建立的，其表示方法是遞歸定義的：</p><p>　　typedef struct Mnode</p><p>　　{ int data;</p><p>　　str

8、uct Mnode *next;</p><p><b>　　}Mnode;</b></p><p>　　根據(jù)題目要求，要讓這M只猴子順序圍坐一圈，那就得用循環(huán)鏈表，只須將單循環(huán)鏈表的尾指針的NEXT域指向頭指針。它的判空條件是L=L->next =NULL；</p><p>　?。ǚ强毡恚?

9、 （空表） </p><p><b>　　單循環(huán)鏈表</b></p><p>　　2）、函數(shù)void hzxdw(M，N)讀取數(shù)據(jù)M、N后,然后就根據(jù)N的值，用for循環(huán)數(shù)猴子結(jié)點(diǎn)用’a’指向開始結(jié)點(diǎn)，往后數(shù)到第N個(gè)結(jié)點(diǎn)，就把第N-1個(gè)結(jié)點(diǎn)與第N+1個(gè)結(jié)點(diǎn)鏈在一起，即實(shí)現(xiàn)了刪除第N個(gè)結(jié)點(diǎn)。如此反復(fù)，直到L的后繼結(jié)點(diǎn)是它自己，即圈中只剩最后一只猴王。其源代碼

10、如下： </p><p>　　void hzxdw(int m,int n)//猴子選大王</p><p><b>　　{</b></p><p>　　Mnode *q,*p,*L,*pre;</p><p><b>　　int i;</b></p><p><b>

11、;　　//s作為n的標(biāo)志</b></p><p>　　for( i=0; i<m; i++)//為猴子編號(hào)</p><p><b>　　{</b></p><p><b>　　if(i==0)</b></p><p><b>　　{</b></p>

12、<p>　　p=(Mnode*)malloc(sizeof(Mnode));</p><p><b>　　if(!p)</b></p><p><b>　　{</b></p><p>　　printf("存儲(chǔ)空間分配失??！\n");</p><p><b>

13、;　　exit(0);</b></p><p><b>　　}</b></p><p>　　p->data=i+1;</p><p><b>　　L=p;</b></p><p>　　p->next=L;</p><p><b>　　}<

14、;/b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　q=(Mnode*)malloc(sizeof(Mnode));</p><p>　　q->data=i+1;</p><p>　　q->ne

15、xt=L;</p><p>　　p->next=q;</p><p><b>　　p=q;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　p=L;//從第一個(gè)猴子開始報(bào)數(shù)</p&g

16、t;<p>　　while(p!=p->next)//當(dāng)p＝p->next時(shí)表明猴子大王已選出</p><p><b>　　{</b></p><p>　　for(i=1; i<=n; i++)</p><p><b>　　{</b></p><p><b>

17、;　　if(i==n)</b></p><p><b>　　{</b></p><p><b>　　q=p;</b></p><p>　　pre->next=p->next;</p><p>　　p=p->next;</p><p><b&

18、gt;　　free(q);</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p><b>　　pre=p;</b></p><p

19、>　　p=p->next;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　printf("選出的猴王是%d號(hào)猴子\n",p->data);<

20、/p><p><b>　　} </b></p><p>　　本算法只用了兩個(gè)簡單的for循環(huán)，所以時(shí)間復(fù)雜度為O(N+MN-M)。其中難點(diǎn)是如何實(shí)現(xiàn)數(shù)到第N就刪除它。</p><p><b>　　4 調(diào)試分析</b></p><p><b>　　程序運(yùn)行截圖如下：</b>&l

21、t;/p><p><b>　　5 用戶使用說明</b></p><p>　　用戶根據(jù)提示輸入兩個(gè)整數(shù)，分別代表猴子M總數(shù)和報(bào)數(shù)N。</p><p><b>　　6課程設(shè)計(jì)總結(jié)</b></p><p>　　要提高自己的編程能力，你必須親自去體驗(yàn)、去設(shè)計(jì)、編輯、編譯、調(diào)試、運(yùn)行。在此之前，我也以為自己對(duì)C語

22、言已經(jīng)比較懂了，可還是遇到了一系列問題，也學(xué)到很多東西。每一個(gè)人都是在失敗、嘗試、失敗、嘗試與收獲中成長起來的。我本學(xué)識(shí)尚淺，無權(quán)談?wù)撨@些，只是希望能對(duì)大家有所警醒，編程之道漫漫無邊，吾將上下而求索.當(dāng)你看著自己把功能一個(gè)個(gè)實(shí)現(xiàn)，把錯(cuò)誤一個(gè)調(diào)試出來，那種感覺給了自己某種安慰，還有自信！讓自己對(duì)語言有了更深一層的了解！</p><p><b>　　參 考 文 獻(xiàn)</b></p>

23、<p>　　[1] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）。清華大學(xué)出版社,1997.4</p><p>　　附錄一 *** 程序代碼</p><p>　　#include<stdio.h></p><p>　　#include<stdlib.h></p><p>　　typedef struct Mnod

24、e</p><p><b>　　{</b></p><p><b>　　int data;</b></p><p>　　struct Mnode *next;</p><p><b>　　} Mnode;</b></p><p>　　void hzxdw

25、(int m,int n)//猴子選大王</p><p><b>　　{</b></p><p>　　Mnode *q,*p,*L,*pre;</p><p><b>　　int i;</b></p><p><b>　　//s作為n的標(biāo)志</b></p><

26、;p>　　for( i=0; i<m; i++)</p><p><b>　　{</b></p><p><b>　　if(i==0)</b></p><p><b>　　{</b></p><p>　　p=(Mnode*)malloc(sizeof(Mnode))

27、;</p><p><b>　　if(!p)</b></p><p><b>　　{</b></p><p>　　printf("存儲(chǔ)空間分配失??！\n");</p><p><b>　　exit(0);</b></p><p>&l

28、t;b>　　}</b></p><p>　　p->data=i+1;</p><p><b>　　L=p;</b></p><p>　　p->next=L;</p><p><b>　　}</b></p><p><b>　　else&

29、lt;/b></p><p><b>　　{</b></p><p>　　q=(Mnode*)malloc(sizeof(Mnode));</p><p>　　q->data=i+1;</p><p>　　q->next=L;</p><p>　　p->next=q;<

30、;/p><p><b>　　p=q;</b></p><p><b>　　}</b></p><p><b>　　}//為猴子編號(hào)</b></p><p><b>　　p=L;</b></p><p>　　while(p!=p->

31、next)//當(dāng)p＝p->next時(shí)表明猴子大王已選到</p><p><b>　　{</b></p><p>　　for(i=1; i<=n; i++)</p><p><b>　　{</b></p><p><b>　　if(i==n)</b></p>

32、;<p><b>　　{</b></p><p><b>　　q=p;</b></p><p>　　pre->next=p->next;</p><p>　　p=p->next;</p><p>　　free(q); //q->data號(hào)猴子出列</p&

33、gt;<p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p><b>　　pre=p;</b></p><p>　　p=p->next;</p>

34、<p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　printf("選出的猴王是%d號(hào)猴子\n",p->data);</p><p><b>　　}&

35、lt;/b></p><p>　　int main()</p><p><b>　　{</b></p><p><b>　　int m,n;</b></p><p>　　printf("請(qǐng)輸入猴子總數(shù)m和規(guī)定猴子報(bào)數(shù)n的值(當(dāng)n或m等于0時(shí)程序結(jié)束)：\n");</p

36、><p>　　while(scanf("%d%d",&m,&n)&&m&&n)</p><p><b>　　{</b></p><p>　　hzxdw(m,n);</p><p>　　printf("請(qǐng)輸入猴子總數(shù)m和規(guī)定猴子報(bào)數(shù)n的值(當(dāng)n或m等