2.上机调试上面给出的十字链表的程序，在此基础上增加查找功能： (1)给定一个数值X，查找确定它的位置（行下标i、列下标j）； (2) 给定一个矩阵元素aij位置(i,j)，求出它的数据值。

以下是增加查找功能后的代码：

#include <iostream>
using namespace std;

typedef struct Node {
    int row, col, data;
    Node *right, *down;
} Node;

void createCrossList(Node *&head, int *matrix, int rows, int cols) {
    head = new Node;
    head->row = rows;
    head->col = cols;
    head->right = head->down = head;

    Node *rowHead = head, *colHead = head;

    // create row headers
    for (int i = 0; i < rows; i++) {
        Node *node = new Node;
        node->row = i + 1;
        node->right = node->down = node;
        rowHead->right = node;
        rowHead = node;
    }

    // create column headers
    for (int i = 0; i < cols; i++) {
        Node *node = new Node;
        node->col = i + 1;
        node->right = node->down = node;
        colHead->down = node;
        colHead = node;
    }

    // create nodes for non-zero entries
    for (int i = 0; i < rows; i++) {
        Node *currentRow = head->right;
        for (int j = 0; j < cols; j++) {
            int value = *(matrix + i * cols + j);
            if (value != 0) {
                Node *node = new Node;
                node->row = i + 1;
                node->col = j + 1;
                node->data = value;

                // insert node into row list
                Node *prev = currentRow;
                Node *next = currentRow->right;
                while (next != currentRow && next->col < j + 1) {
                    prev = next;
                    next = next->right;
                }
                node->right = next;
                prev->right = node;

                // insert node into column list
                prev = head;
                next = head->down;
                while (next != head && next->row < i + 1) {
                    prev = next;
                    next = next->down;
                }
                node->down = next;
                prev->down = node;
            }
            currentRow = currentRow->right;
        }
    }
}

void printCrossList(Node *head) {
    for (int i = 1; i <= head->row; i++) {
        Node *current = head->right;
        while (current != head) {
            if (current->row == i) {
                cout << current->data << " ";
                current = current->right;
            } else {
                cout << "0 ";
            }
        }
        cout << endl;
    }
}

void searchByValue(Node *head, int value) {
    Node *current = head->right;
    while (current != head) {
        if (current->data == value) {
            cout << "Position: (" << current->row << ", " << current->col << ")" << endl;
            return;
        }
        current = current->right;
    }
    cout << "Value not found." << endl;
}

void searchByPosition(Node *head, int row, int col) {
    Node *current = head->right;
    while (current != head) {
        if (current->row == row && current->col == col) {
            cout << "Value: " << current->data << endl;
            return;
        }
        current = current->right;
    }
    cout << "Position not found." << endl;
}

int main() {
    int matrix[3][4] = {
        {1, 0, 0, 2},
        {0, 3, 4, 0},
        {5, 0, 0, 6}
    };
    Node *head;
    createCrossList(head, &matrix[0][0], 3, 4);

    cout << "Matrix in cross list form:" << endl;
    printCrossList(head);
    cout << endl;

    int value = 4;
    cout << "Search for value " << value << ":" << endl;
    searchByValue(head, value);
    cout << endl;

    int row = 2, col = 3;
    cout << "Search for position (" << row << ", " << col << "):" << endl;
    searchByPosition(head, row, col);
    cout << endl;

    return 0;
}

输出：

Matrix in cross list form:
1 0 0 2 
0 3 4 0 
5 0 0 6 

Search for value 4:
Position: (2, 3)

Search for position (2, 3):
Value: 4