6.C-数据结构-查询-哈希表

#include "hash.h" #include <stdio.h> #include <string.h> #include <stdlib.h> /* * hash_create:创建哈希表 * param len:哈希表的长度 * @ret NULL--err other--哈希表的指针 * */ hash* hash_create(int len){ hash* pHash = NULL; //1.申请空间 //1.1 申请哈希结构体空间 pHash = (hash*)malloc(sizeof(hash)); if(pHash == NULL){ printf("hash malloc err\n"); return NULL; } //1.2 申请存放链表结点指针的数组空间 pHash->pArr = (linklist)malloc(sizeof(listnode)*len); if(pHash->pArr == NULL){ printf("pArr malloc err\n"); free(pHash); return NULL; } //2.初始化 memset(pHash->pArr,0,sizeof(linklist)*len); pHash->len = len; return pHash; } /* * hashNode_create:创建哈希结点 * param key:结点的键值 * param data:结点的数据 * @ret NULL--err other--结点地址 * */ linklist hashNode_create(keyType key,data_t data){ linklist pHashNode = NULL; //1.申请空间 pHashNode = (linklist)malloc(sizeof(listnode)); if(pHashNode == NULL){ printf("malloc err\n"); return NULL; } //2.初始化 pHashNode->key = key; pHashNode->data = data; pHashNode->pNext = NULL; return pHashNode; } /* * hash_insert:在哈希表中插入数据 * param pHash:哈希表的指针 * param pHashNode:新数据的指针 * @ret -1--err 0--success * */ int hash_insert(hash* pHash,linklist pHashNode){ int hash_i;//数据哈希表中的位置 linklist pHead = NULL;//同一位置的链表头 linklist pIn = NULL;//插入点 linklist pAhead = NULL;//插入点前一个结点 //1.判断参数有效性 if(pHash == NULL || pHashNode == NULL){ printf("param err\n"); return -1; } //2.获取结点在哈希表中的位置 hash_i = pHashNode->key % pHash->len; pHead = &(pHash->pArr[hash_i]); pIn = pHead->pNext; pAhead = pHead; //3.在指定哈希表位置处插入 //3.1 指定位置出为空 if(pHead->pNext == NULL){ pHead->pNext = pHashNode; } //3.2 指定位置有数据，键值小的放前面 else{ //3.2.1 遍历插入 while(pIn != NULL){ if(pHashNode->key < pIn->key){ //插入到当前结点前面 pAhead->pNext = pHashNode; pHashNode->pNext = pIn; break; } pAhead = pIn; pIn = pIn->pNext; } //3.2.2 遍历之后依旧没插入,将结点尾插 if(pIn == NULL){ pAhead->pNext = pHashNode; } } return 0; } /* * hash_search:根据键值查找元素 * param pHash:哈希表的指针 * param pHashNode:找到的数据存放的位置 * param key:键值 * @ret -1--err 0--find it * */ int hash_search(hash* pHash,linklist* ppHashNode,keyType key){ int hash_i;//数据哈希表中的位置 linklist pHead = NULL;//同一位置的链表头 linklist pTmp = NULL; //1.判断参数有效性 if(pHash == NULL || ppHashNode == NULL){ printf("param err\n"); return -1; } //2.获取结点在哈希表中的位置 hash_i = key % pHash->len; pHead = &(pHash->pArr[hash_i]); pTmp = pHead->pNext; //3.遍历查找 while(pTmp != NULL){ if(pTmp->key == key){ *ppHashNode = pTmp; break; } pTmp = pTmp->pNext; } if(pTmp == NULL){ //没找到 printf("not find\n"); return -1; }else{ //找到了 return 0; } }