不用类函数,利用C++实现散列表的应用,选择合适散列函数和冲突处理方法,编程实现QQ账户的申请与登录
时间: 2023-06-27 12:07:37 浏览: 70
以下是一个基于链表法解决散列冲突的简单示例,使用了除留余数法作为散列函数。我们假设QQ账户的用户名为字符串类型,密码为整数类型。
```c++
#include <iostream>
#include <string>
using namespace std;
const int TABLE_SIZE = 100;
class HashNode {
public:
string key;
int value;
HashNode* next;
HashNode(string key, int value): key(key), value(value), next(NULL) {}
};
class HashMap {
private:
HashNode** table;
public:
HashMap() {
table = new HashNode*[TABLE_SIZE]();
}
~HashMap() {
for (int i = 0; i < TABLE_SIZE; ++i) {
HashNode* entry = table[i];
while (entry != NULL) {
HashNode* prev = entry;
entry = entry->next;
delete prev;
}
table[i] = NULL;
}
delete [] table;
}
int hashFunc(string key) {
int hash = 0;
for (int i = 0; i < key.length(); ++i) {
hash = (hash * 31 + key[i]) % TABLE_SIZE;
}
return hash;
}
void insert(string key, int value) {
int hash = hashFunc(key);
HashNode* prev = NULL;
HashNode* entry = table[hash];
while (entry != NULL) {
prev = entry;
entry = entry->next;
}
if (entry == NULL) {
entry = new HashNode(key, value);
if (prev == NULL) {
table[hash] = entry;
} else {
prev->next = entry;
}
} else {
entry->value = value;
}
}
int get(string key) {
int hash = hashFunc(key);
HashNode* entry = table[hash];
while (entry != NULL) {
if (entry->key == key) {
return entry->value;
}
entry = entry->next;
}
return -1;
}
};
int main() {
HashMap map;
string username, password;
int op;
while (true) {
cout << "1. Register\n2. Login\n3. Exit\n";
cin >> op;
if (op == 1) {
cout << "Enter username: ";
cin >> username;
cout << "Enter password: ";
cin >> password;
if (map.get(username) == -1) {
map.insert(username, stoi(password));
cout << "Registration success!\n";
} else {
cout << "Username already exists!\n";
}
} else if (op == 2) {
cout << "Enter username: ";
cin >> username;
cout << "Enter password: ";
cin >> password;
if (map.get(username) == stoi(password)) {
cout << "Login success!\n";
} else {
cout << "Invalid username or password!\n";
}
} else if (op == 3) {
break;
} else {
cout << "Invalid operation!\n";
}
}
return 0;
}
```
在上述示例中,我们使用 `HashMap` 类来实现散列表。在这个类中,我们使用了链表法来解决散列冲突。每个节点由一个键值对和指向下一个节点的指针组成。我们使用除留余数法作为散列函数,将字符串键值映射到整数索引上。对于每个操作,我们首先读取用户输入,然后使用散列表进行账户信息的查找和插入。