资源描述：
《数据结构与算法多维数组》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构与算法 多维数组赵颖zhaoying511@126.com中南大学，目录数组的定义数组的存储结构特殊矩阵的压缩存储对称矩阵三角矩阵对角矩阵稀疏矩阵稀疏矩阵的定义稀疏矩形的三元组存储结构稀疏矩阵的三元组存储结构的转置稀疏矩阵的链式存储结构数组的定义数组是所有高级编程语言中都已实现的固有数据类型，因此凡学习过高级程序设计语言的读者对数组都不陌生。但它和其它诸如整数、实数等原子类型不同，它是一种结构类型，由许多具有相同特点的元素组成，而且每个元素都可以又是结构类型。换句话说，“数组”是一种数据结构。那么数组是线性结构吗？数组和线性结构有什么关系？数组的定义数组的定义数组是
2、一种数据结构，其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型数组与线性表的关系一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组”的一维数组，三维数组可以看作“数据元素是二维数组”的一维数组，依此类推。结论：线性表结构是数组结构的一个特例，而数组结构又是线性表结构的扩展。()()()()()()()()()数组的定义数组的基本特性数组是一个具有固定数据元素格式和数量的数据有序集数组一旦定义后，数组中的数据元素数目是固定的，数据元素的类型的固定的基于这一点，通常在各种高级语言中数组一旦被定义，每一维的大小及上下界都不能改变。数组中的每个数据元
3、素都与一组唯一的下标值相对应；基于这一点，通常数组被定义和赋值后，不便于做插入和删除数据元素的操作。因为插入和删除操作是不能改变每一维的大小及上下界都不能改变。只能造成数组中的数据发生移动。数组的基本操作取值操作：给定一组下标，读其对应的数据元素。赋值操作：给定一组下标，存储或修改与其相对应的数据元素。目录数组的定义数组的存储结构特殊矩阵的压缩存储对称矩阵三角矩阵对角矩阵稀疏矩阵稀疏矩阵的定义稀疏矩形的三元组存储结构稀疏矩阵的三元组存储结构的转置稀疏矩阵的链式存储结构数组的存储结构从理论上讲，数组结构也可以使用两种存储结构，即顺序存储结构和链式存储结构。然而，由于数组结构以取
4、值和赋值为主要操作，不使用插入、删除元素的操作，所以使用顺序存储结构更为适宜。换句话说，一般的数组结构不使用链式存储结构。组成数组结构的元素可以是多维的，但存储数据元素的内存单元地址是一维的，因此，在存储数组结构之前，需要解决将多维关系映射到一维关系的问题。数组的存储结构一维数组的存储和取值在内存中用地址连续的一块存储空间顺序存放数组各元素数组的存储结构一维数组的存储和取值的计算公式假设L为每个数据元素所占据的存储单元数目。假设数组从1号开始编码（注意：c语言中数组从0编码）相邻两个数据元素的存储位置计算公式LOC(ai+1)=LOC(ai)+L任意一个数据元素的存储位置的计
5、算公式为：LOC(ai+1)=LOC(a1)+i*L数组元素的存储位置是其下标的线性函数，由于计算各个元素存储位置的时间相等，所以存取数组中任一元素的时间也相等。我们称具有这一特点的存储结构为随机存储结构。数组的存储结构多维数组的存储和取值用一维内存来表示多维结构，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。多维数组通常有两种顺序存储方式：行优先顺序（低下标优先）将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。以二维数组为例，按行优先顺序存储的线性序列为：a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,
6、amn在PASCAL、C语言中，数组就是按行优先顺序存储的。列优先顺序（高下标优先）将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后，A的m*n个元素按列优先顺序存储的线性序列为：a11,a21,…,am1,a12,a22,…am2,……,an1,an2,…,anm在FORTRAN语言中，数组就是按列优先顺序存储的。a11a12……..a1na21a22……..a2nam1am2……..amn………………….二维数组按行序为主序存放amn……..am2am1……….a2n……..a22a21a1n…….a12a1101n-1m*n-1n二维按列序为主序存放01m
7、-1m*n-1mamn……..a2na1n……….am2……..a22a12am1…….a21a11a11a12……..a1na21a22……..a2nam1am2……..amn………………….数组的存储结构二维数组的元素位置计算公式？？？算算看？？？假设数组初始元素为A[1,1]（注意：C语言数组从0开始编号）每个数组元素占据L个地址单元行优先：Loc(aij)=Loc(a11)+[(i-1)*n+(j-1)]*L因为数组元素aij的前面有i-1行，每一行的元素个数为n，在第i行中它的前面还有j-1个
