哈希表链地址法

布满荆棘的人生 2022-02-26 01:18 324阅读 0赞

/*************************************************** 目的：将一堆整数存入hash表 键值：本身 哈希函数的构造方法：除留余数法 散列冲突方法：链地址法 ***************************************************/
    #include <stdio.h>
    #include <stdlib.h>
    
    #define N 13
    
    typedef struct node
    { 
        int data;
        struct node *next;
    }listnode, *pLinklist;
    
    int insert(pLinklist h, int key)
    { 
        int value = key % N; /*除留余数法*/
        pLinklist p = &h[value]; /*p指向哈希表中应存的位置,相当于指向链表头*/
        pLinklist q = NULL; /*q生成要存的数据*/
    
        q = (pLinklist)malloc(sizeof(listnode));
        q->data = key;
        q->next = NULL;
    	/*若p->next为NULL，链表头指向空，不走while, head-->q-->NULL 若p->next不为NULL，如head-->q1-->NULL，若q1>q，不走while,head-->q-->q1-->NULL 若p->next不为NULL，如head-->q1-->NULL，若q1<q，走while,head-->q1-->q-->NULL 使链表排列是从小到大的*/
        while (p->next && p->next->data < key)
        { 
            p = p->next;
        }
        
        q->next = p->next;
        p->next = q;
        
        return 0;
    }
    
    int contains(pLinklist h, int key)
    { 
        int value = key % N;
        pLinklist p = h[value].next;
    
        while (p)
        { 
            if (p->data == key)
                return 0;
            p = p->next;
        }
        return -1;
    }
    
    void show(pLinklist p)
    { 
        while (p)
        { 
            printf("%d ", p->data);
            p = p->next;
        }
        printf("\n");
    }
    
    int main()
    { 
        /*哈希表 用链地址法处理冲突 故用节点作为数据结构 数组中节点相当于链表头，不存数据*/
        listnode hash[N] = { { 0, NULL}};
        /*要存入哈希表的数据*/
        int a[] = { 23, 23, 34, 14, 38, 46, 16, 68, 15, 7, 31, 26, 6, 6, 51, 66, 77};
    		int i = 0;
    		
        for (i = 0; i < sizeof(a)/sizeof(int); i++)
            insert(hash, a[i]);
    
        for (i = 0; i < N; i++)
            show(hash[i].next);
    
        printf("** %d\n", contains(hash, 23));
        printf("** %d\n", contains(hash, 99));
    
        return 0;
    }

结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdnb25nXzE5OTE_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdnb25nXzE5OTE_size_16_color_FFFFFF_t_70]: /images/20220226/d10d1585b4874f5ca17f1cc07b297dcd.png