【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) 问题?

参考资料

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