數據結構課程設計---猴子吃桃子問題_第1頁
已閱讀1頁,還剩15頁未讀 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

1、<p><b>  目 錄</b></p><p><b>  1、需求分析1</b></p><p><b>  2、概要設計1</b></p><p>  2.1.用數組數據結構實現上述求解1</p><p>  2.2.用鏈數據結構實現上述求解1<

2、/p><p>  2.3 用棧數據結構實現求解1</p><p>  2.4 用遞歸實現上述求解2</p><p><b>  3、 運行環(huán)境2</b></p><p>  3.1 硬件環(huán)境2</p><p><b>  3.2軟件環(huán)境2</b></p>

3、<p><b>  4、 詳細設計2</b></p><p>  4.1系統流程圖2</p><p>  4.2用數組數據結構實現上述求解3</p><p>  4.3用鏈數據結構實現上述求解4</p><p>  4.4用棧數據結構實現求解5</p><p>  4.5用遞歸

4、實現上述求解6</p><p><b>  5、 調試分析7</b></p><p><b>  6、運行結果7</b></p><p><b>  課程設計總結8</b></p><p><b>  參考文獻9</b></p>&

5、lt;p><b>  附錄:9</b></p><p><b>  1、需求分析</b></p><p><b>  猴子吃桃子問題</b></p><p>  有一群猴子摘了一堆桃子,他們每天都吃當前桃子的一半且再多吃一個,到了第10天就只余下一個桃子。用多種方法實現求出原來這群猴子共摘了多

6、少個桃子。</p><p><b>  要求:</b></p><p>  1) 采用數組數據結構實現上述求解</p><p>  2) 采用鏈數據結構實現上述求解</p><p>  3) 采用棧實現上述求解</p><p>  4) 采用遞歸實現上述求解

7、</p><p><b>  2、概要設計</b></p><p>  2.1.用數組數據結構實現上述求解</p><p>  在taozi函數中定義一個一維數組,分別存儲每天的桃子個數,根據題目的內容找出各個數之間的關系,用數組元素表示出來,根據用戶輸入要計算哪一天的桃子,用for循環(huán)控制結束。在main函數中讓用戶輸入要計算的哪一天,調用t

8、aozi函數,以便用戶可查出任意一天的桃子個數,用switch語句判斷用戶要執(zhí)行的功能,然后用while循環(huán)控制,直到用戶輸入0為止。</p><p>  2.2.用鏈數據結構實現上述求解</p><p>  先寫出預定義常量和類型,寫出結點的類型定義,創(chuàng)建結點,初始化鏈表,定義變量并初始化,找出結點與其后繼結點之間的聯系,然后在主函數中控制。</p><p>  

9、2.3 用棧數據結構實現求解</p><p>  本部分包括預定義常量和類型,順序棧的定義,InitStack函數,Push函數,和main函數,在InitStack函數構造一個空棧,在Push函數中調用該函數,并在其中編寫控制棧頂指針和棧底指針移動的語句,找出指針所指向的數據之間的關系,在main函數中編寫控制循環(huán)結束的語句,最后再用main函數去調用Push函數。</p><p>  

10、2.4 用遞歸實現上述求解</p><p>  這種方法跟上述幾種不同,在函數的執(zhí)行函數的過程中,需多次進行自我調用,遞歸函數的運行過程類似與多個函數的嵌套調用,只是調用函數和被調用函數是同一個函數,從主函數開始調用,一次更深一層,退出時一步一步返回到上一層,所以不需寫控制循環(huán)語句,不需要寫控制循環(huán)語句,比上幾種方法簡單點。</p><p><b>  3、 運行環(huán)境</b

11、></p><p><b>  3.1 硬件環(huán)境</b></p><p><b>  PC</b></p><p><b>  3.2軟件環(huán)境</b></p><p> ?。?)Windows XP</p><p> ?。?)Microsoft V

12、isual C++6.0</p><p><b>  4、 詳細設計</b></p><p><b>  4.1系統流程圖</b></p><p>  4.2用數組數據結構實現上述求解</p><p><b>  //計算桃子的個數</b></p><p&g

13、t;  void taozi(int n,int m)</p><p><b>  {</b></p><p>  int day[10];//初始化變量,用數組元素分別存儲每天的桃子個數</p><p>  int i;//控制循環(huán)執(zhí)行的次數</p><p>  day[0]=n;//最后一天的桃子個數</p&g

14、t;<p>  for(i=0;i<10-m;i++)</p><p>  day[i+1]=2*(day[i]+1);//相鄰元素之間的關系</p><p>  printf("第%d天的桃子為:%d\n",m,day[10-m]);</p><p><b>  }</b></p><

15、;p>  void main()</p><p><b>  {</b></p><p>  int m;//用戶要計算的是第幾天</p><p>  printf("請輸入要求第幾天剩下的桃子:\n");</p><p>  scanf("%d",&m);</

16、p><p>  taozi(1,m);//調用</p><p><b>  while(1){</b></p><p>  int j;//循環(huán)控制條件</p><p>  printf("請輸入j的值 0:退出 1:繼續(xù):\n");</p><p>  scanf("

17、%d",&j);</p><p>  switch(j){</p><p>  //當j=1時,用戶可以輸入多次想要的數值</p><p><b>  case 1:</b></p><p>  printf("請輸入要求第幾天剩下的桃子:\n");</p><p

18、>  scanf("%d",&m);</p><p>  taozi(1,m);</p><p>  break;//跳出</p><p>  //當j=0時,跳出switch結構</p><p><b>  case 0:</b></p><p><b&g

19、t;  return;</b></p><p><b>  break;</b></p><p>  //當用戶輸入除0和1以外的數值時,會讓你重新輸入,直到輸入正確為止</p><p><b>  default:</b></p><p>  printf("輸入有誤請重新輸

20、入!");</p><p><b>  }</b></p><p><b>  }</b></p><p><b>  }</b></p><p>  4.3用鏈數據結構實現上述求解</p><p>  //預定義常量和類型</p>

21、<p>  #define NULL 0</p><p>  //單鏈表的存儲結構</p><p>  typedef struct LNode{</p><p>  int data;//數據域</p><p>  struct LNode *next;//指針域</p><p><b>  

22、}LNode;</b></p><p><b>  LNode *L;</b></p><p>  LNode *p,*s;</p><p><b>  //計算桃子的個數</b></p><p>  int CreateList_L(int e,int m)//e是第十天的桃子的個數,

23、m是將要計算的是第幾天</p><p><b>  { </b></p><p><b>  int i;</b></p><p>  L=(LNode *) malloc(sizeof(LNode));//生成新結點</p><p>  p=(LNode *) malloc(sizeof(LN

24、ode));</p><p>  L->next=NULL;//創(chuàng)建一個帶頭結點的單鏈表</p><p>  L->next=p;//插入到表頭</p><p>  L->next->data=e;//初始化第一個結點</p><p>  for(i=m-1;i>0;i--)</p><p&g

25、t;<b>  {</b></p><p>  s=(LNode *) malloc(sizeof(LNode));</p><p>  p->next=s;</p><p>  s->data=2*(p->data+1);//結點與下一結點之間的聯系</p><p>  p=s;//指針P總是指向最后

26、一個結點</p><p>  s->next=NULL;</p><p><b>  }</b></p><p>  printf("第%d天的桃子為:%d\n",11-m,p->data);</p><p><b>  }</b></p><p&

27、gt;  4.4用棧數據結構實現求解</p><p>  //儲存空間初始分配量</p><p>  #define STACK_INIT_SIZE 100 </p><p><b>  //順序棧的定義</b></p><p>  typedef struct</p><p><b>

28、  {</b></p><p>  int *base;//棧底指針</p><p>  int *top;//棧頂指針</p><p>  int stacksize;//當前已分配的存儲空間</p><p><b>  }SqStack;</b></p><p>  SqStack

29、 s;</p><p><b>  //構造一個空棧</b></p><p>  int InitStack()</p><p><b>  {</b></p><p>  s.base=(int *) malloc(STACK_INIT_SIZE * sizeof(int));</p>

30、<p>  if(!s.base)</p><p>  exit (OVERFLOW);//存儲分配失敗</p><p>  s.top=s.base;//剛開始棧為空</p><p>  s.stacksize=20;</p><p>  return OK;</p><p><b>  }&

31、lt;/b></p><p>  //計算桃子個數的函數</p><p>  void Push(int e,int m)// m是要計算的是第幾天</p><p><b>  {</b></p><p><b>  int i;</b></p><p>  InitS

32、tack();</p><p>  *s.top++=e;//給棧底元素初始化</p><p>  for(i=0;i<10-m;i++)</p><p><b>  {</b></p><p>  *s.top=2*(*(s.top-1)+1);//棧頂元素和剛插入的元素之間的關系</p><

33、p>  s.top++;//每插入一個棧頂元素,指針就要自加1</p><p><b>  }</b></p><p>  printf("第%d天的桃子為:%d\n",m,*(s.top-1));</p><p><b>  }</b></p><p>  4.5用遞歸實

34、現上述求解</p><p>  int i=9;//初始化全局變量</p><p><b>  //遞歸函數</b></p><p>  int taozi(int x)</p><p><b>  {</b></p><p><b>  int y;</b&

35、gt;</p><p>  while(i>0)</p><p><b>  {</b></p><p>  y=2*(x+1);</p><p>  i--;//循環(huán)控制條件</p><p><b>  taozi(y);</b></p><p&g

36、t;  printf("%d\n",y);</p><p><b>  }</b></p><p><b>  }</b></p><p><b>  5、 調試分析</b></p><p>  1 在用鏈數據結構實現時,運行時沒有顯示錯誤,但輸出不是預測的

37、結果,代碼如下:</p><p>  for(i=m-1;i>0;i--)</p><p><b>  {</b></p><p>  s=(LNode *) malloc(sizeof(LNode));</p><p>  p->next=s;</p><p>  s->dat

38、a=2*(p->data+1);</p><p>  s->next=NULL;</p><p><b>  }</b></p><p>  在指針的移動時,由于p總是第一個結點,在for循環(huán)前已經被賦值,指針P 應該總是指向最后一個結點的,所以在這句s->next=NULL前加上一句p=s就行了, 就能輸出正確結果。<

39、/p><p>  2 在生成新結點時,一定要用強制類型轉換,要不就要出錯。不能把s=(LNode *) malloc(sizeof(LNode))寫成s=(LNode) malloc(sizeof(LNode));因為它們不屬于同一類型。</p><p>  3 在用棧數據結構實現的過程中,雖然只有一個錯誤,但卻顯示了好多錯誤。主要原因是由于一個參數是在main函數中定義的,但卻被其它函數調用

40、,只要把該參數定義成全局變量就行了。</p><p>  4 在用while循環(huán)時,由于控制條件的不恰當導致的錯誤,不過只要再認真分析一下,就正確了。</p><p>  5 還有些其它方面的錯誤,不過只要看一眼,就能改正,是粗心造成的。</p><p><b>  6、運行結果</b></p><p>  鏈數組和棧實

41、現結果:</p><p><b>  遞歸實現結果:</b></p><p><b>  課程設計總結</b></p><p>  通過這一周的實踐學習,我認識到學好計算機要重視實踐操作,不僅僅是學習數據結構,以及其它的計算機方面的知識都要重在實踐,很多以前學過的東西,在運用時都不能很熟練,也說明理論知識和實踐之間的差別。

42、這就告訴了我們在以后的學習過程中要培養(yǎng)自己的動手能力,要將學過的知識轉化為實踐。作為一個計科專業(yè)的學生,通過這周的學習,使我更加明白了動手能力的重要性。</p><p>  在這次的課程設計中,我不斷地去找書本知識和查閱其它有關資料,不僅鞏固了對課本知識的掌握,還有利于以后更好的進步,提高了對課外知識的了解,雖然花費了不少時間,但只要學到有價值的東西,我認為都是值得的。在完成該試驗的過程中,我問了同學和老師,還查

43、閱了很多和鏈表有關系的書籍,通過學習,翻看以前學過的知識,使我明白了我在學習知識上的很多不足。不過在此同時又重新復習了課本,從中學到了許多以前未學到的知識,感覺非常有成就感,讓我對自己更加有信心,讓我對數據結構這門課程也更感興趣了,以前我一直感覺枯燥難學的數據結構,現在我也愿意去認真研究學習了。</p><p>  這次數據結構課程設計中,多虧了我的指導老師xx老師的悉心教導。在以后的學習過程中,我要認真負責地對

44、待課本中的每一個知識點,進一步充實自己,提高自己。</p><p><b>  參考文獻</b></p><p>  [1] 黃同成,黃俊民,董建寅.數據結構[M].北京:中國電力出版社,2008</p><p>  [2] 董建寅,黃俊民,黃同成.數據結構實驗指導與題解[M].北京:中國電力出版社,2008</p><p&

45、gt;  [3] 嚴蔚敏,吳偉民. 數據結構(C語言版)[M]. 北京:清華大學出版社,2002</p><p>  [4] 劉振鵬,張曉莉,郝杰.數據結構[M].北京:中國鐵道出版社,2003</p><p><b>  附錄: </b></p><p><b>  源代碼如下</b></p><p&

46、gt;  1 用數組數據結構編寫</p><p>  #include<stdio.h></p><p>  void taozi(int n,int m)</p><p><b>  {</b></p><p>  int day[10];</p><p><b>  in

47、t i;</b></p><p><b>  day[0]=n;</b></p><p>  for(i=0;i<10-m;i++)</p><p>  day[i+1]=2*(day[i]+1);</p><p>  printf("第%d天的桃子為:%d\n",m,day[10-

48、m]);</p><p><b>  }</b></p><p>  void main()</p><p><b>  {</b></p><p><b>  int m;</b></p><p>  printf("請輸入要求第幾天剩下的桃

49、子:\n");</p><p>  scanf("%d",&m);</p><p>  taozi(1,m);</p><p><b>  while(1){</b></p><p><b>  int j;</b></p><p>  

50、printf("請輸入j的值 0:退出 1:繼續(xù):\n");</p><p>  scanf("%d",&j);</p><p>  switch(j){</p><p><b>  case 1:</b></p><p>  printf("請輸入要求第幾天剩

51、下的桃子:\n");</p><p>  scanf("%d",&m);</p><p>  taozi(1,m);</p><p><b>  break;</b></p><p><b>  case 0:</b></p><p>&

52、lt;b>  return;</b></p><p><b>  break;</b></p><p><b>  default:</b></p><p>  printf("輸入有誤請重新輸入!");</p><p><b>  }</b&g

53、t;</p><p><b>  }</b></p><p><b>  }</b></p><p>  2 用鏈數據結構編寫</p><p>  #include<stdio.h></p><p>  #include<stdlib.h></p

54、><p>  #define NULL 0</p><p>  typedef struct LNode{</p><p><b>  int data;</b></p><p>  struct LNode *next;</p><p><b>  }LNode;</b><

55、;/p><p><b>  LNode *L;</b></p><p>  LNode *p,*s;</p><p>  int CreateList_L(int e,int m)</p><p><b>  { </b></p><p><b>  int i;&

56、lt;/b></p><p>  L=(LNode *) malloc(sizeof(LNode));</p><p>  p=(LNode *) malloc(sizeof(LNode));</p><p>  L->next=NULL;//創(chuàng)建頭結點</p><p>  L->next=p;</p><

57、;p>  L->next->data=e;</p><p>  for(i=m-1;i>0;i--)</p><p><b>  {</b></p><p>  s=(LNode *) malloc(sizeof(LNode));</p><p>  p->next=s;</p>

58、<p>  s->data=2*(p->data+1);</p><p>  p=s;//指針P總是指向最后一個結點</p><p>  s->next=NULL;</p><p><b>  }</b></p><p>  printf("第%d天的桃子為:%d\n"

59、,11-m,p->data);</p><p><b>  }</b></p><p>  void main()</p><p><b>  {</b></p><p><b>  int n;</b></p><p><b>  in

60、t k;</b></p><p>  printf("請輸入要求第幾天剩下的桃子:\n");</p><p>  scanf("%d",&n);</p><p><b>  k=11-n;</b></p><p>  CreateList_L(1,k);<

61、/p><p><b>  while(1){</b></p><p><b>  int j;</b></p><p>  printf("請輸入j的值 0:退出 1:繼續(xù):\n");</p><p>  scanf("%d",&j);</p>

62、;<p>  switch(j){</p><p><b>  case 1:</b></p><p>  printf("請輸入要求第幾天剩下的桃子:\n");</p><p>  scanf("%d",&n);</p><p><b>  k=1

63、1-n;</b></p><p>  CreateList_L(1,k);</p><p><b>  break;</b></p><p><b>  case 0:</b></p><p><b>  return;</b></p><p&g

64、t;<b>  break;</b></p><p><b>  default:</b></p><p>  printf("輸入有誤請重新輸入!");</p><p><b>  }</b></p><p><b>  }</b>&

65、lt;/p><p><b>  }</b></p><p>  3 用棧數據結構編寫</p><p>  #include<stdio.h></p><p>  #include<stdlib.h></p><p>  #define STACK_INIT_SIZE 100 &

66、lt;/p><p>  #define OK 1</p><p>  #define OVERFLOW -2</p><p>  typedef struct</p><p><b>  {</b></p><p>  int *base;</p><p><b> 

67、 int *top;</b></p><p>  int stacksize;</p><p><b>  }SqStack;</b></p><p>  SqStack s;</p><p>  int InitStack()</p><p><b>  {</b&g

68、t;</p><p>  s.base=(int *) malloc(STACK_INIT_SIZE * sizeof(int));</p><p>  if(!s.base)</p><p>  exit (OVERFLOW);</p><p>  s.top=s.base;</p><p>  s.stacksiz

69、e=20;</p><p>  return OK;</p><p><b>  }</b></p><p>  void Push(int e,int m)</p><p><b>  {</b></p><p><b>  int i;</b><

70、;/p><p>  InitStack();</p><p>  *s.top++=e;</p><p>  for(i=0;i<10-m;i++)</p><p><b>  {</b></p><p>  *s.top=2*(*(s.top-1)+1);</p><p&g

71、t;<b>  s.top++;</b></p><p><b>  }</b></p><p>  printf("第%d天的桃子為:%d\n",m,*(s.top-1));</p><p><b>  }</b></p><p>  void main(

72、)</p><p><b>  { </b></p><p><b>  int m;</b></p><p>  printf("請輸入要求第幾天剩下的桃子:\n");</p><p>  scanf("%d",&m);</p><

73、;p>  Push(1,m);</p><p><b>  while(1){</b></p><p><b>  int j;</b></p><p>  printf("請輸入j的值 0:退出 1:繼續(xù):\n");</p><p>  scanf("%d&q

74、uot;,&j);</p><p>  switch(j){</p><p><b>  case 1:</b></p><p>  printf("請輸入要求第幾天剩下的桃子:\n");</p><p>  scanf("%d",&m);</p>&

75、lt;p>  Push(1,m);</p><p><b>  break;</b></p><p><b>  case 0:</b></p><p><b>  return;</b></p><p><b>  break;</b></p

76、><p><b>  default:</b></p><p>  printf("輸入有誤請重新輸入!");</p><p><b>  }</b></p><p><b>  }</b></p><p><b>  }<

77、;/b></p><p><b>  4 用遞歸編寫</b></p><p>  #include<stdio.h></p><p><b>  int i=9;</b></p><p>  int taozi(int x)</p><p><b>

78、;  {</b></p><p><b>  int y;</b></p><p>  while(i>0)</p><p><b>  {</b></p><p>  y=2*(x+1);</p><p><b>  i--;</b>

79、</p><p><b>  taozi(y);</b></p><p>  printf("%d\n",y);</p><p><b>  }</b></p><p><b>  }</b></p><p>  void main(

80、)</p><p><b>  {</b></p><p><b>  int a=1;</b></p><p><b>  taozi(a);</b></p><p>  printf("1\n");</p><p><b&g

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論