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

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

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è)計2</b></p><p><b>　　4 調(diào)試分析4</b></p><p>　　5 用戶使用說明5</p><p

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

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

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

7、是大王。</p><p><b>　　2、詳細(xì)設(shè)計</b></p><p>　　1）、猴子的存放采用鏈?zhǔn)酱鎯Y(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個結(jié)點(diǎn)，就把第N-1個結(jié)點(diǎn)與第N+1個結(jié)點(diǎn)鏈在一起，即實(shí)現(xiàn)了刪除第N個結(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++)//為猴子編號</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("存儲空間分配失?。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;//從第一個猴子開始報數(shù)</p&g

16、t;<p>　　while(p!=p->next)//當(dāng)p＝p->next時表明猴子大王已選出</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號猴子\n",p->data);<

20、/p><p><b>　　} </b></p><p>　　本算法只用了兩個簡單的for循環(huán)，所以時間復(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ù)提示輸入兩個整數(shù)，分別代表猴子M總數(shù)和報數(shù)N。</p><p><b>　　6課程設(shè)計總結(jié)</b></p><p>　　要提高自己的編程能力，你必須親自去體驗(yàn)、去設(shè)計、編輯、編譯、調(diào)試、運(yùn)行。在此之前，我也以為自己對C語

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

31、next)//當(dāng)p＝p->next時表明猴子大王已選到</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號猴子出列</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號猴子\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("請輸入猴子總數(shù)m和規(guī)定猴子報數(shù)n的值(當(dāng)n或m等于0時程序結(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("請輸入猴子總數(shù)m和規(guī)定猴子報數(shù)n的值(當(dāng)n或m等