第五章数组和广义表-ppt课件

1、第五章第五章 数组和广义表数组和广义表第一节 数组的定义数组的概念数组的概念 数组是由一组个数固定，类型一样的数据元素组成的阵列。数组是由一组个数固定，类型一样的数据元素组成的阵列。 以二维数组为例：二维数组中的每个元素都受两个线性关系的以二维数组为例：二维数组中的每个元素都受两个线性关系的约束即行关系和列关系，在每个关系中，每个元素约束即行关系和列关系，在每个关系中，每个元素aijaij都有且仅有都有且仅有一个直接前趋，都有且仅有一个直接后继。一个直接前趋，都有且仅有一个直接后继。 二维数组也可看作这样的线性表，其每一个数据元素也是一个二维数组也可看作这样的线性表，其每一个数据元素也是一个线

2、性表。线性表。a00a01a02a0,n-1a10a11a12a1,n-1am-1,0am-1,1am-1,2am-1,n-1Amn=Amn=(a00, a01 a0,n-1)，(a10, a11 a1,n-1)，(am-1,0, am-1,1 am-1,n-1)v根本操作根本操作vInitArray(&A,n,bound1,boundn)构造一个构造一个n维维数组数组vDestroyArray(&A)销毁数组销毁数组AvValue(A,&e,index1,indexn)取元素值到取元素值到evAssign(&A,e,index1,indexn)存存e的值到数组

3、的值到数组A第二节第二节 数组的顺序表示和实现数组的顺序表示和实现v由于存储单元是一维构造，而数组是个多维的构造，那么用一组由于存储单元是一维构造，而数组是个多维的构造，那么用一组延续存储单元存放数组的数据元素就有个次序商定即行列存储。延续存储单元存放数组的数据元素就有个次序商定即行列存储。a00a01a0,n-1a10a11a1,n-1am-1,0am-1,1am-1,n-1第第1行行第第2行行第第m行行Loc(a00)Loc(a10)Loc(am-1,0)以行为主序以行为主序a00a10am-1,0a01a11am-1,1a0,n-1a1,n-1am-1,n-1第第1列列第第2列列第第n列

4、列Loc(a00)Loc(a01)Loc(a0,n-1)以列为主序以列为主序 数组元素存储地址的计算数组元素存储地址的计算 假设二维数组假设二维数组Amn每个元素占用每个元素占用L 个存储单元个存储单元， Loc(aij)为元素为元素aij 的存储地址，的存储地址，Loc(a00 ) 是是a00存储位置存储位置, 也是二维数组也是二维数组A的基址。的基址。 假设以行序为主序的方式存储二维数组，那么元假设以行序为主序的方式存储二维数组，那么元素素aij 的存储位置可由下式确定：的存储位置可由下式确定： Loc(aij ) = Loc(a00 ) +n i+j ) L 假设以列序为主序的方式存储二

5、维数组，那么元假设以列序为主序的方式存储二维数组，那么元素素aij 的存储位置可由下式确定：的存储位置可由下式确定： Loc(aij ) = Loc(a00) +m j+i ) L第三节第三节 矩阵的紧缩存储矩阵的紧缩存储v矩阵是许多科学与工程计算问题中经常涉及到的一矩阵是许多科学与工程计算问题中经常涉及到的一种运算对象。种运算对象。 一个一个m m行行n n列的矩阵是一平面阵列，有列的矩阵是一平面阵列，有m mn n个元素。通常程序员是用二维数组存储矩阵。个元素。通常程序员是用二维数组存储矩阵。由于这种存储方法可以随机地访问矩阵的每个元素，由于这种存储方法可以随机地访问矩阵的每个元素，因此能

6、较为容易地实现矩阵的各种运算。因此能较为容易地实现矩阵的各种运算。v运用中常遇到一些阶数很高的矩阵，矩阵中有许多运用中常遇到一些阶数很高的矩阵，矩阵中有许多值一样的元素或零元素。二维数组存储矩阵会浪费值一样的元素或零元素。二维数组存储矩阵会浪费很多的存储单元。因此，需求运用高效的存储方法，很多的存储单元。因此，需求运用高效的存储方法，减少数据的存储量，即对原矩阵，根据数据分布特减少数据的存储量，即对原矩阵，根据数据分布特征进展紧缩存储。征进展紧缩存储。一、特殊矩阵值一样元素或者零元素分布有一定规律的矩阵称为特殊矩阵 例如对称矩阵、上下三角矩阵都是特殊矩阵。特殊矩阵紧缩存储 (以对称矩阵为例)

7、对称矩阵是满足下面条件的n 阶矩阵: aij= aji 0 i,j n-1a11a12a1,na21a22a2,nan,1an,2an,n对称矩阵元素可以只存储下三对称矩阵元素可以只存储下三角部分，共需角部分，共需 n(n+1)/2 个单个单元的空间元的空间( 三角矩阵的存储方三角矩阵的存储方式类似式类似a11a21a22a31a32a33an,1an,n K= 0 1 2 n(n+1)/2-1v以一维数组以一维数组sa 作为作为n 阶对称矩阵阶对称矩阵A的存储构造，的存储构造，A中恣意一元素中恣意一元素 aij与它的存储位置与它的存储位置 sak 之间存在之间存在着如下对应关系：着如下对应关

8、系：k =i(i-1)/2 +j -1 当当 i jj(j-1)/2 +i -1 当当 i j 例如，例如， a32 在在 sa 中的存储位置是：中的存储位置是：k=3*(3-1)/2+2-1=4 那么那么sa4= a32a11a21a22a31a32a33an,1an,n K= 0 1 2 3 4 n(n+1)/2-1v紧缩存储的对称矩阵的取值算法紧缩存储的对称矩阵的取值算法vint get_M(int i, int j)v if(i=j) return(sai*(i+1)/2+j);v else return(saj*(j+1)/2+i);v紧缩存储的对称矩阵的紧缩存储的对称矩阵的 赋值算

9、法赋值算法void assign_M(int i, int j, int value) if(i=j) sai*(i+1)/2+j=value; else saj*(j+1)/2+i=value;二、稀疏矩阵 有较多值一样元素或较多零元素，且值一样元素或者零元素分布没有一定规律的矩阵称为稀疏矩阵。根本操作CreateSMatrix(&M) 创建稀蔬矩阵M；DestroySMatrix(&M) 销毁稀蔬矩阵M；PrintSMatrix(M) 输出稀蔬矩阵M；CopySMatrix(M,&T) 复制稀蔬矩阵M到T；AddSMatrix(M,N,&Q) 求Q=M+N；

10、SubtSMatrix(M,N,&Q) 求Q=M-N;MultSMatrix(M,N,&Q) 求Q=M*N;TransposeSMatrix(M,&T) 求M的转置阵Tv稀疏矩阵的紧缩存储稀疏矩阵的紧缩存储v 只存储稀疏矩阵的非零元，可由表示非零元的三元组及其行列数只存储稀疏矩阵的非零元，可由表示非零元的三元组及其行列数独一确定独一确定(i,j,aij)(i,j,aij)。012900000000000-3000014000240000018000001500-7000M=ijv121213931-3361443245218611564-7M= ( (1,2,12),

11、(1,3,9), (3,1,-3),(3,6,14), (4,3,24), (5,2,18), (6,1,15), (6,4,-7) )加上行、列数加上行、列数6，7 v三元组的顺序表v 假设以顺序存储构造来表示三元组表，那么可得稀疏矩阵的一种紧缩存储方式我们称之为三元组顺序表(行序表示)。#define MAXSIZE 12500 /假设非零元个数的最大值假设非零元个数的最大值typedef struct int i,j; /非零元的行列下标非零元的行列下标 ElemType e; Triple;typedef struct Triple dataMAXSIZE+1;/非零元三元组表，非零元

12、三元组表，data0未用未用 int mu,nu,tu; /矩阵的行数、列数和非零元个数矩阵的行数、列数和非零元个数 TSMatrix;munutuije转置运算算法转置运算算法 转置运算是一种最常用的矩阵运算。对于一个转置运算是一种最常用的矩阵运算。对于一个 m 行行 n 列的矩阵列的矩阵 M，它的转，它的转置矩阵置矩阵 T是一个是一个n行行m列的矩阵。列的矩阵。 例如，以下图中的矩阵例如，以下图中的矩阵M和和T互为转置矩阵。互为转置矩阵。012900000000000-3000014000240000018000001500-7000M=T=00-300151200018090024000

13、0000-70000000014000000000算法分析：算法分析：1 1将矩阵的行数和列数的值交换将矩阵的行数和列数的值交换2 2将每一个三元组的将每一个三元组的i i 和和 j j互相互换互相互换3 3重排三元组之间的次序重排三元组之间的次序678MT768ijv121213931-3361443245218611564-7i,j互换互换ijv211231913-3631434242518161546-7重排重排ijv13-3161521122518319342446-76314算法实现算法实现Status TransposeSMatrix(TSMatrix M,TSMatrix &am

14、p;T) 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.datap.j=col) T.dataq.i=M.datap.j; T.dataq.j=M.datap.i; T.dataq.e=M.datap.e; +q; return OK;算法的时间重杂度算法的时间重杂度为：为：O(M.nu*M.tu)n十字键表存储紧缩稀疏矩阵n 在链表中，每个非零元可用一个含5个域的结点表示，其中i,j,e用来表示非零元的行、列、值，向右域right用以链接同一行中

15、下一个非零元，向下域down用以链接同一列中下一个非零元。再建两个头结点分别指示行和列。30050-1002000M=11322-1145312M.cheadM.rhead第四节第四节 广义表的定义广义表的定义v概念概念v 广义表也称为列表，是线性表的一种扩展，也是数据元素的有限序广义表也称为列表，是线性表的一种扩展，也是数据元素的有限序列。列。 记作：记作：LS= (d0, d1, d2, dn-1)LS= (d0, d1, d2, dn-1)。其中。其中didi既可以是单个元素，既可以是单个元素，也可以是广义表。也可以是广义表。v阐明阐明v广义表的定义是一个递归定义，由于在描画广义表时又用

16、到了广义表；广义表的定义是一个递归定义，由于在描画广义表时又用到了广义表；v在线性表中数据元素是单个元素，而在广义表中，在线性表中数据元素是单个元素，而在广义表中， 元素可以是单个元元素可以是单个元素素, , 称为单元素称为单元素( (原子原子) )，也可以是广义表，称为广义表的子表；，也可以是广义表，称为广义表的子表；vn n 是广义表长度；是广义表长度；v下面是一些广义表的例子；下面是一些广义表的例子； A = ( ) A = ( )空表，表长为空表，表长为0 0；E=( a ,E ) E=( a ,E ) 递归表递归表. . B = (a,(b,c,d) B B = (a,(b,c,d)

17、 B的表长为的表长为2 2，两个元素分别为，两个元素分别为 a a 和子表和子表b,c,d)b,c,d)； C = (e) C C = (e) C中只需一个元素中只需一个元素e e，表长为，表长为1 1；D=(A,B,C)D=(A,B,C) 假设广义表不空，那么可分成表头和表尾，反之，一对表头假设广义表不空，那么可分成表头和表尾，反之，一对表头和表尾可独一确定广义表。和表尾可独一确定广义表。 对非空广义表：称第一个元素为对非空广义表：称第一个元素为LS的表头，其他元素组成的表头，其他元素组成的表称为的表称为LS的表尾；的表尾； B = (a,(b,c,d) 表头：表头：a 表尾表尾 (b,c,d) 即即 HEADB=a, TAIL(B)=(b,c,d), C = (e) 表头：表头：e 表尾表尾 ( ) D = (A,B,C,f ) 表头：表头：A 表尾表尾 (B,C,f )v从上述定义和例子可推出列