数组与广义表

本章主要内容：1．数组的定义与表示2．矩阵的压缩存储3．广义表的定义与存储结构本章目的和要求：1．掌握数组的定义和表示2．掌握稀疏矩阵的存储本章重点：稀疏矩阵的存储：三元组和十字链表。第五章数组和广义表第五章数组和广义表5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5.4广义表5.1数组的定义一、数组抽象数据类型的定义二、关于二维数组和n维数组的另一种定义三、数组的操作ADTarray{数据对象：ji=0,…,bi-1,i=1,2,…,n,D={aj1j2…jn|n(0)称为数组的维数，bi是数组第i维的长度，ji是数组元素的第i维下标，aj1j2…jn∈elemset}数据关系：R={R1,R2,…,Rn}Ri={aj1…ji…jn,aj1…ji+1…jn|0≤jk≤bk-1,1≤k≤n且k≠i0≤ji≤bi-2,aj1…ji…jn,aj1…ji+1…jn∈D,i=2,…,n}一、数组抽象数据类型的定义5.1数组的定义基本操作：initarray(&A,n,bound1,…,boundn)destroyarray(&A)Value(A,&e,index1,…indexn)Assign(&A,e,index1,…indexn)}一、数组抽象数据类型的定义5.1数组的定义由定义可知：(1)n维数组中含bi个数据元素，每个数据元素受n个关系的约束。(2)每个关系中元素都有一个直接后继元素。(3)数据元素必须属于同一数据类型。(5)当n=1时，n维数组就退化为定长的线性表。反之，n维数组可以看成是线性表的推广。一、数组抽象数据类型的定义5.1数组的定义二、关于二维数组和n维数组的另一种定义1.二维数组(矩阵)：若把它的每个数据元素看成是一个定长的线性表，则它也是一个定长的线性表。Amn=a11a12a13a1na21a22a23a2n……………..am1am2am3amnA看成一个线性表A=(a1,a2,…,ap)（p=m或n）其中每个数据元素aj是一个列向量形式的线性表:aj=(a1j,a2j,…,amj)或者ai是一个行向量形式的线性表:ai=(ai1,ai2,…,ain)5.1数组的定义二、关于二维数组和n维数组的另一种定义因此：一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型。同理，一个n维数组类型可以定义为其数据元素为n-1维数组类型的一维数组类型。如：inta[m][n]相当于有一个a[m]数组，其元素为a[0]…a[i]…a[m-1]，其中每一元素a[i]又是一维数组a[i][0],a[i][1]……a[i][n-1]。5.1数组的定义数组一旦被定义，它的维数和维界就不再改变。因此所能进行的操作只有：初始化销毁数据元素的存取和修改三、数组的操作5.1数组的定义5.2数组的顺序表示和实现一、数组元素的地址对于数组的存储都是采用顺序存储结构。用一组连续的存储单元存储。由于存储单元是一维结构，而数组是个多维结构，确定数组元素的地址，则应有一个次序约定问题。这里以二维数组为例说明。对于二维数组有两种存储方式：(1)以行序为主的存储方式(常用)(2)以列序为主的存储方式a00a01a02a03a10a11a12a13a20a21a22a23a00a01a02a03a10a11a12a13a20a21a22a23第7个位置第8个位置5.2数组的顺序表示和实现以行序为主序的存储结构的元素位置确定设每个数据元素占L个存储单元，则二维数组A中任一元素aij的存储位置：LOC[i，j]=LOC[0，0]+(b2i+j)L其中：LOC[0，0]是a00的存储位置，二维数组的起始地址，称为基址。n维数组的数据元素存储位置：LOC(j1,j2,…jn)=LOC(0,0,…,0)+(b2…bnj1+b3…bnj2+…+bnjn-1+jn)L5.2数组的顺序表示和实现例：设有一二维数组A57每个元素占2字节，已知A的起始存储位置是1000。(1)若按行存储，a24的地址：LOC（2，4）=1000+（72+4）2(2)若按列存储，a24的地址：LOC（2，4）=1000+（54+2）2a00a01a02a03a04a05a06a10a11a12a13a14a15a16a20a21a22a23a24a25a26a30a31a32a33a34a35a36a40a41a42a43a44a45a46a00a01a02a03a04a05a06a10a11a12a13a14a15a16a20a21a22a23a00a01a02a03a04a10a11a12a13a14a20a21a22a23a30a31a32a33a40a41a42a43例：按行存储的a24的地址与按列存储的哪一个元素的地址相同。∵1000+（72+4）2=1000+（5j+i）218=5j+i∴i=3j=3a24与a33地址相同5.2数组的顺序表示和实现例：按低下标优先(行优先)存储整数数组A9358时，每个元素占4个字节，第一个元素的地址是100，计算a3125的存储地址。LOC[3,1,2,5]=100+(3*5*8*3+5*8*1+8*2+5)*45.2数组的顺序表示和实现练习：数组A[0..5，0..6]的每个元素占5个单元，将其按行优先的次序存储在起始地址为1000的连续内存单元中，则元素A[4,5]的地址为()。a.1140b.1145c.1160d.1165Loc(4,5)=1000+(7*4+5)*5=1165若数组为A[1..5，1..6]，则A[4,5]的地址：Loc(4,5)=1000+(6*(4-1)+(5-1))*5=11105.3矩阵的压缩存储一、特殊矩阵二、稀疏矩阵通常用二维数组存储矩阵元素。1．压缩存储为了节省空间，为多个值相同的元素只分配一个存储空间，对零元素不分配空间。2.采用压缩存储的两种矩阵(1)特殊矩阵若值相同的元素或者零元素在矩阵中分布有一定规律，则称此类矩阵为特殊矩阵。(2)稀疏矩阵非零元素占整个元素个数的比率低于的5%，称这种矩阵为稀疏矩阵。δ=t/(mn)δ——稀疏因子5.3矩阵的压缩存储一、特殊矩阵5.3矩阵的压缩存储1．对称矩阵若n阶矩阵A中的元满足下述性质aij=aji1≤i,j≤n则称为n阶对称矩阵。如：A=123224343将n2个元压缩存储到n(n+1)/2个元的空间中。可以行序为主序存储其下三角(包括对角线)的元。一、特殊矩阵设一维数组sa[1…n(n+1)/2]作为n阶对称矩阵A的存储结构，则sa[k]和矩阵元aij之间存在着一一对应的关系：k=i(i-1)/2+ji≥jj(j-1)/2+iij对于任意给定一组下标(i,j)，均可在sa中找到矩阵元aij，反之，对所有的k=1,2,…n(n+1)/2，都能确定sa[k]中的元在矩阵中的位置(i,j)。称sa[0…n(n+1)/2]为n阶对称矩阵A的压缩存储。a12a13a1na11a21a22a31…an1…annk=1234n(n-1)/2+1n(n+1)/25.3矩阵的压缩存储一、特殊矩阵2.下(上)三角矩阵是指矩阵的上(下)三角(不包括对角线)中的元均为常数c或零的n阶矩阵。压缩存储的方法同对称矩阵相似。除了存储下(上)三角中的元之外，再加一个存储常数c存储空间即可。14442244453436781235224622372228下三角矩阵上三角矩阵5.3矩阵的压缩存储一、特殊矩阵(1)下三角矩阵以行为主转换为一维数组的元素位置：i*(i+1)/2+j以列为主转换为一维数组的元素位置：[n+(n-j+1)]*j/2+(i-j)(2)上三角矩阵以行为主转换为一维数组的元素位置：[n+(n-i+1)]*i/2+(j-i)以列为主转换为一维数组的元素位置：j*(j+1)/2+i5.3矩阵的压缩存储一、特殊矩阵1444224445343678例1：如左图，一个4×4的下三角。以行为主：Loc(2,1)=2*(2+1)/2+1=4以列为主：Loc(2,1)=[4+(4-1+1)]*1/2+(2-1)=5例2：如左图，一个4×4的上三角。以行为主：Loc(1,2)=[4+(4-1+1)]*1/2+(2-1)=5以列为主：Loc(1,2)=2*(2+1)/2+1=412352246223722285.3矩阵的压缩存储01230123一、特殊矩阵3.对角矩阵所有的非零元都集中在以主对角线为中心的带状区域中。1200723006340058在上述这些特殊矩阵中，非零元的分布都有一个明显的规律，从而我们都可将其压缩存储到一维数组中，并找到每个非零元在一维数组中的对应关系。5.3矩阵的压缩存储二、稀疏矩阵1．抽象数据类型定义见书。2．稀疏矩阵的压缩存储压缩存储就是只存储非零元。由于稀疏矩阵的非零元素的分布没有规律，因此，对稀疏矩阵的存储采用三元组(i,j,aij)唯一确定了矩阵A的一个非零元。所谓三元组就是除了存储非零元的值还要存储非零元所在的行、列，即(i，j，aij)。如书上图5.5矩阵M可用下列三元组表：((1，2，12)，(1，3，9)，(3，1，-3)，(3，6，14)，(4，3，24)，(5，2，18)，(6，1，15)，(6，4，-7))0100000020100005.3矩阵的压缩存储三元组表的不同表示方法可引出稀疏矩阵不同的压缩存储方法。3．三元组顺序表用顺序存储结构来表示三元组表称之为三元组的顺序表。(1)存储方式对于稀疏矩阵的三元组，可以按行号的递增顺序排列，在同一行中三元组按列号递增顺序排列，从而构成了一个稀疏矩阵的三元组线性表。在该三元组线性表中的每一个结点对应稀疏矩阵中的一个非零元。二、稀疏矩阵ijv121213931-3361443245218611564-75.3矩阵的压缩存储(2)三元组顺序表的存储表示#defineMAXSIZE12500typedefstruct{inti,j;//非零元素的行下标和列下标elemtypee;//非零元素的值}triple;typedefstruct{tripledata[MAXSIZE+1];//非零元三元组表,data[0]未用intmu,nu,tu;//矩阵的行数、列数和非零元个数}tsmatrix;二、稀疏矩阵5.3矩阵的压缩存储二、稀疏矩阵(3)用三元组进行稀疏矩阵的转置运算转置运算是一种最简单矩阵运算，对于mn的M矩阵，它的转置矩阵是一个nm的T矩阵，且T(j,i)=M(i,j)。012900000000000-3000014000240000018000001500-700000-30001512000018090024000000000-70000000001400000000000sa=sb=5.3矩阵的压缩存储对于稀疏矩阵转置矩阵仍是稀疏矩阵。①算法的基本思想设原矩阵A的三元组数组为sa数组,转置后的矩阵B的三元组数组为sb数组。a.将sa和sb的行列值交换；b.将sa中的每个三元组中的i,j相互调换,即原来的(i,j,aij)转置为（j,i,aij）；c.将（j,i,aij）插入到转置后的三元组数组sb的适当位置，使其仍以行为主序。二、稀疏矩阵5.3矩阵的压缩存储二、稀疏矩阵②具体步骤：在sa数组中循环进行如下操作：在sa数组中按列扫描所有元素，将其列号作为sb的行号，其行号作为sb的列号插入到sb数组中。因为原矩阵的按行号递增次序顺序存储，当行号相同时，按列号递增存储，因此，用上述方法处理后，数组sb中每行的元素自然会按列号的递增次序顺序存储。5.3矩阵的压缩存储二、稀疏矩阵ijv121213931-3361443245218611564-7ijv13-3161521122518319342446-76314转置转置前后的三元组表：sa.datasb.data5.3矩阵的压缩存储③算法实现statustransferup(tsmatrixsa,Tsmatrixsb){sb.mu=sa.nu;s