【数据结构算法】查找.ppt

数据结构算法
Visual C++
侯识忠等编著
中国水利水电出版社
第八章查找
8、0 二分查找法(递归调用)
//二分查找法(递归调用)
#include<>
#include<>
#include<>
double a[10]={,,,,,,,,,};
void binsrch(int s,int r,double x)
{int m;
m=(s+r)/2;
if(a[m]==x)
{cout<<x<<"在序列中找到!\n";}
else if(s>r)
{cout<<x<<"在序列中未找到!\n";
();();exit(-1);}
else if(x>a[m])
binsrch(m+1,r,x);
else binsrch(s,m-1,x);
}
单击此处运行程序
void main()
{cout<<"erfenfa1运行结果:\n";
double x=;
int s=0,r=9;
cout<<"输入x:";cin>>x;
cout<<"查找结果:\n";
binsrch(s,r,x);
();();}
8、1 二分查找法(非递归调用)
#include<>
#include<>
#include<>
void binsrch(int a[],int n,int x)
{int mid,top=0,bot=n-1,find=0,m=0;
do {
m=m+1;
mid=(top+bot)/2;
if(a[mid]==x)
{cout<<x<<"在序列中找到!\n";find=1;}
else if(x<a[mid]) bot=mid-1;
else if(x>a[mid]) top=mid+1;
}while((top<=bot)&&(find==0));
if(find==0) cout<<x<<"在序列中未找到!\n";
cout<<"查找次数:"<<m<<endl;}
单击此处运行程序
void main()
{cout<<"erfenfa2运行结果:\n";
int b[]={1,3,5,7,9,10,12,15,17,19};
int x=9,n=10;
cout<<"输入要查找的x:";cin>>x;
cout<<"查找结果:\n";
binsrch(b,n,x);
();();}
8、2 二叉排序树的类定义与实现
//
#include <>
#include <>
#include<>
//二叉树的链式存储结构表示
typedef struct BinaryTree
{ int data;
struct BinaryTree *l;
struct BinaryTree *r;
}*BiTree,BiNode;
//二叉树的类定义
class BiSearchT
{private:
BiTree root;
public:
//构造函数
BiSearchT():root(NULL) {}
//构造二叉链表表示的二叉树T
int CreateSubTree(BiTree &t,int *all,int i);
//先序遍历二叉树T
int PreOrderTraverse(BiTree t,int (*Visit)(int e));
//中序遍历二叉树T
int InOrderTraverse(BiTree t,int (*Visit)(int e));
//插入算法
int InsertBST(BiTree *t,int e);
//在二叉排序树中删除一个节点
void Delete(BiTree *p);
//二叉排序树的删除
bool DeleteBST(BiTree *t,int key);
//二叉排序树上的查找递归算法
bool SearchBST(BiTree t,int key,BiTree f,BiTree *p);
};
//二叉排序树的类实现
//构造二叉链表表示的二叉树T
int BiSearchT::CreateSubTree(BiTree &t,int *all,int i)
{if((all[i]==0)||i>16)
{t=NULL;
return 1;}
t=(