如何遍历多级链表？C语言企业人员多级链表遍历搜索求助

嘿，我懂你现在的困境——这种嵌套多级链表的遍历搜索刚开始确实容易卡壳，但只要理清深度优先或者广度优先的思路，结合你的结构体来实现其实并不难。咱们一步步来拆解：

首先先明确你的结构体逻辑：每个节点要么是管理者（is_manager=1）要么是员工（is_manager=0），next指向同层级的下一个节点，down指向当前节点的直属下属（第一个下属节点），parent指向父节点。搜索的核心就是遍历所有节点，找到符合条件的员工节点。

方法一：递归遍历（最直观） #

递归非常适合这种嵌套结构，逻辑简单易懂：从当前节点出发，先检查自身是否是目标员工，再遍历同层级的兄弟节点，最后遍历下属节点。

代码示例 #

#include <string.h>

// 搜索指定名称的员工节点
NODE* search_employee_recursive(NODE* root, const char* target_name) {
    // 边界条件：空节点或空目标名直接返回
    if (root == NULL || target_name == NULL) {
        return NULL;
    }

    // 检查当前节点是否是目标员工（is_manager=0表示员工）
    if (!root->is_manager && strcmp(root->name, target_name) == 0) {
        return root;
    }

    // 先遍历同层级的兄弟节点
    NODE* found_in_siblings = search_employee_recursive(root->next, target_name);
    if (found_in_siblings != NULL) {
        return found_in_siblings;
    }

    // 再遍历当前节点的下属节点
    return search_employee_recursive(root->down, target_name);
}

关键说明 #

• 字符串比较一定要用strcmp，不能直接用==——因为char*是指针，==比较的是内存地址，不是字符串内容。
• 如果需要搜索管理者，只需要把!root->is_manager改成root->is_manager即可。
• 递归的小缺点：如果企业层级极深（比如几百层），可能会触发栈溢出，这时候就需要用迭代方式。

方法二：迭代遍历（避免栈溢出） #

用队列模拟遍历过程，实现广度优先遍历（先遍历同一层级的所有节点，再遍历下一层），适合层级很深的场景。

代码示例 #

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

NODE* search_employee_iterative(NODE* root, const char* target_name) {
    if (root == NULL || target_name == NULL) {
        return NULL;
    }

    // 用链表模拟队列，存储待遍历的节点
    NODE* queue_head = root;
    NODE* queue_tail = root;

    while (queue_head != NULL) {
        NODE* current = queue_head;
        // 出队：移动队列头指针
        queue_head = queue_head->next;

        // 检查当前节点是否是目标员工
        if (!current->is_manager && strcmp(current->name, target_name) == 0) {
            // 若需避免内存泄漏，可额外遍历剩余队列节点清理，视需求而定
            return current;
        }

        // 将同层级的兄弟节点入队（避免重复入队）
        if (current->next != NULL && current->next != queue_head) {
            queue_tail->next = current->next;
            queue_tail = current->next;
        }

        // 将下属节点入队
        if (current->down != NULL) {
            queue_tail->next = current->down;
            queue_tail = current->down;
        }
    }

    // 遍历完所有节点都没找到
    return NULL;
}

关键说明 #

• 广度优先遍历会先找完同一部门的所有节点，再找下属部门；如果需要优先遍历某管理者的所有下属，可把队列换成栈实现深度优先遍历。
• 你的结构是无环的（每个节点有parent，不会出现循环引用），所以不需要额外标记已遍历的节点。

额外实用提示 #

1. 空指针防护：一定要确保target_name和节点的name都不是空指针，否则strcmp会导致程序崩溃。
2. 修改员工数据：找到目标节点后，直接通过返回的指针修改即可，比如：

   NODE* emp = search_employee_recursive(root, "张三");
   if (emp != NULL) {
       // 假设你扩展了结构体添加薪资字段
       // emp->salary = 8000;
   }
   

3. 对接删除功能：把搜索到的节点传入你已实现的删除函数，结合parent、next、down指针调整链表结构即可完成删除。

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