C++ 中实现哈希表的例子
5星
- 浏览量: 0
- 大小:None
- 文件类型：PDF
简介：
本篇文章提供了一个使用C++语言构建和操作哈希表的具体实例。通过此示例，读者可以了解如何在实际编程中应用哈希表数据结构来高效存储与检索信息。
哈希表是一种常用的数据结构，用于快速存储与检索数据。通过C++实现哈希表的实例能够帮助我们更好地理解其工作原理及内部机制。
一、基本概念
1. 键值对（Key-Value）：每个元素包含一个唯一的键和对应的值。
2. 散列函数（Hash Function）：将键转换为索引，以快速访问数据。
3. slot：哈希表中的每一个slot是一个链表，存储具有相同散列结果的键值对。
二、C++实现示例
首先定义一个LinkNode类用于保存每个节点的数据：
```cpp
class LinkNode {
private:
int key;
LinkNode* next; // 指向下一个节点的指针
friend class Link;
public:
LinkNode():key(-1),next(NULL){} // 默认构造函数
LinkNode(int num):key(num),next(NULL){}
int GetKey() { return key;}
};
```
接下来定义Link类管理链表：
```cpp
class Link {
private:
friend class Hash; // 友元类，可以访问Hash的私有成员
LinkNode* head;
int length;
public:
Link():head(NULL),length(0) {} // 默认构造函数
~Link() { MakeEmpty(); } // 析构函数中调用清理方法
void MakeEmpty() {
if (head == NULL)
return;
LinkNode* p = head; // 清空链表，释放内存
while (p != nullptr){
head = head->next;
delete p;
p = head;
}
}
int GetLength(){return length;}
void Insert(int num) {
length++; // 插入一个元素
LinkNode* node = new LinkNode(num);
if (!head || node->GetKey() < head->GetKey()){
node->next = head;
head = node;
return;
}
LinkNode *p, *q;
for (p=head,q=NULL;p != nullptr && p->key < num;q=p,p=p->next);
q->next = node;
node->next = p;
}
bool Delete(int num) {
if (!head)
cout << 链表为空！ << endl;
LinkNode* temp, *q;
for (temp=head,q=NULL;temp != nullptr && temp->key < num;q=temp,temp=temp->next);
if (temp == NULL || temp->GetKey() > num)
return false;
else {
q->next = temp->next; // 删除节点
delete(temp);
length--;
}
}
int Search(int num) {
LinkNode* p = head;
while(p != nullptr){
if (p->key == num)
return p->GetKey();
else if (p->key < num)
p=p->next;
}
return -1; // 没有找到返回-1
}
```
最后定义Hash类管理哈希表：
```cpp
class Hash {
private:
Link* table; // 存储链表指针的数组
int size;
public:
Hash(int s) { this->size = s;
table = new Link*[s];
for (int i=0;i
全部评论 (0)
