数据结构-实验8查找的算法.doc

-
. z
实现顺序查找的算法
实验目的
，深刻理解各种查找算法及其执行的过程；
2
int BinSearch1(SeqList R,int n,KeyType k) //非递归二分查找算法
{
int low=0,high=n-1,mid,count=0;
while (low<=high)
{
mid=(low+high)/2;
printf("第%d次查找:在[%d,%d]中查找到元素R[%d]:%d\n",++count,low,high,mid,R[mid].key);
if (R[mid].key==k) //查找成功返回
return mid;
if (R[mid].key>k) //继续在R[low..mid-1]中查找
high=mid-1;
else
low=mid+1; //继续在R[mid+1..high]中查找
}
return -1;
}
int BinSearch2(SeqList R,KeyType k,int low,int high,int count) //递归二分查找算法
{
int mid;
if(low<=high)
{
mid=(low+high)/2;
printf("第%d次查找:在[%d,%d]中查找到元素R[%d]:%d\n",++count,low,high,mid,R[mid].key);
if (R[mid].key==k) //查找成功返回
return mid;
else if (R[mid].key>k) //继续在R[low..mid-1]中查找
BinSearch2(R, k,low,mid-1,count);
else
BinSearch2(R, k,mid+1,high,count); //继续在R[mid+1..high]中查找
}
else return -1;
}
void main()
{
SeqList R;
KeyType k=9;
-
. z
int a[]={1,2,3,4,5,6,7,8,9,10},i,n=10;
for (i=0;i<n;i++) //建立顺序表
R[i].key=a[i];
printf("用非递归方法:\n");
if ((i=BinSearch1(R,n,k))!=-1)
printf("元素%d的位置是%d\n",k,i);
else
printf("元素%d不在表中\n",k);
printf("用递归方法:\n");
if ((i=BinSearch2(R,k,0,9,0))!=-1)
printf("元素%d的位置是%d\n",k,i);
else
printf("元素%d不在表中\n",k);
}

//实现二叉排序树的根本运算
#include<> //EOF,NULL
#include<> //atoi( )
#include<> //cout,cin
typedef int Status;
typedef struct BTNode
{
int key;
struct BTNode *lchild;
struct BTNode *rchild;
}BTNode;
//定义二叉排序树插入结点的算法
int BSTInsert(BTNode *&T,int k)
{
if(T==NULL)
{
T=(BTNode *)malloc(sizeof(BTNode));
T->lchild=T->rchild=NULL;
T->key=k;
-
. z
return 1;
}
else
{
if(k==T->key)
return 0;