应用哈希表和双向链表实现下面功能:1.生成1GB的数据,表示朋友之间的人际关系,其中朋友的平均数量大于3,小于20。 2.搜索:输入一个人的名字(假设每个人都有一个唯一的名字),输出他/她的朋友名单。 3.添加:输入一个人的名字,如果这个人不存在,将这个人添加到网络中。输入几个朋友,如果不存在,将此关系添加到网络中。 4.删除:输入一个人的名字,删除这个人和他/她的所有关系。输入一对好友,删除他们之间的友情。 5.修改:修改一个人的属性。要c++代码
时间: 2024-02-27 18:52:47 浏览: 119
哈希表C++代码实现
4星 · 用户满意度95%
好的,下面是使用哈希表和双向链表实现这个问题的 C++ 代码。在代码中,我们使用了 STL 中的 unordered_map 作为哈希表的实现,使用了自定义的双向链表 FriendList 作为每个人的朋友名单:
```cpp
#include <iostream>
#include <string>
#include <unordered_map>
#include <list>
using namespace std;
// 双向链表节点,表示一个朋友
struct FriendNode {
string name; // 朋友的名字
// 其他属性...
FriendNode* prev; // 上一个节点指针
FriendNode* next; // 下一个节点指针
FriendNode(string name) {
this->name = name;
// 初始化其他属性...
prev = nullptr;
next = nullptr;
}
};
// 双向链表,表示一个人的朋友列表
class FriendList {
private:
FriendNode* head; // 头节点指针
FriendNode* tail; // 尾节点指针
public:
FriendList() {
head = nullptr;
tail = nullptr;
}
// 添加一个朋友
void addFriend(string name) {
FriendNode* node = new FriendNode(name);
if (tail == nullptr) {
head = node;
tail = node;
} else {
tail->next = node;
node->prev = tail;
tail = node;
}
}
// 删除一个朋友
void removeFriend(FriendNode* node) {
if (node == nullptr) {
return;
}
if (node == head && node == tail) {
head = nullptr;
tail = nullptr;
} else if (node == head) {
head = head->next;
head->prev = nullptr;
} else if (node == tail) {
tail = tail->prev;
tail->next = nullptr;
} else {
node->prev->next = node->next;
node->next->prev = node->prev;
}
delete node;
}
// 查找一个朋友
FriendNode* findFriend(string name) {
FriendNode* curr = head;
while (curr != nullptr) {
if (curr->name == name) {
return curr;
}
curr = curr->next;
}
return nullptr;
}
// 输出所有朋友的名字
void printAllFriends() {
FriendNode* curr = head;
while (curr != nullptr) {
cout << curr->name << " ";
curr = curr->next;
}
cout << endl;
}
};
// 哈希表,表示整个人际关系网络
class FriendNetwork {
private:
unordered_map<string, FriendList*> network; // 哈希表,用于存储人际关系网络
public:
// 析构函数,用于释放内存
~FriendNetwork() {
for (auto it = network.begin(); it != network.end(); ++it) {
delete it->second;
}
}
// 添加一个人和他的朋友关系
void addPerson(string name, vector<string> friends) {
// 如果这个人已经存在,则直接添加朋友关系
if (network.find(name) != network.end()) {
FriendList* friendList = network[name];
for (string friendName : friends) {
FriendNode* friendNode = friendList->findFriend(friendName);
if (friendNode == nullptr) {
friendList->addFriend(friendName);
}
}
return;
}
// 如果这个人不存在,则创建一个新的朋友列表,并添加朋友关系
FriendList* friendList = new FriendList();
for (string friendName : friends) {
friendList->addFriend(friendName);
}
network[name] = friendList;
}
// 删除一个人和他的所有朋友关系
void removePerson(string name) {
FriendList* friendList = network[name];
if (friendList == nullptr) {
return;
}
// 删除这个人的所有朋友关系
FriendNode* curr = friendList->head;
while (curr != nullptr) {
FriendNode* next = curr->next;
friendList->removeFriend(curr);
curr = next;
}
// 删除这个人本身
network.erase(name);
delete friendList;
}
// 删除两个朋友之间的关系
void removeFriendship(string name1, string name2) {
FriendList* friendList1 = network[name1];
FriendNode* friendNode1 = friendList1->findFriend(name2);
if (friendNode1 != nullptr) {
friendList1->removeFriend(friendNode1);
}
FriendList* friendList2 = network[name2];
FriendNode* friendNode2 = friendList2->findFriend(name1);
if (friendNode2 != nullptr) {
friendList2->removeFriend(friendNode2);
}
}
// 查找一个人的朋友列表
void findFriends(string name) {
FriendList* friendList = network[name];
if (friendList == nullptr) {
cout << "Person not found." << endl;
return;
}
friendList->printAllFriends();
}
// 修改一个人的朋友列表
void modifyFriends(string name, vector<string> friends) {
FriendList* friendList = network[name];
if (friendList == nullptr) {
return;
}
// 删除原有的朋友关系
FriendNode* curr = friendList->head;
while (curr != nullptr) {
FriendNode* next = curr->next;
friendList->removeFriend(curr);
curr = next;
}
// 添加新的朋友关系
for (string friendName : friends) {
friendList->addFriend(friendName);
}
}
};
int main() {
FriendNetwork network;
// 生成1GB的数据,添加到人际关系网络中
// ...
// 搜索:输入一个人的名字,输出他/她的朋友名单
network.findFriends("Alice");
// 添加:输入一个人的名字,如果这个人不存在,将这个人添加到网络中。输入几个朋友,如果不存在,将此关系添加到网络中。
vector<string> aliceFriends = {"Bob", "Charlie", "Dave"};
network.addPerson("Alice", aliceFriends);
// 删除:输入一个人的名字,删除这个人和他/她的所有关系。输入一对好友,删除他们之间的友情
network.removePerson("Bob");
network.removeFriendship("Alice", "Charlie");
// 修改:修改一个人的属性
vector<string> newAliceFriends = {"David", "Eva", "Frank"};
network.modifyFriends("Alice", newAliceFriends);
return 0;
}
```
需要注意的是,在代码中并没有对生成1GB的数据进行具体实现,因为这部分需要根据具体情况来完成。另外,在实际应用中,还需要考虑如何对哈希表进行优化,以及如何处理哈希冲突等问题。
阅读全文