数据结构与算法实验报告
|
实验
|
实验四 哈希表设计
|
|
学院
|
|
|
专业(班级)
|
|
|
姓名
|
|
|
学号
|
|
|
教师
|
|
实验四 哈希表设计
1实验目的
1．熟悉有关哈希表的基本概念；
2．熟悉构造哈希表的方法；
3．掌握哈希冲突的处理方法。
2实验要求
1．根据教材给出的方法，自己设计哈希表的存储结构；
2．根据教材给出的方法，自己设计哈希函数和处理冲突的方法；
3．实现哈希表的基本操作，完成哈希表的查找过程。
3实验环境
硬件平台：计算机CPU 主频2.0G以上；内存128兆以上；
软件平台：Windows2003或以上版本，Visual C++6.0。
4实验内容
1．根据教材给出的方法，选择一种哈希函数的设计方法和处理冲突的方法，设计一种哈希表；输入一批关键字集合，建立哈希表。
2．实现哈希表的基本操作：创建、销毁、取元素个数、置空、判空、赋值、取值、插入、删除等。
3．完成哈希表的查找过程。
5实验步骤
- 本实验要求建立哈希表，并对哈希表进行增删查操作。
- 不经历任何比较，一次存取便能得到所查记录，因此在记录的存储位置和关键字之间建立一个确定的对应关系，使每个关键字和结构中一个唯一的存储位置相对应。对应的建立一个这样的哈希函数。
- 对不同的关键字可能得到同一散列地址，即key1!=key2，但是f(key1)=f(key2)。这就产生了冲突，因此需要处理冲突的函数。
- 根据哈希函数和处理冲突的方法将一组关键字映像到有限的连续地址上，便建立了哈希表。查找时也根据哈希函数和处理冲突方法，找到关键字地址，找到关键字。
哈希表的存储结构：
typedef struct {
ElemType *elem;
int count;
int sizeindex;
}HashTable;//哈希表的结构
int hashsize[]={997,...}//哈希表容量递增表，一个合适的素数序列
Status Hash(int K){
return K%m;
}//哈希函数（除留余数法）
void collision(int *p,int d)//处理冲突函数（我在本次实验中使用了两种方法，开放定址法和链地址法）
Status SearchHash(HashTable H,KeyType K,int &p,int &c){}
// 在开放定址哈希表H中查找关键码为K的元素，若查找成功，以p指示待查数据。
Status InsertHash(HashTable &H,ElemType e){}
//查找不成功时插入数据元素e到开放定址哈希表H中，并返回OK；若冲突次数过大，则重建哈希表。
三．程序思想
1.哈希函数：生成映射地址。
2.处理冲突函数：对冲突的关键字进行处理。
3.插入函数：插入关键字，先计算关键字的映射地址，然后在相应的地址插入，如果冲突，则利用处理冲突函数查找空位插入。
4.查找函数：先计算关键字的地址，再判断是否冲突，再到散列表中查找。
四．功能流程图
程序流程
哈希表的插入
哈希表的查找
五.程序运行截图:
界面
哈希表的查找
哈希表的创建（链地址法）
哈希表的查找（链地址法）
六.程序源代码：
#include
#include
#include
#include
#include
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define SUCCESS 1
#define UNSUCCESS 0
#define DUPLICATE -1
#define NULLKEY 0
using namespace std;
typedef int KeyType;
typedef int Status;
int m=0;
int N;
int hashsize[]={11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997};
typedef struct{
KeyType key;
}ElemType;
struct ElemType1{
KeyType key;
struct ElemType1*next;
};
typedef struct HashTable2{
ElemType1 **elem;//二级指针型向量，采用动态分配空间大小
int count;//当前的头指针向量的元素
int hashindex;//hashsize[H.hashindex]为当前容量
}HashTable1;
typedef struct {
ElemType *elem;
int count;
int sizeindex;
}HashTable;
int SearchHashTable1(ElemType1 *L, KeyType K, ElemType1 *&v){
ElemType1 *s = NULL;
s = (ElemType1*)malloc(sizeof(ElemType1));
s->key = K;
if (!L->next){//一开始为空，插入一个元素
s->next = L->next;
L->next = s;
v = s;
return 0;
}
else{
ElemType1* p = L->next;
ElemType1 *q = L;
while (p&&p->key != K){
q = p;
p = p->next;
}
if (p&&p->key == K){
v = p;
return 1;//找到了数据元素
}
else{//插入一个数据,此时p为空,需要她的前驱指针q指向最后一个元素，采用尾插法插入元素
s->next = q->next;
q->next = s;
v = s;
return 0;
}
}
}
Status Hash(int K){
return K%m;
}//哈希函数
void InitHashTable1(HashTable1 &H){
H.count = 0;
m = hashsize[0];
H.elem = (ElemType1**)malloc(m*sizeof(ElemType1*));
for (int i = 0; i next = NULL;
}
}
ElemType1* SearchHashTable1(HashTable1 H, KeyType K, int &p){
p = Hash(K);//p为根据关键字计算的处的头结点所在的位置,关键
ElemType1 *head = H.elem[p];//记下头结点,关键字记录肯定在以head为头结点的单链表中
return head;
}
void TraverseHashTable1(HashTable1 H){
ElemType1 *p = NULL, *q = NULL;
for (int i = 0; i next){//头结点不空
printf("\n进入了链表，地址为%d:\n",i);
q = p->next;//指向首节点
while (q){
printf("%d->", q->key);
q = q->next;
}
}
}
printf("\n");
}
ElemType1* InsertHashTable1(HashTable1&H, ElemType1 e){
int p = 0;//为插入的位置
ElemType1*v = NULL;
ElemType1*head = SearchHashTable1(H, e.key, p);//找到数据项e应该插入的头结点所在的链表
//SearchHashTableLinkListElemType;
SearchHashTable1(head, e.key, v);//动态查找链表
return v;//返回这个结点,不管找没找到，找到了返回，没找到会自动插入这个元素也返回
//在以head为头结点的链表中查找e.key关键字的元素
}
Status InitHash(HashTable &H){
H.count=0;
H.sizeindex=0;
m=hashsize[0];
H.elem=(ElemType *)malloc(m*sizeof(ElemType));
if(!(H.elem))
exit(0);
for(int i=0;ikey!=NULLKEY)
*p++=*((*H).elem+i);
(*H).count=0;
(*H).sizeindex++;
m=hashsize[(*H).sizeindex];
p=(ElemType *)realloc((*H).elem,m*sizeof(ElemType));
if(!p)
exit(0);
(*H).elem=p;
for(i=0;i%d-->地址-->%d\n",r.key,p);
}//打印函数
void mainview_user( ) //界面函数
{ HashTable h;
HashTable1 h1;
int j,p,x;
int l=1000;
ElemType r[N];
ElemType1 r1[l];
KeyType k;
InitHash(h);
InitHashTable1(h1);
int c;
while(1)
{
system("CLS"); //清除屏幕函数
printf(" ------------------------------------\n");
printf(" |**********哈希表***************|\n");
printf(" |********1 遍历哈希表*********|\n");
printf(" |********2 插入哈希表*********|\n");
printf(" |********3 构建哈希表*********|\n");
printf(" |********4 销毁哈希表*********|\n");
printf(" |********5 哈希表的查找*******|\n");
printf(" |********6 构造哈希表（链地址法）|\n");
printf(" |********7 哈希表的查找（链地址法|\n");
printf(" |********0 退出系统***********|\n");
printf(" ------------------------------------\n");
printf("\n");
printf("请选择：");
scanf("%d",&c);
switch(c)
{
case 1: {
printf("按哈希表地址顺序遍历哈希表:\n");
TraverseHash(h,print);
break;
}
case 2: {
printf("请输入要插入的关键字:");
scanf("%d",&k);
j=Find(h,k,&p);
while(1){
if(j==SUCCESS){
printf("表中有该元素请重新输入:");
scanf("%d",&k);
j=Find(h,k,&p);
}
else break;
}
r[N].key=k;
j=InsertHash(&h,r[N]);
if(j==0)
j=InsertHash(&h,r[N]);
printf("插入成功\n");
TraverseHash(h,print);
N+=1;
break;
}
case 3: {
printf("请输入要输入的关键字数目:");
scanf("%d",&N);
int j;
printf("请输入关键字：");
for(int i=0;inext){//头结点不空
printf("\n进入了链表，地址为%d:\n",Hash(k));
t = q->next;//指向首节点
while (t){
printf("%d->", t->key);
if(t->key==k){
printf(" 找到了\n");
break;
}
t= t->next;
}
printf("没找到\n");
}
else printf("没找到\n");
break;
}
case 0: {
DestroyHash(h);
return;
}
default:printf("输入错误，请重新输入!\n");fflush(stdin);
}
printf("\n\n");
system("PAUSE");
}
}
int main(){
mainview_user();
}
京公网安备 11010802041100号