数据结构-第5章-数组和广义表

第5章数组和广义表

内容提要：

本章主要内容是：数组的类型定义和存储结构；特殊矩阵和稀疏矩阵的压缩存储方法；广义表的逻辑结构和存储结构。重点要求掌握数组转置等基本运算、稀疏矩阵的三元组形式的顺序表示和十字链表的表示方法、用三元组的形式来实现稀疏矩阵的转置运算。1一维数组具有线性表的结构，但操作简单，一般不进行插入和删除操作，只定义给定下标读取元素和修改元素的操作二维数组中，每个数据元素对应一对数组下标，在行方向上和列方向上都存在一个线性关系，即存在两个前驱（前件）和两个后继（后件）。也可看作是以线性表为数据元素的线性表。n维数组中，每个数据元素对应n个下标，受n个关系的制约，其中任一个关系都是线性关系。可看作是数据元素为n-1维数组的一维数组。因此，多维数组和广义表是对线性表的扩展：线性表中的数据元素本身又是一个多层次的线性表。25.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5.4广义表的定义35.1数组的定义

数组（array）是n（n>1）个相同类型数据的有序组合，数组中的数据是按顺序存储在一块地址连续的存储单元中。数组中的每一个数据通常称为数组元素，数组元素用下标区分，其中下标的个数由数组的维数决定。

45.1数组的定义一个二维数组的逻辑结构可以定义成如下形式：Array_2=(D,R)其中D={aij

|i=c1,c1+1,…，d1,j=c2,c2+1,…,d2,aij∈D0} R={ROW,COL} ROW={<aij,ai,j+1>|c1≤i≤d1,c2≤j≤d2-1,aij,ai,j+1∈D} COL={<aij,ai+1,j>|c1≤i≤d1-1,c2≤j≤d2,aij,ai+1,j∈D}55.1数组的定义在C语言中，一个二维数组类型可以定义为其数据元素是一维数组类型的一维数组类型，即下面的二维数组类型的定义：

typedef

ElemTypeArray2[m][n];

相当于下面两条语句的定义：

typedef

ElemTypeArray1[n];

typedefArray1Array2[m];65.2数组的顺序表示和实现

数组在计算机中是采用顺序存储结构来实现数组元素的存放，即在计算机内存中采用一片连续的存储单元来存放数组元素。

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

85.2数组的顺序表示和实现由于数组在内存中是按顺序存放的，因此就很容易根据一个数组元素的地址求出其他数组元素的地址。例如，只要知道了第一个元素的存储地址（即基地址）、数组维数、排列顺序和每个元素所占存储单元数，就可以计算出数组中其他任意一个数组元素的存储地址。

95.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为每个数据元素所占的存储单元。105.2数组的顺序表示和实现n维数组元素地址的计算

元素a[j1][j2]…[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)+115.3矩阵的压缩存储

矩阵在科学计算和工程应用中广泛使用。然而在某些特殊情况下，经常会出现一些阶数很高的矩阵，其中含有很多值相同的元素或者零元素。为了节省存储空间，经常需要对这些矩阵进行压缩存储。所谓压缩存储是对矩阵中值相同的元素只分配一个存储空间，而对零元素则不分配空间。

125.3矩阵的压缩存储对于需要压缩存储的矩阵可以分为特殊矩阵和稀疏矩阵。对那些具有相同值元素或零元素在矩阵中分布具有一定规律的矩阵，我们称之为特殊矩阵（specialmatrices）；而对于那些零元素数目远远多于非零元素数目，并且非零元素的分布没有规律的矩阵称为稀疏矩阵。下面我们就对这两种矩阵及其压缩存储进行介绍。

135.3.1特殊矩阵在一个n阶方阵a中，若元素满足如下性质：aij=aji (0≤i,j≤n-1)

则称A为n阶对称矩阵。对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。145.3.1特殊矩阵按“行优先顺序”存储主对角线（包括对角线）以下的元素，其存储形式如图所示：

15137a11

50800a21a22

18926a31a32a33

30251………………..

70613an1an2an3…ann

在下三角矩阵中，第i行恰有i个元素，元素总数为：n(n+1)/2.因此，我们可以将这些元素存放在一个向量sa[0..n(n+1)/2-1]中155.3.1特殊矩阵

sa[k]与a[i][j])的对应关系：

i*(i-1)/2+j-1当i≥j k=j*(j-1)/2+i-1当i<ji,j=1,2,…,n;k=0,1,…,n(n+1)/2-1思考：给定一个k,如何求i和j？ 165.3.1特殊矩阵除了对称矩阵以外，三角矩阵也属于特殊矩阵，三角矩阵又可分为上三角矩阵和下三角矩阵。上三角矩阵是指矩阵的下三角（除对角线以外）中的元素均为常数或零的矩阵，而下三角矩阵则与上三角矩阵相反。三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到向量sa[0..n(n+1)/2]中，其中c存放在向量的最后一个分量中。175.3.1特殊矩阵上三角矩阵

185.3.1特殊矩阵下三角矩阵

195.3.2稀疏矩阵在通常的数值处理过程中，经常遇到矩阵非零元素较少，但又没有一定的分布规律，这种情况称为稀疏矩阵。人们无法给出稀疏矩阵的确切定义，一般都是凭一个人的直觉来理解这个概念，简单说，设矩阵A中有s个非零元素，若s远远小于矩阵元素的总数（即s<<m×n），则称A为稀疏矩阵。205.3.2稀疏矩阵稀疏矩阵M215.3.2稀疏矩阵由于稀疏矩阵中非零元素较少，零元素较多，因此可以采用只存储非零元素的方法来进行压缩存储。又由于非零元素分布没有规律，所以在进行压缩存储的时候需要在存储非零元素值的同时还要存储非零元素在矩阵中的位置，即非零元素所在的行和列号。也就是在存储某个元素aij值的同时，还需要存储该元素所在的行号i和它的列号j，这样就构称了一个三元组（

i,j,aij

）的形式。

225.3.2稀疏矩阵一个三元组表能够唯一确定一个矩阵中的非零元素，例如下面的三元组是对前面矩阵M中非零元的表示。（0，0，2），（0，4，6），（0，7，7），（1，2，1），（2，2，－2），（2，6，3），（3，5，8），（4，3，5），（5，1，9）

以上是按照行号顺序，将三元组9个非零元素按顺序进行排列（当然也可以按照列号的顺序进行排列），如果再加上一个表示矩阵行数、列数和总的非零元素数目的特殊三元组（6，8，9），就可以唯一的确定一个矩阵。

231.三元组顺序表用顺序存储结构表示三元组表（TripleTable），来实现对稀疏矩阵的一种压缩存储形式，就称为三元组顺序表，简称三元组表。#defineMAXSIZE10000typedef

struct{typedef

struct{Tripledata[MAXSIZE+1];

inti,j;int

mu,nu,tu;

ElemTypee;}TsMatrix;}Triple;

241.三元组顺序表下面以矩阵的转置为例，说明在这种压缩存储结构上如何实现矩阵的运算。一个m×n的矩阵A，它的转置B是一个n×m的矩阵，且a[i][j]=b[j][i]，0≦i≦m，0≦j≦n，即A的行是B的列，A的列是B的行。将A转置为B，就是将A的三元组表a.data置换为表B的三元组表b.data.

由于A的列是B的行，因此，按a.data的列序转置，所得到的转置矩阵B的三元组表b.data必定是按行优先存放的。251.三元组顺序表ijv121213931-3361443245218611564-7ijv13-3161521122518319342446-76314其基本思想是：对A中的每一列col(0≦col≦n-1)，通过从头至尾扫描三元表a.data，找出所有列号等于col的那些三元组，将它们的行号和列号互换后依次放入b.data中，即可得到B的按行优先的压缩存储表示。a.datab.data261.三元组顺序表StatusTransposeSMatrix(TSMatrixM,TSMatrixT){

T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){q=1;

for(col=1;col<=M.nu;++col)for(p=1;p<=M.tu;++p)if(M.data[p].j==col){T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;++q;}}returnOK;}27快速转置算法方法：按a.data中三元组的次序进行转置，并将转置后的三元组置入b中恰当的位置。建立辅助数组num和cpot，num[col]表示矩阵第col列中非零元的个数，cpot[col]指示第col列的第一个非零元素在b.data中的恰当位置。按行扫描矩阵三元组表，根据某项的列号，确定它转置后的行号，查cpot表，按查到的位置直接将该项存入转置三元组表中。转置时间复杂度为

O(nu+tu+nu+tu)=O(tu)。若矩阵有200列，10000个非零元素，总共需10000次处理。28表5.1(教材99页)cpot[1]=1cpot[col]=cpot[col-1]+num[col-1]29稀疏矩阵的快速转置(算法5.2)StatusFastTransposeSMatrix(TSMatrix

M,TSMatrix&T){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){for(col=1;col<=M.nu;++col)num[col]=0; for(t=1;t<=M.tu;++t)++num[M.data[t].j]; cpot[1]=1; for(col=2;col<=M.nu;++col)

cpot[col]=cpot[col-1]+num[col-1];for(p=1;p<=M.tu;++p){ col=M.data[p].j; q=cpot[col];

T.data[q].i=M.data[p].j; T.data[q].j=M.data[p].i;

T.data[q].e=M.data[p].e; ++cpot[col];} }returnOK;}302.十字链表当矩阵中非零元素的个数和位置经过运算后变化较大时，就不宜采用顺序存储结构，而应采用链式存储结构来表示三元组。稀疏矩阵的链接表示采用十字链表：行链表与列链表十字交叉。行链表与列链表都是带表头结点的单链表。用表头结点表征是第几行，第几列。31元素结点(有5个域)right——指向同一行中下一个非零元素的指针（向右域）down——指向同一列中下一个非零元素的指针（向下域）表头结点行表头结点列表头结点next用于表示头结点的链接rowcolvaldownrightcol=0nextrightrow=0nextdown32由于行、列表头结点互相不冲突，所以可以合并起来：总表头结点：row=0col=0nextdownrightrowcolnext33稀疏矩阵的十字链表表示的示例见104页的图5.6。需要辅助结点作链表的表头，同时每个结点要增加两个指针域，所以只有在矩阵较大和较稀疏时才能起到节省空间的效果。分别用两个一维数组存储行链表的头指针和列链表的头指针，可加快访问速度。34十字链表的类型定义typedef

struct

OLNode{//元素结点

int

i,j;//非零元的行和列下标

ElemTypee;

struct

OLNode*right,*down;

//该非零元所在行表和列表的后继链域

}OLNode,*OLink;typedef

struct{

OLink*rhead,*chead;//行和列链表头指针数组

int

mu,nu,tu;}CrossList;35十字链表的建立(算法5.4)自学365.4广义表的定义

广义表（GeneralizedLists）是线性表的推广，又简称表（Lists）。广义表是n(n>=0)个元素a1,a2,a3,…,an的有限序列，其中ai或者是原子项，或者是一个广义表。通常记作LS=（a1,a2,a3,…,an)LS是广义表的名字，n为它的长度。若ai是广义表，则称它为LS