數(shù)據(jù)結(jié)構(gòu)課設(shè)

1、課程設(shè)計報告 排序二叉樹 完成日期：2015/01/03 目錄 一、需求分析 1. 運行環(huán)境； 程序所實現(xiàn)的功能；2. 程序的輸入： 3. 程序的輸出： 4.測試數(shù)據(jù)， 5.合作人及其分工 6.二、設(shè)計說明 1. 算法設(shè)計的思想； 主要的數(shù)據(jù)結(jié)構(gòu)設(shè)計說明； 2.程序的主要流程圖；3. 程序的主要模塊，； 4. 程序的主要函數(shù)及其偽代碼說明 . 5.合作人設(shè)計分工。 6. 三、上機結(jié)果及體會 1. 合作人編碼分工； 實際完成的情況說明； 2.程序的性能分析；3. 打印程序運行時的初值和運行結(jié)果，畫出相應(yīng)的圖示； 4.上機過程中出現(xiàn)的問題及其解決方案；5. 程序中可以改進的地方說明； 6. 收獲及

2、體會； 7.源程序清單并附上注釋。 8. 四、參考文獻 需求分析 一、1.運行環(huán)境 a軟件環(huán)境 操作系統(tǒng)：windows 7 編譯器 microsoft visual studio 2010 b硬件環(huán)境 聯(lián)想 n480 2.程序所實現(xiàn)的功能 1. 創(chuàng)建二叉樹： （1） 按提示信息輸入一組關(guān)鍵字值，并建立相應(yīng)的二叉排序樹。 （2） 按照先序遍歷方式顯示建立的二叉排序樹。 （3） 按照中序遍歷方式顯示建立的二叉排序樹。 （4） 按照后序遍歷方式顯示建立的二叉排序樹。 2. 顯示二叉排序樹： （1） 按照先序遍歷方式顯示二叉排序樹。 （2） 按照中序遍歷方式顯示二叉排序樹。 （3） 按照后序遍歷方式

3、顯示二叉排序樹。 （4） 按照層次遍歷方式顯示二叉排序樹。 3. 刪除一個結(jié)點： 要求可以實現(xiàn)刪除根結(jié)點、葉子結(jié)點以及其它任意結(jié)點的功能。 （1） 按照先序、中序、后序方式顯示刪除前的二叉排序樹。 （2） 按提示信息輸入被刪除結(jié)點的值，并在二叉排序樹進行刪除。 （3） 顯示刪除是否成功的結(jié)果。 （4） 若刪除成功，則按照先序、中序、后序方式顯示刪除后的二叉排序樹。 4. 插入一個結(jié)點： （1） 按照先序、中序、后序方式顯示插入前的二叉排序樹。 （2） 按提示信息輸入要插入結(jié)點的值，并在二叉排序樹進行插入。 （3） 顯示插入是否成功的結(jié)果。 （4） 若插入成功，則按照先序、中序、后序方式顯示插入

4、后的二叉排序樹。 5. 查找給定值的結(jié)點： （1） 按照先序、中序、后序方式顯示二叉排序樹。 （2） 按提示信息輸入待查找的值，并在二叉排序樹進行查找。 （3） 顯示查找是否成功的結(jié)果。 6. 交換二叉排序樹： （1） 按照先序、中序、后序方式顯示初始的二叉排序樹。 （2） 按照先序、中序、后序方式顯示交換左右子樹后的二叉排序樹。 7. 退出：退出整個算法演示程序。 3.程序的輸入 ：輸入為整形數(shù)據(jù)，輸入一串?dāng)?shù)字序列并以-1結(jié)束，且以回車鍵相隔。 4.程序的輸出： 通過用戶手動選擇操作指令，經(jīng)由程序內(nèi)部處理，輸出相應(yīng)的結(jié)果到顯示屏。 5.測試數(shù)據(jù)， 用戶手動輸入一個數(shù)字序列進行數(shù)據(jù)測試 設(shè)計說

5、明 二、1算法設(shè)計的思想 根據(jù)算法的需求，確定算法的主要模塊（建立二叉樹、顯示二叉樹，插入結(jié)點、刪除結(jié)點、查找結(jié)點、退出系統(tǒng)。以及主函數(shù)模塊）對各模塊再進行函數(shù)的選取與構(gòu)造，以及變量的控制等。最后，再將各模塊結(jié)合，形成完整的算法，由主函數(shù)來調(diào)用。并設(shè)計界面。程序運行時在界面上顯示及選擇。注意全局變量的選擇。 2主要的數(shù)據(jù)結(jié)構(gòu)設(shè)計說明； 設(shè)計了一個排序二叉樹的數(shù)據(jù)結(jié)構(gòu)，包括查找，刪除等功能。首先使用類模板建立排序二叉樹類，及結(jié)點類存儲結(jié)構(gòu)。因顯示函數(shù)中的層次遍歷需要用到隊列，所以定義了一個鏈?zhǔn)疥犃蓄?，二叉樹函?shù)成員中包括查找，刪除，顯示，插入函數(shù)。下面分別寫出幾個函數(shù)的代碼。主函數(shù)部分包括一個主

6、函數(shù)和一個界面模塊。主函數(shù)調(diào)用部分1.建立二叉樹即循環(huán)調(diào)用插入函數(shù)。并調(diào)用遍歷函數(shù)，2.遍歷顯示，調(diào)用遍歷函數(shù)。3.刪除，首先由查找函數(shù)查找到關(guān)鍵字的地址，再傳遞給刪除函數(shù)，進行刪除。4.插入，插入前，插入后分別調(diào)用遍歷函數(shù)并且調(diào)用插入函數(shù)即可，插入函數(shù)中，調(diào)用了查找函數(shù)。5.查找，調(diào)用查找函數(shù)，并顯示查找結(jié)果，成功或者失敗。6.退出系統(tǒng)，整個主函數(shù)循環(huán)選擇功能序號的條件是number不等于6。7.交換功能 3.程序的主要流程圖； 開始 主函數(shù) 建樹顯示刪除插入查找交換退出先中 先中后序先中后序遍后序 遍歷先中循環(huán)歷交換遍歷結(jié)束后序調(diào)用前 遍歷插入函數(shù)定義層后中先調(diào)用內(nèi)部次序序序查找遍遍遍遍

7、先中歷歷歷歷查找 后序交換是否找到否查找是否查找失敗遍歷成功是否 是否查找找到是 插入失敗是交換結(jié)點到刪除失敗后刪除否插入 先中先中后序遍后序歷遍歷先中后序遍歷 4.程序的主要模塊，要求對主要流程圖中出現(xiàn)的模塊進行說明； a.創(chuàng)建二叉樹： 循環(huán)條件調(diào)用插入函數(shù)。 b.顯示二叉排序樹： 調(diào)用desplayTree函數(shù)，desplayTree函數(shù)調(diào)用先中后序遍歷。調(diào)用層次遍歷函數(shù)。 c.刪除一個結(jié)點： 并在刪除前后顯示遍進行刪除。再傳遞給刪除函數(shù)，首先由查找函數(shù)查找到關(guān)鍵字的地址，歷結(jié)果。 d.插入一個結(jié)點： 插入前，插入后分別調(diào)用遍歷函數(shù)并且調(diào)用插入函數(shù)即可，插入函數(shù)中，調(diào)用了查找函數(shù)。 e.查

8、找給定值的結(jié)點： 查找，調(diào)用查找函數(shù)，并顯示查找結(jié)果，成功或者失敗。 f.交換二叉排序樹： g.退出： 5.程序的主要函數(shù)及其偽代碼說明 a.刪除函數(shù) P定義為葉結(jié)點p-leftChild = NULL&p-rightChild = NULL 如果p的左孩子右孩子均為空delete p;直接刪除p else if (p-leftChild = NULL) tmpPtr=p; p=p-rightChild; delete tmpPtr; 如果被刪除的元素只有右子樹，沒有左子樹，則可以拿他的左孩子頂替他的位置，再釋放該元素的存儲空間即可；只有左子樹沒有右子樹同理。 tmpF=p; tmpPtr=p

9、-leftChild; while (tmPtr-rightChild != NULL) /查找p在中序序列中直接前驅(qū)tmpPtr及其雙親tmpF tmpF=tmpPtr; tmpPtr=tmpPtr-rightChild; p-data=tmpPtr-data; /將tmpPtr指向結(jié)點的數(shù)據(jù)元素值賦值給被刪除的結(jié)點 if (tmpF-rightChild = tmpPtr) /刪除tmpPtr的結(jié)點 Delete(tmpF-rightChild); else Delete(tmpF-rightChild); else Delete(tmpF-leftChild); 如果被刪除的元素左右孩子

10、都存在的話，則在他的左子樹中尋找關(guān)鍵字值最大的數(shù)據(jù)元素x,用x的值代替被刪除元素的值，再來刪除數(shù)據(jù)元素的值x。 b.交換函數(shù) (head-leftChild=NULL&head-rightChild=NULL)如果左右孩子均為空，則不需要交換。 temp=head-leftChild; head-leftChild=head-rightChild; head-rightChild=temp; 如果不為空，則定義中間變量，進行左右交換。 if(head-leftChild) ExchangeTree(head-leftChild); 如果被交換的結(jié)點存在樹的左子樹上則遞歸遞歸調(diào)用交換函數(shù)。存在于

11、右子樹上同理。c.查找函數(shù) BinTreeNode *p=r;指向當(dāng)前結(jié)點f=NULL;指向p的雙親。從根節(jié)點開始將根節(jié)點的關(guān)鍵字與給定值比較如果相同則成功。 if (key data) f=p; p=p-leftChild; else f=p; p=p-rightChild; f=NULL; 如果給定值小于根節(jié)點的關(guān)鍵字，則在根節(jié)點的左子樹上遞歸查找。大于則在右子樹上遞歸查找。 d.插入函數(shù) （FindTree(e, f) = NULL) 首先查找給定值是否在書中已存在。 if (f=NULL) r=p; 如果為空樹，則新節(jié)點為根節(jié)點。 else if (edata) f-leftChild

12、=p; else f-rightChild=p; 如果小于雙親，則插入結(jié)點為左孩子。大于雙親，則插入結(jié)點為右孩子。 return true; else return false; 如果查找成功，則插入失敗。 e.先中后以及層次遍歷函數(shù) void BinarySortTree:desplayTree() 由該函樹調(diào)用先中后序遍歷，以先序遍歷為例。 if(r !=NULL) coutdataleftChild); PreOrder (r-rightChild); 如果以r為跟的二叉樹為空，則遍歷結(jié)束，如不為空，首先訪問根節(jié)點再先序遍歷他的左子樹。然后再先序遍歷它的右子樹。中序，首先中序遍歷他的左子

13、樹，再訪問他的根節(jié)點，最后中序遍歷它的右子樹。后序首先后序遍歷他的左子樹，再后序遍歷它的右子樹，最后訪問根節(jié)點。 層次遍歷 LinkQueueBinTreeNode * q; BinTreeNode *w; (r!=NULL) q.EnQueue (r); if while (!q.IsEmpty() q.DelQueue(w); coutdataleftChild != NULL) q.EnQueue(w-leftChild); if (w-rightChild != NULL) q.EnQueue(w-rightChild); 1.首先初始化隊列，并將根節(jié)點入隊。2.當(dāng)隊列非空時，取出隊頭

14、結(jié)點轉(zhuǎn)3否則結(jié)束遍歷。3.訪問結(jié)點p如果該節(jié)點有左孩子則將其左孩子入隊；如果 該節(jié)點有右孩子，則將其右孩子入隊。4.重復(fù)步驟2 3 直到隊列為空為止。 6.合作人設(shè)計分工 經(jīng)由郭凱迪同學(xué)指錯改錯。 三、上機結(jié)果及體會 1.實際完成的情況說明 所要求的功能均能實現(xiàn)，數(shù)據(jù)類型為整形數(shù)據(jù) 2.程序的性能分析，包括時空分析 函數(shù) 時間復(fù)雜度 空間復(fù)雜度 O(1) O(log2n)-O(n+1)/2) 查找O(1) 插入 O(log2n) O(1) O(1) 刪除 O(n) O(n) 先中后遍歷O(n) O(n) 層次遍歷O(1) O(1) 交換 3.打印程序運行時的初值和運行結(jié)果 初始界面A. B.建

15、樹 顯示C. D.刪除 E.查找 F.交換 退出G. H.插入 4.上機過程中出現(xiàn)的問題及其解決方案 出現(xiàn)許多語法問題例如定義函數(shù)與聲明不匹配，函數(shù)名稱是否正確，if else的匹配問題，通過一步一步的修改最終實現(xiàn)程序。界面部分修改的更合理。創(chuàng)建函數(shù)部分，循環(huán)調(diào)用插入查找返回的刪除函數(shù)部分首先需要查找關(guān)鍵字結(jié)點，函數(shù)時輸入是在調(diào)用前還是在調(diào)用后。為地址，所以中間傳遞變量應(yīng)為指針，以及參數(shù)數(shù)量應(yīng)相等。 5.程序中可以改進的地方說明 界面可以進行進一步優(yōu)化。 6.收獲及體會 a.進行程序設(shè)計的時候注意模塊的劃分，從各個小 模塊開始進行設(shè)計 b.熟練掌握各函數(shù)的成員構(gòu)成 c.交流與合作 7.打印一份

16、源程序清單并附上注釋。 #include #include #include #include template struct Node ElemType data; Node *next; Node(ElemType &e) data=e; next=NULL; ; Node() next=NULL; ; ElemType templateclass LinkQueue class : public Node *front, *rear; LinkQueue(); LinkQueue(); virtual IsEmpty(); bool DelQueue(ElemType &e); void

17、 ElemType e); void EnQueue(const ; template bool LinkQueue:IsEmpty() if(front=rear) return true; else ; false return ElemType class template LinkQueue:LinkQueue() Node; new rear=front= ElemType template class LinkQueue:LinkQueue() ElemType class template LinkQueue:EnQueue( ElemType e) void Node *p;

18、Node(e); p=new (p) if rear-next=p; rear=rear-next; ElemType templateclass LinkQueue:DelQueue(ElemType &e) void (!IsEmpty() if Node *p=front-next; e=p-data; front-next=p-next; (rear = p) if rear=front; p; delete ElemType template class struct 聲明樹結(jié)構(gòu) BinTreeNode/ ElemType data; BinTreeNode *leftChild;/

19、存放左子樹的指針 BinTreeNode *rightChild; BinTreeNode(); BinTreeNode( ElemType &e); ; template BinTreeNode: BinTreeNode(ElemType &e) data=e; leftChild=NULL; rightChild=NULL; ElemType template class BinTreeNode: BinTreeNode() leftChild=NULL; rightChild=NULL; ElemType classtemplate BinarySortTree class : publ

20、icBinTreeNode *r; BinarySortTree(); /顯示這個數(shù)); void desplayTree(void /在樹中插入一個節(jié)點 bool insertTree( ElemType &e); BinarySortTree(); virtualBinTreeNode *head; PreOrder(BinTreeNode *r); void InOrder(BinTreeNode *r); void PostOrder(BinTreeNode *r); void LevelOrderTree(); void BinTreeNode* buildTree(BinTreeN

21、ode* head,int number); /建立一個樹 DeleteTree(BinTreeNode * &p, BinTreeNode * &fq); bool ExchangeTree(BinTreeNode *head); void; const&key,BinTreeNode *FindTree( BinTreeNode ElemType *&f) destroyTree(BinTreeNode * &r); void ; template BinarySortTree:BinarySortTree() r=NULL; ElemType classtemplate 節(jié)點new/調(diào)用

22、析構(gòu)函數(shù)，運用遞歸刪除所有的BinarySortTree:BinarySortTree() endl; 樹骸?一?棵已?經(jīng)-消?除y了 cout destroyTree(r); template bool BinarySortTree:DeleteTree(BinTreeNode * &p, BinTreeNode * &fq) BinTreeNode *tmpPtr, *tmpF; if (p-leftChild=NULL&p-rightChild=NULL&fq!=NULL) / 葉子結(jié)點? delete p; if (fq != NULL) if (fq-leftChild = p) f

23、q-leftChild = NULL; else fq-rightChild = NULL; p = NULL; / (p-leftChild = NULL) 有右子樹結(jié)點 else if (fq=NULL) if r=p-rightChild; (fq-leftChild = p) else if fq-leftChild = p-rightChild; fq-rightChild = p-rightChild; else p; delete p = NULL; 有左子樹結(jié)點/ (p-rightChild = NULL) elseif (fq=NULL) if r=p-leftChild;

24、(fq-leftChild = p) if fq-leftChild = p-leftChild; else fq-rightChild = p-leftChild; delete p; p = NULL; else /左右子樹都有 tmpF = p; tmpPtr = p-leftChild; while (tmpPtr-rightChild != NULL) /找左子樹的右子樹最后一個結(jié) 點循環(huán)結(jié)束tmpPtr指向目標(biāo)結(jié)點，tmpF指向目標(biāo)結(jié)點的父母. tmpF = tmpPtr; tmpPtr = tmpPtr-rightChild; p-data = tmpPtr-data; (tmp

25、F-rightChild = tmpPtr) if DeleteTree(tmpF-rightChild, tmpF); elseDeleteTree(tmpF-leftChild, tmpF); ; true return template void BinarySortTree:ExchangeTree(BinTreeNode *head) BinTreeNode* temp=NULL; if(head-leftChild=NULL&head-rightChild=NULL) return; else temp=head-leftChild; head-leftChild=head-rig

26、htChild; head-rightChild=temp; (head-leftChild) ifExchangeTree(head-leftChild); (head-rightChild) if ExchangeTree(head-rightChild); ElemType templateclassBinTreeNode *BinarySortTree:FindTree( ElemType &key,BinTreeNode *&f) const BinTreeNode *p=r;/指向當(dāng)前節(jié)點 f=NULL;/ 指向p的雙親 while (p != NULL & p-data != k

27、ey) /查找關(guān)鍵字為key的節(jié)點 if (key data) /key比 p的值小，則在p的左子樹上進行查找 f=p; p=p-leftChild; else 的右子樹上進行查找 比 p的值大，則在p/key f=p; p=p-rightChild; p; return template bool BinarySortTree:insertTree(ElemType &e) /f=NULL;/ 指向被查找節(jié)點的雙親 BinTreeNode *f; BinTreeNode *p; if (FindTree(e, f) = NULL) / 查找失敗，插入成功。 p= new BinTreeNod

28、e (e); if (f=NULL) /空二叉樹，新節(jié)點為根節(jié)點 r=p; else if (edata)/e小于其雙親，插入結(jié)點為f的左孩子 f-leftChild=p; else /e 大于其雙親，插入結(jié)點為 f 的右孩子 f-rightChild=p; return true ; else; return false template void BinarySortTree:desplayTree() cout前序 ?; PreOrder(r); coutendl; ; ?中序cout InOrder(r); coutendl; ; 后序 ?coutPostOrder(r); cout

29、classtemplate BinarySortTree:PreOrder(BinTreeNode *r) void (r !=NULL) if coutdatarightChild);/r再先序遍歷PreOrder (r-leftChild);/再先序遍歷r的左子樹 右子樹 ElemType templateclass BinarySortTree:InOrder(BinTreeNode *r) void (r !=NULL) if r的左子樹/ InOrder (r-leftChild); 首先中序遍歷 /coutdatarightChild); ElemType classtemplat

30、e BinarySortTree:PostOrder(BinTreeNode *r) void (r !=NULL) if 的左子樹r / PostOrder (r-leftChild);首先后序遍歷 r/再后序遍歷的右子樹 PostOrder (r-rightChild); r 再訪問根節(jié)點 ;/coutdata classtemplate BinarySortTree:LevelOrderTree() void q 定義隊列/LinkQueueBinTreeNode * q;BinTreeNode *w; (r!=NULL) q.EnQueue (r); if (!q.IsEmpty()

31、while q.DelQueue(w); ; coutdataleftChild != NULL) if q.EnQueue(w-leftChild); if (w-rightChild != NULL) q.EnQueue(w-rightChild); template void BinarySortTree:destroyTree(BinTreeNode * &r) if(r!=NULL) destroyTree(r-leftChild ); destroyTree(r-rightChild ); r; delete #include #include瑜敲?屨 using namespac

32、e std; void menu() coutendl; cout* 以下是對二叉排序樹的基本操作* endl; | | 0.創(chuàng)建二叉樹 ?撓畯?尼endl; cout| 1.顯示二叉樹 | endl; cout| 2.刪除一個節(jié)點 | endl; | | 3. cout插入一個節(jié)點endl; | 查找一個節(jié)點 cout| 4.endl; | 交換二叉樹| 5. coutendl; | | 6. cout退出 endl; * cout tree; BinarySortTree *p=NULL; intBinTreeNode BinTreeNode *q; int number; int choiceNumber=8; while(choiceNumber!=6) menu () ; en