数据结构(本)课程辅导与练习-第5章.doc

数据结构(本)课程辅导与练习-第5章第5章 数组和广义表数组和广义表都是特殊的线性表，也是较常用的数据结构类型。一、相关术语数组、二维数组、特殊矩阵、对称矩阵、对角矩阵、稀疏矩阵、广义表、原子、子表、表头、表尾二、数组1.数组（向量）常用数据类型 一维数组（向量）是存储于计算机的连续存储空间中的多个具有统一类型的数据元素。同一数组的不同元素通过不同的下标标识。 （a1,a2,an) 2.二维数组 二维数组Amn可视为由m个行向量组成的向量，或由n个列向量组成的向量。 二维数组中的每个元素aij既属于第i行的行向量，又属于第j列的列向量。 3.多维数组 三维数组Amnp可视为以二维数组为数据元素的向量。四维数组可视为以三维数组为数据元素的向量 三维数组中的每个元素aijk都属于三个向量。四维数组中的每个元素都属于四个向量 4.数组的顺序存储方式 由于计算机内存是一维的，多维数组的元素应排成线性序列后存人存储器。数组一般不做插入和删除操作，即结构中元素个数和元素间关系不变化。一般采用顺序存储方法表示数组。 （1）行优先顺序 将数组元素按行向量排列，第i+1个行向量紧接在第i个行向量后面。【例】二维数组Amn的按行优先存储的线性序列为： a11,a12,a1n,a21,a22,a2n,，am1,am2,，amn 注意： PASCAL和C语言中，数组按行优先顺序存储。 （2）列优先顺序 将数组元素按列向量排列，第i+1个列向量紧接在第i个列向量后面。【例】二维数组Amn的按列优先存储的线性序列为： a11,a21,am1,a12,a22,am2,，a1n,a2n,，amn 注意： FORTRAN语言中，数组按列优先顺序存储。 5.数组元素的地址计算公式 （1）一维数组元素地址的计算在C语言中，数组的下标从0开始，若知道元素a0的存储地址是LOC（A0），每个数组元素占R个存储单元，由于元素ai是数组元素的第i+1个元素，它之前有i个元素，而每个元素占R个存储单元，因此可求得数组元素aj的存储地址为： LOC（ai）= LOC(a0+i*R) 或写成 LOC（ai）= LOC(a0+i*R) 若数组的下标从1开始，则一维数组的地址计算公式为： LOC（ai）= LOC(a0+（i-1）*R) 或写成 LOC（ai）= LOC(a0+（i-1）*R)(2)二维数组元素地址的计算对于一个二维数组amn，知道第一数组元素的存储地址是LOC（a00）(数组下标从0开始),每个数组元素占R个存储单元，元素aij位于数组中第i+1行，第j+1列，在它前面有i行个元素，共占用i*n*R个存储单元。在第i+1行上，aij前面共有j个元素，因此共占用了j*R个存储单元，所以可求得元素aij的地址LOC（Aij）为： LOC（aij）= LOC（a00）+（i*n+j）* R或写成 LOC（aij）= LOC(a00+（i*n+j）*R) 若数组下标从1开始，数组元素aij的前面有i-1行，每一行的元素个数为n,在第i行中aij的前面有j-1数据元素，则二维数组的地址计算公式为： LOC（aij）= LOC（a00）+(（i-1）*n+j-1)* R或写成 LOC（aij）= LOC(a11+(（i-1）*n+j-1)* R三、特殊矩阵 所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。常见的有对称矩阵、三角矩阵和对角矩阵等。 1对称矩阵 （1）对称矩阵 在一个n阶方阵A中，若元素满足下述性质： aij=aji 0i,jn-1 则称A为对称矩阵。 【例】下图便是一个5阶对称矩阵。（2）对称矩阵的压缩存储 对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间。这样，能节约近一半的存储空间。 按行优先顺序存储主对角线(包括对角线)以下的元素 即按a00,a10,a11,，an-1,0,an-1,1，an-1,n-1次序存放在一个向量sa0n(n+1)2-1中（下三角矩阵中，元素总数为n(n+1)2）。 其中： sa0= a00 , sa1 = a10 , ， san(n+1)2-1= an-1,n-1 元素aij的存放位置 aij元素前有i行，一共有：i(i+1)2个元素；在第i行上，aij之前恰有j个元素(即ai0，ail，ai,j-1)，因此有： sai(i+1)2+j= aij aij和sak之间的对应关系： 注意：若数组下标从1开始，则aij和sak之间的对应关系为：2.三角矩阵（1）三角矩阵的划分以主对角线划分，三角矩阵有上三角矩阵和下三角矩阵两种。 上三角矩阵 如下图(a)所示，它的下三角(不包括主角线)中的元素均为常数c。 下三角矩阵 与上三角矩阵相反，它的主对角线上方均为常数c，如下图(b)所示。 注意：在多数情况下，三角矩阵的常数c为零。 （2）三角矩阵的压缩存储 三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)2个，因此，三角矩阵可压缩存储到向量sa0n(n+1)2中，其中c存放在向量的最后一个分量中。 下三角矩阵中aij和sak之间的对应关系 四、稀疏矩阵 设矩阵Amn中有s个非零元素，若s远远小于矩阵元素的总数(即smn)，则称A为稀疏矩阵。 1稀疏矩阵的压缩存储 为了节省存储单元，可只存储非零元素。由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须存储非零元素所在的行号、列号，才能迅速确定一个非零元素是矩阵中的哪一个元素。稀疏矩阵的压缩存储会失去随机存取功能。 其中每一个非零元素所在的行号、列号和值组成一个三元组(i，j，aij)，并由此三元组惟一确定。 稀疏矩阵进行压缩存储通常有两类方法：顺序存储和链式存储。 2三元组表 将表示稀疏矩阵的非零元素的三元组按行优先(或列优先)的顺序排列(跳过零元素)，并依次存放在向量中，这种稀疏矩阵的顺序存储结构称为三元组表。 注意： 以下的讨论中，均假定三元组是按行优先顺序排列的。 【例】下图(a)所示的稀疏矩阵A的三元组表表示见图(b)ijv00322106152111131517423-6535396409175228 矩阵M及其三元组顺序表下面讨论压缩存储结构上矩阵的转置运算 一个mn的矩阵A，它的转置矩阵B是一个nm的矩阵，且： Aij=Bji，0im，0jdata置换为B的三元组表b-data。 三元组表的转置 方法一:简单地交换a-data中i和j中的内容，得到按列优先顺序存储倒b-data; 再将b-data重排成按行优先顺序的三元组表。方法二:由于A的列是B的行，因此，按a-data的列序转置，所得到的转置矩阵B的三元组表b-data必定是按行优先存放的。按这种方法设计的算法，其基本思想是：对A中的每一列col(0cola-n-1)，通过从头至尾扫描三元组表a-data，找出所有列号等于col的那些三元组，将它们的行号和列号互换后依次放人b-data中，即可得到B的按行优先的压缩存贮表示。五、广义表 广义表(Lists，又称列表)是线性表的推广。即广义表中放松对表元素的原子限制，容许它们具有其自身结构。 1广义表定义 广义表是n(n0)个元素a1，a2，ai，an的有限序列。其中： ai-或者是原子或者是一个广义表。 广义表通常记作： Ls=( a1，a2，ai，an)。Ls是广义表的名字，n为它的长度。 若ai是广义表，则称它为Ls的子表。 注意： 广义表通常用圆括号括起来，用逗号分隔其中的元素。 为了区分原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。 若广义表Ls非空(n1)，则al是LS的表头，其余元素组成的表(a2，a3，an)称为Ls的表尾。 广义表是递归定义的 2广义表表示 （1）广义表常用表示 E=() E是一个空表，其长度为0。 L=(a，b) L是长度为2的广义表，它的两个元素都是原子，因此它是一个线性表 A=(x，L)=(x，(a，b) A是长度为2的广义表，第一个元素是原子x，第二个元素是子表L。 B=(A，y)=(x，(a，b)，y) B是长度为2的广义表，第一个元素是子表A，第二个元素是原子y。 C=(A，B)=(x，(a，b)，(x，(a，b)，y) C的长度为2，两个元素都是子表。 D=(a，D)=(a，(a，(a，() D的长度为2，第一个元素是原子，第二个元素是D自身，展开后它是一个无限的广义表。 （2）广义表的深度一个表的深度是指表展开后所含括号的层数。 【例】表L、A、B、C的深度为分别为1、2、3、4，表D的深度为。 （3）带名字的广义表表示 如果规定任何表都是有名字的，为了既表明每个表的名字，又说明它的组成，则可以在每个表的前面冠以该表的名字，于是上例中的各表又可以写成：E()L(a，b)A(x，L(a，b)B(A(x，L(a，b)，y)C(A(x，l(a，b)，B(A(x，L(a，b)，y)D(a，D(a，D() 3广义表运算 由于广义表是对线性表和树的推广，并且具有共享和递归特性的广义表可以和有向图(见 第7章)建立对应，因此广义表的大部分运算与这些数据结构上的运算类似。在此，只讨论广义表的两个特殊的基本运算：取表头head(Ls)和取表尾tail(Ls)。 根据表头、表尾的定义可知：任何一个非空广义表的表头是表中第一个元素，它可以是原子，也可以是子表，而其表尾必定是子表。 【例】 head(L)=a， tail(L)=(b) head(B)=A， tail(B)=(y) 由于tail(L)是非空表，可继续分解得到： head(tail(L)=b， tail(tail(L)=() 对非空表A和(y)，也可继续分解。六、练习题单项选择题1.一维数组A采用顺序存储结构，每个元素占用6个字节，第6个元素的存储地址为100，则该数组的首地址是（ ）。A64 B28C70 D902稀疏矩阵采用压缩存储的目的主要是（ ）。A表达变得简单 B对矩阵元素的存取变得简单 C去掉矩阵中的多余元素 D减少不必要的存储空间的开销3一个非空广义表的表头（ ）。 A不可能是原子 B只能是子表 C只能是原子 D可以是子表或原子 4常对数组进行的两种基本操作是（ ）。A建立与删除 B索引与、和修改C查找和修改 D查找与索引5. 设二维数组A56按行优先顺序存储在内存中，已知A00 起始地址为1000，每个