链接法实现散列表构造和查找"/>
用链接法实现散列表构造和查找
在学习数据结构课程时，老师布置的一次录屏作业，以下内容是本次学习中的思路过程。
文章目录
- 题目描述
- 草稿记录->发现问题
- 解决问题
- 编写代码
- 总结
题目描述
【问题描述】
设哈希（Hash）表的地址范围为0～17，哈希函数为：H（K）＝K MOD 16，K为关键字。
用链接法进行处理冲突。
输入11个大于0的整数作为关键字序列，构造出Hash表
之后对输入的数据在表中查找
输出其地址和比较次数（若不在表中，地址值为-1）。
【输入形式】
11个数的整数序列，用空格隔开
要查找的整数
【输出形式】
地址和比较次数（若不在表中，输出-1和比较次数），用空格隔开
【样例输入】
10 24 32 17 31 30 46 47 40 63 49
63
【样例输出】
15 3（尾插法）
15 1（头插法）
草稿记录->发现问题
个人认为，先画个图理解一下最终的效果，通过笔算理清思路，是很有必要的。
本人针对构建Hash表的思路如下图所示。
整理构建Hash表的思路
整理后发现构建一个Hash表所需的行为包括：
- 构建Hash表
- 取关键字
- 求关键字在Hash表中的位置
- 根据求得的位置插入在Hash表相应位置的后面
由此，我有一个疑问。
Q：需要怎样的数据结构才能满足Hash表的要求？
解决问题
搜集的资料
为了解决上述疑问，本人搜集了关于散列表的基础知识、用链接法实现散列表、散列表的概念，散列表的实验报告等相关文章。
最终，整理出了几份构建散列表的数据结构。
typedef struct _HashNode//哈希节点
{int key;//值_HashNode* pNext;//指向下一个节点的值
}HashNode;typedef struct _Hash
{HashNode* pElement;//数据元素的存放空间
}Hash;
typedef struct MapData
{int key;struct MapData* next;
}*MapData;typedef struct HashMap
{int size;MapData* data;
}*HashMap;//二级指针
struct lNode
{int data;lNode *next;
};main(){lNode **arr = new lNode*[16];
}
typedef struct hash_arr
{int data = -1;struct hash_arr *next;struct hash_arr *prev;
} hash_arr;main()
{int a[11] = {10,24,32,17,31,30,46,47,40,63,49};hash_arr *hash_node[17];
}
最终，得到了五头雾水。。。。。
但功夫不负有心人，最终在搜集到的资料中，看到了这样一段话。
采用链地址法，其中的所有同义词构成一个单链表， 再由一个表头结点指向这个单链表的第一个结点。 这些表头结点组成一个一维数组，即哈希表。
数组元素的下标对应由散列函数求出的散列地址。
因此，本人对疑问的解答如下所示。
要满足Hash表的数据结构，就得符合以下条件。
- 能访问Hash表中所有的地址。
- 能访问链接在各个地址后面的所有节点。
其中，节点是Hash表数据结构中的最小单位。
思路一
因为，节点是Hash表数据结构中的最小单位。
所以，表头结点就是组成Hash表数据结构的成分。
因此，可以定义两个结构体
typedef struct _HashNode //节点
{int key;struct _HashNode* pNext;
}hashNode;
typedef struct _HashTable //Hash表头节点数组
{hashNode* pElement;
}hashTable;
思路二
本人还不太确定，先将想法贴上。
各个节点组成了最终的Hash表。
（即由许多个一维单链表组成了链接起来的二维链表。）【由线-> 面】
根据搜集资料中的二级指针，由感而发。
编写代码
根据在草稿记录部分整理出的基本步骤与题目要求，得到以下行为。
- 构建Hash表
- 取关键字
- 求关键字在Hash表中的位置
- 根据求得的位置插入在Hash表相应位置的后面
- 根据关键字在Hash表中查找相应的位置
#include <iostream>
#include <memory.h>
#define HASH 16using namespace std;class HashTable{
//数据结构
public:typedef struct _HashNode{int key;struct _HashNode* pNext;}hashNode; typedef struct _HashTable{hashNode* pElement; }hashTable;//行为
public:void initHashTable(int hashLen); //根据给定的长度初始化Hash表，本题0~17 //构建Hahs表 void createHashTable(int keyLen); //根据给定的键值域长度创建Hash表，在函数中实现数据的录入与插入 void insertKey(int key); //将键值与Hash表中的相应位置进行匹配，完成插入//根据所给值构建HashNode int calHash(int key); //通过键值计算Hash表中的相应位置 //查找int searchKey(int key); //返回查找的次数，在函数中给出查找结果并打印//输出Hash表void showHash(); //显示数据
//属性
private:hashTable MyHashTable;int HashLen;int KeyLen;
};int main(void){HashTable hashOperate;int hashLen;int keyLen;int count;int key;cout << "设置Hash表长:";cin >> hashLen;hashOperate.initHashTable(hashLen);cout << "设置key域大小：";cin >> keyLen;hashOperate.createHashTable(keyLen);hashOperate.showHash();cout << "待查找的键：";cin >> key;cout << hashOperate.searchKey(key) << endl;return 0;
}//根据给定的长度初始化Hash表
void HashTable::initHashTable(int hashLen){HashLen = hashLen;MyHashTable.pElement = new hashNode[hashLen];//开辟存放数组元素空间
/*for(int i=0;i<hashLen;i++){MyHashTable.pElement[i] = NULL;}*/memset(MyHashTable.pElement, 0x00, sizeof(hashNode)*hashLen);cout<<"初始化完成！！"<<endl;
} //根据给定的键值域长度创建Hash表，在函数中实现数据的录入与插入
void HashTable::createHashTable(int keyLen){int key;cout<<"输入数据.....(keyLen ="<<keyLen<<")" <<endl;for(int i=0;i<keyLen;i++){cin >> key;insertKey(key);}
}int HashTable::calHash(int key){return key % HASH;
}void HashTable::insertKey(int key){int hashAddr = calHash(key); //根据key计算在hash表中的相应位置//头插法 hashNode* pNew = new hashNode; //新建一个结点pNew->key = key;pNew->pNext = MyHashTable.pElement[hashAddr].pNext;MyHashTable.pElement[hashAddr].pNext = pNew;
} void HashTable::showHash(){for(int i=0;i<HashLen;i++){cout << "第" << i << ":";hashNode* pNode = &(MyHashTable.pElement[i]);pNode = pNode->pNext;while(pNode){//cout<<"|";cout << pNode->key << " ";pNode = pNode->pNext;}cout << endl; }
}int HashTable::searchKey(int key){int hashAddr = calHash(key);int count = 0;int flag = 1;hashNode* pNode = &(MyHashTable.pElement[hashAddr]);pNode = pNode->pNext;while(pNode&&flag){if(pNode->key == key){cout<<hashAddr<<" ";flag = 0; }count++;pNode = pNode->pNext;}if(pNode==NULL && flag){cout<<"-1 ";}return count;
}总结
本次一共前后花费了将近5个小时。
在搜集资料与理解资料上花费了将近2个小时，在阅读时进行了一些批注与记录。这些记录也促成了本篇文章的完成。
本次解决问题的思路是
- 理解问题，笔算推导
- 搜集资料，学习他人经验
- 思考疑问，重点解决
- 临摹代码，实践动手
本篇文章还存在的问题/可改进的方向
- 思考”解决问题“中思路二的可行性
- 根据思路二编写代码，达成一题多解。
更多推荐
用链接法实现散列表构造和查找
发布评论