《哈希表》项目实验报告[范文]

第一篇：《哈希表》项目实验报告[范文]

《哈希表》项目实验报告

1、实验名称

哈希表问题

2、小组成员

刘艳宁、邓芳益；

3、主要内容和步骤：

（1）分析问题描述，明确问题目标

对于一个哈希表，它是通过哈希算法，然后将数据按照哈希算法所得到的哈希地址存入到哈希表中。所以对于一个哈希表，要了解它的存储方式、哈希表的冲突处理、数据的输入、数据的追加、哈希表的判空、哈希表清空、数据的查找（2）分析问题数据描述

[数据描述]首先分析哈希表的构造方法：除留余数法

取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。H(key)=key MOD p(p<=m);//哈希表的存储方法

但是由于java中已经嵌入了哈希表，所以直接调用java中的哈希表： Import java.uilt.HashMap//调用java中的哈希表函数；

（3）确定算法思路，准确描述算法 [算法描述]首先运用java里面的哈希表；

import java.util.Scanner;//调用java里面的Scanner供用户进行数据的输入 import java.util.HashMap；//调用java哈希表

根据公式：H(key)=key MOD p(p<=m)用输入的关键字来与哈希表的总长度来进行求余运算，然后将求得的余数存入到哈希表相应的位置中

对于哈希表的查找：

则根据哈希表的除留余数法然后进行数据的查找；当ASL为1时时最理想的，因为只需要查找一次，如果第一次没有查找到，则在先前的位置上加一进行查找，直到查找到数据为止然后返回。（4）运行数据记录

输入：学号：1000 姓名：张三 输入：学号：1001 姓名：李四

输出哈希表数据，然后进行判空，查找等操作（5）实验效果图示

4、实验总结：（心得体会、处理结果、存在的问题、建议和意见等）

心得体会：如果要实现哈希表的各个操作，首先要了解哈希表的存储方式；其次就是算法的构造上面，该程序是直接调用java中的hashmap，所以在算法上程序构造相对的比较简单。

存在的问题：不能够直观的输出哈希表的存储方式。

第二篇：软件综合实习-哈希表

哈希表的设计实验报告

1．实验题目

针对自己班级体中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。

2．需求分析

假设人名为中国姓名的汉语拼音模式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用链表法处理冲突。测试数据：

①输入的形式和输入值的范围：输入30个人的姓名拼音，即30个字符串。

②输出的形式:将结果输出，程序自动计算查找长度的总数和平均查找长度，然后用户可以根据需求进行查找操作。

③程序所能达到的功能：在哈希函数确定的前提下用各种不同处理冲突的方法，考察平均查找长度的变化和造好的哈希表中关键字的聚集性。

3．概要设计

#define HASH_LEN 50 //哈希表的长度 #define M 47 #define NAME_NO 30 //人名的个数 typedef struct NAME {char *py;//名字的拼音 int k;//拼音所对应的整数 }NAME;NAME NameList[HASH_LEN];typedef struct hterm //哈希表 {char *py;//名字的拼音 int k;//拼音所对应的整数 int si;//查找长度 }HASH;void InitNameList()void FindList()void Display()4．详细设计

1{for(int i=0;i

int s0=0;for(int r=0;r<20;r++)//求出姓名的拼音所对应的整数(关键字)s0+=name[r];

int sum=1;int adr=s0 % M;//使用哈希函数 int d=adr;

if(HashList[adr].k==s0)//分3种情况进行判断

printf(”n姓名:%s 关键字:%d 查找长度为: 1“,HashList[d].py,s0);else if(HashList[adr].k==0)printf(”无该记录!“);else { int g=0;do { d=(d+s0%10+1)%M;//伪散列 sum=sum+1;if(HashList[d].k==0){ printf(”无记录!“);g=1;} if(HashList[d].k==s0){ printf(”n姓名:%s 关键字:%d 查找长度为:%d“,HashList[d].py,s0,sum);g=1;} }while(g==0);} void main(){ InitNameList();CreateHashList();while(1){ printf(”nn“);printf(” 1.显示哈希表n“);printf(” 2.查找n“);printf(” 3.退出n“);err: char ch1;scanf(”%c“,&ch1);if(ch1=='1')Display();else if(ch1=='2')FindList();else if(ch1=='3')return;else { printf(”n请输入正确的选择!“);goto err;} } } 5．调试分析

测试数据：随机输入的30个人的姓名拼音

测试过程：输入30个人的姓名拼音，观察输出结果，并进行查找操作 测试结果： 6．使用说明

1）进入界面选择1显示哈希表，选择2为查找，选择3退出 2）再输入名字查找，再退出 7．测试结果

8.附录

#include #include #include //#include #define HASH_LEN 50 //哈希表的长度 #define M 47 #define NAME_NO 30 //人名的个数 typedef struct NAME { char *py;//名字的拼音

int k;//拼音所对应的整数 }NAME;NAME NameList[HASH_LEN];

typedef struct hterm //哈希表 { char *py;//名字的拼音

int k;//拼音所对应的整数 int si;//查找长度 }HASH;HASH HashList[HASH_LEN];void InitNameList(){ NameList[0].py=”chenghongxiu“;NameList[1].py=”yuanhao“;NameList[2].py=”yangyang“;NameList[3].py=”zhanghen“;NameList[4].py=”chenghongxiu“;NameList[5].py=”xiaokai“;NameList[6].py=”liupeng“;NameList[7].py=”shenyonghai“;NameList[8].py=”chengdaoquan“;NameList[9].py=”ludaoqing“;NameList[10].py=”gongyunxiang“;NameList[11].py=”sunzhenxing“;NameList[12].py=”sunrongfei“;NameList[13].py=”sunminglong“;NameList[14].py=”zhanghao“;NameList[15].py=”tianmiao“;NameList[16].py=”yaojianzhong“;NameList[17].py=”yaojianqing“;NameList[18].py=”yaojianhua“;NameList[19].py=”yaohaifeng“;NameList[20].py=”chengyanhao“;NameList[21].py=”yaoqiufeng“;NameList[22].py=”qianpengcheng“;NameList[23].py=”yaohaifeng“;NameList[24].py=”bianyan“;NameList[25].py=”linglei“;NameList[26].py=”fuzhonghui“;NameList[27].py=”huanhaiyan“;NameList[28].py=”liudianqin“;NameList[29].py=”wangbinnian“;char *f;int r,s0;for(int i=0;i

for(r=0;*(f+r)!= '';r++)//方法：将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字 s0=*(f+r)+s0;NameList[i].k=s0;} } void CreateHashList(){ for(int i=0;i

HashList[d].k=NameList[i].k;HashList[d].py=NameList[i].py;HashList[d].si=sum+1;}i++;} void FindList(){ printf(”nn请输入姓名的拼音: “);//输入姓名 char name[20]={0};scanf(”%s“,name);

int s0=0;for(int r=0;r<20;r++)//求出姓名的拼音所对应的整数(关键字)s0+=name[r];

int sum=1;int adr=s0 % M;//使用哈希函数 int d=adr;

if(HashList[adr].k==s0)//分3种情况进行判断

printf(”n姓名:%s 关键字:%d 查找长度为: 1“,HashList[d].py,s0);else if(HashList[adr].k==0)printf(”无该记录!“);else { int g=0;do { d=(d+s0%10+1)%M;//伪散列 sum=sum+1;if(HashList[d].k==0){ printf(”无记录!“);g=1;} if(HashList[d].k==s0){ printf(”n姓名:%s 关键字:%d 查找长度为:%d“,HashList[d].py,s0,sum);g=1;} }while(g==0);} } void Display(){ printf(”nn地址t关键字tt搜索长度tH(key)tt拼音 n“);//显示的格式 for(int i=0;i<15;i++){ printf(”%d “,i);printf(”t%d “,HashList[i].k);printf(”tt%d “,HashList[i].si);printf(”tt%d “,(HashList[i].k)%M);printf(”t %s “,HashList[i].py);printf(”n“);} // getch();for(i=15;i<30;i++){ printf(”%d “,i);printf(”t%d “,HashList[i].k);printf(”tt%d “,HashList[i].si);printf(”tt%d “,(HashList[i].k)%M);printf(”t %s “,HashList[i].py);printf(”n“);} // printf(”按任意键继续显示...n“);// getch();for(i=30;i<40;i++){ printf(”%d “,i);printf(”t%d “,HashList[i].k);printf(”tt%d “,HashList[i].si);printf(”tt%d “,(HashList[i].k)%M);printf(”t %s “,HashList[i].py);printf(”n“);} //printf(”按任意键继续显示...n“);//getch();for(i=40;i<50;i++){ printf(”%d “,i);printf(”t%d “,HashList[i].k);printf(”tt%d “,HashList[i].si);printf(”tt%d “,(HashList[i].k)%M);printf(”t %s “,HashList[i].py);printf(”n“);}

float average=0;for(i=0;i

printf(”n------------------------哈希表的建立和查找----------------------“);InitNameList();CreateHashList();

while(1){ printf(”nn“);printf(” 1.显示哈希表n“);printf(” 2.查找n“);printf(” 3.退出n“);

err: char ch1;scanf(”%c“,&ch1);if(ch1=='1')Display();else if(ch1=='2')FindList();else if(ch1=='3')return;else { printf(”n请输入正确的选择!");goto err;} } }

第三篇：电子商务实验报告表、

实验概述：

【实验目的及要求】

B2B E-business / B2C E-business

【实验原理】

【实验环境】（使用的软件）

实验内容：

【实验方案设计】

【实验过程】（实验步骤、记录、数据、分析）

【结论】（结果）

【小结】

第四篇：数字签名及哈希函数

数字签名与哈希函数

懂得一点公钥密码基础知识的人都知道，发信息的人用自己的私钥对所发信息进行加密(Encryption)，接收信息者用发信者的公钥来解密(Decryption)，就可以保证信息的真实性、完整性与不可否认性。（注：这里提到的加密、解密是指密码运算，其目的并非信息保密。）那么，我们也可以笼统地说，以上方法就已经达到了数字签名的目的。因为首先，私钥是发信者唯一持有的，别的任何人不可能制造出这份密文来，所以可以相信这份密文以及对应的明文不是伪造的（当然，发信者身份的确定还要通过数字证书来保证）；出于同样原因，发信者也不能抵赖、否认自己曾经发过这份信息；另外，信息在传输当中不可能被篡改，因为如果有人试图篡改，密文就解不出来。这样，用私钥加密，公钥解密的技术方法就可以代替传统签名、盖章，保证了信息的真实性、完整性与不可否认性。

但是，这样做在实际使用中却存在一个问题：要发的信息可能很长，非对称密码又比较复杂，运算量大，而为了保证安全，私钥通常保存在USB Key或IC卡中，加密运算也是在Key或卡中进行。一般来说，小小的USB Key或IC卡中的微处理器都做得比较简单而处理能力较弱，这样，加密所用的时间就会很长而导致无法实用。

另外，即使对于网站服务器而言，虽然它的处理能力很强，但服务器要同时处理许许多多签名加密的事情，也同样存在着加密耗时长系统效率低的问题。

有没有解决这个问题的办法呢？有的，常用的方法是使用哈希函数。

什么是哈希函数

哈希（Hash）函数在中文中有很多译名，有些人根据Hash的英文原意译为“散列函数”或“杂凑函数”，有些人干脆把它音译为“哈希函数”，还有些人根据Hash函数的功能译为“压缩函数”、“消息摘要函数”、“指纹函数”、“单向散列函数”等等。

1、Hash算法是把任意长度的输入数据经过算法压缩，输出一个尺寸小了很多的固定长度的数据，即哈希值。哈希值也称为输入数据的数字指纹（Digital Fingerprint）或消息摘要（Message Digest）等。Hash函数具备以下的性质：

2、给定输入数据，很容易计算出它的哈希值；

3、反过来，给定哈希值，倒推出输入数据则很难，计算上不可行。这就是哈希函数的单向性，在技术上称为抗原像攻击性；

4、给定哈希值，想要找出能够产生同样的哈希值的两个不同的输入数据，（这种情况称为碰撞，Collision），这很难，计算上不可行，在技术上称为抗碰撞攻击性；

5、哈希值不表达任何关于输入数据的信息。

哈希函数在实际中有多种应用，在信息安全领域中更受到重视。从哈希函数的特性，我们不难想象，我们可以在某些场合下，让哈希值来“代表”信息本身。例如，检验哈希值是否发生改变，借以判断信息本身是否发生了改变。`

怎样构建数字签名

好了，有了Hash函数，我们可以来构建真正实用的数字签名了。

发信者在发信前使用哈希算法求出待发信息的数字摘要，然后用私钥对这个数字摘要，而不是待发信息本身，进行加密而形成一段信息，这段信息称为数字签名。发信时将这个数字签名信息附在待发信息后面，一起发送过去。收信者收到信息后，一方面用发信者的公钥对数字签名解密，得到一个摘要H；另一方面把收到的信息本身用哈希算法求出另一个摘要H’，再把H与H’相比较，看看两者是否相同。根据哈希函数的特性，我们可以让简短的摘要来“代表”信息本身，如果两个摘要H与H’完全符合，证明信息是完整的；如果不符合，就说明信息被人篡改了。

数字签名也可以用在非通信，即离线的场合，同样具有以上功能与特性。

由于摘要一般只有128位或160位比特，比信息本身要短许多倍，USB Key或IC卡中的微处理器对摘要进行加密就变得很容易，数字签名的过程一般在一秒钟内即可完成。

哈希函数的安全性

哈希函数的安全性直接关系到数字签名的安全性，如果哈希函数被攻破，数字签名的有效性就会受到质疑。

目前，已经发明的Hash函数有多种，如Snefru、N-Hash、LOKI、AR、GOST、MD、SHA等。它们在数学上实现的方法各有不同，安全性也各有不同。目前比较常用的Hash函数是MD5与SHA-1。MD5哈希函数以512位来处理输入数据，每一分组又划分为16个32位的子分组。算法的输出由4个32位分组组成，将它们级联起来，形成一个128位的固定长度的哈希值，即输入数据的摘要。SHA-1哈希函数在MD4的基础上增加了数学运算的复杂程度，即SHA=MD4+扩展转换+附加轮+更好的雪崩效应（哈希值中，为0的比特与为1的比特，其总数应该大致相等；输入数据中一个比特的变化，将导致哈希值中一半以上的比特变化，这就叫做雪崩效应）。SHA能够产生160位的哈希值。对SHA还没有已知的密码攻击，并且由于它产生的哈希值位数长于MD5，所以它能更有效地抵抗穷举攻击（包括生日攻击）。

但是，任何一种算法都有其漏洞与局限性。任何一个哈希函数都会存在碰撞——即在一些特定情况下，两个不同的文件或信息会指向同一个数字摘要。在一般情况下，类似碰撞只能尽可能地减少，而不能完全避免。从理论上讲，没有攻不破的密码。随着密码科学的发展，也许会找到攻破某一种密码算法的途径。

评价Hash算法的一个最好方法是看敌手找到一对碰撞消息所花的代价有多高。一般地，假设攻击者知道Hash算法，攻击者的主要攻击目标是找到一对或更多对碰撞消息。目前已有一些攻击Hash算法与计算碰撞消息的方法。在这些方法中，有些是一般的方法，可用于攻击任何类型的Hash算法，比如“生日攻击”；而另一些是特殊的方法，只能用于攻击某些特殊的Hash算法，比如适合于攻击具有分组链结构Hash算法的“中间相遇攻击”，适用于攻击基于模运算的Hash函数的“修正分组攻击”。坚固的哈希函数可通过设计有效的碰撞处理机制，或增加数字摘要的位数来增加复杂度，以减少碰撞出现的概率，2004年8月17日，在美国召开的国际密码学会议（Crypto’ 2004）上，一些国家的密码学者作了破译Hash函数的新进展的报告，其中我国山东大学的王小云教授做了破译MD5、HAVAL-128、MD4、与RIPE MD算法的报告。

到2005年2月，据王小云教授的研究报告，他们已经研究出了搜索SHA-1碰撞的一系列新技术。他们的分析表明，SHA-1的碰撞能在小于2^69次Hash操作中找到。对完整的80轮SHA-1的攻击，这是第一次在小于2^80次Hash操作这个理论界限的情况下找到碰撞。根据他们的估计，对于缩减到70轮的SHA-1能够用现在的超级计算机找出“实碰撞”。他们的研究方法，能自然地运用到SHA-0与缩减轮数的SHA-1的破译分析上。

2005年3月6日，Arjen Lenstra，王小云，Benne de Weger 宣布，他们构造出一对基于MD5 Hash函数的X.509证书，产生了相同的签名。他们提出了一种构造X.509证书的方法，在他们所构造出的证书对中，由于使用了MD5算法，签名部分产生了碰撞。因此，当证书发布者使用MD5作为Hash函数时，发布者就会在证书中产生相同的签名，导致PKI的基础原理遭到可信性破坏。这意味着，从单独某个证书无法确定是否存在另一个不同证书有着相同的签名。由于第二个相同签名证书存在的可能性，证书发布机构无法验证私钥的“拥有证明”，即无法验证证书中的签名。因此，使用“基于MD5函数”公钥证书的任何一方都无法确保所谓的证书拥有者是否真实拥有相应的私钥。

他们也想构造一对基于SHA-1的X.509证书，产生相同的签名。然而，他们还做不到这一点。因为产生SHA-1碰撞还需要相当长一段时间的研究。

专家指出：A.Lenstra与王小云等人声称已经成功地构造了两张符合X．509证书数据结构，拥有同样签名而内容却不同的证书，但该构造方法对证书的部分域要有特殊安排，签名算法RSA的密钥也是按照特殊规律生成的，要用来攻击某个实际应用的电子签名系统仍需时日。而对于SHA-1算法，说其从理论上被破解都还为时过早，只能说其破解工作取得了重大突破，破解所需要运算次数已从原来设计时估算的2^80次降低为2^69次，这比穷举法快了２０４８倍，但2^69次运算需要６０００年左右的时间，在实际计算上仍然是不可行的。

除了运算方面的瓶颈外，哈希函数的不可逆性决定了攻击者无法轻易得手，没有人可以保证通过这个发现的每个碰撞都是“可用”的碰撞。在漫长的运算后，你得到的也许包含一些有价值的信息，也许就是理论上存在的单纯碰撞，运算瓶颈与信息匮乏都会使黑客们的种种努力成为徒劳……据业内人士估计，在当前的技术条件下，２^50或２^ ６０次运算量的范围内的攻击方法才会为我们带来麻烦，即引发实际意义上的攻击行为。在新研究成果发布前的一段时间内，SHA-1 算法只能被称作不完美，但还是安全的。基于PKI技术进行电子签名的最终用户，目前还不用担心自己的签名被伪造或遭遇签名人抵赖。

另外，安全专家强调：一种算法被破译，与整个企业的安全系统被攻破，是两个不同的概念。因为随着攻击技术与能力的提高，算法也会“水涨船高”，向前发展进步。王教授所取得的成就提醒密码学家研究新的算法，提醒有关标准化机构要提前修改算法标准，也提醒有关CA与电子签名产品开发商支持新的算法。当然，有些完全基于摘要算法的密押系统与电子货币系统，还需要尽早考虑替换方案。

美国国家技术与标准局（NIST）曾经发表如下评论：“研究结果说明SHA-1的安全性暂时没有问题，但随着技术的发展，技术与标准局计划在2010年之前逐步淘汰SHA-1，换用其他更长更安全的算法（如：SHA-224, SHA-256, SHA-384与SHA-512）来代替。”

第五篇：数据结构课程设计之姓名哈希表的建立及查找

武汉理工大学《数据结构》课程设计说明书

课程设计任务书

学生姓名： 刘颖 专业班级： 计科1003班 指导教师： 谭新明 工作单位： 计算机科学系 题 目: 哈希表的设计与实现 初始条件：

针对某个集体（比如你所在的班级）中的“人名”设计并实现一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。

（1）假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。

（2）哈希函数用除留余数法构造

（3）用伪随机探测再散列法处理冲突。

（4）测试用例见严蔚敏《数据结构习题集(C语言版)》p166。

要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）

课程设计报告按学校规定格式用A4纸打印（书写），并应包含如下内容：

1.问题描述

简述题目要解决的问题是什么。2.设计

存储结构设计、主要算法设计（用类C/C++语言或用框图描述）、测试用例设计； 3.调试报告

调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。4.经验和体会（包括对算法改进的设想）

5.附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则运行结果要包含这些测试数据和运行输出。

说明：

1.设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。2.凡拷贝往年任务书或课程设计充数者，成绩一律无效，以0分记。

时间安排： 1、6月15日～6月21日完成。2、6月22日上午和下午在实验中心检查程序、交课程设计报告、源程序（U盘）。

指导教师签名： 2012年6月14日 系主任（或责任教师）签名： 年 月 日

武汉理工大学《数据结构》课程设计说明书

目录

1问题分析和任务定义...............................................3 1.1问题描述.......................................................3 1.2问题分析.......................................................3 2开发平台.........................................................3 3数据类型和系统设计...............................................3 3.1存储结构设计...................................................3 3.2主要算法设计...................................................4 3.2.1姓名结构体数组初始化.........................................4 3.2.2获取关键码...................................................5 3.2.3哈希表结构体数组初始化.......................................5 3.2.4构造哈希表...................................................5 3.2.5打印哈希表...................................................6 3.2.6在哈希表中查找姓名...........................................6 4调试结果与运行情况分析...........................................8 4.1程序运行结果...................................................8 4.2运行情况分析...................................................9 4.3算法的时间复杂度...............................................9 5自我评价与总结...................................................9 6参考文献........................................................10 7附：源代码......................................................11

武汉理工大学《数据结构》课程设计说明书

哈希表的设计与实现

1问题分析和任务定义

1.1问题描述

设计哈希表，要求用除留余数法构造哈希函数，用伪随机探测再散列法处理冲突，使平均查找长度的上限为2。待填入哈希表的人名共有30个，且为中国人姓名的汉语拼音形式。

1.2问题分析

（1）待填入哈希表的人名有30个，平均查找长度的上限为2。用除留余数法构造哈希表，用伪随机探测再散列法处理冲突，完成相应的建立和查表程序。

（2）人名为汉语拼音形式，最长不超过20个字符。

（3）查找成功时，显示姓名、关键字、初散列值、再散列值、哈希表中的位置及查找长度；查找失败时，显示无此记录。

（4）可多次查找，继续查找输入1，退退出输入0。

2开发平台

系统：Windows 7 开发工具：Visual studio 2008 语言：C++ 3数据类型和系统设计

3.1 存储结构设计

typedef struct {

int key;

char *p;}NAME;

武汉理工大学《数据结构》课程设计说明书

typedef struct {

int key;//关键字

int hash;//初始地址

int reha;//再散列值

char *p;//名字

int l;//查找长度 }HASH;3.2主要算法设计

3.2.1 NAME（结构体数组）初始化

NAME a[30];a[0].p=“wangjunzhe”;a[1].p=“mahaiping”;a[2].p=“luozijian”;a[3].p=“luoxiangzhou”;a[4].p=“zhangkai”;a[5].p=“fengyuyang”;a[6].p=“wuzhenzhen”;a[7].p=“haokaiqi”;a[8].p=“caopu”;a[9].p=“liuying”;a[10].p=“cuijuan”;a[11].p=“hanqianqiqn”;a[12].p=“lixiaoyu”;a[13].p=“caoyingnan”;a[14].p=“jinbaoyu”;a[15].p=“zhaduo”;a[16].p=“wenbo”;a[17].p=“cuichangwei”;a[18].p=“zhangqiu”;a[19].p=“luopeng”;a[20].p=“hudie”;a[21].p=“xieshanshan”;a[22].p=“liming”;a[23].p=“zhangshuai”;a[24].p=“qiuyajun”;a[25].p=“yanruibin”;a[26].p=“jiangwei”;a[27].p=“fangzhaohua”;a[28].p=“yujia”;

武汉理工大学《数据结构》课程设计说明书

a[29].p=“liuzhenzhen”;3.2.2获取关键码

字符串的各个字符所对应的ASCII码相加，所得的整数做为关键字。

int i,s,r;for(i=0;i<30;i++){

s=0;for(r=0;*(a[i].p+r)!='';r++)

{

s+=*(a[i].p+r);

a[i].key=s;

}

} 3.2.3 HASH(结构体数组)初始化

HASH h[40];for(i=0;i<40;i++){ h[i].key=0;h[i].hash=0;h[i].reha=0;h[i].p=“ ”;h[i].l=0;} 3.2.4构造哈希表

for(i=0;i<30;i++){

int sum=0;int hi=(a[i].key)%37;//哈希函数

int hj=(7*a[i].key)%10+1;//再散列函数 if(h[hi].l==0)//如果不冲突

{ h[hi].key=a[i].key;h[hi].hash=(a[i].key)%37;h[hi].reha=(7*a[i].key)%10+1;h[hi].p=a[i].p;

武汉理工大学《数据结构》课程设计说明书

h[hi].l=1;

} else //冲突

{

int finh;//最终地址

do

{ finh=(hi+hj)%40;//伪随机探测再散列法处理冲突

hi=finh;sum=sum+1;//查找次数加

}while(h[hi].l!=0);

h[hi].key=a[i].key;

h[hi].hash=(a[i].key)%37;

h[hi].reha=(7*a[i].key)%10+1;h[hi].p=a[i].p;h[hi].l=sum+1;

} } 3.2.5打印哈希表

float average=0;cout<<“关键码 初散列 再散列 哈希地址 查找次数 姓名”<

for(i=0;i<40;i++)average+=h[i].l;average/=30;cout<<“平均查找长度：ASL=”<

int m;do //m=1,继续查找；m=0,退出查找 { char *f=new char[20];int key=0,n=0,g,l=1,adr;cout<<“请输入姓名的拼音:”<>f;for(g=0;*(f+g)!='';g++)//求出姓名的拼音所对应的整数(关键字)

武汉理工大学《数据结构》课程设计说明书

{

n+=*(f+g);

key=n;

}

adr=key%37;//哈希函数求初散列值

if(h[adr].key==key)//分3种情况进行判断

{

cout<<“关键字:”<

cout<<“初散列值为:”<

cout<<“再散列值为:”<

cout<<“表中位置为:”<

int finh;//最终地址

int sign=0;

do

{

finh=(adr+7*key%10+1)%40;//再散列法处理冲突

adr=finh;l=l+1;//查找次数加

if(h[adr].key==0)

{

sign=1;

cout<<“无此记录!”<

}

if(h[adr].key==key)

{ sign=1;cout<<“关键字:”<

} }while(sign==0);}

cout<<“继续查询请输入,退出请输入：”<>m;}while(m==1);7

武汉理工大学《数据结构》课程设计说明书

4调试结果与运行情况分析

4.1程序运行结果

武汉理工大学《数据结构》课程设计说明书

4.2运行情况分析

哈希表的输出与预期相同且正确，并查找了“liuying”、“jiangwei”、“huangxiao”三个姓名，分别代表查找一次、多次后成功及查找不成功的情况，且查找结果正确。

4.3算法的时间复杂度

O(n)5自我评价与总结

经过这次课程设计的学习，让我明白了编写程序的思路是很重要的，不仅检验了我所学习的知识，也培养了我如何去把握一件事情，如何去做一件事情，又如何完成一件事情的方法和技巧。在编写一个程序之前，如果脑袋里面没有思路，根本就不可能编出好的程序。就算能编出程序来，相信编出的程序的逻辑性也不会很强，因为是想到什么就编什么，不系统。因此在我们编程序之前一定要做好充分的准备，首先要理清自己的思路，然后再将思路分划成几个模块，一块一块的编写，最后再将所有的模块联系起来，组成一个完整的程序。在上机实验之前，最好将程序编写好在草稿纸上，这样在编译的时候也比较有效率。

课程设计是我们专业课程知识综合应用的实践训练，着是我们迈向社会，从事职业工作前一个必不少的过程．“千里之行始于足下”，通过这次课程设计，武汉理工大学《数据结构》课程设计说明书

我深深体会到这句千古 名言的真正含义。今天认真的进行课程设计，学会脚踏实地迈开这一步，就是为明天能稳 健地在社会大潮中奔跑打下坚实的基础。数据结构，是一门研究非数值计算的程序设计问题中计算机的操作对象（数据元素）以及它们之间的关系和运算等的学科，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。这一门课的内容不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。通过这次哈希表的设计，我在多方面都有所提高。

在这次课程设计的过程中，我也遇到了很多难题。在种种的困难中，我明白了耐心在编写程序时的重要性。如果你没有耐心就肯定编不出好的程序，特别是在调试的过程中。我们初次写的程序在电脑上调试的时候也许会出项几百个错误，这时候我们应该耐心的检查出错的地方和原因，并予以改正，而不是抱怨自己写的程序太烂错误太多，就此放弃。相信再强的人也不可能一次就能编译成功，总会有一些问题出现。其实只要有耐心，就会发现，在修改了一个错误之后，其它有的错误也会跟着消失，所以在编译的时候一定要有耐心。通过这次课程设计，我认识到了自己动手实践的弱势，特别是在编程方面，知道了计算机的实践操作是很重要的，只有通过上机编程才能充分的了解自己的不足。而自己完成了这样的课程设计，也是对自己实力的检测，使我对以后的学习也充满了信心和期待。这次的课程设计，更是让我深刻认识到自己在学习中的不足，同时也找到了克服这些不足的方法，这也是一笔很大的资源。

数据结构是一门比较难的课程，需要花很多的时间去练习和实践。要想把这门课程学好学精不是一件容易的事，但是相信事在人为，只要肯下功夫就一定能学好。总的来说，这次程序设计让我获益匪浅，相信在以后的学习生活中我也能从中获得启发。在以后的时间中，我们应该利用更多的时间去上机 实验，加强自学的能力，多编写程序，相信不久后我们的编程能力都会有很大的提高能设计 出更多的更有创新的作品。

我认为我的设计优点在于只是用了简单的面向过程编程，而没有用面向对象的类的设计。类在用于比较大的程序设计时会显露较大的优势，而在此反而会增加不必要的麻烦。我的设计缺点在于不是面向大众的，即不能由用户在运行时输入姓名，只能通过在代码中的修改达到效果。

这个课题的另一种方法是使用模板类，这样做可以使程序的结构看起来更整洁简明，各种方法的相关函数一览无余；在主函数中直接调用定义在模版类中的函数，使读者可以很快明白主函数做了哪些工作，程序运行后会有哪些输入输出。

6.参考文献

1.《数据结构（用面向对象方法与C++语言描述）》（第2版）清华大学出版社 2.《C++ Primer(中文版)》（第4版）人民邮电出版社

武汉理工大学《数据结构》课程设计说明书

7.附：源代码

#include using namespace std;int main(){ typedef struct {

int key;

char *p;}NAME;NAME a[30];a[0].p=“wangjunzhe”;a[1].p=“mahaiping”;a[2].p=“luozijian”;a[3].p=“luoxiangzhou”;a[4].p=“zhangkai”;a[5].p=“fengyuyang”;a[6].p=“wuzhenzhen”;a[7].p=“haokaiqi”;a[8].p=“caopu”;a[9].p=“liuying”;a[10].p=“cuijuan”;a[11].p=“hanqianqiqn”;a[12].p=“lixiaoyu”;a[13].p=“caoyingnan”;a[14].p=“jinbaoyu”;a[15].p=“zhaduo”;a[16].p=“wenbo”;a[17].p=“cuichangwei”;a[18].p=“zhangqiu”;a[19].p=“luopeng”;a[20].p=“hudie”;a[21].p=“xieshanshan”;a[22].p=“liming”;a[23].p=“zhangshuai”;a[24].p=“qiuyajun”;a[25].p=“yanruibin”;a[26].p=“jiangwei”;a[27].p=“fangzhaohua”;a[28].p=“yujia”;a[29].p=“liuzhenzhen”;int i,s,r;

武汉理工大学《数据结构》课程设计说明书

for(i=0;i<30;i++){

s=0;for(r=0;*(a[i].p+r)!='';r++)

{

s+=*(a[i].p+r);

a[i].key=s;

}

}

typedef struct {

int key;//关键字

int hash;//初始地址

int reha;//再散列值

char *p;//名字

int l;//查找长度 }HASH;HASH h[40];for(i=0;i<40;i++){ h[i].key=0;h[i].hash=0;h[i].reha=0;h[i].p=“";h[i].l=0;} for(i=0;i<30;i++){

int sum=0;int hi=(a[i].key)%37;//哈希函数

int hj=(7*a[i].key)%10+1;//再散列函数

if(h[hi].l==0)//如果不冲突

{

h[hi].key=a[i].key;

h[hi].hash=(a[i].key)%37;

h[hi].reha=(7*a[i].key)%10+1;h[hi].p=a[i].p;h[hi].l=1;

} else //冲突

{

int finh;//最终地址

武汉理工大学《数据结构》课程设计说明书

do

{

finh=(hi+hj)%40;//伪随机探测再散列法处理冲突

hi=finh;sum=sum+1;//查找次数加 1

}while(h[hi].l!=0);

h[hi].key=a[i].key;

h[hi].hash=(a[i].key)%37;

h[hi].reha=(7*a[i].key)%10+1;h[hi].p=a[i].p;h[hi].l=sum+1;

} }

float average=0;cout<<”关键码初散列再散列哈希地址查找次数姓名“<

for(i=0;i<40;i++)average+=h[i].l;average/=30;cout<<”平均查找长度：ASL=“<>f;for(g=0;*(f+g)!='';g++)//求出姓名的拼音所对应的整数(关键字){

n+=*(f+g);

key=n;

} adr=key%37;//哈希函数求初散列值

if(h[adr].key==key)//分3种情况进行判断

{

cout<<”关键字:“<

cout<<”初散列值为:“<

cout<<”再散列值为:“<

武汉理工大学《数据结构》课程设计说明书

cout<<”表中位置为:“<

int finh;//最终地址

int sign=0;

do

{

finh=(adr+7*key%10+1)%40;//再散列法处理冲突

adr=finh;l=l+1;//查找次数加

if(h[adr].key==0)

{

sign=1;

cout<<”无此记录!“<

}

if(h[adr].key==key)

{ sign=1;cout<<”关键字:“<

} }while(sign==0);}

cout<<”继续查询请输入,退出请输入："<>m;}while(m==1);return 0;}