首页 > 程序开发 > 综合编程 > 其他综合 >

数据结构与算法(6)——哈希表

2011-05-18

 在很多情况下,我们需要实现一个符号表,里面保存我们用到的所有符号。每个符号有一个关键码key(不同符号的关键码也不同),其余部分可能非常庞大。换句话说,符号表应该提供以下操作:Search(T, k):查找关键码k是否在表中Insert(T,

 在很多情况下,我们需要实现一个符号表,里面保存我们用到的所有符号。每个符号有一个关键码key(不同符号的关键码也不同),其余部分可能非常庞大。换句话
说,符号表应该提供以下操作:
Search(T, k):查找关键码k是否在表中
Insert(T, x):把x添加到表中
Delete(T, x):从表中删除元素x
有时也把符号表称为"字典",它最经典的实现方法是哈希表。

哈希表的不同设计方法以及解决冲突的方法,我觉得单单看算法书或者数据结构上的书不是很好理解,但是结合具体的题目实例来看,就相当的具体与好理解,哈希表的思想就类似于我们平时用字典查英语单词,没有一个人会从第一页一页一页的去找,我们会以单词本身的每一个字母作为每次搜索的关键码,如apple这个单词,第一次,我们将厚厚的字典分为26个槽,槽a,槽b....槽z,我们翻到槽a的区域,然后又将该区域分为26个槽以此类推,当然这个思想跟准确对应的一种数据结构是Trie字典树,这也就是为什么说,字典树是一种特殊情况的哈希树的原因所在 !

字典树例子:http://www.2cto.com/kf/201105/90890.html

POJ 2002 题目报告

http://poj.org/problem?id=2002

/*开散列的方法建立HASH表并查询
该题目的思路较为简单,就是枚举没两个点,即枚举每一条边,查询以改边
构成的正方形的另两个点是否在HASH表中即可
如果以A(x1,y1)和B(x2,y2)为边进行正方形的查询,那么根据平面几何的
知识得之,另条边的两个点分别有两组,分别是:
C(x1+y1-y2,y1+x2-x1),D(x2+y1-y2,y2+x2-x1)
C(x1-y1+y2,y1-x2+x1),D(x2-y1+y2,y2-x2+x1)
*/
#include
<iostream>
using namespace std;

const int MAX_LEN = 1001;
const int HASH_LEN = 40001;

struct Point{
int x,y;
};

struct TagPoint{
int index;
TagPoint
*next;
TagPoint(){
index
= -1;
next
= NULL;
}
TagPoint(
int indexVal,TagPoint *nextVal){
index
= indexVal;
next
= nextVal;
}
};

Point pInfo[MAX_LEN];
bool find(TagPoint hash[],int x,int y){
int sum = x+y;
if(sum<0)sum=-sum;
TagPoint
*p = &hash[sum];
while(true){
if(p==NULL)
return false;

if(pInfo[p->index].x==x&&pInfo[p->index].y==y)
return true;

else p = p->next;
}
}

int main(){
int pointNum = 0;
while(cin>>pointNum&&pointNum!=0){
TagPoint hash[HASH_LEN];
/****************************************/
//输入点集信息,并且建立好hash表
for(int i=0;i<pointNum;i++){
cin
>>
热点推荐