《数据结构》数组和广义表.ppt

第5章 数组和广义表,5.1 数组的定义与运算 5.2 数组的顺序存储结构 5.3 矩阵的压缩存储 5.4 广义表 习题,5.1 数组的定义与运算,数组定义：类似于线性表，一个两维数组的逻辑结构可形式地表示为 2_Array=(D,R) 其中D=aij|i=0,1,m-1,j=0,1,n-1，aij是同类型数据元素的集合。 R=ROW,COL是数据元素上关系的集合。 ROW=|0im-1,0jn-2每一行上的列关系。 COL=|0im-2,0jn-1每一个列上的行关系。 行列关系跟线性表已经大不相同了,见图5.1所示。,a01 a02 a0n-1 a11 a12 a1n-1 am-11 am-12 am-1n-1 图5.1 二维数组元素关系 二维数组中的每一个元素aij都受到两个关系的约束：ROW(行关系)和COL(列关系)。aij+1是aij在行关系中的直接后续元素；而ai+1j是aij在列关系中的直接后续元素。和线性表一样，所有的数据元素属于同一数据类型。每个数据元素对应于一组下标(i,j)。将这个概念依次类推，可以写出n维数组的逻辑结构，但最常用的是二维数组。,也可以从另一个角度来定义二维数组，即将二维数组看成这样一个线性表：它的每一个数据元素是一个线性表(一维数组)。例如，图5.1所示的是一个二维数组，以m行n列的矩阵形式表示。它可以看成是一个线性表： A =(0 ,1 ,2 ,3 ,P) (p=m-1或n-1) 其中每一个数据元素j 是一个列向量的线性表 j =(a0j ,a1j ,a2j ,am-1j) 或者i 是一个行向量的线性表： i =(ai0 ,ai1 ,ai2 ,ain-1) 这种定义二维数组的方法也可以推广到n维数组，即认为n维数组是一个线性表，它的每一个数据元素是一个n-1维数组。 在数组结构最常用的操作：给定数组的下标i，对相应元素ai作取数、赋值的操作，操作方法根据其存储结构决定。,5.2 数组的顺序存储结构,由于数组一般不作插入或删除操作，也就是说，一旦建立了数组，则结构中的数据元素个数和元素之间的关系就不再发生变动，因此，采用顺序存储结构表示数组。 顺序结构即是用一组连续的存储单元来存放数组结构。内存地址是一维的，而数组结构可能是多维的。如何将多维的数组挤入一维的地址中，就有了策略问题： 按行序为主序(row major order)。首先，存放数组的第一行，然后，按顺序存放数组的各行； 按列序为主序(column major order)。首先，存放数组的第一列，然后，按顺序存放数组的各列， 如图5.2所示。大多数程序设计语言是按行主序来排列数组元素的，但列主序也是常见的。,(a)二维数组 (b)行序 (c)列序,图5.2 二维数组的两种存储方式,数组的顺序存储方式，给对数组元素的随机存取带来方便。因为，数组是同类型数据元素的集合，所以，每一个数据元素所占用的内存空间的单元数是相同的，故只要给出首地址，可以使用统一的地址公式，求出数组中任意元素的地址。这里以二维数组的行主序为例，讨论数组元素的地址计算方法。 二维数组aij(mn) LOC(i,j)=LOC(0,0)+(in+j)s (0im-1, 0jn-1) 其中，s是每个数据元素所占存储单元的个数。 可将二维数组的元素想象为一个一维数组，大小为p，则推出三维数组的地址计算方法。 三维数组aijk(mnp)： LOC(i,j,k)=LOC(0,0,0)+(in+j)sp+ks LOC(i,j,k)=LOC(0,0,0)+(inp+jp+k)s (0im-1, 0jn-1，0kp-1) 可将概念依次类推，可以写出n维数组地址计算方法。,5.3 矩阵的压缩存储,在工程应用中，矩阵有着重要的作用。许多实际问题的解决需要大量数据的综合计算，而这些大量数据之间总是表现出二维数组的逻辑结构。而这种二维数组结构在数学上称为矩阵。 为了使矩阵的各种运算能有效地进行，必须在算法的空间和时间复杂度上下功夫。首先我们考虑如何减少空间复杂度，即找一种高效的存储方法，再在相应的存储结构上找高效的算法。许多矩阵的数据分布是有特征的，那就要利用这种特征，尽量减少数据的存储量。,5.3.1 特殊矩阵 a.对称矩阵 定义：若有一个n阶矩阵A中的元素满足下述性质 aij=aji 1i,jn 则称为n阶对称矩阵。对称矩阵可以只给每一对对称元素分配一个存储空间，则可将nn的二维矩阵，压缩存储到n(n+1)/2个元的空间中。在这里讨论以行序为主序存储其下三角(包括对角线)中的对称矩阵元素。假设以一维数组sn(n+1)/2作为n阶对称矩阵A的存储结构，数组元素sk于矩阵元素aij之间转换公式如下。,存储示意： 对于任意给出的数组下标(i,j)，均可以在sa中找到 矩阵元素aij，反之，对所有的k=1,2,n(n+1)/2,都能确定sak中的矩阵元素在矩阵中的位置(i,j)。由此，称san(n+1)/2为n阶对称矩阵A的压缩存储,如图5.3所示。,图5.3 对称矩阵的压缩存储,运算 算法5.1 压缩存储的对称矩阵中的取值算法。 /* 取对称矩阵s中第i行第j列的元素 */ int Matrix_Get(int s,int i,int j) if(i=j) return(si*(i+1)/2+j); else return(sj*(j+1)/2+i); 算法5.2 压缩存储的对称矩阵中的赋值算法。 void Matrix_Set(int s,int i,int j,int value) if(i=j) si*(i+1)/2+j=value; else sj*(j+1)/2+i=value; ,b.三角矩阵 上述的这种压缩存储的方法同样也适用于三角矩阵。下(上)三角矩阵是指矩阵的主对角线以上(下)的元素均为0或某个常数c的n阶矩阵。例如，上三角矩阵:,只要存储其上三角中元素即可，若下三角不为零，则再加一个存储常数c的存储空间。,算法5.3 压缩存储的上三角矩阵中的取值算法。 int Matrix_Get(int s,int i,int j) if(ij) return(0); else return(sj*(j+1)/2+i); 算法5.4 压缩存储的上三角矩阵中的赋值算法。 void Matrix_Set(int s,int i,int j,int value) if(i=j) sj*(j+1)/2+i=value; ,c. 对角矩阵 在这种矩阵中，所有非0元素都集中在以主对角线为中心的带状区域。即除了主对角线上和直接在对角线上、下方若干条对角线上的元素之外，所有其它的元素皆为0。也称为半带宽为d的带状矩阵(带宽为2d+1)，d为直接在对角线上、下方不为0的对角线数。当对角矩阵带宽为d时，其非零元素个数如下：,所以，对于n阶2d+1对角矩阵，只需存放对角区域内n(2d+1)-d(d+1)个非零元素。但为计算方便，认为每一行都有2d+1个元素，若少于2d+1个元素，则添0补足。这样用s(2d+1)n作为存储结构，扩展了上下二个三角区域，多了(1+d)d个单元。例如，当d=1，n=5，n阶矩阵为,其存储形式为,数组元素sk于矩阵元素aij之间转换公式如下： k=i(2d+1)+d+(j-i) 如a23 所对应sk,k=2(2d+1)+d+(3-2)=8 算法5.5 压缩存储的2d+1对角矩阵中的取值算法。 int Matrix_Get(int s,int d,int i,int j) if(abs(i-j)=d) return(si(2d+1)+d+(j-i); return(0); 算法5.6 压缩存储的2d+1对角矩阵中的赋值算法。 void Matrix_Set(int s,int d,int i,int j,int value) if(abs(i-j)=d) si(2d+1)+d+(j-i)=value; ,5.3.2 稀疏矩阵 定义:矩阵中大量的元素值为0，且非0元素的分布无规律，称为稀疏矩阵。图5.4的矩阵A是67的矩阵，而B是76的矩阵。有42个元素(只有8个非零元素)，且分布无规律可循，所以称它们为稀疏矩阵。 存储方法：只存储非零元素。用一个三元组(i,j,aij)记下非零元素的值，以及所在的行和列的位置(i,j) 。矩阵中所有非零元素的三元组构成一个线性表。,对于三元组的线性表可以采用两种存储方法。 (1)三元组表的顺序存储结构 采用顺序结构来表示三元组的线性表，则可以得到稀疏矩阵的一种压缩存储方式，即三元组表。用C语言描述的具体结构如下： typedef struct /* 三元组结构 */ int i,j; /* 行号、列号 */ int value; /* 元素值 */ TriNode; typedef struct /* 三元组顺序表结构(按行主序) */ int mu,nu,tu; /* 矩阵的行数、列数、非0元素个数 */ TriNode dataMAXSIZE; /* 所有三元组的存储空间 */ TriList;,例如，在图5.4中的稀疏矩阵A和B的三元组表Ma.data 和Mb.data ，如图5.5所示，所有三元组按行主序排列，三元组的排序以行序为主序。,矩阵A(Ma.data) 矩阵B(Mb.data),图5.5稀疏矩阵A和B的三元组表,面讨论在这种存储结构下的运算。 转置运算是一种最常用的矩阵运算。对于一个mn的矩阵A，它的转置矩阵B是一个nm的矩阵,并且有A(i,j)等于B(j,i)，0im-1，0jn-1。例如图5.4中的矩阵A和B互为转置矩阵。显然，一个稀疏矩阵的转置任然是一个稀疏矩阵，从分析图5.5可知，只要做到： (a)将矩阵的行列值交换。 (b)将每一个三元组的i和j相互调换。 (c)重排三元组之间的次序。 便可以实现矩阵的转置，前两条容易实现，关键是第三条。即如何使Mb.data中的三元组是以B的行(A的列)为主序依次排列的。,转置后重排三元组次序可以有两种处理方法： 按照矩阵A的列序来进行转置。 即对Ma.data按列顺序扫描，首先，找出第一列的所有元素，交换i和j后，依次写入Mb.data 中；然后，找出第二列所有元素，交换i和j后，也依次写入Mb.data中；重复上述过程，按列顺序依次取出Ma.data中所有元素，可以得到按行顺序存放的矩阵A的转置矩阵B所对应的三元组表。具体算法如下：,算法5.7 三元组中，按照A的列序来进行转置。 /* 因为C语言参数的传递方式位单向值传递，所以Mb应为指针类型 */ void TriList_Transpose(TriList Ma, TriList *Mb) int k,col,i; Mb-mu=Ma.nu; Mb-nu=Ma.mu; Mb-tu=Ma.tu; if(Mb-tu=0) return; for(k=0,col=0; coldatak.i=Ma.datai.j; Mb-datak.j=Ma.datai.i; Mb-datak.value=Ma.datai.value; k+; /* k为Mb中下一个三元组的位置 */ ,快速转置运算。 快速转置运算以A矩阵的三元组表为中心，依次取出Ma.data中每一个三元组，交换行列后，找到其在Mb.data中的合适位置，直接写入。 这样操作的基础是：需要确定A矩阵中每列(B中每行)的非零元素个数，也就确定了A中每列第一个非零元素在Mb.data中的存放位置。为此，需要两个辅助数组num和pos，numcol(0coln-1)表示A中第col列非零元素的个数。poscol(0coln-1)表示A中第col列非零元素在mb中的位置。显然有： pos0=1 poscol=poscol-1+numcol-1,例如，对图5.4中的稀疏矩阵A，num和pos的值如表5.1所示。即第col列第一个非零元素的位置是：第col-1列的第一个非零元素位置与第col-1列的非零元素个数之和。这样每从Ma.data取出一个元素Ma.datai，根据col= Ma.datai.j，其在Mb.data中的位置是k=poscol，并将poscol加1，当再次取到col列元素时，它在Mb.data中的位置是k+1，恰好是排在该列上一个元素之后，满足矩阵B行序的要求。快速转置运算如下：,表5.1 矩阵A的辅助数组的值,算法5.8 三元组中，快速转置算法。 void TriList_FastTranspose(TriList Ma, TriList *Mb) int i,j,col,k,numMAX,posMAX; Mb-mu=Ma.nu; Mb-nu=Ma.mu; Mb-tu=Ma.tu; if(Mb-tu=0) return; for(i=0; idatak.i=Ma.datai.j; Mb-datak.j=Ma.datai.i; Mb-datak.value=Ma.datai.value; poscol+; ,(2)十字链表的存储结构 以三元组表示的稀疏矩阵，在运算中，若非零元素的位置发生变化，会引起数组元素的频繁移动。例如，要做运算A=A+B，即将矩阵B加到矩阵A上，则会产生大量的数据元素移动。此时，采用十字链表结构将更恰当。,例如，有一个44稀疏矩阵A ,其所对应的十字链表如图5.6所示在十字链表中，稀疏矩阵中的每一个非零元素可以用一个结点表示，每一个结点中有五个域：行,列, 值, 下指针,右指针.,说明：行row,列col,值value，表示一个非零元素，下指针(down)指向同一列中下一个非零元素，右指针(right)指向同一行中下一个非零元素。稀疏矩阵中同一行的非零元素由right,链接成一个带有头结点的行循环链表。同一列的非零元素由down，链接成一个带有头结点的列循环链表。因此,每个非零元素aij既是第i行循环链表中的一个结点，又是第j列循环链表中的一个结点。这样恰好构成一个十字，所以称为十字链表。结点的数据结构如下： struct node int row,col,val； struct node *down,*right； ； typedef struct node NODE；,另外：在表示十字链表的表头结点中，row、col和value分别存放矩阵的行数、列数和非零元素个数；right和down分别指向行(列)循环链表的表头结点所构成的链表。在行(列)循环链表的表头结点中，row、col和value皆为0，行循环链表的表头结点right域指向该行的第一个非零元素的结点，而down域为NULL；列循环链表的表头结点down域指向该列的第一个非零元素的结点，而right域为NULL。 建立和输出十字链表的算法如下： 算法5.9 建立十字链表算法 NODE * create() NODE *head,*new,*pre,*p,*row_p,*col_p; int i,count; head=(NODE *)malloc(sizeof(NODE); scanf(“%d,%d,%dn”,/* 读行列数,非零元素 */ /*接下页,/* 行头结点用down域和表头结点组成循环链表 */ for(pre=head,i=0;irow;i+) p=(NODE *)malloc(sizeof(NODE); p-val=p-row=p-col=0; p-right=p; pre-down=p; pre=p; p-down=head; /* 列头结点用right域和表头结点组成循环链表 */ for(pre=head,i=0;icol;i+) p=(NODE *)malloc(sizeof(NODE); p-val=p-row=p-col=0; p-down=p; pre-right=p; pre=p; p-right=head; count=0; /*接下页,while(countval) count+; new=(NODE *)malloc(sizeof(NODE); scanf(“%d,%d,%dn“, ,算法5.10 输出行主序的十字链表算法。 void print(NODE *head) /* 按行主序输出 */ NODE *row_p,*p; printf(“%d,%d,%dn“,head-row,head-col,head-val); row_p=head-down; while(row_p!=head) p=row_p; while(p-right!=row_p) p=p-right; printf(“%d,%d,%dn“,p-row,p-col,p-val); row_p=row_p-down; ,5.4 广义表,如果将线性表的定义推广，即不限制线性表中每一个元素都是一个结点，那么所得到的表就是一个广义表。 5.4.1 广义表定义 广义表是n个元素的有限序列。广义表一般记作 LS=(d0,d1,dn-1) 其中，LS是广义表的名称，n为表长度。di可为基本数据元素，也可为广义表，分别称为广义表的单元素和子表。习惯上，用大写字母表示广义表的名称，用小写字母表示单元素。当广义表非空时，称第一个元素d0为LS表头(head)，其余元素组成的表(d1,dn-1)为表尾(tail)。下面是几个广义表的实例。,实例： (1) A=()，A是一个空广义表。 (2) B=(a,(b,c,d)，B包含两个元素，其中一个是单元素a，另一个是子表(b,c,d)。 (3) C=(e)，C只有一个单元素e。 (4) D=(A,B,C,f)，D包含四个元素，前三个是子表，第四个是单元素。 (5) E=(a,E)，这是一个递归表，包含两个元素，一个是单元素a，另一个是子表，但该子表是其自身。所以，E相当于一个无限的广义表 (a,(a,(a,)。 从上面的定义和实例中可知： (1) 广义表的元素可以是子表，而子表中元素还可以是个子表。 (2) 一个广义表可以为其它所共享。 (3) 广义表可以是一个递归表。,另外，广义表的元素之间除了存在次序关系外，还存在层次关系，如图5.7表示了这种关系。在图中以圆圈表示广义表，方块表示单元素。,图5.7广义表的图形表示,运算： 和线性表类似，可以对广义表的操作有查询、插入和删除等。但广义表还有两个特殊的操作：取广义表的表头HEAD(LS)和取广义表的表尾TAIL(LS)。 根据前面对表头和表尾的定义可知：任何一个非空广义表其表头可以是单元素，也可以是子表，而其表尾必定为一个广义表(子表)。例如，广义表为前面所定义的A到E表，HEAD和TAIL运算有： HEAD(B)=a， TAIL(B)=(b,c,d), HEAD(C)=e， TAIL(C)=(), HEAD(D)=A， TAIL(D)=(B,C,f)， 另外运算也可以嵌套，如： HEAD(TAIL(B)=b， TAIL(TAIL(B)=(c,d)。,5.4.2 广义表的存储结构 由于广义表中数据元素可以具有不同结构，通常采用链表存储结构，每一个数据元素可用一个结点(可以是子表或单元素)。表示子表的表结点与表示单元素的数据元素结点之间是有差异的，以下是一种常用的存储结构。 struct node /* 表结点 */ int tag; /* =1标识子表结点 */ struct node *child； /* 指向该子表的指针 */ struct node *next； /* 指向下个元素的指针 */ ； struct node /* 数据元素结点 */ int tag; /* =0标识原子结点 */ int val； /* 值域 */ struct node *next； /* 指向下个元素的指针 */ ；,实际存储结构：为了便于处理，将val域和child域以联合的方式存储，表结点和数据结点合二为一，C语言定义的广义表结点结构如下： struct glnode int tag; /* =1标识子表结点，=0标识原子结点 */ union struct glnode *child； /* 表结点中的子表指针域 */ int val; /* 原子结点中的系数域 */ content struct glnode *next； /* 指向下个元素的指针 */ ； typedef struct glnode GLNode; 注意：在该结构中，tag=1表示该结点是表结点，联合中取child域，而tag=0表示该结点是数据结点，在联合中取val域。,上一节所举广义表例子，它们的存储结构如图5.8所示。,图5.8 广义表的存储结构,5.4.3 广义表的基本操作 对广义表基本操作有： (1)建表。 (2)撤销表。 (3)复制(赋值)表。 (4)插入元素作为第i个元素。 (5)删除第i个元素。 (6)求表深度；等。 下面讨论求表深度和建表算法。 广义表的深度定义为表中括号的重数，是广义表的一种度量。广义表中数据元素的最大层次数为表的深度，