哈希表鏈地址法表示與實現

哈希表鏈地址法表示與實現

以下是經過DEV-C++調試過的代碼 還有框圖：

頭文件hashlist.h

#ifndef _H_HASHLIST_
#define _H_HASHLIST_

#define HASH_NUM_MAX 100

#define u32 unsigned int

//typedef struct _Node * pNode;
//typedef struct _Hash_Header * pHash_Header;

typedef struct _Node
{
    u32 id;
    u32 data;
    struct _Node *next;        
}Node,*pNode;

typedef struct _Hash_Header
{
    struct _Node *next;    
}Hash_Header,*pHash_Header;

typedef struct _Hash_List
{
    struct  _Hash_Header* list[100];           
}Hash_List,*pHash_List;

pHash_List init_hash_list(void);
//pHash_Header init_hash_header(void);
//pNode init_node_header(void);
//void init_all_node_header(void);
pNode insert_node_to_hash(pHash_List plist,u32 id,u32 data);
int delete_node_to_hash(pHash_List plist,u32 id);
void print_hash(pHash_List plist);
int free_all_hash(pHash_List plist); 


#endif

存放數據結構的文件hashlist.h

/********************************************

編寫時間：2014.12.10
作者：XIAO_PING_PING
內容：哈希表（拉鏈式） 
功能：學習寫數據結構 
 
********************************************/
#include 
#include 
#include 

#include "hashlist.h"

//pHash_Header hash_list[HASH_NUM_MAX];


/*初始化一個哈希表*/
pHash_List init_hash_list(void)
{
    u32 i;
    pHash_List plist;
    //pHash_Header phead;
    
    plist = (Hash_List *)malloc(sizeof(Hash_List)); 
    
    for( i = 0;i < 100;i++ )
    {
        plist->list[i] = (Hash_Header *)malloc(sizeof(Hash_Header)); 
        plist->list[i]->next = NULL;
    }     
    
    return plist;
} 

#if 0
/*初始化一個哈希鏈表頭*/
pHash_Header init_hash_header(void)
{
    Hash_Header *phead;
    
    phead = (Hash_Header *)malloc(sizeof(Hash_Header));
    phead->next = NULL;
    
    return phead;
}

/*初始化一個鏈表節點頭*/ 
pNode init_node_header(void)
{
    Node *phead;
    
    phead = (Node *)malloc(sizeof(Node));
    phead->next = NULL;
    
    return phead;      
} 

/*初始化所有節點鏈表頭*/
void init_all_node_header(void)
{
    u32 i;
    Hash_Header *plist;
    
    for( i = 0;i < HASH_NUM_MAX;i++)
    {
       hash_list[i] = init_hash_header(); 
    }
}
#endif
/*根據id插入一個節點數據*/
pNode insert_node_to_hash(pHash_List plist,u32 id,u32 data)
{
    Node *ptail,*pre,*p;
    u32 temp = id % 100;
    
    ptail = (Node *)malloc(sizeof(Node));
    ptail->next = NULL;
    ptail->data = data;
    ptail->id   = id;
    
    if( NULL == plist->list[temp]->next )
    {
        plist->list[temp]->next = ptail;
        
        printf("鏈表插入點id=%d\n",ptail->id); 
        
        return ptail;
    }
    pre = plist->list[temp]->next;
    while( pre )
    {
        p = pre;
        pre = pre->next;   
    }
    p->next = ptail;
    printf("鏈表插入點id=%d\n",ptail->id); 
    
    return ptail;
}

/*根據id刪除一個節點數據*/
int delete_node_to_hash(pHash_List plist,u32 id)
{
   u32 temp = id % 100;
   Node *psea;
   
   psea = plist->list[temp]->next; 
   if( NULL == psea )
   {
       printf("搜索的鏈表內容為空\n"); 
       return -1; 
   }
 #if 1  
   if(id == psea->id )
   {
       plist->list[temp]->next = psea->next;  
       free(psea);
       //printf("該鏈表唯一元素被刪除\n"); 
       printf("正確刪除數據\n"); 
       return 0; 
   }
 #endif  
   if( NULL == psea->next )
   {
       printf("搜索的id不存在\n"); 
       return -2;    
   } 
   
   while( id != psea->next->id )
   {
       psea = psea->next;
       if( NULL == psea->next )
       {
           printf("搜索的id不存在\n"); 
           return -2;    
       }       
   } 
   psea->next = psea->next->next;
   free(psea->next);
   
   printf("正確刪除數據\n"); 
   return 0;  
}

/*遍歷打印哈希表信息*/
void print_hash(pHash_List plist)
{
    u32 i;
    pNode p; 
    
    printf("打印整個哈希表信息:\n"); 
    
    for( i = 0;i < 100;i++)
    {
        p = plist->list[i]->next;
        if(NULL != p)
        {
            printf("第%d排: \n",i);       
        }
  
        while( NULL != p )
        {
            printf("節點id=%d，節點信息data=%d\n",p->id,p->data);
            
            p = p->next;
        }        
    }
} 

/*釋放整個哈希表數據*/
int free_all_hash(pHash_List plist)
{
    u32 i;
    pNode p,pn; 
    
    printf("\n釋放哈希表內存空間:\n"); 
    
    for( i = 0;i < 100;i++)
    {
        p = plist->list[i]->next;;
        pn = p;
        if(NULL == p)
        {
            continue;
        }
        printf("釋放第%d排: \n",i);    
        while( NULL != pn )
        {
            p = pn;
            pn = p->next;
            
            printf("節點id=%d，節點信息data=%d\n",p->id,p->data);  
            free(p);              
            //p = p->next;
        }      
        free(plist->list[i]);  
    }
    
} 

以及測試文件main.c

/********************************************/
#include 
#include 
#include 
#include 

#include "hashlist.h"

int main()
{
    pNode p;
    pHash_List plist;

    plist = init_hash_list();
    insert_node_to_hash(plist,301,138);
    insert_node_to_hash(plist,32,1334);
    insert_node_to_hash(plist,201,137);
    
    print_hash(plist);
    
    delete_node_to_hash(plist,32);
    //delete_node_to_hash(plist,201);
    //delete_node_to_hash(plist,301);
    
    print_hash(plist);
    
    free_all_hash(plist);
    
    getch();
}

最後得出測試結果