散列法的实验研究
散列法的实验研究
学生姓名: 学号:
学院:
专业: 信息管理与信息系统
题目: 散列法的实验研究
成绩
指导教师
2010年12月20日
1 设计目的
《数据结构》课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑
关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并
对算法的效率进行简
单的分析和讨论。进行数据结构课程设计要达到以下目的:
(1) 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力;
(2) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方
法和技能;
(3) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力; 训练用
系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的
工作方法和作风。
2. 设计内容和要求
设计内容:
(1) 散列法中，散列函数构造方法多种多样，同时对于同一散列函数解决冲突
的方法也可以不同。两者是影响查询算法性能的关键因素。
(2) 程序实现几种典型的散列函数构造方法，并观察，不同的解决冲突方法对查询性能的影响。
设计要求:
(1) 符合课题要求，实现相应功能;
(2) 要求界面友好美观，操作方便易行;
(3) 注意程序的实用性、安全性;
3(本设计所采用的数据结构
本设计采用散列法，用直接定址法、数字分析法、平方取中法、折叠法、除留余数法五种构造函数及开放定址法(线性探测再散列、二次探测再散列)、链地址法三种解决冲突的方法对散列法进行实验研究。
直接定址法:将待处理数据x直接赋值给adr, adr为关键字存储在散列表内的位置
adr=x
数字分析法:提取用户所要求进行分析的数字的位数，将组成新的数字，然后按照直接
定址法对新数字进行存储
int adr,p2=1,q2=1,i;
int p3=p1,q3=q1; //p1为程序接收用户输入的待分析数字所在的位数
//q1为程序接收用户输入的待分析数字所在的位数
int num=2;
if(p1==1)
p3=x%10;
1
else
{
for(i=1;i { p2=p2*10; p3=x/p2; p3=p3%10; } } for(i=1;i { q2=q2*10; q3=x/q2; q3=q3%10; } adr=p3+10*q3; 平方取中法:将待处理数据平方，取平方后的百位、十位作为存储地址 x1=x*x; a=(x1/100)%10; b=(x1/10)%10; adr=a*10+b; 折叠法:本程序内将待处理数字从低位到高位每三位组成一个新数字，并将所有新数字求 和，产生的新数作为存储地址 if(x<1000) { a1=x; sum=a1; } else { 2 a1=x%1000; a2=x/1000; sum=a1+a2; } adr=sum; 除留余数法:将待处理数据除M=979所得余数作为数据的存储地址adr=x%M; 线性探测再散列: adr=(adr+d)%M d=1,2…… 二次线性探测再散列:adr=(adr+d)%M d=1*1,-1*1,2*2,-2*2…… int p=1,q=0,b=-1; p=b*(p+q)*(p+q); if(num%2==1) p=-p; else q++; num++; adr=(abs(x+p))%M; 链地址法:本程序采用二维数组P[60][60]代替链表对数据进行处理与存储，用二维数组的 行存储数据存储的地址，二维数字的列存储已经进行处理的数据 int j; for(j=0;j<60;j++) { if(P[adr][j]==0) { ha[adr].location=adr; ha[adr].key=x; P[adr][j]=x; } 开放定址法查找成功的平均查找长度: int i; 3 int s=0,n=0; for(i=0;i { if(ha[i].key!=0) { s=s+ha[i].count; n++; } } ASL=s*1.0/n 链地址法查找成功的平均查找长度: int p,q,s=0; for(p=0;p<60;p++) { for(q=0;q<60;q++) { if(array[p][q]!=0) s=s+(q+1); else break; } } ASL=s*1.0/n; 4(功能模块详细设计 4.1 详细设计思想 散列法中，散列函数构造方法多种多样，而且对于同种散列函数解决冲突的方法也各有不同。因此我们要关注不同构造方法结合不同解决冲突的方法对算法性能的影响，以此来判定在存储某类数据时，不同方法对查询性能。 本程序主要就直接定址法、数字分析法、平方取中法、折叠法、除留余数法五种构造函数及开放定址法(线性探测再散列、二次探测再散列)、链地址法三种解决冲突的方法对散列法进行实验研究。根据不同的待处理数据类型选择不同的构造函数及处理冲突的方法，由采用的不同的方法对其查找成功的平均查找长度进行计算，以此来比较不同算法的性能。 4 用户首先根据提示输入待处理数据的个数及待处理的数据，再由程序所给的选项选择构造函数及处理冲突的方法，本程序设计共设计了十五种构造函数及解决冲突的方法: 线性探测再散列) 函数名称:addressDirectlyColl1 1. 直接地址法( 该方法取关键字直接作为散列表的地址，若将要存入的地址已经有关键字，则运用开放 定址法中的线性探测再散列处理冲突，H=(H(key)+d)%M,d为增量序列，且 d=1,2… 2. 直接地址法(二次线性探测再散列) 函数名称:addressDirectlyColl2 该方法取关键字直接作为散列表的地址，若将要存入的地址已经有关键字，则运用开放 定址法中的二次线性探测再散列处理冲突，H=(H(key)+d)%M,d为增量序列，且d=1,-1,4，-4… 3. 直接地址法(链地址法) 函数名称:addressDirectlyColl3 该方法取关键字直接作为散列表的地址，若将要存入的地址已经有关键字，则运用链地 址法处理冲突，将所有关键字为同义词的记录存储在同一线性表中。但在此程序中将二 维数组代替链表，二维数组的行定义为散列地址，列依次存放关键字。 4. 数字分析法(线性探测再散列) 函数名称:numericalMethodColl1 若所有关键字可知，则可取关键字其中任意两位出现频率较随机的数字作为散列地址， 遇到冲突时的解决方法与第一个函数的解决冲突方法相同。 5. 数字分析法(二次线性探测再散列) 函数名称:numericalMethodColl2 若所有关键字可知，则可取关键字其中任意两位出现频率较随机的数字作为散列地址， 遇到冲突时的解决方法与第二个函数的解决冲突方法相同。 6. 数字分析法(链地址法) 函数名称:numericalMethodColl3 若所有关键字可知，则可取关键字其中任意两位出现频率较随机的数字作为散列地址， 遇到冲突时的解决方法与第三个函数的解决冲突方法相同。 7. 平方取中法(线性探测再散列) 函数名称:mid_squareMethodColl1 取关键字平方后的中间几位为散列地址，遇到冲突时的解决方法与第一个函数的解决冲 突方法相同。 8. 平方取中法(二次线性探测再散列) 函数名称: mid_squareMethodColl2 取关键字平方后的中间几位为散列地址，遇到冲突时的解决方法与第二个函数的解决冲 突方法相同。 9. 平方取中法(链地址法) 函数名称: mid_squareMethodColl3 取关键字平方后的中间几位为散列地址，遇到冲突时的解决方法与第三个函数的解决冲 5 突方法相同。 10. 折叠法(线性探测再散列) 函数名称: foldMethodColl1 将关键字分割成位数相同的几部分，然后取这几部分的叠加和作为散列地址，遇到冲突 时的解决方法与第一个函数的解决冲突方法相同。 函数名称: foldMethodColl2 11. 折叠法(二次线性探测再散列) 将关键字分割成位数相同的几部分，然后取这几部分的叠加和作为散列地址，遇到冲突 时的解决方法与第二个函数的解决冲突方法相同。 12. 折叠法(链地址法) 函数名称: foldMethodColl3 将关键字分割成位数相同的几部分，然后取这几部分的叠加和作为散列地址，遇到冲突 时的解决方法与第三个函数的解决冲突方法相同。 13. 除留余数法(线性探测再散列) 函数名称: divisionMethodColl1 取关键字被某个不大于散列表表长的数除后所得余数为散列地址，遇到冲突时的解决方 法与第一个函数的解决冲突方法相同。 14. 除留余数法(二次线性探测再散列) 函数名称: divisionMethodColl2 取关键字被某个不大于散列表表长的数除后所得余数为散列地址，遇到冲突时的解决方 法与第二个函数的解决冲突方法相同。 15. 除留余数法(链地址法) 函数名称: divisionMethodColl3 取关键字被某个不大于散列表表长的数除后所得余数为散列地址，遇到冲突时的解决方 法与第三个函数的解决冲突方法相同。 在对待处理数据全部处完毕后再有程序输出所用方法查找数据成功的平均查找长度。根据程序输出的数据存储位置及存储的次数以及查找数据成功的平均查找长度来分析使用不同的构造方法及处理冲突的方法对算法性能的影响。 4.2 核心代码 #include #include #include #include #include #define SUCCESS 1 #define MAXSIZE 800 6 #define M 797 /*元素类型的定义*/ typedef struct { int location; int key ; int count; }HashTable[MAXSIZE]; HashTable ha; /*散列表初始化*/ void init(HashTable ha) { int i; for(i=0;i<800;i++) { ha[i].location=0; ha[i].key=0; ha[i].count=0; } } /*选择构造函数界面 */ void functionUI1() { printf("*************************请选择构造函 数:**************************\n"); printf("* 1、直接地址法(线性探测再散列) *\n"); printf("* 2、直接地址法(二次线性探测再散列) *\n"); printf("* 3、直接地址法(链地址法) *\n"); printf("* 4、数字分析法(线性探测再散列) *\n"); 7 printf("* 5、数字分析法(二次线性探测再散列) *\n"); printf("* 6、数字分析法(链地址法) *\n"); printf("* 7、平方取中法(线性探测再散列) *\n"); printf("* 8、平方取中法(二次线性探测再散列) *\n"); printf("* 9、平方取中法(链地址法) *\n"); printf("* 10、折叠法(线性探测再散列) *\n"); printf("* 11、折叠法(二次线性探测再散列) *\n"); printf("* 12、折叠法(链地址法) *\n"); printf("* 13、除留余数法(线性探测再散列) *\n"); printf("* 14、除留余数法(二次线性探测再散列) *\n"); printf("* 15、除留余数法(链地址法) *\n"); printf("* 0、退出实验系统 *\n"); printf("************************************************************ ******\n\n "); } /*计算查找成功的平均长度 */ void compASL(HashTable ha,int length) { int i; int s=0,n=0; for(i=0;i { if(ha[i].key!=0) { s=s+ha[i].count; n++; } } printf(" ********查找成功的ASL=%f ******** 8 \n",s*1.0/n); printf("************************************************************ ******\n\n "); } /*链地址法的平均查找长度*/ void Coll3ASL(int array[60][60],int n) { int p,q,s=0; for(p=0;p<60;p++) { for(q=0;q<60;q++) { if(array[p][q]!=0) s=s+(q+1); else break; } } printf(" ********查找成功的ASL=%f ******** \n",s*1.0/n); printf("************************************************************ ******\n\n"); } /*线性探测散列*/ void Coll1(HashTable ha,int x,int adr,int num) { adr=(adr+1)%M; A: if(ha[adr].key==0) 9 { ha[adr].location=adr; ha[adr].key=x; ha[adr].count=num; } else{ adr=(adr+1)%M;num++;goto A;} printf("* %d在散列表的第%d个位置，第%d次放入哈希表\n",ha[adr].key,ha[adr].location,ha[adr].count); } /*二次线性探测再散列*/ void Coll2(HashTable ha,int adr,int x,int num) { int p=1,q=0,b=-1; A: p=b*(p+q)*(p+q); if(num%2==1) p=-p; else q++; num++; adr=(abs(x+p))%M; if(ha[adr].key==0) { ha[adr].location=adr; ha[adr].key=x; ha[adr].count=num; } else{ p=abs(p);goto A;} printf("* %d在散列表的第%d个位置，第%d次放入哈希表 10 \n",ha[adr].key,ha[adr].location,ha[adr].count); num=1; } /*链地址法*/ void Coll3(HashTable ha,int P[60][60],int adr,int x) { int j; for(j=0;j<60;j++) { if(P[adr][j]==0) { ha[adr].location=adr; ha[adr].key=x; P[adr][j]=x; printf("* %d在散列表的第%d个位置\n",x,ha[adr].location); break; } } } /*直接地址法线性探测再散列*/ void addressDirectlyColl1(HashTable ha,int n,int x,int j) { int num=2; int adr; if(j==0) { printf("**本方法构造函数为:直接地址法，解决冲突的方法为:线性探测再散列**\n"); 11 } adr=x; if(ha[adr].key==0) { ha[adr].location=adr; ha[adr].key=x; ha[adr].count=1; printf("* %d在散列表的第%d个位置，第%d次放入哈希表 \n",x,ha[adr].location,ha[adr].count); } else { Coll1(ha,x,adr,num); } } /*直接地址法二次线性探测再散列*/ void addressDirectlyColl2(HashTable ha,int n,int x,int j) { int num=1; int adr; if(j==0) { printf("*本方法构造函数为:直接地址法，解决冲突的方法为:二次线性探测再散列*\n"); } adr=x; if(ha[adr].key==0) { 12 ha[adr].location=adr; ha[adr].key=x; ha[adr].count=1; printf("* %d在散列表的第%d个位置，第%d次放入哈希表 \n",x,ha[adr].location,ha[adr].count); } else { Coll2(ha,adr,x,num); } } /*直接地址法链地址法*/ void addressDirectlyColl3(HashTable ha,int n,int x,int j,int P[60][60]) { int adr; if(j==0) { printf("*****本方法构造函数为:直接地址法，解决冲突的方法为:链地址法*****\n"); } adr=x; if(ha[adr].key==0) { ha[adr].location=adr; ha[adr].key=x; P[adr][0]=x; 13 printf("* %d在散列表的第%d个位置\n",x,ha[adr].location); } else Coll3(ha,P,adr,x); } /*数字分析法线性探测再散列*/ void numericalMethodColl1(HashTable ha,int n,int x,int j,int p1,int q1) { int adr,p2=1,q2=1,i; int p3=p1,q3=q1; int num=2; if(p1==1) p3=x%10; else { for(i=1;i { p2=p2*10; p3=x/p2; p3=p3%10; } } for(i=1;i { q2=q2*10; q3=x/q2; q3=q3%10; 14 } adr=p3+10*q3; if(ha[adr].key==0) { ha[adr].location=adr; ha[adr].key=x; ha[adr].count=1; printf("* %d在散列表的第%d个位置，第%d次放入哈希表 \n",x,ha[adr].location,ha[adr].count); } else { Coll1(ha,x,adr,num); } } /*数字分析法二次线性探测再散列*/ void numericalMethodColl2(HashTable ha,int n,int x,int j,int p1,int q1) { int p=1,q=0,num=1,b=-1; int adr,p2=1,q2=1,i; if(p1==1) p1=x%10; else { 课程实验报告 课程名称：数据结构 实验项目名称：散列表 专业班级： 姓名：XXX 学号： 完成时间：2015 年06 月13 日 背景 散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。在理想情况下，查找、插入、删除操作的时间均为O(1)，是一种高效的动态集合结构。 例1：计算机程序设计语言的编译程序需要维护一个符号表，其中元素的关键值为任意字符串，与语言中的标识符对应。该符号表常采用散列表。 例2：为了节约空间，常常需要把文本文件采用压缩编码方式存储。LZW是对文本文件进行压缩和解压缩的方法之一，该方法采用了散列。 问题描述 我们希望在浩瀚的图书中，去发现一本书是否存在。我们不知道书的编号，只知道它的书名。（其实这已经不错了...）。通过书名，来查询它是否存在。 为了简化问题，我们假设每本书的书名都是一组小写字母组成，长度不超过100字符。 基本要求 （1）根据输入建立图书名称表，采用散列表实现该表，散列函数选用BKDE 字符串哈希。 （2）数据的输入输出格式： 输入分为两部分 第一部分，第一行是行数n，n <= 5000。余下n行，每行一个字符串。表示已存 在的图书记录。 第二部分，第一行是行数m，m <= 1000。余下m行，每行一个字符串。表示要查 询的图书记录。 输出： 输出为m行，如果被查的记录存在，则输出"YES",如果不存在则输出"NO"。 测试数据 输入： 4 a ans and hellocpp 第九章作业 一、选择题 1. 顺序查找算法适用于( )。 A. 线性表 B. 查找树 C. 查找网 D. 连通图 2. 顺序查找法适用于线性表的( )。 A.散列存储 B.压缩存储 C. 索引存储 D. 顺序或链接存储 3. 采用顺序查找方式查找长度为n 的顺序表时，平均查找长度为( ) A. n B. 2/n C. 2/)1(+n D. 2/)1(-n 4. 如果有5个关键吗{a,b,c,d,e }放在顺序表中，他们的查找概率分别为{0.35,0.25,0.20,.015,0.05}，可使平 均查找长度达到最小的存放方式是( )。 A. d,a,b,c,e B. e,d,c,b,a C. a,b,c,d,e D. a,c,e,d,b 5. 对于长度为n 的有序单链表，若查找每个元素的概率相等，则顺序查找表中任一元素的查找成功的平 均查找长度为( ) A. 4/n B. 2/n C. 2/)1(+n D. 2/)1(-n 6. 对线性表进行折半查找时，要求线性表必须( ) A. 以顺序方式存储 B. 以链接方式存储 C. 以顺序方式存储，且结点按关键吗有序排列 D. 以链接方式存储，且结点按关键吗有序排列 7. 采用折半查找法查找长度为n 的有序顺序表时，平均查找长度为( ) A. )(n O B. )(log 2n O C. )(2 n O D. )log (n n O 8. 对于长度为18的有序顺序表，若采用折半查找，则查找第15个元素的查找次数为( )。 A. 3 B. 4 C. 5 D. 6 9. 已知有序顺序表(13,18,24,35,47,50,62,83,90,115,134)，若采用折半查找法查找值为18的元素时，查找 成功的数据比较次数为( )。 A. 1 B. 2 C. 3 D. 4 10. 使用散列法时确定元素存储地址的依据是( )。 A. 元素的序号 B. 元素个数 C. 关键吗 D. 非码属性 11. 设一个散列表中有n 个元素，用散列法进行查找的平均查找长度是( )。 A. )1(O B. )(n O C. )log (2n O D. )(2 n O 12. 使用散列函数将元素的关键吗映射为散列地址时，常会发生冲突。此时的冲突是指( )。 A. 两个元素具有相同的序号 B. 两个元素的关键码不同，而非关键码相同 C. 不同关键码对应到相同的存储地址 D. 装载因子过大，数据元素过多 13. 计算出的地址分布最均匀的散列函数是( )。 A. 数值分析法 B. 除留余数法 C. 平方取中法 D. 折叠法 14. 将10个元素散列到大小为100000个元素的散列表中，( )产生冲突。 A. 一定会 B. 一定不会 C. 仍可能会 D. 以上都不对 15. 采用线性探测法解决冲突时计算出的一系列“下一个空位”( )。 A. 必须大于等于原散列地址 B. 必须小于等于原散列地址 C. 可以大于或小于但不等于原散列地址 D. 对地址在何处没有限制 16. 包含有4个结点的元素值互不相同的二叉查找树有( )棵。 A. 4 B. 6 C. 10 D. 14 17. 利用逐个数据插入的方法建立序列{35,45,25,55,50,10,15,30,40,20}对应的二叉查找树后，查找元素20 需要进行( )次元素之间的比较。 A. 4 B. 5 C. 7 D. 10 18. 一颗高度为h 的AVL 树，若其每个非叶子结点的平衡因子都是0，则该树共有( )个结点。 A. 12 1 --h B. 1 2 -h C. 12 1 +-h D. 12-h 实验报告 姓名：学号： 1．实验题目 针对某个集体中人名设计一个哈希表，使得平均查找长度不超过R，并完成相应的建表和查表程序。 基本要求：假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用线性探测再散列法或链地址法处理冲突。 2．需求分析 本演示程序用VC编写，完成哈希函数用除留余数法构造，用线性探测再散列法或链地址法处理冲突。 输出形式：地址，关键字，收索长度，H（key），拼音 3.概要设计 typedef struct NAME typedef struct hterm void InitNameList() void CreateHashList() void FindList() void Display() int main() 4．详细设计 #include #define HASH_LEN 50 #define M 47 #define NAME_NO 8 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="houxinming"; NameList[1].py="abc"; NameList[2].py="defdgf"; NameList[3].py="zhangrji"; NameList[4].py="jiaxin"; NameList[5].py="xiaokai"; NameList[6].py="liupeng"; NameList[7].py="shenyonghai"; 第九章查找 一、填空题 1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是。 2. 线性有序表（a 1，a 2 ，a 3 ，…，a 256 )是从小到大排列的，对一个给定的值k，用二分法检索 表中与k相等的元素，在查找不成功的情况下，最多需要检索次。设有100个结点，用二分法查找时，最大比较次数是。 3. 假设在有序线性表a[1..20]上进行折半查找，则比较一次查找成功的结点数为1；比较两 次查找成功的结点数为 2 ；比较四次查找成功的结点数为 ,其下标从小到大依次是 ____，平均查找长度为。 4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素比较大小。 5. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是。 6. 散列法存储的基本思想是由决定数据的存储地址。 7. 有一个表长为m的散列表，初始状态为空，现将n（n 计算机算法领域 基本知识 Hash，一般翻译做“散列”，也有直接音译为”哈希“的，就是把任意长度的输入（又叫做预映射，pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。 HASH主要用于信息安全领域中加密算法，他把一些不同长度的信息转化成杂乱的128位的编码里,叫做HASH值. 也可以说，hash就是找到一种数据内容和数据存放地址之间的映射关系 基本概念 * 若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数(Hash function)，按这个思想建立的表为散列表。 * 对不同的关键字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2)，这种现象称冲突。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数H(key)和处理冲突的方法将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象” 作为记录在表中的存储位置，这种表便称为散列表，这一映象过程称为散列造表或散列，所得的存储位置称散列地址。 * 若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数(Uniform Hash function)，这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。 常用的构造散列函数的方法 散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快地定位ǐ 1. 直接寻址法：取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a?key + b，其中a和b为常数（这种散列函数叫做自身函数） 2. 数字分析法 3. 平方取中法 4. 折叠法 5. 随机数法 6. 除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即H(key) = key MOD p, p<=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词。 处理冲突的方法 1. 开放寻址法；Hi=(H(key) + di) MOD m, i=1,2,…, k(k<=m-1)，其中H(key)为散列函数，m为散列表长，di为增量序列，可有下列三种取法： 1. di=1,2,3,…, m-1，称线性探测再散列； 2. di=1^2, (-1)^2, 2^2,(-2)^2, (3)^2, …, ±(k)^2,(k<=m/2)称二次探测再散列; 福建工程学院 课程设计 课程：算法与数据结构 题目：哈希表 专业：网络工程 班级：xxxxxx班 座号：xxxxxxxxxxxx 姓名：xxxxxxx 2011年12 月31 日 实验题目：哈希表 一、要解决的问题 针对同班同学信息设计一个通讯录，学生信息有姓名，学号，电话号码等。以学生姓名为关键字设计哈希表，并完成相应的建表和查表程序。 基本要求：姓名以汉语拼音形式，待填入哈希表的人名约30个，自行设计哈希函数，用线性探测再散列法或链地址法处理冲突；在查找的过程中给出比较的次数。完成按姓名查询的操作。 运行的环境：Microsoft Visual C++ 6.0 二、算法基本思想描述 设计一个哈希表（哈希表内的元素为自定义的结构体）用来存放待填入的30个人名，人名为中国姓名的汉语拼音形式，用除留余数法构造哈希函数，用线性探查法解决哈希冲突。建立哈希表并且将其显示出来。通过要查找的关键字用哈希函数计算出相应的地址来查找人名。通过循环语句调用数组中保存的数据来显示哈希表。 三、设计 1、数据结构的设计和说明 （1）结构体的定义 typedef struct //记录 { NA name; NA xuehao; NA tel; }Record; { Record *elem[HASHSIZE]; //数据元素存储基址 int count; //当前数据元素个数 int size; //当前容量 }HashTable; 哈希表元素的定义，包含数据元素存储基址、数据元素个数、当前容量。 2、关键算法的设计 （1）姓名的折叠处理 long fold(NA s) //人名的折叠处理 { char *p; long sum=0; NA ss; strcpy(ss,s); //复制字符串，不改变原字符串的大小写 strupr(ss); //将字符串ss转换为大写形式 p=ss; while(*p!='\0') sum+=*p++; printf("\nsum====================%d",sum); return sum; } （2）建立哈希表 1、用除留余数法构建哈希函数 2、用线性探测再散列法处理冲突 int Hash1(NA str) //哈希函数 { long n; int m; n=fold(str); //先将用户名进行折叠处理 m=n%HASHSIZE; //折叠处理后的数，用除留余数法构造哈希函数 return m; //并返回模值 }Status collision(int p,int c) //冲突处理函数，采用二次探测再散列法解决冲突{ int i,q; i=c/2+1; while(i 第九章查找 一、选择题 1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为 ( )。【北京航空航天大学 2000 一、8 （2分）】 A． (n-1)/2 B. n/2 C. (n+1)/2 D. n 2. 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( ) 【南京理工大学1998一、7（2分）】 A．（N+1）/2 B. N/2 C. N D. [（1+N）*N ]/2 3. 下面关于二分查找的叙述正确的是 ( ) 【南京理工大学 1996 一、3 （2分）】 A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且只能从小到大排列 B. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储 4. 对线性表进行二分查找时，要求线性表必须（）【燕山大学 2001 一、5 （2分）】 A.以顺序方式存储 B.以顺序方式存储,且数据元素有序 C.以链接方式存储 D.以链接方式存储,且数据元素有序 5．适用于折半查找的表的存储方式及元素排列要求为( ) 【南京理工大学 1997 一、6 （2分）】 A．链接方式存储，元素无序 B．链接方式存储，元素有序 C．顺序方式存储，元素无序 D．顺序方式存储，元素有序 6．当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( ) A．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减 【南京理工大学 1997 一、7 （2分）】 7．当采用分快查找时，数据的组织方式为 ( ) 【南京理工大学 1996 一、7 （2分）】 A．数据分成若干块，每块内数据有序 B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块 C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D. 数据分成若干块，每块（除最后一块外）中数据个数需相同 8. 二叉查找树的查找效率与二叉树的( （1） )有关, 在 (（2） )时其查找效率最低【武汉交通科技大学1996 一、2(4分)】 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。 9. 要进行顺序查找，则线性表（1 ）；要进行折半查询，则线性表（2 ）；若表中元素个数为n,则顺序查找的平均比较次数为 （3 ）；折半查找的平均比较次数为（4H）。【北方交通大学 1999 一、2 （4分）】 （1）（2）：A. 必须以顺序方式存储； B. 必须以链式方式存储；C. 既可以以顺序方式存储，也可以链式方式存储； D. 必须以顺序方式存储，且数据已按递增或递减顺序排好； E. 必须以链式方式存储，且数据已按递增或递减的次序排好。 （3）（4）：A.n B.n/2 C.n*n D.n*n/2 E.log2n F.nlog2n G.(n+1)/2 H.log2(n+1) 10．如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用( )查找法。 A. 分快查找 B. 顺序查找 C. 折半查找 D. 基于属性 【西安电子科技大学 2001应用一、8 （2分）】 11. 既希望较快的查找又便于线性表动态变化的查找方法是 ( ) 【北方交通大学 2000 二、4 （2分）】 A．顺序查找 B. 折半查找 C. 索引顺序查找 D. 哈希法查找 12．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( ) 【合肥工业大学2000一、4（2分）】A．（100，80， 90， 60， 120，110，130） B.（100，120，110，130，80， 60， 90） C.（100，60， 80， 90， 120，110，130） D. (100，80， 60， 90， 120，130，110) 13. 散列表的地址区间为0-17,散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8， 18，59依次存储到散列表中。 （1）元素59存放在散列表中的【北方交通大学 2001 一、（19，20）（4分）】地址是（）。 A． 8 B. 9 C. 10 D. 11 （2）存放元素59需要搜索的次数是（）。 A． 2 B. 3 C. 4 D. 5 14. 将10个元素散列到100000个单元的哈希表中，则（）产生冲突。【北京邮电大学 2001 一、4 （2分）】 A. 一定会 B. 一定不会 C. 仍可能会 15. 设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key） =key MOD 13,散列地址为1的链中有（）个记录。【南京理工大学1997 一、4 （2分）】 A．1 B. 2 C. 3 D. 4 16. 下面关于哈希(Hash，杂凑)查找的说法正确的是( ) 【南京理工大学 1998 一、10 （2分）】 第一章绪论 一、选择题 1.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算等的学科。1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像 2 A.结构 B.关系 C.运算 D.算法 2.数据结构被形式地定义为(K, R)，其中K是1的有限集，R是K上的2有限集。 1 A.算法 B.数据元素 C.数据操作 D.逻辑结构 2 A.操作 B.映像 C.存储 D.关系 3.在数据结构中，从逻辑上可以把数据结构分成。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 4.线性结构的顺序存储结构是一种1的存储结构，线性表的链式存储结构是一种2的存储结构。A.随机存取 B.顺序存取 C.索引存取 D.散列存取 5.算法分析的目的是1，算法分析的两个主要方面其一是指2，其二是指正确性和简单性。1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2 A.空间复杂度和时间复杂度 B.研究算法中的输入和输出的关系 C.可读性和文档性 D.数据复杂性和程序复杂性k 6.计算机算法指的是1，它必须具备输入、输出和2等5个特性。 1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。A.正确 B.不正确 8线性表若采用链式存储结构时，要求内存中可用存储单元的地址。 A.必须连续的 B.部分地址必须连续的 C.一定是不续的D连续不连续都可以 9.以下的叙述中，正确的是。A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。A.正确B.不正确 二、填空题1.数据逻辑结构包括三种类型、和，树形结构和图形结构合称为。2.在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。3.算法的五个重要特性是、、、、。 4.下面程序段的时间复杂度是。 for( i = 0; i < n; i++) for( j = 0; j < m; j++) A[i][j] = 0; 5.下面程序段的时间复杂度是。 i = s = 0; while ( s < n) { i ++; /* i = i +1*/ s += i; /* s = s + i*/ } 6.下面程序段的时间复杂度是。 s = 0; for( i = 0; i < n; i++) for( j = 0; j < n; j++) s += B[i][j]; sum = s; 7.下面程序段的时间复杂度是。 i = 1; while ( i <= n ) i = i * 3; 计算公式： 计算公式是人们在研究自然界物与物之间时发现的一些联系，并通过一定的方式表达出来的一种表达方法。是表征自然界不同事物之数量之间的或等或不等的联系，它确切的反映了事物内部和外部的关系，是我们从一种事物到达另一种事物的依据，使我们更好的理解事物的本质和内涵。 二次再散列法： 散列（Hashing）是计算机科学中一种对资料的处理方法，通过某种特定的函数/算法（称为散列函数/算法）将要检索的项与用来检索的索引（称为散列，或者散列值）关联起来，生成一种便于搜索的数据结构（称为散列表）。二次再散列法是指第一次散列产生哈希地址冲突，为了解决冲突，采用另外的散列函数或者对冲突结果进行处理的方法。 散列表： 设所有可能出现的关键字集合记为U(简称全集)。实际发生(即实际存储)的关键字集合记为K（|K|比|U|小得多）。 散列方法是使用函数h将U映射到表T[0..m-1]的下标上（m=O(|U|)）。这样以U中关键字为自变量，以h为函数的运算结果就是相应结点的存储地址。从而达到在O(1)时间内就可完成查找。 其中： ① h：U→{0，1，2，…，m-1} ，通常称h为散列函数(Hash Function)。散列函数h的作用是压缩待处理的下标范围，使待处理 的|U|个值减少到m个值，从而降低空间开销。 ② T为散列表(Hash Table)。 ③ h(Ki)(Ki∈U)是关键字为Ki结点存储地址(亦称散列值或散列地址)。 ④ 将结点按其关键字的散列地址存储到散列表中的过程称为散列(Hashing) 冲突： 两个不同的关键字，由于散列函数值相同，因而被映射到同一表位置上。该现象称为冲突(Collision)或碰撞。发生冲突的两个关键字称为该散列函数的同义词(Synonym)。 安全避免冲突的条件 最理想的解决冲突的方法是安全避免冲突。要做到这一点必须满足两个条件： ①其一是|U|≤m ②其二是选择合适的散列函数。 这只适用于|U|较小，且关键字均事先已知的情况，此时经过精心设计散列函数h有可能完全避免冲突。 冲突不可能完全避免 通常情况下，h是一个压缩映像。虽然|K|≤m，但|U|>m，故无论怎样设计h，也不可能完全避免冲突。因此，只能在设计h时尽可能使冲突最少。同时还需要确定解决冲突的方法，使发生冲突的同义词能够存储到表中。 第九章IPSec及IKE原理 9.1 IPSec概述 IPSec（IP Security）是IETF制定的为保证在Internet上传送数据的安全保密性能的三层隧道加密协议。IPSec在IP层对IP报文提供安全服务。IPSec协议本身定义了如何在IP数据包中增加字段来保证IP包的完整性、私有性和真实性，以及如何加密数据包。使用IPsec，数据就可以安全地在公网上传输。IPsec提供了两个主机之间、两个安全网关之间或主机和安全网关之间的保护。 IPSec包括报文验证头协议AH（协议号51）和报文安全封装协议ESP（协议号50）两个协议。AH可提供数据源验证和数据完整性校验功能；ESP除可提供数据验证和完整性校验功能外，还提供对IP报文的加密功能。 IPSec有隧道（tunnel）和传送（transport）两种工作方式。在隧道方式中，用户的整个IP 数据包被用来计算AH或ESP头，且被加密。AH或ESP头和加密用户数据被封装在一个新的IP数据包中；在传送方式中，只是传输层数据被用来计算AH或ESP头，AH或ESP头和被加密的传输层数据被放置在原IP包头后面。 9.2 IPSec的组成 IPSec包括AH（协议号51）和ESP（协议号50）两个协议： AH（Authentication Header）是报文验证头协议，主要提供的功能有数据源验证、数据完整性校验和防报文重放功能，可选择的散列算法有MD5（Message Digest ），SHA1（Secure Hash Algorithm）等。AH插到标准IP包头后面，它保证数据包的完整性和真实性，防止黑客截断数据包或向网络中插入伪造的数据包。AH采用了hash算法来对数据包进行保护。AH没有对用户数据进行加密。 ESP（Encapsulating Security Payload）是报文安全封装协议，ESP将需要保护的用户数据进行加密后再封装到IP包中，证数据的完整性、真实性和私有性。可选择的加密算法有DES，3DES等。 9.3 IPSec的安全特点 数据机密性（Confidentiality）：IPSec发送方在通过网络传输包前对包进行加密。 数据完整性（Data Integrity）：IPSec接收方对发送方发送来的包进行认证，以确保数据在传输过程中没有被篡改。 hashing定义了一种将字符组成的字符串转换为固定长度(一般是更短长度)的数值或索引值 的方法，称为散列法，也叫哈希法。由于通过更短的哈希值比用原始值进行数据库搜索更快，这种方法一般用来在数据库中建立索引并进行搜索，同时还用在各种解密算法中。 设所有可能出现的关键字集合记为u(简称全集)。实际发生(即实际存储)的关键字集合记为k（|k|比|u|小得多）。|k|是集合k中元素的个数。 散列方法是使用函数hash将u映射到表t[0..m-1]的下标上（m=o(|u|)）。这样以u中关键字为自变量，以h为函数的运算结果就是相应结点的存储地址。从而达到在o(1)时间内就可完成查找。 其中： ①hash：u→{0，1，2，…，m-1} ，通常称h为散列函数(hash function)。散列函数h 的作用是压缩待处理的下标范围，使待处理的|u|个值减少到m个值，从而降低空间开销。 ②t为散列表(hash table)。 ③hash(ki)(ki∈u)是关键字为ki结点存储地址(亦称散列值或散列地址)。 ④将结点按其关键字的散列地址存储到散列表中的过程称为散列(hashing). 比如：有一组数据包括用户名字、电话、住址等，为了快速的检索，我们可以利用名字作为关键码，hash规则就是把名字中每一个字的拼音的第一个字母拿出来，把该字母在26个字母中的顺序值取出来加在一块作为改记录的地址。比如张三，就是z+s＝26+19＝45。就是把张三存在地址为45处。 但是这样存在一个问题，比如假如有个用户名字叫做：周四，那么计算它的地址时也是z+s＝45，这样它与张三就有相同的地址，这就是冲突，也叫作碰撞！ 冲突：两个不同的关键字，由于散列函数值相同，因而被映射到同一表位置上。该现象称为冲突(collision)或碰撞。发生冲突的两个关键字称为该散列函数的同义词(synonym)。 冲突基本上不可避免的，除非数据很少，我们只能采取措施尽量避免冲突，或者寻找解决冲突的办法。影响冲突的因素 冲突的频繁程度除了与h相关外，还与表的填满程度相关。 设m和n分别表示表长和表中填人的结点数，则将α=n/m定义为散列表的装填因子(load factor)。α越大，表越满，冲突的机会也越大。通常取α≤1。 散列函数的构造方法： 1、散列函数的选择有两条标准：简单和均匀。 简单指散列函数的计算简单快速； 均匀指对于关键字集合中的任一关键字，散列函数能以等概率将其映射到表空间的任何一个位置上。也就是说，散列函数能将子集k随机均匀地分布在表的地址集{0，1，…，m-1}上，以使冲突最小化。 2、常用散列函数 （1）直接定址法：比如在一个0～100岁的年龄统计表，我们就可以把年龄作为地址。 （2）平方取中法 单向散列函数算法（Hash算法）： 一种将任意长度的消息压缩到某一固定长度（消息摘要）的函数（过程不可逆），常见的单向散列算法有MD5,SHA.RIPE-MD,HAVAL,N-Hash 由于Hash函数的为不可逆算法，所以软件智能使用Hash函数作为一个加密的中间步骤 MD5算法： 即为消息摘要算法（Message Digest Algorithm），对输入的任意长度的消息进行预算，产生一个128位的消息摘要 简易过程： 1、数据填充..即填出消息使得其长度与448（mod 512）同余，也就是说长度比512要小64位（为什么数据长度本身已经满足却仍然需要填充？直接填充一个整数倍） 填充方法是附一个1在后面，然后用0来填充.. 2、添加长度..在上述结果之后附加64位的消息长度，使得最终消息的长度正好是512的倍数.. 3、初始化变量..用到4个变量来计算消息长度（即4轮运算），设4个变量分别为A,B,C,D（全部为32位寄存器）A=1234567H,B=89abcdefH,C=fedcba98H,D=7654321H 4、数据处理..首先进行分组，以512位为一个单位，以单位来处理消息.. 首先定义4个辅助函数，以3个32为双字作为输入，输出一个32为双字 F(X,Y,Z)=(X&Y)|((~X)&Z) G(X,Y,Z)=(X&Z)|(Y&(~Z)) H(X,Y,Z)=X^Y^Z I(X,Y,Z)=Y^(X|(~Z)) 其中，^是异或操作 这4轮变换是对进入主循环的512为消息分组的16个32位字分别进行如下操作： （重点）将A,B,C,D的副本a,b,c,d中的3个经F,G,H,I运算后的结果与第四个相加，再加上32位字和一个32位字的加法常数（所用的加法常数由这样一张表T[i]定义，期中i为1至64之中的值，T[i]等于4294967296乘以abs(sin(i))所得结果的整数部分）（什么是加法常数），并将所得之值循环左移若干位（若干位是随机的？？），最后将所得结果加上a,b,c,d之一（这个之一也是随机的？）（一轮运算中这个之一是有规律的递增的..如下运算式），并回送至A,B,C,D，由此完成一次循环。（这个循环式对4个变量值进行计算还是对数据进行变换？？） For i=0 to N/16 do For j=0 to 15 do Set X[i] to M[i*16+j] End AA = A BB=B CC=C DD=D //第一轮，令[ABCD K S I]表示下面的操作： //A=B+((A+F(B,C,D)+X[K]+T[I])<< 南昌航空大学实验报告 课程名称：数据结构实验名称：实验九查找 班级：学生姓名：学号： 指导教师评定：签名: 题目：编程实现哈希表的造表和查找算法。 要求：用除留余数法构造哈希函数，用二次探测再散列解决冲突。 一、需求分析 1.用户可以根据自己的需求输入一个顺序表（哈希表） 2.通过用除留余数法构造哈希函数，并用开放地址的二次探测再散列解决冲突。 3.在经过排序后显示该哈希表。 4.程序执行的命令包括： （1）创建哈希表（2）输出哈希表（3）二次探测再散列解决冲突 二、概要设计 ⒈为实现上述算法，需要顺序表的抽象数据类型： ADT Hash { 数据对象D：D是具有相同特征的数据元素的集合。各数据元素均含有类型相同，可唯一标识数据元素的关键字。 数据关系R：数据元素同属一个集合。 基本操作P: Creathash(&h) 操作结果：构造一个具有n个数据元素的哈希查找表h。 destroyhash(&h) 初始条件：哈希查找表h存在。 操作结果：销毁哈希查找表h。 displayhash（h） 初始条件：哈希查找表h存在。 操作结果：显示哈希查找表h。 hash(h，&k) 初始条件：哈希查找表h存在。 操作结果：通过除留余数法得到地址用k返回。 hash2 (i，&k) 初始条件：哈希查找表h存在存在，i是除留余数法得到的地址。 操作结果：返回二次探测再散列解决冲突得到的地址k。 search (h，key) 初始条件：哈希查找表h存在。 操作结果：查找表h中的key，若查找成功，返回其地址，否则返回 -1 insert (&h，key) 初始条件：哈希查找表h存在。 操作结果：若表h中没有key，则在h中插入key。 search1(h, key,&p) 初始条件：哈希查找表h存在。 操作结果：在表h中查找key，若没有，则返回p的插入的地址，否 则返回-1。 }ADT Hash 2. 本程序有三个模块： ⑴主程序模块 main(){ 初始化； { 接受命令； 显示结果； ｝ ｝ ⑵创建hash表的模块：主要建立一个哈希表； ⑶解决冲突模块：利用开放地址的二次探测再散列解决冲突； (4)输出哈希表模块：显示已创建哈希表。 三、详细设计 ⒈元素类型，结点类型 typedef struct { int key; }keytype; typedef struct { keytype elem[100]; int length; /*当前的长度*/ int size; /*哈希表的总长*/ }hashtable; /*全局变量*/ int a=0,b=0; /*哈希函数*/ 2.对抽象数据类型中的部分基本操作的伪码算法如下： /*哈希函数*/ int hash(hashtable *h,int k) { return k%h->size; } 第九章作业 一、选择题 1. 顺序查找算法适用于( )。 A. 线性表 B. 查找树 C. 查找网 D. 连通图 2. 顺序查找法适用于线性表的( )。 A.散列存储 B.压缩存储 C. 索引存储 D. 顺序或链接存储 3. 采用顺序查找方式查找长度为n 的顺序表时，平均查找长度为( ) A. n B. 2/n C. 2/)1(+n D. 2/)1(-n 4. 如果有5个关键吗{a,b,c,d,e }放在顺序表中，他们的查找概率分别为{,,,.015,}，可使平均查找长度达到 最小的存放方式是( )。 A. d,a,b,c,e B. e,d,c,b,a C. a,b,c,d,e D. a,c,e,d,b 5. 对于长度为n 的有序单链表，若查找每个元素的概率相等，则顺序查找表中任一元素的查找成功的平 均查找长度为( ) A. 4/n B. 2/n C. 2/)1(+n D. 2/)1(-n 6. 对线性表进行折半查找时，要求线性表必须( ) A. 以顺序方式存储 B. 以链接方式存储 C. 以顺序方式存储，且结点按关键吗有序排列 D. 以链接方式存储，且结点按关键吗有序排列 7. 采用折半查找法查找长度为n 的有序顺序表时，平均查找长度为( ) A. )(n O B. )(log 2n O C. )(2n O D. )log (n n O 8. 对于长度为18的有序顺序表，若采用折半查找，则查找第15个元素的查找次数为( )。 A. 3 B. 4 C. 5 D. 6 9. 已知有序顺序表(13,18,24,35,47,50,62,83,90,115,134)，若采用折半查找法查找值为18的元素时，查找 成功的数据比较次数为( )。 A. 1 B. 2 C. 3 D. 4 10. 使用散列法时确定元素存储地址的依据是( )。 A. 元素的序号 B. 元素个数 C. 关键吗 D. 非码属性 11. 设一个散列表中有n 个元素，用散列法进行查找的平均查找长度是( )。 A. )1(O B. )(n O C. )log (2n O D. )(2n O 12. 使用散列函数将元素的关键吗映射为散列地址时，常会发生冲突。此时的冲突是指( )。 A. 两个元素具有相同的序号 B. 两个元素的关键码不同，而非关键码相同 C. 不同关键码对应到相同的存储地址 D. 装载因子过大，数据元素过多 13. 计算出的地址分布最均匀的散列函数是( )。 A. 数值分析法 B. 除留余数法 C. 平方取中法 D. 折叠法 14. 将10个元素散列到大小为100000个元素的散列表中，( )产生冲突。 A. 一定会 B. 一定不会 C. 仍可能会 D. 以上都不对 15. 采用线性探测法解决冲突时计算出的一系列“下一个空位”( )。 A. 必须大于等于原散列地址 B. 必须小于等于原散列地址 C. 可以大于或小于但不等于原散列地址 D. 对地址在何处没有限制 16. 包含有4个结点的元素值互不相同的二叉查找树有( )棵。 A. 4 B. 6 C. 10 D. 14 17. 利用逐个数据插入的方法建立序列{35,45,25,55,50,10,15,30,40,20}对应的二叉查找树后，查找元素20 需要进行( )次元素之间的比较。 A. 4 B. 5 C. 7 D. 10 18. 一颗高度为h 的AVL 树，若其每个非叶子结点的平衡因子都是0，则该树共有( )个结点。 A. 121--h B. 12-h C. 121+-h D. 12-h 浅析散列函数MD5算法的原理及其碰撞攻击 摘要随着网络技术的广泛应用，网络信息安全越来越引起人们的重视。针对数据在存储时存在大量的安全问题，目前通常将需要存储的数据进行加密然后再存储，应用MD5算法是一个不错的选择。本文详细介绍了MD5算法的概念，对MD5算法的原理、碰撞攻击以及MD5算法破解的重要意义进行探讨。 关键字：MD5 原理碰撞攻击 一、引言 现阶段，信息安全性已成为全社会共同关心的问题，密码学研究也越来越被人们所关注。密码学主要研究的是通讯保密。近年来，密码学研究之所以十分活跃，主要原因是它与计算机科学的蓬勃发展息息相关。由于公共和私人的一些机构越来越多的应用电子数据处理，将数据存储在数据库中，因此防止非法泄露、删除、修改等是必须重视的问题。对数据进行加密能够防止他人盗取需要保密的信息，但这只解决了一方面的问题，至于如何防止他人对重要数据进行破坏，如何确定交易者的身份，以及如何防止日后发生纠纷时交易者抵赖，还需要采取其它的手段，这一手段就是数字签名。数字签名技术实际上是在数据加密技术基础上的一种延伸的应用。数字签名经常和单向散列(Hash)函数一起使用，而单向散列(Hash)函数是现代密码学的核心。最常见的散列算法有MD5，SHA和Snefru，MD5是当今非常流行的Hash加密技术，因而本文选取MD5作为研究对象，详细介绍了MD5算法的概念，对MD5算法的原理、碰撞攻击以及MD5算法破解的重要意义进行探讨。 二、MD5算法的概念 MD5的全称是Message -Digest Algorthm 5(信息--摘要算法), 即将任意长度的“字节串”变换成一个128bit的大整数, 是一种不可逆的字符串变换算法。通过数学运算,把不同长度的信息转化到128位编码中,形成Hash值, 通过比较该数值是否正确,来确定通信双方的合法性, 即数字签名功能。在数据传输后, 可以通过比较Hash值来判断信息途中是否被截获修改, 是否由合法的发送人发 实验课程名称：电子商务安全管理实验项目名称1:DES 、RSA 和Hash 算法的实现实验成绩 试验者 王秀梅专业班级1105441 组别同组者无实验的目的 (1) 掌握常用加密处理软件的使用方法。 (2) 理解DES 、RSA 和Hash 算法的原理。 (3) 了解MD5算法的破解方法。实验环境 (1) 装有Windows XP/2003操作系统的PC 机1台。 (2) MixedCS 、RSATool 、DAMN_HashCalc 、MD5Crack 工具软件各1套。实验步骤1、请参考实验指导PPT 。并在最后写实验心得体会。2、将实验电子版提交FTP——1105441电子商务安全管理——第一次实验报告，文件名为“学号（1105441）+姓名+实验一”。 实验过程记录 (1) 对称加密算法DES 的实现 步骤1：双击运行MixedCS.exe 程序，打开的程序主界面步骤2：单击“浏览文件”按钮，选择要进行DES 加密的源文件，选择完成后在“输出文件”文本框中会自动出现默认的加密后的文件名。步骤3：选中“DES 加密”单选按钮，在“DES 密钥”文本框中输入5个字符 (区分大小、管路敷设技术通过管线敷设技术，不仅可以解决吊顶层配置不规范问题，而且可保障各类管路习题到位。在管路敷设过程中，要加强看护关于管路高中资料试卷连接管口处理高中资料试卷弯扁度固定盒位置保护层防腐跨接地线弯曲半径标高等，要求技术交底。管线敷设技术中包含线槽、管架等多项方式，为解决高中语文电气课件中管壁薄、接口不严等问题，合理利用管线敷设技术。线缆敷设原则：在分线盒处，当不同电压回路交叉时，应采用金属隔板进行隔开处理；同一线槽内，强电回路须同时切断习题电源，线缆敷设完毕，要进行检查和检测处理。、电气课件中调试对全部高中资料试卷电气设备，在安装过程中以及安装结束后进行高中资料试卷调整试验；通电检查所有设备高中资料试卷相互作用与相互关系，根据生产工艺高中资料试卷要求，对电气设备进行空载与带负荷下高中资料试卷调控试验；对设备进行调整使其在正常工况下与过度工作下都可以正常工作；对于继电保护进行整核对定值，审核与校对图纸，编写复杂设备与装置高中资料试卷调试方案，编写重要设备高中资料试卷试验方案以及系统启动方案；对整套启动过程中高中资料试卷电气设备进行调试工作并且进行过关运行高中资料试卷技术指导。对于调试过程中高中资料试卷技术问题，作为调试人员，需要在事前掌握图纸资料、设备制造厂家出具高中资料试卷试验报告与相关技术资料，并且了解现场设备高中资料试卷布置情况与有关高中资料试卷电气系统接线等情况，然后根据规范与规程规定，制定设备调试高中资料试卷方案。 、电气设备调试高中资料试卷技术电力保护装置调试技术，电力保护高中资料试卷配置技术是指机组在进行继电保护高中资料试卷总体配置时，需要在最大限度内来确保机组高中资料试卷安全，并且尽可能地缩小故障高中资料试卷破坏范围，或者对某些异常高中资料试卷工况进行自动处理，尤其要避免错误高中资料试卷保护装置动作，并且拒绝动作，来避免不必要高中资料试卷突然停机。因此，电力高中资料试卷保护装置调试技术，要求电力保护装置做到准确灵活。对于差动保护装置高中资料试卷调试技术是指发电机一变压器组在发生内部故障时，需要进行外部电源高中资料试卷切除从而采用高中资料试卷主要保护装置。数据结构实验 散列表实验报告
第9章作业
哈希表实验报告完整版
数据结构 第九章 查找 作业及答案
哈希算法散列
数据结构课程设计--哈希表实验报告
习题第九章查找(1)
数据结构作业及答案
双重散列探查法的计算公式
第九章 IPSec及IKE原理
HASH表
单向散列函数算法Hash算法
哈希查找_数据结构实验报告
第9章作业
浅析散列函数MD5算法的原理及其碰撞攻击
【免费下载】hash算法实验