散列-分离链接法（数据结构与算法分析-C语言描述）

散列是一种以常数平均时间执行插入、删除和查找的技术。但是，那些需要元素间任何排序信息的操作将不会得到有效的支持。
　　
　　理想的散列表是一个具有固定大小的数组。把表的大小记作TableSize，通常的习惯是让表从０到TableSize - 1变化。每个关键字被映射到从０到TableSize - 1这个范围中的某个数，并且被放到适当的单元中。这个映射就叫做散列函数（hash function）。理想情况下它应该运算简单并且应该保证任何两个不同的关键字映射到不同的单元。但这是不可能的，因为单元的数目有限，而关键字是无穷的。
　　
　　两个不同的关键字散列到同一个值的时候，我们称之为冲突(collision)，假设散列函数为Hash(X) = X mod 10，那么当关键字为10、20、30时都会被映射到 0 这个单元，这样就产生了冲突。
　　
　　处理冲突的方法主要有“分离链接法”和“开放地址法”。这里主要说明“分离链接法”。（注：Hash Table可以翻译为散列表，也可以音译为哈希表）

〇、结构体定义
struct ListNode //链表的节点定义
{
int element;
struct ListNode *next;
};

struct HashTbl //哈希表定义
{
int tablesize; //哈希表的大小
struct ListNode thelists; //thelists为指向链表节点ListNode的指针的指针
};
　　其中难点在于struct ListNode thelists语句，表面上定义了一个“链表节点ListNode的指针”的指针，但真实目的是想定义一个指针数组 thelists[N]（N为哈希表长度），每一个数组元素 thelists[i] 都是指向链表节点ListNode的指针，即相当于这样定义：struct ListNode *thelists[N]。

　　但是不直接定义struct ListNode *thelists[N]的原因就是哈希表长度N无法确定，只有在初始化函数执行时才可以确定。
　　
　　Hash Table

一、分离链接表（哈希表）的初始化操作
/*
分离链接表初始化函数
输入：哈希表的大小tablesize
返回：指向哈希表的指针H
*/
struct HashTbl InitializeTable(int tablesize)
{
struct HashTbl H;
if (tablesize < MINTABLESIZE) //输入的哈希表大小太小
{
printf(“Table size too small!”);
return NULL;
}

H = malloc(sizeof(struct HashTbl)); //为哈希表分配空间
if (H == NULL)
{
    printf("Out of space!");
    return NULL;
}
H->tablesize = NextPrime(tablesize); //哈希表长度应当选择素数
H->thelists = malloc(sizeof(struct ListNode *) * H->tablesize);     
//为指向ListNode指针的指针分配空间，即为指针数组分配空间
//所以空间大小应为：每一个ListNode型指针空间*指针个数
if (H->thelists == NULL)
{
    printf("Out of space!");
    return NULL;
}
for (int i = 0; i < H->tablesize; i++)      //为指向ListNode的指针分配空间
{
    H->thelists[i] = malloc(sizeof(struct ListNode));  //每一个指针指向ListNode节点
    if (H->thelists[i] == NULL)
    {
        printf("Out of space!");
        return NULL;
    }
    else
        H->thelists[i]->next = NULL;
}
return H;

}
二、分离链接表（哈希表）的Find操作
struct ListNode Find(int key, struct HashTbl H)
{
struct ListNode p; //p指向查找的元素所在节点
struct ListNode loc; //loc指向链表头结点
loc = H->thelists[Hash(key, H->tablesize)];
p = loc->next;while (p != NULL && p->element != key)
{
p = p->next;
}
return p;
}
三、分离链接表（哈希表）的Insert操作
void Insert(int key, struct HashTbl H)
{
struct ListNode pos;
pos = Find(key, H);
if (pos == NULL) //未找到时插入
{
struct ListNode newlistnode = malloc(sizeof(struct ListNode)); //要插入的新节点
if (newlistnode == NULL)
{
printf(“Out of space!”);
}
else
{
struct ListNode loc = H->thelists[Hash(key, H->tablesize)]; //要插入队列的头结点
newlistnode->element = key;
newlistnode->next = loc->next;
loc->next = newlistnode; //在队头插入
}
}
}
代码主要摘录自《数据结构与算法分析-C语言描述 Mark Allen Weiss》，但去掉了typedef语句并加入更多的注释，个人觉得大量使用typedef语句后经常会忘记变量的原始类型…

更多相关文章

随机推荐