搜尋此網誌

2011年5月14日 星期六

hash list

  1. 拉链法实现HASH链表
    1.  #include <stdio.h>
    2.  #include <string.h>
    3.  
    4.  #define N 14
    5.  #define M 14
    6.  
    7.   typedef struct struct_node{
    8.       int key;
    9.       struct struct_node *next;
    10.   }node;
    11.  
    12.   int get_hash_key(int key)
    13.   {
    14.       return key % 11;
    15.   }
    16.  
    17.   node **hash_init(node **hash_table,int m)
    18.   {
    19.       int i = 0;
    20.  
    21.       for ( ; i < m ; i++ )
    22.           hash_table[i] = NULL;
    23.  
    24.       return hash_table;
    25.   }
    26.  
    27.   node **create_hash_table(node **hash_table,int *a)
    28.   {
    29.       node *m;
    30.       int i = 0,key;
    31.  
    32.       for ( ; i < N ; i++ ) {
    33.           key = get_hash_key(a[i]);
    34.           m = (node *)malloc(sizeof(node));
    35.           if ( !) {
    36.               printf("malloc failed.\n");
    37.               exit(0);
    38.           }
    39.           m->key = a[i];
    40.  
    41.           if ( hash_table[key] == NULL ) {
    42.               hash_table[key] = m;
    43.               m->next = NULL;
    44.               continue;
    45.           }
    46.  
    47.           m->next = hash_table[key];
    48.           hash_table[key] = m;
    49.       }
    50.  
    51.       return hash_table;
    52.   }
    53.  
    54.   node *search_node(node **hash_table,int key)
    55.   {
    56.       node *p;
    57.       int i = 0,hash_key;
    58.  
    59.       hash_key = get_hash_key(key);
    60.       p = hash_table[hash_key];
    61.  
    62.       if ( !)
    63.           return NULL;
    64.  
    65.       while ( p ) {
    66.           if ( p->key == key )
    67.               return p;
    68.           p = p->next;
    69.       }
    70.  
    71.       return NULL;
    72.   }
    73.  
    74.   node **delete_node(node **hash_table,int key)
    75.   {
    76.       node *p,*q,*head;
    77.  
    78.       p = hash_table[get_hash_key(key)];
    79.       if ( !) {
    80.           printf("[-] no key in hash_table .\n");
    81.           return hash_table;
    82.       }
    83.  
    84.       if ( p->next == NULL ) {
    85.           hash_table[get_hash_key(key)] = NULL;
    86.           return hash_table;
    87.       }
    88.  
    89.       while ( p != NULL ) {
    90.           if ( p->key == key ) {
    91.               if ( p == hash_table[get_hash_key(key)] ) {
    92.                   hash_table[get_hash_key(key)] = p->next;
    93.                   return hash_table;
    94.               }
    95.               else{
    96.                   q->next = p->next;
    97.                   return hash_table;
    98.               }
    99.           }
    100.           q = p;
    101.           p = p->next;
    102.       }
    103.  
    104.       return NULL;
    105.   }
    106.  
    107.   void print_node(node *head)
    108.   {
    109.       if ( !head )
    110.           return ;
    111.  
    112.       while ( head != NULL ) {
    113.           printf("%d,",head->key);
    114.           head = head->next;
    115.       }
    116.   }
    117.  
    118.   void print_hash_table(node **hash_table)
    119.   {
    120.       int i = 0;
    121.  
    122.       for ( ; i < M ; i++ ) {
    123.           print_node(hash_table[i]);
    124.           printf("\n");
    125.       }
    126.   }
    127.  
    128.   void destroy_node(node *head)
    129.   {
    130.       node *p;
    131.  
    132.       while ( head != NULL ) {
    133.           p = head->next;
    134.           free(head);
    135.           head = p;
    136.       }
    137.   }
    138.  
    139.   void destroy_hash_table(node **hash_table)
    140.   {
    141.       int i = 0;
    142.  
    143.       for ( ; i < N ; i++ )
    144.           destroy_node(hash_table[i]);
    145.   }
    146.  
    147.   int main(void)
    148.   {
    149.       node *hash_table[M],*p,**s;
    150.       int a[N] = {47,7,29,11,16,92,22,8,3,50,37,89,94,21};
    151.  
    152.       hash_init(hash_table,M);
    153.       printf("[+] hash init ok.\n");
    154.       create_hash_table(hash_table,a);
    155.       printf("[+] hash table create ok.\n");
    156.       print_hash_table(hash_table);
    157.  
    158.       printf("..................................\n");
    159.  
    160.       p = search_node(hash_table,29);
    161.       printf("%d\n",p->key);
    162.       printf("..................................\n");
    163.  
    164.       s = delete_node(hash_table,8);
    165.       if ( !)
    166.           printf("[-] hash_table NULL.\n");
    167.       print_hash_table(s);
    168.  
    169.       destroy_hash_table(hash_table);
    170.       printf("[+] destroy hash_table ok.\n");
    171.  
    172.       return 0;
    173.   }

沒有留言:

張貼留言