前面写过一篇哈希表在检索SIP电话中的应用,是在阅读代码中遇到的,而专门去学习了哈希表的基本思想和哈希函数。下面自己阅读C算法精解书籍中自己总结了下面的内容。只总结一小部分,随后会继续更新。现在也在学习思维导图的应用,前面的博客中已经使用过。下面就利用思维导图总结的哈希表的内容:
下面介绍个经典的字符串哈希函数:
/*hashpjw.c*/
unsigned int hashpjw(const void *key)
{
const char *ptr;
unsigned int val;
val = 0;
ptr = key;
while (*ptr != '\0'){
unsigned int tmp;
val = (val << 4) +(*ptr);
if (tmp = (val & 0xf0000000)){
val = val ^ (tmp >> 24);
val = val ^ tmp;
}
ptr++;
}
return val%PRIME_TBLSIZ //桶的个数
}
链式哈希表构造图
链式哈希表的实现和定义
/*chtbl.h*/
#ifndef CHTBL_H
#define CHTBL_H
#include <stdlib.h>
/*单链表的头文件*/
#include "list.h"
/* 定义一个链式哈希表的结构体*/
typedef struct Chtbl_ {
int buckets; /*哈希表分配桶的个数*/
int (*h)(const void *key);/*哈希函数指针h */
int (*match)(const void *key1,const void *key2);/*判断2个键是否匹配*/
void (*destroy)(void *data);/*释放内存空间*/
int size;/*成员个数*/
List *table;/*哈希表中链表桶的头指针*/
}Chtbl;
/* 函数接口*/
int chtbl_init (Chtbl *htbl,int buckets,int (*h)(const void *key),int
(*match)(const void *key1,const void *key2),void (*destroy)(void *data));
int chtbl_destroy (Chtbl *htbl);
int chtbl_insert(Chtbl *htbl,const void *data);
int chtbl_remove (Chtbl *htbl,void **data);
int chtbl_lookup(const Chtbl *htbl,void **data);
#define chtbl_size(Chtbl *htbl) ((htbl)->size)
#endif
/*chtbl_c*/
#include <stdlib.h>
#include <string.h>
#include "./include/list.h"
#include "./include/chtbl.h"
/* 初始化哈希表结构体*/
int chtbl_init(Chtbl * htbl, int buckets, int(* h)(const void * key), int(* match)(const void * key1, const void * key2), void(* destroy)(void * data))
{
int i;
/* 申请空间为桶*/
if ((htbl->table = (List *)malloc(buckets * sizeof(List))) == NULL){
return -1;
}
/* 初始化哈希表*/
htbl->buckets = buckets;
for (i = 0; i < buckets; i++){
list_init(&htbl->table[i], destroy);
}
htbl->h = h;
htbl->match = match;
htbl->destroy = destroy;
htbl->size = 0;
return 0;
}
/*哈希表销毁*/
void chtbl_destroy(Chtbl * htbl)
{
int i;
if (htbl == NULL)
return;
/*销毁各个桶*/
for (i = 0; i < htbl->buckets; i++){
list_destory(htbl->table[i]);
}
/* 释放hash table 空间*/
free(htbl->table);
/*清空htbl结构体*/
memset(htbl,0,sizeof(Chtbl));
return ;
}
/* 插入数据
* return 成功返回0;失败返回-1;存在返回1;
*
*/
int chtbl_insert(Chtbl * htbl, const void * data)
{
void *temp;
int bucket;
int retval;
/*如何data已经在哈希表中返回1*/
temp = (void *)data;
if (chtbl_lookup(htbl, &temp) == 0)
return 1;
/*获得哈希键*/
bucket = htbl ->h(data) % htbl->buckets;
/*插入哈希表*/
if ((retval = list_ins_next(htbl->table[bucket], NULL, data)) == 0)
htbl ->size ++;
return retval;
}
/*删除数据
*return 成功返回0;失败返回-1;
*/
int chtbl_remove(Chtbl * htbl, void * * data)
{
ListElmt *element = NULL;
ListElmt *prev = NULL;
int bucket = -1;
/*获得哈希键*/
bucket = htbl ->h(*data)%htbl -> buckets;
/*查找在哈希表中的data*/
for (element = list_head(&htbl->table [bucket]);element != NULL;element =
list_next(element)){
if (htbl->match(*data,list_data(element))){
if (list_rem_next(&htbl->table[bucket], prev, data) == 0){
htbl->size --;
return 0;
} else {
return -1;
}
}
prev = element;
}
return -1;
}
/* 在哈希表中查找元素
*return :如果找到元素返回0;否则返回-1.
*/
int chtbl_lookup(const Chtbl * htbl, void * * data)
{
ListElmt *element;
int bucket;
/*获得哈希键*/
bucket = htbl -> h(*data)%htbl->buckets;
/*在哈希表中查找元素*/
for (element = list_head(&htbl->table [bucket]);element != NULL;element =
list_next(element)){
if (htbl->match(*data,list_data(element))){
*data = list_data(element);
return 0;
}
}
return -1;
}
分享到:
相关推荐
《算法精解:C语言描述》是数据结构和算法领域的经典之作,十余年来,畅销不衰!全书共分为三部分:第一部分首先介绍了数据结构和算法的概念,以及使用它们的原因和意义,然后讲解了数据结构和算法中最常用的技术...
算法精解:C语言描述》是数据结构和算法领域的经典之作,十余年来,畅销不衰!《算法精解:C语言描述》共分为三部分:第一部分首先介绍了数据结构和算法的概念,以及使用它们的原因和意义,然后讲解了数据结构和算法中...
《算法精解:C语言描述》是数据结构和算法领域的经典之作,十余年来,畅销不衰!全书共分为三部分:部分首先介绍了数据结构和算法的概念,以及使用它们的原因和意义,然后讲解了数据结构和算法中最常用的技术——...
《算法精解:C语言描述》是数据结构和算法领域的经典之作,十余年来,畅销不衰!全书共分为三部分:第一部分首先介绍了数据结构和算法的概念,以及使用它们的原因和意义,然后讲解了数据结构和算法中最常用的技术...
命名规则适用于全书所有的代码,所有的代码都包含大量注释……《算法精解:C语言描述》内容包括:数据结构和算法的概念,以及使用它们的原因和意义 指针和递归算法分析常用数据结构:链表、栈、队列、集合、哈希表、...
算法精解:C语言描述》是数据结构和算法领域的经典之作,十余年来,畅销不衰!全书共分为三部分:部分首先介绍了数据结构和算法的概念,以及使用它们的原因和意义,然后讲解了数据结构和算法中最常用的技术——指针...
第二部分对链表、栈、队列、集合、哈希表、堆、图等常用数据结构进行了深入阐述;第三部分对排序、搜索数值计算、数据压缩、数据加密、图算法、几何算法等经典算法进行了精辟的分析和讲解。 本书的众多特色使得它在...
C语言算法精解的部分代码,包括链表、哈希等,以及进程通信管道的部分。
1. 书中第一部分从讲述相关的C语言基础知识和算法分析方法入手,在随后的章节中采用软件工程中的良好准则,结合作者的实践经验将基于接口的C程序设计理念贯穿全书。使得本书中的数据结构和算法实现能够以接口的形式...
《Reilly精品图书系列·算法精解:C语言描述》内容包括: · 数据结构和算法的概念,以及使用它们的原因和意义 · 指针和递归 · 算法分析 · 常用数据结构:链表、栈、队列、集合、哈希表、树、堆、...
本书是数据结构和算法领域...第二部分对链表、栈、队列、集合、哈希表、堆、图等常用数据结构进行了深入阐述;第三部分对排序、搜索数值计算、数据压缩、数据加密、图算法、几何算法等经典算法进行了精辟的分析和讲解。
第二部分对链表、栈、队列、集合、哈希表、堆、图等常用数据结构进行了深入阐述;第三部分对排序、搜索数值计算、数据压缩、数据加密、图算法、几何算法等经典算法进行了精辟的分析和讲解。 本书的众多特色使得它在...
第二部分对链表、栈、队列、集合、哈希表、堆、图等常用数据结构进行了深入阐述;第三部分对排序、搜索数值计算、数据压缩、数据加密、图算法、几何算法等经典算法进行了精辟的分析和讲解。 本书的众多特色使得它在...
《算法精解:C语言描述》是数据结构和算法领域的经典之作,十余年来,畅销不衰!《算法精解:C语言描述》共分为三部分:第一部分首先介绍了数据结构和算法的概念,以及使用它们的原因和意义,然后讲解了数据结构和算法...
《算法精解:C语言描述》是数据结构和算法领域的经典之作,十余年来,畅销不衰!《算法精解:C语言描述》共分为三部分:第一部分首先介绍了数据结构和算法的概念,以及使用它们的原因和意义,然后讲解了数据结构和算法...