使用分离链路法处理冲突（C语言）

1. 使用分离链路法处理冲突
2. 问题描述
   
   • Hash表的大小为2k-1，初始可以为15
   • 表中的装填因子达到3/4时，增加表的大小至2k+1 –1，完成再哈希
   • 实现插入，删除和查找操作
3. 问题分析与算法设计
   
   1. hash表 ：首先定义一个数组链表，元素存储在链表中，并且每个链表是首元素为仅为表头，不存储任何元素。
   2. 插入 ：首先找到链表数组位置，然后将元素查到元素前端
   3. 删除 ：同样先查找元素，如果存储，则删除，不存在，就提示没有该元素
   4. 查找 ：首先查找链表数组，然后依次遍历链表
4. 算法实现

//使用分离链路法处理hash冲突
//并同时实现添加，删除，查找操作
#include <stdio.h>
#include <stdlib.h>

#define SUCCESS 1
#define FAILURE 0

typedef struct ListNode *position;
typedef position list;
typedef struct HashTable *hashTable;
typedef int ElementType;

hashTable initializeTable(int tablesize);
void destroyTable(hashTable H);
position find(ElementType key, hashTable hash);
void insert(ElementType key, hashTable hash);
int Hash(ElementType key, int tableSize);
int Delete(ElementType key, hashTable hash);
void extend(hashTable hash);

/******************************
    *数据存储链表
    *element ： 存储的数据
    *next ： 指向下一个元素地址的指针
*******************************/
struct ListNode
{
    ElementType element;
    position next;
};

/******************************
    *hash表
    *tableSize ： hash表是尺寸
    *curSize ： 当前已经填入的元素的个数
    *thelists ： 指向ListNode的指针的指针
*******************************/
struct HashTable
{
    int tableSize;
    int curSize;    
    list *thelists;
};

/******************************
    *初始化hash表
    *tableSize ： hash表输入尺寸，实际尺寸为 2^k - 1
*******************************/
hashTable initializeTable(int tableSize)
{
    //初始化为实际尺寸
    tableSize = (tableSize >> 1) - 1;
    hashTable hash;
    hash = (hashTable)malloc(sizeof(struct HashTable));
    if (hash == NULL)
    {
        printf("out of spacen");
        return NULL;
    }
    hash->tableSize = tableSize;
    hash->curSize = 0;

    //创建指针数组,数组里不放数据，数据放在链表里
    hash->thelists = (list*)malloc(sizeof(list) * hash->tableSize); 

    if (hash->thelists == NULL)
    {
        printf("out of space!n");
        return NULL;
    }
    //创建指针数组元素指向的链表表头
    for (int i = 0; i < tableSize; i++)
    {
        hash->thelists[i] = (struct ListNode*)malloc(sizeof(struct ListNode));
        if (hash->thelists[i] == NULL)
        {
            printf("out of space!n");
            return NULL;
        }
        else
        {
            hash->thelists[i]->element = 0;
            hash->thelists[i]->next = NULL;
        }
    }
    return hash;
}

/******************************
    *删除原有的hash表
    *hash ： hash表
*******************************/
void destroyTable(hashTable hash)
{
    position list, tmp, ptr;
    int i;
    for (i = 0; i < hash->tableSize; i++)
    {
        list = hash->thelists[i];
        ptr = list->next;
        while (ptr)
        {
            tmp = ptr->next;
            if (!tmp)
            {
                free(tmp);
                tmp = NULL;
            }
            else
            {
                free(ptr);
                ptr = tmp;
            }
        }
    }
    free(hash);
}

/******************************
    *根据元素查找hash表
    *key ： 要查找的元素
    *hash ： 被查找的hash表
*******************************/
position find(ElementType key, hashTable hash)
{
    position pos;
    list list;
    //hash，找到 key 本该被存入的位置
    list = hash->thelists[Hash(key, hash->tableSize)];
    if (list == NULL)
        return NULL;
    pos = list->next;
    while(pos)
    {
        if (pos->element == key)
        {
            return pos;
        }
        pos = pos->next;
    }
    return NULL;
}

/********************************
    *自定义hash方法，求模运算
    *key ： 元素值
    *tableSize ： hash表尺寸
*********************************/
int Hash(ElementType key, int tableSize)
{
    return key % tableSize;
}

/********************************
    *进行hash表元素的插入，如果元素个数超过hash表尺寸的3/4，则进行再hash
    *key ： 要插入的元素
    *hash ： 被插入的hash表
*********************************/
void insert(ElementType key, hashTable hash)
{
    position pos, cell;
    position lsit;
    pos = find(key, hash);
    if (pos == NULL) //错把pos=null当作判断条件，此条件永远为真。
    {
        cell = (struct ListNode*)malloc(sizeof(struct ListNode));
        if (cell == NULL)
        {
            printf("out of spacen");
            return;
        }
        else
        {
            lsit = hash->thelists[Hash(key, hash->tableSize)];
            if (lsit->next == NULL)
                hash->curSize++;
            //将元素插入到链表前端，list为链表表头，不存储元素
            cell->next = lsit->next;
            cell->element = key;
            lsit->next = cell;

            //将int型转化为float型
            //c编译系统会自动向高精度类型进行转化。
            if (hash->curSize * 1.0 / hash->tableSize >= 0.75)
            {
                extend(hash);
            }
        }
    }
}

/********************************
    *实现 hash 表元素的删除
    *key ：要删除的元素
    *hash ：要被删除的 hash 表
*********************************/
int Delete(ElementType key, hashTable hash)
{
    position pos, list;
    //对应 hash 表位置的表头
    list = hash->thelists[Hash(key, hash->tableSize)];

    if (list->next == NULL)
    {
        printf("can't find that key!n");
        return FAILURE;
    }
    else
    {
        while (list != NULL && list->next != NULL && list->next->element != key)
        {
            list = list->next;
        }
        //要删除的元素在链表的表尾
        if (list->next == NULL && list->element == key)
        {
            free(list);
            return SUCCESS;
        }
        if (list->next != NULL && list->next->element == key)
        {
            //pos 为要删除的元素的指针
            pos = list->next;
            list->next = pos->next;
            free(list);
            return SUCCESS;
        }
    }
    return FAILURE;
}

/********************************
    *进行再 hash
    *hash ：被再 hash 的hash表
*********************************/
void extend(hashTable hash)
{
    int preSize = hash->tableSize;
    hash->tableSize = (1 << preSize) + 1;
    int nowSize = hash->tableSize;
    list* pre = hash->thelists;
    hash->thelists = (list*)malloc(sizeof(list) * nowSize);
    for (int i = 0; i < hash->tableSize; i++)
    {
        hash->thelists[i] = (struct ListNode*)malloc(sizeof(struct ListNode));
    }
    for (int i = 0; i < nowSize; i++)
    {
        list temp = pre[i]->next;
        while (temp != NULL)
        {
            insert(temp->element, hash);
            list temp2 = temp;
            temp = temp->next;
            free(temp2);
        }
    }

}

最后

以上就是留胡子云朵为你收集整理的使用分离链路法处理冲突（C语言）的全部内容，希望文章能够帮你解决使用分离链路法处理冲突（C语言）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。