Skip to content

Latest commit

 

History

History
212 lines (156 loc) · 7.2 KB

从零开始学习数据结构_散列桶.md

File metadata and controls

212 lines (156 loc) · 7.2 KB

散列桶的本质是哈希表，哈希表的本质是 K-V，K-V 不就是 map，那么这样一层一层学习下来，就能理解的更为透彻，学习编程一定要有追根刨底的好奇心，这样你的进步会非常快。

一、桶

就是可以存放数据的结构，在这里我认为桶就是结构体！

在哈希表的改进之上，哈希表当时自己的做法是：表中存放的是指针，而不能存放数据；

现在用桶存储：哈希表中的每个元素是结构体，有数据域和链域！(根据自己的情况不同而进行规定存放数据的多少和相应的有几个链域)；其后哈希结点也可以这样定义，结点存放数据多少自己都可以定义；表中的结构体和结点的结构体没有什么联系！

在这我为了简单起见，让表中元素的结构体类型和链表结点类型一致。

模型图：

二、实际问题

现在就是有一个存放整数的 Hash 表，Hash 表的存储单位叫做桶，每个桶存放 3 个整数，当一个桶中的元素超过 3 个时，要将新的元素存放在溢出桶中，每个溢出桶最多也只能放 3 个元素，多个溢出桶用链表串起来，此 Hash 表的基桶数目为 P，Hash 表的 hash 函数为对 P 取模，初始化桶时，要求数据默认为 -1，指针为 NULL，要求代码实现上述内容。

2.1 问题分析

Hash 表的存储单位叫做桶 --> 就是说 Hash 表元素的数据类型是结构体。

结构体中有 3 个数据域和 1 个指针域，溢出桶的结构体类型和表元素类型一致；哈希函数用的是除留余数法。

这个问题的模型和上面的那个图正好一一对应。

2.2 代码实现

在这我只实现了初始化，插入，输出的函数。

我把函数声明和定义都写在了 .h 文件中，只是为了方便；声明和定义本质上是应该分开写的。

以下代码都是纯 C 写的，与 C++ 没有牵扯。

#ifndef _BUCKET_HASH_H_
#define _BUCKET_HASH_H_

#include<malloc.h>

typedef unsigned char boolean;

#define TRUE    1
#define FALSE    0

#define P                    7
#define BUCKET_NODE_SIZE    3
#define NULL_DATA            -1

//表和结点都是这个结构体类型
typedef struct BUCKET_NODE{
    ElemType data[BUCKET_NODE_SIZE];
    struct BUCKET_NODE *next;
}BUCKET_NODE;

typedef BUCKET_NODE HashTable[P];

int Hash(ElemType key){
    return key % P;
}
//初始化哈希表，只不过是桶的形式。
void initHashTable(HashTable ht);
boolean insertNewElement(HashTable ht, ElemType value);
void showHashTable(HashTable ht);

void showHashTable(HashTable ht){  //显示表中元素
    int i;
    int j;
    BUCKET_NODE *p;

    for(i = 0; i < P; i++){
        printf("%d : ", i);
        if(ht[i].data[0] != NULL_DATA){
            for(j = 0; j < BUCKET_NODE_SIZE; j++){
                if(ht[i].data[j] != NULL_DATA){
                    printf("%d ", ht[i].data[j]);
                }
            }
            printf("-->");
            p = ht[i].next;
            while(p){
                for(j = 0; j < BUCKET_NODE_SIZE; j++){
                    if(p->data[j] != NULL_DATA){
                        printf("%d ", p->data[j]);
                    }
                }
                printf("-->");
                p = p->next;
            }
        }
        printf("NULL\n");
    }
}
boolean insertNewElement(HashTable ht, ElemType value){
    int index = Hash(value);
    int i;
    BUCKET_NODE *p;
    BUCKET_NODE *q;
    BUCKET_NODE *s;

    for(i = 0; i < BUCKET_NODE_SIZE; i++){ //在这里先判断表中是否可以存放元素
        if(ht[index].data[i] == NULL_DATA){
            ht[index].data[i] = value;
            return TRUE;
        }
    }
    p = &ht[index];  //取表中某元素的地址
    q = p->next;     //指向了第一个结点,目的:保存前驱结点，在新生成结点时方便连接。
    while(q){
        for(i = 0; i < BUCKET_NODE_SIZE; i++){  //对链表中的元素进行一个一个遍历，看是否可以存储。
            if(q->data[i] == NULL_DATA){
                q->data[i] = value;
                return TRUE;
            }
        }
        p = q;  //p永远保存的是前驱结点
        q = q->next;
    }

    s = (BUCKET_NODE *)malloc(sizeof(BUCKET_NODE)); //此时，的生成新节点，用来存放数据
    if(s == NULL){
        return FALSE;
    }
    for(i = 0; i < BUCKET_NODE_SIZE; i++){  //对新生成的结点进行初始化工作
        s->data[i] = NULL_DATA;   //这里可以写个函数提取出来
    }
    s->next = NULL;
    s->data[0] = value; //新生成的结点，对其赋值

    p->next = s;  //链域的连接。

    return TRUE;

}
void initHashTable(HashTable ht){
    int i;
    int j;

    for(i = 0; i < P; i++){
        for(j = 0; j < BUCKET_NODE_SIZE; j++){
            ht[i].data[j] = NULL_DATA;
        }
        ht[i].next = NULL;
    }
}

#endif

2.3 测试代码

#include<stdio.h>

typedef int ElemType;

#include"bucketHash.h"

void main(void){
    HashTable ht;
    int ar[] = {1, 8, 15, 22, 29, 36, 43, 3, 5 ,99, 55, };
    int n = sizeof(ar) / sizeof(int);
    int i;

    initHashTable(ht);
    for(i = 0; i < n; i++){
        insertNewElement(ht, ar[i]);
    }

    showHashTable(ht);
}

2.4 测试结果

三、分析总结

  1. 我自己认为插入函数(尾插)是重点。

    1.1 我们在插入数据时，首先考虑的是哈希表中是否可以存放我们的数据；其次不是立马开辟空间，而是判断其后的链域空间是否可以存放；最后，就只能自己开辟空间，把数据存放到第一个位置。

  2. 这个问题还远远没有结束，还有好几个方法没有实现。

    2.1 对新生成的结点进行前插；

    2.2 删除某一个数据，这个情况就比较多了，注意：删除数据，其它的应该前移，不然造成空间的浪费，对于结点中没有数据的应该释放这个空间；

    2.3 查找某一个结点的位置，通过返回值和参数，一个确定地址，一个确定在数组的下标；

    2.4 还有销毁函数；

    2.5 。。。

  3. 以空间换时间的查找算法，哈希函数选取恰当，在较好的处理冲突的前提下，哈希查找的时间复杂度可以认为是O(1)。

四、说明

原创文章链接：从零开始学习数据结构-->散列桶