實驗7查找排序的應(yīng)用匯編

1、實驗報告書課 程 名 ： 數(shù)據(jù)結(jié)構(gòu)題 目： 查找、排序的應(yīng)用實驗（ 1）班 級：學(xué) 號：姓 名：評語：成績： 指導(dǎo)教師：批閱時間：年月、目的與要求1）完整理解二叉排序樹的基本概念 ;2）掌握二叉排序樹的建立、查找、插入和刪除算法實現(xiàn)思想和基本應(yīng)用方法；3）掌握二叉排序樹的建立、查找、插入和刪除算法實現(xiàn)的c 語言編程技巧；4）按照實驗題目要求獨立正確地完成實驗內(nèi)容（提交程序清單及相關(guān)實驗數(shù)據(jù)與運行結(jié)果）5）認真書寫實驗報告 , 并按時提交。二、實驗內(nèi)容或題目用 C或 C+語言設(shè)計實現(xiàn)二叉排序樹的基本操作應(yīng)用程序，功能包括： 二叉排序樹的建立，二叉排序樹的查找， 二叉排序樹的插入， 二叉排序樹的刪

2、除。 程序?qū)崿F(xiàn)后， 用記錄關(guān)鍵字序列： 98 ，47，55，70，22，8，32，69 進行正確性驗證（在建立、刪除、插入操作后要給出相應(yīng) 二叉排序樹遍歷結(jié)果） 。三、實驗步驟與源程序#include "stdafx.h"#include<iostream.h>#include<malloc.h>#include<stdio.h>#defineMAX_Node_NUM20#defineElemTypeint#defineKeyTypeint#defineInforTypechar#defineTRUE1#defineFALSE0#defi

3、neEQ(a,b)(a)=(b)#defineLT(a,b)(a)<(b)#defineLQ(a,b)(a)<=(b)記錄的關(guān)鍵字記錄的其它信息指針typedef struct dataKeyType key; /InforType *infor; / Data,*DT;typedef struct BiTNodeData data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;BiTree p,f,s,q;int SearchBST(BiTree T,KeyType key,BiTree f,BiTree &p)/ 根指針

4、T 所指的二插排序數(shù)遞歸查找關(guān)鍵字等于key 的數(shù)據(jù)元素，/ 查找成功時， p指向該結(jié)點，并返回 TRUE，否則 p 指向查找路徑/ 上訪問的最后一個結(jié)點，并返回FALSE，指針 f 指向 T 的雙親，其初始值為 NULL；if(!T)p=f;return FALSE; / 查找不成功 else if(EQ(key,T->data.key)p=T;return TRUE; / 查找成功else if(LT(key,T->data.key)return SearchBST(T->lchild,key,T,p); / 在左子樹中繼 續(xù)查找else return SearchBST

5、(T->rchild,key,T,p); / 在右子樹中繼續(xù)查 找/SearchBST int InsertBST(BiTree &T,DT e)/ 若二插排序樹中不存在關(guān)鍵字等于 e.key 的數(shù)據(jù)元素時，/ 插入 e 并返回 TRUE,否則返回 FALSE if(!SearchBST(T,e->key,NULL,p) s=(BiTree)malloc(sizeof(BiTNode); s->data=*e;s->lchild=s->rchild=NULL;if(!p)T=s; / 頭記錄 else if(LT(e->key,p->data.

6、key)p->lchild=s;else p->rchild=s;return TRUE; else return FALSE;/InsertBST int Delete(BiTree &p)/ 從二插排序樹中刪除結(jié)點 p, 并重接它的左右子樹 if(!p->rchild)/ 右子樹空則只需重接它的左子樹 q=p;p=p->lchild;delete q;else if(!p->lchild)/ 左子樹空則只需重接它的右子樹 q=p;p=p->rchild;delete q; else / 左右子樹均不空 q=p;s=p->lchild;whi

7、le(s->rchild)q=s;s=s->rchild; / 找到中序遍歷時 p 的直接前驅(qū) s p->data=s->data; /s 指向被刪結(jié)點的前驅(qū)if(q!=p) q->rchild=s->lchild; / 重接 *q 的右子樹 else q->lchild=s->lchild; / 重接 *q 的左子樹 delete s;return TRUE;/Delete int DeleteBST(BiTree &T,KeyType key)/ 若二插排序樹中存在關(guān)鍵字等于 key 的數(shù)據(jù)元素時，/ 則刪除該數(shù)據(jù)元素結(jié)點，并返回TR

8、UE，否則返回 FALSEif(!T)return FALSE; / 不存在關(guān)鍵字等于 key 的數(shù)據(jù)元素結(jié)點else if(EQ(key,T->data.key) return Delete(T); / 找到關(guān)鍵字等于 key 的數(shù)據(jù)元素結(jié)點 else if(LT(key,T->data.key)return DeleteBST(T->lchild,key);else return DeleteBST(T->rchild,key);/DeleteBST void InOrderTraverse(BiTree T)if(!T) return ;elseInOrderTr

9、averse(T->lchild);cout<<T->data.key<<"t"InOrderTraverse(T->rchild);return;/ 中序遍歷void main()BiTree T=NULL;DT e,c;int i,j=0,n;KeyType key1,key2,key3;cout<<"ttt 在二叉排序樹 T 上的操作 "<<endl;cout<<"="<<endlcout<<"="<&

10、lt;endl <<endl;cout<<"1. 建立二叉排序樹 "<<endl<<endl<<"2. 二叉排序樹中關(guān)鍵字的查找 "<<endl<<endl;cout<<"3. 二 叉 排 序 樹 中 關(guān) 鍵 字 的 插 入 "<<endl<<endl<<"4.二 叉 排 序 樹 中 關(guān) 鍵 字 的 刪 除"<<endl<<endl;cout<<&q

11、uot;5. 中序遍歷打印二叉排序樹 "<<endl<<endl<<"6. 將表置空 "<<endl<<endl<<"7. 退出操作 "<<endl<<endl;while(j!=7)cout<<" 選擇上面的數(shù)字操作項 :"cin>>j;if(j!=1&&j!=2&&j!=3&&j!=4&&j!=5&&j!=6&&am

12、p;j!=7)cout<<endl<<"Sorry! 您的輸入不正確 ! 請正確輸入 !"<<endl; continue;switch (j)case 1:cout<<" 輸入記錄關(guān)鍵字總數(shù) : "cin>>n;c=(DT)malloc(n*sizeof(Data); cout<<endl<<" 輸入記錄關(guān)鍵字序列 : " e=c;for(i=1;i<=n;i+,e+) cin>>e->key;e=c;for(i=1;i<

13、;=n;i+,e+) InsertBST(T,e); cout<<"tSuccess!"break;case 2:cout<<endl<<endl<<" 輸入要查找的記錄關(guān)鍵字 : "cin>>key1;if(SearchBST(T,key1,f,p) cout<<endl<<"t 您要查找的記錄存在 !"<<endl<<endl; else cout<<endl<<"tSorry! 沒有您要找

14、的記錄 !"<<endl<<endl;break;case 3:cout<<" 輸入要插入的記錄關(guān)鍵字 : "cin>>key2;e->key=key2;if(InsertBST(T,e) cout<<"tSuccess!"<<endl;else cout<<endl<<"tSorry!您要插入的關(guān)鍵字已經(jīng)存在 !"<<endl;break;case 4:cout<<endl<<endl&

15、lt;<" 輸入要刪除的記錄關(guān)鍵字 : " cin>>key3;if(DeleteBST(T,key3) cout<<"tSuccess!"<<endl;else cout<<"tSorry!您要刪除的記錄不存在 !"<<endl;break;case 5:cout<<endl<<"t 二叉排序樹序列為 : " if(!T) cout<<"NULL List!"<<endl; else InOrderTraverse(T);break;case 6:T=NULL; cout<<"tSuccess!" break; return; cout<<endl;四、測試數(shù)據(jù)與實驗結(jié)果圖 1 輸出