BST實現(xiàn)動態(tài)查找表

1、HUNAN UNIVERSITY課程實習(xí)報告題 目： BST實現(xiàn)動態(tài)查找表 學(xué)生姓名 學(xué)生學(xué)號 專業(yè)班級 計算機科學(xué)與技術(shù) 指導(dǎo)老師 李曉鴻 完 成 日 期 一、需求分析 1、程序任務(wù)：本程序是利用二叉查找樹（BST）來實現(xiàn)；二叉樹使用鏈式結(jié)構(gòu)（二叉鏈表）實現(xiàn)；本程序要實現(xiàn)BST的構(gòu)建，查找兩個功能。2、輸入形式：整數(shù)n/BST的節(jié)點個數(shù)n/n個數(shù)據(jù)數(shù)據(jù)x/查找此數(shù)據(jù)3、輸出形式： 查找成功 整數(shù)m（次數(shù)）/返回成功和查找時比較的次數(shù) 或：查找不成功 整數(shù)m（次數(shù)） /返回不成功和查找時比較的次數(shù)4、測試數(shù)據(jù)： 輸入：8/BST的節(jié)點個數(shù)34, 76, 45, 18, 26, 54, 92,

2、65 /8個數(shù)據(jù)輸入：45/查找 45 輸出：查找成功 3 /返回成功和查找時比較的次數(shù) 輸入：34/查找 34輸出：查找成功 1 /返回成功和查找時比較的次數(shù)輸入：100/查找 100輸出：查找不成功 3 /返回成功和查找時比較的次數(shù)二、概要設(shè)計 抽象數(shù)據(jù)類型以正整數(shù)儲存用戶輸入節(jié)點個數(shù)，浮點小數(shù)存儲用戶輸入的數(shù)據(jù)。要實現(xiàn)動態(tài)查找表，二叉查找樹BST的效率很高，因此用BST實現(xiàn)，二叉查找樹定義如下：ADT BST數(shù)據(jù)對象：D具有相同特性的一組數(shù)據(jù)元素 數(shù)據(jù)關(guān)系：若D為空集，則稱為空樹 。 否則: (1) 在D中存在唯一的稱為根的數(shù)據(jù)元素root； (2) 當n>1時，其余結(jié)點可分為m

3、(m>0)個互不相交的有限集Tl、 Tr，其中每一棵子集本身又是一棵符合本定義的樹，稱為根root的子樹。 (3)對于任意結(jié)點，設(shè)其值為K，則該結(jié)點左子樹中任意一個結(jié)點的值都小于K， 右子樹中任意一個結(jié)點的值都大于等于K。 基本操作： InitBST(BST &)/初始化二叉樹InitBSTNode(BSTNode *)/初始化結(jié)點clearBST(BSTNode *)/銷毀二叉樹結(jié)構(gòu)insert(BST &, Elem&)/插入結(jié)點find(BST &,Elem& ,int count)/查找結(jié)點,記錄查找次數(shù) ADT BST算法的基本思想根據(jù)題

4、目要求，用二叉查找樹實現(xiàn)動態(tài)查找表。首先將輸入的元素插入BST中。判斷輸入要查找的元素是否在BST中，遞歸比較要查找的元素與當前元素的值的大小，若小于當前值，則查找其左子樹；若大于，則查找其右子樹。設(shè)置一個計數(shù)器，每查找一次則加一。如果找到，則輸出位置和查找次數(shù)。程序的流程程序由三個模塊組成：（1） 輸入模塊：輸入結(jié)點數(shù)目初始數(shù)據(jù)，構(gòu)建二叉查找樹（2） 查找模塊：判斷需要查找的值是否在該BST中（3） 輸出模塊：輸出查找成功與否，并輸出比較的次數(shù)三、詳細設(shè)計算法的具體步驟插入元素e時，先判斷該二叉樹是否為空，若為空，將e作為該二叉樹的根節(jié)點。否則，從根節(jié)點開始，比較e與節(jié)點n的大小。如果e的值

5、更小，判斷n的左子樹是否為空，若為空，將e作為節(jié)點n的左孩子并返回e，否則比較e與n左孩子的值，依此循環(huán)下去；如果e的值更大，判斷n的右子樹是否為空，若為空，將e作為節(jié)點n的右孩子并返回e，否則比較e與n右孩子的值，依此循環(huán)下去。查找元素時，從根節(jié)點開始，比較e與節(jié)點x的大小，若相等，返回true；如果e比節(jié)點x的值小，判斷x的左子樹是否為空，若為空，返回false，不為空則比較e與x左孩子的值，依次循環(huán)下去；如果e比節(jié)點x的值大，判斷x的右子樹是否為空，若為空，返回false，不為空則比較e與x右孩子的值，依次循環(huán)下去。物理數(shù)據(jù)類型動態(tài)查找表的數(shù)據(jù)為小數(shù)或整數(shù)，用float類型保存。type

6、def float ElemType;為了提高空間利用率，用鏈表來實現(xiàn)BST，由于BST是二叉樹，每個節(jié)點有左右兩個節(jié)點，所以用二叉鏈表實現(xiàn)。typedef struct BSTNode ElemType data; struct BSTNode *lchild, *rchild;BSTNode;typedef struct BST BSTnode *root;BST;基本操作：bool InitBST(BST &b) /初始化二叉樹 b.root=NULL;return ture;bool InitBSTNode(BSTNode * &n) /初始化節(jié)點 n=(BSTNode

7、 *)malloc(sizeof(BSTnode); (*n).lchild=NULL;(*n).rchild=NULL;return ture;bool clearBST(BSTNode * &n) /銷毀BST if(n) return false;if(*n).lchild) clearBST(*n).lchild); if(*N).rchild) clearBST(*n).rchild); free(n); return ture;bool insert(BST &b,ElemType e)/把結(jié)點插入BST BSTNode *n,*m; InitBSTNode(n);

8、 (*n).data=e; if(b.root=NULL) b.root=n; return ture; m=b.root; while(1)/循環(huán)比較 if(e<(*m).data)/小于根節(jié)點則插入左子樹 if(*m).lchild=NULL) (*m).lchild=m;/給左孩子賦值return ture; else m=(*m).lchild;continue; /跳出此次循環(huán)，開始下一次 else/大于根節(jié)點則插入右子樹 if(*m).rchild=NULL) (*m).rchild=n; /給右孩子賦值return ture; else m=(*m).rchild;cont

9、inue;/跳出此次循環(huán)，開始下一次 bool find(BST b,ElemType e,int &count) /查詢元素e，記錄比較的次數(shù)，查詢成功返回ture，否則返回false int count=0; BSTnode *x=b.root; while(1)/循環(huán)比較count+;/設(shè)置計數(shù)器 if(e<(*x).data)/小于根節(jié)點則在左子樹中查找 if(*x).lchild=NULL) return false;/左子樹為空則查找失敗 x=(*x).lchild;/繼續(xù)與左孩子的值比較continue; if(e>(*x).data) /大于根節(jié)點則在右子樹

10、中查找 if(*x).rchild=NULL) return false; /右子樹為空則查找失敗 x=(*x).rchild; /繼續(xù)與右孩子的值比較continue; if(e=(*x).data) return ture;算法的時空分析查找元素需要的比較次數(shù)由樹的深度決定。因此平均情況為（log（n），最差情況為（n）。輸入和輸出的格式輸入請輸入樹的節(jié)點數(shù)目：/等待輸入 請輸入所有節(jié)點數(shù)據(jù)：/等待輸入請輸入要查找的數(shù)據(jù)：/等待輸入輸出查找成功，查找次數(shù)：/輸出次數(shù) 或查找失敗，查找次數(shù)：/輸出次數(shù) 四、測試結(jié)果附錄：源代碼#include<iostream>#include&

11、lt;stdlib.h>using namespace std;typedef float ElemType;typedef struct BSTNode ElemType data; struct BSTNode *lchild, *rchild;BSTNode;typedef struct BST BSTNode *root;BST;bool InitBST(BST *b) /初始化二叉樹 b->root=NULL;return true;bool InitBSTNode(BSTNode * &n) /初始化節(jié)點 n=(BSTNode *)malloc(sizeof(B

12、STNode); (*n).lchild=NULL;(*n).rchild=NULL;return true;bool clearBST(BSTNode * &n) /銷毀BST if(n) return false; if(*n).lchild) clearBST(*n).lchild); if(*n).rchild) clearBST(*n).rchild); free(n); return true;bool insert(BST *b,ElemType e)/把結(jié)點插入BST BSTNode *n,*m; InitBSTNode(n); (*n).data=e; if(b-&g

13、t;root=NULL)b->root=n; return true; m=b->root; while(1)/循環(huán)比較 if(e<(*m).data)/小于根節(jié)點則插入左子樹 if(*m).lchild=NULL) (*m).lchild=n;/給左孩子賦值 return true; else m=(*m).lchild; continue; else/大于根節(jié)點則插入右子樹 if(*m).rchild=NULL) (*m).rchild=n; /給右孩子賦值 return true; else m=(*m).rchild; continue; bool find(BST

14、*b,ElemType e) /查詢元素e，記錄比較的次數(shù)查詢成功返回true，否則返回false int count=0; BSTNode *x=b->root; while(1)/循環(huán)比較 count+;/設(shè)置計數(shù)器 if(e<(*x).data)/小于根節(jié)點則在左子樹中查找 if(*x).lchild=NULL) cout<<"查找失敗,查找次數(shù)： "<<count<<endl;return false;/左子樹為空則查找失敗x=(*x).lchild;/繼續(xù)與左孩子的值比較 continue; if(e>(*x)

15、.data) /大于根節(jié)點則在右子樹中查找 if(*x).rchild=NULL) cout<<"查找失敗,查找次數(shù)： "<<count<<endl;return false;/右子樹為空則查找失敗x=(*x).rchild;/繼續(xù)與右孩子的值比較 continue; if(e=(*x).data) cout<<"查找成功,查找次數(shù)： "<<count<<endl; cout<<count; return true; void main()int n,m=0,count;BST b;InitBST(&b);cout<<"請輸入樹的節(jié)點數(shù)目："<<endl;cin>>n;ElemType *