数据结构(本)课程辅导与练习-第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开始，若知道元素a[0]的存储地址是LOC（A[0]），每个数组元素占R个存储单元，由于元素a[i]是数组元素的第i+1个元素，它之前有i个元素，而每个元素占R个存储单元，因此可求得数组元素a[j]的存储地址为： LOC（a[i]）= LOC(a[0]+i*R) 或写成 LOC（ai）= LOC(a0+i*R) 若数组的下标从1开始，则一维数组的地址计算公式为： LOC（a[i]）= LOC(a[0]+（i-1）*R) 或写成 LOC（ai）= LOC(a0+（i-1）*R)(2)二维数组元素地址的计算对于一个二维数组a[m][n]，知道第一数组元素的存储地址是LOC（a[0][0]）(数组下标从0开始),每个数组元素占R个存储单元，元素a[i][j]位于数组中第i+1行，第j+1列，在它前面有i行个元素，共占用i*n*R个存储单元。

在第i+1行上，a[i][j]前面共有j个元素，因此共占用了j*R个存储单元，所以可求得元素a[i][j]的地址LOC（A[i][j]）为： LOC（a[i][j]）= LOC（a[0][0]）+（i*n+j）* R或写成 LOC（aij）= LOC(a00+（i*n+j）*R) 若数组下标从1开始，数组元素aij的前面有i-1行，每一行的元素个数为n,在第i行中aij的前面有j-1数据元素，则二维数组的地址计算公式为： LOC（a[i][j]）= LOC（a[0][0]）+(（i-1）*n+j-1)* R或写成 LOC（aij）= LOC(a11+(（i-1）*n+j-1)* R三、特殊矩阵     　所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵常见的有对称矩阵、三角矩阵和对角矩阵等 1．对称矩阵 （1）对称矩阵    　在一个n阶方阵A中，若元素满足下述性质：        aij=aji 0≤i,j≤n-1 则称A为对称矩阵 【例】下图便是一个5阶对称矩阵。

 （2）对称矩阵的压缩存储    对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间这样，能节约近一半的存储空间 ①按"行优先顺序"存储主对角线(包括对角线)以下的元素     即按a00,a10,a11,……，an-1,0,an-1,1…，an-1,n-1次序存放在一个向量sa[0．．n(n+1)／2-1]中（下三角矩阵中，元素总数为n(n+1)／2）    其中：         sa[0]= a00 ,         sa[1] = a10 ,         ……，         sa[n(n+1)／2-1]= an-1,n-1 ②元素aij的存放位置    aij元素前有i行，一共有：i×(i+1)／2个元素；    在第i行上，aij之前恰有j个元素(即ai0，ail，…，ai,j-1)，因此有：           sa[i×(i+1)／2+j]= aij  ③aij和sa[k]之间的对应关系：    注意：若数组下标从1开始，则aij和sa[k]之间的对应关系为：2.三角矩阵  （1）三角矩阵的划分 以主对角线划分，三角矩阵有上三角矩阵和下三角矩阵两种。

①上三角矩阵    　如下图(a)所示，它的下三角(不包括主角线)中的元素均为常数c ②下三角矩阵    　与上三角矩阵相反，它的主对角线上方均为常数c，如下图(b)所示  注意：　在多数情况下，三角矩阵的常数c为零 （2）三角矩阵的压缩存储    三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n×(n+1)／2个，因此，三角矩阵可压缩存储到向量sa[0．．n(n+1)／2]中，其中c存放在向量的最后一个分量中  下三角矩阵中aij和sa[k]之间的对应关系 四、稀疏矩阵     设矩阵Am´n中有s个非零元素，若s远远小于矩阵元素的总数(即s<

2．三元组表  将表示稀疏矩阵的非零元素的三元组按行优先(或列优先)的顺序排列(跳过零元素)，并依次存放在向量中，这种稀疏矩阵的顺序存储结构称为三元组表  注意：　    以下的讨论中，均假定三元组是按行优先顺序排列的 【例】下图(a)所示的稀疏矩阵A的三元组表表示见图(b)　　　　　ijv[0]0322[1]0615[2]1111[3]1517[4]23-6[5]3539[6]4091[7]5228 矩阵M及其三元组顺序表下面讨论压缩存储结构上矩阵的转置运算    一个m×n的矩阵A，它的转置矩阵B是一个n×m的矩阵，且：         A[i][j]=B[j][i]，0≤idata置换为B的三元组表b->data ②三元组表的转置    方法一:简单地交换a->data中i和j中的内容，得到按列优先顺序存储倒b->data; 再将b->data重排成按行优先顺序的三元组表。

   方法二:由于A的列是B的行，因此，按a->data的列序转置，所得到的转置矩阵B的三元组表b->data必定是按行优先存放的   按这种方法设计的算法，其基本思想是：对A中的每一列col(0≤col≤a->n-1)，通过从头至尾扫描三元组表a->data，找出所有列号等于col的那些三元组，将它们的行号和列号互换后依次放人b->data中，即可得到B的按行优先的压缩存贮表示五、广义表    　广义表(Lists，又称列表)是线性表的推广即广义表中放松对表元素的原子限制，容许它们具有其自身结构 1．广义表定义    　广义表是n(n≥0)个元素a1，a2，…，ai，…，an的有限序列 其中：    　①ai--或者是原子或者是一个广义表　  ②广义表通常记作：              Ls=( a1，a2，…，ai，…，an)　　 ③Ls是广义表的名字，n为它的长度　 ④若ai是广义表，则称它为Ls的子表  注意：    　①广义表通常用圆括号括起来，用逗号分隔其中的元素    　②为了区分原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子    　③若广义表Ls非空(n≥1)，则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）带名字的广义表表示    如果规定任何。