符号(hash)表是以集合为基础,支持一下几种运算:
1、判断某个元素是否在集合中;
2、元素的插入;
3、元素的删除;
主要写一下哈希表其核心思想,通过一个类似数组的表,表的编号代表着所要存储以及使用的数据的某种具有分别性(可以快速寻找到)的特征,表中存储的是该数据;在实现上述三个运算过程中需要处理的主要有两点:
1、如何快速寻找定位某个元素,即设计一个哈希函数,寻找其key值;
2、如何处理无法避免的可能出现的重复key;
用于存储的表可以有两种思路,一种是链表式思路,即长度大小不定,可根据需要随时增减,但查找元素时会稍微更耗时,另一种是数组式思路,即先固定某个长度及大小,后续使用不能超越,但查询时可以更快定位;
简单介绍几种哈希函数(寻找key):
1、除余法:
选择一适当的正整数m,用m除以键值所得余数作为key值(比如给定一些大数据123446、264513、5684513,可以通过选择适当的数据除余求得key值);
2、数乘法:
选择一个适当的纯小数与键值相乘做适当处理得到key值;
3、基数转换法:
将键值转换成另外的进制数表示或者其他编码,取其中若干位作为key值(比如如果给定一些字符串,每个具有一个val,后续需要多次寻找,则可以通过将其ASKII码转换成数字作为key,也可以转换成26进制或其他进制得到key);
个人认为比较合适的使用哈希表是数组链表结合使用,通过数组编号存储其key值,然后通过链表处理其可能出现的重复情况存储;(比如下面写的“三角形”题目)
第七次作业:
1、(输入多个三角形,每个都有其val,保存每一种相似三角形的最大val,然后多次查找多种相似三角形的val)首先哈希函数可以通过对三角形的三边求和除以其gcd得到key值(此时已经将许多三角形相对平均分布了,缩短查询时间);然后还存在少量想死三角形key值相等但不相似,此时通过链表存储相同key值的不同类三角形,在查找某一类三角形时,先找到其key值,然后再对该key值的链表遍历寻找这种相似三角形;(之前没有过的代码,这次再实现一遍过了,博客已更新)题目博客链接
代码:
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
using namespace std;
#define Maxsize 100005
#define INF 100000000
typedef struct atri* Tri;
typedef struct atri
{
int a[3];
int val;
Tri next;
}Atri;
//typedef struct atriList* Head;
//typedef struct atriList
//{
// Tri fir_tri;
//};
//求gcd函数
int gcd(int a, int b)
{
if (a<b)
{
int tmp = a; a = b; b = tmp;
}
int tmp=1;
while (b != 0)
{
tmp = b;
b = a%b;
a = tmp;
}
return tmp;
}
void Init(Tri tris[Maxsize])
{
int i;
for (i = 0; i<Maxsize; i++)
{
tris[i] = new Atri;
tris[i]->a[0] = tris[i]->a[1] = tris[i]->a[2] = 0;
tris[i]->next = NULL;
tris[i]->val = -INF;
}
}
Tri tris[Maxsize];
int main()
{
int n, m, i, j;
int a[3], val;
int gcdof;
Init(tris);
scanf("%d", &n);
for (i = 0; i<n; i++)
{
scanf("%d%d%d%d", &a[0], &a[1], &a[2], &val);
sort(a, a + 3);
gcdof = gcd(a[0], gcd(a[1], a[2]));
a[0] /= gcdof; a[1] /= gcdof; a[2] /= gcdof;
Tri link = tris[a[0] + a[1] + a[2]]->next; //link代表这个key值的链表头指针
int exist = 0; //设置初始该相似三角形在链表中不存在时为0;
if (link!= NULL)
{
while (1)
{
if (link->a[0] == a[0] && link->a[1] == a[1] && link->a[2] == a[2])
{
if (link->val < val)link->val = val;
exist = 1; break;
}
else if (link->next == NULL)
{
Tri tmp = new Atri;
tmp->a[0] = a[0]; tmp->a[1] = a[1]; tmp->a[2] = a[2];
tmp->val = val; tmp->next = NULL; link->next = tmp; break;
}
else if (link->next != NULL)
{
link = link->next;
}
}
}
else
{
Tri tmp = new Atri;
tmp->a[0] = a[0]; tmp->a[1] = a[1]; tmp->a[2] = a[2];
tmp->val = val; tmp->next = NULL;
tris[a[0]+a[1]+a[2]]->next= tmp;
}
}
scanf("%d", &m);
for (i = 0; i<m; i++)
{
scanf("%d%d%d", &a[0], &a[1], &a[2]);
sort(a, a + 3);
gcdof = gcd(a[0], gcd(a[1], a[2]));
printf("%d\n",gcdof);
a[0] /= gcdof; a[1] /= gcdof; a[2] /= gcdof;
Tri link = tris[a[0]+a[1]+a[2]]->next; //link代表这个key值的链表头指针
if (link != NULL)
{
while (1)
{
if (link->a[0] == a[0] && link->a[1] == a[1] && link->a[2] == a[2])
{
printf("%d\n", link->val);
break;
}
else if (link->next == NULL)
{
printf("Sorry\n"); break;
}
else if (link->next != NULL)
{
link = link->next;
}
}
}
else printf("Sorry\n");
}
return 0;
}
2、(每个学生名字为字符串,成绩为整型数据,存储每个学生的成绩,并多次查询学生的成绩)我的第一个思路是用map直接map
复习这章时个人链表使用熟悉了很多,链表的next指针以及NULL赋值问题比较清晰了,可以在定义每个结构体时将其指针形式定义好,后面使用会不容易混淆;比如:
typedef struct astu* Stu;
typedef struct astu
{
char* name;
int val;
Stu next;
}