一个hash表的简单操作

时间：2007-04-19 来源：tthacker

hash表操作这么基础的东西，直到现在才写一个程序来学习下，真的够蠢了。

hash.h

#ifndef HASH_H
#define HASH_H

#define N 14
#define M 14

typedef struct struct_node{
int key;
struct struct_node *next;
}node;

//node *hash_table[M];

#endif

hash.c

/*
    简单hash表操作 by wzt
*/

#include <stdio.h>
#include <string.h>
#include "hash.h"

/* 得到关键码 */
int get_hash_key(int key)
{
    return key % 11;
}

/* hash表初始化 */
node **hash_init(node *hash_table[],int m)
{
    int i = 0;

    for ( ; i < m ; i++ )
        hash_table[i] = NULL;

    return hash_table;
}

/* 建立一个hash表 */
node **create_hash_table(node *hash_table[],int a[])
{
    node *m;
    int i = 0,key;

    for ( ; i < N ; i++ ) {
        key = get_hash_key(a[i]);
        m = (node *)malloc(sizeof(node));
        if ( !m ) {
            printf("malloc failed.\n");
            exit(0);
        }
        m->key = a[i];

        if ( hash_table[key] == NULL ) {
            hash_table[key] = m;
            m->next = NULL;
            continue;
        }

        m->next = hash_table[key];
        hash_table[key] = m;
    }

    return hash_table;
}

/* 查找hash表中的一个节点 */
node *search_node(node *hash_table[],int key)
{
    node *p;
    int i = 0,hash_key;

    hash_key = get_hash_key(key);
    p = hash_table[hash_key];

    if ( !p )
        return NULL;

    while ( p ) {
        if ( p->key == key )
            return p;
        p = p->next;
    }

    return NULL;
}

/* 删除hash表中的一个节点 */
node **delete_node(node *hash_table[],int key)
{
    node *p,*q,*head;

    p = hash_table[get_hash_key(key)];
    if ( !p ) {
        printf("[-] no key in hash_table .\n");
        return hash_table;
    }

    /* 删除的是首节点 */
    if ( p->next == NULL ) {
        hash_table[get_hash_key(key)] = NULL;
        return hash_table;
    }

    while ( p != NULL ) {
        if ( p->key == key ) {
            /* 只有两个节点的删除 */
            if ( p == hash_table[get_hash_key(key)] ) {
                hash_table[get_hash_key(key)] = p->next;
                return hash_table;
            }
            /* 3个以上节点的删除 */
            else{
                q->next = p->next;
                return hash_table;
            }
        }
        q = p;
        p = p->next;
    }

    return NULL;
}

/* 打印一个链表 */
void print_node(node *head)
{
    if ( !head )
        return ;

    while ( head != NULL ) {
        printf("%d,",head->key);
        head = head->next;
    }
}

/* 打印hash表 */
void print_hash_table(node *hash_table[])
{
    int i = 0;

    for ( ; i < M ; i++ ) {
        print_node(hash_table[i]);
        printf("\n");
    }
}

/* 释放一个链表 */
void destroy_node(node *head)
{
    node *p;

    while ( head != NULL ) {
        p = head->next;
        free(head);
        head = p;
    }
}

/* 释放一个hash表 */
void destroy_hash_table(node *hash_table[])
{
    int i = 0;

    for ( ; i < N ; i++ )
        destroy_node(hash_table[i]);
}

int main(void)
{
    node *hash_table[M],*p,**s;
    int a[N] = {47,7,29,11,16,92,22,8,3,50,37,89,94,21};

    hash_init(hash_table,M);
    printf("[+] hash init ok.\n");
    create_hash_table(hash_table,a);
    printf("[+] hash table create ok.\n");
    print_hash_table(hash_table);

    printf("..................................\n");

    p = search_node(hash_table,29);
    printf("%d\n",p->key);
    printf("..................................\n");

    s = delete_node(hash_table,8);
    if ( !s )
        printf("[-] hash_table NULL.\n");
    print_hash_table(s);

    destroy_hash_table(hash_table);
    printf("[+] destroy hash_table ok.\n");

    return 0;
}