課程設計-猴子吃桃.doc

湖 南 工 學 院 數(shù)據(jù)結(jié)構(gòu)課程設計題 目： 數(shù)據(jù)結(jié)構(gòu)實現(xiàn)猴子吃桃系 別： 專 業(yè)： 年 級： 班 級： 學 生： 學 號： 目 錄l 論 文 提 要 3l 需 求 分 析 4l 詳 細 設 計 5n 數(shù)組結(jié)構(gòu) 5n 遞歸 7n 鏈表 9l 調(diào) 試 結(jié) 果 11l 調(diào)試分析 12論文提要初步分析說明數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)類型等基本概念；從抽象數(shù)據(jù)類型的角度，通過數(shù)學應用的分析，把問題進行分析，整理，面后通過觀察選擇適當?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)入及其相應的算法來解決問題,數(shù)據(jù)結(jié)構(gòu)課程主要是為了培養(yǎng)我們對數(shù)據(jù)的抽象能力和對算法在時間和空間和復雜度上進行優(yōu)化，猴子吃桃這一數(shù)學方面的例題是很典型的一道程序例題，在這里主要以C語言作為數(shù)據(jù)結(jié)構(gòu)和描述語言，分析并采用數(shù)組數(shù)據(jù)結(jié)構(gòu)，遞歸，鏈數(shù)據(jù)結(jié)構(gòu)實現(xiàn)上述問題。需 求 分 析實現(xiàn)課題猴子吃桃摘 要：猴子吃桃這一典型的數(shù)學課題,其主要實現(xiàn)的過程是將其數(shù)學課題公式化，用一些簡單的數(shù)據(jù)定義、初使化、通過一系列的條件判斷和循環(huán)用來實現(xiàn)學數(shù)公式的計算機化。通過C語言基礎分析和數(shù)據(jù)結(jié)構(gòu)初步了解,我們使用C語言,利用C和數(shù)據(jù)結(jié)構(gòu)的結(jié)合使用,讓我們在短時間內(nèi)建立起對數(shù)據(jù)結(jié)構(gòu)的進一步認識。然后,形成正確的對算法和優(yōu)有個的理解觀念。關鍵詞：C語言的基本了解，數(shù)據(jù)結(jié)構(gòu)的基本了解, 數(shù)據(jù)中數(shù)組的使用，遞歸調(diào)用，用C語言實現(xiàn)數(shù)據(jù)鏈表題目：猴子第一天摘下若干個桃子，當即吃了一半，還不癮，又多吃了一個，第二天早上又將剩下的桃子吃掉一半，又多吃了一個。以后每天早上都吃了前一天剩下的一半零一個。到第10天早上想再吃時，見只剩下一個桃子了，求第一天共摘了多少？ 要求： 采用數(shù)組，遞歸，鏈數(shù)據(jù)結(jié)構(gòu)實現(xiàn)上述求解 詳 細 設 計1 數(shù)組結(jié)構(gòu)把猴子吃桃的天數(shù)倒過來看的話，以天數(shù)作為數(shù)組的下標i，剩下桃子的個數(shù)ai的遞推公式為ai=(ai-1+1)*2。ai實際代表了倒數(shù)第i天剩下的桃子數(shù)。數(shù)組結(jié)構(gòu)算法的流程圖如圖3-1：開 始建立一個以天數(shù)為下標以剩下桃子數(shù)為元素的數(shù)組規(guī)定此數(shù)組的通向公式求第一天的桃子數(shù)結(jié) 束程序如下：#includevoid main() int i,tao10; tao9=1;/tao9代表第10天剩的桃子數(shù) for(i=8;i=0;i-) taoi=2*(taoi+1+1); printf(共摘了%d個桃子！n,tao0);2.鏈結(jié)構(gòu) 建立一個鏈表，根據(jù)每天桃子數(shù)與后一天桃子數(shù)的關系n=2*n+2,依次將每天的桃子數(shù)存進鏈表中，最后輸出第一天的桃子數(shù)。首先是建立一個空鏈表，產(chǎn)生一個頭結(jié)點，且將頭結(jié)點的地址賦給L。然后把每天的桃子數(shù)從鏈表的第一個結(jié)點插入鏈表。最后第一天的桃子數(shù)被最后一個插入鏈表，成為鏈表中第一個值，將其賦給e，最后只要輸出e即得到第一天的桃子數(shù)。程序如下：#includestdio.h#includestdlib.h#define TRUE 1#define FALSE 0#define NULL 0typedef int ElementType;typedef struct nodeElementType data;struct node *next;StackNode,*LinkStack;void InitStack(LinkStack top)top-next=NULL;int IsEmpty(LinkStack top) if(top-next=NULL) return TRUE;else return FALSE;int Push(LinkStack top,ElementType element)StackNode *temp;temp=(StackNode *)malloc(sizeof(StackNode);if(!temp) return FALSE;else temp-data=element;temp-next=top-next;top-next=temp; return TRUE;int Pop(LinkStack top,ElementType *element)if(IsEmpty(top) return FALSE;else StackNode *temp=top-next;*element=temp-data;top-next=temp-next;free(temp);return TRUE;void main() int i=10,data; Stack s; InitStack(s); PushStack(s,1); while(i-1) data=PopStack(s); PushStack(s,2*(data+1); printf(共摘了%d個桃子！n,PopStack(s);3.遞歸結(jié)構(gòu)設計遞歸算法，利用x=2*x+2，定義一個函數(shù)sum_fan，然后不斷調(diào)用自身，求得第一天的桃子數(shù)。遞歸算法的流程圖如圖3-3開 始定義參數(shù)i和ni0NY調(diào)用本身，且-i輸出sum開 始程序如下：#includeint tao(int n) if(n=10) return 1; return 2*(tao(n+1)+1);void main() int sum=0; sum+=tao(1); printf(共摘了%d個桃子！n,sum);調(diào) 試 結(jié) 果4.2運行結(jié)果數(shù)組結(jié)構(gòu)，鏈結(jié)構(gòu)，遞歸結(jié)構(gòu)的運行結(jié)果如圖：數(shù)組結(jié)構(gòu)結(jié)果 調(diào) 試 分 析 運行環(huán)境在本課程設計中，系統(tǒng)開發(fā)平臺為Windows2000,程序設計語言為Visual C+6.0，程序的運行環(huán)境為Visual C+ 6.0。Visual C+一般分為三個版本:學習版、專業(yè)版和企業(yè)版，不同的版本適合于不同類型的應用開發(fā)。實驗中可以使用這三個版本的任意一種，在本課程設計中，以Visual C+ 6.0為編程環(huán)境。 程序編輯體會 這次的課程設計的內(nèi)容是用C語言實現(xiàn)猴子吃桃子問題，這對我來說是個很具有挑戰(zhàn)性的任務，雖然只做了一個很簡單的學生學籍管理模塊，但通過兩個星期的設計也從中學到了不少東西，更深刻的理解了課本中的內(nèi)容。數(shù)據(jù)結(jié)構(gòu)是一門實踐性較強的課程，為了學好這門課程，必須在掌握理論知識的同時，加強上機實踐。同時再次深刻理解了C+中類的思想和實現(xiàn)，文件的概念和相關操作，以及有關數(shù)據(jù)結(jié)構(gòu)的很多知識。根據(jù)實際問題的需要，對個方面的優(yōu)缺點加以綜合平衡，從中選擇比較適宜的實現(xiàn)方法。在本次課程設計中，我明白了理論與實際相結(jié)合的重要性，并提高了自己組織數(shù)據(jù)及編寫程序的能力，培養(yǎng)了基本的，良好的程序設計技能。提高綜合運用所學知識的能力。在這次課程設計中曾遇到了不少問題，就單憑我一個人的能力很難準時有效的完成這次的課程設計，在此，我忠心感謝我的指導老師戴成秋。