使用c语言,使用双亲链表储存结构储存名字来建树
时间: 2024-05-06 16:16:00 浏览: 70
好的,下面是使用C语言,基于双亲链表的树的结构体定义和建树代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_NODE_NUM 100
// 树节点的结构体定义
typedef struct Node {
char name[20]; // 节点名称
int parent; // 双亲节点的下标
struct Node *child; // 第一个孩子节点的指针
struct Node *sibling; // 兄弟节点的指针
} TreeNode;
// 根据名称查找节点在数组中的下标
int find_node_index(TreeNode nodes[], int node_num, char name[]) {
for (int i = 0; i < node_num; i++) {
if (strcmp(nodes[i].name, name) == 0) {
return i;
}
}
return -1; // 没有找到
}
// 创建节点
TreeNode *create_node(char name[], int parent) {
TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
strcpy(node->name, name);
node->parent = parent;
node->child = NULL;
node->sibling = NULL;
return node;
}
// 建树函数
void create_tree(TreeNode nodes[], int *node_num) {
// 输入根节点名称
char name[20];
printf("Please input the root node name: ");
scanf("%s", name);
// 创建根节点
nodes[0] = *create_node(name, -1);
*node_num = 1;
// 输入每个节点及其父节点名称,建立节点间的双亲关系
while (1) {
printf("Please input the node name and its parent name (end with -1): ");
scanf("%s", name);
if (strcmp(name, "-1") == 0) {
break;
}
char parent_name[20];
scanf("%s", parent_name);
// 查找父节点的下标
int parent_index = find_node_index(nodes, *node_num, parent_name);
if (parent_index == -1) {
printf("Parent node not found!\n");
continue;
}
// 创建当前节点,并将其插入到父节点的子节点链表中
TreeNode *node = create_node(name, parent_index);
TreeNode *p = nodes[parent_index].child;
if (p == NULL) {
nodes[parent_index].child = node;
} else {
while (p->sibling != NULL) {
p = p->sibling;
}
p->sibling = node;
}
nodes[*node_num] = *node;
(*node_num)++;
}
}
int main() {
TreeNode nodes[MAX_NODE_NUM];
int node_num = 0;
create_tree(nodes, &node_num);
// 输出树的节点信息
for (int i = 0; i < node_num; i++) {
printf("Node %d: name=%s, parent=%d\n", i, nodes[i].name, nodes[i].parent);
}
return 0;
}
```
以上代码中,我们定义了 `TreeNode` 结构体,其中包含了节点名称、双亲节点下标、第一个孩子节点指针和兄弟节点指针。使用 `create_node` 函数可以创建一个节点,使用 `find_node_index` 函数可以根据名称查找节点在数组中的下标。
`create_tree` 函数中,首先输入根节点名称,然后输入每个节点及其父节点名称,建立节点间的双亲关系。具体实现中,我们先查找父节点的下标,然后创建当前节点,并将其插入到父节点的子节点链表中。
最后,我们输出树的节点信息,便于检查建树结果。
阅读全文