數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)二叉連鏈表.doc

課程設(shè)計(jì)指導(dǎo)書(shū)姓 名學(xué) 號(hào)班 級(jí)課程名稱數(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ù)庫(kù)設(shè)計(jì)目的使用Microsoft Visual C+ 設(shè)計(jì)二叉鏈表結(jié)構(gòu)的相關(guān)函數(shù)庫(kù)，并能夠在程序設(shè)計(jì)中調(diào)用設(shè)計(jì)要求設(shè)計(jì)二叉鏈表結(jié)構(gòu)的相關(guān)函數(shù)庫(kù)，以便在程序設(shè)計(jì)中調(diào)用，實(shí)現(xiàn)二叉樹(shù)的各種基本函數(shù)以及常用函數(shù)；并給出1-2個(gè)例子，通過(guò)調(diào)用自己的庫(kù)函數(shù)來(lái)實(shí)現(xiàn)問(wèn)題的求解。設(shè)計(jì)思路與設(shè)計(jì)過(guò)程1. 程序需求分析完成：根據(jù)需求分析，確定各個(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í)對(duì)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ù)程序的編寫(xiě)。12.11-12.13 進(jìn)行主函數(shù)程序功能的設(shè)計(jì)編寫(xiě)。12.14-12.16 進(jìn)行對(duì)整個(gè)程序的完善。12.17-12.18 進(jìn)行程序的調(diào)試運(yùn)行。12.19-12.20 資料歸檔，填寫(xiě)相關(guān)文檔。任課教師意 見(jiàn)備 注課程設(shè)計(jì)報(bào)告課程：學(xué)號(hào)：姓名：班級(jí)：教師時(shí)間：計(jì)算機(jī)科學(xué)與技術(shù)系設(shè)計(jì)名稱： 設(shè)計(jì)二叉鏈表的相關(guān)函數(shù)庫(kù)日期：2010年 12 月 20 日 設(shè)計(jì)內(nèi)容：使用Microsoft Visual C+ 設(shè)計(jì)二叉鏈表結(jié)構(gòu)的相關(guān)函數(shù)庫(kù)，以便在程序設(shè)計(jì)中調(diào)用設(shè)計(jì)目的與要求：設(shè)計(jì)二叉鏈表結(jié)構(gòu)的相關(guān)函數(shù)庫(kù)，在程序設(shè)計(jì)中調(diào)用，并實(shí)現(xiàn)二叉樹(shù)的各種基本函數(shù)以及常用函數(shù)。設(shè)計(jì)環(huán)境或器材、原理與說(shuō)明：器材：計(jì)算機(jī)一臺(tái)硬件環(huán)境：處理器：Intel core i3內(nèi)存： 1GB硬盤(pán)空間：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ì)過(guò)程（步驟）和部分程序代碼(可以加頁(yè))：一 題目要求 設(shè)計(jì)二叉鏈表結(jié)構(gòu)的相關(guān)函數(shù)庫(kù)，在程序設(shè)計(jì)中調(diào)用，并實(shí)現(xiàn)二叉樹(shù)的各種基本函數(shù)以及常用函數(shù)。二 需求分析 建立一棵二叉樹(shù)： （1）二叉樹(shù)的鏈表結(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 四 開(kāi)發(fā)工具和編程語(yǔ)言 1.開(kāi)發(fā)工具：Microsoft Visual C+6.02.編程語(yǔ)言：C語(yǔ)言五 概要設(shè)計(jì)1. 數(shù)據(jù)結(jié)構(gòu)typedef char datatype; typedef struct node /定義二叉樹(shù)結(jié)點(diǎn)類型datatype data;struct node *lchild;struct node *rchild;Btnode,* Btree;2.模塊劃分1根據(jù)先序遞歸建立二叉樹(shù) Btree pre_creat() 2遞歸遍歷輸出函數(shù) void preorder_btree(Btree root) /由先根序列遍歷輸出二叉樹(shù)void inorder_btree(Btree root) /由中根序列遍歷輸出二叉樹(shù) void postorder_btree(Btree root) /由后根序列遍歷輸出二叉樹(shù)3層次遍歷輸出算法 void level_btree(Btree root) /層次遍歷輸出二叉樹(shù)六 詳細(xì)設(shè)計(jì)1創(chuàng)建二叉樹(shù)的實(shí)現(xiàn)Btree pre_creat() /使用先根序列建立二叉樹(shù)，返回指針Btree t;char ch;fflush(stdin);scanf("%c",&ch); /輸入一個(gè)結(jié)點(diǎn)數(shù)據(jù)if(ch=)return NULL; /空結(jié)點(diǎn)elset=(Btnode *)malloc(sizeof(Btnode); /申請(qǐng)結(jié)點(diǎn)空間，根節(jié)點(diǎn)t->data=ch;t->lchild=pre_creat(); /生成左子樹(shù)t->rchild=pre_creat(); /生成右子樹(shù)return t;2先序、中序、后序遞歸遍歷輸出算法void preorder_btree(Btree root) /由先根序列輸出二叉樹(shù)Btree p=root;if(p!=NULL) printf("%3c",p->data); /輸出結(jié)點(diǎn)值preorder_btree(p->lchild); /輸出左子樹(shù)preorder_btree(p->rchild); /輸出右子樹(shù) void inorder_btree(Btree root) /由中根序列輸出二叉樹(shù)Btree p=root;if(p!=NULL) inorder_btree(p->lchild); /輸出左子樹(shù) printf("%3c",p->data); /輸出結(jié)點(diǎn)值inorder_btree(p->rchild); /輸出右子樹(shù) void postorder_btree(Btree root) /由后根序序列輸出二叉樹(shù)Btree p=root;if(p!=NULL) postorder_btree(p->lchild); /輸出左子樹(shù)postorder_btree(p->rchild); /輸出右子樹(shù) printf("%3c",p->data); /輸出結(jié)點(diǎn)值 3.層次遍歷輸出算法 void level_btree(Btree root) /層次遍歷輸出二叉樹(shù) Btree p;p=(Btnode *)malloc(sizeof(Btnode); /申請(qǐng)一個(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 +;Qrear=p; /結(jié)點(diǎn)不為空就入隊(duì)if(rear=1)front=1;Qfront=p; /根節(jié)點(diǎn)入隊(duì)作為隊(duì)列頭結(jié)點(diǎn)rear +;while(front!=rear)p=Qfront; /隊(duì)頭結(jié)點(diǎn)出隊(duì)front +;printf("%3c",p->data);if(p->lchild!=NULL)Qrear=p->lchild;rear +;if(p->rchild!=NULL)Qrear=p->rchild;rear +; 這三個(gè)函數(shù)實(shí)現(xiàn)了二叉樹(shù)的遞歸遍歷方法。先序思想是先根、后左孩子、再右孩子，中序遍歷思想是先左孩子、后根、再右孩子，后序是先左孩子、后右孩子、再根。4.主函數(shù)int main()Btree boot;boot=(Btnode *)malloc(sizeof(Btnode);boot=NULL;int x;doprintf("_n"); printf("-歡迎使用！-n");printf("_n"); printf("n*主菜單*n"); printf(" x=1. 先序遍歷建立二叉樹(shù)!n"); printf(" x=2. 先序遍歷輸出二叉樹(shù)!n"); printf(" x=3. 中序遍歷輸出二叉樹(shù)!n"); printf(" x=4. 后序遍歷輸出二叉樹(shù)!n"); printf(" x=5. 層次遍歷輸出二叉樹(shù)!n"); printf(" x=0. 退出n"); printf("*n");dofflush(stdin);printf("請(qǐng)輸入x的值:");scanf("%d",&x);if(x!=1)&&(x!=2)&&(x!=3)&&(x!=4)&&(x!=0)&&(x!=5)printf("請(qǐng)輸入正確的x的值n");while(x!=1)&&(x!=2)&&(x!=3)&&(x!=4)&&(x!=0)&&(x!=5);switch(x)case 1:printf("t先序遍歷建立二叉樹(shù):n"); printf("t請(qǐng)輸入二叉樹(shù)結(jié)點(diǎn)的值!:n"); printf("(可以輸n個(gè)值均為字母或(n<100)字符間以回車符換行,想結(jié)束時(shí)輸多個(gè)):n"); boot=pre_creat(); /順序表的逆置printf("nn");break;case 2: printf("t先序遍歷輸出二叉樹(shù)！:n"); printf("建立的二叉樹(shù)是: "); preorder_btree(boot);printf("nn");break;case 3:printf("t中序遍歷輸出二叉樹(shù)！:n"); printf("建立的二叉樹(shù)是: "); inorder_btree(boot);printf("nn");break; case 4: printf("t后序遍歷輸出二叉樹(shù)！:n"); printf("建立的二叉樹(shù)是: "); postorder_btree(boot);printf("nn");break;case 5: printf("t層次遍歷輸出二叉樹(shù)！:n"); printf("建立的二叉樹(shù)是: "); level_btree(boot);printf("nn");break;while(x!=0);printf("ByeBye!");return x;7. 運(yùn)行結(jié)果： 圖 一 圖 二 圖 三 圖 四 圖 五 圖 六 圖 七設(shè)計(jì)結(jié)果與分析(可以加頁(yè))：本次課程設(shè)計(jì)實(shí)現(xiàn)了二叉鏈表的相關(guān)函數(shù)庫(kù)的調(diào)用。為了實(shí)現(xiàn)以鏈表為存儲(chǔ)結(jié)構(gòu)的二叉樹(shù)的有關(guān)操作，要熟練掌握二叉鏈表的特性，但對(duì)于一些算法較為復(fù)雜，代碼量多些，容易出現(xiàn)一些變量的定義、函數(shù)聲明、函數(shù)調(diào)用等細(xì)節(jié)上的問(wèn)題出錯(cuò)。在本程序的設(shè)計(jì)過(guò)程中，為了克服以上困難，采取了一些措施：建立清晰的程序設(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í)和基礎(chǔ)實(shí)驗(yàn)的基礎(chǔ)上，通過(guò)實(shí)踐設(shè)計(jì)一定量的程序，掌握應(yīng)用計(jì)算機(jī)解決實(shí)際問(wèn)題的基本方法，是理解和運(yùn)用數(shù)據(jù)結(jié)構(gòu)及算法，提高編程能力的有效途徑，并為學(xué)習(xí)軟件專業(yè)課程積累理論基礎(chǔ)和實(shí)踐基礎(chǔ)。程序的設(shè)計(jì)和開(kāi)發(fā)過(guò)程，不僅要求我們牢固地掌握各種基礎(chǔ)知識(shí)，更考查了對(duì)基礎(chǔ)知識(shí)的綜合運(yùn)用能力。這次我的實(shí)驗(yàn)課題是二叉樹(shù)的基本算法綜合分析。算法是數(shù)據(jù)結(jié)構(gòu)的核心，是我們學(xué)習(xí)軟件開(kāi)發(fā)必須掌握的基本知識(shí)。簡(jiǎn)單課程設(shè)計(jì)最重要的是基礎(chǔ)知識(shí)的運(yùn)用，以及綜合分析問(wèn)題的能力。二叉樹(shù)的遞歸算法主要是將二叉樹(shù)存儲(chǔ)到鏈表結(jié)構(gòu)中。遍歷是二叉樹(shù)各種操作的基礎(chǔ)，先序、中序、后序是二叉樹(shù)遍歷的三種基本遍歷方法。而這些都是數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)內(nèi)容，是我們必須理解和牢記的基礎(chǔ)知識(shí)。將這些基礎(chǔ)算法綜合起來(lái)，更能清晰地認(rèn)識(shí)和理解各種算法的作用。當(dāng)然，要學(xué)會(huì)編程不會(huì)僅局限于課本知識(shí)，而是根據(jù)課本知識(shí)進(jìn)行有效的拓展，并且不得不學(xué)會(huì)在眾多的參考資料中搜索有用的自己所需的知識(shí)，并迫使自己去學(xué)習(xí)掌握它們，從中不斷提高自己。例如，課本上只給出了二叉樹(shù)的遞歸中序遍歷方法，由此可容易推出遞歸的前序和中序遍歷方法。二叉樹(shù)的基本操作是多種多樣的，由于時(shí)間的短促和作者水平有限，因不能做太大規(guī)模的設(shè)計(jì)。雖然程序規(guī)模不大，我依然為此付出了努力，仍免不了各種錯(cuò)誤的出現(xiàn)。編程過(guò)程需要很大的毅力和耐心，而且要有良好的思維和扎實(shí)的專業(yè)基礎(chǔ)知識(shí)，所以我需要不斷的學(xué)習(xí)，發(fā)現(xiàn)自身不足之處并改正它，逐步提高自身能力，不斷取得進(jìn)步。對(duì)于數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)，我一直感到很吃力，但想過(guò)放棄。通過(guò)實(shí)踐，讓我們認(rèn)識(shí)到知識(shí)的運(yùn)用性，并加深對(duì)基礎(chǔ)知識(shí)的理解，從中了解自己需要學(xué)習(xí)的東西并學(xué)會(huì)自學(xué)。在此我要感謝我的老師對(duì)我們專心致志的輔導(dǎo)，讓我學(xué)會(huì)了許多分析和解決問(wèn)題的方法，讓我受益匪淺。作為一名計(jì)算機(jī)專業(yè)的學(xué)生，今后我將加倍努力學(xué)習(xí)專業(yè)知識(shí)，為自己從事的職業(yè)打下堅(jiān)實(shí)基礎(chǔ)。設(shè)計(jì)成績(jī)：教師簽名：年月日