數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-苑聰聰

《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-苑聰聰》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、河北工程大學(xué)科信學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告（2010/2011學(xué)年第?二?學(xué)期）題????目：線索二叉樹(shù)的應(yīng)用專(zhuān)業(yè)班級(jí)：09計(jì)算機(jī)（2）班學(xué)生姓名：苑聰聰學(xué)????號(hào)：090212236指導(dǎo)教師：??陳麗、楊榮愛(ài)設(shè)計(jì)周數(shù)：????19、20周設(shè)計(jì)成績(jī)：2011???年?7月?4日一、需求分析：1、題目：線索二叉樹(shù)的應(yīng)用2、目的和任務(wù)：《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)是計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)集中實(shí)踐性環(huán)節(jié)之一，是學(xué)習(xí)完《數(shù)據(jù)結(jié)構(gòu)》課程后進(jìn)行的一次全面的綜合練習(xí)。其目的就是要達(dá)到理論與實(shí)際應(yīng)用相結(jié)合，使學(xué)生能夠根據(jù)數(shù)據(jù)對(duì)

2、象的特性，學(xué)會(huì)數(shù)據(jù)組織的方法，能把現(xiàn)實(shí)世界中的實(shí)際問(wèn)題在計(jì)算機(jī)內(nèi)部表示出來(lái)，并培養(yǎng)良好的程序設(shè)計(jì)技能。其任務(wù)為：要求：實(shí)現(xiàn)線索樹(shù)建立、插入、刪除、恢復(fù)線索的實(shí)現(xiàn)。3、數(shù)據(jù)輸入輸出：原始數(shù)據(jù)要求輸入二叉樹(shù)的7個(gè)結(jié)點(diǎn)：1234567，輸出的是一個(gè)二叉樹(shù)，這就實(shí)現(xiàn)了二叉樹(shù)的建立過(guò)程。然后對(duì)二叉樹(shù)進(jìn)行線索化。對(duì)其進(jìn)行插入：在7結(jié)點(diǎn)處插入結(jié)點(diǎn)8；刪除：刪除結(jié)點(diǎn)8;恢復(fù)線索等功能。進(jìn)行二叉樹(shù)的初始化，依次輸入，以*結(jié)束：1234567*線索二叉樹(shù)的應(yīng)用****************************1、進(jìn)

3、行二叉樹(shù)線索化2、進(jìn)行插入操作3、刪除4、中序輸出5、線索輸出0、退出請(qǐng)選擇：1已經(jīng)實(shí)現(xiàn)二叉樹(shù)的線索化，可選擇5查看線索4、設(shè)計(jì)算法測(cè)試用例：（1）輸入結(jié)點(diǎn):1234567;(2)對(duì)輸入的二叉樹(shù)進(jìn)行線索化；（3）查看二叉樹(shù)的中序線索輸出：4->2->5->1->6->3->7；（4）在7結(jié)點(diǎn)處插入結(jié)點(diǎn)8，此時(shí)完成線索化恢復(fù)，查看二叉樹(shù)的中序線索輸出：4->2->5->1->6->3->8->7;(5)刪除結(jié)點(diǎn)8，此時(shí)完成線索化恢復(fù)，發(fā)現(xiàn)結(jié)點(diǎn)8，ltag=1,rtag=1,查看二叉樹(shù)的中序線索輸出：4-

4、>2->5->1->6->3->7;(6)繼續(xù)刪除結(jié)點(diǎn)r，發(fā)現(xiàn)無(wú)該結(jié)點(diǎn)，則輸入錯(cuò)誤。二、數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計(jì)1、數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)是由n（n>=0）個(gè)結(jié)點(diǎn)組成的有限集合，其中：（1）當(dāng)n＝0時(shí)，為空二叉樹(shù)。（2）當(dāng)n>0時(shí)，有且僅有一個(gè)特定的結(jié)點(diǎn)，稱(chēng)為二叉樹(shù)的根，不相交的子集，其中每一個(gè)子集本身又是一棵二叉樹(shù)，分別稱(chēng)為左子樹(shù)和右子樹(shù)。線索化是將二叉樹(shù)轉(zhuǎn)換成線索二叉樹(shù)的過(guò)程。按某種遍歷將二叉樹(shù)線索化，只需在遍歷過(guò)程中將二叉樹(shù)中每個(gè)結(jié)點(diǎn)的空的左右孩子指針域分別修改為指向其前驅(qū)和后繼結(jié)點(diǎn)。（1）線索二叉樹(shù)的

5、結(jié)點(diǎn)的結(jié)構(gòu)如下：ltaglchilddatartagrchild約定：Ltag=0//表示lchild域指示該結(jié)點(diǎn)的左孩子Ltag=1//表示lchild域指示該結(jié)點(diǎn)的前驅(qū)Rtag=0//表示rchild域指示該結(jié)點(diǎn)的右孩子Rtag=1//表示rchild域指示該結(jié)點(diǎn)的后繼(2)線索鏈表中結(jié)點(diǎn)類(lèi)型說(shuō)明：Typedefchardatatype;Typedefstructnode{Intltag,rtag;Datatypedata;Structnode*lchild,*rchild;}bithptr;(3

6、)線索化算法：結(jié)點(diǎn)*pre是結(jié)點(diǎn)*p的前驅(qū)，而*p是*pre的后繼。這樣，當(dāng)遍歷到結(jié)點(diǎn)*p時(shí)，可以進(jìn)行以下三步操作：1）若*p有空指針域，則將相應(yīng)的標(biāo)志置1.2）若*p的左線索標(biāo)志已經(jīng)建立（p->ltag=1）,則可使其前驅(qū)線索化，令p->lchild=pre.3)若*pre的右線索標(biāo)志已經(jīng)建立（pre->rtag=1）,則可使其后繼線索化，令pre->rchild=p.如此，二叉樹(shù)的線索化可以在二叉樹(shù)的遍歷過(guò)程完成，該算法應(yīng)為相應(yīng)順序的遍歷算法的一種變化形式。（4）二叉鏈表的建立：其算法描述如下：B

7、itree*crt_bt_pre(bitree*bt){Charch;Ch=getchar();If(ch==‘?！?Bt=null;Else{Bt=(bitree*)malloc(sizeof(bitree));Bt->data=c;Bt->lchild=crt_bt_pre(bt->lchild);Bt->rchild=crt_bt_pre(bt->rchild);}Return(bt);}2、設(shè)計(jì)思想建立二叉樹(shù)（即指在內(nèi)存中建立二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)），建立一個(gè)二叉鏈表，需按某種順序一次輸入二叉樹(shù)中的

8、結(jié)點(diǎn)，且輸入順序必須隱含結(jié)點(diǎn)間的邏輯結(jié)構(gòu)信息。對(duì)于一般的二叉樹(shù)，需添加虛結(jié)點(diǎn)，使其成為完全二叉樹(shù)。關(guān)鍵在于如何將新結(jié)點(diǎn)作為左孩子和右孩子連接到它的父結(jié)點(diǎn)上?？梢栽O(shè)置一個(gè)隊(duì)列，該隊(duì)列是一個(gè)指針類(lèi)型的數(shù)組，保存已輸入的結(jié)點(diǎn)地址。操作：（1）令隊(duì)頭指針front指向其孩子結(jié)點(diǎn)當(dāng)前輸入的建立鏈接的父結(jié)點(diǎn)，隊(duì)尾指針rear指向當(dāng)前輸入的結(jié)點(diǎn)，初始：front=1,rear=0;（2）若rear為偶數(shù)，則該結(jié)點(diǎn)為父結(jié)點(diǎn)的左孩子；若rear為奇數(shù)，則該結(jié)點(diǎn)的右孩子；若