资源描述：
《数组和广义表-副本》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第五章数组和广义表本章内容5.1数组的定义5.2数组的顺序表示5.3矩阵的压缩存储5.3.1特殊矩阵5.3.2稀疏矩阵5.4广义表的定义5.5广义表的存储结构5.1数组的定义数组是我们很熟悉的一种数据结构，它可以看作线性表的推广。数组作为一种数据结构其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型，比如：一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组”的一维数组，三维数组可以看作“数据元素是二维数组”的一维数组，依此类推。由于数组中各元素具有统一的类型，并且数组元
2、素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。多维数组是一维数组的推广。2例如，二维数组A：5.1数组的定义(续)Am×n=a11a12…a1na21a22…a2n…………am1am2…amn二维数组A可以看成是由m个行向量组成的向量，也可以看成是n个列向量组成的向量。数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。3由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一
3、列序列，然后将这个线性序列存放在存储器中。数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般采用顺序存储的方法来表示数组。5.2数组的顺序表示4行优先顺序或以行为主序存储方式：将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。以二维数组为例，按行优先顺序存储的线性序列为：a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,amn在PASCAL、C等语言中，数组就是按行优先顺序存储的。5.2数组的顺序表示(续)Am×n=a11a12…a1na21
4、a22…a2n…………am1am2…amnLOC(aij)=LOC(a11)+[(i-1)*n+j-1]*d5列优先顺序或以列为主序存储方式：将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后，A的m*n个元素按列优先顺序存储的线性序列为：a11,a21,…,am1,a12,a22,…am2,……,an1,an2,…,anm在FORTRAN语言中，数组按列优先顺序存储。5.2数组的顺序表示(续)Am×n=a11a12…a1na21a22…a2n…………am1am2…amnLOC(aij)=
5、LOC(a11)+[(j-1)*m+i-1]*d6行优先顺序——先排最右的下标，从右到左，最后排最左下标。列优先顺序——先排最左下标，从右向左，最后排最右下标。例如：三维数组Am*n*p5.2数组的顺序表示(续)7只要知道开始结点的存放地址（即基地址）、维数和每维的上、下界，以及每个数组元素所占用的单元数，就可以将数组元素的存放地址表示为其下标的线性函数。因此，数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。数组存储的特点8压缩存储：为多个值相同的非零元素只分配一个存储空间
6、；对零元素不分配空间。5.3矩阵的压缩存储9特殊矩阵：非零元素按照一定的规律分布。5.3.1特殊矩阵的压缩存储a1,1a1,2…a1,na2,1a2,2…a2,n……ai,j…an,1an,2…an,naij=aji1234213433144441对称矩阵常见的特殊矩阵有对称矩阵、三角矩阵、对角矩阵等。对称矩阵：元素的值按照主对角线对称105.3.1(续)对称矩阵的压缩存储对称矩阵123421343314444112342134331444411213314441数组B12345678910下标k例如
7、：一个4*4的对称矩阵。115.3.1(续)对称矩阵的压缩存储对称矩阵数组Bai,jan,na1,1a2,1a2,2a3,11234km下标a1,1a1,2…a1,na2,1a2,2…a2,n……ai,j…an,1an,2…an,na1,1a2,1a2,2…ai,j…an,1an,2…an,n……k=?m=?推广至一般情况，n*n的对称矩阵125.3.1(续)三角矩阵的压缩存储10002100331044411234013400140001(a)下三角矩阵(a)上三角矩阵三角矩阵：上(下)三角矩阵是指
8、矩阵的下（上）三角（不包括对角线）中的元素均为常数或零的n阶矩阵，即非零元素的分布在矩阵中呈现为三角形。例如：一个4*4的三角矩阵。135.3.1(续)三角矩阵的压缩存储18882188331844411234913499149991(c)下三角矩阵(d)上三角矩阵例如：一个4*4的三角矩阵。145.3.1(续)三角矩阵的压缩存储a0,0a0,1a0,2………a0,n-2a0,n-1a1,1a1,2………a1,n-2a1,n-1………ai,i…ai,j…
