数据结构基础详解:哈希表【C语言代码实践篇】开放地址法__拉链法_哈希表的创建_增删查操作详解
原创数据结构基础详解:哈希表【C语言代码实践篇】开放地址法__拉链法_哈希表的创建_增删查操作详解
原创
小徐在进步
发布于 2024-10-09 23:41:42
发布于 2024-10-09 23:41:42
文章被收录于专栏：数据结构与算法
1.哈希表代码实现之开放地址法
1.1 开放地址法创建哈希表
哈希表本质就是一个线性表，定义一个哈希表结构体，包括一个动态数组PList,表长，和关键字个数（元素个数）
代码实现的一些细节
1.没有关键字的地方，默认初始值要设置成99999（就是无穷大），因为动态设置一个数组是随机值，会影响到代码结果
//开放地址法哈希表的创建
# define INF 999999999;
typedef int ElemType;
typedef struct HashTable
{
int kNum;
ElemType *pList;
int tLength;
}HashTable;
void initial(HashTable &HT,int tlength)
{
HT.pList=(ElemType *)malloc(sizeof(HashTable)*tlength);
HT.tLength=tlength;
for(int i=0;i<tlength;i++)
{
HT.pList[i]=INF;
}
HT.kNum=0;
}
HashTable creatHT(ElemType tlength)
{
HashTable HT;
initial(HT,tlength);
return HT;
}1.2 开放地址法之查找
构建一个如上图所示的哈希表作为样例：
int main()
{
HashTable HT=creatHT(10);
getDi(HT.tLength);
HT.pList[6]=6;
HT.pList[7]=13;
HT.pList[8]=27;
HT.pList[9]=41;
HT.pList[0]=55;
HT.tLength=10;
int ret=search(54, HT);
printf("%d\n",ret);
}具体查找代码的实现：
#define P 7
int Hash(ElemType key) //除留余数法哈希函数
{
return key%P;
}
int Di[100]={0};
void getDi(int tLength) //初始化一个线性探测序列，0，1，2，3，4，5，6，.....
{
for(int i=1;i<=tLength-1;i++) //为什么是tLength-1,因为假如表长为10，地址空间是0-9
{
Di[i]=i;
}
}
int isUpperBound(int di,int tLength) //判断边界是否超过，意味着若超出边界，则哈希表中没有该元素
{
if(di>tLength-1) //是否超出查找范围
{
return 0; //超出查找范围
}
return 1;
}
int search(ElemType key,HashTable HT) //给出要查的关键字和哈希表，进行查找
{
//初始化查找
int i=0;
int Hi=(Di[i]+Hash(key))%HT.tLength; //线性探测法函数的构建，除的是表长
//如果没有超出界限，并且没有查到空白的元素，就一直找到超出界限为止
while (isUpperBound(Di[i], HT.tLength)&&HT.pList[Hi]!=INF){
if(HT.pList[Hi]==key)return 1; //找到了
i++;
Hi=(Di[i]+Hash(key))%HT.tLength;
}
return 01.3 开放地址法之插入
开放地址的插入其实就是在查找操作上进行了改进，在查找中，多引入一个pos指针，pos指针返回待插入位置或是当前哈希表已经满了，pos就返回最后一个元素地址。
查找操作的修改代码:
int search(ElemType key,HashTable HT,int &pos) //给出要查的关键字和哈希表，进行查找
{
//初始化查找
int i=0;
int Hi=(Di[i]+Hash(key))%HT.tLength; //线性探测法函数的构建，除的是表长
//如果没有超出界限，并且没有查到空白的元素，就一直找到超出界限为止
while (isUpperBound(Di[i], HT.tLength)&&HT.pList[Hi]!=INF){
if(HT.pList[Hi]==key)return 1; //找到了
i++;
Hi=(Di[i]+Hash(key))%HT.tLength;
}
pos=Hi; //这个位置可能是空白的存储单元，也可能是最后一个访问的关键字位置
return 0;
}插入代码的实现：
int insrt(ElemType key,HashTable &HT)
{
int pos=-1;
int ret=search(key, HT, pos); //拿到pos
if(ret==0&&HT.pList[pos]==INF) //ret==0意味着，我们要插入的元素，原哈希表中并不存在
{
HT.pList[pos]=key;
HT.kNum++;
return 1; //插入成功
}
return 0; //插入失败
}测试代码：
int main()
{
HashTable HT=creatHT(10);
getDi(HT.tLength);
HT.pList[6]=6; HT.pList[7]=13;HT.pList[8]=27;
HT.pList[9]=41;HT.pList[0]=55;
HT.tLength=10;
int ret=insrt(57, HT);
for (int i=0; i<HT.tLength; i++) {
printf("%d\n",HT.pList[i]);
}
}1.4 开放地址法之删除
删除操作，本质上也是在查找操作的基础上修改
找到要删除元素的位置，将那个位置的值设置为无穷大，并统计表中元素-1
修改后的查找函数:
int delete_serch(ElemType key,HashTable HT,int &pos)
{
//初始化查找
int i=0;
int Hi=(Di[i]+Hash(key))%HT.tLength; //线性探测法函数的构建，除的是表长
//如果没有超出界限，并且没有查到空白的元素，就一直找到超出界限为止
while (isUpperBound(Di[i], HT.tLength)&&HT.pList[Hi]!=INF){
if(HT.pList[Hi]==key)
{
pos=Hi;
return 1; //找到了
}
i++;
Hi=(Di[i]+Hash(key))%HT.tLength;
}
return 0;
}删除操作:
int detele_hash(ElemType key,HashTable &HT)
{
int pos=-1;
if(delete_serch(key, HT, pos)==1)
{
HT.pList[pos]=INF;
}
return 0;
}2.哈希表代码实现之链地址法(拉链法)
把这个拉链法，分成两部分，右边，就看成多条链表。
左边存储的是指针，是指针数组，也就是存储的它挂着的那些链的第一个结点
pList是指向指针数组的指针，是指针的指针
2.1 链地址法之创建哈希表
typedef struct Node
{
ElemType key;
struct Node * next;
}Node;
typedef struct ChHashTable
{
Node **pList; //指向指针数组的指针
int tlength; //哈希表长度
int kNum; //关键字的个数
}ChHashTable;
void initial(ChHashTable &CHT,int tLength)
{
CHT.pList=(struct Node**)malloc(sizeof(struct node *)*tLength); //分配动态数组
CHT.tlength=tLength;
for(int i=0;i<tLength;i++)
{
CHT.pList[i]=NULL;
}
CHT.kNum=0;
}
ChHashTable creat(int tLength)
{
ChHashTable CHT;
initial(CHT, tLength);
return CHT;
}2.2 链地址法之查找
链地址法的查找和插入基本上一样，这里省略，插入不省略
2.3 链地址法之插入
插入代码如下：
//链地址的插入其实就是单链表的插入，这里用尾插法进行链地址哈希表的插入
void insrt(ElemType key,ChHashTable &CHT)
{
int i=Hash(key); //找到待插入的数组下标
Node *pCur=CHT.pList[i]; //获取当前数组下标的第一个元素，可能空的，也可能非空，就是存储的是第一个链表的地址
Node * preNode=NULL;
if(pCur==NULL) //如果它是空的
{
struct Node * pNode=(Node *)malloc(sizeof(Node));
pNode->key=key;
pNode->next=NULL;
CHT.pList[i]=pNode;
}else
{
//如果它非空，就不断的查找，如果查到了就不插入，查不到就用尾插法插入
while(pCur!=NULL)
{
if(pCur->key==key) break; //不插入了
preNode=pCur;
pCur=pCur->next;
if(pCur==NULL) //没有找到待插入的元素，用尾插法插入
{
struct Node * pNode=(Node *)malloc(sizeof(Node));
pNode->key=key;
pNode->next=NULL;
preNode->next=pNode;
}
}
}
}测试代码如下：
int main()
{
ChHashTable CHT=creat(10);
ElemType keyList[]={31,23,17,27,19,11,13,91,61,41};
int keyListLength=10;
for(int i=0;i<keyListLength;i++)
{
insrt(keyList[i], CHT);
}
// int dd=delt(31, CHT); 删除测试
// int dd1=delt(11, CHT);
//int dd2=delt(13, CHT);
for(int i=0;i<CHT.tlength;i++)
{
Node *pCur=CHT.pList[i];
while(pCur!=NULL)
{
printf("%d ",pCur->key);
pCur=pCur->next;
}
printf("\n");
}
2.4 链地址法之删除
int delt(ElemType key,ChHashTable &CHT)
{
int i=Hash(key); //找到待插入的数组下标
Node *pCur=CHT.pList[i]; //获取当前数组下标的第一个元素，可能空的，也可能非空，就是存储的是第一个链表的地址
Node * preNode=NULL;
//在删除操作中，需要分为两种情况，第一种情况，是第一个结点，要在指针数组上操作，不是第一个结点
if(pCur==NULL)
{
return 0;
}else //在不为空的情况下，删除
{
if(pCur->key==key)
{
CHT.pList[i]=pCur->next;
free(pCur);
return 1;
}
else
{
while(pCur!=NULL) //一直找
{
if(pCur->key==key)
{
preNode->next=pCur->next;
free(pCur);
break;
}
preNode=pCur;
pCur=pCur->next;
}
}
}
return 0;
}原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
