hash表-使用数组加链表实现hash表

深碍√TFBOYSˉ_ 2022-10-07 06:59 139阅读 0赞

## hash表-使用数组加链表实现hash表 ##

hash.h

typedef int ElementType;
    struct ListNode{
        
        ElementType Element;
        int val;
        struct ListNode * next;
    };
    typedef struct ListNode * Position;
    typedef Position List;
    struct HashTbl{
        
        int TableSize;
        List * TheLists;
    };
    
    typedef struct HashTbl * HashTable;
    HashTable InitializeTable(int TableSize);
    void DestroyTable(HashTable H);
    Position Find(ElementType Key,HashTable H);
    void Insert(ElementType Key,HashTable H);
    ElementType Retrieve(Position P);
    void list_free(struct ListNode * head);
    int aHash(int x);

hash.c

#include <stdio.h>
    #include <stdlib.h>
    #include "hash.h"
    
    int main()
    {
        
        HashTable H = InitializeTable(10);
        int i = 0;
        for(i=0;i<10;i++)
        {
        
            Insert(i*i,H);
        }
        Insert(99,H);
        Find(49,H);
        DestroyTable(H);
    }
    
    HashTable InitializeTable(int TableSize){
        
        HashTable H;
        int i;
        H = malloc(sizeof(struct HashTbl));
        H->TableSize = TableSize;
        H->TheLists = malloc(sizeof(List)*TableSize);
        for(i=0;i<H->TableSize;i++){
        
            H->TheLists[i] = mallic(sizeof(struct ListNode));
            H->TheLists[i]->next = NULL;
        }
        return H;
    }
    
    void DestroyTable(HashTable H){
        
        if(H==NULL)
            return;
        int tablesize = H->TableSize;
        int i = 0;
        for(i=0;i<tablesize;i++)
        {
        
            struct ListNode * head = H->TheLists[i];
            list_free(head);
        }
        free(H->TheLists);
        free(H);
    }
    
    void list_free(struct ListNode * head){
        
        if(head==NULL)
            return;
        struct ListNode * temp = head;
        while(head->next!=NULL)
        {
        
            temp = head->next;
            head->next = temp->next;
            free(temp);
        }
        free(head);
    }
    
    int aHash(int x){
        
        return x%10;
    }
    
    void Insert(ElementType Key,HashTable H){
        
        int p = aHash(Key);
        struct ListNode * po = H->TheLists[p];
        struct ListNode * temp = malloc(sizeof(struct ListNode));
        temp->Element = Key;
        temp->val = Key-1;
        temp->next = po->next;
        po->next = temp;
    }
    
    Position Find(ElementType Key,HashTable H){
        
        int p = aHash(Key);
        struct ListNode * po = H->TheLists[p];
        struct ListNode * temp = po->next;
        while(temp!=NULL){
        
            if(temp->Element==Key){
        
                printf("Key=%d, value=%d\n",Key,temp->val);
                return temp;
                break;
            }
            temp=temp->next;
         }
         return NULL;
    }