C语言如何创建及遍历十字链表

这篇文章将为大家详细讲解有关C语言如何创建及遍历十字链表，小编觉得挺实用的，因此分享给大家做个参考，希望大家阅读完这篇文章后可以有所收获。

一、十字链表是什么？

十字链表常用于表示稀疏矩阵，可视作稀疏矩阵的一种链式表示，因此，这里以稀疏矩阵为背景介绍十字链表。不过，十字链表的应用远不止稀疏矩阵，一切具有正交关系的结构，都可用十字链表存储。

二、十字链表的存储结构

1.用于总结点的存储结构

m:总行数

n:总列数

len:总元素个数

row_head:行指针数组（通过行指针数组可以快速定位到某一行）

col_head:列指针数组

2.用于单个节点的存储结构

row :行数

col:列数

value:存储的元素值

right :右指针域

down:下指针域

3.对于每一行，通过指针数组记录下每一行的头节点位置，对于列来说相同

4.通过对某一行，某一列的元素可以快速访问

三、代码实现

1.引入头文件并定义结构体

#include  #include/*十字链表的总结点结构类型定义如下：*/typedef struct OLNode{        int row, col; /*非零元素的行和列下标*/        int value;        struct OLNode* right; /*非零元素所在行表、列表的后继链域*/        struct OLNode* down;}OLNode,  *OLink; /*单个节点结构类型定义如下：*/typedef struct{        OLink* row_head; /*行、列链表的头指针向量*/        OLink* col_head;        int m, n, len; /*稀疏矩阵的行数、列数、非零元素的个数*/}CrossList;void out_M(CrossList M);void CreateCrossList(CrossList* M);

2.建立十字链表

void CreateCrossList(CrossList* M){        int m, n, t, i, j, e;        OLNode* p;//单元的结构体指针          OLNode* q;/*采用十字链表存储结构，创建稀疏矩阵M*/        printf("请输入行数,列数和非零元素的个数\n");        scanf_s("%d%d%d", &m, &n, &t); /*输入M的行数,列数和非零元素的个数*/        M->m = m;        M->n = n;        M->len = t;        M->row_head = (OLink*)malloc((m + 1) * sizeof(OLink));        M->col_head = (OLink*)malloc((n + 1) * sizeof(OLink));/*初始化行、列头指针向量，各行、列链表为空的链表*/        for (int h = 0; h < m + 1; h++)        {                M->row_head[h] = NULL;        }        for (int t = 0; t < n + 1; t++)        {                M->col_head[t] = NULL;        }        printf("请输入第i行，第j列中存储的元素，以0结束\n");        for (scanf_s("%d%d%d", &i, &j, &e); i != 0; scanf_s("%d%d%d", &i, &j, &e))        {                p = (OLNode*)malloc(sizeof(OLNode));                p->row = i;                p->col = j;                p->value = e; /*生成结点*/                /*在十字链表中插入节点，对于行指针数组和列指针数组分开看，类似于单链表中的插入操作*/                if (M->row_head[i] == NULL)                {                        M->row_head[i] = p;                        p->right = NULL;                }                else                {/*寻找行表中的插入位置*/                        for (q = M->row_head[i]; q->right && q->right->col < j; q = q->right); /*空循环体*/                        p->right = q->right;                        q->right = p; /*完成插入*/                }                if (M->col_head[j] == NULL)                {                        M->col_head[j] = p;                        p->down = NULL;                }                else                {/*寻找列表中的插入位置*/                        for (q = M->col_head[j]; q->down && q->down->row < i; q = q->down); /*空循环体*/                        p->down = q->down;                        q->down = p; /*完成插入*/                }        }}

3.遍历十字链表

void out_M(CrossList M){        /*遍历十字链表的思想：可采用双重for循环实现，对于每一行中的每一列进行遍历输出*/        int i;        OLNode* p;        char ch;        /*  输出矩阵的总行数、总列数、非零元素总个数 */        printf("\n  总行数有%d    总列数有%d   非零元素有%d\n", M.m,M.n,M.len);        for (i = 1; i <= M.m; i++) {                p = M.row_head[i];         /*  指向第i行 */                if (p) {                        printf("\n 第%d行的数据如下\n", i);                        while (p) {                                printf("  (%3d%3d%4d) ", p->row, p->col, p->value);                                p = p->right;                        }                }                printf("\n");        }}

4.调用函数

void out_M(CrossList M){        /*遍历十字链表的思想：可采用双重for循环实现，对于每一行中的每一列进行遍历输出*/        int i;        OLNode* p;        char ch;        /*  输出矩阵的总行数、总列数、非零元素总个数 */        printf("\n  总行数有%d    总列数有%d   非零元素有%d\n", M.m,M.n,M.len);        for (i = 1; i <= M.m; i++) {                p = M.row_head[i];         /*  指向第i行 */                if (p) {                        printf("\n 第%d行的数据如下\n", i);                        while (p) {                                printf("  (%3d%3d%4d) ", p->row, p->col, p->value);                                p = p->right;                        }                }                printf("\n");        }}

关于"C语言如何创建及遍历十字链表"这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，使各位可以学到更多知识，如果觉得文章不错，请把它分享出去让更多的人看到。