实验十一散列表实验.doc

查找技术实验十一 散列表实验1. 实验目的 掌握散列查找的基本思想； 掌握闭散列表的构造方法； 掌握线性探测处理冲突的方法； 掌握散列技术的查找性能。2. 实验内容 对于给定的一组整数和散列函数，采用线性探测法处理冲突构造散列表； 设计查找算法，验证查找性能。3. 实现提示 假设散列表长为m，散列函数为除留余数法，即H(key)=key % p，m和p在主函数中由用户从键盘输入，待散列的数据也由用户从键盘输入，算法如下：int CreatHash(int ht , int m) for (i=0; ik; while (k!=#) /#作为结束标志 j=k % p; if (htj=0) htj=k; /没有发生冲突，直接存入 else i=(j+1) % m; while (hti!=0 & i!=j) if (hti= =0) hti=k; /发生冲突，向后探测若干次后存入 break; else i=(i+1) % m; /向后探测一个位置 if (i= =j) throw 溢出; cink; 闭散列表构造算法 假设在已建立的散列表中进行静态查找，在查找过程中设置计数器count统计元素的比较次数，查找算法如下：int HashSearch(int ht , int m, int k) j=k % p; count=0; i=j;while (hti!=0 ) if (+count & hti= =k) /发生冲突，比较若干次查找成功 cout查找成功，比较次数为：countendl; return i; i=(i+1) % m; /向后探测一个位置 if (i= =j) break;cout查找不成功，比较次数为：countendl;闭散列表的查找算法HashSearch选作内容：闭散列表和开散列表查找性能的比较1. 问题描述对于给定的一组关键码，分别采用线性探测法和拉链法建立散列表，并且在这两种方法构建的散列表中查找关键码k，比较两种方法的时间性能和空间性能。2. 基本要求 用线性探测法处理冲突建立闭散列表； 用拉链法处理冲突建立开散列表； 设计合理的测试数据，比较二者的查找性能。3. 设计思想对于给定的一组关键码和相同的散列函数，如果处理冲突时采用的方法不同，建立散列表也不同，通常查找性能也不同。采用线性探测法处理冲突建立闭散列表以及在闭散列表上进行查找的算法在教材中已做过实验，下面讨论拉链法处理冲突的方法。首先定义开散列表的存储结构。同义词子表中的结点即为单链表中的结点，其结点结构定义如下（本章假定数据域均为整数）：struct Node int data; Node *next;每个同义词子表由一个头指针指示，将所有头指针存储在一个一维数组中，形成开散列表。假设散列表长为m，则开散列表ht定义如下：Node *htm;采用拉链法建立开散列表，需将待散列的每个关键码按散列地址存储到相应的同义词子表中，算法如下：Node *HashTable(Node *ht , int m, int r , int n) for (i=0; im; i+) hti=NULL; /开散列表初始化 for (i=0; idata=ri;j=ri % p; s-next= htj; /头插法插入同义词子表htj=s; 开散列表的建立算法HashTable在开散列表上进行查找，只需到相应的同义词子表中进行查找，为记载与关键码的比较次数，设置计数器count。算法如下：Node *HashSearch2(Node *ht , int m, int k) j=H(k); p=htj; count=0;while (p & +count & p-data!=k)p=p-next;if (p-data= =k) cout查找成功，比较次数为