数据结构基础详解:哈希表【C语言代码实践篇】开放地址法__拉链法_哈希表的创建_增删查操作详解

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 0

1.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); //拿到posif(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;
}