哈希----链地址法
代码#pragma once//链式哈希//链地址法中后边链接的单链表的有效节点设计:typedefint ELEM_TYPE;#define MAX_SIZE 12typedef struct Node{ELEM_TYPE data; //一个数据域struct Node* next; //一个指针域}Node,*PNode;typedef struct Head{struct Nodearr[
文章共976字 · 阅读需要大约4分钟
一键AI生成摘要,助你高效阅读
问答
·
我们将介绍采取链地址法来处理哈希冲突。
链地址法:将所有关键字为同义词的记录存储在同一线性单链表中,我们称这种表为同义词子表,在哈希表中只存储所有同义词子表的头指针。对于关键字集合{12,67,56,16,25,37,22,29,47,48,34},我们用12作为除数,进行除留余数法,可得到下图结构,此时,就不存在哈希冲突换地址的问题,无论有多少个冲突,都只是在当前位置给单链表增加结点的问题。
链地址法对于可能会造成很多冲突的哈希函数来说,提供了绝不会出现找不到地址的保障。当然,这也增加了查找时需要遍历单链表的性能消耗。
链地址法的结构体设计
//链地址法中后边链接的单链表的有效节点设计:
typedef int ELEM_TYPE;
#define MAX_SIZE 12
typedef struct Node
{
ELEM_TYPE data; //一个数据域
struct Node* next; //一个指针域
}Node,*PNode;
typedef struct Head
{
struct Node arr[MAX_SIZE]; //每一个格子存放一个单链表的表头(用的是有效节点的
}Head,*PHead;
代码实现:
#pragma once
//链式哈希
//链地址法中后边链接的单链表的有效节点设计:
typedef int ELEM_TYPE;
#define MAX_SIZE 12
typedef struct Node
{
ELEM_TYPE data; //一个数据域
struct Node* next; //一个指针域
}Node,*PNode;
typedef struct Head
{
struct Node arr[MAX_SIZE]; //每一个格子存放一个单链表的表头(用的是有效节点的
}Head,*PHead;
//初始化
void Init_hash(struct Head* hd);
//插入 头插
bool Insert_head(PHead hd,ELEM_TYPE val);
//删除
bool Del_val(PHead hd, ELEM_TYPE val);
//查找
PNode Search(PHead hd, ELEM_TYPE val);
//判空
bool Isempty(PHead hd);
//获取有效个数
int Get_length(PHead hd);
//清空
void Clear(PHead hd);
//销毁
void Destroy(PHead hd);
//打印
void Show(PHead hd);
#include<stdio.h>
#include<assert.h>
#include<malloc.h>
#include"list_hash.h"
//初始化
void Init_hash(struct Head* hd)
{
assert(hd != NULL);
if (hd == NULL)
{
return;
}
for (int i = 0; i < MAX_SIZE; i++)
{
hd->arr[i].next = NULL;
}
}
//插入 头插
bool Insert_head(PHead hd,ELEM_TYPE val)
{
assert(hd != NULL);
if (hd == NULL)
{
return false;
}
//购买新节点
PNode pnewnode = (PNode)malloc(sizeof(Node));
assert(pnewnode != NULL);
if (pnewnode == NULL)
{
return false;
}
pnewnode->data = val;
//找到插入位置
int hash = val % MAX_SIZE;
//移动指向
pnewnode->next = hd->arr[hash].next;
hd->arr[hash].next = pnewnode;
}
//删除 (从前向后遍历一遍,确实存在val这个节点,则删除)//像单链表的按值删除
bool Del_val(PHead hd, ELEM_TYPE val)
{
assert(hd != NULL);
if (hd == NULL)
{
return false;
}
//找到删除位置
int hash = val % MAX_SIZE;
//保存头结点的地址
PNode p = &hd->arr[hash];
for (p; p->next!= NULL; p = p->next) //需要前驱的for循环
{
if (p->next->data == val)
{
PNode q = p->next;
p->next = q->next;
free(q);
q = NULL;
return true;
}
}
return false;
}
//查找
PNode Search(PHead hd,ELEM_TYPE val)
{
int hash = val % MAX_SIZE;
PNode p = hd->arr[hash].next;
for (p; p != NULL; p = p->next) //查找不用前驱的for循环
{
if (p->data == val)
{
return p;
}
}
return NULL;
}
//判空
bool Isempty(PHead hd)
{
return Get_length(hd) == 0;
}
//获取有效个数
int Get_length(PHead hd)
{
assert(hd != NULL);
if (hd == NULL)
{
return -1;
}
int count = 0;
for (int i = 0; i < MAX_SIZE; i++)
{
PNode p = hd->arr[i].next;
for (p; p != NULL; p = p->next)
{
count++;
}
}
}
//清空
void Clear(PHead hd)
{
Destroy(hd);
}
//销毁
void Destroy(PHead hd)
{
for (int i = 0; i < MAX_SIZE; i++)
{
while (hd->arr[i].next != NULL)
{
struct Node* p = hd->arr[i].next;
hd->arr[i].next = p->next;
free(p);
}
}
}
//打印
void Show(PHead hd)
{
for (int i = 0; i < MAX_SIZE; i++)
{
printf("%d: ", i);
struct Node* p = hd->arr[i].next;//保存首元素的地址
for (p; p != NULL; p = p->next) //查找,不需要前驱的for循环
{
printf("%d ", p->data);
}
printf("\n");
}
}
测试用例
更多推荐
已为社区贡献1条内容
所有评论(0)