基于链地址法的哈希表类模板设计与实现

《基于链地址法的哈希表类模板设计与实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、学院专业学生姓名学号设计题目基于链地址法的哈希表类模板设计与实现内容及要求：实现哈希表类模板，数据元素可以是char,int,float等多种数据类型，包括以下功能：（1）实现哈希表的建立，散列函数采用除留余数法；（2）使用链地址法处理冲突；（3）实现哈希表元素的插入；（4）实现哈希表元素的删除；（5）实现哈希表的查找；（6）将上述功能作为类的成员函数实现，编写主函数测试上述查找功能。进度安排：第17周：分析题目，查阅课题相关资料，进行类设计、算法设计；第18周：程序的设计、调试与实现；第19周：程序测试与分析，撰写课程设计报告，进行答辩验收。指

2、导教师（签字）：年月日学院院长（签字）年月日课程设计任务书目录1需求分析32算法基本原理33类设计44详细设计64.1类的接口设计64.2类的实现74.3主函数设计105DOS界面程序运行结果及分析115.1程序运行结果115.2运行结果分析136基于MFC的图形界面程序开发136.1基于MFC的图形界面程序设计136.2程序测试256.3MFC程序编写总结287参考文献291需求分析（1）对于保存在顺序容器的无序列表来说，顺序查找的时间效率为O(n),对于有序列表，二分查找可以提供O（log2n）的查找时间。最理想的情况是，我们可以设计一个容器

3、，它访问数据的时间复杂度为O（1）。如果这样，访问某数据的时间就和容器中其他数据没有关系了。此时，这样的结构我们称为哈希表，其中，表中的元素都有唯一的键与之对应。（2）哈虚函数根据键求出索引值，并利用索引值来定位表中的某项数据：……键--值0定位器“哈希函数”1键2iin-2n-12算法基本原理（1）除留余数法原理取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。即H（key）=keyMODp,p<=m如：关键字分别为：13293564778796105当p=7,m=8时，根据哈希函数H（key）=keyMODp得H（key）=key

4、MOD7，计算结果如下表：关键字13293564778796105哈希地址61010350（2）链地址法处理冲突原理将所有关键字为同义词的记录存储在同一线性链表中。假设某哈希函数产生的哈希地址在区间（0，m-1）上，则设立一个指针型变量H[m]，其每个分量的初始状态都是空指针。凡哈希地址为i的记录都插入到头指针H[i]的链表中。在链表中的插入位置可以在表头也可以在表尾，也可以在中间，以保持同义词在同一线性链表中按关键字有序。如以（1）中的关键字为例，则链地址法处理冲突可形象地表示如下：105∧7735064∧2912∧87∧34∧96∧513∧6

5、3类设计类模板就是设计一种类的框架，可以适用不同的数据类型，只是一种类的抽象，因此，利用类模板可以针对不同的数据类型定义出具有共性的一组类。定义形式如下：template<类型名参数名1，类型名参数名2，…>　class类名　{　　类声明体；　}；与函数模板类似，通过使用类模板可以使得所定义的类中的某些数据成员某些成员函数的参数某些成员函数的返回值都可以是任意的数据类型（包括基本类型和自定义类型）。所以，可以通过类模板将程序所处理的对象的类型参数化，从而使得同一段程序可用于处理多种不同类型的对象，提高了程序的抽象层次和可重用性。由于哈希表中的数据

6、元素可以是char,int,float等多种数据类型，因此可以使用类模板来构造本程序的实现框架。具体定义如下：templateclasshash{public:typedefnode*linknode;typedefnodeln;hash();~hash();voidinsert(t1key,t2data);voidremove(t1key);t2query(t1key);voiddisplay();linknode*array;private:intfunc(char*);intfu

7、nc(string);intfunc(int);intfunc(char);intfunc(float);stringtype;};同时，程序中也定义了结构体的模板，具体如下：templatestructnode{t1key;t2data;node*next;};该类模板经过实例化后得到的模板类的UML图表示如下：hash-type:string-array:linknode*-linknode:node*-ln:node+hash()+~hash()+func(string):int

8、+func(int):int+func(char):int+func(float):int+func(char*):int+query(