数据结构
课程设计报告
计算机科学与教育软件学院计算机系07级网络工程4班
郭盛初
（学号：0726850049）（班内序号：03）
2009年10月
f一、题目序号及题目内容
7杂凑表的设计与实现难度系数：12问题描述：针对本班的人名设计一个杂凑表，数据表的长度为5080个记录；分析平均查找长度，完成相应的建表和查表程序，设计直观的界面显示杂凑表的内容。基本要求：人名用汉语拼音表示，例如“陈伟津”表示为“che
weiji
”。人名的长度不超过19个字符。字符的取码方法可直接利用C语言中的toascii函数。
二、解决的思路
由于中国人的名字多以三个字居多，而且单字的拼音长度不超过6位，比如zhua
g（庄），所以三个字的人名串长度最大为18，在姓与名之间加空格刚好19个。将全班人名用汉语拼音表示之后存入一个
ametxt文件，每一个人名占用一行，方便输入、修改跟读取。构造哈希表时，只需利用文件操作，即可获得人名信息，无需逐个重新录入。为了构造哈希关键字，对19个字符中截取前18个，再将18个字符分成3组，每组各6个字符。每一组的每一个字符都利用toascii函数转成ASCII码，只取该ASCII码的个位数，并按每组字符的先后顺序组成3组6位的整数，不满六位的后面补零。比如字符串“che
weiji
”分组转ASCII后为“941029”“156500”和“000000”，。再将所得的三个6位整数分别加上姓名串的串长，最后将所得的三个6位数相加。即94102911941040，15650011156511，00000011000011，9410401565110000111097562。所得1097562这个数就是关键字。利用以上办法获得关键字，再使用哈希类提供的除留余数法和线性探查法，将关键字插入哈希表并可以进行搜索操作。
三、算法思想
KeyTypeCharToNumchar
ameNAMELENGHT将
ame转为整数i
ti0j0k0i
t
ameLe
ameLe
GetNameLe
ame单个名字的长度KeyTypetemp0fori0j0i3ifork0k6kjtemptoascii
amej10pow105ktemp
ameLe
将最多NAMELENGHT位的姓名拆分为3组6位的串，每位字符取其ASCII码的个位数，每组组成一个6位的整数加上名字的长度，再将这3个6位整数相加得到结果关键字fori0iNAMELENGHTi
f
amei0清空名字数组，恢复原始状态，防止上一操作影响下一操作retur
tempvoidBuildHashHashTablemyTablei
tli
e创建哈希查找表ifstreami
file