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

《数据结构第5章数组和广义表.ppt》由会员分享，可在线阅读，更多相关《数据结构第5章数组和广义表.ppt（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、5.1数组类型5.1.1 数组的类型定义数组的类型定义ADT Array 数据对象：数据对象：Daj1,j2,.,ji,.jN|ji=0,.,bi-1,i=1,2,.,N,称N(0)为数组的维数，bi为数组第i维的长度，ji为数组元素的第i维下标，aj1,.,jNElemSet数据关系：数据关系：RR1,R2,.,RNRi|0jkbk-1,1kN且k=i,0jibi-2,aj1,.,ji,.,jn,aj1,.ji+1,.,jnD,i=2,.,N第五章第五章 数组和广义表数组和广义表基本操作：基本操作：InitArray(&A,n,bound1,.,boundn)操作结果：若维数n和各维长度合法

2、则构造相应数组A。DestroyArray(&A)初始条件：数组A已经存在。操作结果：销毁数组A。Value(A,&e,index1,.,indexn)初始条件：A是n维数组，e为元素变量，n个下标值。操作结果：若各下标不超界，则e赋值为所指定的A的元素值，并返回OK。Assign(&A,e,index1,.,indexn)初始条件：A是n维数组，e为元素变量，n个下标值。操作结果：若下标不超界，则将e的值赋给A中指定下标的元素。ADT Array5.1.2 数组的数组的顺序存储顺序存储表示表示通常有两种映象方法：“以行(序)为主(序)”的映象方法“以列(序)为主(序)”的映象方法如：二维数组

3、：A AB BC CD DE EF FGGH HI IJ JK KL LMMN NOOA AB BC CD DE EF FGGH HI IJ JK KL LMMN NOOA AF FK KB BGGL LC CH HMMD DI IN NE EJ JOO“以行为主“的映象方法：“以列为主“的映象方法：假设二维数组Rmn每个数据元素占L个存储地址LOC(i,j)表示下标为(i,j)的数据元素的存储地址，则LOC(i,j)在“以行为主”的顺序映象中的存储地址为：LOC(i,j)=LOC(0,0)+(in+j)L在“以列为主”的顺序映象中的存储地址为：LOC(i,j)=LOC(0,0)+(jm+i)

4、L基地址或基址假设三维数组Rpmn中每个数据元素占L个存储地址，并以LOC(i,j,k)表示下标为(i,j,k)的数据元素的存储地址，则该数组中任何一对下标(i,j,k)对应的数据元素在“以行为主”的顺序映象中的存储地址为：LOC(i,j,k)=LOC(0,0,0)+(imn+jn+k)L5.2矩阵的压缩存储5.2.1 特殊矩阵的压缩存储方法特殊矩阵的压缩存储方法特殊矩阵:矩阵中值相同的元素或零元素在矩阵中的分布有一定规律。大致有这样三类特殊矩阵：1.对称矩阵：若n阶方阵A中的元素满足特性aij=aji1i,jn则称为n阶对称矩阵；2.三角矩阵：若n阶方阵中下(上)三角(不包括对角线)中的元均

5、为常量c或0，则称为上(下)三角矩阵；3.对角矩阵：若n阶方阵中的非零值元都集中在以主对角线为中心的(由k条对角线组成的)带状区域中，则称为k对角矩阵。三角矩阵对角矩阵对称矩阵中n2个元压缩存储到n(n+1)/2个存储空间中假设以一维数组san(n+1)/2压缩存储n阶对称方阵A，则一维数组中的数据元素和方阵中的元aij之间存在着下列一一对应的关系：5.2.2 稀疏矩阵的压缩存储方法稀疏矩阵的压缩存储方法如果矩阵中只有少量的非零值元，并且这些非零值元在矩阵中的分布没有一定规律，则称为随机稀疏矩阵，简称为稀疏矩阵假设在mn的矩阵中有t个非零值元，令=t/（mn），称为矩阵的稀疏因子，则通常认定0

6、.05的矩阵为稀疏矩阵。如何存储稀疏矩阵中的非零值元？仍然采用二维数组表示稀疏矩阵，它的弊病是一、浪费空间二、浪费时间由此解决稀疏矩阵压缩存储的目标是：1)尽可能减少或不存储零值元；2)尽可能不作和零值元进行的运算；3)便于进行矩阵运算，即易于从一对行列号找到矩阵的元，易于找到同一行或同一列的非零值元。一个三元组唯一确定了矩阵A中的一个非零值元,由此可以其数据元素为上述三元组的线性表表示稀疏矩阵,并且非零元在三元组线性表中是以行为主有序排列的例如表示矩阵三元组线性表为：(1,3,9),(1,5,-7),(3,4,8),(4,1,5),(4,6,2),(5,2,16)一、三元组顺序表一、三元组顺

7、序表以顺序存储结构作为三元组线性表的存储结构，由此得到的稀疏矩阵的一种压缩存储方法.稀疏矩阵的三元组顺序表的结构定义稀疏矩阵的三元组顺序表的结构定义constMAXTERMS=12500;/非零个数的最大值为12500typedef struct inti,j;/该非零元的行号和列号ElemTypee;/该非零元的值Triple;/三元组typedef struct TripledataMAXTERMS+1;/data0未用introws,cols,terms;/矩阵的行数、列数和非零元的个数TSMatrix;/三元组顺序表当以三元组顺序表表示稀疏矩阵时，是否仍然便于进行运算呢？在此以“转置”

8、运算为例讨论算法。假设前面所列举的矩阵M的转置矩阵为 T，则按照矩阵转置的定义 M的三元组顺序表为：T的三元组顺序表为：转置的主要操作就是要确定M中的每个非零元在T的三元组顺序表中的位序以下表格中的三行依次为：colM的列号、numcolM中各列非零元的总数rposcolT中每一行第一个非零元在T.data中的序号：colcol1 12 23 34 45 56 6numcolnumcol1 10 01 11 12 21 1rposcolrposcol1 12 22 23 34 46 6rpos中的值可递推求得：rpos1=1;rposcol=rposcol-1+numcol-1由此，转置算法的

9、操作步骤为：1.求M矩阵的每一列中非零元的个数；2.确定T的每一行中第一个非零元在T.data中的序号；3.将M.data中每个元素依次复制到T.data中相应位置。算法算法 5.1voidFastTransposeSMatrix(TSMatrixM,TSMatrix&T)/采用三元组顺序表存储表示，求稀疏矩阵采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵的转置矩阵 TT.rows=M.cols;T.cols=M.rows;T.terms=M.terms;if(T.terms)for(col=1;col=M.cols;+col)numcol=0;for(t=1;t=M.terms;+t)+n

10、umM.datat.j;/求M中每一列所含非零元的个数rpos1=1;for(col=2;col=M.cols;+col)rposcol=rposcol-1+numcol-1;/求T中每一行的第一个非零元在T.data中的序号 for(p=1;p=M.terms;+p)/转置矩阵元素col=M.datap.j;q=rposcol;T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;+rposcol;/for/if/FastTransposeSMatrix上述算法的时间复杂度为O(M.cols+M.terms)。5.3广义表的定

11、义5.3.1广义表的定义广义表是线性表的推广，有人称之为列表（lists）抽象数据类型定义参见教材p107LS=（a1，a2，.，an）表头（head）表尾（tail）LS为广义表的名称n为广义表的长度ai可以是单个元素（原子），也可以是广义表（子表）下面列举一些广义表的例子：1.A=（）-A是一个空表，长度为0。2.B=（e）-列表B只有一个原子e，长度为1。3.C=（a，（b，c，d）-列表C的长度为2。两个元素分别是原子a和子表（b，c，d）。4.D=（A，B，C，）-列表D的长度为3，三个元素都是列表广义表的深度：定义为广义表中括号的重数由上述的例子可以得出列表的三个结论：1）列表的元

12、素可以是子表，而子表的元素也可以是子表因此，列表是个多层次的结构。2）列表可被其他列表所共享。3）列表可以是个递归的表，即列表也可以是他本身的一个子表。广义表的存储结构：链式存储结构列表结点：Tag=1Tag=1hphptptp标志域头指针域 尾指针域原子结点：Tag=0Tag=0atomatom标志域值域如前面所举的例子，他的存储结构如下A=NULL1 10 0e eBC1 11 11 10 0a a1 11 10 0b b0 0c c0 0d d1 11 11 1DE1 10 0a a1 1本章小结本章小结 1.数组的类型定义及其实现的方法。2.随机稀疏矩阵的三种表示方法。3.广义表的定义

13、和存储表示方法。课后习题课后习题【基础知识题】【基础知识题】【基础知识题】【基础知识题】1.1.假设有二维数组假设有二维数组 A A6868，每个元素用相邻的，每个元素用相邻的 6 6 个字节存个字节存储，存储器按字节编址。已知储，存储器按字节编址。已知 A A 的起始存储位置的起始存储位置(基地基地址址)为为 1000 1000，计算：，计算：(1)(1)数组数组 A A 的体积（即存储量）的体积（即存储量）;(2)(2)数组数组 A A 的最后一个元素的最后一个元素 a a5757 的第一个字节的地址的第一个字节的地址;(3)(3)按行存储时，元素按行存储时，元素 a a14 14 的第一个字节的地址的第一个字节的地址;(4)(4)按列存储时，元素按列存储时，元素 a a47 47 的第一个字节的地址。的第一个字节的地址。2.2.假设按低下标优先存储整数数组假设按低下标优先存储整数数组A9358A9358时，第时，第一个元素的字节地址是一个元素的字节地址是 100 100，每个整数占四个字节。问，每个整数占四个字节。问下列元素的存储地址是什么？下列元素的存储地址是什么？(1)a(1)a0000 0000(2)a(2)a11111111 (3)a(3)a3125 3125(4)a(4)a8247 8247