内容发布更新时间 : 2024/12/25 16:20:03星期一 下面是文章的全部内容请认真阅读。
实验七 查找
一、实验目的
1、掌握查找表、动态查找表、静态查找表和平均查找长度的概念。 2、掌握线性表中顺序查找和折半查找的方法。
3、学会哈希函数的构造方法,处理冲突的机制以及哈希表的查找。
二、实验内容和要求
1. 静态查找表技术
依据顺序查找算法和折半查找算法的特点,对下面的两个查找表选择一个合适的算法,设计出完整的C源程序。并完成问题:
查找表1 : { 8 ,15 ,19 ,26 ,33 ,41 ,47 ,52 ,64 ,90 } ,查找key = 41 查找表2 : {12 ,76 ,29 ,15 ,62 ,35 ,33 ,89 ,48 ,20 } ,查找key =35 查找key=41的比较次数: 查找key=35的比较次数: ? 算法实现代码
1
2、哈希表的构造与查找
/* 采用开放地址法构造哈希表*/ #include
#define DUPLICATE -1
2
#define TRUE 1 #define FALSE 0
typedef struct{ /*哈希表元素结构*/ int key; /*关键字值*/ int flag; /*是否存放元素*/ }ElemType;
typedef struct {
ElemType data[MAXSIZE];
int count; /*元素个数*/
int sizeindex; /*当前哈希表容量*/ }HashTable;
int d1[15]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14}; /*线性探测序列*/
int d2[15]={0,1,-1,2*2,-2*2,3*3,-3*3,4*4,-4*4,5*5,-5*5,6*6,-6*6,7*7,-7*7}; /*二次探测序列*/
void dataset(int ds[],int *len);
int InsertHash(HashTable *H,int e,int d[]);
int CreateHash(HashTable *H,int ds[],int len,int d[]); int SearchHash(HashTable *H, int e,int d[]); void menu(); /*输入查找表*/
void dataset(int ds[],int *len){ int n,m; n=0;
printf(\查找表输入:\
while(scanf(\以输入一个非整数作为结束*/ ds[n]=m; n++; }
*len=n; }
/*计算哈希地址,插入哈希表*/
int InsertHash(HashTable *H,int e,int d[]){ int k,i=1; k=e%P;
while(H->data[k].flag==TRUE||k<0){ k=(e%P+d[i])%MAXSIZE;i++; if(i>=15)
return ERROR; }
H->data[k].key=e; H->data[k].flag=TRUE; H->count++;
3