实验报告八查找算法实现实验班级： 2009053 姓名：汤冬劼学号：20091776 专业：一、实验目的：1、熟悉线性查找算法。

2、掌握顺序查找、二分查找算法3、熟悉非线性查找算法。

3、掌握二叉排序树操作算法。

二、实验内容：[实现提示] （同时可参见教材及ppt上的算法）函数、类名称等可自定义，部分变量请加上学号后3位。

也可自行对类中所定义的操作进行扩展。

所加载的库函数或常量定义及类的定义：#include<iostream>using namespace std;template <class T1,class T2> class seqlist;template <class T1,class T2>class elem{friend class seqlist<T1,T2>;T1 key;T2 other;};template <class T1,class T2>class seqlist{public:seqlist(int n1,T1 a[ ]);int seqcheck(int k);private:elem<T1,T2> *data;int n;};1、存储结构类定义与实现：自定义如下：template<class T1,class T2>seqlist<T1,T2>::seqlist(int n1,T1 a[ ]){data=new elem<T1,T2>[n1];for(int i=0;i<n1;i++)data[i].key=a[i];n=n1;}2、顺序查找算法[实现提示] （同时可参见教材算法）顺序查找算法实现如下：template <class T1,class T2>int seqlist<T1,T2>::seqcheck(int k){int i=n;data[0].key=k;//哨兵while (data[i].key!=k)i--;return i;}测试结果粘贴如下：3、有序表的二分查找（折半查找）[实现提示] （同时可参见教材算法）库函数和常量定义：#include<iostream>using namespace std;template <class T1,class T2> class seqlist; template <class T1,class T2>class elem{friend class seqlist<T1,T2>;T1 key;T2 other;};template <class T1,class T2>class seqlist{public:seqlist(int n1,T1 a[ ]);int seqcheck(int k);int rfcz(int k);private:elem<T1,T2> *data;int n;};（1）存储结构定义：自定义如下：（可自已定义）template<class T1,class T2>seqlist<T1,T2>::seqlist(int n1,T1 a[ ]){data=new elem<T1,T2>[n1];for(int i=0;i<n1;i++)data[i].key=a[i];n=n1;}（2）二分查找算法template <class T1,class T2>int seqlist<T1,T2>::rfcz(int k){//二分查找算法int low,high,mid;for(low=1,high=n;low<=high;){mid=(low+high)/2;if(k==data[mid].key) return mid;else if(k<data[mid].key) high=mid-1;else low=mid+1;}return 0;}测试结果粘贴如下：4、二叉排序树的操作算法[实现提示] （同时可参见教材算法）（1）二叉排序树的查找算法（2）二叉排序树的插入算法#include<iostream>using namespace std;template <class T> class BiSortTree; template <class T>class BiNode //二叉树的结点结构{friend class BiSortTree<T>;T data;BiNode<T> *lchild, *rchild;};template <class T>class BiSortTree //假定记录中只有一个整型数据项{public:BiSortTree(T a[ ],int n);~BiSortTree();BiNode<T>*InsertTree(BiNode<T> *p,BiNode<T> *s);void chazhao(T k,BiNode<T> *p);void find(T k);private:BiNode<T> *root;void Release(BiNode<T> *p);};template<class T>BiSortTree<T>::BiSortTree(T a[ ],int n){root=new BiNode<T>;BiNode<T> *m;root->data=a[0];root->lchild=NULL;root->rchild=NULL;for(int i=1;i<n;i++){m=new BiNode<T>;m->data=a[i];m->rchild=NULL;m->lchild=NULL;InsertTree(root,m);}}template <class T>BiNode<T>* BiSortTree<T>::InsertTree(BiNode<T> *p, BiNode<T> *s) {if(p==NULL) return s;else{if(s->data>p->data)p->rchild=InsertTree(p->rchild, s);elsep->lchild=InsertTree(p->lchild, s);return p;}}template<class T>void BiSortTree<T>::chazhao(T k,BiNode<T> *p) {if(p==NULL){BiNode<T> *s;s=new BiNode<T>;s->data=k;s->rchild=NULL;s->lchild=NULL;p=s;cout<<"以添加"<<endl;}else{if(k<p->data)chazhao(k,p->lchild);if(k>p->data)chazhao(k,p->rchild);if(k==p->data)cout<<"找到了"<<endl;}}template<class T>void BiSortTree<T>::find(T k){chazhao(k,root);}template<class T>void BiSortTree<T>::Release(BiNode<T> *p) {if(p!=NULL){if(p->lchild==NULL&&p->rchild==NULL) delete p;else{Release(p->lchild);Release(p->rchild);}}}template<class T>BiSortTree<T>::~BiSortTree(){Release(root);}int main(){int b[7]={10,8,13,6,9,12,15};BiSortTree<int> tree(b,7);tree.find(5);return 0;}测试结果粘贴如下：选做：试写有序表的分块查找算法和二叉排序树的删除算法。

#include<iostream>using namespace std;template <class T1,class T2> class seqlist;template <class T1,class T2>class elem{friend class seqlist<T1,T2>;T1 key;T2 other;};template <class T1,class T2>class seqlist{public:seqlist(int n1,T1 a[ ]);int chazhao(T1 k);private:elem<T1,T2> *data;elem<T1,T2> *data1;int n;};template<class T1,class T2>seqlist<T1,T2>::seqlist(int n1,T1 a[ ]){data=new elem<T1,T2>[n1];paixu(n1,a);for(int i=0;i<n1;i++)data[i].key=a[i];n=n1;data1=new elem<T1,T2>[n1/2+1]; for(i=0;2*i+1<n1;i++){data1[i].key=data[2*i+1].key; data1[i].other=2*i;}data1[n/2].key=data[n-1].key;data1[n/2].other=n-1;}template<class T1>void paixu(int n1,T1 a[ ]){T1 min=a[0];for(int i=0;i<n1;i++)for(int j=i+1;j<n1;j++)if(min>a[j]){min=a[j];a[i]=a[j];}}template<class T1,class T2>int seqlist<T1,T2>::chazhao(T1 k) {int i=0,j;while(data1[i].key<k&&i<n/2+1) i++;if(i==n/2+1)return 0;else{j=data1[i].other;if(j==n-1)return 0;for(int k1=0;k1<2;k1++){if(data[j].key==k)return j;j++;}return 0;}}int main(){int b[5]={1,2,3,4,5};seqlist<int,int>cha(5,b);cout<<cha.chazhao(3)<<endl;return 0;}#include<iostream>using namespace std;template <class T> class BiSortTree;template <class T>class BiNode //二叉树的结点结构{friend class BiSortTree<T>;T data;BiNode<T> *lchild, *rchild,*parent;};template <class T>class BiSortTree //假定记录中只有一个整型数据项{public:BiSortTree(T a[ ],int n);~BiSortTree();BiNode<T>*InsertTree(BiNode<T> *p,BiNode<T> *s);void chazhao(T k,BiNode<T> *p);void find(T k);void display();private:BiNode<T> *root;void Release(BiNode<T> *p);void dDLR(BiNode<T> *rt);};template<class T>BiSortTree<T>::BiSortTree(T a[ ],int n){root=new BiNode<T>;BiNode<T> *m;root->data=a[0];root->lchild=NULL;root->rchild=NULL;for(int i=1;i<n;i++){m=new BiNode<T>;m->data=a[i];m->rchild=NULL;m->lchild=NULL;InsertTree(root,m);}}template <class T>BiNode<T>* BiSortTree<T>::InsertTree(BiNode<T> *p, BiNode<T> *s) {if(p==NULL) return s;else{if(s->data>p->data){p->rchild=InsertTree(p->rchild, s);p->rchild->parent=p;}else{p->lchild=InsertTree(p->lchild, s);p->lchild->parent=p;}return p;}}template<class T>void BiSortTree<T>::chazhao(T k,BiNode<T> *p){BiNode<T> *q;int i=0;if(p==NULL)cout<<"无此结点"<<endl;else{if(k<p->data)chazhao(k,p->lchild);if(k>p->data)chazhao(k,p->rchild);if(k==p->data){if(p->rchild==NULL){if(p->rchild==NULL&&p->lchild==NULL) {if(p->parent->rchild==p)p->parent->rchild=NULL;elsep->parent->lchild=NULL;delete p;}if(p->lchild!=NULL&&p->rchild==NULL) {if(p->parent->rchild==p)p->parent->rchild=p->lchild;elsep->parent->lchild=p->lchild;delete p;}}else{if(p->lchild==NULL){if(p->parent->rchild==p)p->parent->rchild=p->rchild;elsep->parent->lchild=p->rchild;delete p;}elseif(p->lchild!=NULL){q=p->lchild;while(q->rchild!=NULL){q=q->rchild;i++;}if(i==0)q->parent->lchild=NULL;elseq->parent->rchild=NULL;q->lchild=p->lchild;q->rchild=p->rchild;q->parent=p->parent;if(p!=root){if(p->parent->lchild==p)p->parent->lchild=q;elsep->parent->rchild=q;}elseroot=q;delete p;}}}}}template <class T>void BiSortTree<T>::dDLR(BiNode<T> *rt) {if (rt){cout<<rt->data<<ends;dDLR(rt->lchild);dDLR(rt->rchild);}}template<class T>void BiSortTree<T>::find(T k){chazhao(k,root);}template<class T>void BiSortTree<T>::Release(BiNode<T> *p) {if(p!=NULL){if(p->lchild==NULL&&p->rchild==NULL) delete p;else{Release(p->lchild);Release(p->rchild);}}}template<class T>BiSortTree<T>::~BiSortTree(){Release(root);}template<class T>void BiSortTree<T>::display(){dDLR(root);}int main(){int b[8]={10,8,13,6,9,12,15,16};BiSortTree<int> tree(b,8);tree.find(16);tree.display();return 0;}三、实验心得（含上机中所遇问题的解决办法，所使用到的编程技巧、创新点及编程的心得）。