数据结构教程5数组和广义表

第五章数组和广义表⒈教学内容：5.1多维数组5.2特殊矩阵的压缩存储5.3稀疏矩阵5.4广义表⒉教学目的：⑴理解多维数组的结构特点和在内存中的两种顺序存储方式；⑵理解并掌握矩阵和特殊矩阵元素在存储区中地址的计算；⑶领会稀疏矩阵的压缩方式和简单运算；⑷了解广义表的定义和基本运算。第五章数组和广义表⒊教学重点：⑴多维数组的逻辑结构；⑵多维数组的两种顺序存储方式，计算给定元素在存储区中的地址；⑶对称矩阵、三角矩阵的压缩存储方式；⑷稀疏矩阵的三元组表表示方法。⒋教学难点：稀疏矩阵的压缩存储表示下的运算的实现5.1多维数组§数组的逻辑结构§数组的内存映象5.1.1数组的逻辑结构§数组是我们熟悉的一种数据结构，可以看作线性表的推广。数组作为一种数据结构其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型，比如：一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组”的一维数组，三维数组可以看作“数据元素是二维数组”的一维数组，依此类推。数组是一个具有固定格式和数量的数据有序集，每一个数据元素有唯一的一组下标来标识，因此，在数组上不能做插入、删除数据元素的操作。通常在各种高级语言中数组一旦被定义，每一维的大小及上下界都不能改变。类型特点:1)只有引用型操作，没有加工型操作；2)数组是多维的结构，而存储空间是一个一维的结构。在数组中通常做下面两种操作：(1)取值操作：给定一组下标，读其对应的数据元素。(2)赋值操作：给定一组下标，存储或修改与其相对应的数据元素。我们着重研究二维和三维数组，因为它们的应用是广泛的，尤其是二维数组。5.1.2数组的内存映象§通常，数组在内存被映象为向量，即用向量作为数组的一种存储结构，这是因为内存的地址空间是一维的，数组的行列固定后，通过一个映象函数，则可根据数组元素的下标得到它的存储地址。§对于一维数组按下标顺序分配即可。§对多维数组分配时，要把它的元素映象存储在一维存储器中，一般有两种存储方式：一是以行为主序（或先行后列）的顺序存放，如BASIC、PASCAL、COBOL、C等程序设计语言中用的是以行为主的顺序分配，即一行分配完了接着分配下一行。另一种是以列为主序（先列后行）的顺序存放，如FORTRAN语言中，用的是以列为主序的分配顺序，即一列一列地分配。以行为主序的分配规律是：最右边的下标先变化，即最右下标从小到大，循环一遍后，右边第二个下标再变，…，从右向左，最后是左下标。以列为主序分配的规律恰好相反：最左边的下标先变化，即最左下标从小到大，循环一遍后，左边第二个下标再变，…，从左向右，最后是右下标。有两种顺序映象的方式:1)以行序为主序(低下标优先)；2)以列序为主序(高下标优先)。例如一个2×3二维数组，逻辑结构可以用左图表示。以行为主序的内存映象如右图（a）所示。分配顺序为：a11，a12，a13，a21，a22，a23;以列为主序的分配顺序为：a11，a21，a12，a22，a13，a23;它的内存映象如右图（b）所示。设有m×n二维数组Amn，按元素的下标求其地址：以“以行为主序”的分配为例：设数组的基址为LOC(a11)，每个数组元素占据L个地址单元，那么aij的物理地址可用一个线性寻址函数计算：LOC(aij)=LOC(a11)+((i-1)*n+j-1)*L称为基地址或基址。在C语言中，数组中每一维的下界定义为0，则：LOC(aij)=LOC(a00)+(i*n+j)*L推广到一般的二维数组：A[c1..d1][c2..d2]，则aij的物理地址计算函数为：LOC(aij)=LOC(ac1c2)+((i-c1)*(d2-c2+1)+(j-c2))*L同理对于三维数组Amnp，即m×n×p数组，对于数组元素aijk其物理地址为：LOC(aijk)=LOC(a111)+((i-1)*n*p+(j-1)*p+k-1)*L推广到一般的三维数组：A[c1..d1][c2..d2][c3..d3]，则aijk的物理地址为：LOC(i,j)=LOC(ac1c2c3)+((i-c1)*(d2-c2+1)*(d3-c3+1)+(j-c2)*(d3-c3+1)+(k-c3))*L数组元素的存储位置是其下标的线性函数。•三维数组的逻辑结构和以行为主序的分配示意图如图所示。例5.1若矩阵Am×n中存在某个元素aij满足：aij是第i行中最小值且是第j列中的最大值，则称该元素为矩阵A的一个鞍点。试编写一个算法，找出A中的所有鞍点。基本思想：在矩阵A中求出每一行的最小值元素，然后判断该元素它是否是它所在列中的最大值，是则打印出，接着处理下一行。矩阵A用一个二维数组表示。voidsaddle(intA[][],intm,intn)/*m,n是矩阵A的行和列*/{inti,j,min;for(i=0;im;i++)/*按行处理*/{min=A[i][0]for(j=1;jn;j++)if(A[i][j]min)min=A[i][j];/*找第i行最小值*/for(j=0;jn;j++)/*检测该行中的每一个最小值是否是鞍点*/if(A[i][j]==min){k=j;p=0;while(pm&&A[p][j]=min)p++;if(p=m)printf(＂%d,%d,%d\n＂,i,k,min);}}}算法的时间性能为O(m*(n+m*n))。5.2特殊矩阵的压缩存储§对称矩阵§三角矩阵§带状矩阵矩阵是在很多科学与工程计算中遇到的数学模型。在数学上，矩阵是这样定义的：它是一个由m×n个元素排成的m行（横向）n列（纵向）的表。下面就是一个矩阵：它是一个m×n的矩阵。mnmmnnaaaaaaaaa.....................212222111211所谓特殊矩阵就是元素值的排列具有一定规律的矩阵。常见的这类矩阵有：对称矩阵、下（上）三角矩阵、对角线矩阵等等。5.2.1对称矩阵§对称矩阵的特点是：在一个n阶方阵中，有aij=aji，其中1≤i,j≤n，如图所示是一个５阶对称矩阵。•对称矩阵关于主对角线对称，因此只需存储上三角或下三角部分即可。比如，只存储下三角中的元素aij，其特点是j≤i且1≤i≤n，对于上三角中的元素aij，它和对应的aji相等，因此当访问的元素在上三角时，直接去访问和它对应的下三角元素即可，这样，原来需要n*n个存储单元，现在只需要n(n+1)/2个存储单元了，节约了n(n-1)/2个存储单元，当n较大时，这是可观的一部分存储资源。•如何只存储下三角部分？对下三角部分以行为主序顺序存储到一个向量中去，在下三角中共有n*(n+1)/2个元素，因此，不失一般性，设存储到向量SA[n(n+1)/2]中，存储顺序可用下图示意，这样，原矩阵下三角中的某一个元素aij则具体对应一个sak，下面的问题是要找到k与i、j之间的关系。n•对于下三角中的元素aij，其特点是：i≥j且1≤i≤n，存储到SA中后，根据存储原则，它前面有i-1行，共有1+2+…+i-1=i*(i-1)/2个元素，而aij又是它所在的行中的第j个，所以在上面的排列顺序中，aij是第i*(i-1)/2+j个元素，因此它在SA中的下标k与i、j的关系为：k=i*(i-1)/2+j-1(０≤kn*(n+1)/2)•若ij，则aij是上三角中的元素，因为aij=aji，这样，访问上三角中的元素aij时则去访问和它对应的下三角中的aji即可，因此将上式中的行列下标交换就是上三角中的元素在SA中的对应关系：k=j*(j-1)/2+i-1(０≤kn*(n+1)/2)综上所述，对于对称矩阵中的任意元素aij，若令I=max(i,j)，J=min(i,j)，则将上面两个式子综合起来得到：k=I*(I-1)/2+J-1。5.2.2三角矩阵§形如下图的矩阵称为三角矩阵，其中c为某个常数。其中(a)为下三角矩阵：主对角线以上均为同一个常数；(b)为上三角矩阵，主对角线以下均为同一个常数；下面讨论它们的压缩存储方法。下（上）三角矩阵的特点是以主对角线为界的上（下）半部分是一个固定的值，下（上）半部分的元素值没有任何规律。比如，下面是一个下三角矩阵：209261303010800126000291.下三角矩阵与对称矩阵类似，不同之处在于存完下三角中的元素之后，紧接着存储对角线上方的常量，因为是同一个常数，所以存一个即可，这样一共存储了n*(n+1)/2+1个元素，设存入向量：SA[n*(n+1)/2+1]中，这种的存储方式可节约n*(n-1)/2-1个存储单元，sak与aji的对应关系为：)k是下三角矩阵位于（i，j）位置的元素在一维数组中的存放位置。ji12)1(ji12)1(当当ijjjiik2.上三角矩阵对于上三角矩阵，存储思想与下三角类似，以行为主序顺序存储上三角部分，最后存储对角线下方的常量。对于第1行，存储n个元素，第2行存储n-1个元素，…，第p行存储(n-p+1)个元素，aij的前面有i-1行，共存储：个元素，aij是它所在的行中要存储的第（j-i+1）个，也就是上三角存储顺序中的第(i-1)*(2n-i+2)/2+(j-i+1)个，因此它在SA中的下标为：k=(i-1)*(2n-i+2)/2+j-i。综上，sak与aji的对应关系为：§对角矩阵的特点是所有的非零元素都集中在以主对角线为中心的带状区域中。比如，下面就是一个3阶对角矩阵：113400069210001773000020590001235.2.3带状矩阵(对角矩阵)§n阶矩阵A称为带状矩阵，如果存在最小正数m，满足当∣i-j∣≥m时，aij=0，这时称w=2m-1为矩阵A的带宽。下图是一个w=3(m=2)的带状矩阵。带状矩阵也称为对角矩阵。由下图可看出，在这种矩阵中，所有非零元素都集中在以主对角线为中心的带状区域中，即除了主对角线和它的上下方若干条对角线的元素外，所有其他元素都为零(或同一个常数c)。•一种压缩方法是将A压缩到一个n行w列的二维数组B中，如下图所示，当某行非零元素的个数小于带宽w时，先存放非零元素后补零。•那么aij映射为bi′j′，映射关系为：•另一种压缩方法是将带状矩阵压缩到向量C中去，按以行为主序，顺序的存储其非零元素，如下图所示，按其压缩规律，找到相应的映象函数。如当w=3时，映象函数为：k=2*i+j-35.3稀疏矩阵§稀疏矩阵的三元组表存储§稀疏矩阵的十字链表存储假设m行n列的矩阵含t个非零元素，则称为稀疏因子。通常认为0.05的矩阵为稀疏矩阵。nmt何谓稀疏矩阵？0200000000000210010070003以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题:1)零值元素占了很大空间;2)计算中进行了很多和零值的运算，如是除法，还需判别除数是否为零。1)尽可能少存或不存零值元素；解决问题的原则:2)尽可能减少没有实际意义的运算；3)操作方便。即：能尽可能快地找到与下标值(i，j)对应的元素；能尽可能快地找到同一行或同一列的非零值元素。2)特殊矩阵非零元素在矩阵中的分布有一定规则例如:三角矩阵对角矩阵1)随机稀疏矩阵非零元素在矩阵中随机出现有两类稀疏矩阵：5.3.1稀疏矩阵的三元组表存储§将三元组按行优先的顺序，同一行中列号从小到大的规律排列成一个线性表，称为三元组表，采用顺序存储方法存储该表。如图(a)稀疏矩阵对应的三元组表为图(b)。#defineSMAX1024/*一个足够大的数*/typedefstruct{inti,j;/*非零元素的行、列*/datatypev;/*非零元素值*/}SPNode;/*三元组类型*/typedefstruct{intmu,nu,tu;/*矩阵的行、列及非零元素的个数*/SPNodedata[SMAX];/*三元组表*/}SPMatrix;/*三元组表的存储类型*/这样的存储方法确实