数据结构数组与广义表.ppt

《数据结构数组与广义表.ppt》由会员分享，可在线阅读，更多相关《数据结构数组与广义表.ppt（46页珍藏版）》请在优知文库上搜索。

1、第五章第五章 数组和广义表数组和广义表1第五章第五章 数组和广义表数组和广义表l本章前讨论的线性结构数据元素都是非结构本章前讨论的线性结构数据元素都是非结构的的原子类型原子类型，元素值不可再分。本章讨论了，元素值不可再分。本章讨论了两种数据结构两种数据结构数组和广义表。作为线性表数组和广义表。作为线性表的扩展，表中的数据元素也是一种数据结构。的扩展，表中的数据元素也是一种数据结构。l数组数组这种数据结构可以看成这种数据结构可以看成是线性表的推广是线性表的推广。l广义表广义表是另一种推广形式的线性表，是一种是另一种推广形式的线性表，是一种灵活的数据结构，在许多方面有广泛的应用。灵活的数据结构，在

2、许多方面有广泛的应用。2知识结构图知识结构图数组与广义表数组与广义表 数数 组组广义表广义表类型定义类型定义表示方法表示方法稀疏矩阵稀疏矩阵特殊矩阵特殊矩阵存储结构存储结构逻辑结构逻辑结构 应用应用压缩存储压缩存储各种运算各种运算35.1 数组数组数组数组是是n(n1)个相同数据类型的数据元素个相同数据类型的数据元素a0,a1,a2,.,an-1构成的占用一块地址连续的内存单元的有限序列。构成的占用一块地址连续的内存单元的有限序列。数组中任意一个元素可以用该元素在数组中的位置来表示，数组中任意一个元素可以用该元素在数组中的位置来表示，数组元素的位置通常称作数组元素的位置通常称作数组的下标数组的

3、下标。45.1.1 数组的概念及其与线性表的关系数组的概念及其与线性表的关系 由定义知由定义知，n维数组中有维数组中有b1 b2 bn个数据元素个数据元素，每个每个数据元素都受到数据元素都受到n维关系的约束维关系的约束。直观的直观的n维数组维数组 以二维数组为例讨论。以二维数组为例讨论。将二维数组看成是一个定长的线性表，将二维数组看成是一个定长的线性表，其每个元素又是一个定长的线性表其每个元素又是一个定长的线性表。 设二维数组设二维数组A=(aij)m n，则，则 A=(1，2，p) (p=m或或n)其中每个数据元素其中每个数据元素j是一个列向量是一个列向量(线性表线性表) ： j =(a1j

4、 ，a2j ，amj) 1jn或或是一个行向量是一个行向量： i =(ai1 ，ai2 ，ain) 1im如图如图5-1所示。所示。5 a11 a12 a1n a21 a22 a2n am1 am2 amnA= A=a11 a12 a1na21 a22 a2nam1 am2 amna11 a21 am1a12 a22 am2a1n a2n amnA=图图5-1 二维数组图二维数组图例形式例形式(a) 矩阵矩阵表示形式表示形式(b)行行向量的一维数组形式向量的一维数组形式(c)列向量的一维数组形式列向量的一维数组形式6n维数组的特点维数组的特点l每个数据元素都受着每个数据元素都受着n n个关系的

5、约束；个关系的约束；l在每个关系中，元素在每个关系中，元素 (0=j(0=ji i=b=bi i-2)-2)都有一个直接后继都有一个直接后继; ;l数据元素都必须属于同一数据类型数据元素都必须属于同一数据类型; ;ln=1n=1时，退化为定长的线性表；时，退化为定长的线性表；ln n维数组可以看成是线性表的推广。维数组可以看成是线性表的推广。l数组一旦被定义，则维数已定，对于数组的操作只有存取元数组一旦被定义，则维数已定，对于数组的操作只有存取元素和修改元素。素和修改元素。( (一旦建立了数组，数组中的元素个数和元一旦建立了数组，数组中的元素个数和元素之间的关系就不再发生变动素之间的关系就不再

6、发生变动) )l数组是多维的结构，而存储空间是一个一维的结构。（存储数组是多维的结构，而存储空间是一个一维的结构。（存储时需要一个次序约定）时需要一个次序约定）njjja.2175.1.2 数组的顺序存储结构数组的顺序存储结构数组的实现机制数组的实现机制(1)ina一一维维数数组组( ( 个个元元素素) )中中任任一一元元素素 的的内内存存单单元元地地址址0()()*(0)iLoc aLoc ai Lin a的内存单元地址的内存单元地址每个元素所需的字节个数每个元素所需的字节个数(2)mn一一维维 行行 列列的的二二维维数数组组00()()( *)*ijLoc aLoc ai njL00()(

7、)( *)*ijLoc aLoc aj miL00010,110111,11,01,11,1nnmmmnaaaaaaAaaa811221122(3), . ,.cdcdA cd cd更更一一般般地地假假设设二二维维数数组组行行下下界界是是行行上上界界为为列列下下界界为为列列上上界界为为，即即数数组组。12,1222()()()*(1)()*ijc cLoc aLoc aicdcjcL以以行行序序为为主主序序的的求求元元素素地地址址的的公公式式：12,2111()()()*(1)()*ijc cLoc aLoc ajcdcicL以以列列序序为为主主序序的的求求元元素素地地址址的的公公式式：9数组

8、的顺序表示数组的顺序表示- -小结小结ln维数组的特点维数组的特点:l数据元素同属于一种数据类型；数据元素同属于一种数据类型；l数组一旦被定义，则维数和各维长度不能改变；数组一旦被定义，则维数和各维长度不能改变；l数组操作只有引用型操作，没有加工型操作；数组操作只有引用型操作，没有加工型操作；l数组是多维结构，但存储空间是一维结构。数组是多维结构，但存储空间是一维结构。l数组顺序表示的特点数组顺序表示的特点l存储单元地址连续（需要一段连续空间）存储单元地址连续（需要一段连续空间）l存储规则（以行（列）为主序）决定元素实际存储位置存储规则（以行（列）为主序）决定元素实际存储位置l随机存取随机存取

9、l存储密度最大（存储密度最大（100%100%）105.2 矩阵的压缩存储矩阵的压缩存储 在科学与工程计算问题中，矩阵是一种常用的数学在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编程时，通常将一个矩阵描述为对象，在高级语言编程时，通常将一个矩阵描述为一个二维数组。这样，可以对其元素进行随机存取一个二维数组。这样，可以对其元素进行随机存取，各种矩阵运算也非常简单。，各种矩阵运算也非常简单。 对于对于高阶矩阵高阶矩阵，若其中，若其中非零元素呈某种规律分非零元素呈某种规律分布布或者或者矩阵中有大量的零元素矩阵中有大量的零元素，若仍然用常规方法，若仍然用常规方法存储，可能存储重复的非零

10、元素或零元素，将造成存储，可能存储重复的非零元素或零元素，将造成存储空间的大量浪费。对这类矩阵进行压缩存储：存储空间的大量浪费。对这类矩阵进行压缩存储： 多个相同的非零元素只分配一个存储空间多个相同的非零元素只分配一个存储空间； 零元素不分配空间。零元素不分配空间。115.2.1 5.2.1 特殊矩阵的压缩存储特殊矩阵的压缩存储l1.对称矩阵对称矩阵n阶矩阵阶矩阵A中元素满足性质中元素满足性质aij=aji (1i,jn)。（即aij=aji,1=i,j=n）a11a21a22aijannLTA0.n(n+1)/2-1k= 0 1 2 n(n+1)/2-112lk的含义：按行优先，是第k个（从

11、0开始）15675289683079041526837904i=3j=2k=4 公式的推导（下三角） i=3，j=2 则前面有一个i-1行的完整三角形，共有元素 (1+i-1)(i-1)/2 = i(i-1)/2个 另外，同一行，前面还有j-1个元素 所以，k = i(i-1)/2+j-114/502 2、三角矩阵、三角矩阵 以主对角线划分，以主对角线划分， n阶三角矩阵有阶三角矩阵有n阶上三角矩阵和阶上三角矩阵和n阶下三角矩阵两种。阶下三角矩阵两种。 n阶上三角矩阵的下三角（不包括主对角线）中的元素均为阶上三角矩阵的下三角（不包括主对角线）中的元素均为0（或常数）。（或常数）。n阶下三角矩阵

12、正好相反，它的主对角线上方均为阶下三角矩阵正好相反，它的主对角线上方均为0（或常数）。（或常数）。 注：在大多数情况下，注：在大多数情况下， n阶三角矩阵常数为零。阶三角矩阵常数为零。111213122232333nnnmnaaaacaaaAccaaccca112122313233123mmmmnacccaaccAaaacaaaa 下三角矩阵元素下三角矩阵元素ai j保存保存在向量在向量sa中时的中时的下标值下标值k与与（i,j）之间的对应关系）之间的对应关系是：是：i (i-1)/2+j 当当ij时时n (n+1)/2 当当ij 时时K=1i,jn (5-5)155.2.2 稀疏矩阵的压缩存

13、储稀疏矩阵的压缩存储l稀疏矩阵：设稀疏矩阵：设m行行n列的矩阵含列的矩阵含t个非零元素，则个非零元素，则=t/(m*n)称称为为稀疏因子稀疏因子，通常认为，通常认为 0.05 的矩阵为稀疏矩阵。的矩阵为稀疏矩阵。(1)、稀疏矩阵、稀疏矩阵矩阵中非零元素的个数远远小于矩阵元素个数。矩阵中非零元素的个数远远小于矩阵元素个数。(2) 、稠密矩阵、稠密矩阵 一个不稀疏的矩阵。一个不稀疏的矩阵。(3) 、稀疏矩阵压缩存储方法、稀疏矩阵压缩存储方法 只存储稀疏矩阵中的非零元素，只存储稀疏矩阵中的非零元素，实现方法是实现方法是:将每个将每个非零元素用一个非零元素用一个三元组（三元组（i，j，aij）来表示，

14、则每个稀来表示，则每个稀疏矩阵可用一个疏矩阵可用一个来表示。来表示。161、三元组顺序表、三元组顺序表稀疏矩阵和对应的三元组线性表稀疏矩阵和对应的三元组线性表 001101700025000000000000190000000000000000370000000005012345671234567(1,3,11),(1,5,17),(2,2,25),(4,1,19),(6,4,37),(7,7,50)若把稀疏矩阵的三元组线性表按顺序存储结构存储，则称为稀疏矩阵的三元若把稀疏矩阵的三元组线性表按顺序存储结构存储，则称为稀疏矩阵的三元组顺序表。组顺序表。17三元组表表示的稀疏矩阵转置三元组表表示的

15、稀疏矩阵转置1818稀疏矩阵的转置 Tij= Mji 0 12 9 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14 0 0 24 0 0 0 0 18 0 0 0 0 0 0 -3 0 012 0 0 0 18 9 0 0 24 0 0 0 0 0 0 0 18 0 0 0 0 0 14 0 0566121213931-336144324521865613-3211225183193424631419稀疏矩阵用三元组表示的转置行数和列数交换i、j的值相互交换重排三元组之间的次序566121213931-336144324521865613-32112251831934246314

16、656211231913-363143424251820用三元组表示，求稀疏矩阵M的转置矩阵TM566121213931-3361443245218T1.行数和列数交换，总个数不变: T.m = M.n; T.n = M.m; T.t = M.t;2.让q定位T中的第一条记录: q=1;6 5 6q21M566121213931-3361443245218T3.让col取M的每一列: for(col=1; col=M.n; col+) 4.让p扫描三元组M的每一条记录: for (p=1; p=M.t; p+)6 5 6qcol = 1p22M566121213931-3361443245218T6 5 6qcol = 1p5.如果p指向的记录的j下标与col相等: if (M.datap.j = col)ije23M566121213931-3361443245218T6 5 6qcol = 1p6.把M中的记录p复制到T中的记录q: T.dataq.i = M.datap.j; T.dataq.j = M.datap.i; T.dataq.v = M.datap.v;7.让q下移: