c++基于链地址法哈希表类模板设计与实现.docxVIP

学院信息科学与工程专业通信工程学生姓名姜智峰学号1203060127设计题目基于链地址法的哈希表类模板设计与实现内容及要求：  实现哈希表类模板，数据元素可以是char, int, float等多种数据类型， 包括以下功能： （1） 实现哈希表的建立，散列函数采用除留余数法； （2） 使用链地址法处理冲突； （3） 实现哈希表元素的插入； （4） 实现哈希表元素的删除； （5） 实现哈希表的查找； （6） 将上述功能作为类的成员函数实现，编写主函数测试上述查找功能。进度安排： 第17周：分析题目，查阅课题相关资料，进行类设计、算法设计； 第18周：程序的设计、调试与实现； 第19周：程序测试与分析，撰写课程设计报告，进行答辩验收。指导教师（签字）： 年 月 日学院院长（签字） 年 月 日课 程 设 计 任 务 书 目录  TOC \o 1-3 \h \z \u  HYPERLINK \l _Toc313135992 1 需求分析  PAGEREF _Toc313135992 \h 3  HYPERLINK \l _Toc313135993 2 算法基本原理  PAGEREF _Toc313135993 \h 3  HYPERLINK \l _Toc313135994 3 类设计  PAGEREF _Toc313135994 \h 3  HYPERLINK \l _Toc313135995 4 详细设计  PAGEREF _Toc313135995 \h 3  HYPERLINK \l _Toc313135996 4.1 类的接口设计  PAGEREF _Toc313135996 \h 3  HYPERLINK \l _Toc313135997 4.2 类的实现  PAGEREF _Toc313135997 \h 3  HYPERLINK \l _Toc313135998 4.3 主函数设计  PAGEREF _Toc313135998 \h 3  HYPERLINK \l _Toc313135999 5 DOS界面程序运行结果及分析  PAGEREF _Toc313135999 \h 3  HYPERLINK \l _Toc313136000 5.1 程序运行结果  PAGEREF _Toc313136000 \h 3  HYPERLINK \l _Toc313136001 5.2运行结果分析  PAGEREF _Toc313136001 \h 3  HYPERLINK \l _Toc313136002 6 基于MFC的图形界面程序开发  PAGEREF _Toc313136002 \h 3  HYPERLINK \l _Toc313136003 6.1 基于MFC的图形界面程序设计  PAGEREF _Toc313136003 \h 3  HYPERLINK \l _Toc313136004 6.2 程序测试  PAGEREF _Toc313136004 \h 3  HYPERLINK \l _Toc313136005 6.3 MFC程序编写总结  PAGEREF _Toc313136005 \h 3  HYPERLINK \l _Toc313136006 7 参考文献  PAGEREF _Toc313136006 \h 3  1 需求分析 （1）对于保存在顺序容器的无序列表来说，顺序查找的时间效率为O(n),对于有序列表，二分查找可以提供O（ QUOTE log2n log2n）的查找时间。最理想的情况是，我们可以设计一个容器，它访问数据的时间复杂度为O（1）。如果这样，访问某数据的时间就和容器中其他数据没有关系了。此时，这样的结构我们称为哈希表，其中，表中的元素都有唯一的键与之对应。 （2）哈虚函数根据键求出索引值，并利用索引值来定位表中的某项数据： …… 键--值 0 定位器 “哈希函数” 1 键 2 i i n-2 n-1 2 算法基本原理 除留余数法原理 取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。即H（key）=keyMODp, p=m 如：关键字分别为：13 29 35 64 7787 96105当p