【12.1】高级数据结构-- 多维数组

一、基本概念

  • 数组 (Array) 是数量和元素类型固定的 有序序列
  • 静态数组必须在定义它的时候指定其大小 和类型
  • 动态数组可以在程序运行才分配内存空间
  • 多维数组 (Multi-array) 是向量的扩充
  • 向量的向量就组成了多维数组

二、数组的空间结构

三、数组的存储

  • 内存是一维的,所以数组的存储也只能是一维的
  • 以行为主序 (也称为“行优先”)
  • 以列为主序 (也称为“列优先”)

四、数组的声明

五、用数组表示特殊矩阵

  • 三角矩阵:上三角、下三角
  • 对称矩阵
  • 对角矩阵
  • 稀疏矩阵

5.1 下三角矩阵图例

5.2 对称矩阵

5.3 对角矩阵

  • 对角矩阵是指:所有的非零元素都集中在主对角线及以 它为中心的其他对角线上。
  • 如果 |i-j| > 1,那么数组元素 a[i][j] = 0。
  • 下面是一个三对角矩阵:

5.4 稀疏矩阵

稀疏矩阵中的非零元素非常少,而且分布也不规律

六、稀疏矩阵

稀疏因子:

  • 在 m×n 的矩阵中,有 t 个非零元素,则稀疏因子 为: δ = t/(m*n)
  • 当这个值小于0.05时,可以认为是稀疏矩阵

三元组 (i, j, aij) :输入/输出常用

  • i 是该元素的行号
  • j 是该元素的列号
  • aij 是该元素的值

6.1 稀疏矩阵的十字链表

十字链表有两组链表组成:

  • 行和列的指针序列
  • 每个结点都包含两个指针:同一行的后继,同一列的后继

6.2 经典矩阵乘法

经典矩阵乘法时间代价

  • p=d1-c1+1,m=d3-c3+1,n=d2-c2+1;
  • A 为 p×m 的矩阵,B 为 m×n 的矩阵,乘得的结果 C 为 p×n 的矩阵
  • 经典矩阵乘法所需要的时间代价为 O (p×m×n)

6.3 稀疏矩阵乘法

稀疏矩阵乘法时间代价

  • A为 p×m 的矩阵,B 为 m×n 的矩阵,乘得的结果 C 为 p×n 的矩阵
  • 若矩阵 A 中行向量的非零元素个数最多为 ta
  • 矩阵 B 中列向量的非零元素个数最多为 tb
  • 总执行时间降低为 O ( (ta+tb) × p × n)
  • 经典矩阵乘法所需要的时间代价为 O (p × m × n)

6.4 稀疏矩阵的应用

6.5 思考

多元多项式如何使用矩阵表示?如何 使用稀疏矩阵进行存储?

如何用十字链表结构求解数独(sudoku) 问题?

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾

这里是一个广告位,,感兴趣的都可以发邮件聊聊:tiehan@sina.cn
个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn