文档介绍：数据结构与算法分析
第1页，共23页，编辑于2022年，星期六
多维数组
数组定义
数组是数据结构的基本结构形式，它是一种顺序式的结构，数组是存储同一类型数据的数据结构，使用数组时需要定义数组的大小和存储数据元素。如果下标从0开始，只要不用减1即可。
按此公式可以推广到多维数组的数据元素的地址计算（假设按照行优先顺序存储）：
m行n 列纵标为k的三维数组，假设第一个元素的地址是loc(a111)，如果按行优先顺序存储，i行j列纵标为p的数据元素的地址为（可以将它分解为二维数组）：
loc(aijp)=loc(a111)+[(i-1)*n*k+(j-1)*k +p-1]*c;
如果下标从0开始，只要不用减1即可。
读者可以从以上的地址公式中可以找出一定的地址计算规律：多维数组中按行优先计算公式用一个下标乘以后面的最大值。
第8页，共23页，编辑于2022年，星期六
多维数组
显示二维数组的内容
一般情况下，只要定义了数组的存储顺序，数组的存储顺序就不会改变了，所以对数组的各种操作后，应按照数组的已定义的存储顺序存储；也就是说，如果是按行优先顺序存储，在对数组操作后，即使改变了存储顺序，应加以改变仍然按照行优先顺序存储。
第9页，共23页，编辑于2022年，星期六
矩阵的压缩存储
矩阵的压缩存储
所谓矩阵的压缩存储，也就是在存储数组时，尽量减少存储空间，但是数组中的每个元素必须存储，所以在矩阵存储中，如果有规律可寻，只要存储其中一部分，而另一部分的存储地址可以通过相应的算法将它计算出来，从而占有比较少的存储空间达到存储整个矩阵的目的，称为矩阵的压缩存储。
矩阵的压缩存储仅是针对特殊矩阵的；而对于没有规律可循的二维数组则不能够使用压缩存储。
二维数组（矩阵）的压缩存储一般有三种，它们分别是对称矩阵、稀疏矩阵和三角矩阵。三种矩阵中以稀疏矩阵比较常见。
第10页，共23页，编辑于2022年，星期六
矩阵的压缩存储
矩阵的压缩存储
特殊矩阵
若n 阶矩阵A中的元素满足以下条件：
aij=aji i≥1，j≥1
则称为n阶对称矩阵。
对于对称矩阵，如果不采用压缩存储，占有的存储单元有n2个，因为是对称矩阵，所以只要存储对角的数据元素和一半的数据元素即可，占有的存储单元有n（n-1）/2个存储单元中。如果我们以行序为主序存储其下三角（包括对角线）的元素，其上三角的元素可以推算出来。
第11页，共23页，编辑于2022年，星期六
矩阵的压缩存储
矩阵的压缩存储
特殊矩阵
如果用一维数组存储一个对称矩阵，只要将对称矩阵存储在一个最大下标为n（n-1）/2的一维数组S中即可。此时按照行优先顺序存储，数据元素aij与数组S的下标k的对应关系为：
i(i-1)/2 +j-1 当i≥j时
k=
j(j-1)/2 + i-1 当i＜j时
第12页，共23页，编辑于2022年，星期六
矩阵的压缩存储
矩阵的压缩存储
特殊矩阵
对于任意给定的一组下标（i，j），均可在S中找到元素aij，反之，对所有元素都能够确定在S中位置，当i＜j时，根据对称矩阵的性质推算即可。由此可以看出对称矩阵的存储可以使用一维数组S存储，占用的空间不再是n2，而是n（n-1）/2空间减少了接近一半，实现了二维数组的压缩存储。
所谓对角矩阵是指，矩阵的所有非零元素都集中在以主对角线为中心的带状区域中，即除了主对角线上和直接在主对角线上、下方若干条对角线上的元素之外，其余元素皆为零。
第13页，共23页，编辑于2022年，星期六
矩阵的压缩存储
矩阵的压缩存储
特殊矩阵
也可以按照某个原则（或者以行序为主序，或者以列序为主序，或者按对角线的顺序）将对角矩阵B的所有非零元素压缩存储到一个一维数组LTB[1…3n-2]中。这里不妨仍然以行序为主序的原则对B进行压缩存储，当B中任一非零元素bij与LTB[k]之间存在着如下一一对应关系：
k=2*i+j-2
时，则有bij=LTB[k]。称LTB[1…3n-2]为对角矩阵B的压缩存储。
上面讨论的几种特殊矩阵中，非零元素的分布都具有明显的规律，因而都可以被压缩存储到一个一维数组中，并能够确定这些矩阵的每个非零元素在一维数组中的存储位置。但是，对于那些非零元素在矩阵中的分布没有规律的特殊矩阵(如稀疏矩阵)，则需要寻求其他方法来解决压缩存储问题。
第14页，共23页，编辑于2022年，星期六
矩阵的压缩存储
矩阵的压缩存储
稀疏矩阵
对稀疏矩阵很