杂凑表的设计与实现 数据结构 哈希 hash

一、题目序号及题目内容

7.杂凑表的设计与实现(难度系数：1.2)

问题描述：

针对本班的人名设计一个杂凑表，数据表的长度为 50~80 个记录；分析平均查找长度，完成相

应的建表和查表程序，设计直观的界面显示杂凑表的内容。

基本要求：

人名用汉语拼音表示，例如“陈伟津”表示为“chen weijin”。人名的长度不超过 19 个字符。字符

的取码方法可直接利用 C 语言中的 toascii 函数。

每一组的每一个字符都利用 toascii 函数转成 ASCII 码，只取该 ASCII 码的个位数，并按每组字符

的先后顺序组成 3 组 6 位的整数，不满六位的后面补零。比如字符串“ chen weijin”分组转 ASCII 后

为“941029”，“ 156500”和“000000”。再将所得的三个 6 位整数分别加上姓名串的串长，最后将所

得 的 三 个 6 位 数 相 加 。 即

941029+11=941040，156500+11=156511，000000+11=000011，941040+156511+000011=1097562。

所得 1097562 这个数就是关键字。

利用以上办法获得关键字，再使用哈希类提供的除留余数法和线性探查法，将关键字插入哈希

表并可以进行搜索操作。

三、算法思想

KeyType CharToNum(char name[NAMELENGHT]) //将 name 转为整数

{

for(k=0;k<6;k++,j++)

{

temp+=toascii(name[j])%10*pow(10,5-k);

}

temp+=+nameLen;

//将最多 NAMELENGHT 位的姓名拆分为 3 组 6 位的串，每位字符取其 ASCII 码的个位数，每组组成一

个 6 位的整数加上名字的长度，再将这 3 个 6 位整数相加得到结果关键字

}

for(i=0;i<NAMELENGHT;i++)

if(!infile)

{ cout<<"文件读取失败"<<endl;

abort(); //文件读取失败直接退出

}

char name[NAMELENGHT]="\0";

int j;

KeyType result=0;

cout<<"哈希表内容："<<endl;

while(infile.getline (name,NAMELENGHT))//逐行读取文件

{ result=CharToNum(name);//获取名字转换后的数字（关键字）

cout<<setiosflags(ios::left)<<setw(7)<<j<<"ht[]="<<item.key<<endl;//设置对齐，不足补空格

}

}

cout<<"--------------------"<<endl<<endl;

infile.close();

}

四、实现的功能的描述

hash.cpp 包含以下操作：

int GetNameLen(char name[NAMELENGHT])//返回当个姓名的长度

KeyType CharToNum(char name[NAMELENGHT])//将姓名从汉语拼音转为整数，即求关键字

int HashTable::Find(const DataType &x)const//哈希表的查找

int HashTable::Insert(const DataType &x,int pos)//哈希表的插入

int HashTable::GetPos(int x); //输出找到的元素的所在位置

五、数据结构的说明

Data 域存储关键字，info 域存储状态标识，position 存储姓名在文件中的位置。

六、主程序的流程图和主要功能模块流程图及说明