《数组和广义表》PPT课件.ppt

本章的基本内容是： 数组的逻辑结构特征； 数组的存储方式及寻址方法； 特殊矩阵和稀疏矩阵的压缩存储方法； 广义表的基本概念和存储结构。,3.1.1 数组的定义,是由一组类型相同的数据元素构成的有序集合，每个数据元素称为一个数组元素（简称为元素），每个元素受n(n1)个线性关系的约束，每个元素在n个线性关系中的序号i1、i2、in称为该元素的下标，并称该数组为n维数组。,3.1 多维数组,数组的特点:,元素本身可以具有某种结构,但属于同一数据类型； 数组是线性表的推广; 数组是一个具有固定格式和数量的数据集合。,数组示意图,3.1.2 数组的存储结构与寻址,采用顺序存储结构存储数组首先需要将多维结构映射到一维结构。,常用的映射方法有两种：按行优先和按列优先。,按行优先存储的基本思想是：先行后列，先存储行号较小的元素，行号相同者先存储列号较小的元素。,1.一维数组的存储与寻址,设一维数组的下标的范围为闭区间l，h，则其 的任一元素ai的存储位置可由下式确定： LOC(ai)LOC(al)(il)c,2.二维数组的存储与寻址,二维数组按行优先存储寻址示意图,aij前面的元素个数=阴影部分的面积=整行数每行元素个数+本行中aij前面的元素个数=(i -l1)(h2 -l21)(j -l2),二维数组寻址的计算方法,aij,按列优先存储的基本思想：先列后行，先存储列号较小的元素，列号相同者先存储行号较小的元素。,任一元素存储地址的计算方法你能推导出来吗？,n（n2）维数组，一般也采用按行优先和按列优先两种存储方法。 请给出基本思想和寻址计算方法，好吗？,下标为 i1, i2, i3的数组元素的存储地址： 按页/行/列存放 各维元素个数为 m1, m2, m3,LOC ( ai j k ) = Loc(a000) + ( i* m2 * m3 + j* m3 + k ) * l,3.2 矩阵的压缩存储,在矩阵中很多值相同的元素并且它们的分布有一定的规律，我们将这样的矩阵称为特殊矩阵。 若矩阵中有很多零元素称为稀疏矩阵,压缩存储的基本思想是： 为多个值相同的元素只分配一个存储空间； 对零元素不分配存储空间。,3.2.1 特殊矩阵的压缩存储对称矩阵,3 6 4 7 8 6 2 8 4 2 4 8 1 6 9 7 4 6 0 5 8 2 9 5 7,A,5阶对称矩阵,对称矩阵特点：在一个n阶方阵中，有aij=aji ，其中1i , jn。,只需要n（n1）/2个存储单元。,(a) 下三角矩阵 (b) 存储说明 (c) 计算方法,aij在一维数组中的序号 =阴影部分的面积 = i(i+1)/2+ j+1 一维数组下标从0开始 aij在一维数组中的下标 k= i(i+1)/2+ j,对称矩阵按行优先存储寻址示意图,结论：将下三角中的所有元素按行优先存储到一维数组中SA，下三角中的元素aij（ij）在数组SA中的下标k与i、j的关系为：ki(i1)/2j 。 同理我们可以得到： 上三角中的元素aij（ij），因为aijaji，则访问和它对应的元素aji即可，即：kj(j1)/2i 。,对称矩阵的压缩存储,3.2.1 特殊矩阵的压缩存储三角矩阵,3 c c c c 6 2 c c c 4 8 1 c c 7 4 6 0 c 8 2 9 5 7,(a) 下三角矩阵,3 4 8 1 0 c 2 9 4 6 c c 5 7 c c c 0 8 c c c c 7,(b) 上三角矩阵,只需存储n(n1)/21,下三角矩阵的压缩存储既要存储下三角中的元素，还要存储对角线上方的常数。因为是同一个常数，所以只存一个即可。,对于上三角矩阵，其存储思想与下三角类似，按行存储上三角部分，最后存储对角线下方的常数。,结论：1.下三角矩阵中任一元素aij在SA中的下标k与i、j的对应关系为：,2.上三角矩阵中任一元素aij在SA中的下标k与i、j的对应关系为：,K=j(j1)/2i 当ij,K=i(i1)/2j 当ij,3.2.1 特殊矩阵的压缩存储对角矩阵,所谓对角矩阵是指所有非零元素都集中在以主对角线为中心的带状区域中，除了主对角线和它的上下方若干条对角线的元素外，所有其他元素都为零。,(b) 压缩为5*3的矩阵,对角矩阵的压缩存储方法2,(c) 压缩到一维数组中,(a) 三对角矩阵,0 0 0 0 0 0 0 0 0 0 0 0,A=,按行存储非零元素,元素aij在一维数组中的序号 =2 + 3(i1)+( ji + 2) =2i+ j+1 一维数组下标从0开始 元素aij在一维数组中的下标 =2i+ j,(b) 寻址的计算方法,3.2.2 稀疏矩阵的压缩存储,什么是稀疏矩阵?有哪些特征?,三元组定义:将稀疏矩阵中的每个非零元素表示为：(行号，列号，非零元素值)称为三元组表示法。,C+中，用结构类型来描述三元组： template struct element int row, col; T item ;,三元组表：将稀疏矩阵的非零元素对应的三元组所构成的集合，按行优先的顺序排列成一个线性表。,采用顺序存储结构存储的三元组表称为三元组顺序表。,稀疏矩阵,A的三元组顺序表,一、三元组顺序表 假设以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方法三元顺序表。 #define maxsize 10000 typedef int datatype; typedef struct int i,j; datatype v; triple;,typedef struct triple datamaxsize; int m,n,t; tripletable; 设A为tripletable型的结构变量，图5.4中所示的稀疏矩阵的三元组的表示如下： i j v 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7,下面以矩阵的转置为例，说明在这种压缩存储结构上如何实现矩阵的运算。 一个mn的矩阵A，它的转置B是一个nm的矩阵，且aij=bji，0im，0jn，即A的行是B的列，A的列是B的行。 将A转置为B，就是将A的三元组表a.data置换为表B的三元组表b.data，如果只是简单地交换a.data中i和j的内容，那么得到的b.data将是一个按列优先顺序存储的稀疏矩阵B，要得到按行优先顺序存储的b.data，就必须重新排列三元组的顺序。 由于A的列是B的行，因此，按a.data的列序转置，所得到的转置矩阵B的三元组表b.data必定是按行优先存放的。,按这种方法设计的算法，其基本思想是：对A中的每一列 col(0coln-1)，通过从头至尾扫描三元表a.data，找出所有列号等于col的那些三元组，将它们的行号和列号互换后依次放入b.data中，即可得到B的按行优先的压缩存储表示。 i j v 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14,Void transmatrix(tripletable a,tripletable b) int p q col; b.m=a.n; b.n=a.m; b.t=a.t; if(b.t=0) printf(“A=0n”); q=0;,for(col=1;col=a.n;col+) for(p=0;p=a.t;p+) if(a.datap.j=col) b.dataq.i=a.datap.j; b.dataq.j=a.datap.i; b.dataq.v=a.datap.v; q+; ,分析这个算法，主要的工作是在p和col的两个循环中完成的，故算法的时间复杂度为O(n*t)，即矩阵的列数和非零元的个数的乘积成正比。而一般传统矩阵的转置算法为： for(col=0;col=n-1;+col) for(row=0;row=m;+row) tcolrow=mrowcol; 其时间复杂度为O(n*m)。当非零元素的个数t和m*n同数量级时，算法transmatrix的时间复杂度为O(n*n2)。,三元组顺序表虽然节省了存储空间，但时间复杂度比一般矩阵转置的算法还要复杂，同时还有可能增加算是法的难度。因此，此算法仅适用于t=m*n的情况。 下面给出另外一种称之为快速转置的算法，其算法思想为：对A扫描一次，按A第二列提供的列号一次确定位置装入B的一个三元组。具体实施如下：一遍扫描先确定三元组的位置关系，二次扫描由位置关系装入三元组。可见，位置关系是此种算法的关键。,为了预先确定矩阵M中的每一列的第一个非零元素在数组B中应有的位置，需要先求得矩阵M中的每一列中非零元素的个数。因为：矩阵M中第一列的第一个非零元素在数组B中应有的位置等于前一列第一个非零元素的位置加上前列非零元素的个数。 为此，需要设置两个一维数组num0n和cpot0n num0n：统计M中每列非零元素的个数，numcol的值可以由A的第二列求得。,cpot0n：由递推关系得出M中的每列第一个非零元素在B中的位置。 算法通过cpot数组建立位置对应关系： cpot1=1 cpotcol=cpotcol-1+numcol-1 2=cpl=a.n 例如：图5.4中的矩阵M和相应的三元组A可以求得numcol和 cpotcol的值如下： col 1 2 3 4 5 6 7 numcol 2 2 2 1 0 1 0 cpotcol 1 3 5 7 8 8 9,A i j v,第一列元素个数 第二列元素个数 第三列元素个数,num,cpot,q=cpotcol,p,p,快速转置算法如下： void fasttranstri(tritupletable b,tritupletable a) int p,q,col,k; int num0a.n,copt0a.n; b.m=a.n; b.n=a.m; b.t=a.t; if(b.t=0) printf(“a=0”n); for(col=1;col=a.u;+col) numcol=0; for(k=1;k=a.t;+k) +numa.datak.j;,cpot0=1; for(col=2;col=a.t;+col) cpotcol=cpotcol-1+numcol-1; for(p=1;p=a.t;+p) col=a.datap.j; q=cpotcol; b.dataq.i=a.datap.j; b.dataq.j=a.datap.i; b.dataq.v=a.datap.v; +cpotcol; ,算法的伪代码描述：,1. 设置转置后矩阵B的行数、列数和非零元素的个数； 2. 在B中设置初始存储位置pb； 3. for (col=最小列号; col=最大列号; col+) 3.1 在A中查找列号为col的三元组； 3.2 交换其行号和列号，存入B中pb位置； 3.3 pb+；,分析时间复杂度？,稀疏矩阵三元组顺序表存储操作 转置算法,分析：如何确定当前从A中取出的三元组在B中的位置。注意到A中第0列的第一个非零元素一定存储在B中下标为0的位置上，该列中其它非零元素应存放在B中后面连续的位置上，那么第1列的第一个非零元素在B中的位置便等于第0列的第一个非零元素在B中的位置加上第0列的非零元素的个数，以此类推。,该算法的基本思想：是在A中依次取三元组，交换其行号和列号放到B 中适当位置。,1.引入两个数组作为辅助数据结构： numnu：表示矩阵A中某列的非零元素的个数； cpotnu：初始值表示矩阵A中某列的第一个非零元素在B中的位置。,算法设计：,2.num与cpot递推关系：,1. 设置转置后矩阵B的行数、列数和非零元素的个数； 2. 计算A中每一列的非零元素个数； 3. 计算A中每一列的第一个非零元素在B中的下标； 4. 依次取A中的每一个非零元素对应的三元组； 4.1 确定该元素在B中的下标pb； 4.2 将该元素的行号列号交换后存入B中pb的位置； 4.3 预置该元素所在列的下一个元素的存放位置；,算法的伪代码：,稀疏矩阵链接存储的基本思想是：将每个非零元素对应的三元组存储为一个链表结点，结点由5个域组成，,其中: row：存储非零元素的行号； col：存储非零元素的列号； item：存储非零元素的值； right：指针域，指向同一行中的下一个三元组； down：指针域，指向同一列中的下一个三元组.,例:,3.3 广 义 表,3.3.1 广义表的逻辑结构,广义表的定义,广义表是n（n0）个数据元素的有限序列，一般记作：LS(a1，a2，an),其中:LS是广义表的名称，ai（1in）是LS的成员（也称直接元素），它可以是单个的数据元素，也可以是一个广义表，分别称为LS的单元素和子表。,其它概念: 1表头:当广义表LS非空时，称第一个元素为LS的表头； 2表尾: 广义表LS中除去表头后其余元素组成的广义表为LS的表尾; 3 广义表长度:广义表LS中的直接元素的个数； 4 广义表的深度:广义表LS中括号的最大嵌套层数。,广义表( )和广义表( )不同？,广义表表示方法,通常用图形方法来表示广义表的逻辑结构，具体表示方法为：对每个广义表的直接元素ai用一个结点来表示，若ai为单元素，则用矩形结点表示，若ai为广义表，则用圆形结点表示，结点之间的边表示元素之间的“包含/属于”关系。,广义表的特性, 广义线性性； 元素复合性； 元素递归性； 元素共享性：,3.3.2 广义表的存储结构及实现,广义表的存储结构头尾表示法,结点结构有两种：一种是表结点；另一种是元素结点。,其中，tag：区分表结点和元素结点的标志； hp：指向表头结点的指针； tp：指向表尾结点的指针； data：存放单元素的数据域。,enum Elemtag Atom, List; template struct GLNode Elemtag tag; union T data; struct GLNode *hp, *tp; ptr; ; ;,定义广义表的结点结构,template class Lists public: Lists( ) ls=NULL; Lists(Lists ls1, Lists ls2)