网站建设注册什么公司,做数学题挣钱的网站,金溪做网站,如何制作网页广告文章目录 前言一、哈希表的思想二、哈希表总结 前言 散列技术#xff1a;在记录的存储位置和它的关键字之间建立一个确定的对应关系f#xff0c;使得每个关键字key对应一个存储位置f(key) 哈希表#xff1a;采用散列技术将记录存储在一块连续的存储空间中#xff0c;这块连… 文章目录 前言一、哈希表的思想二、哈希表总结 前言 散列技术在记录的存储位置和它的关键字之间建立一个确定的对应关系f使得每个关键字key对应一个存储位置f(key) 哈希表采用散列技术将记录存储在一块连续的存储空间中这块连续存储空间称为散列表或哈希表 一、哈希表的思想 创建哈希表结构体创建哈希表数据结构HashTable用来存放散列地址和该散列表存放的数据个数。 //创建哈希表结构
typedef struct HashTable
{int count;//记录哈希表中元素个数int* elem;//创建哈希表
}HashTable;初始化哈希表初始化哈希表主要还是动态开辟存放数据的数组再初始化count的个数并将哈希表中的值赋值为空这里用NULLKEY标志来表示为空。 //初始化哈希表
void InitHashTable(HashTable* HT)
{int i;m MAXSIZE;//动态开辟内存HT-elem (int*)malloc(m * sizeof(int));HT-count MAXSIZE;for (i 0; i m; i){HT-elem[i] NULLKEY;}}插入哈希表插入哈希表通过哈希函数Hash来计算出散列地址判断该地址是否为NULLKEY是的话就直接插入不是的话就将散列地址赋值为下一个地址继续判断直到找到了就执行插入操作。 //哈希表的插入
void InsertHashTable(HashTable* HT, int key)
{int addr;addr Hash(key);//求散列地址while (HT-elem[addr] ! NULLKEY){addr (addr 1) % m;}HT-elem[addr] key;
}查询哈希表先通过哈希函数获得散列地址再通过散列地址查询访问。在查询时如果通过散列地址找到的值和key值不等则散列地址找到下一个操作直到循环一圈或则通过地址找到的地址为NULLKEY就返回查找失败成功则返回查找成功。 //哈希表查找
int SearchHash(HashTable HT, int key)
{int addr Hash(key);int begin addr;while (HT.elem[addr] ! key){addr (addr 1) % m;if (HT.elem[addr] NULLKEY || addr begin)return 0;}return 1;
}
二、哈希表
#define MAXSIZE 12
#define NULLKEY -32768
#include iostream
using namespace std;//哈希表查找//创建哈希表结构
typedef struct HashTable
{int count;//记录哈希表中元素个数int* elem;//创建哈希表
}HashTable;int m 0;//初始化哈希表
void InitHashTable(HashTable* HT)
{int i;m MAXSIZE;//动态开辟内存HT-elem (int*)malloc(m * sizeof(int));HT-count MAXSIZE;for (i 0; i m; i){HT-elem[i] NULLKEY;}}//散列函数
int Hash(int key)
{return key % m;
}//哈希表的插入
void InsertHashTable(HashTable* HT, int key)
{int addr;addr Hash(key);//求散列地址while (HT-elem[addr] ! NULLKEY){addr (addr 1) % m;}HT-elem[addr] key;
}//哈希表查找
int SearchHash(HashTable HT, int key)
{int addr Hash(key);int begin addr;while (HT.elem[addr] ! key){addr (addr 1) % m;if (HT.elem[addr] NULLKEY || addr begin)return 0;}return 1;
}int main()
{int i,result,key;HashTable HT;int arr[MAXSIZE] { 12,67,56,16,25,37,22,29,15,47,48,34 };//初始化哈希表InitHashTable(HT);key 39;for (i 0; i m; i){InsertHashTable(HT, arr[i]);}result SearchHash(HT,key);if (result)printf(查找 %d 成功 \n, key);elseprintf(查找 %d 失败。\n, key);for (i 0; i m; i){key arr[i];result SearchHash(HT, key);if (result)printf(查找 %d 成功 \n, key);elseprintf(查找 %d 失败。\n, key);}return 0;
}总结 散列表查找的效率是最高的因为它的时间复杂度为O(1)。可惜在实际情况中会产生冲突不同的数据在同一地址的情况但散列表查询还是非常值得的。
