第5章 数组和广义表.ppt

《第5章 数组和广义表.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第5章数组和广义表内容提要：本章主要内容是：数组的定义、运算和存储结构；特殊矩阵和稀疏矩阵的压缩存储方法；广义表的存储结构及运算。5.1数组的定义数组（array）是n（n>1）个相同类型数据的有序组合，数组中的数据是按顺序存储在一块地址连续的存储单元中。数组中的每一个数据通常称为数组元素，数组元素用下标区分，其中下标的个数由数组的维数决定。5.1数组的定义一个二维数组的逻辑结构可以定义成如下形式：Array_2=(D,R)其中D={aij

2、i=c1,c1+1,…，d1,j=c2,c2+1,…,d2,aij∈D0}R={ROW,COL}ROW={

3、,ai,j+1>

4、c1≤i≤d1,c2≤j≤d2-1,aij,ai,j+1∈D}COL={

5、c1≤i≤d1-1,c2≤j≤d2,aij,ai+1,j∈D}5.1数组的定义在C语言中，一个二维数组类型可以定义为其数据元素是一维数组类型的一维数组类型，即下面的二维数组类型的定义：typedefElemTypeArray2[m][n];相当于下面两条语句的定义：typedefElemTypeArray1[n];typedefArray1Array2[m];5.2数组的顺序表示和实现数组在计算机中是采用顺序存储结构来实现数组元素的存放，即

6、在计算机内存中采用一片连续的存储单元来存放数组元素。5.2数组的顺序表示和实现对于二维数组，有两种排列形式，一种是以行序为主（RowMajorOrder），即先存储第一行，然后是第二行，依次向下存储，直到最后一行的最后一个元素；另一种是以列序为主（ColumnMajorOrder），即先存储第一列，然后是第二列，依次向下直到最后一列的最后一个元素。高级语言中，PASCAL、COBOL、C、PL/1、BASIC等语言均是采用以行序为主的存储形式，而高级语言FORTORN是采用以列序为主的存储形式。5.2数组的顺序表示和实现由于数组在内存中是按顺序存放的，因

7、此就很容易根据一个数组元素的地址求出其他数组元素的地址。例如，只要知道了第一个元素的存储地址（即基地址）、数组维数、排列顺序和每个元素所占存储单元数，就可以计算出数组中其他任意一个数组元素的存储地址。5.2数组的顺序表示和实现二维数组元素地址的计算元素aij的地址LOC(i,j)为：以行序为主LOC(i,j)=LOC(0,0)+(i*n+j)*L以列序为主LOC(i,j)=LOC(0,0)+(j*m+i)*L其中，LOC(0,0)为元素a00的地址，L为每个数据元素所占的存储单元。5.2数组的顺序表示和实现n维数组元素地址的计算元素a[j1][j2]…[

8、jn]的存储位置为：LOC(j1,j2,…,jn)=LOC(0,0,…,0)+(d2*d3*…*dn*j1+d3*d4*…*dn*j2+…+dn*jn-1+jn)*L=LOC(0,0,…,0)+5.3矩阵的压缩存储矩阵在科学计算和工程应用中广泛使用。然而在某些特殊情况下，经常会出现一些阶数很高的矩阵，其中含有很多值相同的元素或者零元素。为了节省存储空间，经常需要对这些矩阵进行压缩存储。所谓压缩存储是对矩阵中值相同的元素只分配一个存储空间，而对零元素则不分配空间。5.3矩阵的压缩存储对于需要压缩存储的矩阵可以分为特殊矩阵和稀疏矩阵。对那些具有相同值元素或零

9、元素在矩阵中分布具有一定规律的矩阵，我们称之为特殊矩阵（specialmatrices）；而对于那些零元素数目远远多于非零元素数目，并且非零元素的分布没有规律的矩阵称为稀疏矩阵。下面我们就对这两种矩阵及其压缩存储进行介绍。5.3.1特殊矩阵在一个n阶方阵a中，若元素满足如下性质：aij=aji(0≤i,j≤n-1)则称A为n阶对称矩阵。对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。5.3.1特殊矩阵按“行优先顺序”存储主对角线（包括对角线）以下的元素，其存储形式

10、如图所示：15137a1150800a21a2218926a31a32a3330251………………..70613an1an2an3…ann在下三角矩阵中，第i行恰有i个元素，元素总数为：n(n+1)/2.因此，我们可以将这些元素存放在一个向量sa[0..n(n+1)/2-1]中5.3.1特殊矩阵sa[k]与a[i][j])的对应关系：i*(i-1)/2+j-1当i≥jk=j*(j-1)/2+i-1当i

11、三角矩阵又可分为上三角矩阵和下三角矩阵。上三角矩阵是指矩阵的下三角（除对角线以外