1、数据结构数据结构课程设计课程设计 1 哈希表的操作设计报告哈希表的操作设计报告 一一 目的目的 通过此次课程设计，让学生充分掌握对哈希表的有关操作，例如除留余数法的运用， 处理冲突的三个办法：线性探测再散列，二次探测再散列，连地址法等。加深学生对于哈 希表这种独特存储方式（区别于线性存储和链式存储）的理解，和几种算法之间的优越性 的体会。 二二 需求分析需求分析 1 1、功能需求功能需求 用户能够自定义输入单词，存入哈希表里； 用户能够对当前哈希表进行管理。操作内容包括：查看当前哈希表、搜索某个单 词、插入任意单词、删除表中某个单词、查看当前表的平均搜索长度、置空当前哈希表。 程序有良好的交互
2、界面，有操作提示和出错提示，方便用户使用和进出入程序。 2 2、程序约束程序约束 哈希表的散列方法为除留余数法，处理冲突的办法为线性探测在散列。 使用 C/C+语言编写，程序模块化设计。 三三 概要设计概要设计 1 1、模块设计模块设计 程序分为主程序模块和哈希表类定义模块，主程序存放在 main.app 中，哈希表类存放 在 HashTable.h 头文件中。 主程序模块 用于数据和 DOS 用户界面的初始化，主函数 mai()内部定义子函数 function()，调用哈 希表类中的各个功能函数。 哈希表类定义 Calculate(string s) 单词 key 值计算函数，类友元 形参
3、s 传送输入的单词。由于单词为 string 型，不方便直接拿来参与取余数计算，故用 计算函数求出一个 key 来，同时可以减少冲突（字母相同的单词 key 有可能不同）。 FindPos(int key,string value) 地址查找函数，类成员 key 传送计算出的单词的关键值，value 传送输入的单词，下同。此函数为查找、插 入、删除等函数提供地址搜索服务。 Search(int key,string value) 查找函数，类成员 Insert(string value) 插入函数，类成员 Remove(int key,string value) 删除函数，类成员 makeEm
4、pty() 置空哈希表函数，类成员 数据结构数据结构课程设计课程设计 2 getInfo(int address) 获取某个地址中元素的信息，类成员 形参 address 是哈希表中某元素的地址（数组下标），通过 key % divitor 得到 getSize(HashTable HT) 获取哈希表存储情况，类友员 ASL(HashTable HT) 平均查找长度计算函数，类友元 四四 详细设计详细设计 1 1、主要主要功能实现功能实现 全局定义：#define DefaultSize 30 数组最大容量 divitor 取余除数，设为 29（30 的最大质数） 单词 key 计算： int
5、 Calculate(string s) /key 计算函数：word 前 5 个字符的 ASCII 码 + 单词长度 /不足 5 个字符的 word，用所有字符的 ASCII 码 + 单词长度 int k=0,len; len=s.length(); if(lenc; switch(c) case 1: for(int i=0;iword; if(HT.Search(Calculate(word),word)=true) coutword; HT.Insert(word); break; case 4: coutcount; if(countword; if(HT.Insert( word )=-1) i-; /输入有误，后退一步再输入一次 do function(); while(10);
