利用二叉排序樹對(duì)順序表進(jìn)行排序.doc

長 沙 學(xué) 院課程設(shè)計(jì)說明書題目 利用二叉排序樹對(duì)順序表進(jìn)行排序系(部)專業(yè)(班級(jí))姓名學(xué)號(hào)指導(dǎo)教師起止日期2015.12.82015.12.15課程設(shè)計(jì)任務(wù)書課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)設(shè)計(jì)題目：為了充分調(diào)動(dòng)學(xué)生的學(xué)習(xí)積極性與主動(dòng)性，適應(yīng)不同興趣、不同程度的學(xué)生對(duì)課程設(shè)計(jì)的要求，本課程設(shè)計(jì)提供四個(gè)任選題。每個(gè)學(xué)生可以根據(jù)本人的興趣及能力選擇教師指定的選題，也可以自定其他的選題。1、一元多項(xiàng)式計(jì)算問題2、迷宮問題3、利用二叉排序樹對(duì)順序表進(jìn)行排序4、交通咨詢系統(tǒng)5、內(nèi)部排序算法的比較已知技術(shù)參數(shù)和設(shè)計(jì)要求：需求說明及要求題目三：利用二叉排序樹對(duì)順序表進(jìn)行排序問題描述：利用二叉排序樹對(duì)順序表進(jìn)行排序?；疽螅?1) 生成一個(gè)順序表L;(2) 對(duì)所生成的順序表L構(gòu)造二叉排序樹;(3) 利用棧結(jié)構(gòu)實(shí)現(xiàn)中序遍歷二叉排序樹;(4) 中序遍歷所構(gòu)造的二叉排序樹將記錄由小到大輸出。測試數(shù)據(jù)：用偽隨機(jī)數(shù)產(chǎn)生程序產(chǎn)生，表長不小于20。選作內(nèi)容：用實(shí)現(xiàn)二叉排序樹的插入和刪除操作。各階段具體要求：1、需求分析階段熟悉系統(tǒng)業(yè)務(wù)，從業(yè)務(wù)中抽取出系統(tǒng)的需求，形成完善的需求說明書。2、系統(tǒng)設(shè)計(jì)階段根據(jù)需求，進(jìn)行程序設(shè)計(jì)，包括定義系統(tǒng)的界面、定義系統(tǒng)數(shù)據(jù)的存儲(chǔ)方式等，形成完善的設(shè)計(jì)說明書。3、編碼實(shí)現(xiàn)階段（1）完成代碼編寫 （2）要求代碼編寫規(guī)范4、系統(tǒng)測試階段（1）完成功能調(diào)試（2）要求完成必要的測試工作5、交付實(shí)施階段（1）提交可正常執(zhí)行的系統(tǒng)（2）提交系統(tǒng)需求說明書、設(shè)計(jì)說明書、程序代碼（3）撰寫課程設(shè)計(jì)報(bào)告書（4）要求規(guī)范地書寫文檔設(shè)計(jì)工作量：（1）軟件設(shè)計(jì)：完成問題陳述中所提到的所有需求功能。（2）論文：要求撰寫不少于3000字的文檔，詳細(xì)說明各階段具體要求。工作計(jì)劃：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)總學(xué)時(shí)數(shù)為2 周，其進(jìn)度及時(shí)間大致分配如下：序號(hào) 設(shè)計(jì)內(nèi)容 天數(shù)1 分析問題，給出數(shù)學(xué)模型，選擇數(shù)據(jù)結(jié)構(gòu) 12 設(shè)計(jì)算法，給出算法描述 23 給出源程序清單 14 編輯、編譯、調(diào)試源程序 55 編寫課程設(shè)計(jì)報(bào)告 1總 計(jì) 10注意事項(xiàng)n 提交文檔 長沙學(xué)院課程設(shè)計(jì)任務(wù)書（每學(xué)生1份） 長沙學(xué)院課程設(shè)計(jì)鑒定表（每學(xué)生1份） 長沙學(xué)院課程設(shè)計(jì)說明書（每學(xué)生1份）指導(dǎo)教師簽名： 日期： 教研室主任簽名： 日期：系主任簽名： 日期：長沙學(xué)院課程設(shè)計(jì)鑒定表姓名學(xué)號(hào) 專業(yè)班級(jí)設(shè)計(jì)題目利用二叉排序樹對(duì)順序表進(jìn)行排序指導(dǎo)教師指導(dǎo)教師意見：評(píng)定等級(jí)： 教師簽名： 日期： 答辯小組意見：評(píng)定等級(jí)：答辯小組長簽名：日期：教研室意見：教研室主任簽名： 日期： 系（部）意見：系主任簽名：日期：說明課程設(shè)計(jì)成績分“優(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ù)在物理空間中的存儲(chǔ)方式，稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。相同的邏輯結(jié)構(gòu)可以具有不同的存儲(chǔ)結(jié)構(gòu)，因而有不同的算法。本次課程設(shè)計(jì)，是基于鏈?zhǔn)巾樞虮斫⒍媾判驑?。主要功能有建立、重建、插入、刪除以及遍歷。關(guān)鍵詞：二叉排序樹、中序遍歷、插入結(jié)點(diǎn)、刪除結(jié)點(diǎn)目錄第1章設(shè)計(jì)內(nèi)容與要求71.1課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)71.2 設(shè)計(jì)要求：7第2章需求分析82.1設(shè)計(jì)目的82.2 設(shè)計(jì)環(huán)境8第三章 概要設(shè)計(jì)93.1 功能結(jié)構(gòu)93.2函數(shù)的結(jié)構(gòu)體103.3系統(tǒng)主要的函數(shù)10第四章 詳細(xì)設(shè)計(jì)124.1插入模塊的設(shè)計(jì)124.2刪除模塊的設(shè)計(jì)134.3遍歷模塊設(shè)計(jì)144.4樹型打印模塊的設(shè)計(jì)154.5重建二叉樹模塊的設(shè)計(jì)15第五章 模塊測試165.1插入模塊測試165.2刪除插入模塊測試175.3遍歷模塊測試185.4樹型打印模塊測試195.5二叉排序樹重建模塊測試20第六章 總結(jié)22第七章 附錄源代碼23第1章 設(shè)計(jì)內(nèi)容與要求 1.1課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì) 設(shè)計(jì)題目： 利用二叉排序樹對(duì)順序表進(jìn)行排序 問題描述：利用二叉排序樹對(duì)順序表進(jìn)行排序。1.2 設(shè)計(jì)要求： (1) 生成一個(gè)順序表L;(2) 對(duì)所生成的順序表L構(gòu)造二叉排序樹;(3) 利用棧結(jié)構(gòu)實(shí)現(xiàn)中序遍歷二叉排序樹;(4) 中序遍歷所構(gòu)造的二叉排序樹將記錄由小到大輸出。測試數(shù)據(jù)：用偽隨機(jī)數(shù)產(chǎn)生程序產(chǎn)生，表長不小于20。選作內(nèi)容：用實(shí)現(xiàn)二叉排序樹的插入和刪除操作。第2章 需求分析2.1設(shè)計(jì)目的 本次構(gòu)造的是一個(gè)二叉排序樹，主要的功能有二叉排序樹的建立、節(jié)點(diǎn)的插入與刪除，二叉樹的中序遍歷、樹型打印、以及重建一個(gè)新的二叉排序樹。 二叉排序樹系統(tǒng)主菜單建立退出中序遍歷樹型打印刪除插入 圖2.1 系統(tǒng)功能模塊圖2.2 設(shè)計(jì)環(huán)境Windows 10系統(tǒng)、visual studio2015下編譯運(yùn)行第三章 概要設(shè)計(jì) 3.1 功能結(jié)構(gòu) 本程序主要實(shí)現(xiàn)的有七個(gè)功能，首先創(chuàng)建二叉排序樹，完成后出現(xiàn)菜單界面，菜單界面的功能有：二叉排序樹的插入、刪除、中序遍歷、樹形輸出、二叉排序樹的重建、退出。 創(chuàng)建二叉樹Switch(1)插入結(jié)點(diǎn)刪除結(jié)點(diǎn)重建二叉樹樹型打印Exit(0)退出中序遍歷Switch(2)Switch(3)Switch(4)Switch(5)Switch(6) 圖3.1 主要功能結(jié)構(gòu)流程圖 3.2函數(shù)的結(jié)構(gòu)體typedef int keytype;typedef int valuetype;typedef int listtype;/struct linklist struct linklist *next;int element; /參數(shù)的數(shù)值; /順序表結(jié)點(diǎn)的結(jié)構(gòu)體struct int_linklist struct linklist *head; /順序表的頭結(jié)點(diǎn)的定義int counts; /對(duì)順序表的元素的多少進(jìn)行統(tǒng)計(jì);/typedef struct BSTNode keytype data; /存放關(guān)鍵字的datastruct BSTNode *lchild, *rchild; /定義二叉排序樹的指針BTNode, *Btree;/typedef Btree Selem;typedef struct snode Selem data; /定義棧的存儲(chǔ)的數(shù)據(jù)struct snode *next; /棧的指針snode, *linkst;typedef struct linkstack linkst top; /定義棧的棧頂指針int count; /統(tǒng)計(jì)棧里面的元素linkstack; 3.3系統(tǒng)主要的函數(shù)struct int_linklist*init();/ 初始化鏈?zhǔn)巾樞虮韛oid add(struct int_linklist*, int);/鏈?zhǔn)巾樞虮碓黾咏Y(jié)點(diǎn)void printf_list(struct int_linklist *);/輸出已經(jīng)創(chuàng)建好的順序表/void emptyMessage(char *);/輸出錯(cuò)誤的提示void initstack(linkstack *);/初始化鏈?zhǔn)綏oid push_stacks(linkstack *, Selem );/進(jìn)棧函數(shù)void pop_stacks(linkstack *,Selem&);/出棧函數(shù)bool empty_stack(linkstack *);/判斷棧是否為空的函數(shù)/BTNode *init_BSTree(Btree);/初始化二叉排序樹Btree BSTree_fund();/建立一個(gè)二叉排序樹的函數(shù)bool Search_BSTree(Btree, keytype, BTNode&, BTNode&);/判斷該值是否在二叉樹存在bool insert_BSTree(Btree&, valuetype);/插入一個(gè)數(shù)值，返回0或1，判斷是否插入成功bool Delete_BSTree(Btree&, keytype);/刪除函數(shù)，找到要?jiǎng)h除的數(shù)值，調(diào)用delete_value(Btree &tree)，返回0或1判斷刪除是否成功 void delete_value(Btree &tree);/刪除這個(gè)結(jié)點(diǎn)void inoder_rec(Btree);/中序非遞歸遍歷二叉排序樹void PrintTree(Btree, int);/按樹狀圖就行輸出/void menu(Btree);/函數(shù)的菜單界面第四章 詳細(xì)設(shè)計(jì)4.1插入模塊的設(shè)計(jì) bool Search_BSTree(Btree tree, keytype value, Btree &parents, Btree &child) /尋找函數(shù)，判斷二叉排序樹中是否有該值，有返回1，無返回0child = tree;/子節(jié)點(diǎn)等于根節(jié)點(diǎn)while (child) /如果子節(jié)點(diǎn)child不為空，則執(zhí)行下面代碼if (value = child-data) /如果值等于child-data，則表示找到，返回1return 1;else if (value data) /如果該值小于child-data，則向左子樹進(jìn)行查找parents = child; /parents紀(jì)錄child結(jié)點(diǎn)的上一個(gè)結(jié)點(diǎn)，相當(dāng)于記錄父節(jié)點(diǎn)child = child-lchild;else parents = child;child = child-rchild;return 0; /如果不執(zhí)行上面一段代碼，或者沒有找到，返回0/ bool insert_BSTree(Btree &tree, keytype value) Btree parents, child; /定義指針if (!Search_BSTree(tree, value, parents, child) /如果二叉排序樹找不到該值，則插入Btree S = (BTNode*)malloc(sizeof(BTNode); /申請(qǐng)一個(gè)結(jié)構(gòu)體空間S-data = value; /賦值S-lchild = NULL;S-rchild = NULL;if (!tree) tree = S; /如果tree為空，則tree為s，設(shè)置根結(jié)點(diǎn)else if (value data) /如果value data，就插入到左子樹parents-lchild = S;else parents-rchild = S; /反之，插入到右子樹return 1;/ return tree;4.2刪除模塊的設(shè)計(jì) bool Delete_BSTree(Btree &tree, keytype value) /刪除函數(shù)if (!tree)return 0; /tree為空，則表示刪除功能不能執(zhí)行else if (value = tree-data) /如果找到與value值相同的指針，調(diào)用delete_value函數(shù)進(jìn)行刪除delete_value(tree);return 1;else if (value data) /value小于結(jié)點(diǎn)的值，往左子樹進(jìn)行尋找return Delete_BSTree(tree-lchild, value);else return Delete_BSTree(tree-rchild, value);/printf(%dn, tree-data);void delete_value(Btree &p) Btree q = NULL, s = NULL;if (p-lchild & p-rchild) /刪除的結(jié)點(diǎn)，左右子樹都不為空的情況q = p; s = p-lchild; /q記錄,s設(shè)為刪除結(jié)點(diǎn)的左結(jié)點(diǎn)while (s-rchild) q = s; s = s-rchild;/進(jìn)行循環(huán)，找到最右邊的那個(gè)結(jié)點(diǎn)p-data = s-data; /把找到的最右邊結(jié)點(diǎn)的關(guān)鍵字賦值給p的關(guān)鍵字if (q != p) q-rchild = s-lchild; /掛接左右子樹else q-lchild = s-lchild;/printf(%dt%dt%dt%dn, q-data, q-data, s-data, tree-data);free(s); /刪除s這個(gè)結(jié)點(diǎn)else if (!p-rchild) /右子樹為空，所以掛接到左子樹上q = p; p = p-lchild; free(q);else q = p; p = p-rchild; free(q); /左子樹為空，所以掛接到右子樹上/printf(%dt%dt%dn,q - data,q - data,tree-data);4.3遍歷模塊設(shè)計(jì) void inoder_rec(Btree T) linkstack S ;initstack( &S);/初始化一個(gè)棧Selem e;Btree p = T;while (p | !(S.count = 0) /當(dāng)棧不為空或者p不為空時(shí)執(zhí)行while(p) push_stacks(&S, p); /p不為空，則進(jìn)棧p = p-lchild; /對(duì)左子樹進(jìn)行遍歷if(!empty_stack(&S) e = Get_top(S, e); /當(dāng)棧不為空時(shí)，取棧頂，輸出棧頂指針?biāo)赶虻膁ata值printf(%dn,e - data);pop_stacks(&S, p); /出棧，對(duì)右子樹進(jìn)行遍歷p = p-rchild;/*if (T) inoder_rec(T-lchild);printf(%dn, T-data);inoder_rec(T-rchild);*/menu(tree);4.4樹型打印模塊的設(shè)計(jì) void PrintTree(Btree bt, int nlayer) /采用先序遍歷的方法，進(jìn)行樹型打印 if(bt)PrintTree(bt-rchild, nlayer + 10);for (int i = 0; idata);PrintTree(bt-lchild, nlayer + 10);4.5重建二叉樹模塊的設(shè)計(jì) Btree BSTree_fund() struct int_linklist *lists = NULL;Btree tree = NULL;int n;lists = init();/初始化順序表srand(unsigned)time(NULL); /偽隨機(jī)函數(shù)的初始化printf(please input how many numbers:n);scanf_s(%d, &n); /輸入要插入多少的數(shù)for (int i = 0; i head-next;while (p != NULL) insert_BSTree(tree, p-element);p = p-next;/調(diào)用insert_BSTree函數(shù)構(gòu)造二叉樹return tree; 第五章 模塊測試5.1插入模塊測試5.2刪除插入模塊測試5.3遍歷模塊測試5.4樹型打印模塊測試5.5二叉排序樹重建模塊測試第六章 總結(jié)通過這次課程設(shè)計(jì)，我對(duì)二叉排序樹的整個(gè)構(gòu)造流程更加了解了，同時(shí)也對(duì)順序表和棧這兩種數(shù)據(jù)結(jié)構(gòu)做了一次復(fù)習(xí)，但同時(shí)也存在了很多問題。我在刪除函數(shù)中因?yàn)橛行┲羔槢]有用好，所以最開始只是跟我報(bào)錯(cuò)說是read()出錯(cuò)，我反復(fù)的檢查許久一直找不到出錯(cuò)的地方在哪，不得已，只能重新寫了一遍刪除函數(shù)，發(fā)現(xiàn)我分成兩個(gè)刪除函數(shù)去執(zhí)行（一個(gè)函數(shù)去找那個(gè)需要?jiǎng)h除的結(jié)點(diǎn)，另一個(gè)函數(shù)則是對(duì)這已經(jīng)找到的結(jié)點(diǎn)進(jìn)行刪除），沒有問題。而對(duì)于中序遍歷函數(shù)，我先用遞歸做測試，先把其他功能做完善以后，再用棧來實(shí)現(xiàn)中序非遞歸遍歷。第七章 附錄源代碼 #include#include#include#include#include/#include/using namespace std;/unsigned int n = 30;/typedef int keytype;typedef int valuetype;typedef int listtype;/struct linklist struct linklist *next;int element;struct int_linklist struct linklist *head;int counts;/typedef struct BSTNode keytype data;struct BSTNode *lchild, *rchild;BTNode, *Btree;/typedef Btree Selem;typedef struct snode Selem data;struct snode *next;snode, *linkst;typedef struct linkstack linkst top;int count;linkstack;/struct int_linklist*init();void add(struct int_linklist*, int);void printf_list(struct int_linklist *);/void emptyMessage(char *);void initstack(linkstack *);void push_stacks(linkstack *, Selem );void pop_stacks(linkstack *,Selem&);bool empty_stack(linkstack *);/BTNode *init_BSTree(Btree);Btree BSTree_fund();bool Search_BSTree(Btree, keytype, BTNode&, BTNode&);bool insert_BSTree(Btree&, valuetype);bool Delete_BSTree(Btree&, keytype);void delete_value(Btree &tree);void inoder_rec(Btree);void PrintTree(Btree, int);/void menu(Btree);/、int main() Btree tree = NULL;/printf_list(lists);tree = BSTree_fund();/printf(n);/printf(%dn, tree-data);/printf(n);/inoder_rec(tree);menu(tree);return 0;/struct int_linklist* init() struct int_linklist*lists;lists = (struct int_linklist*)malloc(sizeof(struct int_linklist*);lists-head = (struct linklist*)malloc(sizeof(struct linklist);lists-head-element = -1;lists-counts = 0;lists-head-next = NULL;return lists;void add(struct int_linklist *lists, int value) struct linklist *p;p = (struct linklist *)malloc(sizeof(struct linklist);p-next = NULL;p-element = value;p-next = lists-head-next;lists-head-next = p;lists-counts+;/return lists;void printf_list(struct int_linklist *lists) struct linklist *p;p = lists-head-next;while (p != NULL) printf(%dn, p-element);p = p-next;/void emptyMessage(char *s) printf(%sn, s);exit(1);void initstack(linkstack *stacks) /linkst *p;stacks-top = (linkst)malloc(sizeof(snode);if (stacks-top = NULL)emptyMessage(it is false);stacks-top = NULL;stacks-count = 0;/stacks.top - next = NULL;Selem Get_top(linkstack stacks, Selem &e) if (stacks.top = NULL)emptyMessage(it is empty);e = stacks.top-data;return e;void push_stacks(linkstack *stacks, Selem e) linkst p = (linkst)malloc(sizeof(snode);if (p = NULL)emptyMessage(False);p-data = e;p-next = stacks-top;stacks-top = p;stacks-count+;void pop_stacks(linkstack *stacks,Selem &e) linkst p;if (stacks-count = 0)emptyMessage(it is empty);e = stacks-top-data;p = stacks-top;/printf(%dn, p-data);stacks-top = stacks-top-next;free(p);stacks-count-;bool empty_stack(linkstack *stacks) if (stacks-count = 0)return 1;else return 0;/BTNode *init_BSTree(Btree tree) Btree root = tree;return root;bool Search_BSTree(Btree tree, keytype value, Btree &parents, Btree &child) /if(tree != NULL)child = tree;while (child) if (value = child-data) return 1;else if (value data) parents = child;child = child-lchild;else parents = child;child = child-rchild;return 0;/ bool insert_BSTree(Btree &tree, keytype value) Btree parents, child;if (!Search_BSTree(tree, value, parents, child) Btree S = (BTNode*)malloc(sizeof(BTNode);S-data = value;S-lchild = NULL;S-rchild = NULL;if (!tree) tree = S;else if (value data) parents-lchild = S;else parents-rchild = S;return 1;/ return tree;/ menu(tree);Btree BSTree_fund() struct int_linklist *lists = NULL;Btree tree = NULL;int n;lists = init();srand(unsigned)time(NULL);printf(please input how many numbers:n);scanf_s(%d, &n);for (int i = 0; i head-next;while (p != NULL) insert_BSTree(tree, p-element);p = p-next;return tree;bool Delete_BSTree(Btree &tree, keytype value) if (!tree)return 0;else if (value = tree-data) delete_value(tree);return 1;else if (value data) return Delete_BSTree(tree-lchild, value);else return Delete_BSTree(tree-rchild, value);printf(%dn, tree-data);void delete_value(Btree &p) Btree q = NULL, s = NULL;if (p-lchild & p-rchild) q = p; s = p-lchild;while (s-rchild) q = s; s = s-rchild;p-data = s-data;if (q != p) q-rchild = s-lchild;else q-lchild = s-lchild;/printf(%dt%dt%dt%dn, q-data, q-data, s-data, tree-data);free(s);else if (!p-rchild) q = p; p = p-lchild; free(q);else q = p; p = p-rchild; free(q);/printf(%dt%dt%dn,q - data,q - data,tree-data);void inoder_rec(Btree T) linkstack S ;initstack( &S);Selem e;Btree p = 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