hash list

1. 拉链法实现HASH链表

    #include <stdio.h>
    #include <string.h>
    
    #define N 14
    #define M 14
    
     typedef struct struct_node{
         int key;
         struct struct_node *next;
     }node;
    
     int get_hash_key(int key)
     {
         return key % 11;
     }
    
     node **hash_init(node **hash_table,int m)
     {
         int i = 0;
    
         for ( ; i < m ; i++ )
             hash_table[i] = NULL;
    
         return hash_table;
     }
    
     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;
     }
    
     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;
     }
    
     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;
                 }
                 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;
         }
     }
    
     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;
         }
     }
    
     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;
     }