| 《数据结构》实验报告七：查找 | 您所在的位置：网站首页 › 数据结构数组的顺序存储和实现实验体会 › 《数据结构》实验报告七：查找 |
《数据结构》实验报告七：查找
|
一、实验目的
1、掌握查找表、动态查找表、静态查找表和平均查找长度的概念。 2、掌握线性表中顺序查找和折半查找的方法。 3、学会哈希函数的构造方法，处理冲突的机制以及哈希表的查找。 二、实验预习说明以下概念 1、顺序查找： 顺序查找又叫线性查找，是最基本的查找方法。 查找思路：从查找表的第一个（或最后一个）数据元素开始，逐个将数据元素的关键字和给定的关键字进行比较，如果存在某个数据元素的关键字和给定关键字相等，则查找成功，返回该数据元素相关信息；如果直到最后一个（或第一个）数据元素，还未找到和给定关键字相等的数据元素，则查找失败，表中没有所查的数据。 2、折半查找： 折半查找也叫二分查找、对分查找。折半查找的前提是查找表中所有数据元素的关键字按照递增或递减有序排列。 查找思路：假设查找表中数据元素关键字按照递增有序排列，设置一个指针 low 指向查找表中关键字最小的位置，设置一个指针 high 指向查找表中关键字最大的位置，再设置一个指针 mid 指向查找表中间位置。 ① mid=(low+high)/2。 ② 将给定的关键字 k 与 mid 位置的关键字 m 比较： 若k=m，查找成功，返回相关数据元素信息。 若km，则low=mid+1，重复以上操作（从①开始） ③ 如果直至 low>high 还未查找成功，则查找失败。 3、哈希函数： 哈希函数又叫散列函数、杂凑函数，是散列方法中使用的转换函数。 在使用散列方法存储查找表中的数据元素时，选取一个函数，依照该函数和关键字计算数据元素的存储位置，并按此位置存放，这个函数就是哈希函数。 同样的，在查找时，由同一个哈希函数对给定的关键字 k 进行计算得到地址，再将 k 与该地址中数据元素的关键字进行比较，确认是否查找成功。 哈希函数就是记录的存储位置与关键字之间的对应关系：Loc(element.i)=Hash(key.i) 4、冲突及处理： 冲突就是在散列表中使用哈希函数，根据关键字计算存储地址时，不同的关键码映射到了同一个散列地址，这些具有相同函数值的多个关键字叫做同义词。 处理方法：开放地址法、链地址法、再散列法、建立一个公共溢出区…… （1）开放地址法（开地址法） 基本思想：发生冲突时就寻找下一个空的散列地址(即地址加上某个增量)，若找到空地址，则将数据存入。 例如：除留余数法 Hi=( Hash(key)+di )mod m ，di为增量序列（m为查找表中元素个数） 开放地址法寻找空地址常用方法： ① 线性探测法：di为1，2，3，……，m-1 的线性序列。 ② 二次探测法：di为1*1，- 1*1，2*2，- 2*2，……，q*q 的二次序列。 ③伪随机探测法：di为伪随机数序列。 （2）链地址法（拉链法） 基本思想：相同散列地址（同义词）的数据元素链成一个单链表，m个散列地址就设置m个单链表，然后用一个数组存储m个单链表的表头指针，形成一个动态的结构。 根据数据元素的关键字计算散列函数值（即地址），若该地址对应的链表为空，则该地址直接存储该数据元素结点；若该地址对应的链表非空，则将该元素插入此链表（前插法/后插法）。 三、实验内容和要求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 的算法： 折半查找法 比较次数： 3 查找 key=35 的算法： 顺序查找法 比较次数： 5 选择依据：可以看出查找表1中的数据是按递增有序排列的，所以可以选择折半查找法；而查找表2中的数据是无序的，看不出什么规律，所以选择顺序查找法。 顺序查找算法实现代码 #include #define MAX_NUM 50 //查找表中数据元素最大数量 typedef struct{ int key; //关键字域 }ElemType; //定义数据元素类型 typedef struct{ ElemType elem[MAX_NUM]; //从下标为1的分量开始存储(0位置设置监视哨) int length; //表长 }SST; //Sequence Search Table-顺序查找表 /*顺序查找算法,ST为目标查找表,key为给定的关键字*/ int Seq_Search(SST ST,int key) { ST.elem[0].key = key; //设置监视哨 int i; for(i=ST.length;ST.elem[i].key != key;i--) { ; //for循环内为空语句 } return i; //返回0:查找失败;返回值>0:查找成功 } int main() { int i,n,key; printf("请输入查找表中记录个数n：\n"); scanf("%d",&n); SST ST; ST.length = n; printf("\n请输入查找表中数据记录：\n"); for(i=1;i0:查找成功 } /*折半查找的递归算法*/ //ST为目标查找表,key为给定的关键字,low为查找区间的开始下标,high为查找区间的结束下标,*/ int Bin_Search_R(SST ST,int key,int low,int high) { if(low > high) return 0; //查找失败 int mid; mid = (low+high)/2; if(key == ST.elem[mid].key) return mid; if(key < ST.elem[mid].key) Bin_Search_R(ST,key,low,high-1); if(key > ST.elem[mid].key) Bin_Search_R(ST,key,low+1,high); } int main() { int i,n,key; printf("请输入查找表中记录个数n：\n"); scanf("%d",&n); SST ST; ST.length = n; printf("\n请输入查找表中数据记录：\n"); for(i=1;idata[k].flag==TRUE || kdata[k].key = e; H->data[k].flag = TRUE; H->count++; //插入成功,哈希表长度+1 return OK; //返回1 } /*构造哈希表*/ int CreateHash(HashTable *H,int ds[],int len,int d[]){ //ds数组存放查找表的关键字,len为记录个数,d数组指向线性或二次探测序列 int i; for(i=0;icount >= MAXSIZE) return ERROR; //记录个数超过MAXSIZE,返回0 } return OK; //创建成功,返回1 } /*初始化哈希表*/ void InitHash(HashTable *H){ int i; for(i=0;idata[i].key = 0; H->data[i].flag = FALSE; } } /*在哈希表中查找*/ int SearchHash(HashTable *H,int e,int d[]){ //e为查找的关键字,d数组指向线性或二次探测序列(查找和插入应使用同一个探测序列) int k,i=1; k = e%P; while(H->data[k].key!=e || k=15) return -1; //探测序列中所有值都尝试过仍未找到关键字e,说明哈希表中不存在该关键字,查找失败,返回-1 } return k; //查找成功,返回该关键字在哈希表中的位置 } /*演示菜单*/ void menu(){ int choice; int *p; HashTable h; h.count=0; h.sizeindex = MAXSIZE; int a[MAXSIZE]={0}; int i,n,e; dataset(a,&n); /*建立查找表*/ getchar(); //消耗回车键 printf("\n"); do{ printf("\n----哈希查找演示----\n"); printf("\n1.线性探测构造哈希表\n"); printf("\n2.二分探测构造哈希表\n"); printf("\n3.退出\n"); printf("\n输入选择："); scanf("%d",&choice); if(choice == 1) p = d1; //p指向线性探测序列 else if(choice == 2) p = d2; //p指向二次探测序列 else return; InitHash(&h); /*初始化哈希表*/ i = CreateHash(&h,a,n,p); /*构造哈希表*/ if( !i ) printf("\n哈希表构造失败！\n"); else if(i == DUPLICATE) printf("\n哈希表具有重复关键字！\n"); else { printf("\n哈希表：\n"); for(i=0;i …… } printf("重复关键字：%d，在哈希表中下标为：%d",H->data[k].key,k); //添加代码 return k; //查找成功,返回该关键字在哈希表中的位置 }运行后得到以下结果：
容易看出 68 在查找表中是没有重复的，但是却显示重复，而且下标还是个负数，哈希表的下标范围应该是 0 ~ MAXSIZE-1，所以负数下标指示的关键字不属于哈希表。 那为什么会查找到哈希表以外的数据呢？因为在插入关键字和查找关键字时哈希地址的计算没有统一。 InsertHash函数中，对地址 k 是有限制的：当计算出的地址 kdata[k].flag==TRUE || k k = (e%P+d[i])%MAXSIZE; i++; if(i>=15) return -1; } return k; //查找成功,返回该关键字在哈希表中的位置 } |
【本文地址】