課程設(shè)計(jì)-猴子吃桃.doc

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