数据结构之数组与广义表课件(编辑修改稿)

数据结构之数组与广义表课件(编辑修改稿)内容摘要：

/*矩阵的行数 */ int。 /*矩阵的列数 */ int tn。 /*矩阵的非 0元素个数 */ tritype data[maxn]。 /*非 0元素的三元组表 */ }tmatrix。  把 M压缩后，存储成： 行数 rn 列数 非 0数 tn 行号 列号 元素值 1 2 2 1 3 1 3 1 1 3 6 4 5 2 8 6 1 5 7 6 9 7 7 7  例 : 求 M的转置矩阵 . s: t: 1 2 2 1 3 1 3 1 1 3 6 4 5 2 8 6 1 5 7 6 9 7 7 7 7 7 7 1 3 1 1 6 5 2 1 2 2 5 8 3 1 1 6 3 4 6 7 9 基本思想： 把 S转置成 T，就是把 S中的每一个三元组的行号和列号（ row 和 col）交换，并存储在 T中。 但是，这样的结果是按列优先存储的稀疏矩阵 T，所以，还必须重新排列三元组的顺序。 由于 S的列是 T的行，因此，应按 S中列的顺序扫描 ,即先扫描第 1列所有非 0元素，然后第2列所有非 0元素 ,…… ，最后得到的结果就是按行优先顺序存储的。 算法如下： Inttrmatrix(tmatrix s, t) { int i, j, k。 =。 /*列数变行数 */ =。 /*行数变列数 */ =； /*非 0元素个数赋值 */ if (!=0) { j=0。 /*三元组 T（目的地）中的位置 for (i=1。 i=。 i++) /* for (k=0。 k。 k++) /* 0元素个数 if([k].col==i) /*若列号为 I, 则置换 { [j].row=[k].col。 [j].col=[k].row。 [j].element=[k].element。 j++。 } }。 return(0)。 } 稀疏矩阵的十字链表 当矩阵的非零元素的位置和个数经常变动时 , 三元组就不适用于稀疏矩阵的存储了 . 例 : A=A+B 把矩阵 B加到 A上 , 则会产生大量的数据移动 , 此时 , 采用十字链表存储更合适 . 对一个 m*n 的稀疏矩阵 , 对每一个非零元素 , 用一个结点表示 . 结点的结构如下 : 其中 : row 非零元素所在行 col 非零元素所在行 value 非零元素的值。