散列法实验研究源代码

题目：顺序表的实现一、实验题目顺序表的实现二、实验目的⑴掌握线性表的顺序存储结构；⑵验证顺序表及其基本操作的实现；⑶理解算法与程序的关系，能够将顺序表算法转换为对应的程序。

三、实验内容与实现⑴建立含有若干个元素的顺序表；⑵对已建立的顺序表实现插入、删除、查找等基本操作。

实验实现#include<stdio.h>#include<memory.h>int a[10000];int arrlong(){int j;for(j=0;j<12;j++)if(a[j]==0)break;return j;}int Insect(int n,int s) ////插入{int j;for(j=0;j<10000;j++)if(a[j]==0)break;printf("要操作的元素\n");for(int i=0;i<j;i++)printf("%d ",a[i]);printf("\n");for(int i=j;i>n-1;i--)a[i+1]=a[i];a[n]=s;for(int k=0;k<j+1;k++)printf("%d ",a[k]);printf("\n");}int Search(int p) //查找{int j,h;for(j=0;j<12;j++){if(a[j]==0)break;}for(h=0;h<j;h++){if(a[h]==p){printf("查找到的数在第%d位\n",h+1);break;}}if(h==j)printf("查无此数\n");}int Delate(int g,int q) //删除{int j;g=g-1;for(int j=g;j<12;j++)a[j]=a[j+1];for(q =0;q<12;q++){if(a[q]==0)break;}for(int i=0;i<q;i++)printf("%d ",a[i]);printf("\n");}int main(){int y,c;printf(" 菜单\n");printf("-------------------------------------------------\n");printf("0 建表\n1 插入\n2 查找\n3 删除\n4 退出\n");printf("-------------------------------------------------\n");while(scanf("%d",&y)!=EOF){int n,x,s;if(y==0){memset(a,0,sizeof(a));printf("请输入元素的个数:\n");scanf("%d",&c);printf("请输入数据:\n");for(int i = 0;i < c;i++)scanf("%d",&a[i]);}else if(y==1){int L;printf("请输入插入的第几位\n");scanf("%d",&n);//输入L=arrlong();if(n<=L){printf("请输入插入的数字\n");scanf("%d",&s);Insect(n,s);}else{printf("输入有误\n");continue;}}else if(y==2){int p;printf("请输入要查找的数字\n");scanf("%d",&p);Search(p);}else if(y==3){int g,q,L;printf("请输入要删除数的位置\n");scanf("%d",&g);L=arrlong();if(L>=g){Delate(g,q);}else{printf("输入有误\n");printf(" 菜单\n");printf("-------------------------------------------------\n");printf("0 建表\n1 插入\n2 查找\n3 删除\n4 退出\n");printf("-------------------------------------------------\n");continue;}}else if(y==4)break;else{printf("输入有误\n");printf(" 菜单\n");printf("-------------------------------------------------\n");printf("0 建表\n1 插入\n2 查找\n3 删除\n4 退出\n");printf("-------------------------------------------------\n");continue;}printf(" 菜单\n");printf("-------------------------------------------------\n");printf("0 建表\n1 插入\n2 查找\n3 删除\n4 退出\n");printf("-------------------------------------------------\n");}}建立顺序表：插入操作：查找操作：删除操作：插入数据超出顺序表范围：查找不到输入数据：删除数据超出顺序表范围：四、实验心得1.掌握了为数组赋值的方法，深刻理解了数组的含义2.掌握了为数组排序的方法。

山东大学计算机科学与技术学院数据结构课程实验报告了Input函数和Output函数。

对问题三，仿课本所述，定义Term类作为SparseMatrix类的友元类，包含行、列、值三个要素的成员变量，用Term类的数组实现稀疏矩阵的行主映射存储。

查找行为的实现方式是，找到位于目标元素前一行的最后一个元素，再从这个元素开始向下搜索，直到找到和目标元素同一行但是列数小于目标元素的元素a[k-1]，然后决定下一步的行为————插入一个新项Term作为a[k]并将已有元素向后移位，还是修改已存在的项a[k]。

以此原理编写了Store和Retrieve函数，并扩展编写了Input函数和Output函数。

对问题四，仿照课本例子编写了有序链表类SortedChain、开放寻址的散列表类HashTable、基于有序链表链接的散列表类ChainHashTable，并对这三个类分别扩展编写了Output函数。

3.测试结果（测试输入，测试输出）问题一：问题二：上图显示了输入不符合下三角方阵约束时，抛出异常并退出程序。

上图是正常运行的结果。

问题三：普通的输入和输出操作如下：矩阵相加：矩阵转置：问题四：以上图的数据为例。

从346就应该在链表链接的散列表上看到开放寻址解决冲突的例子。

返回开放寻址的输出段，可以看到符合预期的结果：4.实现源代码（程序风格清晰易理解，有充分的注释）/** TridiagonalMatrix.h** Created on: Nov 22, 2015* Author: xudp*/#ifndef TRIDIAGONALMATRIX_H_#define TRIDIAGONALMATRIX_H_#include<iostream>using namespace std;template<class T>class TridiagonalMatrix {public:// 1、创建三对角矩阵类,采用按列映射方式,提供 store 和 retrieve 方法。

数据结构课程设计-散列法的研究大全第一篇：数据结构课程设计-散列法的研究大全学院：班级：完成人：姓指导教师：数据结构课程设计说明书信息科学与工程学院计算机科学与技术名：学号：山东科技大学 2013年12月25日课程设计任务书一、课程设计题目：散列法的实验研究二、课程设计应解决的主要问题：（1）数据元素的输入和输出（2）线性再散列法建立哈希表（3）二次探测再散列法建立哈希表（4）链地址法建立哈希表（5）线性再散列法进行数据查找（6）二次探测再散列法进行数据查找（7）链地址法进行数据查找（8）退出系统三、任务发出日期： 2013-10-01 课程设计完成日期： 2013-12-20小组分工说明小组编号 7 题目：散列法的实验研究小组分工情况：一人独立完成所有工作。

组长签字： 2013 年 12 月 31 日指导教师对课程设计的评价成绩：指导教师签字：年月日目录1．需求分析说明2．概要设计说明3．详细设计说明4．调试分析5．用户使用说明6．课程设计总结7．测试结果8．参考书目-3-4-5-7-8-10-10-12需求分析说明内部排序教学软件的总体功能要求：散列法中，散列函数构造方法多种多样，同时对于同一散列函数解决冲突的方法也可以不同。

两者是影响查询算法性能的关键因素。

对于几种典型的散列函数构造方法，做实验观察，不同的解决冲突方法对查询性能的影响。

基本功能如下：（1）界面友好，易与操作。

采用菜单方式进行选择。

（2）实现三种方法进行哈希表的构造。

包括线性再散列法、二次探测再散列法和链地址法。

（3）根据三种构造方法分别进行数据元素的查找，若查找成功，则同时输出探查/冲突次数。

以下是各功能模块的功能描述： 1．主函数模块本模块的主要功能是初始化图形界面，调用各模块，实现功能。

2．构造哈希表子模块本模块的主要功能是采用线性再散列法、二次探测再散列法、链地址法三种方法构造哈希表。

3．查找功能及输出子模块本模块的主要功能是在采用线性再散列法、二次探测再散列法、链地址法三种方法构造哈希表后，采用相应的方法对键入的数据进行查找，并计算探查/冲突次数。

散列表实验报告(不同装载因子下链表法和放寻址法对比)TOC \o “1-4“ \h \z \u 1 概述22 原理介绍22.1 散列表介绍22.2 直接寻址表32.3 散列函数32.3.1 除法散列42.3.2 乘法散列42.3.3 全域散列42.4 解决碰撞问题52.4.1 链接法52.4.2 开放寻址法52.4.2.1 线性探查62.4.2.2 二次探查62.4.2.3 双重散列73 算法说明73.1 概述73.2 使用链接法解决碰撞问题83.2.1 算法思想83.2.2 伪代码描述93.2.3 算法分析与证明103.3 使用开放寻址法的双重散列解决碰撞问题123.3.1 算法思想123.3.2 伪代码描述123.3.3 算法分析与证明143.4 两个算法的比较144 实验设计与分析165 C++实现与结果分析185.1 C++实现与结果185.2 结果分析266 实验总结和感想27概述该实验报告主要是通过介绍散列表的各种技术，包括散列函数、解决碰撞的机制等技术，并对两种解决碰撞的机制：链接法和开放寻址法进行分析和证明，并通过实验分析两者在不同的规模下的运行时间和空间占用的对比，来证明在“算法说明”一章中的理论分析。

原理介绍散列表介绍散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。

也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。

这个映射函数叫做散列函数，存放记录的数组叫做散列表。

它实际上是是普通数组概念的推广，因为可以对数组进行直接寻址，故可以而在O(1)时间内访问数组的任意元素。

如果存储空间允许，我们可以提供一个数组，为每个可能的关键字保留一个位置，就可以应用直接寻址技术。

基本概念若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上。

由此，不需比较便可直接取得所查记录。

称这个对应关系f为散列函数(Hash function)，按这个思想建立的表为散列表。

实验课题：做这个实验时采用Open Addressing框架，也可加做Separate Chaining以形成比较。

1 构造散列表，把字符串数组中的各项加入到散列表中string MyBirds[13] = { "robin", "sparrow", "hawk", "eagle", "seagull", "bluejay","owl", "cardinal", "Jakana", "Moa", "Egret", "Penguin", "hawk" };用C表示，可以是char * MyBirds[13] = { "robin", "sparrow", "hawk", "eagle", "seagull", "bluejay","owl", "cardinal", "Jakana", "Moa", "Egret", "Penguin", "hawk" };为便于观察冲突现象，初始构造散列表时，表的容量不要过大，对Open Addressing，装载因子为0.5左右，对于Separate Chaining，装载因子为1左右即可。

也不要做rehash（应该改源代码的哪里，如何改）。

建议对源代码做些改动、增加一些输出（建议用条件编译控制这些输出），以便于观察冲突的发生和解决；对于Open Addressing，参考代码的冲突解决方案是用的平方探测（quadratic probing），如果用线性探测（linear probing）的策略，应该对函数findPos做什么修改（冲突解决的策略都集中在那里）？2 观察不同的散列函数产生冲突散列地址的情况教科书上给了3个以字符串作输入的散列函数（两教科书第3个不一样），观察记录它们产生冲突散列地址的情况，写入你的实验报告。

数据结构实验散列表实验报告一、实验目的本次实验的主要目的是深入理解和掌握散列表这种数据结构的基本原理、实现方法以及其在实际应用中的性能特点。

通过实际编写代码和进行相关测试，提高对散列表的操作能力，并能够分析和解决在使用散列表过程中可能遇到的问题。

二、实验原理散列表（Hash Table）是一种根据关键码值（Key value）而直接进行访问的数据结构。

通过一个特定的函数（哈希函数）将关键码映射到表中的一个位置来访问记录，以加快查找的速度。

这个映射函数称为哈希函数，存放记录的数组称为哈希表。

哈希函数的设计至关重要，它需要尽可能地将不同的关键码值均匀地分布在哈希表中，以减少冲突的发生。

常见的哈希函数有直接定址法、除留余数法、数字分析法等。

冲突解决方法也是散列表中的重要部分。

当不同的关键码通过哈希函数映射到相同的位置时，就会产生冲突。

常见的冲突解决方法有开放定址法（线性探测、二次探测等）和链地址法。

三、实验环境本次实验使用的编程语言为C+＋，开发工具为Visual Studio 2019。

四、实验内容1、哈希函数的实现采用除留余数法实现哈希函数。

代码如下：｀｀｀cppint hashFunction(int key, int tableSize) ｛return key ％ tableSize;｝｀｀｀2、散列表的创建与初始化使用动态数组创建散列表，并将所有位置初始化为空。

｀｀｀cppclass HashTable ｛private:int table;int size;public:HashTable(int tableSize) ｛size ＝ tableSize;table ＝ new intsize;for （int i ＝ 0; i ＜ size; i+＋）｛tablei ＝－1; ／／－1 表示为空｝｝～HashTable(）｛delete table;｝｝；｀｀｀3、数据插入操作采用线性探测法解决冲突。

用Java语言实现的安全散列算法SHA的源代码：import java.io.*;import java.util.*;public class SHA1 {private final int[] abcde = { 0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476, 0xc3d2e1f0 };private int[] digestInt = new int[5];private int[] tmpData = new int[80];private int process_input_bytes(byte[] bytedata) { System.arraycopy(abcde, 0, digestInt, 0, abcde.length);byte[] newbyte = byteArrayFormatData(bytedata);int MCount = newbyte.length / 64;for (int pos = 0; pos < MCount; pos++) {for (int j = 0; j < 16; j++) {tmpData[j] = byteArrayToInt(newbyte, (pos * 64) + (j * 4)); }encrypt(); }return 20; }private byte[] byteArrayFormatData(byte[] bytedata) {int zeros = 0;int size = 0;int n = bytedata.length;int m = n % 64;if (m < 56) {zeros = 55 - m;size = n - m + 64;} else if (m == 56) {zeros = 63;size = n + 8 + 64;} else {zeros = 63 - m + 56;size = (n + 64) - m + 64; }byte[] newbyte = new byte[size];System.arraycopy(bytedata, 0, newbyte, 0, n);int l = n;newbyte[l++] = (byte) 0x80;for (int i = 0; i < zeros; i++) {newbyte[l++] = (byte) 0x00; }long N = (long) n * 8;byte h8 = (byte) (N & 0xFF);byte h7 = (byte) ((N >> 8)& 0xFF);byte h6 = (byte) ((N >> 16) & 0xFF);byte h5 = (byte) ((N >> 24) & 0xFF);byte h4 = (byte) ((N >> 32) & 0xFF);byte h3 = (byte) ((N >> 40) & 0xFF);byte h2 = (byte) ((N >> 48) & 0xFF);byte h1 = (byte) (N >> 56);newbyte[l++] = h1;newbyte[l++] = h2;newbyte[l++] = h3;newbyte[l++] = h4;newbyte[l++] = h5;newbyte[l++] = h6;newbyte[l++] = h7;newbyte[l++] = h8;return newbyte; }private int f1(int x, int y, int z) {return (x & y) | (~x & z); }private int f2(int x, int y, int z) {return x ^ y ^ z; }private int f3(int x, int y, int z) {return (x & y) | (x & z) | (y & z); } private int f4(int x, int y) {return (x << y) | x >>> (32 - y); }private void encrypt() {for (int i = 16; i <= 79; i++) {tmpData[i] = f4(tmpData[i - 3] ^ tmpData[i - 8] ^ tmpData[i - 14] ^tmpData[i - 16], 1); }int[] tmpabcde = new int[5];for (int i1 = 0; i1 < tmpabcde.length; i1++) {tmpabcde[i1] = digestInt[i1]; }for (int j = 0; j <= 19; j++) {int tmp = f4(tmpabcde[0], 5) +f1(tmpabcde[1], tmpabcde[2], tmpabcde[3]) + tmpabcde[4] +tmpData[j] + 0x5a827999;tmpabcde[4] = tmpabcde[3];tmpabcde[3] = tmpabcde[2];tmpabcde[2] = f4(tmpabcde[1], 30);tmpabcde[1] = tmpabcde[0];tmpabcde[0] = tmp; }for (int k = 20; k <= 39; k++) {int tmp = f4(tmpabcde[0], 5) +f2(tmpabcde[1], tmpabcde[2], tmpabcde[3]) + tmpabcde[4] +tmpData[k] + 0x6ed9eba1;tmpabcde[4] = tmpabcde[3];tmpabcde[3] = tmpabcde[2];tmpabcde[2] = f4(tmpabcde[1], 30);tmpabcde[1] = tmpabcde[0];tmpabcde[0] = tmp; }for (int l = 40; l <= 59; l++) {int tmp = f4(tmpabcde[0], 5) +f3(tmpabcde[1], tmpabcde[2], tmpabcde[3]) + tmpabcde[4] +tmpData[l] + 0x8f1bbcdc;tmpabcde[4] = tmpabcde[3];tmpabcde[3] = tmpabcde[2];tmpabcde[2] = f4(tmpabcde[1], 30);tmpabcde[1] = tmpabcde[0];tmpabcde[0] = tmp; }for (int m = 60; m <= 79; m++) {int tmp = f4(tmpabcde[0], 5) +f2(tmpabcde[1], tmpabcde[2], tmpabcde[3]) + tmpabcde[4] +tmpData[m] + 0xca62c1d6;tmpabcde[4] = tmpabcde[3];tmpabcde[3] = tmpabcde[2];tmpabcde[2] = f4(tmpabcde[1], 30);tmpabcde[1] = tmpabcde[0];tmpabcde[0] = tmp; }for (int i2 = 0; i2 < tmpabcde.length; i2++) {digestInt[i2] = digestInt[i2] + tmpabcde[i2]; }for (int n = 0; n < tmpData.length; n++) {tmpData[n] = 0; } }private int byteArrayToInt(byte[] bytedata, int i) {return ((bytedata[i] & 0xff) << 24) | ((bytedata[i + 1] & 0xff) << 16) |((bytedata[i + 2] & 0xff) << 8)| (bytedata[i + 3] & 0xff); }private void intToByteArray(int intValue, byte[] byteData, int i) {byteData[i] = (byte) (intValue >>> 24);byteData[i + 1] = (byte) (intValue >>> 16);byteData[i + 2] = (byte) (intValue >>> 8);byteData[i + 3] = (byte) intValue; } private static String byteToHexString(byte ib) { char[] Digit = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F' };char[] ob = new char[2];ob[0] = Digit[(ib >>> 4) & 0X0F];ob[1] = Digit[ib & 0X0F];String s = new String(ob);return s; }private static String byteArrayToHexString(byte[] bytearray) {String strDigest = "";for (int i = 0; i < bytearray.length; i++) {strDigest += byteToHexString(bytearray[i]); }return strDigest; }public byte[] getDigestOfBytes(byte[] byteData) {process_input_bytes(byteData);byte[] digest = new byte[20];for (int i = 0; i < digestInt.length; i++) {intToByteArray(digestInt[i], digest, i * 4); }return digest; }public String getDigestOfString(byte[] byteData) {returnbyteArrayToHexString(getDigestOfBytes(byteData)); }public static void main(String[] args) {String data;Scanner sc = new Scanner(System.in);System.out.println("请输入明文内容:");data = sc.nextLine();System.out.println("\n确认内容:");System.out.println(data);System.out.println("\nSHA-1:");String digest = new SHA1().getDigestOfString(data.getBytes());System.out.println(digest); } }。

散列数据结构代码（线性探测法和拉链法）线性探测法1//使⽤线性探测法和数组结构创建散列表，2//然后输⼊数据的查询。

并且将创建过程3//都输出来4 #include <stdlib.h>5 #include <stdio.h>6 #include <time.h>7#define MAX 10 //最⼤数组容量8#define NUM 8 //随机数⽣成的个数9#define BLANK -1 //空⽩空间1011int hashtable[MAX]; //散列表声明1213//散列函数14int hashfunc(int value)15 {16return value % MAX; //余数17 }1819//线性探测法20int linehash(int key)21 {22int pos; //位置变量23int temp;2425 pos = hashfunc(key);26 temp = pos; //保留开始位置27while(hashtable[temp] != key && //线性探测循环28 hashtable[temp] != BLANK)29 {30//使⽤余数将数组变为环状31 temp = (temp + 1) % MAX; //下⼀个位置32if(pos == temp) //查询结束33return -1; //没有找到34 }35if(hashtable[temp] == BLANK) //是否空⽩36return -1;37else38return temp; //找到了39 }404142//创建散列表43void createtable(int key)44 {45int pos; //位置变量46int temp;47//调⽤散列函数计算位置48 pos = hashfunc(key);49 temp = pos; //保留开始位置50while(hashtable[temp] != BLANK) //找寻存⼊位置51 {52 temp = (temp + 1) % MAX; //下⼀个位置53if(pos == temp) //散列表是否已满54 {55 printf("散列表已满！\n");56return;57 }58 }59 hashtable[temp] = key; //存⼊散列表60 }616263//主程序：散列查找法64int main()65 {66int checked[50]; //检查数组67int i,j,temp;68long temptime;69for(i = 0;i < MAX;i++)70 hashtable[i] = BLANK; //清除散列表71for(i = 0;i < 50;i++)72checked[i] = 0; //清楚检查数组7374 printf("散列表内容：\n");75 srand(time(&temptime) % 60); //使⽤时间初始随机数76 i = 0;77while(i != NUM) //⽣成数组值的循环79 temp = rand() % 50; //随机数取值 0-49 80if(checked[temp] == 0) //是否是已有的值81 {82 createtable(temp); //创建散列表83 printf("%2d => ",temp);84for(j = 0;j < MAX;j++) //输出散列表85 printf("[%2d]",hashtable[j]);86 printf("\n");87checked[temp] = 1; //设置此值⽣成过88 i++; //下⼀个数组值89 }90 }9192while(1) //主循环开始93 {94 printf("\n请输⼊查找值(0-49) ==> ");95 scanf("%d",&temp); //导⼊查找值96if(temp != -1)97 {98 i = linehash(temp); //调⽤散列查找99if(i != -1)100 printf("找到查找值：%d[%d]\n",temp,i); 101else102 printf("没有找到查找值：%d\n",temp); 103 }104else105 exit(1); //结束程序106 }107return0;108 }⽤链表创建散列表1//⽤链表创建散列表2 #include <stdlib.h>3 #include <time.h>4 #include <stdio.h>5#define MAX 106#define NUM 1078struct list9 {10int key;11struct list*next;12 };13 typedef struct list node;14 typedef node* link;1516 node hashtable[MAX];1718int hashfunc(int value)19 {20return value % MAX;21 }23int linkhash(int key)24 {25 link ptr;26int pos;2728 pos = hashfunc(key);29 ptr = hashtable[pos].next;30while(ptr != NULL)31if(ptr->key == key)32return1;33else34 ptr = ptr->next;35return0;36 }3738void createtable(int key)39 {40 link ptr;41 link new;42int pos;4344new = (link)malloc(sizeof(node));45new->key = key;46new->next = NULL;4748 pos = hashfunc(key);49 ptr = hashtable[pos].next;50if(ptr != NULL)51 {52new->next = ptr;53 hashtable[pos].next = new;54 }55else56 hashtable[pos].next = new;57 }5859int main()60 {61 link ptr;62int checked[50];63int i,temp;64long temptime;65for(i = 0;i < MAX;i++)66 hashtable[i].next = NULL;67for(i = 0;i < 50;i++)68checked[i] = 0;6970 srand(time(&temptime) % 60);71 i = 0;72while(i != NUM)73 {74 temp = rand() % 50;75if(checked[temp] == 0)76 {77 createtable(temp);78checked[temp] = 1;79 i++;80 }81 }82 printf("散列表内容：\n");83for(i = 0;i < MAX;i++)84 {85 printf("\n%2d ==> ",i);86 ptr = hashtable[i].next;87while(ptr != NULL)88 {89 printf("[%2d]",ptr->key);90 ptr = ptr->next;91 }92 }9394while(1)95 {96 printf("\n请输⼊查找值(0-49) ==> ");97 scanf("%d",&temp);98if(temp != -1)99 {100 i = linkhash(temp);101if(i != 0)102 printf("找到查找值：%d\n",temp); 103else104 printf("没有找到查找值：%d\n",temp); 105 }106else 107 exit(1); 108 }109return0; 110 }。

计算机科学与技术系之欧侯瑞魂创作哈希表的设计与实现项目陈说专业名称计算机科学与技术项目课程数据结构与算法项目名称哈希表的设计与实现班级项目人员钱海峰,郑秀娟,王传敏,杨青,凌波实验日期 2015.12.9目录一．设计目的 (3)二．问题分析 (3)三．设计环境 (3)四．人员分配 (3)五．详细设计和编码 (4)六．实验分析 (7)1测试分析 (7)2性能分析……………………………………………………11附录 (12)参考书目 (17)一．设计目的（1）掌握散列结构和散列函数的相关概念（2）掌握散列结构的存储结构的相关概念（2）掌握散列抵触的处置方法（3）运用散列解决抵触问题.二．问题分析要完成如下要求：设计哈希表实现整数查询系统.实现本项目需要解决以下问题：（1）如何设计一个哈希表.（2）如何在哈希表中拔出记录.（3）如何删除哈希表中的记录.（4）如何查找并显示记录.（5）如何解决抵触问题.三．设计环境⒈硬件：计算机每人一台.⒉软件：Windows把持系统和Microsoft Visual VC++6.0编译器.四．人员分配五．详细设计和编码1.界说结点结构类型在链地址法中,每个结点对应一个链表结点,由3个域组成,结构如图9-1所示.其中,key为关键字域,寄存结点关键字；data为数据域,寄存结点数据信息；next为链域,寄存指向下一个同义词结点的指针.图9-1 链地址法结点结构链地址数据结构类型如下：#define MAX_LENGTH 50typedef struct node{int data;struct node *next;}ElemNode;typedef struct{ElemNode *first;}ElemHeader,HashTable[MAX_LENGTH];#include <stdio.h>设计一个Hash（）函数,本设计中对散列函数选择的是除留余数法,即对关键字进行模运算,将运算结果所得的余数作为关键字（或结点）的存储地址,即i=ht mod n,本设计n由用户自己输入,然后将计算出来的结果返回.具体设计如下：int Hash(int ht){ int i;i = ht%n;return i;}3.初始化散列链表初始化链地址散列算法只需要把散列表中所有表头结点的指针域置为NULL.初始化散列链表的算法如下：void initHashTable(HashTable ht,int n){int i;for(i =0;i<n;i++){ ht[i].first= NULL;}}在整个设计中,创立哈希表必需是第一步要做的,结点之前应先输入结点的个数,利用链地址法解决抵触.添加结点实际是调用了拔出结点函数insert（）,需要利用哈希函数计算出地址,其次将结点拔出以关键字为地址的链表后.建立结点应包括静态申请内存空间,想地址中输入信息,同时最后一个结点中的next指针即是NULL.具体实现如下：int createHashTable(HashTable ht){HashTable *p=ht;int ad[MAX_LENGTH]={0};int i;printf("请输入拔出个数n:");scanf("%d",&n);printf("\n请输入拔出%d个整数:",n);for(i=0;i<n;i++)scanf("%d",&ad[i]);initHashTable(p,n);for(i=0;i<n;i++)insert(p,ad[i]);return 1;5.散列链表拔出结点算法将一个结点拔出到散列链表中,其算法分为以下几步：（1）根据结点关键字计算散列地址；（2）根据散列地址找到表头结点,并将结点拔出到对应的链表中.链地址法散列表的拔出算法如下：void insert(HashTable ht,int ele){int i;ElemNode *p;i=Hash(ele);p=(ElemNode *)malloc(sizeof(ElemNode));p->data = ele;p->next = ht[i].first;ht[i].first = p;}6.散列链表查找结点算法在散列链表中查找一个结点,其算法分为以下几步：（1）根据待查找关键字计算散列地址；（2）在散列地址所指向的单链表中顺序查找待查找关键字；（3）如果找到待查关键字,则返回指向该结点的指针；否则返回NULL.散列链表中查找结点的算法如下：ElemNode* search(HashTable ht,int ele){ int i;ElemNode *p;i = Hash(ele);p=ht[i].first;while(p!=NULL && p->data != ele){ p = p->next; }if(p!=NULL){printf("数据%d的位置为%d\n",ele,i);return p;}else{ printf("哈希表中无%d\n",ele);return p;}}7.散列链表删除结点算法在散列表中删除一个结点,其算法分为两步：（1）查找要删除的结点；（2）如果找到则删除,否则显示提示信息.在散列表中删除一个结点的算法如下：void dele(HashTable ht,int ele){//删除指定命据int i;ElemNode *p,*q;i = Hash(ele);p=ht[i].first;if(p == NULL){printf("error occurred! ");}if(p->data == ele){ht[i].first = p->next;}else {q= p->next;while(q!=NULL && q->data != ele){p=q;q = q->next;}if(q == NULL){printf("error occurred! ");}else{p->next = q->next;free(q);}}}六．实验分析1.测试分析（1）建立哈希表（2）拔出一个结点并显示：（3）查找结点：在哈希表中没有3这个数,会输出一行提示信息.（4）删除一个结点并显示：2.性能分析散列法实质上是一种通过关键字直接计算存储地址的方法.在理想情况下,散列函数可以把结点均匀地分布在散列表中,不发生抵触,则查找过程无需比力,其时间复杂度O（1）.但在实际使用过程中,为了将范围广泛的关键字映射到一组连续的存储空间,往往会发生同义词抵触,这时就需要进行关键字比力.能够把关键字尽可能均匀地分布到散列表中的函数是“好”的散列函数.好的散列函数可以有效地降低抵触的的发生,从而提高查找性能.但好的散列函数和关键字的数字特征有关,因此不存在对任何结点都好的散列函数.对同一种散列函数,采纳分歧的抵触处置方法将发生分歧的效果,例如线性探测法容易招致“二次聚集”,而拉链法可以从根本上根绝二次聚集,从而提高查找性能.不外也会“浪费”一部份散列表的空间.附录****************************法式源代码*********************************//头文件#include <stdio.h>#include <stdlib.h>#define MAX_LENGTH 50typedef struct node{int data;struct node *next;}ElemNode;typedef struct{ElemNode *first;}ElemHeader,HashTable[MAX_LENGTH];int n;//存储哈希表长度void initHashTable(HashTable ht,int n);void insert(HashTable ht,int ele);ElemNode* search(HashTable ht,int ele);void dele(HashTable ht,int ele);int Hash(int ht);int createHashTable(HashTable ht);void showHashTable(HashTable ht);void menu(HashTable ht);//菜单//功能函数sanlibiao.c#include"sanlibiao.h"void initHashTable(HashTable ht,int n){//初始化int i;for(i =0;i<n;i++){ht[i].first= NULL;}}void insert(HashTable ht,int ele){//拔出int i;ElemNode *p;i=Hash(ele);p=(ElemNode *)malloc(sizeof(ElemNode)); // p->key = ele;p->data = ele;p->next = ht[i].first;ht[i].first = p;}ElemNode* search(HashTable ht,int ele){//查找int i;ElemNode *p;i = Hash(ele);p=ht[i].first;while(p!=NULL && p->data != ele){p = p->next;}if(p!=NULL){printf("数据%d的位置为%d\n",ele,i);return p;}else{printf("哈希表中无%d\n",ele);return p;}}void dele(HashTable ht,int ele){//删除指定命据int i;ElemNode *p,*q;i = Hash(ele);p=ht[i].first;if(p == NULL){printf("error occurred! ");}if(p->data == ele){ht[i].first = p->next;}else {q= p->next;while(q!=NULL && q->data != ele){p=q;q = q->next;}if(q == NULL){printf("error occurred! ");}else{p->next = q->next;free(q);}}}int Hash(int ht){//哈希函数int i;i = ht%n;return i;}int createHashTable(HashTable ht)//创立哈希表{HashTable *p=ht;int ad[MAX_LENGTH]={0};int i;printf("请输入拔出个数n:");scanf("%d",&n);printf("\n请输入拔出%d个整数:",n);for(i=0;i<n;i++)scanf("%d",&ad[i]);initHashTable(p,n);for(i=0;i<n;i++)insert(p,ad[i]);return 1;}void showHashTable(HashTable ht)//显示哈希表{int i;ElemNode *p;//i = Hash(ele);for(i=0;i<n;i++){p=ht[i].first;if(p!=NULL)printf("位置%d上的数据：",i);while(p!=NULL){printf("%d ",p->data);p = p->next;}if(ht[i].first!=NULL)printf("\n");}}void menu(HashTable ht){int p,h; //p 菜单选择；do{// system("cls");//清屏printf("★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆\n");printf("☆★☆★\n");printf("★☆************** 欢迎来到哈希表系统! ***************★☆\n");printf("☆★合肥学院☆★\n");printf("★☆计算机科学与技术★☆\n");printf("☆★钱海峰,郑秀娟,王传敏,杨青,凌波☆★\n");printf("☆★☆★\n");printf("☆★※※※※※※※☆★\n");printf("★☆※菜单※★☆\n");printf("☆★※※※※※※※☆★\n");printf("☆★☆★\n");printf("★☆************** (1)---创立哈希表******************★☆\n");printf("☆★************** (2)---查找******************★☆\n");printf("★☆************** (3)---删除******************★☆\n");printf("☆★************** (4)---拔出******************★☆\n");printf("★☆************** (5)---输出哈希表******************★☆\n");printf("☆★************** (0)---退出******************☆★\n");printf("★☆****************************************************★☆\n");printf("☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★\n");printf("\n请在上述序号中选择一个并输入： ");scanf("%d",&p);switch(p){case 1:createHashTable(ht);break;case 2:printf("请输入要查找的数：\n");scanf("%d",&h);search(ht,h);break;case 3:printf("请输入要删除的数：\n");scanf("%d",&h);dele(ht,h);printf("\n");break;case 4:printf("请输入要拔出的数：\n");scanf("%d",&h);insert(ht,h);printf("\n");break;case5:showHashTable(ht);printf("\n");break;case 0: break; //退出default:printf("输入毛病!请重新输入!\n");break;}//system("pause");//系统暂停,提示按任意键继续....}while(p!=0); //for do}//主函数 mian.c#include "sanlibiao.h"int main(){HashTable ht;menu(ht);//进入菜单循环return 0;参考书目王昆仑,李红,《数据结构与算法》,中国铁道出书社,2007年6月初版.谭浩强,《C语言法式设计》,北京：清华年夜学出书社,2005年7月第三版.。

课程设计报告问题描述：(1) 散列法中，散列函数构造方法多种多样，同时对于同一散列函数解决冲突的方法也可以不同。

两者是影响查询算法性能的关键因素。

(2) 程序实现几种典型的散列函数构造方法，并观察，不同的解决冲突方法对查询性能的影响。

a. 需求分析：散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。

对不同的关键字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2)，这种现象称冲突。

具有相同函数值的关键字对该散列函数来说称做同义词。

综上所述，根据散列函数H(key)和处理冲突的方法将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象”作为记录在表中的存储位置，这种表便称为散列表，这一映象过程称为散列造表或散列，所得的存储位置称散列地址。

散列表的查找过程基本上和造表过程相同。

一些关键码可通过散列函数转换的地址直接找到，另一些关键码在散列函数得到的地址上产生了冲突，需要按处理冲突的方法进行查找。

对散列表查找效率的量度，依然用平均查找长度来衡量。

查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。

因此，影响产生冲突多少的因素，也就是影响查找效率的因素。

该课程设计要求比较几种哈希函数的构造方法和解决冲突的方法对查询性能的影响。

b. 概要设计该程序实现对哈希函数的构造方法、处理冲突的方法及在哈希表中查找数据的功能。

用线性再散列方法建立哈希表，用代码实现为：typedef struct{int key;int si;}HashTable1;void CreateHashTable1(HashTable1 *H,int *a,int num)//哈希表线性探测在散列；{int i,d,cnt;for(i=0;i<HashSize;i++){H[i].key=0;H[i].si=0;}for(i=0;i<num;i++){cnt=1;d=a[i]%HashSize;if(H[d].key==0){H[d].key=a[i];H[d].si=cnt;}else{do{d=(d+1)%HashSize; cnt++;}while(H[d].key!=0); H[d].key=a[i];H[d].si=cnt;}}printf("\n线性再探索哈希表已建成!");}用二次探测再散列建立哈希表，代码实现如下：void CreateHash3(HashTable3 *h,int *a,int num)//二次探索表{int i,p=-1,c,pp;for(i=0;i<num;i++){c=0;p=a[i]%HashSize;pp=p;while(h->elem[pp]!=NULL){pp=Collision(p,c);if(pp<0){printf("第%d个记录无法解决冲突\n",i+1);continue;}}h->elem[pp]=&(a[a[i]]);h->count++;printf("第%d个记录冲突次数为%d\n",i+1,c);}printf("\n建表完成！\n此哈希表容量为%d,当前表内存储的记录个数%d.\n",HashSize,h->count);}二次探测再散列法解决冲突int Collision(int p,int &c){int i,q;i=c/2+1;while(i<HashSize) {if(c%2==0){c++;q=(p+i*i)%HashSize; if(q>=0)return q;elsei=c/2+1;}else{q=(p-i*i)%HashSize; c++;if(q>=0)return q; else i=c/2+1;}}return (-1);}用线性再散列法查找，代码实现如下：void SearchHash1(HashTable1 *h,int data){int d;d=data%HashSize;if(h[d].key==data)printf("数字%d的探查次数为：%d\n",h[d].key,h[d].si); else{dod=(d+1)%HashSize;while(h[d].key!=data && d<HashSize);if(d<HashSize)printf("数字%d的探查次数为：%d\n",h[d].key,h[d].si); elseprintf("没有查找到你所输入的数\n");}用二次探测再散列法查找void SearchHash2(HashTable2 * h[],int data,int num) {int d;Node *q;d=data%num;q=h[d]->link;while(q->key!=data && q->next!=NULL)q=q->next;if(q->next!=NULL)printf("数字%d的查找次数为：%d\n",q->key,q->next); elseprintf("没有找到你要查找的那个数\n");}用链地址法查找，代码实现如下：void CreateHashTable2(HashTable2 *ht[],int *a,int num)//哈希表链地址；{int i,d,cnt;Node *s,*q;for(i=0;i<num; i++){ht[i]=(HashTable2 *)malloc(Sizeof(HashTable2));ht[i]->link=NULL;}for(i=0;i<num;i++){cnt=1;s=(Node *)malloc(sizeof(Node));s->key=a[i];s->next=NULL;d=a[i]%num;if(ht[d]->link==NULL) {ht[d]->link=s;s->si=cnt;}else{q=ht[d]->link;while(q->next!=NULL) {q=q->next;cnt++;}cnt++;s->si=cnt;q->next=s;}}}c. 详细设计(1) 程序中结构体的定义typedef struct{int key;int si;}HashTable1;typedef struct node {int key;int si;struct node *next;}Node;typedef struct{Node *link;}HashTable2;typedef struct{int * elem[HashSize];int count;int size;}HashTable3;(2) 主函数模块void main(){int data;HashTable1 hash1[HashSize];HashTable2 * hash2[HashSize];HashTable3 * ha;ha=(HashTable3 *)malloc(sizeof(HashTable3)); for(int i=0;i<HashSize;i++)ha->elem[i]=NULL;ha->count=0;ha->size=HashSize;int a[MaxSize];while(1){printf("\n ┏━━━━━━━━━━━━━━━┓ ");printf("\n ┃欢迎使用本系统┃ ");printf("\n ┏〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓┓");printf("\n ┃★ ★ ★ ★ ★ ★散列法的实验研究★ ★ ★ ★ ★ ★┃");printf("\n ┃ 【1】. 添加数据信息【2】数据的输出┃");printf("\n ┃【3】. 建立哈希表(线性再散列) ┃");printf("\n ┃【4】. 建立哈希表(二次探测再散列) ┃");printf("\n ┃【5】. 建立哈希表(链地址法) ┃");printf("\n ┃【6】. 线性再散列法查找┃");printf("\n ┃【7】. 二次探测再散列法查找┃");printf("\n ┃【8】. 链地址法查找┃");printf("\n ┃【0】. 退出程序┃");printf("\n ┗〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓┛");printf("\n");。