数据结构实验8查找的算法_实验8查找算法应用
数据结构实验8查找的算法由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“实验8查找算法应用”。
8.1 实现顺序查找的算法
一，实验目的
1.熟悉掌握各种查找方法，深刻理解各种查找算法及其执行的过程； 2.学会分析各种查找算法的性能。
二，实验内容
8.1 实现顺序查找的算法
编写一个程序，输出在顺序表{3,6,2,10,1,8,5,7,4,9}中采用顺序查找法查找关键字5的结果。
8.2 实现折半查找算法
编写一个程序，输出在顺序表{1,2,3,4,5,6,7,8,9,10}中采用折半查找方法查找关键字9的结果。要求：（1）用非递归方法；（2）用递归方法。8.3 实现二叉排序树的基本运算
编写一个程序实现二叉排序树的基本运算，并在此基础上完成如下功能：（1）由{4,9,0,1,8，6,3,5,2,7}创建一个二叉排序树bt；
（2）判断bt是否为一棵二叉排序树（提示：在遍历过程中检查是否符合二叉排序树定义）；
（3）采用非递归方法查找关键字为6的结点，并输出其查找路径（提示：查找过程中保留经过的结点信息，找到后顺序输出之）。8.4 实现哈希表的相关运算
编写一个程序，实现哈希表的相关运算，并在此基础上完成如下功能：
（1）建立{16,74,60,43,54,90,46,31,29,88,77}哈希表A[0…12]，哈希函数为H(k)=key % 11，并采用线性探测法解决冲突。输出哈希表；（2）在上述哈希表中查找关键字为29的记录；
（3）在上述哈希表中删除关键字为77的记录，再将其插入，然后输出哈希表。要求：输出格式
哈希地址：0 1 2 ………..12 关键字值：……………………
三，源代码及结果截图
8.1 //实现顺序查找的算法 #include #define MAXL 100
//定义表中最多记录个数 typedef int KeyType;typedef int InfoType;typedef struct {
KeyType key;//KeyType为关键字的数据类型 InfoType data;//其他数据 } NodeType;
typedef NodeType SeqList[MAXL];
//顺序表类型 int Search(SeqList R,int n,KeyType k)//顺序查找算法
{ int i=0;while(i
printf(“%d ”,R[i].key);
i++;
//从表头往后找
} if(i>=n)
return-1;else {
printf(“%d”,R[i].key);
return i;} } void main(){ SeqList R;int n=10;KeyType k=5;InfoType a[]={3,6,2,10,1,8,5,7,4,9};int i;for(i=0;i
//建立顺序表
R[i].key=a[i];printf(“查找结果：n”);if((i=Search(R,n,k))!=-1)
printf(“n元素%d的位置是:%d”,k,i);else
printf(“n元素%d不在表中n”,k);printf(“n”);}
8.2
//实现折半查找算法 #include #define MAXL 100
//定义表中最多记录个数
typedef int KeyType;typedef char InfoType[10];typedef struct { KeyType key;
//KeyType为关键字的数据类型
InfoType data;
//其他数据 } NodeType;typedef NodeType SeqList[MAXL];
//顺序表类型
int BinSearch1(SeqList R,int n,KeyType k)//非递归二分查找算法 { int low=0,high=n-1,mid,count=0;while(low
{ mid=(low+high)/2;printf(“第%d
次
查
找
:
在[%d,%d]
中
查
找
到R[%d]:%dn”,++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
次
查
找
:
在[%d,%d]
中
查
找
到
元
素printf(“R[%d]:%dn”,++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;int a[]={1,2,3,4,5,6,7,8,9,10},i,n=10;for(i=0;i
//建立顺序表
printf(“用非递归方法:n”);if((i=BinSearch1(R,n,k))!=-1)printf(“元素%d的位置是%dn”,k,i);else printf(“元素%d不在表中n”,k);printf(“用递归方法:n”);if((i=BinSearch2(R,k,0,9,0))!=-1)printf(“元素%d的位置是%dn”,k,i);else printf(“元素%d不在表中n”,k);
8.3 //实现二叉排序树的基本运算 #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;
return 1;
}
else
{
if(k==T->key)
return 0;
else if(kkey)
return BSTInsert(T->lchild, k);
else
return BSTInsert(T->rchild, k);
} } //定义二叉排序树的创建算法 BTNode *createBST(int k[],int n){
BTNode *T;
T=NULL;
for(int i=0;i
BSTInsert(T,k[i]);
}
return T;} //判断是否为二叉排序树 Status Judge(BTNode *&T){
} //定义二叉排序树的查找算法
BTNode *BSTSearch(BTNode *&T,int k){
if(T==NULL)
return NULL;
else if(T==NULL)return 1;else if((T>T->lchild)&&(Trchild)){
} else return 0;Judge(T->lchild);Judge(T->rchild);
{
printf(“%d ”,T->key);
if(T->key==k)
return T;
else if(kkey)
{
return BSTSearch(T->lchild, k);
}
else
{
return BSTSearch(T->rchild, k);
}
} } void main(){
int a[50]={4,9,0,1,8,6,3,5,2,7};
BTNode *bt=createBST(a,10);
if(Judge(bt)==0)cout
}
8.4 //实现哈希表的相关运算 #include #define MaxSize 100
//定义最大哈希表长度 #define NULLKEY 0
//定义空关键字值
#define DELKEY-1
//定义被删关键字值
typedef int KeyType;
//关键字类型
typedef char * InfoType;//其他数据类型 typedef struct { KeyType key;//关键字域
InfoType data;
//其他数据域 int count;
//探查次数域
} HashTable[MaxSize];
//哈希表类型
void InsertHT(HashTable ha,int *n,KeyType k,int p)中 {
//将关键字k插入到哈希表
int i,adr;adr=k % p;if(ha[adr].key==NULLKEY || ha[adr].key==DELKEY)//x[j]可以直接放在哈希表中
} void CreateHT(HashTable ha,KeyType x[],int n,int m,int p)//创建哈希表 {
} else {
} n++;i=1;do { adr=(adr+1)% p;i++;
//i记录x[j]发生冲突的次数
//发生冲突时采用线性探查法解决冲突 ha[adr].key=k;ha[adr].count=1;} while(ha[adr].key!=NULLKEY && ha[adr].key!=DELKEY);ha[adr].key=k;ha[adr].count=i;
{ int i,n1=0;for(i=0;i
//哈希表置初值
{
ha[i].key=NULLKEY;
ha[i].count=0;
}
} int SearchHT(HashTable ha,int p,KeyType k){
int i=0,adr;adr=k % p;while(ha[adr].key!=NULLKEY && ha[adr].key!=k){
} if(ha[adr].key==k)return adr;
//查找失败
//查找成功 i++;
//采用线性探查法找下一个地址
//在哈希表中查找关键字k for(i=0;i
} return-1;int DeleteHT(HashTable ha,int p,int k,int *n)//删除哈希表中关键字k {
} void DispHT(HashTable ha,int n,int m)
//输出哈希表 {
float avg=0;int i;printf(“ 哈希表地址:t”);for(i=0;i
} else
//在哈希表中未找到该关键字 ha[adr].key=DELKEY;n--;
//哈希表长度减1
//在哈希表中找到该关键字
return 1;return 0;
printf(“ n”);
printf(“ 哈希表关键字:t”);
for(i=0;i
if(ha[i].key==NULLKEY || ha[i].key==DELKEY)printf(“
”);
//输出3个空格
else printf(“ %3d”,ha[i].key);printf(“ n”);printf(“ 搜索次数:t”);for(i=0;i
if(ha[i].key==NULLKEY || ha[i].key==DELKEY)printf(“
”);
//输出3个空格
else printf(“ %3d”,ha[i].count);printf(“ n”);
for(i=0;i
} if(ha[i].key!=NULLKEY && ha[i].key!=DELKEY)avg=avg+ha[i].count;avg=avg/n;printf(“ 平均搜索长度ASL(%d)=%gn”,n,avg);
void main(){
int x[]={16,74,60,43,54,90,46,31,29,88,77};int n=11,m=13,p=13,i,k=29;HashTable ha;CreateHT(ha,x,n,m,p);printf(“n”);DispHT(ha,n,m);printf(“ 查找关键字29:n”);i=SearchHT(ha,p,k);if(i!=-1)printf(“ ha[%d].key=%dn”,i,k);else printf(“ 未找到%dn”,k);k=77;printf(“ 删除关键字%dn”,k);DeleteHT(ha,p,k,&n);DispHT(ha,n,m);i=SearchHT(ha,p,k);if(i!=-1)printf(“ ha[%d].key=%dn”,i,k);else printf(“ 未找到%dn”,k);
} printf(“ 插入关键字%dn”,k);InsertHT(ha,&n,k,p);DispHT(ha,n,m);printf(“n”);
四，实验小结
1、通过本次实验，加深了我对查找表的认识。
2、有序表的查找之折半查找：前提必须是有序表，性能只有在均匀分布的时候才是最优的。
3、二叉排序树查找：通过一系列的查找和插入过程形成的树。之所以叫做排序树，因为按照中序遍历可得一个有序的序列。
