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

1、課程設(shè)計(jì)指導(dǎo)書(shū)姓名學(xué)號(hào)班級(jí)課程名稱數(shù)據(jù)結(jié)構(gòu)課程性質(zhì)專(zhuān)業(yè)必修課設(shè)計(jì)時(shí)間201 0 年 12 月 1 日20104 1 2 月 20日設(shè)計(jì)名稱設(shè)計(jì)二叉鏈表結(jié)構(gòu)的相關(guān)函數(shù)庫(kù)設(shè)計(jì)目的使用M i c rosof t 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. 程序需求分郴完成：根扌居需求分析，確定各個(gè)程序功 能的需求；2. 程序總統(tǒng)設(shè)計(jì)完成：根據(jù)程序需求，進(jìn)行程序大概框架的設(shè)計(jì)；3. 主函數(shù)設(shè)計(jì)

2、完成：主函數(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-12o 2復(fù)習(xí)對(duì)vc+6. 0使用，了解關(guān)于二叉鏈表的相關(guān)特征等。12. 3- 1 2. 4查找有關(guān)二叉鏈表基本操作的算法等。1 2.5-12. 7根據(jù)需求分析，確立各個(gè)函數(shù)程序功能。12o 812. 10根據(jù)程序需求，進(jìn)行相關(guān)子函數(shù)程序的編寫(xiě)。12o 1 1 -12. 13進(jìn)行主函數(shù)程序功能的設(shè)計(jì)編寫(xiě).12. 14-12. 16進(jìn)行對(duì)整個(gè)程序的完善.1 2. 17-1 2. 1 8進(jìn)行程序的調(diào)試運(yùn)行。1

3、2. 1 9- 1 2o 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ù)日期:20 10年12 月20日設(shè)計(jì)內(nèi)容：使用Microso f tV i sua I 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 c ore i 3內(nèi)存：1GB硬盤(pán)空間:320GB顯卡：ATI Mobi I i ty Radeon軟件環(huán)

4、境：Windows XP, M icrosof t Visual C+6 0使用數(shù)損結(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)境W i ndow s X P四. 開(kāi)發(fā)工具和編程語(yǔ)言1 開(kāi)發(fā)工具：M i c r o s oft Visual C+6. 02. 編程語(yǔ)言：C

5、語(yǔ)言五. 概要設(shè)計(jì)1. 數(shù)據(jù)結(jié)構(gòu)ty p e d e f char d a t atype;t yped e f stru c t node/定義二叉樹(shù)結(jié)點(diǎn)類(lèi)型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根據(jù)先序遞歸建立二叉樹(shù)Btr e e precreat () 2o遞歸遍歷輸出函數(shù)/由先根序列遍歷/由中根序列遍歷輸/由后根序列遍歷/ /層次遍void preo r d e r_ b t r ee (Bt ree r o ot) 輸出二叉

6、樹(shù)void i n o r derbtree (B t ree root) 出二叉樹(shù)void pos t o rde r _b tree (Bt ree r oot) 輸出二叉樹(shù)3. 層次遍歷輸出算法root)voi d I e v e l_ b t ree (Btree 歷輸出二叉樹(shù)六. 詳細(xì)設(shè)計(jì)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 .創(chuàng)建二叉樹(shù)的實(shí)現(xiàn)/使用先根序列建立二叉樹(shù)

7、，返回指針/輸入一個(gè)結(jié)點(diǎn)數(shù)據(jù)/空結(jié)點(diǎn)9 e Ise0 ° t =(Btn o de *) m a I I oc (si zeof (B tnode) );/申請(qǐng)結(jié)點(diǎn)空間,根節(jié)點(diǎn)° n t data=ch：0 tI c h i I d 二pe_cea t () ;/生成左子樹(shù)trc h i I d 二pe _ c r e a t () ;/生成右子樹(shù)> 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)/由先根序列輸出二叉樹(shù)/輸出結(jié)點(diǎn)值 /輸出左子樹(shù)/輸出右子樹(shù)/由中根序列輸出二叉樹(shù)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 樹(shù)/輸出左子樹(shù) /輸出結(jié)點(diǎn)值/輸出右子樹(shù)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);/輸出左子樹(shù)/輸出右子樹(shù)/輸出結(jié)點(diǎn)值3o層次遍歷輸出算法b Btr e e p=r oot; n if (p!二NULL)voidleve

10、l_b tree (Bt r e e root)輸出二叉樹(shù)B t r e e p;s p二(Btn o de *) mal Io c (s i z eof (B t node); 點(diǎn)n p>data= ' '：p> Ich i I d =p>rchi Id二NULL; 賦初值int fo n t, rear;fro n t =ear=O ;p =root;指向根節(jié)點(diǎn)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 ;列頭結(jié)點(diǎn)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);/層次遍歷/申請(qǐng)一個(gè)新結(jié)/為新結(jié)點(diǎn)/置空隊(duì)列/工作結(jié)點(diǎn)/結(jié)點(diǎn)不為空就入隊(duì)/根節(jié)點(diǎn)入隊(duì)作為隊(duì)/隊(duì)頭結(jié)點(diǎn)出隊(duì)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 +;。 )。這三個(gè)函數(shù)實(shí)現(xiàn)了二叉樹(shù)的遞歸遍歷方法。先序思想是先根、后左孩子.再右孩子，中序遍歷思想是先左孩子.后根、再右孩子，后序是先左孩子、后右孩子、再根.4. 主函數(shù)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 . 先序遍歷建立二叉樹(shù)！n ");printf ("x=2o . o 先序遍歷輸出二叉樹(shù)！n ")：pr i ntf ("x=3. .o 中序遍歷輸出二叉樹(shù)！ n”)；printf (”x=4.o.后序遍歷輸出二叉樹(shù)！n ");printf ("x二5。.。層次遍歷輸出二叉樹(shù)！ n");printf(” x =0o .退出n”)；p r intf (” * 沃 * * *n "):n n do® ® ® f fIu s h (

14、stdin);® ® ® p r i n tf (” 請(qǐng)輸入 x 的值：")：° ds canf (” d " , &x);o 9if ( X != 1 )&& ( X ! =2) && (x!=3) &&( X ! =4) &&(x! =0)&&(x! = 5)d d 0®printf(”請(qǐng)輸入正確的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先序遍歷建立二叉樹(shù)：n “)；printf (” t請(qǐng)輸入二叉樹(shù)結(jié)點(diǎn)的值?。簄”)；pr i ntf (”(可以輸n個(gè)值均為字母或(n < 1 00)字符間以回車(chē)符換行，想結(jié)束時(shí)輸多個(gè)逍')：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、歷輸出二叉樹(shù)!: n"); pr i ntf (“建立的二叉樹(shù)是：”)： 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中序遍歷輸出二叉樹(shù)?。?n”)； print f ("建立的二叉樹(shù)是：")；i n order_ btr e e (boot);6 pr i ntf ("nn");o break;° case 4：pr i ntf (" t后序遍歷輸出二叉樹(shù)！ ：n”)

17、； p r intf ("建立的二叉樹(shù)是：”)；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層次遍歷輸出二叉樹(shù)?。?n"); printf (”建立的二叉樹(shù)是：”);level_btree (boot);6 pr i ntf ("nn ”)；obreak;0 ® wh i I e ( x ! =0);® pr int f ("ByeBye!"

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

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

20、I I 1 "1 "1 "" ' I ' "I ”'W6請(qǐng)輸入X的值山ByeBye?Ppess： any key to continue設(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í)軟件專(zhuān)業(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)的核