文档介绍：该【数据结构-实验8查找的算法】是由【久阅文学】上传分享，文档一共【14】页，该文档可以免费在线阅读，需要了解更多关于【数据结构-实验8查找的算法】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。数据结构-实验8查找的算法

实验目的
,深刻理解各种查找算法及其执行的过程;
。
实验内容

编写一个程序,输出在顺序表{3,6,2,10,1,8,5,7,4,9}中采用顺序查找法查找关键字5的结果。

编写一个程序,输出在顺序表{1,2,3,4,5,6,7,8,9,10}中采用折半查找方法查找关键字9的结果。要求:(1)用非递归方法;(2)用递归方法。

编写一个程序实现二叉排序树的基本运算,并在此基础上完成如下功能:
(1)由{4,9,0,1,8,6,3,5,2,7}创建一个二叉排序树bt;
(2)判断bt是否为一棵二叉排序树(提示:在遍历过程中检查是否符合二叉排序树定义);
(3)采用非递归方法查找关键字为6的结点,并输出其查找路径(提示:查找过程中保留经过的结点信息,找到后顺序输出之)。

编写一个程序,实现哈希表的相关运算,并在此基础上完成如下功能:
(1)建立{16,74,60,43,54,90,46,31,29,88,77}哈希表A[0…12],哈希函数为H(k)=key%11,并采用线性探测法解决冲突。输出哈希表;
(2)在上述哈希表中查找关键字为29的记录;
(3)在上述哈希表中删除关键字为77的记录,再将其插入,然后输出哈希表。
要求:输出格式
哈希地址:012………..12
关键字值:……………………
源代码及结果截图

//实现顺序查找的算法
#include<>
#defineMAXL100 //定义表中最多记录个数
typedefintKeyType;
typedefintInfoType;

//实现折半查找算法
#include<>
#defineMAXL100 //定义表中最多记录个数
typedefintKeyType;
typedefcharInfoType[10];
typedefstruct
{
KeyTypekey; //KeyType为关键字的数据类型
InfoTypedata; //其他数据
}NodeType;
typedefNodeTypeSeqList[MAXL]; //顺序表类型
intBinSearch1(SeqListR,intn,KeyTypek)//非递归二分查找算法
{
intlow=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) //查找成功返回
returnmid;
if(R[mid].key>k) //继续在R[low..mid-1]中查找
high=mid-1;
else
low=mid+1; //继续在R[mid+1..high]中查找
}
return-1;
}
intBinSearch2(SeqListR,KeyTypek,intlow,inthigh,intcount)//递归二分查找算法
{
intmid;
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) //查找成功返回
returnmid;
elseif(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]中查找
}
elsereturn-1;
}
voidmain()
{
SeqListR;
KeyTypek=9;
inta[]={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
typedefintStatus;
typedefstructBTNode
{
intkey;
structBTNode*lchild;
structBTNode*rchild;
}BTNode;
//定义二叉排序树插入结点的算法
intBSTInsert(BTNode*&T,intk)
{
if(T==NULL)
{
T=(BTNode*)malloc(sizeof(BTNode));
T->lchild=T->rchild=NULL;
T->key=k;
return1;
}
else
{
if(k==T->key)
return0;
elseif(k<T->key)
returnBSTInsert(T->lchild,k);
else
returnBSTInsert(T->rchild,k);
}
}
//定义二叉排序树的创建算法
BTNode*createBST(intk[],intn)
{
BTNode*T;
T=NULL;
for(inti=0;i<=n-1;i++){
BSTInsert(T,k[i]);
}
returnT;
}
//判断是否为二叉排序树
StatusJudge(BTNode*&T)
{
if(T==NULL)
return1;
elseif((T>T->lchild)&&(T<T->rchild))
{
Judge(T->lchild);
Judge(T->rchild);
}
elsereturn0;
}
//定义二叉排序树的查找算法
BTNode*BSTSearch(BTNode*&T,intk)
{
if(T==NULL)
returnNULL;
else
{printf("%d",T->key);
if(T->key==k)
returnT;
elseif(k<T->key)
{
returnBSTSearch(T->lchild,k);
}
else
{
returnBSTSearch(T->rchild,k);
}
}
}
voidmain()
{
inta[50]={4,9,0,1,8,6,3,5,2,7};
BTNode*bt=createBST(a,10);
if(Judge(bt)==0)cout<<"bt不是二叉排序树"<<endl;
elsecout<<"bt是二叉排序树"<<endl;
cout<<"查找关键字6的查找路径:"<<endl;
BTNode*t=BSTSearch(bt,6);
cout<<endl;
}

//实现哈希表的相关运算
#include<>
#defineMaxSize100 //定义最大哈希表长度
#defineNULLKEY0 //定义空关键字值
#defineDELKEY -1 //定义被删关键字值
typedefintKeyType; //关键字类型
typedefchar*InfoType; //其他数据类型
typedefstruct
{
KeyTypekey; //关键字域
InfoTypedata; //其他数据域
intcount; //探查次数域
}HashTable[MaxSize]; //哈希表类型
voidInsertHT(HashTableha,int*n,KeyTypek,intp)//将关键字k插入到哈希表中
{
inti,adr;
adr=k%p;
if(ha[adr].key==NULLKEY||ha[adr].key==DELKEY) //x[j]可以直接放在哈希表中
{
ha[adr].key=k;
ha[adr].count=1;
}
else //发生冲突时采用线性探查法解决冲突
{
i=1; //i记录x[j]发生冲突的次数
do
{
adr=(adr+1)%p;
i++;
}while(ha[adr].key!=NULLKEY&&ha[adr].key!=DELKEY);
ha[adr].key=k;
ha[adr].count=i;
}
n++;
}
voidCreateHT(HashTableha,KeyTypex[],intn,intm,intp)//创建哈希表
{
inti,n1=0;
for(i=0;i<m;i++) //哈希表置初值
{
ha[i].key=NULLKEY;
ha[i].count=0;
}
for(i=0;i<n;i++)
InsertHT(ha,&n1,x[i],p);