数组

地址计算

一维
- Loc( A[ i ] ) = Loc( A[ 1 ]) + ( i - 1 ) * size
二维
- Loc( A[ i ] [ j ]) = Loc( A[ 1 ] [ 1 ]) + ( ( i - 1 ) * n + j - 1 ) * size
三维
- Loc( A[ i ] [ j ] [ k ]) = Loc( A[ 1 ] [ 1 ] [ k ]) + ( ( i - 1 ) * m * n + ( j - 1 ) * n + k -1) * size

特殊矩阵的压缩存储

三角矩阵
- 只存储上/下三角
带状矩阵
- 所有非零元都在以主对角线的为中心的带状区域
- 压缩存储原则：计算位置，将非零元按照行序存储
稀疏矩阵
- 大多数元素为0
- 三元组表示法
  - 存储行、列、值

矩阵转置

二维数组，略
列序递增转置
- 【算法思想】采用按照被转置矩阵三元组表A的列序(即转置后三元组表B的行序)递增的顺序进行转置,并依次送入转置后矩阵的三元组表B中,这样一来,转置后矩阵的三元组表B恰好是以“行序为主序”的。
- 【具体做法】
  
  找出第一行全部元素:第一遍从头至尾扫描三元组表A,找出其中所有col找出第1行全部元素:第一遍从头至尾扫描三元组表A,找出其中所有col
  
  找出第二行全部元素:第二遍从头至尾扫描三元组表A,找出其中所有col为2的三元组,转置后按顺序送到三元组表B中。
  
  以此类推,找出第k行全部元素:第k遍扫描三元组表A,找出其中所有col为h的三元组,转置后按顺序送到三元组表B中。
  
  k的取值:1≤k≤A.n。
  
  为实现处理附设一个当前存放位置计数器j,用于指向当前转置后元素应放入三元组表B中的位置下标。j初值为1,当处理完一个元素后, j加1。
- 时间复杂度：O( A.len * A.n )
一次定位快速转置法。
- 【算法思想】在列序递增转置中,为了使转置后矩阵的三元组表B仍按行序递增存放,必须多次扫描被转置矩阵的三元组表A,以保证按被转置矩阵列序递增形式进行转置,因此要通过双重循环来完成。要改善算法的时间性能,必须去掉双重循环,使整个转置过程通过一重循环来完成,即只对被转置矩阵的三元组表A扫描一次,就使A中所有非零元的三元组"1次定位",直接放到三元组表B的正确位置上。为了能将被转置三元组表A中的元素一次定位到三元组表B的正确位置上,需要预先计算以下数据:
  
  1. 待转置矩阵三元组表A每一-列中非零元素的总个数,即转置后矩阵三元组表B的每一行中非零元素的总个数。
  
  2. 待转置矩阵每-.列中第一个非零元素在三元组表B中的正确位置，即转置后矩阵每一行中第-1个非零元素在三元组表B中的正确位置。
  
  为此,需要设两个数组分别为num[ ]和position[ ],其中num[col]用来存放三元组表A第col列中非零元素总个数(三元组表B第col行中非零元素的总个数), position[col]用来存放转置前三元组表A中第col列(转置后三元组表B中第col行)中第一个非零元素在三元组表B中的存储位置(下标值)。num[col]的计算方法是,将三元组表A扫描一遍,对于其中列号为col的元素，给相应的num数组中下标为col的元素加1。
  
  说明:在num[col]的计算中,采用了“数组下标计数法”。
  
  position[col]的计算方法如下:
  
  position[1]=1,表示三元组表A中,列值为1的第一个非零元素在三元组表B中的下标值。
  
  position[col] = position[col-1] +num[col-1],其中2≤col≤A.n。
- 【具体做法】position[ col ]的初值为三元组表A中第col列(三元组表B的第col行)中第一个非零元素的正确位置,当三元组表A中第col列有一个元素加人到三元组表B时,则position[ col] = position[ col]+1,即令position[ col ]始终指向三元组表A中第col列中下一个非零元素在三元组表B中的正确存放位置(下标值)。
- 时间复杂度：O(A.len + A.n)

十字链表

略