试题-稀疏矩阵一般的压缩存储方法有两种,即()

题目

稀疏矩阵一般的压缩存储方法有两种,即()

A.二维数组和三维数组

B.三元组和散列

C.三元组和十字链表

D.散列和十字链表

上一题 下一题

解答

正确答案是 C

1.三元组顺序表又称有序的双下标法，对矩阵中的每个非零元素用三个域分别表示其所在的行号、列号和元素值。它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。当矩阵中的非0元素少于1/3时即可节省存储空间。

2.十字链表：是既带行指针又带列指针的链接存储方式，每个三元组结点处于所在行单链表与列单链表的交点处，当矩阵的非零元个数和位置在操作过程中变化较大时，用这种存储结构更为恰当。
在十字链表中，每个非零元可用一个含五个域的结点表示，其中 i, j 和e 三个域分别表示该非零元所在的行、列和非零元的值，向右域 right 用以链接同一行中下一个非零元，向下域down 用以链接同一列中下一个非零元。同一行的非零元通过 right 域链接成一个线性链表，同一列的非零元通过 down 域链接成一个线性链表，每个非零元既是某个行链表中的一个结点，又是某个列链表中的一个结点，整个矩阵构成了一个十字交叉的链表，故称这样的存储结构为十字链表，可用两个分别存储行链表的头指针和列链表的头指针的一维数组表示之。