摘要
现实生活中许多数据的处理依赖于哈希表的应用，通过应用哈希表使复杂问题更加简单化。通过实用类模板，使用开放地址法和除留余数法来实现对哈希表的建立、插入、删除等功能，采用Visual C++ 6.0的控制台工程和MFC工程分别实现了哈希表的应用。
关键词：除留余数法；哈希表；开放地址法；MFC工程
目录
1需求分析 (1)
2算法基本原理 (1)
2.1除留余数法原理 (1)
2.2开放地址法基本思想 (2)
3类设计 (3)
3.1类的概述 (3)
3.2类的接口设计 (4)
3.3类的实现 (5)
4基于控制台的应用程序 (9)
4.1主函数设计 (9)
4.2运行结果及分析 (10)
5基于MFC的应用程序 (12)
5.1图形界面设计 (12)
5.2程序代码设计 (14)
5.3运行结果及分析 (20)
结论 (22)
参考文献 (23)
1 需求分析
很多自然科学和工程技术中的问题的解决最终都归结到线性方程组的求解，高斯消去法是线性方程组解法中很经典的算法，由它改进、变形得到的全选主元消去法，是一种效率很高、较为常用的线性方程组解法。
线性方程组的一般形式为Ax=b ，其中A 是线性方程组的系数矩阵，x 是列向量，是方程组的解，b 也是列向量，这里假定A 是非奇异矩阵。
程序测试数据来自徐士良先生编著的《C 常用算法程序集》中，所选的方程是： (1)
2 算法基本原理
2.1 除留余数法原理
设有n 元线性方程组：
(2)
将(2)写成矩阵形式b Ax =，其中： (3)
将系数矩阵A 和向量b 放在一起，形成增广矩阵B ：
(4)
全选主元消去就在这个B 矩阵上进行，整个过程分为两个步骤：
??????
?=+++=+++=+++=+++5471.11490.01397.01245.01161
.16471.11871.01768.01675.11581
.07471.12271.02168.12071.01968.08471.12671.12568.02471
.02368.03210321032103210x x x x x x x x x x x x x x x x ??
?
??
?
?=+++=+++=+++----------1
11,111,100,1111,1111010011,0101000n n n n n n n n n n b x a x a x a b x a x a x a b x a x a x a ???
??
?
??????=?????
???????=?
?
???????
???=------1101101,11
,10
,1,11110
,00100,
,n n n n n n n n b b b b x x x x a a a a a a a a a A
????????????==-----1101,11,10
,1,11110,00100
),(n n n n n n n b b b a a a a a a a a a b A B
第一步，消去过程。
对于k 从0开始到n-2结束，进行以下三步：
（1）首先，从系数矩阵A 的第k 行、k 列开始的子矩阵中选取绝对值最大的元素作为主元素，例如：
(5)
然后交换B 的第k 行与第i1行，第k 行与第j1列，这样，这个子矩阵中的具有最大绝对值的元素被交换到第k 行、k 列的位置。
（2）其次，进行归一化计算。计算方法为： (6)
（3）最后，进行消去运算：
(7)
第二步，回代过程。 (8)
在这里，只是列出简要地给出了全选主元高斯消去法的算法步骤，具体推导及详细过程可参考数值分析方面的有关资料。
2.2 开放地址法基本思想
当发生地址冲突时，按照某种方法继续探测哈希表中的其他存储单元，直到找到空位置为止。这个过程可用下式描述：
采用这种方法时，首先计算出元素的直接哈希地址，如果该存储单元已被其他元素占用，则继续查看地址为的存储单元，如此重复直至找到某个存储单元为空时，将关键字为 key 的数据元素存放到该单元。增量 d 可以有不同的取法，并根据其取法有不同的称呼。
max 1,1≠=<≤≤≤ij n
j k n i k j i a a 1,,2,1,
/-++==n k k j a a a kk kj kj kk
k k a b b /=1
,,2,1,,
-++=-=n k k i j a a a a kj ik kj ij 1
,,2,1,
-++=-=n k k i b a b b k ik i i 1,111/----=n n n n a b x 0
,,1,2,
1
1
--=-
=∑-+=n n i x a
b b n i j j ij
i i
3类设计
3.1 类的概述
类模板就是设计一种类的框架，可以适用不同的数据类型，只是一种类的抽象，因此，利用类模板可以针对不同的数据类型定义出具有共性的一组类。
定义形式如下：
template <类型名参数名1，类型名参数名2，…>
class 类名
{
类声明体；
}；
与函数模板类似，通过使用类模板可以使得所定义的类中的某些数据成员某些成员函数的参数某些成员函数的返回值都可以是任意的数据类型（包括基本类型和自定义类型）。所以，可以通过类模板将程序所处理的对象的类型参数化，从而使得同一段程序可用于处理多种不同类型的对象，提高了程序的抽象层次和可重用性。由于哈希表中的数据元素可以是char, int, float等多种数据类型，因此可以使用类模板来构造本程序的实现框架。
本设计面临的计算问题的关键是矩阵运算。可以定义一个矩阵类Matrix作为基类，然后由矩阵类派生出线性方程组类Linequ。矩阵类Matrix只处理n×n类型的方阵，方阵用一个一维数组来存放，矩阵类Matrix的数据成员包括数组的首地址和n，矩阵类Matrix的功能有设置矩阵的值SetMatrix( )和显示矩阵PrintM( )等。
从问题的需要来看，线性方程组类Linequ的数据除了由矩阵类Matrix继承过来用于存放系数矩阵A的成员外，还应该包括存放解向量x和方程右端向量b的数组首地址。线性方程组类Linequ的主要操作有设置SetLinequ( )、显示PrintL( )、求解Solve( )及输出方程的解showX( )。可以通过定义线性方程组类Linequ的新增成员函数来实现这些针对方程组求解的功能。
在线性方程组的求解过程中，在线性方程组类Linequ的成员函数Solve中需要访问基类矩阵类Matrix的数据成员，利用公有继承方式派生，同时将Matrix类中的数据成员的访问控制设置为保护类型。这样，经过公有派生之后，基类的保护成员在派生类中依然是保护成员，可以被派生类的成员函数访问。
整个类分别使用了insert(t1 key,t2 data)实现哈希表元素的插入，remove(t1 key)实现哈
希表元素的删除，query(t1 key)实现哈希表元素的查找，display()实现哈希表元素的显示。
3.2 类的接口设计
//Linequ.h文件，实现类的声明
#include
#include
using namespace std;
class Matrix //基类Matrix声明
{
public: //外部接口
Matrix(int dims=2); //构造函数
~Matrix(); //析构函数
void SetMatrix(double *rmax); //矩阵赋初值
void PrintM(); //显示矩阵
protected:
int index; //方阵的行数
double* MatrixA; //矩阵存放数组首地址
};
class Linequ:public Matrix //公有派生类Linequ声明
{
public: //外部接口
Linequ(int dims=2); //构造函数
~Linequ(); //析构函数
void SetLinequ(double *a, double *b); //方程赋值
void PrintL(); //显示方程
int Solve(); //全选主元高斯消去法求解方程
void ShowX(); //显示方程的解
private: //私有数据
double *sums; //方程右端项
double *solu; //方程的解
};
经过公有派生，Linequ类获得了除构造函数、析构函数之外的Matrix类的全部成员，由于基类的成员是公有和保护类型，因此在派生类中的成员函数中，基类继承来的成员全部可以访问，而对于建立Linequ类对象的外部模块来讲，基类的保护成员是无法访问的。通过保护访问类型和公有的继承方式，实现了基类Matrix的数据的有效共享和可靠保护。在程序中，方程的系数矩阵、解以及右端项全部采用了动态内存分配技术，这些工作都是在基类、派生类的构造函数中完成，它们的清理工作在析构函数中完成。
3.3 类的实现
template
hash
array=new linknode[7];
for(int i=0;i<7;i++){
array[i]=NULL;
}
}
template
hash
for(int i=0;i<7;i++){
if(array[i]!=NULL){
linknode n=array[i];
while(n!=NULL){
linknode n1=n;
n=n->next;
delete n1;
}
}
}
}
template
void hash
int sum=func(key)%7;
//派生类Linequ的实现
Linequ::Linequ(int dims):Matrix(dims) //派生类Linequ的构造函数
{ //使用参数调用基类构造函数
sums=new double[dims]; //动态内存分配
solu=new double[dims];
}
Linequ::~Linequ() //派生类Linequ的析构函数
{
delete[] sums; //释放内存
delete[] solu;
}
}else{
ln *n=new ln;
n->key=key;
n->data=data;
n->next=NULL;
array[sum]=n;
}
}
template
t2 hash
int sum=func(key)%7;
linknode p=array[sum];
while(p){
if(type=="char*"){
if(stricmp((char*)(int)p->key,(char*)(int)key)==0){ cout<<"关键字"< return p->data; }else{ p=p->next; } }else if(type=="void*"){ if((int)p->key==(int)key){ cout<<"关键字"< return p->data; }else{ p=p->next; } }else{ if(p->key==key){ cout<<"关键字"< return p->data; }else{ p=p->next; } } } return "您所查询的关键字在该哈希表中不存在！"; } template void hash { for(int i=0;i<7;i++) { if(array[i]!=NULL) { ln *n=array[i]; while(n!=NULL) { cout<<"array["< n=n->next; } }else cout<<"array["< } } template int hash type="int"; return i; } template int hash type="float"; int s=i*100; return s; } template type="char*"; int s=strlen(i)*i[0]; return s; } template int hash type="char"; int s=(int)i; return s; } } template void hash { int sum=func(key)%7; linknode p=array[sum]; if(p!=NULL) { if(p->next!=NULL) {if(p->key==key) {array[sum]=p->next;delete p;cout<<"关键字"< else { while(p->next!=NULL&&p->next->key!=key) p=p->next; linknode p2=p->next; p->next=p2->next; delete p2; cout<<"关键字"< } } else {array[sum]=NULL;delete p;cout<<"关键字"< } else {cout<<"对不起！您删除的关键字"< 4基于控制台的应用程序 4.1 主函数设计 //main.cpp主函数 #include "linequ.h" int main() //主函数 { double a[]= //系数矩阵 { 0.2368,0.2471,0.2568,1.2671, 0.1968,0.2071,1.2168,0.2271, 0.1581,1.1675,0.1768,0.1871, 1.1161,0.1254,0.1397,0.1490 }; double b[4]={ 1.8471,1.7471,1.6471,1.5471}; //方程右端项 Linequ equ1(4); //定义一个四元方程组对象 equ1.SetLinequ(a,b); //设置方程组 equ1.PrintL(); //输出方程组 if(equ1.Solve()) //求解方程组 equ1.ShowX(); //输出方程组的解 else cout<<"Fail"< return 1; } 在程序的主函数部分，选择了一个四元方程组作为一个实际例子来验证算法。方程组的系数及右端项数据都使用一维数组来存储。首先定义一个四元方程组对象equ1，在定义过程中调用派生类的构造函数，通过派生类的构造函数，又调用了基类的构造函数，对进一步求解动态分配了内存。接着给方程组的系数和右端项赋初值，把我们选定的方程组输入到新定义的方程组对象equ1中。对象成员函数PrintL、Solve和ShowX分别完成了输出方程组、求解方程组和输出求解结果的任务。 4.2 运行结果及分析 程序初始化运行的结果如图1所示。从图1中可以看出通过关键字的输入，锁定key 和data,可以对哈希表进行数据的插入，并使哈希表数据重新初始化，实现数据的更新。 图1 程序初始化运行结果 图2为经过插入操作后对数据的查询结果，由图2可以看出，——————————————————————————————————————————————————————————————————。 图2 执行插入操作后的程序运行结果 图3为执行删除操作后的程序运行结果，可以看出。通过哈希表中关键字的索引进 行数据的删除，删除的元素为哈希表中已经存在的元素。 图3 执行删除操作的程序运行结果 在操作过程中，若删除的关键字在本哈希表中不存在则提示删除出错。 5基于MFC的应用程序 MFC的图形界面程序设计可在上述类设计的基础上进行改造，MFC的图形界面程序与DOS界面程序的主要不同点是：MFC图形界面程序与DOS界面程序的输入输出方式不同，DOS界面程序采用字符交互式实现数据输入输出，主要通过cin，cout等I/O 流实现，而MFC的图形程序界面采用标准Windows窗口和控件实现输入输出，因此必须在MFC类的框架下加入上面所设计的矩阵和方程组类，并通过图形界面的输入输出改造来完成。 5.1 图形界面设计 首先在VC中建立MFC AppWizard（exe）工程，名称为GassineGU，并在向导的Step1中选择Dialog based，即建立基于对话框的应用程序，如图4~5所示。 图4 建立MFC AppWizard（exe）工程 将对话框资源中的默认对话框利用工具箱改造成如图6所示界面。 图6 方程组求解程序界面设计 图6所示的界面中包含了3个Static Text控件，3个Button控件，和2个Edit Box 控件，控件的基本信息列表如下表1所示。 表1 控件基本信息 5.2 程序代码设计 为了能够将对话框界面上的控件能够与代码联系起来，需要为24个Edit Box控件建立Member Variables，按Ctrl+w键进入MFC ClassWizard界面，选择Member Variables 选项卡，可显示成员变量设置界面，如图7所示。 图7 成员变量设置界面 下面是编写代码的重要阶段，可以借鉴在设计基于DOS界面的控制台应用程序的代码，并将其作必要的改写，具体改写的步骤与内容如下。 // Haxibiao.cpp : implementation file // 类 #ifdef _DEBUG #define new DEBUG_NEW #undef THIS_FILE static char THIS_FILE[] = __FILE__; #endif hash ///////////////////////////////////////////////////////////////////////////// // CAboutDlg dialog used for App About class CAboutDlg : public CDialog { public: CAboutDlg(); // Dialog Data //{ //{{AFX_MSG(CAboutDlg) //}}AFX_MSG DE BEGIN_MESSAGE_MAP(CAboutDlg, CDialog) //{{AFX_MSG_MAP(CAboutDlg) // No message handlers //}}AFX_MSG_MAP END_MESSAGE_MAP() ///////////////////////////////////////////////////////////////////////////// // CWANGDlg dialog CWANGDlg::CWANGDlg(CWnd* pParent /*=NULL*/) : CDialog(CWANGDlg::IDD, pParent) {xGetApp()->LoadIcon(IDR_MAINFRAME); } void CWANGDlg::DoDataExchange(CDataExchange* pDX) { CDialog::DoDataExchange(pDX); //{{AFX_DATA_MAP(CWANGDlg) DDX_Text(pDX, IDC_EDIT1, m_HX); DDX_Text(pDX, IDC_EDIT2, m_key); DDX_Text(pDX, IDC_EDIT3, m_data); //}}AFX_DATA_MAP } BEGIN_MESSAGE_MAP(CWANGDlg, CDialog) //{{AFX_MSG_MAP(CWANGDlg) ON_WM_SYSCOMMAND() ON_W///////////////////////////////////////////////////////////////////////////// // CWANGDlg message handlers BOOL CWANGDlg::OnInitDialog() { CDialog::OnInitDialog(); h.insert("sds","etew");//初始化哈希表 h.insert("n25","45");//初始化哈希表 h.insert("4.5765k","2");//初始化哈希表 h.insert("$345","6");//初始化哈希表 h.insert("43.r","55");//初始化哈希表 h.insert("yan","24");//初始化哈希表 h.display();//h对象调用display()函数以显示哈希表元素 m_HX=h.str; UpdateData(0);//在编辑框处显示哈希表元素 // Add "About..." menu item to system menu. // IDM_ABOUTBOX must be in the system command range. Menu->AppendMenu(MF_SEPARATOR); pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu); } } if ((nID & 0xFFF0) == IDM_ABOUTBOX) { CAboutDlg dlgAbout; dlgAbout.DoModal(); } else { CDialog::OnSysCommand(nID, lParam); } } // If you add a minimize button to your dialog, you will need the code below // to draw the icon. For MFC applications using the document/view model, // this is automatically done for you by the framework. void CWANGDlg::OnPaint() { if (IsIconic()) { CPaintDC dc(this); // device context for painting SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0); { CDialog::OnPaint(); } } // The system calls this to obtain the cursor to display while the user drags // the minimized window. HCURSOR CWANGDlg::OnQueryDragIcon() { return (HCURSOR) m_hIcon; } 一: 需求分析 (2) 三: 详细设计（含代码分析） (4) 1.程序描述: (4) 2具体步骤 (4) 四调试分析和测试结果 (7) 五，总结 (9) 六.参考文献; (10) 七.致谢 (10) 八.附录 (11) 一: 需求分析 问题描述：设计哈希表实现电话号码查询系统。 基本要求 1、设每个记录有下列数据项：电话号码、用户名、地址 2、从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表； 3、采用再哈希法解决冲突； 4、查找并显示给定电话号码的记录； 5、查找并显示给定用户名的记录。 6、在哈希函数确定的前提下，尝试各种不同类型处理冲突的方法（至少 两种），考察平均查找长度的变化。 二: 概要设计 进入主函数,用户输入1或者2,进入分支选择结构:选1:以链式方法建立哈希表,选2:以再哈希的方法建立哈希表,然后用户输入用户信息,分别以上述确定的方法分别以用户名为检索以及以以电话号码为检索将用户信息添加到哈希表,.当添加一定量的用户信息后,用户接着输入用户名或者电话号码分别以用户名或者电话号码的方式从以用户名或电话号码为检索的哈希表查找用户信息.程序用链表的方式存储信息以及构造哈希表。 具体流程图如下所示: 三: 详细设计（含代码分析） 1.程序描述: 本程序以要求使用哈希表为工具快速快速查询学生信息，学生信息包括电话号码、用户名、地址；用结构体存储 struct node { string phone; //电话号码 string name; //姓名 string address;//地址 node *next; //链接下一个地址的指针 }; 2具体步骤 1. 要求主要用在哈希法解决冲突，并且至少尝试用两种方法解决冲突，定义两个指针数组存储信息node *infor_phone[MAX]; node *infor_name[MAX];前者以电话号码为关键字检索哈希表中的信息，后者以姓名为关键字检索哈希表中的信息 用链式法和再哈希法解决冲突： int hash(string key) //以姓名或者电话号码的前四位运算结果作为哈{ //希码 int result=1,cur=0,i; if(key.size()<=4) i=key.size()-1; else i=4; for(;i>=0;i--) { cur=key[i]-'0'; result=result*9+cur; } result%=(MOD); return result; 数据结构课程设计哈希表设计问题 目录 1 前言 (1) 2 需求分析 (1) 2.1 任务和要求 (1) 2.2 运行环境 (1) 2.3 开发工具 (1) 3 分析和设计 (2) 3.1 系统分析及设计思路 (2) 3.2 主要数据结构及算法 (2) 3.3 函数流程图 (2) （1）哈希表的创建及初始化流程图 (2) 5 课程设计总结 (13) 5.1 程序运行结果或预期运行结果 (13) 说明：输入的数为30个姓的拼音，查找的为“pan”，输出的如上图所示。 (14) 5.2 设计结论 (15) 参考文献 (15) 致谢 (15) 1 前言 从C语言产生到现在，它已经成为最重要和最流行的编程语言之一。在各种流行编程语言中，都能看到C语言的影子，如Java的语法与C语言基本相同。学习、掌握C语言是每一个计算机技术人员的基本功之一。 根据本次课程设计的要求，我设计小组将编写一个C语言程序来处理哈希表问题，通过这个程序，将针对自己的班集体中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。 2 需求分析 2.1 任务和要求 针对自己的班集体中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。 要求：假设人名为中国姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用链表法处理冲突。 2.2 运行环境 （1）WINDOWS2000/XP系统 （2）Visual C++ 6.0编译环境或TC编译环境 2.3 开发工具 C语言 3 分析和设计 3.1 系统分析及设计思路 （1）创建哈希表 （2）姓名（结构体数组）初始化 （1）用除留余数法构建哈希函数 （2）用链表法处理冲突 (3)查找哈希表 在哈希表中进行查找，输出查找的结果和关键字，并计算和输出查找成功的平均查找长度 (4) 显示哈希表 显示哈希表的的格式： 3.2 主要数据结构及算法 定义结构体typedef struct hashtable创建哈希表 定义函数Hash_Init(HashTable ht)来对哈希表初始化 定义函数Hash_Insert(HashTable ht, Node *node)来为哈希表分配地址 定义函数Hash_Init(ht)输入30个名字 定义函数Hash_Create(HashTable ht)来求哈希表长度 定义函数hash_output(HashTable h)来输出哈希表 定义函数Hash_Link()构造链表函数 定义函数int hash_search(int h[],int key)查找输入的名字 3.3 函数流程图 （1）哈希表的创建及初始化流程图 数据结构与算法-基础算法篇-哈希算法 1. 哈希算法 如何防止数据库中的用户信息被脱库？ 你会如何存储用户密码这么重要的数据吗？仅仅 MD5 加密一下存储就够了吗？ 在实际开发中，我们应该如何用哈希算法解决问题？ 1. 什么是哈希算法？ 将任意长度的二进制值串映射成固定长度的二进制值串，这个映射的规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值。 2. 如何设计一个优秀的哈希算法？ 单向哈希： 从哈希值不能反向推导出哈希值（所以哈希算法也叫单向哈希算法）。 篡改无效： 对输入敏感，哪怕原始数据只修改一个Bit，最后得到的哈希值也大不相同。 散列冲突： 散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小。 执行效率： 哈希算法的执行效率要尽量高效，针对较长的文本，也能快速计算哈 希值。 2. 哈希算法的常见应用有哪些？ 7个常见应用：安全加密、唯一标识、数据校验、散列函数、负载均衡、数据分片、分布式存储。 1. 安全加密 常用于加密的哈希算法： MD5：MD5 Message-Digest Algorithm，MD5消息摘要算法 SHA：Secure Hash Algorithm，安全散列算法 DES：Data Encryption Standard，数据加密标准 AES：Advanced Encryption Standard，高级加密标准 对用于加密的哈希算法，有两点格外重要，第一点是很难根据哈希值反向推导出原始数据，第二点是散列冲突的概率要小。 在实际开发中要权衡破解难度和计算时间来决定究竟使用哪种加密算法。 2. 唯一标识 通过哈希算法计算出数据的唯一标识，从而用于高效检索数据。 3. 数据校验 利用哈希算法对输入数据敏感的特点，可以对数据取哈希值，从而高效校验数据是否被篡改过。 4. 散列函数 1.如何防止数据库中的用户信息被脱库？你会如何存储用户密码这么重要的数据吗？ /* （1）设计哈希表，该表应能够容纳50个英文单词。 （2）对该哈希表进行查询，实现对特定单词的快速查询，并显示经过的节点内容 已经发到你邮箱里了enochwills@https://www.doczj.com/doc/f415578081.html, */ #include 实习6、哈希表设计 一、需求分析 1. 问题描述 针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度均不超过R，完成相应的建表和查表顺序。 2. 基本要求 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突。 3. 测试数据 取读者周围较熟悉的30个人的姓名。 4. 实现提示 如果随机数自行构造，则应首先调整好随机函数，使其分布均匀。人名的长度均不超过19个字符（最长的人名如：庄双双（Zhuang Shuangshuang））。字符的取码方法可直接利用C 语言中的toascii函数，并可先对过长的人名先作折叠处理。 二、概要设计 ADT Hash { 数据对象D：D是具有相同特征的数据元素的集合。各数据元素均含有类型相同，可唯一标识数据元素的关键字。 数据关系R：数据元素同属一个集合。 InitNameTable() 操作结果：初始化姓名表。 CreateHashTable() 操作结果：建立哈希表。 DisplayNameTable() 操作结果：显示姓名表。 DisplayHashTable() 操作结果：显示哈希表。 FindName() 操作结果：查找姓名。 }ADT Hash 三、详细设计（源代码） （使用C语言） #include 合肥学院 计算机科学与技术系 课程设计报告 2009 ～2010 学年第二学期 课程数据结构与算法 课程设计名称哈希表的设计与实现 学生姓名王东东 学号0804012030 专业班级08计本（2) 指导教师王昆仑、李贯虹 2010 年5 月 课程设计目的 “数据结构与算法课程设计”是计算机科学与技术专业学生的集中实践性环节之一， 是学习“数据结构与算法”理论和实验课程后进行的一次全面的综合练习。其目的是要达到 理论与实际应用相结合，提高学生组织数据及编写程序的能力，使学生能够根据问题要求和 数据对象的特性，学会数据组织的方法，把现实世界中的实际问题在计算机内部表示出来并 用软件解决问题，培养良好的程序设计技能。 一、问题分析和任务定义 1、问题分析 要完成如下要求：设计哈希表实现电话号码查询系统。 实现本程序需要解决以下几个问题： （1）如何定义一个包括电话号码、用户名、地址的节点。 （2）如何以电话号码和用户名为关键字建立哈希表。 （3）用什么方法解决冲突。 （4）如何查找并显示给定电话号码的记录。 （5）如何查找并显示给定用户名的记录。 2 任务定义 1、由问题分析知，本设计要求分别以电话号码和用户名为关键字建立哈希表，z在此基 础上实现查找功能。本实验是要我们分析怎么样很好的解决散列问题，从而建立一比较合理 的哈希表。由于长度无法确定，并且如果采用线性探测法散列算法，删除结点会引起“信息 丢失”的问题。所以采用链地址法散列算法。采用链地址法，当出现同义词冲突时，可以使 用链表结构把同义词链接在一起，即同义词的存储地址不是散列表中其他的空地址。 根据问题分析，我们可以定义有3个域的节点，这三个域分别为电话号码char num[30]，姓名char name[30]，地址char address[30]。这种类型的每个节点对应链表中的每个节点，其中电话号码和姓名可分别作关键字实现哈希表的创建。 二、数据结构的选择和概要设计 1、数据结构的选择 数据结构：散列结构。 散列结构是使用散列函数建立数据结点关键词与存储地址之间的对应关系，并提供多 种当数据结点存储地址发生“冲突”时的处理方法而建立的一种数据结构。 散列结构基本思想，是以所需存储的结点中的关键词作为自变量，通过某种确定的函 数H（称作散列函数或者哈希函数）进行计算，把求出的函数值作为该结点的存储地址，并 将该结点或结点地址的关键字存储在这个地址中。 散列结构法（简称散列法）通过在结点的存储地址和关键字之间建立某种确定的函数 关系H，使得每个结点（或关键字）都有一个唯一的存储地址相对应。 当需要查找某一指定关键词的结点时，可以很方便地根据待查关键字K计算出对应的“映像”H(K)，即结点的存储地址。从而一次存取便能得到待查结点，不再需要进行若干次的 比较运算，而可以通过关键词直接计算出该结点的所在位置。 数据结构课程设计报告 课题四哈希表查找的设计 1. 任务和功能要求 设哈希表长为20，用除留余数法构造一个哈希函数，以开放定址法中的线性探测再散列法作为解决冲突的方法，编程实现哈希表查找、插入和建立算法。 2. 需求分析 用户输入20个以内的数字存储在哈希表中，并可以在表中查找关键字。3.概要设计 typedef struct { int *key; //关键字 int count; //表长 }HashTable; int creat(HashTable *T) //初始化哈希表 程序调用关系如下： 主函数模块 哈希表初始化模块查询模块 插入模块 4. 详细设计 #include #include 一、问题描述 针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度均不超过R，完成相应的建表和查表顺序。 二、基本要求 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突。 三、概要设计 1.构造结构体：typedef struct{}； 2.姓名表的初始化：void InitNameTable()； 3.建立哈希表：void CreateHashTable()； 4.显示姓名表：void DisplayNameTable()； 5.姓名查找：void FindName()； 6.主函数：void main() ； 四、详细设计 1.姓名表的初始化 void InitNameTable() { NameTable[0].py="louyuhong"; NameTable[1].py="shenyinghong"; NameTable[2].py="wangqi"; NameTable[3].py="zhuxiaotong"; NameTable[4].py="zhataotao"; NameTable[5].py="chenbinjie"; NameTable[6].py="chenchaoqun"; NameTable[7].py="chencheng"; NameTable[8].py="chenjie"; NameTable[9].py="chenweida"; NameTable[10].py="shanjianfeng"; NameTable[11].py="fangyixin"; NameTable[12].py="houfeng"; NameTable[13].py="hujiaming"; NameTable[14].py="huangjiaju"; NameTable[15].py="huanqingsong"; NameTable[16].py="jianghe"; NameTable[17].py="jinleicheng"; NameTable[18].py="libiao"; NameTable[19].py="liqi"; NameTable[20].py="lirenhua"; NameTable[21].py="liukai"; NameTable[22].py="louhanglin"; NameTable[23].py="luchaoming"; NameTable[24].py="luqiuwei"; NameTable[25].py="panhaijian"; NameTable[26].py="shuxiang"; NameTable[27].py="suxiaolei"; NameTable[28].py="sunyubo"; NameTable[29].py="wangwei"; for (i=0;i 计算与数据结构篇 - 哈希算法 (Hash) 计算与数据结构篇 - 哈希算法 (Hash) 哈希算法的定义和原理非常简单，基本上一句话就可以概括了。将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值。 构成哈希算法的条件： 从哈希值不能反向推导出原始数据（所以哈希算法也叫单向哈希算法）对输入数据非常敏感，哪怕原始数据只修改了一个 Bit，最后得到的哈希值也大不相同； 散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小； 哈希算法的执行效率要尽量高效，针对较长的文本，也能快速地计算出哈希值。 哈希算法的应用(上篇) 安全加密 说到哈希算法的应用，最先想到的应该就是安全加密。最常用于加密的哈希算法是 MD5（MD5 Message-Digest Algorithm，MD5 消息摘要算法）和 SHA（Secure Hash Algorithm，安全散列算法）。 除了这两个之外，当然还有很多其他加密算法，比如 DES（Data Encryption Standard，数据加密标准）、AES（Advanced Encryption Standard，高级加密标准）。 前面我讲到的哈希算法四点要求，对用于加密的哈希算法来说，有两点格外重要。第一点是很难根据哈希值反向推导出原始数据，第二点是散列冲突的概率要很小。 不过，即便哈希算法存在散列冲突的情况，但是因为哈希值的范围很大，冲突的概率极低，所以相对来说还是很难破解的。像 MD5，有 2^128 个不同的哈希值，这个数据已经是一个天文数字了，所以散列冲突的概率要小于 1-2^128。 如果我们拿到一个 MD5 哈希值，希望通过毫无规律的穷举的方法，找到跟这个 MD5 值相同的另一个数据，那耗费的时间应该是个天文数字。所以，即便哈希算法存在冲突，但是在有限的时间和资-源下，哈希算法还是被很难破解的。 对于加密知识点的补充，md5这个算法固然安全可靠，但网络上也有针对MD5中出现的彩虹表，最常见的思路是在密码后面添加一组盐码(salt), 比如可以使用md5(1234567.'2019@STARK-%$#-idje-789'),2019@STARK-%$#-idje-789 作为盐码起到了一定的保护和安全的作用。 唯一标识(uuid) 我们可以给每一个图片取一个唯一标识，或者说信息摘要。比如，我们可以从图片的二进制码串开头取 100 个字节，从中间取 100 个字节，从最后再取 100 个字节，然后将这 300 个字节放到一块，通过哈希算法（比如 MD5），得到一个哈希字符串，用它作为图片的唯一标识。通过这个唯一标识来判定图片是否在图库中，这样就可以减少很多工作量。 课程设计(论文)任务书 软件学院学院软件工程专业班 一、课程设计(论文)题目：通讯录管理系统的设计与实现——哈希表 二、课程设计(论文)工作自2016 年 1 月 4 日起至 2016 年 1 月 10 日止 三、课程设计(论文) 地点: 软件测试中心（北区测试二室） 四、课程设计(论文)内容要求： 1．本课程设计的目的 ⑴训练学生灵活应用所学数据结构知识，独立完成问题分析，结合课程的理论知识，编写程序求解指定问题； ⑵初步掌握软件开发过程的问题分析、系统设计、编码、测试等基本方法和技能； ⑶提高综合运用所学的理论知识和方法独立分析和解决问题的能力，巩固、深化学生的理论知识，提升编程水平。 2．课程设计的任务及要求 1）基本要求： ⑴要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编写上机程序和上机调试等若干步骤完成题目，最终写出完整的报告； ⑵在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率； ⑶程序设计语言推荐使用C/C++，程序书写规范，源程序需加必要的注释； ⑷每位同学需提交可独立运行的程序和规范的课程设计报告。 2）课程设计论文编写要求 ⑴理论设计部分以课程设计论文的形式提交，格式必须按照课程设计论文标准格式进行书写和装订； ⑵课程设计报告包括中文目录、设计任务、需求分析、概要设计、详细设计、编码实现、调试分析、课设总结、谢辞、参考文献、附录等； ⑶设计部分应包含系统功能模块图，调试分析应包括运行截图等。 3）课程设计评分标准： ⑴学习态度：10分； ⑵系统设计：20分； ⑶编程调试：20分； ⑷回答问题：20分； ⑸论文撰写：30分。 哈希表设计数据结构课程设计 实习6、哈希表设计 一、需求分析 1. 问题描述 针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度均不超过R，完成相应的建表和查表顺序。 2. 基本要求 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突。 3. 测试数据 取读者周围较熟悉的30个人的姓名。 4. 实现提示 如果随机数自行构造，则应首先调整好随机函数，使其分布均匀。人名的长度均不超过19个字符（最长的人名如：庄双双（Zhuang Shuangshuang））。字符的取码方法可直接利用C语言中的toascii函数，并可先对过长的人名先作折叠处理。 二、概要设计 ADT Hash { 数据对象D：D是具有相同特征的数据元素的集合。各数据元素均含有类型相同，可唯一标识数据元素的关键 字。 数据关系R：数据元素同属一个集合。 InitNameTable() 操作结果：初始化姓名表。 CreateHashTable() 操作结果：建立哈希表。 DisplayNameTable() 操作结果：显示姓名表。 DisplayHashTable() 操作结果：显示哈希表。 FindName() 操作结果：查找姓名。 }ADT Hash 三、详细设计（源代码） （使用C语言） #include 哈希表查找不成功怎么计算？ 解答：先建好表，然后可以算出每个位置不成功时的比较次数之和，再除以表空间个数！ 例如：散列函数为hash(x)=x MOD 13，用线性探测，建立了哈希表之后，如何求查找不成功时的平均查找长度！？ 地址：0 1 2 3 4 5 6 7 8 9 10 11 12 数据： 39 1228154244 625－－ 36－ 38 成功次数： 1 3 1 2 2 1 191 1 不成功次数：98 7 65 4 3 2 1 1 2 110 查找成功时的平均查找长度:ASL=(1+3+1+2+2+1+1+9+1+1)/10 =2.2 查找不成功时的平均查找长度:ASL=(9+8+7+6+5+4+3+2+1+1+2+1+10)/13=4.54 说明： 第n个位置不成功时的比较次数为，第n个位置到第1个没有数据位置的距离。至少要查询多少次才能确认没有这个值。 （1）查询hash(x)=0,至少要查询9次遇到表值为空的时候，才能确认查询失 败。 （2）查询hash(x)=1,至少要查询8次遇到表值为空的时候，才能确认查询失 败。 （3）查询hash(x)=2,至少要查询7次遇到表值为空的时候，才能确认查询失 败。 （4）查询hash(x)=3,至少要查询6次遇到表值为空的时候，才能确认查询失 败。 （5）查询hash(x)=4,至少要查询5次遇到表值为空的时候，才能确认查询失 败。 （6）查询hash(x)=5,至少要查询4次遇到表值为空的时候，才能确认查询失 败。 （7）查询hash(x)=6,至少要查询3次遇到表值为空的时候，才能确认查询失败。 （8）查询hash(x)=7,至少要查询2次遇到表值为空的时候，才能确认查询失败。 （9）查询hash(x)=8,至少要查询1次遇到表值为空的时候，才能确认查询失败。 （10）查询hash(x)=9,至少要查询1次遇到表值为空的时候，才能确认查询失败。 （11）查询hash(x)=10,至少要查询2次遇到表值为空的时候，才能确认查询失败。 （12）查询hash(x)=11,至少要查询1次遇到表值为空的时候，才能确认查询失败。 （13）查询hash(x)=12,至少要查询10次遇到表值为空(循环查询顺序表)的时候，才能确认查询失败。 下面看下2010年2010年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题中一个考哈希表的题。 Question1: 将关键字序列（7、8、30、11、18、9、14）散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组，散列函数为：H(key) = (keyx3) MOD 7，处理冲突采用线性探测再散列法，要求装填（载）因子为0.7。 (1) 请画出所构造的散列表。 (2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。 Ans： (1).首先明确一个概念装载因子，装载因子是指所有关键子填充哈希表后饱和的程度，它等于关键字总数/哈希表的长度。根据题意，我们可以确定哈希表的长度为 L = 7/0.7 = 10；因此此题需要构建的哈希表是下标为0~9的一维数组。根据散列函数可以得到如下散列函数值表。 H(Key) = (keyx3) MOD 7, 例如key=7时， H(7) = (7x3）%7 = 21%7=0，其他关键字同理。 福建工程学院 课程设计 课程：算法与数据结构 题目：哈希表 专业：网络工程 班级：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 令胆嗲院 计算机科嗲b练水系 课程设计报告 2007 2008 学年第 2 学期 课程数据结构与算法 课程设计名称哈希表的设计与实现 学生姓名 学号0604011026 专业班级06计科（1) 指导教师 2008 年9 月 课程设计题目： （哈希表的设计与实现的问题〉设计哈希表实现电话号码查询系统。设计程序完成以下要求：(1）设每个记录有下列数据项：电话号码、用户名、地址：（2）从键盘输入各记录，分别以电话号码和用户名为关键字建立晗希表；(3）采用再哈希法解决冲突；（4）查找并显示给定电话号码的记录：（5）查找并显示给定用户的记录。 一、问题分析和任务定义 1、问题分析 要完成如下要求：设计晗希表实现电话号码查询系统。实现本程序需要解决以下几个问题： (1) 如何设计一个结点使该结点包括电话号码、用户名、地址。 (2) 如何分别以电话号码和用户名为关键字建立哈希表。 (3) 如何利用再晗希法解决冲突。 (4) 如何实现用晗希法查找并显示给定电话号码的记录。 (5) 如何查找并显示给定用户的记录。 2、任务定义 由问题分析知，本设计主要要求分别以电话号码和用户名为关键字建立晗希表，并实现查找功能。所以本设计的核心问题是如何解决散列的问题，亦即设计一个良好的哈希表。由于结点的个数无法确认，并且如果采用线性探测法散列算法，删除结点会引起“信息丢失”的问题。所以采用链地址法散列算法。采用链地址法，当出现同义词冲突时，使用链表结构把同义词链接在一起，即同义词的存储地址不是散列表中其他的空地址。 决的是定义链表结点，在链地址法中，每个结点对应一个链表结点，它由三个首先，解 域组成，而由于该程序需要分别用电话号码和用户名为关键字建立晗希表，所以该链表结点它是由四个域组成.name[8］、num[ll］和address[20］都是char浮点型，输入输出都只能是浮点型的。 采用链地址法，其中的所有同义词构成一个单链表，再由一个表头结点指向这个单链表的第一个结点。这些表头结点组成一个一维数组，即哈希表。数组元素的下标对应由散列函数求出的散列地址。 课程设计题目哈希表及其应用 教学院计算机学院 专业 班级 姓名 指导教师 年月日 课程设计任务书 2010 ～2010 学年第 1 学期 一、课程设计题目哈希表及其应用 二、课程设计内容 建立一个小型信息管理系统（可以是图书、人事、学生、物资、商品等任何信息管理系统）。要求： 1.使用哈希查找表存储信息； 2.实现查找、插入、删除、统计、输出等功能； 三、进度安排 1．初步完成总体设计，搭好框架； 2．完成最低要求：尝试使用多种哈希函数和冲突解决方法，并通过实际运行测试给出自己的评价 四、基本要求 1．界面友好，函数功能要划分好 2．程序要加必要的注释 3．要提供程序测试方案 教研室主任签名： 年月日 1 概述 (4) 2 设计目的 (4) 3 设计功能说明 (4) 4 详细设计说明 (5) 5 流程图 (5) 6 程序代码 (6) 7 程序运行结果 (15) 8 总结 (19) 参考文献 (19) 成绩评定表 (20) 数据结构是一门理论性强、思维抽象、难度较大的课程，是基础课和专业课之间的桥梁，只有进行实际操作，将理论应用于实际中，才能确实掌握书中的知识点。通过课程设计，不仅可以加深学生对数据结构基本概念的了解，巩固学习成果，还能够提高实际动手能力。为学生后继课程的学习打下良好的基础。 2 设计目的 《数据结构》课程设计是在教学实践基础上进行的一次大型实验，也是对该课程所学理论知识的深化和提高。因此，要求学生能综合应用所学知识，设计与制造出具有较复杂功能的应用系统，并且在实验的基本技能方面上进行一次全面的训练。通过程序的编译掌握对程序的调试方法及思想，并且让学生学会使用一些编程技巧。促使学生养成良好的编程习惯。 1.使学生能够较全面地巩固和应用课堂中所学的的基本理论和程序设计方法，能够较熟练地完成程序的设计和调试。 2.培养学生综合运用所学知识独立完成程序课题的能力。 3.培养学生勇于探索、严谨推理、实事求是、有错必改，用实践来检验理论，全方位考虑问题等科学技术人员应具有的素质。 4．提高学生对工作认真负责、一丝不苟，对同学团结友爱，协作攻关的基本素质。 5.培养学生从资料文献、科学实验中获得知识的能力，提高学生从别人经验中找到解决问题的新途径的悟性，初步培养工程意识和创新能力。 6.对学生掌握知识的深度、运用理论去处理问题的能力、实验能力、课程设计能力、书面及口头表达能力进行考核。 3 设计功能分析 本设计的功能如下： 1、利用哈希函数来实现一个小型信息管理系统，其中信息包含用户名，地址，电话等。 2、能添加用户信息，并能保存该信息。 3、查询管理系统中的信息：可通过姓名查找，也可通过电话查找等两种方式。 福建工程学院课程设计 课程：算法与数据结构 题目：哈希表 专业：网络工程 班级：xxxxxx班 座号：xxxxxxxxxxxx 姓名：xxxxxxx 2011年12 月31 日 实验题目：哈希表 一、要解决的问题 针对同班同学信息设计一个通讯录，学生信息有姓名，学号，电话号码等。以学生姓名为关键字设计哈希表，并完成相应的建表和查表程序。 基本要求：姓名以汉语拼音形式，待填入哈希表的人名约30个，自行设计哈希函数，用线性探测再散列法或链地址法处理冲突；在查找的过程中给出比较的次数。完成按姓名查询的操作。 运行的环境：Microsoft Visual C++ 6.0 二、算法基本思想描述 设计一个哈希表（哈希表内的元素为自定义的结构体）用来存放待填入的30个人名，人名为中国姓名的汉语拼音形式，用除留余数法构造哈希函数，用线性探查法解决哈希冲突。建立哈希表并且将其显示出来。通过要查找的关键字用哈希函数计算出相应的地址来查找人名。通过循环语句调用数组中保存的数据来显示哈希表。 三、设计 1、数据结构的设计和说明 （1）结构体的定义 typedef struct //记录 { NA name; NA xuehao; NA tel; }Record; 录入信息结构体的定义，包含姓名，学号，电话号码。 typedef struct //哈希表 { Record *elem[HASHSIZE]; //数据元素存储基址 int count; //当前数据元素个数 int size; //当前容量 }HashTable; 哈希表元素的定义，包含数据元素存储基址、数据元素个数、当前容量。 2、关键算法的设计 （1）姓名的折叠处理哈希表的设计与实现 课程设计报告
数据结构课程设计哈希表设计问题复习过程
哈 希 常 见 算 法 及 原 理
哈希表查询设计及实现
哈希表设计-数据结构课程设计
哈希表的设计与实现-数据结构与算法课程设计报告
数据结构课程设计哈希表
数据结构哈希表设计
哈 希 常 见 算 法 及 原 理
数据结构课设-通讯录系统的设计与实现——哈希表
哈希表设计数据结构课程设计
哈希表查找成功和不成功的算法
数据结构课程设计--哈希表实验报告
哈希表的设计与实现
哈希表及其应用-课程设计
数据结构课程设计--哈希表实验报告
相关主题
文本预览