目录
学习数据结与算法,我最大的感受就是:学完相关的知识点其实并不难,主要是学会真正将所学知识点与实际相结合,其实,这也是学习任何知识所具备的一个基本素养,唯有将理论与实践相结合,做出结果,才是真正的掌握!
总之,积极钻研,深度思考,勤加练习,熟练运用是我现阶段所追求的目标!加油!!!
哈希表的顺序存储
原理:存在一个哈希桶,根据分组序号,将键相同的数据存储在一个顺序表中,每一个键对应一个顺序表.
实现哈希表的顺序存储让我废了很大劲,现在想想,也就那样,主要还是对于前面知识点的掌握程度不够,所以导致在很多地方出错,通俗一点叫写BUG.
话不多说,直接上代码.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "hash_table.h"
/*根据key计算索引,定位Hash桶的位置*/
int Hash(int key, int TableSize) {
return (key % TableSize);
}
/*初始化哈希表*/
HashTable* InitHash(int TableSize) {
int i = 0;
HashTable* hTable = NULL;
if (TableSize <= 0) {
TableSize = DEFAULT_SIZE;
}
hTable = (HashTable*)malloc(sizeof(HashTable));
if (hTable == NULL) {
printf("HashTable malloc error.\n");
return NULL;
}
hTable->TableSize = TableSize;
//为Hash桶分配内存空间,其为一个指针数组
hTable->Thelists = (List*)malloc(sizeof(List) * TableSize);
if (hTable->Thelists == NULL) {
printf("Thelists malloc error!\n");
free(hTable);
return NULL;
}
//为Hash桶对应的指针数组初始化链表节点
for (i = 0; i < TableSize; i++) {
hTable->Thelists[i] = (ListNode*)malloc(sizeof(ListNode));
if (hTable->Thelists[i] == NULL) {
printf("Thelists malloc error!\n");
free(hTable);
return NULL;
}
else {
memset(hTable->Thelists[i], 0, sizeof(ListNode));
}
}
return hTable;
}
/*从哈希表中根据键值查找元素*/
Element Find(HashTable* HashTable, int key) {
int i = 0;
List L = NULL;
Element e = NULL;
i = Hash(key, HashTable->TableSize);
L = HashTable->Thelists[i];
e = L->next;
while (e != NULL && e->key != key) {
e = e->next;
}
return e;
}
/*哈希表插入*/
void Insert(HashTable* HashTable, int key, void* value) {
Element e = NULL, tmp = NULL;
List L = NULL;
e = Find(HashTable, key);
if (e == NULL) {
tmp = (Element)malloc(sizeof(ListNode));
if (tmp == NULL) {
printf("malloc error!\n");
return;
}
L = HashTable->Thelists[Hash(key, HashTable->TableSize)];
tmp->key = key;
tmp->data = value;
tmp->next = L->next;//前插法
L->next = tmp;
}
else {
printf("the key already exist!\n");
}
}
/*哈希表删除元素*/
void Delete(HashTable* HashTable, int key) {
Element e = NULL, last = NULL;
List L = NULL;
int i = Hash(key, HashTable->TableSize);
L = HashTable->Thelists[i];
last = L;
e = L->next;
while (e != NULL && e->key != key) {
last = e;
e = e->next;
}
if (e) {
last->next = e->next;
delete(e);
}
}
/*哈希表元素中提取数据*/
void* Retrieve(Element e) {
return e ? e->data : NULL;
}
/*销毁哈希表*/
void Destory(HashTable* HashTable) {
int i = 0;
Element cur = NULL, next = NULL;
List L = NULL;
for ( i = 0; i < HashTable->TableSize; i++){
L = HashTable->Thelists[i];
cur = L->next;
while (cur != NULL) {
next = cur->next;
free(cur);
cur = next;
}
free(L);
}
free(HashTable->Thelists);
free(HashTable);
}
int main(void) {
char* elems[] = { (char* )"翠花",(char*)"小芳",(char*)"苍老师" };
int i = 0;
HashTable* HashTable;
HashTable = InitHash(31);
Insert(HashTable, 1, elems[0]);
Insert(HashTable, 2, elems[1]);
Insert(HashTable, 3, elems[2]);
Delete(HashTable, 1);
for (i; i < 4; i++) {
Element e = Find(HashTable, i);
if (e) {
printf("%s\n", (const char*)Retrieve(e));
}
else {
printf("Not Found![key:%d]\n", i);
}
}
return 0;
}
哈希表的链式存储
相较于顺序存储,原理不变,只是存储方式变为单链表的形式.
需要注意的是,在哈希桶的结构定义时运用了二级指针,但也不是很难理解,就那样.(具体怎么样,自己体会一下就知道啦)
上代码
hash_table.h
#pragma once
#define DEFAULT_SIZE 16
/*哈希表元素定义*/
typedef struct _ListNode {
struct _ListNode* next;
int key;
void* data;
}ListNode;
typedef ListNode* List;
typedef ListNode* Element;
/*哈希表结构定义*/
typedef struct _HashTable {
int TableSize;
List* Thelists;
}HashTable;
/*哈希函数*/
int Hash(int key, int TableSize);
/*初始化哈希函数*/
HashTable* InitHash(int TableSize);
/*哈希表插入*/
void Insert(HashTable* HashTable, int key, void* value);
/*哈希表查找*/
Element Find(HashTable* HashTable, int key);
/*哈希表删除元素*/
void Delete(HashTable* HashTable, int key);
/*哈希表销毁*/
void Destory(HashTable* HashTable);
/*哈希表元素中提取数据*/
void* Retrieve(Element e);main.cpp
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "hash_table.h"
/*根据key计算索引,定位Hash桶的位置*/
int Hash(int key, int TableSize) {
return (key % TableSize);
}
/*初始化哈希表*/
HashTable* InitHash(int TableSize) {
int i = 0;
HashTable* hTable = NULL;
if (TableSize <= 0) {
TableSize = DEFAULT_SIZE;
}
hTable = (HashTable*)malloc(sizeof(HashTable));
if (hTable == NULL) {
printf("HashTable malloc error.\n");
return NULL;
}
hTable->TableSize = TableSize;
//为Hash桶分配内存空间,其为一个指针数组
hTable->Thelists = (List*)malloc(sizeof(List) * TableSize);
if (hTable->Thelists == NULL) {
printf("Thelists malloc error!\n");
free(hTable);
return NULL;
}
//为Hash桶对应的指针数组初始化链表节点
for (i = 0; i < TableSize; i++) {
hTable->Thelists[i] = (ListNode*)malloc(sizeof(ListNode));
if (hTable->Thelists[i] == NULL) {
printf("Thelists malloc error!\n");
free(hTable);
return NULL;
}
else {
memset(hTable->Thelists[i], 0, sizeof(ListNode));
}
}
return hTable;
}
/*从哈希表中根据键值查找元素*/
Element Find(HashTable* HashTable, int key) {
int i = 0;
List L = NULL;
Element e = NULL;
i = Hash(key, HashTable->TableSize);
L = HashTable->Thelists[i];
e = L->next;
while (e != NULL && e->key != key) {
e = e->next;
}
return e;
}
/*哈希表插入*/
void Insert(HashTable* HashTable, int key, void* value) {
Element e = NULL, tmp = NULL;
List L = NULL;
e = Find(HashTable, key);
if (e == NULL) {
tmp = (Element)malloc(sizeof(ListNode));
if (tmp == NULL) {
printf("malloc error!\n");
return;
}
L = HashTable->Thelists[Hash(key, HashTable->TableSize)];
tmp->key = key;
tmp->data = value;
tmp->next = L->next;//前插法
L->next = tmp;
}
else {
printf("the key already exist!\n");
}
}
/*哈希表删除元素*/
void Delete(HashTable* HashTable, int key) {
Element e = NULL, last = NULL;
List L = NULL;
int i = Hash(key, HashTable->TableSize);
L = HashTable->Thelists[i];
last = L;
e = L->next;
while (e != NULL && e->key != key) {
last = e;
e = e->next;
}
if (e) {
last->next = e->next;
delete(e);
}
}
/*哈希表元素中提取数据*/
void* Retrieve(Element e) {
return e ? e->data : NULL;
}
/*销毁哈希表*/
void Destory(HashTable* HashTable) {
int i = 0;
Element cur = NULL, next = NULL;
List L = NULL;
for ( i = 0; i < HashTable->TableSize; i++){
L = HashTable->Thelists[i];
cur = L->next;
while (cur != NULL) {
next = cur->next;
free(cur);
cur = next;
}
free(L);
}
free(HashTable->Thelists);
free(HashTable);
}
int main(void) {
char* elems[] = { (char* )"翠花",(char*)"小芳",(char*)"苍老师" };
int i = 0;
HashTable* HashTable;
HashTable = InitHash(31);
Insert(HashTable, 1, elems[0]);
Insert(HashTable, 2, elems[1]);
Insert(HashTable, 3, elems[2]);
Delete(HashTable, 1);
for (i; i < 4; i++) {
Element e = Find(HashTable, i);
if (e) {
printf("%s\n", (const char*)Retrieve(e));
}
else {
printf("Not Found![key:%d]\n", i);
}
}
return 0;
}