计算机软件就是基础软件基础之数据结构_数组.pptVIP

第二章　常用数据结构及其运算----数组;主要介绍多维数组的概念及在计算机中的存放，特殊矩阵的压缩存储及相应运算，广义表的概念和存储结构及其相关运算的实现。通过学习，要求掌握如下内容： 1．多维数组的定义及在计算机中的存储表示； 2．对称矩阵、三角矩阵、对角矩阵等特殊矩阵在计算机中的压缩存储表示及地址计算公式； 3．稀疏矩阵的三元组表示及转置算法实现； 4．稀疏矩阵的十字链表表示及相加算法实现；;多维数组;2．二维数组 二维数组可以看成是向量的推广。例如，设A是一个有m行n列的二维数组，则A可以表示为：;在此，可以将二维数组A看成是由m个行向量[X0，X1， …，Xm-1]T组成，其中，Xi=( ai0, ai1, ….,ain-1)， 0≤i≤m-1；也可以将二维数组A看成是由n个列向量[y0, y1, ……,yn-1]组成，其中 yi=(a0i, a1i, …..,am-1i)，0≤i≤n-1。由此可知二维数组中的每一个元素最??可有两个直接前驱和两个直接后继（边界除外），故是一种典型的非线性结构。;3．多维数组 同理，三维数组最多可有三个直接前驱和三个直接后继，三维以上数组可以作类似分析。因此，可以把三维以上的数组称为多维数组，多维数组可有多个直接前驱和多个直接后继，故多维数组是一种非线性结构。 多维数组在计算机内的存放 怎样将多维数组中元素存入到计算机内存中呢？由于计算机内存结构是一维的（线性的），因此，用一维内存存放多维数组就必须按某种次序将数组元素排成一个线性序列，然后将这个线性序列顺序存放在存储器中，具体实现方法在下一节介绍。;1．存放规则 行优先顺序也称为低下标优先或左边下标优先于右边下标。具体实现时，按行号从小到大的顺序，先将第一行中元素全部存放好，再存放第二行元素，第三行元素，依次类推…… 在BASIC语言、PASCAL语言、C/C++语言等高级语言程序设计中，都是按行优先顺序存放的。例如，对刚才的Am×n二维数组，可用如下形式存放到内存：a00，a01,…a0n-1，a10，a11，...， a1 n-1，…，am-1 0 ， am-1 1，…，am-1 n-1。即二维数组按行优先存放到内存后，变成了一个线性序列（线性表）。 因此，可以得出多维数组按行优先存放到内存的规律：最左边下标变化最慢，最右边下标变化最快，右边下标变化一遍，与之相邻的左边下标才变化一次。因此，在算法中，最左边下标可以看成是外循环，最右边下标可以看成是最内循环。;2．地址计算 由于多维数组在内存中排列成一个线性序列，因此，若知道第一个元素的内存地址，如何求得其他元素的内存地址？我们可以将它们的地址排列看成是一个等差数列，假设每个元素占l个字节，元素aij 的存储地址应为第一个元素的地址加上排在aij 前面的元素所占用的单元数，而aij 的前面有i行(0~i-1)共i×n个元素，而本行前面又有j个元素，故aij的前面一共有i×n+j个元素，设a00的内存地址为LOC(a00)，则aij的内存地址按等差数列计算为LOC(aij)=LOC(a00)+（i×n+j）×l。同理，三维数组Am×n×p按行优先存放的地址计算公式为：LOC(aijk)=LOC(a000)+(i×n×p+j×p+k)×l。;;列优先顺序;2．地址计算 同样与行优先存放类似，若知道第一个元素的内存地址，则同样可以求得按列优存放的某一元素aij的地址。 对二维数组有：LOC(aij)=LOC(a00)+(j×m+i)×l 对三维数组有： LOC(aijk)=LOC(a000)+(k×m×n+j×m+i)×l;二维动态数组的存储方式也称作间接地址方式。间接地址是存储的数据元素为某个数据元素的地址（或称指针）。间接地址有单数据和数组两种情况，单数据的间接地址就是C语言中的指针的指针；数组的间接地址通常称作指针数组，即每个数组元素中存放的是指针类型的数据。指针数组在数据结构的存储结构中较为常见。指针数组中的地址（或称指针）可以是一个数组的首地址，也可以是一个链表的头指针。二维动态数组的指针数组中存放的是一个一维动态数组的首地址。;二维动态数组的全部存储空间不是一次申请的，所以它的每一维数组在物理上是连续的，而全部二维动态数组在物理上不一定是连续的。如图示：;静态数组和动态数组的对比;特殊矩阵及其压缩存储 矩阵是一个二维数组，它是很多科学与工程计算问题中研究的数学对象。矩阵可以用行优先或列优先方法顺序存放到内存中，但是，当矩阵的阶数很大时将会占较多存储单元。而当里面的元素分布呈现某种规律时，这时，从节约存储单元出发，可考虑若干元素共用一个存储单元，即进行压缩存储。所谓压缩存储是指：为多个值相同的元素只分配一个存储空间，值为零的元素不分配空间。但是压缩存储时，节约了存储单元，但怎