《数据结构》数据结构查找

1、实验十数据结构查找一、实验目的1、掌握查找表、动态查找表、静态查找表和平均查找长度的概念。2、掌握线性表中顺序查找和折半查找的方法。3、学会哈希函数的构造方法，处理冲突的机制以及哈希表的查找。二、实验预习说明以下概念1、顺序查找：2、折半查找：3、哈希函数：4、冲突及处理：三、实验内容和要求1.静态查找表技术依据顺序查找算法和折半查找算法的特点， 设计出完整的C源程序。并完成问题： 查找表 1 : 8，15，19，26，33查找表 2 :12， 67，29，15，62查找key=41的算法：顺序查找查找key=35的算法：折半查找顺序查找算法算法实现代码#include#define N 10

2、int arrayN = 12,76,29,15,62,35,33,89,48,20;int search(int array,int key) for(int i=0;iN;i+)if(key=arrayi)return i;return 0;int main()4135对下面的两个查找表选择一个合适的算法，47，52，64，90 ，查找 key = 41 33，89，48，20 ，查找 key =35 比较次数：5比较次数：5int a;a=search(array,35);if(a)printf（-查找的关键字35已经找到！它在表中的下标为：dn，a）;elseprintf(该关键字不存

3、在！n);return 0;折半查找算法算法实现代码#include#define N 10int arrayN = 8,15,19,26,23,41,47,52,64,90;int search(int key,int array)int low=0;int mid;int high=N-1;int ley=41;while(lowkey)high=mid-1;elselow=mid+1;return 0;int main()int a;a=search(41,array);if(a)printf(-关键字：41已找到！该关键字在表中的下标为：dn，a);elseprintf(该关键字不存在

4、！n);return 0;五、教师评语2、哈希表的构造与查找/*采用开放地址法构造哈希表*/#include#include#define MAXSIZE 25#define P 13#define OK 1#define ERROR 0#define DUPLICATE -1#define TRUE 1#define FALSE 0typedef struct /*哈希表元素结构*/int key; /*关键字值*/int flag; /*是否存放元素*/ElemType;typedef struct ElemType dataMAXSIZE;int count; /*元素个数 */int

5、sizeindex; /*当前哈希表容量*/HashTable;int d115 = 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14; /*线性探测序列 */int d215 = 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 Se

6、archHash(HashTable *H, int e,int d);void menu();/*输入查找表*/void dataset(int ds,int *len)int n,m;n=0;printf(n查找表输入：)；while(scanf(%d”,&m)=1) /*以输入一个非整数作为结束*/dsn=m;n+;*len=n;/*计算哈希地址，插入哈希表*/int InsertHash(HashTable *H,int e,int d)int k,i=1;k=e%P;while(H-datak.flag=TRUE|k=15)return ERROR;H-datak.key=e;H-d

7、atak.flag=TRUE;H-count+;return OK;/*构造哈希表*/int CreateHash(HashTable *H,int ds,int len,int d) int i;for(i=0;icount=MAXSIZE)return ERROR;return OK;/*初始化哈希表*/void InitHash(HashTable *H)int i;for(i=0;idatai.key=0;H-datai.flag=FALSE;/*在哈希表中查找*/int SearchHash(HashTable *H, int e,int d)int k,i=1;k=e%P;whil

8、e(H-datak.key!=e)k=(e%P+di)%MAXSIZE;i+;if(i=15)return -1;return k;/*演示菜单*/void menu()int choice;int *p;HashTable h;h.count=0;h.sizeindex=MAXSIZE;int aMAXSIZE=0;int i,n,e;dataset(a,&n); /*建立查找表*/getchar();printf(n)；doprintf(n哈希查找演示n);printf(n1.线性探测构造哈希表n);printf(n2.二分探测构造哈希表n);printf(n3.退出n);printf(n

9、 输入选择：)；scanf(%d”,&choice);if(choice=1)p=d1;else if(choice=2)p=d2;elsereturn;InitHash(&h);/*初始化哈希表*/if(!(i=CreateHash(&h,a,n,p) /*构造哈希表 */ printf(n哈希表构造失败！ n);else if(i=DUPLICATE)printf(n哈希表具有重复关键字！ n);elseprintf(n 哈希表：n)；for(i=0;i* I* ll Hirnv U I* iniIij I H jnl mjL4 Ai-lMfJLF Lflri LI I；M b者曲E=F王

10、日参II E用旎1E 耳村#include定义函数库可以便于可以使用后面的函数语句；#define N 10定义大N为10代表数组的最大个数为10个数；int arrayN = 12,76,29,15,62,35,33,89,48,20;int search(int array,int key)定义搜索内容包括以查找的一维数组、关键字；for(int i=0;iN;i+)for ()函数循环进对数组的所有数据进行查找，使得数组可以全部被查询;if (key=arrayi)判断如果查询的关键字是否等于一维数组中的值；return i;如果等于返回值i；return 0;反之算法结束；int ma

11、in ()函数调用定义以下的值使得以下的值可以执行以上的语句；int a;定义一个整型值a；a=search(array,35);将2赋值于搜索对象35的下标；if(a)如果a满足上述i的判断条件；printf(-查找的关键字35已经找到！它在表中的下标为%dn，a);输出查找成功提示语；else否则；printf(-该关键字不存在！n)；输出查找失败提示语return 0;并且算法结束；实验半折查找41：输入输出结果囱I C:WINDOWS诂y3temW2cmcl.exE关键字，41已找到！该美魂字在表中的卜标为:5 请按任意键继续一一一#include定义函数库以便于后面的函数语句可以使用

12、；#define N 10定义一维数组的最大长度为N并且N的值为10；int arrayN = 8,15,19,26,23,41,47,52,64,90;定义一维数组的 10个数值；int search(int key, int array 口)定义搜索查询的关键字和查询的一维数组；int low=0;定义初始为0；int mid;定义中间值为整型；int high=N-1;定义数值高的值进行向前进一位；int ley=41;定义需要查找的值为41；while (lowkey)否则如果一维数组的中间值的大于所查询的关键字；high=mid-1;高的值赋值于中间值向前进一位；else否则；low=mid+1;将低值赋值于中间值前进一个值；return 0;返回值0算法结束；int main ()函数调用使得下面定义的数值可