实验十一 散列表实验

《实验十一 散列表实验》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、查找技术实验十一散列表实验1.实验目的⑴掌握散列查找的基本思想；⑵掌握闭散列表的构造方法；⑶掌握线性探测处理冲突的方法；⑷掌握散列技术的查找性能。2.实验内容⑴对于给定的一组整数和散列函数，采用线性探测法处理冲突构造散列表；⑵设计查找算法，验证查找性能。3.实现提示假设散列表长为m，散列函数为除留余数法，即H(key)=key%p，m和p在主函数中由用户从键盘输入，待散列的数据也由用户从键盘输入，算法如下：intCreatHash(intht[],intm){for(i=0;i

2、;　cin>>k;while(k!='#')//#作为结束标志{j=k%p;if(ht[j]=0)ht[j]=k;//没有发生冲突，直接存入else{i=(j+1)%m;while(ht[i]!=0&&i!=j){if(ht[i]==0){ht[i]=k;//发生冲突，向后探测若干次后存入break;}elsei=(i+1)%m;//向后探测一个位置}if(i==j)throw"溢出";}cin>>k;}}闭散列表构造算法假设在已建立的散列表中进行静态查找，在查找过程中设置计数器count统计元素的比较次数，查找算法如下

3、：查找技术intHashSearch(intht[],intm,intk){j=k%p;count=0;i=j;while(ht[i]!=0){if(++count&&ht[i]==k){//发生冲突，比较若干次查找成功cout<<"查找成功，比较次数为："<

4、.问题描述对于给定的一组关键码，分别采用线性探测法和拉链法建立散列表，并且在这两种方法构建的散列表中查找关键码k，比较两种方法的时间性能和空间性能。2.基本要求⑴用线性探测法处理冲突建立闭散列表；⑵用拉链法处理冲突建立开散列表；⑶设计合理的测试数据，比较二者的查找性能。3.设计思想对于给定的一组关键码和相同的散列函数，如果处理冲突时采用的方法不同，建立散列表也不同，通常查找性能也不同。采用线性探测法处理冲突建立闭散列表以及在闭散列表上进行查找的算法在教材中已做过实验，下面讨论拉链法处理冲突的方法。首先定义开散列表的存储结

5、构。同义词子表中的结点即为单链表中的结点，其结点结构定义如下（本章假定数据域均为整数）：structNode{intdata;Node*next;查找技术};每个同义词子表由一个头指针指示，将所有头指针存储在一个一维数组中，形成开散列表。假设散列表长为m，则开散列表ht定义如下：Node*ht[m];采用拉链法建立开散列表，需将待散列的每个关键码按散列地址存储到相应的同义词子表中，算法如下：Node*HashTable(Node*ht[],intm,intr[],intn){for(i=0;i

6、ULL;//开散列表初始化for(i=0;idata=r[i];j=r[i]%p;s->next=ht[j];//头插法插入同义词子表ht[j]=s;}}开散列表的建立算法HashTable在开散列表上进行查找，只需到相应的同义词子表中进行查找，为记载与关键码的比较次数，设置计数器count。算法如下：Node*HashSearch2(Node*ht[],intm,intk){j=H(k);p=ht[j];count=0;while(p&&++count&&p->data!=k)

7、p=p->next;if(p->data==k){cout<<"查找成功，比较次数为"<