定义一个节点结构体,包括节点的名称、双亲节点、子节点; 定义一个根节点,作为族谱的根节点; 初始化族谱,添加至少10个节点; 提供查询功能,能够查询某个指定人物的双亲和他所有的子孙,新增子孙的插入,指定人物由键盘输入。; 提供修改功能,根据输入的指定人物名称,将其修改为新的名称,并更新其子孙节点的双亲节点。 能够查询某个指定人物的双亲和他所有的子孙,新增子孙的插入,指定人物由键盘输入。
时间: 2024-03-10 13:47:35 浏览: 56
好的,以下是代码实现:
```c++
#include<iostream>
#include<string>
#include<vector>
#include<map>
using namespace std;
// 节点结构体
struct Node {
string name; // 节点名称
Node* parent; // 双亲节点
vector<Node*> children; // 子节点
Node(string n) : name(n), parent(nullptr) {} // 构造函数
};
// 根节点
Node* root = new Node("祖先");
// 添加节点
void addNode(string parentName, string childName) {
// 查找父节点
Node* parentNode = nullptr;
if (parentName != "祖先") {
parentNode = root;
while (parentNode && parentNode->name != parentName) {
int n = parentNode->children.size();
for (int i = 0; i < n; i++) {
if (parentNode->children[i]->name == parentName) {
parentNode = parentNode->children[i];
break;
}
}
}
}
// 添加子节点
Node* childNode = new Node(childName);
childNode->parent = parentNode;
if (parentNode) {
parentNode->children.push_back(childNode);
}
}
// 查询节点
void queryNode(string name) {
// 查找节点
Node* node = root;
while (node && node->name != name) {
int n = node->children.size();
for (int i = 0; i < n; i++) {
if (node->children[i]->name == name) {
node = node->children[i];
break;
}
}
if (node->name != name) {
node = node->parent;
}
}
// 输出结果
if (!node) {
cout << "未找到该节点!" << endl;
}
else {
// 输出双亲节点
if (node->parent) {
cout << "双亲节点:" << node->parent->name << endl;
}
else {
cout << "双亲节点:无" << endl;
}
// 输出子孙节点
cout << "子孙节点:";
vector<Node*> q;
q.push_back(node);
while (!q.empty()) {
Node* front = q.front();
q.erase(q.begin());
int n = front->children.size();
for (int i = 0; i < n; i++) {
q.push_back(front->children[i]);
cout << front->children[i]->name << " ";
}
}
cout << endl;
}
}
// 修改节点
void modifyNode(string name, string newName) {
// 查找节点
Node* node = root;
while (node && node->name != name) {
int n = node->children.size();
for (int i = 0; i < n; i++) {
if (node->children[i]->name == name) {
node = node->children[i];
break;
}
}
if (node->name != name) {
node = node->parent;
}
}
// 修改节点名称
if (!node) {
cout << "未找到该节点!" << endl;
}
else {
node->name = newName;
cout << "修改成功!" << endl;
// 更新子孙节点的双亲节点
vector<Node*> q;
q.push_back(node);
while (!q.empty()) {
Node* front = q.front();
q.erase(q.begin());
int n = front->children.size();
for (int i = 0; i < n; i++) {
q.push_back(front->children[i]);
front->children[i]->parent = front;
}
}
}
}
int main() {
// 初始化族谱
addNode("祖先", "父亲1");
addNode("祖先", "父亲2");
addNode("祖先", "父亲3");
addNode("父亲1", "儿子1");
addNode("父亲1", "儿子2");
addNode("父亲2", "儿子3");
addNode("父亲2", "儿子4");
addNode("父亲3", "儿子5");
addNode("儿子2", "孙子1");
addNode("孙子1", "曾孙子1");
while (true) {
// 输出菜单
cout << endl << "--------------- 族谱管理系统 ---------------" << endl;
cout << "1. 查询某个人物的双亲和他所有的子孙" << endl;
cout << "2. 新增某个人物的子孙" << endl;
cout << "3. 修改某个人物的名称" << endl;
cout << "4. 退出系统" << endl;
cout << "请输入序号:";
// 输入菜单选项
int choice;
cin >> choice;
// 执行相应操作
if (choice == 1) {
// 查询节点
string name;
cout << "请输入人物名称:";
cin >> name;
queryNode(name);
}
else if (choice == 2) {
// 新增子孙节点
string parentName, childName;
cout << "请输入父亲节点名称:";
cin >> parentName;
cout << "请输入子孙节点名称:";
cin >> childName;
addNode(parentName, childName);
cout << "新增成功!" << endl;
}
else if (choice == 3) {
// 修改节点名称
string name, newName;
cout << "请输入人物名称:";
cin >> name;
cout << "请输入新名称:";
cin >> newName;
modifyNode(name, newName);
}
else if (choice == 4) {
// 退出系统
cout << "谢谢使用!" << endl;
break;
}
else {
// 输入错误选项
cout << "输入错误,请重新输入!" << endl;
}
}
return 0;
}
```
以上代码实现了一个简单的族谱管理系统,包括节点的添加、查询、修改等功能,可以通过菜单进行操作。注意在查询节点时,使用了广度优先搜索算法来搜索子孙节点。
阅读全文