10-7.c

数据结构的经典实现算法

#include "stdio.h"
#include <string.h>
#define MAX_CHAR  10  /*max number of characters in an identifier */                                            
#define TABLE_SIZE 13 /*max table size = prime number*/   
typedef  struct  info{   
	char  key [MAX_CHAR ];
	 /* 其他数据 */
} element;
typedef  struct  list  {
		element  item;
		struct  list *  link ;
}List;
typedef  struct  list  *list_pointer;
void init_table(element hashtable[ ])
{       
	int i ; 
    for ( i = 0 ; i < TABLE_SIZE ; i++ )
            hashtable[i].key[0] = NULL ; 
}
int transform  ( char *key )
{/* 把key转换成一个自然数*/
	int number = 0 ; 
    while   ( *key )
        number += *key++ ; 
    return number ; 
}
int hash(char *key )
{
   return (transform  (key )%TABLE_SIZE ) ; 
}
void chain_insert(list_pointer ht[],element item )
{
        int hash_value = hash  ( item.key ) ; 
        list_pointer ptr, trail = NULL, lead = ht[hash_value] ; 
        for(  ; lead ; trail = lead, lead = lead->link )
            if( !strcmp(lead->item.key, item.key ) ){
                printf( "哈希表中已经存在该关键值\n" ) ; 
                exit  (1 ) ; 
            }
        ptr =  ( list_pointer )malloc(sizeof(List ) ) ; 
        if(ptr==NULL){
            printf("内存已满\n" ) ; 
            exit(1); 
        }   
        ptr->item = item ; 
        ptr->link = NULL ; 
        if(trail )
            trail->link = ptr ; 
        else
            ht[hash_value] = ptr ; 
}

void main()
{
	list_pointer  hash_table[TABLE_SIZE ];
	element item;
	chain_insert(hash_table,item);
}