数据结构第五章数组和广义表.ppt

第五章 数组和广义表,第五章 数组和广义表 5. 1 数组的定义 5.2 数组的顺序存储结构 5. 3 矩阵的压缩存储 5. 4 广义表的定义 5.5 广义表的存储结构,3,前4章介绍的数据结构共同特点： 都属于线性数据结构； 每种数据结构中的数据元素，都作为原子数据，不再进行分解； 本章讨论的两种数据结构：数组和广义表，其共同特点是： 从逻辑结构上看它们，可看成是线性结构的一种扩展； 数据元素本身也是一个数据结构；,第五章 数组和广义表,4,一、数组的定义 (1) 数组的抽象数据类型定义 ADT Array 数据对象： Daj1,j2,ji,jn|ji=0,bi-1,i=1,2,n ( n0) 称为数组的维数,bi是数组第i维的长度，ji是数组元素的第i维下标,51 数组的定义,数据关系：RR1, R2, ,Rn,5,Ri|0jkbk-1,1kn 且 ki, 0jibi-2, aj1 jijn, aj1 ji+1 jn D， i=2, ,n 如二维数组的定义: 数据对象: D= aij|0ib1-1,0jb2-1 数据关系: R= ROW, COL ROW= | 0ib1-2,0jb2-1 COL= | 0ib1-1,0jb2-2 ,6,(2) 二维数组的解释,二维数组中的每个元素都受两个线性关系的约束，即行关系和列关系，在每个关系中，每个元素aij都有且仅有一个直接前趋，都有且仅有一个直接后继。,在行关系中 aij直接前趋是 aij-1 aij直接后继是 aij+1 在列关系中 aij直接前趋是 ai-1j aij直接后继是 ai+1j,7,A=(0 ,1 ,2 ,3 , 4 ,p ) p = m-1 或 n-1 其中每一个数据元素 j 是一个列向量的线性表 j=（a0j , a1j ,a2j , a3j , ,am-1j ) 0jn-1,二维数组也可看作这样的线性表：其每一个数据元素也是一个线性表。,8,或 i 是一个行向量的线性表 i=（ai0 ,ai1 ,ai2 , ai3 , ,ain-1 ) 0im-1 Amn=(a00 a01 a0 n-1 ),(a10 a11 a1 n-1),(am-1 0 am-1 1 am-1 n-1),(3) C语言中二维数组类型的一种定义,typedef elemtype Array2mn; 等价于 typedef elemtype Array1n; typedef Array1 Array2m; 同理，可以用 n-1 维数组的数据类型来定义 n 维数组。,9,一、数组的顺序表示和实现 (1) 类型特点 只有引用型操作，一般不作插入或删除操作； 数组是多维的结构，而存储空间是一个一维的结构。 (2) 两个策略-两种顺序映象的方式 以行序为主序(低下标优先)； 以列序为主序(高下标优先)。,52 数组的顺序存贮结构,10,以行为主序的方式：,11,以列为主序的方式：,12,12,(4) 存储位置的公式,假设二维数组A每个元素占用L 个存储单元，若以行序为主序的方式存储二维数组，二维数组A中任一元素ai,j的存储位置为： LOC(i, j) = LOC(0,0) + (b2ij),L,三维数组A中任一元素ai,j,k的存储位置为： LOC(i,j,k)=LOC(0,0,0)+(b2b3ib3j+k)L,若以列序为主序的方式存储二维数组，则元素aij 的存储位置可由 下式确定： Loc(aij ) = Loc(a00) +（ b1 j+i ) L,13,13,14,14,14,推广到一般情况，可得到 n 维数组数据元素存储位置的映象关系: P93,称为 n 维数组的映象函数。数组元素的存储位置是其下标的线性函数。 是随机存储结构。,其中cn=L,ci-1=bi*ci,1i=n,15,15,15,(5) 结构定义 #define maxarraydim 8 typedef struct elemtype *base; / 数组元素基址 int dim; / 数组维数 int *bounds; / 数组维界基址(各维容量) int *constants; / 数组映象函数常量基址 array;,5. 3 矩阵的压缩存储 一 特殊矩阵的压缩存储 二 稀疏矩阵的压缩存储 1 三元组表的存储结构 2 十字链表的存储结构,(1) 矩阵压缩存储的必要性 矩阵是许多科学与工程计算问题中常常涉及到的一种运算对象。通常程序员是用二维数组存储矩阵。由于这种存储方法可以随机地访问矩阵的每个元素，因而能较为容易地实现矩阵的各种运算。 应用中常遇到一些阶数很高的矩阵，矩阵中有许多值相同的元素或零元素。二维数组存储矩阵会浪费很多的存储单元。 例如，设一个1000 1000的矩阵中有800个非零元素，若用二维数组存储需要106个存储单元。因此，需要使用高效的存储方法，减少数据的存储量，即对原矩阵，根据数据分布特征进行压缩存储。,1、矩阵的压缩存储,53 矩阵的压缩存储,(2) 压缩存储的有关概念 压缩存储：为多个值相同的元素分配一个存储空间，对零元不分配空间。 特殊矩阵：值相同的元素或零元素在矩阵中的分布有一定规律。, 稀疏矩阵：值相同的元素或者零元素在矩阵中的分布无规律。, 压缩存储方法 为每一对对称元分配一个存储空间，则可将n2个元压缩存储到n(n+1)/2个元的空间中。,(3) 特殊矩阵 概念：若n阶矩阵 A 中的元满足：aij=aji 1i,jn，则称为n 阶对称矩阵。, 下标对应关系,k=,当 i j,当 i j,矩阵的上(下)三角(不含对角线)中的元均为常数C或0的n阶矩阵(三角矩阵)，其存储方法相同。 例如， a32 在 sa 中的存储位置是：k=3*(3-1)/2+2-1=4 sa4= a32 (4) 对角矩阵 概念：非零元都集中在以主对角线为中心的带状区域中。 存储：这种矩阵可以某个原则(以行为主，或以对角线的顺序)将其压缩存储到一维数组上。,压缩存储的对称矩阵的取值算法 int get_M(int i, int j) if(i=j) return(sai*(i+1)/2+j) else return(saj*(j+1)/2+i); 压缩存储的对称矩阵的 赋值算法 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; ,带状矩阵 所有非0元素都集中在以主对角线为中心的带状区域，半带宽为d时, 非0元素有,(2d+1)*n-(1+d)*d个,a00 a01 a 02 0 0 0 0 0 0 0 0 0 a10 a11 a12 a13 0 0 0 0 0 0 0 0 a20 a21 a22 a23 a24 0 0 0 0 0 0 0 0 a31 a32 a33 a34 a35 0 0 0 0 0 0 0 0 a42 a43 a44 a45 a46 0 0 0 0 0 0 0 0 a53 a54 a55 a56 a57 0 0 0 0 0 0 0 0 a64 a65 a66 a67 a68 0 0 0 0 0 0 0 0 a75 a76 a77 a78 a79 0 0 0 0 0 0 0 0 a86 a87 a88 a89 a810 0 0 0 0 0 0 0 0 a97 a98 a99 a910 a911 0 0 0 0 0 0 0 0 a108 a109 a1010 a1011 0 0 0 0 0 0 0 0 0 a119 a1110 a1111,d,为计算方便，认为每一行都有2d+1个非0元素，若少则用0补足，所以，存放矩阵的数组sa 有n(2d+1) 个元素 数组元素sak与矩阵元素aij 之间有关系： k=i*(2d+1)+d+(j-i),压缩存储的带状矩阵的取值算法 int get_Md(int i, int j) if(abs(i-j)=d） return(sai*(2*d+1)+d+(j-i)； else return(0); 压缩存储的 带状矩阵的 赋值算法 void assign_Md(int i, int j, int value) if(abs(i-j)=d） sai*(i+1)/2+j=value; ,(5) 稀疏矩阵, 含义：在 mn 的矩阵中，有t 个元素不为零，令：,称为矩阵的稀疏因子，通常认为0.05 时称稀疏矩阵, 抽象数据类型稀疏矩阵的定义, 分析 按常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题: I 零值元素占了很大空间； II 计算中进行了很多和零值的运算，遇除法，还需判别除数是否为零。,解决问题的原则: I 尽可能少存或不存零值元素； II 尽可能减少没有实际意义的运算； III 操作方便。即：能尽可能快地找到与下标值(i，j)对应的元素，能尽可能快地找到同一行或同一列的非零值元。 为此提出一种存储方法：为了能找到相应的元素，仅存储非零元素的值是不够的，还要记下它所在的行和列。于是采取将非零元素所在的行、列以及它的值构成一个三元组(i,j,v)，然后再按某种规律存储这些三元组，这种方法可以节约存储空间。,例如：稀疏矩阵：,可用三元组表(i,j,aij) A=(0,1,12), (0,2,9), (2,0,-3),(2,5,14), (3,2,24), (4,1,18), (5,0,15), (5,3,-7)加上行、列数、非零元个数6，7,8 表示。 用三元组表存储稀疏矩阵有三种方法： I 三元组顺序表 II 行逻辑链接的顺序表 III 十字链表, 三元组顺序表 I 概念：以顺序存储结构来表示三元组表，得稀疏矩阵的一种压缩存储方式称之为三元组顺序表。,如：,如：ma1.row=1, ma1.col=1, ma1.value=12,II 结构定义 #define maxsize 1024 typedef struct int i,j; elemtype v; triple;,typedef struct triple datamaxsize+1; int mu,nu,tu; tsmatrix;,III 转置运算算法,转置运算是一种最常用的矩阵运算。对于一个 m 行 n 列的矩阵 A，它的转置矩阵 B 是一个 n 行 m 列的矩阵。如，下图中的矩阵 A 和 B 互为转置矩阵。,转置运算算法,分析： 将矩阵的行列数的值交换 将每一个三元组的 i 和 j 相互调换 重排三元组之间的次序,算法一,按照A的列序来进行转换的基本思想 对 ma 从头至尾扫描： 第一次扫描时，将 ma 中列号为0的所有元组交换行列值后，依次赋值到 mb 中； 第二次扫描时，将 ma 中列号为1的所有元组交换行列值后，依次赋值到 mb 中； 依此类推，直至将 ma 的所有三元组赋值到 mb 中。,i j v,i j v,3 1 -3,2 5 18,1 3 -3,6 1 15,1 6 15,1 2 12,2 1 12,5 2 18,1 3 9,3 1 9,4 3 24,3 4 24,6 4 -7,4 6 -7,3 6 14,6 3 14,A矩阵,B矩阵,对A六次扫描完成转置运算,第一次扫描查找第1列元素,第一次扫描结束,第二次扫描结束,第二次扫描查找第2列元素,第三次扫描查找第3列元素,第四次扫描查找第4列元素,第五次扫描查找第5列元素,第六次扫描查找第6列元素,转置运算算法图示,0 1 2 3 4 5 6 7 8,6 7 8,7 6 8,算法一描述(保持以行序为主序存储),int tpm(tsmatrix m, tsmatrix *t) t-mu=m.nu; t-nu=m.mu; t-tu=m.tu; if(t-tu) q=1; for(col=1;coldataq.i=m.datap.j; t-dataq.j=m.datap.i; t-dataq.v=m.datap.v; q+; return ok; , 时间复杂度为 (nutu),算法二快速转置算法,方法：以 A 矩阵的三元组为中心, 依次取出 ma 中的每一个三元组，交换行列后，直接将其写入mb 合适的位置中。,3 4 24,1 6 15,3 1 9,6 3 14,2 5 18,1 3 -3,2 1 12,4 6 -7, 十字链表,I 概念：以三元组表示的稀疏矩阵，在运算中，若非0元素的位置发生变化，会引起数组元素的频繁移动。为解决这个问题，采用十字链表的存储结构 在十字链表中，表示非0元素结点除了三元组,还有两个指针域： 向下域(down) 链接同一列下一个非0元素 向右域(right) 链接同一行下一个非0元素 稀疏矩阵中同一行的非0元素结点通过向右域，链接成一个带头结点的行循环链表。 同一列的非0元素结点通过向下域，链接成一个带头结点的列循环链表。,II 十字链表的存储结构(结点的数据结构)如下： struct node int row, col, val; struct node *down, *right; ,例如矩阵,22,十字链表图示,小 结 1 矩阵压缩存储是指为多个值相同的元素分配一个 存储空间，对零元素不分配存储空间； 2 特殊矩阵的压缩存储是根据元素的分布规律，确定 元素的存储位置与元素在矩阵中的位置的对应关系； 3 稀疏矩阵的压缩存储除了要保存非零元素的值外，还 要保存非零元素在矩阵中的位置；,1、广义表的定义,(1) 广义表的引入 线性表是由n个数据元素组成的有限序列。其中每个组成元素被限定为单元素，有时这种限制需要拓宽。 例如，中国举办的某体育项目国际邀请赛，参赛队清单可采用如下的表示形式： (俄罗斯，巴西，(国家，河北，四川)，古巴，美国，( )，日本) 在这个拓宽了的线性表中，韩国队应排在美国队的后面，但由于某种原因未参加，成为空表。国家队、河北队、四川队均作为东道主的参赛队参加，构成一个小的线性表，成为原线性表的一个数据项。这种拓宽了的线性表就是广义表。,5. 4 广义表,(2) 广义表的定义,广义表（Generalized Lists）是n（n0）个数据元素 a1，a2，ai，an 的有序序列，一般记作： ls（a1，a2，ai，an） 其中：ai（1in）是ls的成员，它可以是单个元素，也可以是一个广义表。 说明 ls是广义表的名称，n是它的长度。 广义表的定义是一个递归定义，因为在描述广义表时又用到了广义表；, 在线性表中数据