英文网站 字体大小/淘宝排名查询

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 0typedef 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 space\n");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 space\n");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);}}}