1、課程設計指導書姓名學號班級課程名稱數據結構課程性質專業必修課設計時間201 0 年 12 月 1 日20104 1 2 月 20日設計名稱設計二叉鏈表結構的相關函數庫設計目的使用M i c rosof t Visual C+設計二叉鏈表結構的相關函數 庫，并能夠在程序設計中調用設計要求設計二叉鏈表結構的相關函數庫，以便在程序設計中調用，實現二 叉樹的各種基本函數以及常用函數；并給出1-2個例子，通過調用 自己的庫函數來實現問題的求解。設計思路與設計過程1. 程序需求分郴完成：根扌居需求分析，確定各個程序功 能的需求；2. 程序總統設計完成：根據程序需求，進行程序大概框架的設計；3. 主函數設計

2、完成：主函數程序中設計一個菜單，并調 試所用算法；4. 其他函數設計完成：建立二叉鏈表以及遞歸序列遍歷算法5. 系統程序完即完成：完善整個程序細節代碼的要求， 進行調試。計劃與進度12. 1-12o 2復習對vc+6. 0使用，了解關于二叉鏈表的相關特征等。12. 3- 1 2. 4查找有關二叉鏈表基本操作的算法等。1 2.5-12. 7根據需求分析，確立各個函數程序功能。12o 812. 10根據程序需求，進行相關子函數程序的編寫。12o 1 1 -12. 13進行主函數程序功能的設計編寫.12. 14-12. 16進行對整個程序的完善.1 2. 17-1 2. 1 8進行程序的調試運行。1

3、2. 1 9- 1 2o 20資料歸檔，填寫相關文檔。任課教師意見備 汪課程設計報告課程：學號：姓名：班級：教師時間：計算機科學與技術系設計名稱：設計二叉鏈表的相關函數庫日期:20 10年12 月20日設計內容：使用Microso f tV i sua I C+設計二叉鏈表結構的相關函數庫, 以便在程序設計中調用設計目的與要求：設計二叉鏈表結構的相關函數庫，在程序設計中調用，并實現二 叉樹的各種基本函數以及常用函數。設計環境或器材、原理與說明：器材：計算機一臺峻件環境：處理器：Intel c ore i 3內存：1GB硬盤空間:320GB顯卡：ATI Mobi I i ty Radeon軟件環

4、境：Windows XP, M icrosof t Visual C+6 0使用數損結構設計的一般方法步驟進行設計。設計過程(步驟)和部分程序代碼(可以加頁): 題目要求設計二叉鏈表結構的相關函數庫，在程序設計中調用，并實現二叉樹的各種 基本函數以及常用函數。二. 需求分析建立一棵二叉樹：(1) 二叉樹的鏈表結構；(2) 進行先序遍歷，輸出結果;(3) 進行中序遍歷，輸出結果；(4) 進行后序遍歷，輸出結果;(5) 進行層次遍歷，輸出結呆。三. 運行環境W i ndow s X P四. 開發工具和編程語言1 開發工具：M i c r o s oft Visual C+6. 02. 編程語言：C

5、語言五. 概要設計1. 數據結構ty p e d e f char d a t atype;t yped e f stru c t node/定義二叉樹結點類型datatype data;0 st ru c t node * I chi I d;struet n ode rc h iId; B t n o de, * B t r e e;2. 模塊劃分1 o根據先序遞歸建立二叉樹Btr e e precreat () 2o遞歸遍歷輸出函數/由先根序列遍歷/由中根序列遍歷輸/由后根序列遍歷/ /層次遍void preo r d e r_ b t r ee (Bt ree r o ot) 輸出二叉

6、樹void i n o r derbtree (B t ree root) 出二叉樹void pos t o rde r _b tree (Bt ree r oot) 輸出二叉樹3. 層次遍歷輸出算法root)voi d I e v e l_ b t ree (Btree 歷輸出二叉樹六. 詳細設計Btree pre一 creat ()B t ree t;ch a r c h：f f Iush (stdin);® sea nf (” %c", &ch)： if(ch 二='')d return NULL;1 .創建二叉樹的實現/使用先根序列建立二叉樹

7、，返回指針/輸入一個結點數據/空結點9 e Ise0 ° t =(Btn o de *) m a I I oc (si zeof (B tnode) );/申請結點空間,根節點° n t data=ch：0 tI c h i I d 二pe_cea t () ;/生成左子樹trc h i I d 二pe _ c r e a t () ;/生成右子樹> re t u r n t;2o先序.中序、后序遞歸遍歷輸出算法 void preorde r _btree (Bt ree root)Btee p=r o ot; n if ( p ! =N ULL)p r i ntf(

8、” % 3cM, p>da t a ):0 d p r eor d er_btr e e ( p > Ic h i I d): o p r eorder btree(p>r c hi I d):0 ) "vo i d i n o r d er_ btree (Bt r ee root)/由先根序列輸出二叉樹/輸出結點值 /輸出左子樹/輸出右子樹/由中根序列輸出二叉樹ino r der_bt r ee (p>Ic h i I d )pr i nt f ("%3 c ",p->data);n 3 i norderbt re e (p) r

9、chi Id); _void po s to r d er_ bt r e e (Btee 樹/輸出左子樹 /輸出結點值/輸出右子樹r o ot)由后根序序列輸出二叉0 Bt ree p = root; o i f(p !二NULL)p o sto r der_bt r ee (p> I c hi Id); p os tor der bte e (p>rc h i I d );pr i ntf (” %3 c n , p一> d ata);/輸出左子樹/輸出右子樹/輸出結點值3o層次遍歷輸出算法b Btr e e p=r oot; n if (p!二NULL)voidleve

10、l_b tree (Bt r e e root)輸出二叉樹B t r e e p;s p二(Btn o de *) mal Io c (s i z eof (B t node); 點n p>data= ' '：p> Ich i I d =p>rchi Id二NULL; 賦初值int fo n t, rear;fro n t =ear=O ;p =root;指向根節點s i f (p !二NULL)3rear +;0Q rea r = p ;o i f (rear=1)a d a front=d :0 Q f rorrt = p ;列頭結點n n 9 r ear

11、 +;0 while (fro nt!二 rear)0 3 o P二Q f ront;0fro nt +;0 0 pr intf ( H %3c” , pdata);/層次遍歷/申請一個新結/為新結點/置空隊列/工作結點/結點不為空就入隊/根節點入隊作為隊/隊頭結點出隊o。if(p->lchi I d !=NULL) an b Q r e a r = p -> Ichi I d ;6 ° 0 r e ar +;o o ® ® i f ( p->r c h i ld!=NULL)d o3 Q o Qrear = p >rchi I d;

12、76; ° ° r e ar +;。 )。這三個函數實現了二叉樹的遞歸遍歷方法。先序思想是先根、后左孩子.再右孩子，中序遍歷思想是先左孩子.后根、再右孩子，后序是先左孩子、后右孩子、再根.4. 主函數int mai n 0n Bt r e e bo o t ：boot= (Bt n ode*) ma I I o c (siz e of (Btnod e );n boot二NULL：> i nt x ;d d oa pr i nt f L n v)：pr i nt f (”歡迎使用！n");p r i n t f ( ” n ");pr i n tf

13、 (”n* * 夫主菜單* * *printf(”x= 1 . 先序遍歷建立二叉樹！n ");printf ("x=2o . o 先序遍歷輸出二叉樹！n ")：pr i ntf ("x=3. .o 中序遍歷輸出二叉樹！ n”)；printf (”x=4.o.后序遍歷輸出二叉樹！n ");printf ("x二5。.。層次遍歷輸出二叉樹！ n");printf(” x =0o .退出n”)；p r intf (” * 沃 * * *n "):n n do® ® ® f fIu s h (

14、stdin);® ® ® p r i n tf (” 請輸入 x 的值：")：° ds canf (” d " , &x);o 9if ( X != 1 )&& ( X ! =2) && (x!=3) &&( X ! =4) &&(x! =0)&&(x! = 5)d d 0®printf(”請輸入正確的x的值 n ");o wh i le( (x!二 1) & &( x ! = 2) & & (x

15、! =3) &&(x ! =4) && (x!=0) && (x!=5):° switch(x)0 d 0 0 c ase 1:0printf (”t先序遍歷建立二叉樹：n “)；printf (” t請輸入二叉樹結點的值?。簄”)；pr i ntf (”(可以輸n個值均為字母或(n < 1 00)字符間以回車符換行，想結束時輸多個逍')：n”)；b oot=p r eere at() ;/順序表的逆置p r i n tf (" n n”)；b r ea k ;00 case 2:p r intf (” t先序遍

16、歷輸出二叉樹!: n"); pr i ntf (“建立的二叉樹是：”)： preord e r _ b t r ee ( b o ot);p r i ntf (” n n ”)；®° b r eak;c ase 3:o o o p r i ntf (” t中序遍歷輸出二叉樹！： n”)； print f ("建立的二叉樹是：")；i n order_ btr e e (boot);6 pr i ntf ("nn");o break;° case 4：pr i ntf (" t后序遍歷輸出二叉樹！ ：n”)

17、； p r intf ("建立的二叉樹是：”)；po s t o rder_bt r e e (boot): pr intf ("n n ”)；® ® » b r eak;° c a s e 5:p r i ntf("t層次遍歷輸出二叉樹?。?n"); printf (”建立的二叉樹是：”);level_btree (boot);6 pr i ntf ("nn ”)；obreak;0 ® wh i I e ( x ! =0);® pr int f ("ByeBye!"

18、;);return x ;七. 運行結果：歡迎使用！二二二二二 葉立出岀出出 時歷歷歷歷歷 "序序序序次出 袖先先中后曇12 3 4 5 0 = X X X X X X請輸入K的值:歡迎使用!二八X二二 一反靈叉叉叉 一三二一三二 聖i出岀 由歷BraB胯 、£遍遍遍遍遍 卄序序序艮出 W先先中后層退23.4.5.0. =X X X X X X請輸入X卸值:1. 五_廠丄蠶翹飜結翻祐:可以輸樣適均為字母或回“諭字符間以回車符換行恿結束時輸多個,“ > :abdgpeo衛 f hGyP歡迎使用!軒、寫菜一柱遍鶏遍遍初序序e序吹出初先先中后最歷 21是 驚 XR- 入的

19、輸立 請建歡迎使用！一文叉叉叉叉 - 亜亠V出出出出 ¥11 捋歷歷歷歷歷 18® i序序序長出 7先先屯后展很12 3 4 5 0 =一一=一一= X X X X X X:輸丫龍晉歷輸岀二叉樹!: 建立的二叉樹是二 d g b歡迎使用！叉叉叉叉叉 - 亜寺出出出出 蒲建gllffl楓 由歷歷歷歷歷 -3遍遍遍遍遍 序序序寥岀 Z先先屯后層退12 3 4 5 0 _一 = 一一 = X X X X X X讐 胡- 入的 輸-V 請建歡迎使用卄叉叉xxx T二二二二 嚴V出出岀岀 匸建Haa榊 總歷歷歷歷歷請建xh -a lz z歡迎使用！舟立出出出出 Eg歷BB5一 JB

20、I I 1 "1 "1 "" ' I ' "I ”'W6請輸入X的值山ByeBye?Ppess： any key to continue設計體會與建議：數據結構是計算機程序設計的重要理論技術基礎，在理論學 習和基礎實驗的基礎上，通過實踐設計一定量的程序，掌握應用計算機解決實際 問題的基本方法，是理解和運用數據結構及算法，提高編程能力的有效途徑，并 為學習軟件專業課程積累理論基礎和實踐基礎。程序的設計和開發過程，不僅要 求我們牢固地掌握各種基礎知識，更考查了對基礎知識的綜合運用能力。這次我 的實驗課題是二叉樹的基本算法綜合分析。算法是數據結構的核