《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)二叉連鏈表.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)二叉連鏈表.doc（14頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、 課程設(shè)計(jì)指導(dǎo)書 姓 名 學(xué) 號 班 級 課程名稱 數(shù)據(jù)結(jié)構(gòu) 課程性質(zhì) 專業(yè)必修課 設(shè)計(jì)時(shí)間 2010 年 12 月 1日—— 2010 年 12月 20日 設(shè)計(jì)名稱 設(shè)計(jì)二叉鏈表結(jié)構(gòu)的相關(guān)函數(shù)庫 設(shè)計(jì)目的 使用Microsoft Visual C++ 設(shè)計(jì)二叉鏈表結(jié)構(gòu)的相關(guān)函數(shù)庫，并能夠在程序設(shè)計(jì)中調(diào)用 設(shè)計(jì)要求 設(shè)計(jì)二叉鏈表結(jié)構(gòu)的相關(guān)函數(shù)庫，以便在程序設(shè)計(jì)中調(diào)用，實(shí)現(xiàn)二叉樹的各種基本函數(shù)以及常用函數(shù)；并給出1-2個(gè)例子，通過調(diào)用自己的庫函數(shù)來實(shí)現(xiàn)問題的求解。 設(shè)計(jì)思路 與 設(shè)計(jì)過程 1. 程序需求分析 完成：根據(jù)需求分析，確定

2、各個(gè)程序功能的需求； 2. 程序總統(tǒng)設(shè)計(jì) 完成：根據(jù)程序需求，進(jìn)行程序大概框架的設(shè)計(jì)； 3. 主函數(shù)設(shè)計(jì) 完成：主函數(shù)程序中設(shè)計(jì)一個(gè)菜單，并調(diào)試所用算法； 4. 其他函數(shù)設(shè)計(jì) 完成：建立二叉鏈表以及遞歸序列遍歷算法 5. 系統(tǒng)程序完善 完成：完善整個(gè)程序細(xì)節(jié)代碼的要求，進(jìn)行調(diào)試。 計(jì)劃與進(jìn)度 12.1-12.2 復(fù)習(xí)對vc++6.0使用，了解關(guān)于二叉鏈表的相關(guān)特征等。 12.3-12.4 查找有關(guān)二叉鏈表基本操作的算法等。 12.5-12.7 根據(jù)需求分析，確立各個(gè)函數(shù)程序功能。 12.8-12.10 根據(jù)程序需求，進(jìn)行相關(guān)子函數(shù)

3、程序的編寫。 12.11-12.13 進(jìn)行主函數(shù)程序功能的設(shè)計(jì)編寫。 12.14-12.16 進(jìn)行對整個(gè)程序的完善。 12.17-12.18 進(jìn)行程序的調(diào)試運(yùn)行。 12.19-12.20 資料歸檔，填寫相關(guān)文檔。 任課教師 意 見 備 注 課程設(shè)計(jì)報(bào)告 課程： 學(xué)號： 姓名： 班級： 教師 時(shí)間： 計(jì)算機(jī)科學(xué)與技術(shù)系 設(shè)計(jì)名稱： 設(shè)計(jì)二叉鏈表的相關(guān)函數(shù)庫 日期：2010年 12 月 20 日 設(shè)計(jì)內(nèi)容：使用Microsoft Visual C++ 設(shè)計(jì)二

4、叉鏈表結(jié)構(gòu)的相關(guān)函數(shù)庫，以便在程序設(shè)計(jì)中調(diào)用 設(shè)計(jì)目的與要求：設(shè)計(jì)二叉鏈表結(jié)構(gòu)的相關(guān)函數(shù)庫，在程序設(shè)計(jì)中調(diào)用，并實(shí)現(xiàn)二叉樹的各種基本函數(shù)以及常用函數(shù)。 設(shè)計(jì)環(huán)境或器材、原理與說明： 器材：計(jì)算機(jī)一臺(tái) 硬件環(huán)境： 處理器：Intel core i3 內(nèi)存： 1GB 硬盤空間：320GB 顯卡：ATI Mobility Radeon 軟件環(huán)境： Windows XP,Microsoft Visual C++6.0 使用數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)的一般方法步驟進(jìn)行設(shè)計(jì)。 設(shè)計(jì)過程（步驟）和部分程序代碼(可以加頁)： 一． 題目要求 設(shè)計(jì)二叉鏈表結(jié)構(gòu)的相關(guān)函數(shù)庫，在程序設(shè)計(jì)

5、中調(diào)用，并實(shí)現(xiàn)二叉樹的各種基本函數(shù)以及常用函數(shù)。 二． 需求分析 建立一棵二叉樹： （1）二叉樹的鏈表結(jié)構(gòu)； （2）進(jìn)行先序遍歷，輸出結(jié)果； （3）進(jìn)行中序遍歷，輸出結(jié)果； （4）進(jìn)行后序遍歷，輸出結(jié)果； （5）進(jìn)行層次遍歷，輸出結(jié)果。 三． 運(yùn)行環(huán)境 Windows XP 四． 開發(fā)工具和編程語言 1.開發(fā)工具：Microsoft Visual C++6.0 2.編程語言：C語言 五． 概要設(shè)計(jì) 1. 數(shù)據(jù)結(jié)構(gòu) typedef char datatype; typedef struct node //定

6、義二叉樹結(jié)點(diǎn)類型 { datatype data; struct node *lchild; struct node *rchild; }Btnode,* Btree; 2.模塊劃分 1．根據(jù)先序遞歸建立二叉樹 Btree pre_creat() 2．遞歸遍歷輸出函數(shù) void preorder_btree(Btree root) //由先根序列遍歷輸出二叉樹 void inorder_btree(Btree root) //由中根序列遍歷輸出二叉樹 void postorder_btree(Btree ro

7、ot) //由后根序列遍歷輸出二叉樹 3．層次遍歷輸出算法 void level_btree(Btree root) //層次遍歷輸出二叉樹 六． 詳細(xì)設(shè)計(jì) 1．創(chuàng)建二叉樹的實(shí)現(xiàn) Btree pre_creat() //使用先根序列建立二叉樹，返回指針 { Btree t; char ch; fflush(stdin); scanf("%c",&ch); //輸入一個(gè)結(jié)點(diǎn)數(shù)據(jù) if(ch==@) return NULL; //空結(jié)點(diǎn) else { t=(Btnode *)m

8、alloc(sizeof(Btnode)); //申請結(jié)點(diǎn)空間，根節(jié)點(diǎn) t->data=ch; t->lchild=pre_creat(); //生成左子樹 t->rchild=pre_creat(); //生成右子樹 } return t; } 2．先序、中序、后序遞歸遍歷輸出算法 void preorder_btree(Btree root) //由先根序列輸出二叉樹 { Btree p=root; if(p!=NULL) { printf("%3c",p->data); //輸出結(jié)點(diǎn)值

9、 preorder_btree(p->lchild); //輸出左子樹 preorder_btree(p->rchild); //輸出右子樹 } } void inorder_btree(Btree root) //由中根序列輸出二叉樹 { Btree p=root; if(p!=NULL) { inorder_btree(p->lchild); //輸出左子樹 printf("%3c",p->data); //輸出結(jié)點(diǎn)值 inorder_btree(p->rchild); //輸出右子樹 } }

10、void postorder_btree(Btree root) //由后根序序列輸出二叉樹 { Btree p=root; if(p!=NULL) { postorder_btree(p->lchild); //輸出左子樹 postorder_btree(p->rchild); //輸出右子樹 printf("%3c",p->data); //輸出結(jié)點(diǎn)值 } } 3.層次遍歷輸出算法 void level_btree(Btree root) //層次遍歷輸出二叉樹 {

11、 Btree p; p=(Btnode *)malloc(sizeof(Btnode)); //申請一個(gè)新結(jié)點(diǎn) p->data=@; p->lchild=p->rchild=NULL; //為新結(jié)點(diǎn)賦初值 int front, rear; front=rear=0; //置空隊(duì)列 p=root; //工作結(jié)點(diǎn)指向根節(jié)點(diǎn) if(p!=NULL) { rear ++; Q[rear]=p;

12、 //結(jié)點(diǎn)不為空就入隊(duì) if(rear==1) { front=1; Q[front]=p; //根節(jié)點(diǎn)入隊(duì)作為隊(duì)列頭結(jié)點(diǎn) rear ++; } while(front!=rear) { p=Q[front]; //隊(duì)頭結(jié)點(diǎn)出隊(duì) front ++; printf("%3c",p->data); if(p->lchild!=NULL) { Q[rear]=p->lchild;

13、 rear ++; } if(p->rchild!=NULL) { Q[rear]=p->rchild; rear ++; } } } } 這三個(gè)函數(shù)實(shí)現(xiàn)了二叉樹的遞歸遍歷方法。先序思想是先根、后左孩子、再右孩子，中序遍歷思想是先左孩子、后根、再右孩子，后序是先左孩子、后右孩子、再根。 4.主函數(shù) int main() { Btree boot; boot=(Btnode *)malloc(sizeof(Btnode)); boot=NULL; int x; do { printf

14、("_____________________________________\n"); printf("--------------歡迎使用！-------------\n"); printf("_____________________________________\n"); printf("\n***************主菜單****************\n"); printf(" x=1... 先序遍歷建立二叉樹!\n"); printf(" x=2... 先序遍歷輸出二叉樹!\n");

15、 printf(" x=3... 中序遍歷輸出二叉樹!\n"); printf(" x=4... 后序遍歷輸出二叉樹!\n"); printf(" x=5... 層次遍歷輸出二叉樹!\n"); printf(" x=0... 退出\n"); printf("****************************************\n"); do { fflush(stdin); printf("請輸入x的值:"); scanf("%d",&x);

16、 if((x!=1)&&(x!=2)&&(x!=3)&&(x!=4)&&(x!=0)&&(x!=5)) { printf("請輸入正確的x的值\n"); } }while((x!=1)&&(x!=2)&&(x!=3)&&(x!=4)&&(x!=0)&&(x!=5)); switch(x) { case 1: printf("\t先序遍歷建立二叉樹:\n"); printf("\t請輸入二叉樹結(jié)點(diǎn)的值!:\n"); printf("(可以輸n個(gè)值均為字母或@(n<100)字符間以回車

17、符換行,想結(jié)束時(shí)輸多個(gè)@):\n"); boot=pre_creat(); //順序表的逆置 printf("\n\n"); break; case 2: printf("\t先序遍歷輸出二叉樹！:\n"); printf("建立的二叉樹是: "); preorder_btree(boot); printf("\n\n"); break; case 3: printf("\t中序遍歷輸出二叉樹！:\n");

18、 printf("建立的二叉樹是: "); inorder_btree(boot); printf("\n\n"); break; case 4: printf("\t后序遍歷輸出二叉樹！:\n"); printf("建立的二叉樹是: "); postorder_btree(boot); printf("\n\n"); break; case 5: printf("\

19、t層次遍歷輸出二叉樹！:\n"); printf("建立的二叉樹是: "); level_btree(boot); printf("\n\n"); break; } }while(x!=0); printf("ByeBye!"); return x; } 7. 運(yùn)行結(jié)果： 圖 一 圖 二 圖 三 圖 四

20、 圖 五 圖 六 圖 七 設(shè)計(jì)結(jié)果與分析(可以加頁)： 本次課程設(shè)計(jì)實(shí)現(xiàn)了二叉鏈表的相關(guān)函數(shù)庫的調(diào)用。為了實(shí)現(xiàn)以鏈表為存儲(chǔ)結(jié)構(gòu)的二叉樹的有關(guān)操作，要熟練掌握二叉鏈表的特性，但對于一些算法較為復(fù)雜，代碼量多些，容易出現(xiàn)一些變量的定義、函數(shù)聲明、函數(shù)調(diào)用等細(xì)節(jié)上的問題出錯(cuò)。在本程序的設(shè)計(jì)過程中，為了克服以上困難，采取了一些措施：建立清晰的程序設(shè)計(jì)的步驟方法，分步各個(gè)模塊程序設(shè)計(jì)，進(jìn)行仔細(xì)的總體結(jié)構(gòu)設(shè)計(jì)，反復(fù)調(diào)試、細(xì)心觀察達(dá)到完善整個(gè)系統(tǒng)等。 設(shè)計(jì)體會(huì)與建議：數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)程序設(shè)計(jì)的重要理論技術(shù)基礎(chǔ)，在理論學(xué)習(xí)

21、和基礎(chǔ)實(shí)驗(yàn)的基礎(chǔ)上，通過實(shí)踐設(shè)計(jì)一定量的程序，掌握應(yīng)用計(jì)算機(jī)解決實(shí)際問題的基本方法，是理解和運(yùn)用數(shù)據(jù)結(jié)構(gòu)及算法，提高編程能力的有效途徑，并為學(xué)習(xí)軟件專業(yè)課程積累理論基礎(chǔ)和實(shí)踐基礎(chǔ)。程序的設(shè)計(jì)和開發(fā)過程，不僅要求我們牢固地掌握各種基礎(chǔ)知識(shí)，更考查了對基礎(chǔ)知識(shí)的綜合運(yùn)用能力。這次我的實(shí)驗(yàn)課題是二叉樹的基本算法綜合分析。算法是數(shù)據(jù)結(jié)構(gòu)的核心，是我們學(xué)習(xí)軟件開發(fā)必須掌握的基本知識(shí)。 簡單課程設(shè)計(jì)最重要的是基礎(chǔ)知識(shí)的運(yùn)用，以及綜合分析問題的能力。二叉樹的遞歸算法主要是將二叉樹存儲(chǔ)到鏈表結(jié)構(gòu)中。遍歷是二叉樹各種操作的基礎(chǔ)，先序、中序、后序是二叉樹遍歷的三種基本遍歷方法。而這些都是數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)內(nèi)容，是我

22、們必須理解和牢記的基礎(chǔ)知識(shí)。將這些基礎(chǔ)算法綜合起來，更能清晰地認(rèn)識(shí)和理解各種算法的作用。當(dāng)然，要學(xué)會(huì)編程不會(huì)僅局限于課本知識(shí)，而是根據(jù)課本知識(shí)進(jìn)行有效的拓展，并且不得不學(xué)會(huì)在眾多的參考資料中搜索有用的自己所需的知識(shí)，并迫使自己去學(xué)習(xí)掌握它們，從中不斷提高自己。例如，課本上只給出了二叉樹的遞歸中序遍歷方法，由此可容易推出遞歸的前序和中序遍歷方法。 二叉樹的基本操作是多種多樣的，由于時(shí)間的短促和作者水平有限，因不能做太大規(guī)模的設(shè)計(jì)。雖然程序規(guī)模不大，我依然為此付出了努力，仍免不了各種錯(cuò)誤的出現(xiàn)。編程過程需要很大的毅力和耐心，而且要有良好的思維和扎實(shí)的專業(yè)基礎(chǔ)知識(shí)，所以我需要不斷的學(xué)習(xí)，發(fā)現(xiàn)自身不足之處并改正它，逐步提高自身能力，不斷取得進(jìn)步。對于數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)，我一直感到很吃力，但想過放棄。通過實(shí)踐，讓我們認(rèn)識(shí)到知識(shí)的運(yùn)用性，并加深對基礎(chǔ)知識(shí)的理解，從中了解自己需要學(xué)習(xí)的東西并學(xué)會(huì)自學(xué)。在此我要感謝我的老師對我們專心致志的輔導(dǎo)，讓我學(xué)會(huì)了許多分析和解決問題的方法，讓我受益匪淺。作為一名計(jì)算機(jī)專業(yè)的學(xué)生，今后我將加倍努力學(xué)習(xí)專業(yè)知識(shí)，為自己從事的職業(yè)打下堅(jiān)實(shí)基礎(chǔ)。 設(shè)計(jì)成績： 教師簽名： 年 月 日