标签归档:哈希表

简单哈希表(hash table c)

hash表,有时候也被称为散列表。

引自wiki: 散列表(Hash table,也叫哈希表),是根据关键字(Key value)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称做散列函数,存放记录的数组称做散列表。
下面我们可以写一个简单的hash操作代码。

定义哈希表数据类型

/* hash.h */
#include <stdbool.h>

#ifndef HASH_H
#define HASH_H

typedef struct _NODE {
        int data;
        struct _NODE *next;
} NODE;

typedef struct _HASH_TABLE {
        NODE *value[10];
} HASH_TABLE;

HASH_TABLE *create_hash_table(void);
NODE *find_data_in_hash(HASH_TABLE *pHashTab, int data);
void print_hash_table(HASH_TABLE *pHashTab);
bool insert_data_into_hash(HASH_TABLE *pHashTab, int data);
bool delete_data_from_hash(HASH_TABLE *pHashTab, int data);
bool delete_idx_data_from_hash(HASH_TABLE *pHashTab, int idx);
bool delete_all_data_from_hash(HASH_TABLE *pHashTab);
bool reset_hash_table(HASH_TABLE *pHashTab);
bool destroy_hash_table(HASH_TABLE **ppHashTab);

#endif//HASH_H

继续阅读

按文件名存储-哈希表

通过散列函数将数据值和它的存储位置联系起来。即通过精心地向表载入元素实现,从而提高访问速度。本例中采取的解决冲突的办法是建立一个链表,挂在这个位置的后面,所有散列函数值为这个位置的元素都添加到这个链表中,可以从头部插入也可以从尾部追加,甚至可以再这个位置后面再挂一个散列表。代码实现了将文件名按字母a-z分类,不区分大小写。先以数组存储各节点,当发生冲突后即将节点加入链表中。然后遍历显示所有的文件名。

/* a2z.c */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define HASHSIZE 26
#define FILENAMELENGTH 20
#define TRUE 1
#define FALSE 0

struct file {
        char name[FILENAMELENGTH];
        struct file *next;
};

struct file * files[HASHSIZE];

char case_insensitive(char ch)
{
        if (isupper(ch))
                return ch - 'A' + 'a';
        return ch;
}

void init(void)
{
        int i;
        for (i = 0; i < HASHSIZE; i++)
                files[i] = NULL;
}

int hash(char *s)
{
        return case_insensitive(s[0]) - 'a';
}

int search(char *s)
{
        int num = hash(s);
        if (files[num] != NULL) {
                struct file *p = files[num];
                while (p != NULL) {
                        if (strcmp(p->name, s) == 0)
                                return TRUE;
                        p = p->next;
                }
        }

        return FALSE;
}

void insert(char *s)
{
        if (search(s) == FALSE) {
                int num = hash(s);
                struct file *new_node = malloc(sizeof (struct file));
                strcpy(new_node->name, s);
                if (files[num] == NULL) {
                        files[num] = new_node;
                        files[num]->next = NULL;
                } else {
                        new_node->next = files[num];
                        files[num] = new_node;
                }
        }

        return;
}

void free_node(struct file *p)
{
        free(p);

        return;
}


void del_node(char *s)
{
        if (search(s) == TRUE) {
                struct file *p = files[hash(s)], *q;
                if (strcmp(p->name, s) == 0) {
                        q = p;
                        files[hash(s)] = p->next;
                        free_node(q);
                } else {
                        while (p != NULL) {
                                q = p;
                                p = p->next;
                                if (strcmp(p->name, s) == 0)
                                        free_node(q);
                        }
                }
        }

        return;
}


void del(int num)
{
        struct file *p =files[num], *q;
        while (p != NULL) {
                q = p;
                p = p->next;
                free(q);
        }

        return;
}

void destroy(void)
{
        int i;

        for (i = 0; i < HASHSIZE; i++)
                del(i);

        return;
}

void show(int num)
{
        struct file *p = files[num];
        if (p != NULL) {
                printf("For file begins with '%c': \n", num + 'a');
                while (p != NULL) {
                        printf("%s\n", p->name);
                        p = p->next;
                }
                printf("\n");
        }



}

void show_all(void)
{
        int i;
        for (i = 0; i < HASHSIZE; i++)
                show(i);

        return;
}

int main(void)
{
        char * file_name[] = {
                "apple", "because", "song", "Dan", "discuz", "cartoon",
                "nobody", "android", "information", "love", "like", "No",
                "nothing", "like", "alone", "nothing", "sizeof", "Yes",
        };

        int len = sizeof file_name / sizeof (char *);
        int i;
        for (i = 0; i < len; i++)
                insert(file_name[i]);
        show_all();

        printf("---------------------------------\n");
        del_node("like");
        show_all();
        destroy();

        return 0;
}

继续阅读