用C语言怎样实现十字链表？一文带你看懂过程

这篇文章我们来了解用C语言怎样实现十字链表的内容，一些朋友可能对于十字链表是什么也不是很了解，对此下文会介绍十字链表及十字链表的实现，但是本文示例需要读者有一定代码基础会更好理解，最好是能了解指针，链表，数组等这些诶，那么接下来就跟随小编来一起学习一下吧！

一、十字链表是什么？

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

二、十字链表的存储结构

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

m:总行数

n:总列数

len:总元素个数

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

col_head:列指针数组

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

row :行数

col:列数

value:存储的元素值

right :右指针域

down:下指针域

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

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

三、代码实现

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

#include stdio.h>
     
#includestdlib.h>

/*十字链表的总结点结构类型定义如下：*/
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语言怎样实现十字链表应该都清楚了吧，上述示例有一定的借鉴价值，有需要的朋友可以参考学习，希望对大家学习C语言有帮助，想要了解更多大家可以关注网络其它相关文章。

文本转载自脚本之家

声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！