C语言数据结构创建及遍历十字链表

什么是十字链表

十字链表是一种二维数据结构，常用于表示稀疏矩阵，它是在链式储存结构的基础上，将正反两个方向都链起来，形成一个交叉的链表。

十字链表的创建

在创建十字链表时，我们需要定义两种结构：

//行结点
typedef struct CrossRowNode{
    int row; //行下标
    int col; //列下标
    int value; //具体值
    struct CrossRowNode *right, *down; //右指针和下指针
} CRNODE, *CRPTR;

// 列头结点
typedef struct CrossColHead{
    int colIndex; // 列下标
    struct CrossColHead *next; //下一个列头结点
    CRPTR bottom; //该列第一个非零元素所在的行结点
} CHEAD, *CHPTR;

其中，CRNODE表示十字链表中的行结点，CHEAD表示列头结点，CRPTR表示CrossRowNode的指针，CHPTR表示CrossColHead的指针。

我们可以通过输入稀疏矩阵的行数和列数，以及非零元素的个数，来初始化一个十字链表：

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

// 初始化一个十字链表
void initCrossList(int row, int col, int count, int data[][3], CHPTR *chead){
    int i, j, k;
    CRPTR p, last;
    // 创建列头结点
    for(i = 0; i < col; ++i){
        CHPTR head = (CHPTR)malloc(sizeof(CHEAD));
        head->colIndex = i;
        head->next = NULL;
        head->bottom = NULL;
        (*chead)->next = head;
        *chead = head;
    }
    // 创建行结点
    for(k = 0; k < count; ++k){
        i = data[k][0];
        j = data[k][1];
        // 创建一个新结点
        p = (CRPTR)malloc(sizeof(CRNODE));
        p->row = i;
        p->col = j;
        p->value = data[k][2];
        // 找到该元素所在的列头结点
        last = (*chead)->next;
        while(last->colIndex < j) last = last->next;
        // 找到该元素的上一个结点
        CRPTR pre = last->bottom;
        while(pre && pre->row < i){
            last = pre;
            pre = pre->down;
        }
        // 将新结点插入到链表中
        if(last->bottom == NULL){
            last->bottom = p;
            p->down = NULL;
        } else {
            p->down = last->bottom->down;
            last->bottom->down = p;
        }
        // 找到该元素所在的行头结点
        last = (*chead)->next;
        while(last->colIndex < j) last = last->next;
        // 找到该元素的上一个结点
        pre = last;
        while(pre->bottom != NULL && pre->bottom->row < i) pre = pre->bottom;
        // 将新结点插入到链表中
        if(pre->bottom == NULL){
            pre->bottom = p;
            p->right = NULL;
        } else {
            p->right = pre->bottom->right;
            pre->bottom->right = p;
        }
    }
}

示例：

假设我们有一个3行4列的稀疏矩阵：

1 0 0 0
0 0 0 2
3 0 4 0

将其转换成十字链表，可以这样调用函数：

int data[4][3] = {{0, 0, 1}, {1, 3, 2}, {2, 0, 3}, {2, 2, 4}};
int row = 3, col = 4, count = 4;
CHPTR head = (CHPTR)malloc(sizeof(CHEAD));
initCrossList(row, col, count, data, &head);

十字链表的遍历

遍历十字链表的方式有多种，这里介绍两种比较常用的遍历方式。

按照行优先顺序遍历

按照行优先顺序遍历十字链表是比较常用的一种方式，具体实现可以使用嵌套循环来实现。

// 按照行优先顺序遍历十字链表
void travelByRow(CHPTR head){
    CRPTR node;
    for(node = head->bottom; node != NULL; node = node->down){
        printf("%d %d %d\n", node->row, node->col, node->value);
        CRPTR next = node->right;
        while(next != NULL){
            printf("%d %d %d\n", next->row, next->col, next->value);
            next = next->right;
        }
    }
}

示例：

假设我们有一个3行4列的十字链表，内容与之前的矩阵相同，我们可以按照以下方式遍历该链表：

travelByRow(head);

输出结果为：

0 0 1
1 3 2
2 0 3
2 2 4

按照行优先顺序遍历

按照列优先顺序遍历十字链表也是比较常用的一种方式，具体实现与行优先顺序遍历类似，只是循环的顺序相反。

// 按照列优先顺序遍历十字链表
void travelByCol(CHPTR head){
    CRPTR node;
    CHPTR chead = head->next;
    while(chead != NULL){
        node = chead->bottom;
        while(node != NULL){
            printf("%d %d %d\n", node->row, node->col, node->value);
            node = node->down;
        }
        chead = chead->next;
    }
}

示例：

与之前相同，假设我们有一个3行4列的十字链表，可以按照以下方式遍历该链表：

travelByCol(head);

输出结果为：

0 0 1
2 0 3
1 3 2
2 2 4