数据结构-实验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 <stdio.h>
#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<n && R[i].key!=k)
{
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<n;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 <stdio.h>
#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<=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;
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);
}
8.3
//实现二叉排序树的基本运算
#include<stdio.h> //EOF,NULL
#include<stdlib.h> //atoi( )
#include<iostream.h> //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(k<T->key)
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<=n-1;i++){
BSTInsert(T,k[i]);
}
return T;
}
//判断是否为二叉排序树
Status Judge(BTNode *&T)
{
if(T==NULL)
return 1;
else if((T>T->lchild)&&(T<T->rchild))
{
Judge(T->lchild);
Judge(T->rchild);
}
else return 0;
}
//定义二叉排序树的查找算法
BTNode *BSTSearch(BTNode *&T,int k)
{
if(T==NULL)
return NULL;
else
{ printf("%d ",T->key);
if(T->key==k)
return T;
else if(k<T->key)
{
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<<"bt不是二叉排序树"<<endl;
else cout<<"bt是二叉排序树"<<endl;
cout<<"查找关键字6的查找路径:"<<endl;
BTNode *t=BSTSearch(bt,6);
cout<<endl;
}
8.4
//实现哈希表的相关运算
#include <stdio.h>
#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]可以直接放在哈希表中
{
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++;
}
void CreateHT(HashTable ha,KeyType x[],int n,int m,int p) //创建哈希表
{
int i,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);
}
int SearchHT(HashTable ha,int p,KeyType k) //在哈希表中查找关键字k
{
int i=0,adr;
adr=k % p;
while (ha[adr].key!=NULLKEY && ha[adr].key!=k)
{
i++; //采用线性探查法找下一个地址
adr=(adr+1) % p;
}
if (ha[adr].key==k) //查找成功
return adr;
else //查找失败
return -1;
}
int DeleteHT(HashTable ha,int p,int k,int *n) //删除哈希表中关键字k
{
int adr;
adr=SearchHT(ha,p,k);
if (adr!=-1) //在哈希表中找到该关键字
{
ha[adr].key=DELKEY;
n--; //哈希表长度减1
return 1;
}
else //在哈希表中未找到该关键字
return 0;
}
void DispHT(HashTable ha,int n,int m) //输出哈希表
{
float avg=0;
int i;
printf(" 哈希表地址:\t");
for (i=0;i<m;i++)
printf(" %3d",i);
printf(" \n");
printf(" 哈希表关键字:\t");
for (i=0;i<m;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<m;i++)
if (ha[i].key==NULLKEY || ha[i].key==DELKEY)
printf(" "); //输出3个空格
else
printf(" %3d",ha[i].count);
printf(" \n");
for (i=0;i<m;i++)
if (ha[i].key!=NULLKEY && ha[i].key!=DELKEY)
avg=avg+ha[i].count;
avg=avg/n;
printf(" 平均搜索长度ASL(%d)=%g\n",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=%d\n",i,k);
else
printf(" 未找到%d\n",k);
k=77;
printf(" 删除关键字%d\n",k);
DeleteHT(ha,p,k,&n);
DispHT(ha,n,m);
i=SearchHT(ha,p,k);
if (i!=-1)
printf(" ha[%d].key=%d\n",i,k);
else
printf(" 未找到%d\n",k);
printf(" 插入关键字%d\n",k);
InsertHT(ha,&n,k,p);
DispHT(ha,n,m);
printf("\n");
}
四，实验小结
1、通过本次实验，加深了我对查找表的认识。
2、有序表的查找之折半查找：前提必须是有序表，性能只有在均匀分布的时候才是最优的。
3、二叉排序树查找：通过一系列的查找和插入过程形成的树。之所以叫做排序树，因为按照中序遍历可得一个有序的序列。
-
数据结构查找实验报告
实验题91设计一个程序exp91cpp输出在顺序表36210185749中采用顺序方法找关键字5的过程程序如下文件名exp91cp…
-
数据结构实验报告 实验五 查找算法
昆明理工大学信息工程与自动化学院学生实验报告201201学年第一学期课程名称数据结构开课实验室年月日一实验内容查找算法其中线性表的…
-
数据结构查找实验报告
实验报告课程名称实验项目数据结构查找姓名xx专业班级学号网络工程网络132130402xxxx计算机科学与技术学院实验教学中心20…
-
数据结构查找算法实验报告
100410528孙晨添数据结构实验报告实验第四章实验简单查找算法一需求和规格说明查找算法这里主要使用了顺序查找折半查找二叉排序树…
-
《数据结构》实验报告查找
实验四查找一实验目的1掌握顺序表的查找方法尤其是折半查找方法2掌握二叉排序树的查找算法二实验内容1234建立一个顺序表用顺序查找的…
-
数据结构实验报告-静态查找表中的查找
数据结构实验实验一静态查找表中的查找一、实验目的：1、理解静态查找表的概念2、掌握顺序查找和折半查找算法及其实现方法3、理解顺序查…
-
数据结构上机实验报告
实验一线性表的基本操作实验目的学习掌握线性表的顺序存储结构链式存储结构的设计与操作对顺序表建立插入删除的基本操作对单链表建立插入删…
- 数据结构图实验报告
-
焦作数据结构实验报告
河南省高等教育自学考试实验报告册计算机及应用专业本科段数据结构姓名李威威准考证号所属地市焦作市实验地点焦作大学实验实训中心实验日期…
-
数据结构实验报告
河南省高等教育自学考试实验报告册计算机及应用专业本科段数据结构姓名准考证号所属地市实验地点实验日期实验总成绩指导教师签名实验单位实…
-
五种查找算法总结
一、顺序查找条件：无序或有序队列。原理：按顺序比较每个元素，直到找到关键字为止。时间复杂度：O(n)二、二分查找（折半查找）条件：…