散列表的创建与查找c++
时间: 2024-02-13 21:03:06 浏览: 62
散列表(哈希表)的创建与查找可以使用C++ STL中的unordered_map容器来实现。
1. 创建散列表
可以使用unordered_map的构造函数进行创建,构造函数的参数为键值对的类型。例如,创建一个存储string类型键和int类型值的散列表可以使用以下代码:
```c++
#include <unordered_map>
using namespace std;
unordered_map<string, int> myMap;
```
2. 在散列表中插入元素
使用insert函数可以向散列表中插入键值对,例如:
```c++
myMap.insert({"apple", 5});
```
3. 在散列表中查找元素
使用find函数可以在散列表中查找指定键的值,例如:
```c++
auto it = myMap.find("apple");
if (it != myMap.end()) {
cout << "Value of apple is " << it->second << endl;
} else {
cout << "apple not found in the map" << endl;
}
```
这里使用auto关键字来推导迭代器类型,it->second表示散列表中键为"apple"的值。如果键不存在,则find函数返回散列表的end迭代器。
相关问题
实现分离链接散列表的创建,查找和删除代码
下面是基于链表实现的分离链接散列表的创建、查找和删除代码示例:
```c++
#include <iostream>
#include <string>
using namespace std;
class HashNode {
public:
int key;
string value;
HashNode* next;
HashNode(int key, string value) {
this->key = key;
this->value = value;
this->next = nullptr;
}
~HashNode() {
delete next;
}
};
class HashMap {
private:
HashNode** table; // 散列表
int capacity;
public:
HashMap(int capacity) {
this->capacity = capacity;
table = new HashNode*[capacity];
for (int i = 0; i < capacity; i++) {
table[i] = nullptr;
}
}
~HashMap() {
for (int i = 0; i < capacity; i++) {
if (table[i] != nullptr) {
delete table[i];
}
}
delete[] table;
}
int hash(int key) {
return key % capacity;
}
void insert(int key, string value) {
int index = hash(key);
HashNode* node = new HashNode(key, value);
if (table[index] == nullptr) {
table[index] = node;
} else {
HashNode* cur = table[index];
while (cur->next != nullptr) {
cur = cur->next;
}
cur->next = node;
}
}
bool search(int key, string& value) {
int index = hash(key);
HashNode* cur = table[index];
while (cur != nullptr) {
if (cur->key == key) {
value = cur->value;
return true;
}
cur = cur->next;
}
return false;
}
void remove(int key) {
int index = hash(key);
if (table[index] == nullptr) {
return;
}
if (table[index]->key == key) {
HashNode* tmp = table[index];
table[index] = table[index]->next;
tmp->next = nullptr;
delete tmp;
} else {
HashNode* cur = table[index];
while (cur->next != nullptr && cur->next->key != key) {
cur = cur->next;
}
if (cur->next != nullptr && cur->next->key == key) {
HashNode* tmp = cur->next;
cur->next = cur->next->next;
tmp->next = nullptr;
delete tmp;
}
}
}
};
int main() {
HashMap map(10);
map.insert(1, "value1");
map.insert(11, "value11");
map.insert(21, "value21");
map.insert(31, "value31");
map.insert(41, "value41");
map.insert(2, "value2");
map.insert(3, "value3");
map.insert(4, "value4");
map.insert(5, "value5");
map.insert(6, "value6");
string value;
if (map.search(31, value)) {
cout << "Found key 31: " << value << endl;
} else {
cout << "Not found key 31" << endl;
}
map.remove(31);
if (map.search(31, value)) {
cout << "Found key 31: " << value << endl;
} else {
cout << "Not found key 31" << endl;
}
return 0;
}
```
在上面的代码中,`HashNode` 类表示散列表中的一个节点,包含键、值和指向下一个节点的指针。`HashMap` 类表示分离链接散列表,使用 `HashNode*` 指针数组来存储数据,数组中每个元素都是一个链表的头指针,表示散列表中的一个桶。`hash` 方法用于计算给定键的散列值,然后根据散列值找到对应的桶,将新节点插入到链表的末尾。`search` 方法用于查找给定键的值,先计算散列值,然后遍历桶中的链表查找匹配的键。`remove` 方法用于删除给定键的节点,先计算散列值,然后遍历桶中的链表查找匹配的键,如果找到则删除该节点。
在 `main` 函数中,首先创建了一个容量为 10 的散列表,然后插入了 10 个节点。接着通过 `search` 方法查找键为 31 的节点,输出节点的值,然后通过 `remove` 方法删除键为 31 的节点。最后再次通过 `search` 方法查找键为 31 的节点,输出节点的值。
c++散列表实现电话号码查询系统
好的,我可以为您介绍一下如何使用 C++ 实现电话号码查询系统的散列表。
散列表是一种用于快速查询数据的数据结构,它将数据存储在数组中,并使用哈希函数将数据映射到数组中的索引位置。在电话号码查询系统中,我们可以将每个电话号码作为键,将联系人信息存储为值,然后使用散列表来快速查找联系人信息。
以下是一个简单的 C++ 代码示例,用于实现基于散列表的电话号码查询系统:
```cpp
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int main() {
// 创建一个散列表,用于存储电话号码和联系人信息
unordered_map<string, string> phoneBook;
// 添加一些联系人信息
phoneBook["111-222-3333"] = "Alice";
phoneBook["222-333-4444"] = "Bob";
phoneBook["333-444-5555"] = "Charlie";
// 从用户输入中查找联系人信息
string phoneNumber;
cout << "Enter a phone number (xxx-xxx-xxxx): ";
cin >> phoneNumber;
// 查找电话号码对应的联系人信息
auto it = phoneBook.find(phoneNumber);
if (it != phoneBook.end()) {
cout << "Contact name: " << it->second << endl;
} else {
cout << "Contact not found." << endl;
}
return 0;
}
```
在上面的代码中,我们首先创建了一个 `unordered_map` 对象,用于存储电话号码和联系人信息。然后,我们向电话簿中添加了一些联系人信息。
在查询联系人信息时,我们首先从用户输入中获取电话号码,然后使用散列表的 `find()` 函数来查找电话号码对应的联系人信息。如果找到了联系人信息,我们就输出联系人的姓名;否则,我们输出“联系人未找到”的提示信息。
希望这个简单的代码示例可以对您有所帮助。如果您有任何问题,请随时问我。
阅读全文