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

数据结构(本)课程辅导与练习-第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]中（下三角