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

1、第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-1a11 a12 a1n-1 am-11am-12am-1n-1 图5.1

2、二维数组元素关系 二维数组中的每一个元素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其中每一个数据元

3、素j 是一个列向量的线性表 j =a0j ,a1j ,a2j ,am-1j或者i 是一个行向量的线性表： i =ai0 ,ai1 ,ai2 ,ain-1 这种定义二维数组的方法也可以推广到n维数组，即认为n维数组是一个线性表，它的每一个数据元素是一个n-1维数组。 在数组构造最常用的操作：给定数组的下标i，对相应元素ai作取数、赋值的操作，操作方法根据其存储构造决定。5.2 数组的顺序存储构造 由于数组一般不作插入或删除操作，也就是说，一旦建立了数组，那么构造中的数据元素个数和元素之间的关系就不再发生变动，因此，采用顺序存储构造表示数组。 顺序构造即是用一组连续的存储单元来存放数组构造。内存地

4、址是一维的，而数组构造可能是多维的。如何将多维的数组挤入一维的地址中，就有了策略问题： 按行序为主序row major order。首先，存放数组的第一行，然后，按顺序存放数组的各行； 按列序为主序column major order。首先，存放数组的第一列，然后，按顺序存放数组的各列， 如图5.2所示。大多数程序设计语言是按行主序来排列数组元素的，但列主序也是常见的。 a二维数组 b行序 c列序图5.2 二维数组的两种存储方式 数组的顺序存储方式，给对数组元素的随机存取带来方便。因为，数组是同类型数据元素的集合，所以，每一个数据元素所占用的内存空间的单元数是一样的，故只要给出首地址，可以使用

5、统一的地址公式，求出数组中任意元素的地址。这里以二维数组的行主序为例，讨论数组元素的地址计算方法。二维数组aijmn LOCi,j=LOC0,0+in+js 0im-1, 0jn-1 其中，s是每个数据元素所占存储单元的个数。 可将二维数组的元素想象为一个一维数组，大小为p，那么推出三维数组的地址计算方法。 三维数组aijkmnp： LOCi,j,k=LOC0,0,0+in+jsp+ks LOCi,j,k=LOC0,0,0+inp+jp+ks 0im-1, 0jn-1，0kp-1 可将概念依次类推，可以写出n维数组地址计算方法。 5.3 矩阵的压缩存储 在工程应用中，矩阵有着重要的作用。许多实

6、际问题的解决需要大量数据的综合计算，而这些大量数据之间总是表现出二维数组的逻辑构造。而这种二维数组构造在数学上称为矩阵。 为了使矩阵的各种运算能有效地进展，必须在算法的空间和时间复杂度上下功夫。首先我们考虑如何减少空间复杂度，即找一种高效的存储方法，再在相应的存储构造上找高效的算法。许多矩阵的数据分布是有特征的，那就要利用这种特征，尽量减少数据的存储量。 5.3.1 特殊矩阵 a.对称矩阵 定义：假设有一个n阶矩阵A中的元素满足下述性质 aij=aji 1i,jn那么称为n阶对称矩阵。对称矩阵可以只给每一对对称元素分配一个存储空间，那么可将nn的二维矩阵，压缩存储到nn+1/2个元的空间中。在

7、这里讨论以行序为主序存储其下三角包括对角线中的对称矩阵元素。假设以一维数组snn+1/2作为n阶对称矩阵A的存储构造，数组元素sk于矩阵元素aij之间转换公式如下。jiijjjijiik21)21()( 存储示意： 对于任意给出的数组下标i,j，均可以在sa中找到 矩阵元素aij，反之，对所有的k=1,2,nn+1/2,都能确定sak中的矩阵元素在矩阵中的位置i,j。由此，称sann+1/2为n阶对称矩阵A的压缩存储,如图5.3所示。 a00 a10 a11 an1 an-1n-1 k= 1 2 3nn+1/2-1图5.3 对称矩阵的压缩存储 运算算法5.1 压缩存储的对称矩阵中的取值算法。

8、/* 取对称矩阵s中第i行第j列的元素 */ int Matrix_Getint s,int i,int j ifi=j returnsi*i+1/2+j; else returnsj*j+1/2+i; 算法5.2 压缩存储的对称矩阵中的赋值算法。 void Matrix_Setint s,int i,int j,int value ifi=j si*i+1/2+j=value; else sj*j+1/2+i=value; b.三角矩阵 上述的这种压缩存储的方法同样也适用于三角矩阵。下上三角矩阵是指矩阵的主对角线以上下的元素均为0或某个常数c的n阶矩阵。例如，上三角矩阵: 只要存储其上三角中

9、元素即可，假设下三角不为零，只要存储其上三角中元素即可，假设下三角不为零，那么再加一个存储常数那么再加一个存储常数c的存储空间。的存储空间。 算法5.3 压缩存储的上三角矩阵中的取值算法。 int Matrix_Getint s,int i,int j ifij return0; else returnsj*j+1/2+i; 算法5.4 压缩存储的上三角矩阵中的赋值算法。 void Matrix_Setint s,int i,int j,int value ifi=j sj*j+1/2+i=value; c. 对角矩阵 在这种矩阵中，所有非0元素都集中在以主对角线为中心的带状区域。即除了主对角

10、线上和直接在对角线上、下方假设干条对角线上的元素之外，所有其它的元素皆为0。也称为半带宽为d的带状矩阵带宽为2d+1，d为直接在对角线上、下方不为0的对角线数。当对角矩阵带宽为d时，其非零元素个数如下：带宽非零元素个数d=0 d=1 d=2 d=3 d=dnn+2n-1n+2n-1+n-2n+2n-1+n-2+n-3n+2n-1+n-2+n-d=n+2n-1+n-dd/2=n+2n-1-dd=n+2nd-1d-dd=2d+1n-1+dd 所以，对于n阶2d+1对角矩阵，只需存放对角区域内n2d+1-dd+1个非零元素。但为计算方便，认为每一行都有2d+1个元素，假设少于2d+1个元素，那么添0

11、补足。这样用s2d+1n作为存储构造，扩展了上下二个三角区域，多了1+dd个单元。例如，当d=1，n=5，n阶矩阵为 0 a00 a01 a10 a11 a12 a21 a22 a23 a32 a33 a34 a43 a44 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14其存储形式为其存储形式为 数组元素sk于矩阵元素aij之间转换公式如下： k=i2d+1+d+j-i 如a23 所对应sk,k=22d+1+d+3-2=8算法5.5 压缩存储的2d+1对角矩阵中的取值算法。 int Matrix_Getint s,int d,int i,int j ifabsi-j=

12、d returnsi2d+1+d+j-i; return0; 算法5.6 压缩存储的2d+1对角矩阵中的赋值算法。 void Matrix_Setint s,int d,int i,int j,int value ifabsi-jmu=Ma.nu; Mb-nu=Ma.mu; Mb-tu=Ma.tu; ifMb-tu=0 return; fork=0,col=0; colMa.nu; col+ fori=0; idatak.i=Ma.datai.j; Mb-datak.j=Ma.datai.i; Mb-datak.value=Ma.datai.value; k+; /* k为Mb中下一个三元组的

13、位置 */ 快速转置运算。 快速转置运算以A矩阵的三元组表为中心，依次取出Ma.data中每一个三元组，交换行列后，找到其在Mb.data中的适宜位置，直接写入。 这样操作的根底是：需要确定A矩阵中每列B中每行的非零元素个数，也就确定了A中每列第一个非零元素在Mb.data中的存放位置。为此，需要两个辅助数组num和pos，numcol0coln-1表示A中第col列非零元素的个数。poscol0coln-1表示A中第col列非零元素在mb中的位置。显然有： pos0=1 poscol=poscol-1+numcol-1例如，对图5.4中的稀疏矩阵A，num和pos的值如表5.1所示。即第co

14、l列第一个非零元素的位置是：第col-1列的第一个非零元素位置与第col-1列的非零元素个数之和。这样每从Ma.data取出一个元素Ma.datai，根据col= Ma.datai.j，其在Mb.data中的位置是k=poscol，并将poscol加1，当再次取到col列元素时，它在Mb.data中的位置是k+1，恰好是排在该列上一个元素之后，满足矩阵B行序的要求。快速转置运算如下： Col 0 1 2 3 4 5 6numcol 2 2 2 1 0 1 0 poscol 0 2 4 6 7 7 8表表5.1 矩阵矩阵A的辅助数组的值的辅助数组的值 算法5.8 三元组中，快速转置算法。 voi

15、d TriList_FastTransposeTriList Ma, TriList *Mb int i,j,col,k,numMAX,posMAX; Mb-mu=Ma.nu; Mb-nu=Ma.mu; Mb-tu=Ma.tu; ifMb-tu=0 return; fori=0; iMa.nu; i+ numi=0; /*统计M中每列的三元组个数*/ fori=0; iMa.tu; i+ numMa.datai.j+; forpos0=0,col=1; colMa.nu; col+ /* 计算pos数组 */ poscol=poscol-1+numcol-1; fori=0; idatak.i

16、=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所示在十字链表所示在十字链表中，稀疏矩阵中的中，稀疏矩阵中的每一个非零元素可每一个非零元素可以用一个结点表示，以用一个结点表示

17、，每一个结点中有五每一个结点中有五个域：行个域：行,列列, 值值, 下下指针指针,右指针右指针. 说明：行row,列col,值value，表示一个非零元素，下指针down指向同一列中下一个非零元素，右指针right指向同一行中下一个非零元素。稀疏矩阵中同一行的非零元素由right,链接成一个带有头结点的行循环链表。同一列的非零元素由down，链接成一个带有头结点的列循环链表。因此,每个非零元素aij既是第i行循环链表中的一个结点，又是第j列循环链表中的一个结点。这样恰好构成一个十字，所以称为十字链表。结点的数据构造如下： struct node int row,col,val； struct

18、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 *

19、head,*new,*pre,*p,*row_p,*col_p; int i,count; head=NODE *mallocsizeofNODE; scanf“%d,%d,%dn,&head-row,&head-col, &head-val;/* 读行列数,非零元素 */ /*接下页 /* 行头结点用down域和表头结点组成循环链表 */ forpre=head,i=0;irow;i+ p=NODE *mallocsizeofNODE; p-val=p-row=p-col=0; p-right=p; pre-down=p; pre=p; p-down=head; /*

20、 列头结点用right域和表头结点组成循环链表 */ forpre=head,i=0;icol;i+ p=NODE *mallocsizeofNODE; p-val=p-row=p-col=0; p-down=p; pre-right=p; pre=p; p-right=head; count=0; /*接下页 whilecountval count+; new=NODE *mallocsizeofNODE; scanf%d,%d,%dn,&new-row,&new-col,&new-val; /* 定位行头结点 */ forrow_p=head,i=0;irow;i+

21、 row_p=row_p-down; p=row_p; /* 在循环行表中，定位插入位置 */ whilep-right!=row_p & p-right-colcol p=p-right; new-right=p-right; p-right=new; /* 将*new插入为*p的后续 */ /* 定位列头结点 */ forcol_p=head,i=0;icol;i+ col_p=col_p-right; p=col_p; /* 在循环列表中，定位插入位置 */ whilep-down!=col_p & p-down-rowrow p=p-down; new-down=p-d

22、own; p-down=new; /* 将*new插入为*p的后续 */ returnhead; 算法5.10 输出行主序的十字链表算法。 void printNODE *head /* 按行主序输出 */ NODE *row_p,*p; printf%d,%d,%dn,head-row,head-col,head-val; row_p=head-down; whilerow_p!=head p=row_p; whilep-right!=row_p p=p-right; printf%d,%d,%dn,p-row,p-col,p-val; row_p=row_p-down; 5.4 广义表 假

23、如将线性表的定义推广，即不限制线性表中每一个元素都是一个结点，那么所得到的表就是一个广义表。 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

24、 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广义表的图形表示广义表的图形表示 运算： 和线性表类似，可以对广义表的操作

25、有查询、插入和删除等。但广义表还有两个特殊的操作：取广义表的表头HEADLS和取广义表的表尾TAILLS。 根据前面对表头和表尾的定义可知：任何一个非空广义表其表头可以是单元素，也可以是子表，而其表尾必定为一个广义表子表。例如，广义表为前面所定义的A到E表，HEAD和TAIL运算有： HEADB=a， TAILB=b,c,d, HEADC=e， TAILC=, HEADD=A， TAILD=B,C,f，另外运算也可以嵌套，如： HEADTAILB=b， TAILTAILB=c,d。 5.4.2 广义表的存储构造 由于广义表中数据元素可以具有不同构造，通常采用链表存储构造，每一个数据元素可用一个

26、结点可以是子表或单元素。表示子表的表结点与表示单元素的数据元素结点之间是有差异的，以下是一种常用的存储构造。 struct node /* 表结点 */ int tag; /* =1标识子表结点 */ struct node *child； /* 指向该子表的指针 */ struct node *next； /* 指向下个元素的指针 */ ； struct node /* 数据元素结点 */ int tag; /* =0标识原子结点 */ int val； /* 值域 */ struct node *next； /* 指向下个元素的指针 */ ； 实际存储构造：为了便于处理，将val域和chi

27、ld域以结合的方式存储，表结点和数据结点合二为一，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求表深度；等。 下面讨论求表深度和建表算法。 广义表的深度定义为表中括号的重数，