数据结构其他线性结构分析.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 转置操作 // 转置，将*this的转置矩阵送入B bool SparseMatrix::TransposeTo(SparseMatrix B) { if(terms B.maxterms) return false; B.rows = cols; B.cols = rows; B.terms = terms; if (terms 0) { int p = 0; for (int j = 1; j = cols; j++) // 依次对每一列 for (int k = 0; k terms; k++) // 到data[]中找出该列的元素放到B.data[]中 if (data[k].col == j) { B.data[p].row = j; B.data[p].col = data[k].row; B.data[p].val = data[k].val; p++; } } return true; } 时间复杂度：O(cols×terms) 适用于terms＜＜rows×cols的情况。 转置操作 快速转置。 按A.data中三元组的次序进行转置，并将转置后的三元组放入B中恰当的位置。 引入两个辅助向量： 1num[col-1]表示矩阵A中第col列中非零元的个数； 2cpot[col-1]表示矩阵A中第col列的第一非零元在B.data中的位置。 一个n阶方阵An×n为对称矩阵应满足性质： aij == aji （1≤i, j≤n） 转置操作 一个n阶方阵An×n为对称矩阵应满足性质： aij == aji （1≤i, j≤n） cpot[0]＝0 cpot[col]＝cpot[col－1]＋num[col－1] 1≤col≤ cols-1 M＝ col 0 1 2 3 4 5 6 num[col] 2 2 0 1 2 0 1 cpot[col] 0 2 4 4 5 7 7 用下式来求数组cpot[] 例如： 详细算法请见课本P95。 十字链表存储表示 一个n阶方阵An×n为对称矩阵应满足性质： aij == aji （1≤i, j≤n） 定义： 当非零元素的位置或个数经常发生变化时，三元组表就不适合作稀疏矩阵的存储结构了，用链表作存储结构更为恰当。 行指针域（rptr） 和列指针域（cptr），前者用来指向本行中下一个非零元素；而后者用来指向本列中下一个非零元素。 结点结构： 示例：矩阵B的十字链表表示 一个n阶方阵An×n为对称矩阵应满足性质： aij == aji （1≤i, j≤n） 3.5 广义表 广义表是对线性表的进一步推广，允许每个数据元素不同构，这点跟前面的线性结构均不同。 广义表的基本概念和基本操作 广义表的存储结构 3.5.1 广义表的基本概念和基本操作 广义表（又称列表，简称为表）是n (n≥0)个数据元素的有限序列。通常记作：? GL= (e1, e2, …, en)。 其中 GL是广义表的名字，n为表的长度； ei (1≤ i ≤n）可以为原子项，也可以为广义表，分别称为广义表GL的原子（atom)和子表。 对任一非空广义表有： 表头head: e1 表尾tail :（ e2, …,en） 表的深度:指该广义表展开后所含括号的层数。 广义表示例 广义表 长度 表头 表尾 深度 A = ( ) 0 空 空 1 B = (a, b) 2 a (b) 1 C = ((s, t ), u, (v)) 3 (s, t) (u, (v)) 2 D = (A, (B), y, C) 4 ( ) (((a, b))