实验十 查找技术验证实验报告

栈特殊线性表班级：计算机11-1学号：姓名：成绩：_________实验十查找技术验证实验实验目的(1)掌握折半查找算法的基本思想;(2)掌握折半查找算法的实现方法;(3)掌握折半查找算法的时间性能;(4)掌握二叉排序树定义和特性;(5)掌握二叉排序树的建立方法;(6)实现基于二叉排序树的查找技术;(7)掌握二叉排序树的查找性能.实验内容(1)对给定的有序数组（假设长度为n），查找数组中与给定值k相等的元素。(2)①对给定的一组无序序列，建立一棵二叉排序树；②对建立的二叉排序树实现查找操作。设计与编码折半查找验证#include<iostream>usingnamespacestd;intBinSearch1(intr[],intn,intk){intlow=1; inthigh=n; intcount=0; while(low<=high) { intmid=(low+high)/2; count++; if(k<r[mid-1]) high=mid-1; else if(k>r[mid-1])low=mid+1; else { cout<<"比较次数是："<<count; return0; } } return0;}intmain(){ intn,b,a[100];cout<<"*********************"<<endl; cout<<"请输入数组的个数："; cin>>n; cout<<"请输入各个数的值:"; for(inti=0;i<n;i++) cin>>a[i]; cout<<"请输入你要查找的值："; cin>>b; BinSearch1(a,n,b); cout<<endl;cout<<"*********************"<<endl; return0;}㈡二叉排序树的建立#include<iostream>usingnamespacestd;structBiNode{intdata;BiNode*lchild,*rchild;};classBiSortTree{public: voiddesplayTree(void);//显示这个树BiSortTree(inta[],intn);//建立查找集合a[n]的二叉排序树~BiSortTree(){};//析构函数，释放二叉排序树中所有结点，同二叉链表的析构函数voidInsertBST(BiNode*&root,BiNode*s);//在二叉排序树中插入一个结点sBiNode*searchTree(intk);//在树中查找一个值private: BiNode*root;//二叉排序树（即二叉链表）的根指针voidShowTree(BiNode*&root);//显示BiNode*SearchBST(BiNode*&root,intk);//查找值为k的结点};//二叉排序树插入算法voidBiSortTree::InsertBST(BiNode*&root,BiNode*s){ if(root==NULL) root=s; elseif(s->data<root->data) InsertBST(root->lchild,s); elseInsertBST(root->rchild,s);}//构造二叉排序树BiSortTree::BiSortTree(intr[],intn){root=NULL; for(inti=0;i<n;i++) { BiNode*s=newBiNode; s->data=r[i]; s->lchild=NULL; s->rchild=NULL; InsertBST(root,s); }}//二叉排序树查找算法BiNode*BiSortTree::searchTree(intk){ returnSearchBST(root,k);}BiNode*BiSortTree::SearchBST(BiNode*&root,intk){if(root==NULL)returnNULL;elseif(root->data==k){returnroot;}elseif(k<root->data){returnSearchBST(root->lchild,k);}else{ returnSearchBST(root->rchild,k);}}//显示二叉排序树voidBiSortTree::desplayTree(void){ ShowTree(root); cout<<endl;}voidBiSortTree::ShowTree(BiNode*&root){ if(root!=NULL){ ShowTree(root->lchild);cout<<root->data<<"\t";ShowTree(root->rchild);} else return;}voidmenu(){ cout<<"查找技术验证实验"<<endl;cout<<"*********************"<<endl; cout<<"1.中序遍历："<<endl; cout<<"2.查找元素："<<endl;cout<<"3.退出："<<endl;cout<<"*********************"<<endl;}intmain(){ intn,b,k;inta[100]; cout<<"**********************************"<<endl;cout<<"请输入二叉排序树的元素的个数：";cin>>n;cout<<"请输入二叉排序树的各个元素的值：";for(inti=0;i<n;i++) { cin>>b;a[i]=b; } BiSortTreec(a,n); menu(); intflag=1; while(flag) { inti; cout<<"请输入你所需要的选项："; cin>>i; switch(i) { case1: { cout<<"中序遍历为："<<endl; c.desplayTree(); break; } case2: { cout<<"请输入二叉顺序树要查找的元素："; cin>>k; if(c.searchTree(k)==NULL) { cout<<"你所要查找的元素无法在树中找到..."<<endl; } else { cout<<"你所要查找的元素已在查找到了..."<<endl; } break; } case3: { flag=0;