HOME

十字链表遍历方法

引言

在数据结构中，十字链表是一种用于表示二维网格（如矩阵）的数据结构。与传统的线性链表不同，十字链表能够更灵活地处理网格中的节点关系，使得遍历操作更加高效和直观。本文将详细介绍十字链表的基本概念及其遍历方法。

十字链表的定义

十字链表由一系列节点组成，每个节点包含四个指针，分别指向其左、右、上、下相邻节点。这种结构不仅能够表示节点之间的四方向关系，还便于实现各种复杂的操作和遍历方式。

节点定义

struct Node {
    int data;            // 数据域
    struct Node* left;   // 左指针
    struct Node* right;  // 右指针
    struct Node* up;     // 上指针
    struct Node* down;   // 下指针
};

遍历方法

深度优先遍历（DFS）

深度优先遍历是一种常见的遍历方式，通过递归或栈实现。在十字链表中，可以从任意一个节点开始，沿着四方向指针进行深入探索。

代码示例

void dfs(Node* node, std::unordered_set<Node*>& visited) {
    if (!node || visited.count(node)) return;
    visited.insert(node);
    printf("%d ", node->data); // 输出当前节点的数据

    Node* left = node->left;   // 深度优先遍历左邻居
    Node* down = node->down;   // 深度优先遍历下邻居
    dfs(left, visited);
    dfs(down, visited);
}

广度优先遍历（BFS）

广度优先遍历则通过队列来实现，确保每个节点都被访问到。从起始节点开始，先访问其四方向的邻居节点，然后再递归地处理这些邻居节点。

代码示例

void bfs(Node* start) {
    std::queue<Node*> queue;
    std::unordered_set<Node*> visited;

    queue.push(start);
    while (!queue.empty()) {
        Node* node = queue.front();
        queue.pop();

        if (visited.count(node)) continue;
        printf("%d ", node->data); // 输出当前节点的数据

        visited.insert(node);

        Node* left = node->left;   // 广度优先遍历左邻居
        Node* right = node->right; // 广度优先遍历右邻居
        Node* up = node->up;       // 广度优先遍历上邻居
        Node* down = node->down;   // 广度优先遍历下邻居

        queue.push(left);
        queue.push(right);
        queue.push(up);
        queue.push(down);
    }
}

按行按列遍历

十字链表可以方便地实现按行或按列的遍历。例如，可以从最上边的一行开始，按从左到右的顺序依次访问；或者从最左边的一列开始，按从上到下的顺序依次访问。

代码示例（按行遍历）

void rowTraversal(Node* top) {
    Node* current = top;
    while (current != nullptr) {
        Node* right = current->right;
        printf("%d ", current->data); // 输出当前节点的数据

        if (right == nullptr || visited.count(right)) break;

        visited.insert(current);
        current = right;
    }
}

优化与注意事项

结语

十字链表提供了一种灵活且高效的方法来处理二维网格数据结构。通过不同的遍历方法，不仅可以实现对整个结构的全面访问，还能针对特定需求进行优化。掌握这些技巧有助于更有效地利用十字链表这一强大的数据结构工具。