十字交叉链表数据结构c++

十字交叉链表是一种比较特殊的链表结构，它可以用来表示稀疏矩阵。在十字交叉链表中，每个节点都有两个指针，一个指向同一行中的下一个节点，另一个指向同一列中的下一个节点。这样，我们就可以很方便地遍历整个矩阵，而不需要遍历其中的空白位置。

下面是一个简单的十字交叉链表的实现代码：

#include <iostream>
using namespace std;

// 十字交叉链表的节点定义
struct Node {
    int row;
    int col;
    int val;
    Node *right, *down;
};

// 创建一个新的节点
Node* newNode(int row, int col, int val) {
    Node *p = new Node;
    p->row = row;
    p->col = col;
    p->val = val;
    p->right = NULL;
    p->down = NULL;
    return p;
}

// 插入一个节点
void insert(Node *&head, Node *&last, int row, int col, int val) {
    Node *p = newNode(row, col, val);
    if (head == NULL) {
        head = last = p;
    } else {
        last->right = p;
        last = p;
    }
}

// 创建一个稀疏矩阵的十字交叉链表
Node* create(int mat[][4], int m, int n) {
    Node *head = NULL, *last = NULL;
    for (int i = 0; i < m; i++) {
        Node *rowHead = NULL, *rowLast = NULL;
        for (int j = 0; j < n; j++) {
            if (mat[i][j] != 0) {
                insert(rowHead, rowLast, i, j, mat[i][j]);
            }
        }
        if (rowHead != NULL) {
            if (head == NULL) {
                head = last = rowHead;
            } else {
                last->down = rowHead;
                last = rowLast;
            }
        }
    }
    return head;
}

// 打印稀疏矩阵的十字交叉链表
void print(Node *head) {
    for (Node *p = head; p != NULL; p = p->down) {
        for (Node *q = p; q != NULL; q = q->right) {
            cout << q->val << " ";
        }
        cout << endl;
    }
}

int main() {
    int mat[][4] = {
        {1, 0, 0, 0},
        {0, 2, 0, 0},
        {0, 0, 3, 0},
        {0, 0, 0, 4}
    };
    Node *head = create(mat, 4, 4);
    print(head);
    return 0;
}

在上面的代码中，我们定义了一个 `Node` 结构体来表示十字交叉链表中的节点，其中包含了行号、列号、值以及指向同一行中的下一个节点和同一列中的下一个节点的指针。我们还定义了一个 `newNode` 函数来创建一个新的节点，以及一个 `insert` 函数来插入一个节点。

然后，我们定义了一个 `create` 函数来创建一个稀疏矩阵的十字交叉链表。在这个函数中，我们先遍历每一行，然后对于每一行，再遍历每一列，如果当前位置的值不为零，就将它插入到当前行的节点中。最后，我们返回整个链表的头节点。

最后，我们定义了一个 `print` 函数来打印整个链表，以便我们可以测试它是否正确地表示了稀疏矩阵。