1、長沙學(xué)院課程設(shè)計說明書題目利用二叉排序樹對順序表進行排序系（部）專業(yè)（班級）姓名學(xué)號指導(dǎo)教師起止日期2015.12.82015.12.15課程設(shè)計任務(wù)書課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計設(shè)計題目：為了充分調(diào)動學(xué)生的學(xué)習(xí)積極性與主動性，適應(yīng)不同興趣、不同程度的學(xué)生對課程設(shè)計的要求，本課程設(shè)計提供四個任選題。每個學(xué)生可以根據(jù)本人的興趣及能力選擇教師指定的選題，也可以自定其他的選題。1、一元多項式計算問題2、迷宮問題3、利用二叉排序樹對順序表進行排序4、交通咨詢系統(tǒng)5、內(nèi)部排序算法的比較已知技術(shù)參數(shù)和設(shè)計要求：需求說明及要求題目三：利用二叉排序樹對順序表進行排序問題描述：利用二叉排序樹對順序表進行排序

2、?；疽螅?1)生成一個順序表L;(2)對所生成的順序表L構(gòu)造二叉排序樹；(3)利用棧結(jié)構(gòu)實現(xiàn)中序遍歷二叉排序樹；(4)中序遍歷所構(gòu)造的二叉排序樹將記錄由小到大輸出。測試數(shù)據(jù)：用偽隨機數(shù)產(chǎn)生程序產(chǎn)生，表長不小于20。選作內(nèi)容：用實現(xiàn)二叉排序樹的插入和刪除操作。各階段具體要求：1、需求分析階段熟悉系統(tǒng)業(yè)務(wù)，從業(yè)務(wù)中抽取出系統(tǒng)的需求，形成完善的需求說明書。2、系統(tǒng)設(shè)計階段根據(jù)需求，進行程序設(shè)計，包括定義系統(tǒng)的界面、定義系統(tǒng)數(shù)據(jù)的存儲方式等，形成完善的設(shè)計說明書。3、編碼實現(xiàn)階段(1)完成代碼編寫(2)要求代碼編寫規(guī)范4、系統(tǒng)測試階段(1)完成功能調(diào)試(2)要求完成必要的測試工作5、交付實施階段(

3、1)提交可正常執(zhí)行的系統(tǒng)(2)提交系統(tǒng)需求說明書、設(shè)計說明書、程序代碼(3)撰寫課程設(shè)計報告書(4)要求規(guī)范地書寫文檔設(shè)計工作量：(1)軟件設(shè)計：完成問題陳述中所提到的所有需求功能。(2)論文：要求撰寫不少于3000字的文檔，詳細說明各階段具體要求。工作計劃：數(shù)據(jù)結(jié)構(gòu)課程設(shè)方t總學(xué)時數(shù)為2周，其進度及時間大致分配如下：序號設(shè)計內(nèi)容天數(shù)1 分析問題，給出數(shù)學(xué)模型，選擇數(shù)據(jù)結(jié)構(gòu)12 設(shè)計算法，給出算法描述23 給出源程序清單14 編輯、編譯、調(diào)試源程序55 編寫課程設(shè)計報告1總計10注意事項提交文檔?長沙學(xué)院課程設(shè)計任務(wù)書(每學(xué)生1份)?長沙學(xué)院課程設(shè)計鑒定表(每學(xué)生1份)?長沙學(xué)院課程設(shè)計說明書

4、(每學(xué)生1份)指導(dǎo)教師簽名：日期：教研室主任簽名：日期：系主任簽名：日期：長沙學(xué)院課程設(shè)計鑒定表姓名學(xué)號專業(yè)班級設(shè)計題目利用二叉排序樹對順序表進行排序指導(dǎo)教師指導(dǎo)教師意見：評定等級：教師簽名：日期：答辯小組意見：評定等級：答辯小組長簽名：日期：教研室總見：教研室主任簽名：日期：系（部）意見：系主任簽名：日期：說明課程設(shè)計成績分“優(yōu)秀”、“良好”、“及格”、“不及格”四類；摘要數(shù)據(jù)結(jié)構(gòu)是研究與數(shù)據(jù)之間的關(guān)系，我們稱這一關(guān)系為數(shù)據(jù)的邏輯結(jié)構(gòu)，簡稱數(shù)據(jù)結(jié)構(gòu)。當(dāng)數(shù)據(jù)的邏輯結(jié)構(gòu)確定以后，數(shù)據(jù)在物理空間中的存儲方式，稱為數(shù)據(jù)的存儲結(jié)構(gòu)。相同的邏輯結(jié)構(gòu)可以具有不同的存儲結(jié)構(gòu)，因而有不同的算法。本次課程設(shè)計，

5、是基于鏈?zhǔn)巾樞虮斫⒍媾判驑?。主要功能有建立、重建、插入、刪除以及遍歷。關(guān)鍵詞：二叉排序樹、中序遍歷、插入結(jié)點、刪除結(jié)點目錄第1章設(shè)計內(nèi)容與要求61.1 課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計61.2 設(shè)計要求：6第2章需求分析72.1 設(shè)計目的72.2 設(shè)計環(huán)境8第三章概要設(shè)計83.1 功能結(jié)構(gòu)83.2 函數(shù)的結(jié)構(gòu)體93.3 系統(tǒng)主要的函數(shù)10第四章詳細設(shè)計114.1 插入模塊的設(shè)計114.2 刪除模塊的設(shè)計124.3 遍歷模塊設(shè)計134.4 樹型打印模塊的設(shè)計144.5 重建二叉樹模塊的設(shè)計15第五章模塊測試165.1 插入模塊測試165.2 刪除插入模塊測試175.3 遍歷模塊測試185.4

6、 樹型打印模塊測試195.5 二叉排序樹重建模塊測試20第六章總結(jié)22第七章附錄源代碼23第1章設(shè)計內(nèi)容與要求1.1 課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計設(shè)計題目：利用二叉排序樹對順序表進行排序問題描述：利用二叉排序樹對順序表進行排序。1.2 設(shè)計要求：(1)生成一個順序表L;(2)對所生成的順序表L構(gòu)造二叉排序樹(3)利用棧結(jié)構(gòu)實現(xiàn)中序遍歷二叉排序樹；(4)中序遍歷所構(gòu)造的二叉排序樹將記錄由小到大輸出。測試數(shù)據(jù)：用偽隨機數(shù)產(chǎn)生程序產(chǎn)生，表長不小于20。選作內(nèi)容：用實現(xiàn)二叉排序樹的插入和刪除操作。第2章需求分析2.1 設(shè)計目的二叉樹的中序本次構(gòu)造的是一個二叉排序樹，主要的功能有二叉排序樹的建立、節(jié)

7、點的插入與刪除,遍歷、樹型打印、以及重建一個新的二叉排序樹。圖2.1系統(tǒng)功能模塊圖2.2 設(shè)計環(huán)境Windows10系統(tǒng)、visualstudio2015下編譯運行第三章概要設(shè)計3.1功能結(jié)構(gòu)本程序主要實現(xiàn)的有七個功能，首先創(chuàng)建二叉排序樹，完成后出現(xiàn)菜單界面，菜單界面的功能有：二叉排序樹的插入、刪除、中序遍歷、樹形輸出、二叉排序樹的重建、退出。創(chuàng)建二叉樹Switch(1)Switch(2)中序遍歷Switch(3)Exit(0)退出Switch(4)樹型打印Switch(5)Switch(6)圖3.1主要功能結(jié)構(gòu)流程圖3.2函數(shù)的結(jié)構(gòu)體typedefintkeytype;typedefintv

8、aluetype;typedefintlisttype;/structlinkliststructlinklist*next;intelement;/參數(shù)的數(shù)值；/順序表結(jié)點的結(jié)構(gòu)體structint_linkliststructlinklist*head;/順序表的頭結(jié)點的定義intcounts;/對順序表的元素的多少進行統(tǒng)計/typedefstructBSTNodekeytypedata;/存放關(guān)鍵字的datastructBSTNode*lchild,*rchild;/定義二叉排序樹的指針BTNode,*Btree;/typedefBtreeSelem;typedefstructsnode

9、Selemdata;/定義棧的存儲的數(shù)據(jù)structsnode*next;/棧的指針snode,*linkst;typedefstructlinkstacklinksttop;/定義棧的棧頂指針intcount;/統(tǒng)計棧里面的元素linkstack;3.3系統(tǒng)主要的函數(shù)structint_linklist*init();/初始化鏈?zhǔn)巾樞虮韛oidadd(structint_linklist*,int);/鏈?zhǔn)巾樞虮碓黾咏Y(jié)點voidprintf_list(structint_linklist*);/輸出已經(jīng)創(chuàng)建好的順序表/voidemptyMessage(char*);/輸出錯誤的提示voidi

10、nitstack(linkstack*);/初始化鏈?zhǔn)綏oidpushstacks(linkstack*,Selem);/進棧函數(shù)voidpopstacks(linkstack*,Selem&);/出棧函數(shù)boolempty_stack(linkstack*);/判斷棧是否為空的函數(shù)/BTNode*init_BSTree(Btree);/初始化二叉排序樹BtreeBSTree_fund();/建立一個二叉排序樹的函數(shù)boolSearch_BSTree(Btree,keytype,BTNode&,BTNode&);/判斷該值是否在二叉樹存在boolinsert_BSTr

11、ee(Btree&,valuetype);/插入一個數(shù)值，返回0或1,判斷是否插入成功boolDelete_BSTree(Btree&,keytype);/刪除函數(shù)，找到要刪除的數(shù)值，調(diào)用delete_value(Btree&tree),返回0或1判斷刪除是否成功voiddelete_value(Btree&tree);/刪除這個結(jié)點voidinoder_rec(Btree);/中序非遞歸遍歷二叉排序樹voidPrintTree(Btree,int);/按樹狀圖就行輸出/voidmenu(Btree);/函數(shù)的菜單界面第四章詳細設(shè)計4.1插入模塊的設(shè)計boolS

12、earchBSTree(Btreetree,keytypevalue,Btree&parents,Btree&child)/尋找函數(shù)，判斷二叉排序樹中是否有該值，有返回1,無返回0child=tree;/子節(jié)點等于根節(jié)點while(child)/如果子節(jié)點child不為空，則執(zhí)行下面代碼if(value=child->data)/如果值等于child->data,則表示找到，返回1return1;elseif(value<child->data)/如果該值小于child->data,則向左子樹進行查找紀(jì)錄child結(jié)點的上一個結(jié)點，相當(dāng)于記錄父節(jié)點

13、parents=child;/parentschild=child->lchild;elseparents=child;child=child->rchild;return0;/如果不執(zhí)行上面一段代碼，或者沒有找到，返回0/'boolinsert_BSTree(Btree&tree,keytypevalue)Btreeparents,child;/定義指針if(!Search_BSTree(tree,value,parents,child)/如果二叉排序樹找不到該值，則插入BtreeS=(BTNode*)malloc(sizeof(BTNode);申請一個結(jié)構(gòu)體空間

14、S->data=value;/賦值S->lchild=NULL;S->rchild=NULL;if(!tree)tree=S;/如果tree為空，則tree為s,設(shè)置根結(jié)點elseif(value<parents->data)/如果value<parents->data,就插入至U左子樹return1;/returntree;4.2刪除模塊的設(shè)計boolDeleteBSTree(Btree&tree,keytypevalue)/刪除函數(shù)if(!tree)return0;/tree為空，則表示刪除功能不能執(zhí)行elseif(value=tree-&

15、gt;data)/如果找到與value值相同的指針，調(diào)用delete_value函數(shù)進行刪除deletevalue(tree);return1;elseif(value<tree->data)/value小于結(jié)點的值，往左子樹進行尋找returnDelete_BSTree(tree->lchild,value);)elsereturnDelete_BSTree(tree->rchild,value);)/printf("%dn",tree->data);Ivoiddelete_value(Btree&p)Btreeq=NULL,s=NU

16、LL;if(p->lchild&&p->rchild)/刪除的結(jié)點，左右子樹都不為空的情況q=p;s=p->lchild;/q記錄,s設(shè)為刪除結(jié)點的左結(jié)點while(s->rchild)q=s;s=s->rchild;/進行循環(huán)，找到最右邊的那個結(jié)點p->data=s->data;/把找到的最右邊結(jié)點的關(guān)鍵字賦值給p的關(guān)鍵字if(q!=p)q->rchild=s->lchild;/掛接左右子樹elseq->lchild=s->lchild;/printf("%dt%dt%dt%dn",q-&g

17、t;data,q->data,s->data,tree->data);free(s);/刪除s這個結(jié)點elseif(!p->rchild)/右子樹為空，所以掛接到左子樹上q=p;p=p->lchild;free(q);elseq=p;p=p->rchild;free(q);/左子樹為空，所以掛接到右子樹上/printf("%dt%dt%dn",q->data,q->data,tree->data);4.3 遍歷模塊設(shè)計voidinoder_rec(BtreeT)linkstackS;|initstack(&S);

18、/初始化一個棧Seleme;Btreep=T;while(p|!(S.count=0)/當(dāng)棧不為空或者p不為空時執(zhí)行while(p)push_stacks(&S,p);/p不為空，則進棧p=p->lchild;/對左子樹進行遍歷)if(!empty_stack(&S)e=Get_top(S,e);/當(dāng)棧不為空時，取棧頂，輸出棧頂指針?biāo)赶虻膁ata值printf("%dn",e->data);pop_stacks(&S,p);/出棧，對右子樹進行遍歷p=p->rchild;)/*if(T)ninoderrec(T->lchil

19、d);printf("%dn",T->data);inoderrec(T->rchild);*/menu(tree);4.4 樹型打印模塊的設(shè)計voidPrintTree(Btreebt,intnlayer)/采用先序遍歷的方法，進行樹型打印if(bt)PrintTree(bt->rchild,nlayer+10);for(inti=0;i<nlayer;i+)printf("");printf("%dn",bt->data);PrintTree(bt->lchild,nlayer+10);4.5

20、重建二叉樹模塊的設(shè)計BtreeBSTree_fund()structint_linklist*lists=NULL;Btreetree=NULL;intn;lists=init();/初始化順序表srand(unsigned)time(NULL);/偽隨機函數(shù)的初始化printf("pleaseinputhowmanynumbers:n");scanf_s("%d",&n);輸入要插入多少的數(shù)for(inti=0;i<n;i+)add(lists,rand();/構(gòu)造順序表structlinklist*p;/Btreetree=NULL;t

21、ree=initBSTree(tree);/初始化二叉樹p=lists->head->next;while(p!=NULL)insertBSTree(tree,p->element);p=p->next;/調(diào)用insertBSTree函數(shù)構(gòu)造二叉樹returntree;第五章模塊測試5.1插入模塊測試pleaseinputhowujajiylumbers:6BStra好mpnu1.BStree_insert2iBStree_delete3.inoderBStree4、exit5.Treeoutput6.ReconstructiontheBStreepleaseinput

22、yourwant二1pleaseinputtheinsertnumbers：100successinsert!BStreemenu1. BStree_insert24BStree_delete2. inoderBStree4.exit5. Tts?ourput6,ReeonsTrucriontheBStreebleaseinputyourwant;5.2刪除插入模塊測試EiW's狀二建屋設(shè)計Dmtnjgt七二課程曲十X3.inoderBStree4.exitt),treeoutput6.ReconstructiontheBStreepleaseinputyourwant：3100得09

23、964216532211431375BSrreemenuLBStrce_insert2.BStrce_dclete3. inoderBStree4.exit,Treeoutput6,ReconstructiontheBStreepleaseinputycurwant:oz.pleaseinputth?deletekevnumbers；7520succeeddelete!BStreemenuLEStrce_inserr2.BStree_dclete&inoderBStree4.exitt>+Treeoutput6.ReconstructiontheBStreepleaseinput

24、yourwant*5.3遍歷模塊測試ij二曲毓巾比加浜±二婕設(shè)計.«31009961216532211431375BStrt?yiiieriukBStree_insert2.BStree_delete3.inoderBStree4.exitb.Ireecutpiit6.KeconstructionthfBStreepleaseinputyoi;rwnntrB1009964216532211431375一一j-BStreemenu1,13Srree_insert2,UStree_delete3.inoderBStree4.exit5xTreeoutput6.Reconstru

25、ctiontheBStreepleaseinputyourwant15.4樹型打印模塊測試?軟A二曲院設(shè)計DmbugWt二謂程iStt.eT照Xpleaseinputyourwant:31009964216532211431375BStreemenu1.BStree_inseit2.BStree_deleteinoderBStree4.exitn.Treeourput6,ReconstructiontheBStre?pleaseinputyourwant：53137522114216539964100.BStreemenu1,inserr2.UStree_delete3,inoderBStre

26、e4.exitSxTreeDLitput6.Recunsti'uctiontheBStreepleaseinputyourwant15.5二叉排序樹重建模塊測試31375216539964100BStreemenuLBStreeinsert2.BStreedeleteB.inoderBStree5. Treepleast?6please10SIJ：（*EKoutputinputinputBStree4.exit6. ReconstructiontheBStreeyourwant：howmanynumbers:menuIkBStree_insert2,BStree_delete3.ino

27、derBSti*ee4.exittheRStrepTreeoutput6.Reconstructionpleaseinputyourwant：13941803上二；，尤為第六章總結(jié)通過這次課程設(shè)計，我對二叉排序樹的整個構(gòu)造流程更加了解了，同時也對順序表和棧這兩種數(shù)據(jù)結(jié)構(gòu)做了一次復(fù)習(xí)，但同時也存在了很多問題。我在刪除函數(shù)中因為有些指針沒有用好，所以最開始只是跟我報錯說是read()出錯，我反復(fù)的檢查許久一直找不到出錯的地方在哪，不得已，只能重新寫了一遍刪除函數(shù)，發(fā)現(xiàn)我分成兩個刪除函數(shù)去執(zhí)行(一個函數(shù)去找那個需要刪除的結(jié)點，另一個函數(shù)則是對這已經(jīng)找到的結(jié)點進行刪除)，沒有問題。而對于中序遍歷函數(shù)，

28、我先用遞歸做測試，先把其他功能做完善以后，再用棧來實現(xiàn)中序非遞歸遍歷。第七章附錄源代碼#include<iostream>#include<malloc.h>#include<cstdio>#include<stdlib.h>|#include<time.h>/#include<graphics.h>/usingnamespacestd;/unsignedintn=30;/typedefintkeytype;typedefintvaluetype;typedefintlisttype;/structlinkliststru

29、ctlinklist*next;intelement;structint_linkliststructlinklist*head;intcounts;/typedefstructBSTNode|keytypedata;structBSTNode*lchild,*rchild;BTNode,*Btree;/typedefBtreeSelem;typedefstructsnodeSelemdata;structsnode*next;snode,*linkst;typedefstructlinkstacklinksttop;intcount;linkstack;/structintlinklist*

30、init();voidadd(structintlinklist*,int);voidprintf_list(structint_linklist*);/voidemptyMessage(char*);voidinitstack(linkstack*);voidpush_stacks(linkstack*,Selem);voidpop_stacks(linkstack*,Selem&);boolempty_stack(linkstack*);/BTNode*init_BSTree(Btree);BtreeBSTree_fund();boolSearch_BSTree(Btree,key

31、type,BTNode&,BTNode&);boolinsert_BSTree(Btree&,valuetype);boolDelete_BSTree(Btree&,keytype);voiddelete_value(Btree&tree);voidinoder_rec(Btree);voidPrintTree(Btree,int);/voidmenu(Btree);/、intmain()Btreetree=NULL;/printf_list(lists);tree=BSTreefund();/printf("n");/printf(

32、"%dn",tree->data);|/printf("n");/inoder_rec(tree);menu(tree);return0;/structintlinklist*init()structint_linklist*lists;lists=(structintlinklist*)malloc(sizeof(structintlinklist*);lists->head=(structlinklist*)malloc(sizeof(structlinklist);lists->head->element=-1;lists-

33、>counts=0;lists->head->next=NULL;returnlists;|)voidadd(structint_linklist*lists,intvalue)structlinklist*p;p=(structlinklist*)malloc(sizeof(structlinklist);p->next=NULL;p->element=value;p->next=lists->head->next;lists->head->next=p;lists->counts+;/returnlists;voidprin

34、tf_list(structint_linklist*lists)structlinklist*p;p=lists->head->next;while(p!=NULL)printf("%dn",p->element);p=p->next;/voidemptyMessage(char*s)printf("%sn",s);exit(1);voidinitstack(linkstack*stacks)/linkst*p;stacks->top=(linkst)malloc(sizeof(snode);if(stacks->t

35、op=NULL)emptyMessage("itisfalse");stacks->top=NULL;stacks->count=0;/stacks.top->next=NULL;SelemGet_top(linkstackstacks,Selem&e)if(stacks.top=NULL)emptyMessage("itisempty");e=stacks.top->data;returne;voidpushstacks(linkstack*stacks,Seleme)linkstp=(linkst)malloc(siz

36、eof(snode);if(p=NULL)emptyMessage("False");p->data=e;p->next=stacks->top;stacks->top=p;stacks->count+;voidpop_stacks(linkstack*stacks,Selem&e)linkstp;if(stacks->count=0)emptyMessage("itisempty");e=stacks->top->data;p=stacks->top;/printf("%dn&qu

37、ot;,p->data);|stacks->top=stacks->top->next;free(p);stacks->count-;boolempty_stack(linkstack*stacks)if(stacks->count=0)return1;elsereturn0;/BTNode*init_BSTree(Btreetree)Btreeroot=tree;returnroot;boolSearchBSTree(Btreetree,keytypevalue,Btree&parents,Btree&child)/if(tree!=NUL

38、L)child=tree;while(child)if(value=child->data)return1;elseif(value<child->data)parents=child;child=child->lchild;elseparents=child;child=child->rchild;return0;/boolinsertBSTree(Btree&tree,keytypevalue)Btreeparents,child;if(!SearchBSTree(tree,value,parents,child)BtreeS=(BTNode*)mal

39、loc(sizeof(BTNode);S->data=value;S->lchild=NULL;S->rchild=NULL;if(!tree)tree=S;elseif(value<parents->data)parents->lchild=S;return1;/returntree;/menu(tree);BtreeBSTree_fund()structint_linklist*lists=NULL;Btreetree=NULL;intn;lists=init();srand(unsigned)time(NULL);printf("please

40、inputhowmanynumbers:n");scanfs("%d",&n);for(inti=0;i<n;i+)add(lists,rand();structlinklist*p;/Btreetree=NULL;tree=init_BSTree(tree);p=lists->head->next;while(p!=NULL)insert_BSTree(tree,p->element);p=p->next;returntree;boolDelete_BSTree(Btree&tree,keytypevalue)if(

41、!tree)return0;elseif(value=tree->data)deletevalue(tree);returnDelete_BSTree(tree->rchild,value);)printf("%dn",tree->data);voiddelete_value(Btree&p)Btreeq=NULL,s=NULL;if(p->lchild&&p->rchild)|q=p;s=p->lchild;while(s->rchild)Iq=s;s=s->rchild;|)p->data=s

42、->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;/printf("%dt%dt%dt%dn",q->data,q->data,s->data,tree->data);free(s);)elseif(!p->rchild)q=p;p=p->lchild;free(q);)elseq=p;p=p->rchild;free(q);)/printf("%dt%dt%dn",q->data,q->data,tree->data);)voidinoder_rec(BtreeT)linkstackS;initstack(&S);Seleme;Btreep=T;while(p|!(S.count=0)while(p)push_stacks(&S,p);p=p->lchild;)if(!empty_stack(&S)e=Get_top(S,e);printf("%dn",e->data);pop_stacks(&S,p);p=p->rchild;/*