基于C语言构建多家族树：节点关联与输入校验求助

需求说明 #

• 从指定格式的文本文件构建多家族树，输出至控制台或文件，每个人物以NAME开头
• 已实现节点创建与存储，但无法建立节点间的亲属关联
• 需要处理非法输入校验：
  • 循环亲属关系（如A是B的父亲，B又是A的父亲）
  • 一人多母这类矛盾输入

输入文件格式示例 #

NAME son
MOTHER mother
FATHER father

NAME father
MOTHER grandmother 

NAME otherson
FATHER otherfather
MOTHER other mother

现有代码（存在问题） #

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_LINE_LENGTH 63

typedef struct node
{
    char* name;
    struct node *mom; //left
    struct node *dad; //right
} t_node;

t_node* createNode(char* name) {
    t_node* newNode = malloc(sizeof(t_node));
    if (newNode == NULL) {
        fprintf(stderr, "Memory allocation failed.\n");
        exit(1);
    }
    newNode->name = strdup(name); // Allocate memory for the name and copy it
    newNode->mom = NULL;
    newNode->dad = NULL;

    return newNode;
}

void freeMemory(t_node* nodeArray[], int numNodes){
    for (int i = 0; i < numNodes; i++) {
        free(nodeArray[i]->name);
        free(nodeArray[i]);
    }
}

void printNodes(t_node* nodeArray[], int numNodes){
    printf("Nodes created:\n");
    for (int i = 0; i < numNodes; i++) {
        printf("%s\n", nodeArray[i]->name);
    }
}

int main() {
    FILE *fin;
    char line[MAX_LINE_LENGTH];
    char* name;

    fin = fopen("input.txt", "r");
    if(fin == NULL) {
        printf("Error opening input file.\n");
        return 1;
    }

    t_node* nodeArray[10000]; // Array to store pointers to created nodes
    int numNodes = 0;

    while (fgets(line, MAX_LINE_LENGTH, fin) != NULL) {
        if (strstr(line, "VARDS")) { // 笔误：应为"NAME"
            name = strstr(line, "NAME") + 6;
            name[strcspn(name, "\n")] = 0; // Remove newline character

            // Create a node for the person
            t_node* person = createNode(name);
            nodeArray[numNodes++] = person;
        } else if (strstr(line, "FATHER")) {
            char* father = strstr(line, "TEVS") + 5; // 笔误：应为"FATHER"
            father[strcspn(father, "\n")] = 0;
        
            // Create a node for the father if not already created
            int found = 0;
            for (int i = 0; i < numNodes; i++) {
                if (strcmp(nodeArray[i]->name, father) == 0) {
                    found = 1;
                    break;
                }
            }
            if (!found) {
                t_node* fatherNode = createNode(father);
                nodeArray[numNodes++] = fatherNode;
            }
        } else if (strstr(line, "MOTHER")) {
            char* mother = strstr(line, "MATE") + 5; // 笔误：应为"MOTHER"
            mother[strcspn(mother, "\n")] = 0;

            // Create a node for the mother if not already created
            int found = 0;
            for (int i = 0; i < numNodes; i++) {
                if (strcmp(nodeArray[i]->name, mother) == 0) {
                    found = 1;
                    break;
                }
            }
            if (!found) {
                t_node* motherNode = createNode(mother);
                nodeArray[numNodes++] = motherNode;
            }
        }
        //one iteration through 1 person with mother and father
    }

    fclose(fin);

   printNodes(nodeArray, numNodes);
   freeMemory(nodeArray, numNodes);

    return 0;
}

问题分析与修复方案 #

核心问题 #

1. 代码存在多处字符串匹配笔误，导致无法正确识别输入行
2. 未跟踪当前处理的人物节点，无法建立父母与子女的关联
3. 缺少非法输入校验逻辑

修复后的代码 #

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_LINE_LENGTH 63
#define MAX_NODES 10000

typedef struct node
{
    char* name;
    struct node *mom;
    struct node *dad;
} t_node;

// 查找指定名称的节点
t_node* findNode(t_node* nodeArray[], int numNodes, const char* name) {
    for (int i = 0; i < numNodes; i++) {
        if (strcmp(nodeArray[i]->name, name) == 0) {
            return nodeArray[i];
        }
    }
    return NULL;
}

// 创建新节点（若不存在则创建）
t_node* createOrFindNode(t_node* nodeArray[], int* numNodes, const char* name) {
    t_node* node = findNode(nodeArray, *numNodes, name);
    if (node == NULL) {
        if (*numNodes >= MAX_NODES) {
            fprintf(stderr, "节点数量超出上限\n");
            exit(1);
        }
        node = malloc(sizeof(t_node));
        if (node == NULL) {
            fprintf(stderr, "内存分配失败\n");
            exit(1);
        }
        node->name = strdup(name);
        node->mom = NULL;
        node->dad = NULL;
        nodeArray[(*numNodes)++] = node;
    }
    return node;
}

// 检查循环亲属关系（递归遍历祖先）
int hasCycle(t_node* ancestor, t_node* target) {
    if (ancestor == NULL) return 0;
    if (ancestor == target) return 1;
    return hasCycle(ancestor->mom, target) || hasCycle(ancestor->dad, target);
}

// 递归打印家族树
void printFamilyTree(t_node* node, int depth) {
    if (node == NULL) return;
    // 打印缩进
    for (int i = 0; i < depth; i++) {
        printf("  ");
    }
    printf("%s\n", node->name);
    printFamilyTree(node->mom, depth + 1);
    printFamilyTree(node->dad, depth + 1);
}

// 释放所有节点内存
void freeAllNodes(t_node* nodeArray[], int numNodes) {
    for (int i = 0; i < numNodes; i++) {
        free(nodeArray[i]->name);
        free(nodeArray[i]);
    }
}

int main() {
    FILE *fin = fopen("input.txt", "r");
    if (fin == NULL) {
        fprintf(stderr, "无法打开输入文件\n");
        return 1;
    }

    t_node* nodeArray[MAX_NODES];
    int numNodes = 0;
    t_node* currentPerson = NULL;
    char line[MAX_LINE_LENGTH];

    while (fgets(line, MAX_LINE_LENGTH, fin) != NULL) {
        // 跳过空行
        if (strlen(line) <= 1) continue;

        // 处理NAME行：切换当前人物
        if (strncmp(line, "NAME ", 5) == 0) {
            char* name = line + 5;
            name[strcspn(name, "\n")] = '\0';
            currentPerson = createOrFindNode(nodeArray, &numNodes, name);
        }
        // 处理MOTHER行：关联母亲节点
        else if (strncmp(line, "MOTHER ", 7) == 0) {
            if (currentPerson == NULL) {
                fprintf(stderr, "错误：MOTHER行前未定义人物\n");
                continue;
            }
            char* momName = line + 7;
            momName[strcspn(momName, "\n")] = '\0';
            // 检查一人多母
            if (currentPerson->mom != NULL) {
                fprintf(stderr, "错误：人物%s已有母亲%s，无法重复设置\n",
                        currentPerson->name, currentPerson->mom->name);
                continue;
            }
            t_node* momNode = createOrFindNode(nodeArray, &numNodes, momName);
            // 检查循环关系
            if (hasCycle(currentPerson, momNode)) {
                fprintf(stderr, "错误：人物%s的母亲%s会导致循环亲属关系\n",
                        currentPerson->name, momName);
                continue;
            }
            currentPerson->mom = momNode;
        }
        // 处理FATHER行：关联父亲节点
        else if (strncmp(line, "FATHER ", 7) == 0) {
            if (currentPerson == NULL) {
                fprintf(stderr, "错误：FATHER行前未定义人物\n");
                continue;
            }
            char* dadName = line + 7;
            dadName[strcspn(dadName, "\n")] = '\0';
            t_node* dadNode = createOrFindNode(nodeArray, &numNodes, dadName);
            // 检查循环关系
            if (hasCycle(currentPerson, dadNode)) {
                fprintf(stderr, "错误：人物%s的父亲%s会导致循环亲属关系\n",
                        currentPerson->name, dadName);
                continue;
            }
            currentPerson->dad = dadNode;
        }
        else {
            fprintf(stderr, "无效行：%s", line);
        }
    }

    fclose(fin);

    // 输出所有家族树（以无父母的节点为根）
    printf("家族树结构：\n");
    for (int i = 0; i < numNodes; i++) {
        t_node* node = nodeArray[i];
        if (node->mom == NULL && node->dad == NULL) {
            printFamilyTree(node, 0);
            printf("\n");
        }
    }

    freeAllNodes(nodeArray, numNodes);
    return 0;
}

修复说明 #

1. 修正原代码中的字符串匹配笔误，改用strncmp更可靠地判断行首标识
2. 添加currentPerson变量跟踪当前处理的人物，实现父母与子女节点的关联
3. 实现非法输入校验：
   • 检测一人多母的矛盾输入并报错
   • 通过递归遍历祖先的方式检测循环亲属关系并报错
4. 添加家族树递归打印功能，以无父母的节点为根输出完整结构
5. 优化节点查找与创建逻辑，避免重复创建节点

内容的提问来源于stack exchange，提问作者Richard0exe