第四关：在采用除留余数法加链地址法建立的哈希表中删除数据 第一关：采用除留余数法加线性探测法建立哈希表
#include"stdio.h"
#include"stdlib.h"
#define NULL_KEY -1 // -1为无记录标志
#define SUCCESS 1
#define UNSUCCESS 0
#define DUPLICATE -1
#define N 100 // 数据元素个数
typedef int KeyType; // 设关键字域为整型
struct ElemType // 数据元素类型
{ KeyType key;
};
struct HashTable
{ ElemType *elem; // 数据元素存储基址，动态分配数组
int count; // 当前数据元素个数
int sizeindex; // sizeindex为哈希表表长
};
// 哈希函数的基本操作函数
void InitHashTable(HashTable &H); // 构造一个空的哈希表
void DestroyHashTable(HashTable &H); // 哈希表H存在。操作结果：销毁哈希表H
unsigned Hash(KeyType K); // 哈希函数
void collision(int &p,int d); // 线性探测再散列
int SearchHash(HashTable H,KeyType K,int &p,int &c); // 在开放定址哈希表H中查找关键码为K的元素
int InsertHash(HashTable &H,ElemType e); // 查找不成功时插入数据元素e到开放定址哈希表H中
void TraverseHash(HashTable H,void(*Vi)(int));
void print(int p);
int m=0; // 全局变量, H(key) = key % m
int main()
{ ElemType r[N]={0};
HashTable h;
int i,p,n;
int j;
KeyType k;
InitHashTable(h);
scanf("%d",&m); // H(key) = key % m
scanf("%d",&n); // 数据的个数
for(i=0;i scanf("%d",&r[i].key);
}
for(i=0;i // 插入前N-1个记录
j=InsertHash(h,r[i]);
}
//printf("按哈希地址的顺序遍历哈希表:\n");
TraverseHash(h,print);
DestroyHashTable(h);
}
// 哈希函数的基本操作函数
void InitHashTable(HashTable &H)
{ // 操作结果：构造一个空的哈希表
int i;
H.count=0; // 当前元素个数为0
scanf("%d",&H.sizeindex ); // 哈希表存储容量
H.elem=(ElemType*)malloc(H.sizeindex*sizeof(ElemType));
for(i=0;i // 初始条件：哈希表H存在。操作结果：销毁哈希表H
free(H.elem);
H.elem=NULL;
H.count=0;
H.sizeindex=0;
}
unsigned Hash(KeyType K)
{ // 一个简单的哈希函数(m为全局变量)
/********** Begin **********/
return K%m;
/********** End **********/
}
void collision(int &p,int d) // 线性探测再散列
{ // 开放定址法处理冲突
/********** Begin **********/
p=(p+1)%m;
/********** End **********/
}
int SearchHash(HashTable H,KeyType K,int &p,int &c)
{ // 在开放定址哈希表H中查找关键码为K的元素，若查找成功，以p指示待查数据
// 元素在表中位置，并返回SUCCESS；否则，以p指示插入位置，并返回UNSUCCESS
// c用以计冲突次数，其初值置零，供建表插入时参考。
/********** Begin **********/
p=Hash(K); // 求得哈希地址
while( H.elem[p].key!=NULL_KEY && K!= H.elem[p].key )
{ // 该位置中填有记录．并且关键字不相等
c++;
if(c // 查找不成功时插入数据元素e到开放定址哈希表H中，并返回OK；
// 若冲突次数过大，则重建哈希表，算法9.18
/********** Begin **********/
int c,p;
c=0;
if(SearchHash(H,e.key,p,c)) // 表中已有与e有相同关键字的元素
return DUPLICATE;
else if(c // 插入e
H.elem[p]=e;
++H.count;
return SUCCESS;
}
else
return UNSUCCESS;
/********** End **********/
}
void TraverseHash(HashTable H,void(*Vi)(int))
{ // 按哈希地址的顺序遍历哈希表
printf("哈希地址0～%d\n",H.sizeindex-1);
for(int i=0;i printf("%d\t",p);
}
第二关：在采用除留余数法加线性探测法建立的哈希表中查找数据
#include"stdio.h"
#include"stdlib.h"
#define NULL_KEY -1 // -1为无记录标志
#define SUCCESS 1
#define UNSUCCESS 0
#define DUPLICATE -1
#define N 100 // 数据元素个数
typedef int KeyType; // 设关键字域为整型
struct ElemType // 数据元素类型
{ KeyType key;
};
struct HashTable
{ ElemType *elem; // 数据元素存储基址，动态分配数组
int count; // 当前数据元素个数
int sizeindex; // sizeindex为哈希表表长
};
// 哈希函数的基本操作函数
void InitHashTable(HashTable &H); // 构造一个空的哈希表
void DestroyHashTable(HashTable &H); // 哈希表H存在。操作结果：销毁哈希表H
unsigned Hash(KeyType K); // 哈希函数
void collision(int &p,int d); // 线性探测再散列
int SearchHash(HashTable H,KeyType K,int &p,int &c); // 在开放定址哈希表H中查找关键码为K的元素
int InsertHash(HashTable &H,ElemType e); // 查找不成功时插入数据元素e到开放定址哈希表H中
void TraverseHash(HashTable H,void(*Vi)(int));
void print(int p);
int Find(HashTable H,KeyType K,int &p);
int m=0; // 全局变量, H(key) = key % m
int main()
{ ElemType r[N]={0};
HashTable h;
int i,p,n;
int j;
KeyType k;
InitHashTable(h);
scanf("%d",&m); // H(key) = key % m
scanf("%d",&n); // 数据的个数
for(i=0;i scanf("%d",&r[i].key);
}
for(i=0;i // 插入前N-1个记录
j=InsertHash(h,r[i]);
}
//printf("按哈希地址的顺序遍历哈希表:\n");
TraverseHash(h,print);
//printf("请输入待查找记录的关键字: ");
scanf("%d",&k);
j=Find(h,k,p);
if(j==SUCCESS)
{ printf("查找成功：");
print(h.elem[p].key);
}
else
printf("查找失败\n");
DestroyHashTable(h);
}
// 哈希函数的基本操作函数
void InitHashTable(HashTable &H)
{ // 操作结果：构造一个空的哈希表
int i;
H.count=0; // 当前元素个数为0
scanf("%d",&H.sizeindex ); // 哈希表存储容量
H.elem=(ElemType*)malloc(H.sizeindex*sizeof(ElemType));
for(i=0;i // 初始条件：哈希表H存在。操作结果：销毁哈希表H
free(H.elem);
H.elem=NULL;
H.count=0;
H.sizeindex=0;
}
unsigned Hash(KeyType K)
{ // 一个简单的哈希函数(m为全局变量)
return K%m;
}
void collision(int &p,int d) // 线性探测再散列
{ // 开放定址法处理冲突
p=(p+1)%m;
}
int SearchHash(HashTable H,KeyType K,int &p,int &c)
{ // 在开放定址哈希表H中查找关键码为K的元素，若查找成功，以p指示待查数据
// 元素在表中位置，并返回SUCCESS；否则，以p指示插入位置，并返回UNSUCCESS
// c用以计冲突次数，其初值置零，供建表插入时参考。
p=Hash(K); // 求得哈希地址
while( H.elem[p].key!=NULL_KEY && K!= H.elem[p].key )
{ // 该位置中填有记录．并且关键字不相等
c++;
if(c // 查找不成功时插入数据元素e到开放定址哈希表H中，并返回OK；
// 若冲突次数过大，则重建哈希表
int c,p;
c=0;
if(SearchHash(H,e.key,p,c)) // 表中已有与e有相同关键字的元素
return DUPLICATE;
else if(c // 插入e
H.elem[p]=e;
++H.count;
return SUCCESS;
}
else
return UNSUCCESS;
}
void TraverseHash(HashTable H,void(*Vi)(int))
{ // 按哈希地址的顺序遍历哈希表
printf("哈希地址0～%d\n",H.sizeindex-1);
for(int i=0;i printf("%d\t",p);
}
int Find(HashTable H,KeyType K,int &p)
{ // 在开放定址哈希表H中查找关键码为K的元素，若查找成功，以p指示待查数据
// 元素在表中位置，并返回SUCCESS；否则，返回UNSUCCESS
/********** Begin **********/
p=Hash(K);
int c=0;
while(H.elem[p].key!=NULL_KEY&&H.elem[p].key!=K)
{ c++;
printf("哈希地址为%d，第%d次冲突\n",p,c);
if(c collision(p,c);
}
}
c++;
if(H.elem[p].key==K)
{ printf("哈希地址为%d，第%d次查找成功\n",p,c);
return SUCCESS;
}
else
{ printf("哈希地址为%d，第%d次查找为空\n",p,c);
return UNSUCCESS;
}
/********** End **********/
}
第三关：采用除留余数法加链地址法建立哈希表
#include #include #define N 20 // 数据元素个数
typedef int KeyType; // 设关键字域为整型
struct ElemType // 数据元素类型
{ KeyType key;
};
typedef struct Node { //链地址,其实这个指针就是链表
ElemType r;
struct Node* next;
}Node;
typedef struct {Node** rcd; //（指向指针的指针）存放指针的数组
int size; //哈希表的容量
int count; //当前表中含有的记录个数
}HashTable;
int InitHash(HashTable& H, int size); //初始化哈希表
int DestroyHash(HashTable& H); //销毁哈希表
Node* SearchHash(HashTable H, KeyType key); //查找
int InsertHash(HashTable& H, ElemType e); //插入
int DeleteHash(HashTable& H, KeyType key, ElemType& e); //删除
void HashTraverse(HashTable H); //遍历
unsigned Hash(KeyType K,int m);
int m,n,i,j;
int main()
{ HashTable h;
KeyType k;
ElemType r[N]={0};
scanf("%d",&m); // H(key) = key % m
scanf("%d",&n); // 数据的个数
InitHash(h,m);
for(i=0;i scanf("%d",&r[i].key);
}
for(i=0;i // 插入前N-1个记录
InsertHash(h, r[i]);
}
printf("采用链地址法得到的哈希表为：\n");
HashTraverse(h);
DestroyHash(h);
}
unsigned Hash(KeyType K,int m)
{ // 一个简单的哈希函数
return K%m;
}
int InitHash(HashTable& H, int size)
{H.rcd = (Node**)malloc(size*sizeof(Node*));
if (H.rcd != NULL)
{for (int i = 0; i < size; i++)
{H.rcd[i] = NULL;
}
H.size = size;
H.count = 0;
return 1;
}
else
{return 0;
}
}
int DestroyHash(HashTable& H)
{if (H.rcd != NULL)
{Node* np, * nt;
for (int i = 0; i < H.size; i++)
{np = H.rcd[i];
while (np != NULL)
{nt = np;
np = np->next;
free(nt);
}
}
H.size = 0;
H.count = 0;
return 1;
}
else
{return 0;
}
}
Node* SearchHash(HashTable H, KeyType key)
{/*********BEGIN*********/
int p;
Node* np;
p = Hash(key,H.size);
np = H.rcd[p];
while (np)
{ if(key == np->r.key)
return np ;
np = np->next;
}
return NULL;
/**********END**********/
}
int InsertHash(HashTable& H, ElemType e)
{ /*********BEGIN*********/
int p;
Node* np;
np = SearchHash(H, e.key);
if (np == NULL)
{ p = Hash(e.key,H.size);
np = (Node*)malloc(sizeof(Node));
np->r = e;
np->next = H.rcd[p];
H.rcd[p] = np;
H.count++;
return 1;
}
else
{ return 0;
}
}
/**********END**********/
void HashTraverse(HashTable H)
{if (H.rcd != NULL)
{Node* np, * nq;
for (int i = 0; i < H.size; i++)
{printf("%d: ", i);
if (H.rcd [i])
{printf("%d ",H.rcd [i]->r .key);
Node* curr=H.rcd [i]->next;
while (curr) { printf("-> %d ", curr->r.key);
curr=curr->next;
}
printf("\n");
}
else
printf("-\n");
}
}
}
第四关：在采用除留余数法加链地址法建立的哈希表中删除数据
#include #include #define N 20 // 数据元素个数
typedef int KeyType; // 设关键字域为整型
struct ElemType // 数据元素类型
{ KeyType key;
};
typedef struct Node { //链地址,其实这个指针就是链表
ElemType r;
struct Node* next;
}Node;
typedef struct { Node** rcd; //（指向指针的指针）存放指针的数组
int size; //哈希表的容量
int count; //当前表中含有的记录个数
}HashTable;
int InitHash(HashTable& H, int size); //初始化哈希表
int DestroyHash(HashTable& H); //销毁哈希表
Node* SearchHash(HashTable H, KeyType key); //查找
int InsertHash(HashTable& H, ElemType e); //插入
int DeleteHash(HashTable& H, KeyType key, ElemType& e); //删除
void HashTraverse(HashTable H); //遍历
unsigned Hash(KeyType K,int m);
int main()
{ HashTable h;
KeyType k;
ElemType r[N]={0},e;
int m,n,i,j;
scanf("%d",&m); // H(key) = key % m
scanf("%d",&n); // 数据的个数
InitHash(h,m);
for(i=0;i scanf("%d",&r[i].key);
}
for(i=0;i // 插入前N-1个记录
InsertHash(h, r[i]);
}
printf("采用链地址法得到的哈希表为：\n");
HashTraverse(h);
//printf("请输入要删除的整数值：\n");
scanf("%d",&k);
if ( DeleteHash(h, k, e) )
{ printf("删除元素后哈希表为：\n");
HashTraverse(h);
}
else
printf("删除元素失败。\n");
DestroyHash(h);
}
unsigned Hash(KeyType K,int m)
{ // 一个简单的哈希函数
return K%m;
}
int InitHash(HashTable& H, int size)
{ H.rcd = (Node**)malloc(size*sizeof(Node*));
if (H.rcd != NULL)
{ for (int i = 0; i < size; i++)
{ H.rcd[i] = NULL;
}
H.size = size;
H.count = 0;
return 1;
}
else
{ return 0;
}
}
int DestroyHash(HashTable& H)
{ if (H.rcd != NULL)
{ Node* np, * nt;
for (int i = 0; i < H.size; i++)
{ np = H.rcd[i];
while (np != NULL)
{ nt = np;
np = np->next;
free(nt);
}
}
H.size = 0;
H.count = 0;
return 1;
}
else
{ return 0;
}
}
Node* SearchHash(HashTable H, KeyType key)
{ int p;
Node* np;
p = Hash(key,H.size);
np = H.rcd[p];
while (np)
{ if(key == np->r.key)
return np ;
np = np->next;
}
return NULL;
}
int InsertHash(HashTable& H, ElemType e)
{ int p;
Node* np;
np = SearchHash(H, e.key);
if (np == NULL)
{ p = Hash(e.key,H.size);
np = (Node*)malloc(sizeof(Node));
np->r = e;
np->next = H.rcd[p];
H.rcd[p] = np;
H.count++;
return 1;
}
else
{ return 0;
}
}
int DeleteHash(HashTable& H, KeyType key, ElemType& e)
{ /*********BEGIN*********/
Node* n;
n = SearchHash(H, key);
if (n != NULL)
{ int p = Hash(key,H.size);
Node* np, * nq;
np = H.rcd[p];
nq = NULL;
while (np != NULL)
{ if (np->r.key != key)
{ nq = np;
np = np->next;
}
else
{ e = np->r;
if (nq == NULL)//表头
{ H.rcd[p] = np->next;
}
else//不是表头
{ nq->next = np->next;
}
break;
}
}
H.count--;
free(np);
return 1;
}
else
{ return 0;
}
/**********END**********/
}
void HashTraverse(HashTable H)
{ if (H.rcd != NULL)
{ Node* np, * nq;
for (int i = 0; i < H.size; i++)
{ printf("%d: ", i);
if (H.rcd [i])
{ printf("%d ",H.rcd [i]->r .key);
Node* curr=H.rcd [i]->next;
while (curr) { printf("-> %d ", curr->r.key);
curr=curr->next;
}
printf("\n");
}
else
printf("-\n");
}
}
}
