用十字链表构成稀疏矩阵时，为什么每行列链表为循环链表?
一、用十字链表构成稀疏矩阵时，为什么每行\列链表为循环链表
因为每行\列链表为循环链表可以解决数组 “不利于插入和删除数据” 的特点，将所有行链表的表头存储到一个数组（rhead），将所有列链表的表头存储到另一个数组（chead）中。
两个指针域分别指向所在行的下一个元素和所在列的下一个元素。
可以用如下的结构体来表示链表中的节点：
typedef struct OLNode{ int i,j;//元素的行标和列标 int data;//元素的值 struct OLNode * right,*down;//两个指针域}OLNode, *OLink;在此基础上，表示十字链表的结构体为：
typedef struct{ OLink *rhead, *chead; //行和列链表头指针 int mu, nu, tu; //矩阵的行数,列数和非零元的个数}CrossList;以存储图 1 所示的矩阵为例，十字链表存储该矩阵的 C 语言实现代码为：
#include运行结果：
输入矩阵的行数、列数和非0元素个数：3 4 4
1 1 3
1 4 5
2 2 -1
3 1 2
输出矩阵M:
3 0 0 5
0 -1 0 0
2 0 0 0
延伸阅读：
二、稀疏矩阵的十字链表存储
当矩阵的非零元个数和位置在操作过程中变化较大时，就不宜采用顺序存储结构来表示三元组的线性表。对这种类型的矩阵，采用链式存储结构表示三元组的线性表更为恰当。
在链表中，每个非零元可用一个含 5 个域的结点表示，其中 i , j , e 这 3 个域分别表示该非零元所在的行、列和非零元的值，向右域 right 用以链接同一行中下一个非零元，向下域 down 用以链接同一列中下一个非零元。
同一行的非零元通过 right 域链接成一个线性链表，同一列的非零元通过 down 域链接成一个线性链表，每个非零元既是某个行链表中的一个结点，又是某个列链表中的一个结点，整个矩阵构成了一个十字交叉的链表，故称这样的存储结构为十字链表。
可用两个分别存储行链表的头指针和列链表的头指针的一维数组表示。
猜你喜欢LIKE
相关推荐HOT
更多>>
chmod 755与chmod +x的区别?
一、chmod 755与chmod +x的区别chmod 755 的含义是将此文件的permission flags 改为 111(7) 101(5) 101(5)。也就是755 的含义所有用户都拥有详情>>
2023-10-14 21:44:16
在SWIFT中class与struct有哪些区别?
一、在SWIFT中class与struct的区别1、继承不同class可以继承自另一个class，而struct则不能。这意味着，一个class可以通过继承来获得父类的所有...详情>>
2023-10-14 20:36:56
Java开发主要是做什么?
一、Java开发主要的用途Java是一种高级编程语言，最初由Sun Microsystems在1995年推出。Java有着丰富的应用场景，被广泛应用于桌面应用程序、We...详情>>
2023-10-14 19:50:06
PHP能做什么?
一、PHP能做什么1、Web开发PHP是一种广泛用于Web开发的脚本语言，可以用来开发各种类型的Web应用程序，包括动态网站、博客、论坛、电子商务网站...详情>>
2023-10-14 19:15:46热门推荐
技术干货
京公网安备 11010802030320号