第五章，数组和广义表.pptVIP

第五章 数组和广义表 第一节 数组的定义 数组的概念 数组是由一组个数固定，类型相同的数据元素组成的阵列。 以二维数组为例：二维数组中的每个元素都受两个线性关系的约束即行关系和列关系，在每个关系中，每个元素aij都有且仅有一个直接前趋，都有且仅有一个直接后继。 二维数组也可看作这样的线性表，其每一个数据元素也是一个线性表。 基本操作 InitArray(A,n,bound1,…,boundn)构造一个n维数组 DestroyArray(A)销毁数组A Value(A,e,index1,…,indexn)取元素值到e Assign(A,e,index1,…,indexn)存e的值到数组A 第二节 数组的顺序表示和实现 由于存储单元是一维结构，而数组是个多维的结构，则用一组连续存储单元存放数组的数据元素就有个次序约定即行列存储。 数组元素存储地址的计算 假设二维数组Am×n每个元素占用L 个存储单元， Loc(aij)为元素aij 的存储地址，Loc(a00 ) 是a00存储位置, 也是二维数组A的基址。 若以行序为主序的方式存储二维数组，则元素aij 的存储位置可由下式确定： Loc(aij ) = Loc(a00 ) +（n? i+j ) ?L 若以列序为主序的方式存储二维数组，则元素aij 的存储位置可由下式确定： Loc(aij ) = Loc(a00) +（m? j+i ) ?L 第三节 矩阵的压缩存储 矩阵是许多科学与工程计算问题中常常涉及到的一种运算对象。 一个m行n列的矩阵是一平面阵列，有m?n个元素。通常程序员是用二维数组存储矩阵。由于这种存储方法可以随机地访问矩阵的每个元素，因而能较为容易地实现矩阵的各种运算。 应用中常遇到一些阶数很高的矩阵，矩阵中有许多值相同的元素或零元素。二维数组存储矩阵会浪费很多的存储单元。因此，需要使用高效的存储方法，减少数据的存储量，即对原矩阵，根据数据分布特征进行压缩存储。 一、特殊矩阵 值相同元素或者零元素分布有一定规律的矩阵称为特殊矩阵 例如对称矩阵、上（下）三角矩阵都是特殊矩阵。 特殊矩阵压缩存储 (以对称矩阵为例) 对称矩阵是满足下面条件的n 阶矩阵: aij= aji 0? i,j? n-1 压缩存储的对称矩阵的取值算法 int get_M(int i, int j) { if(i=j) return(sa[i*(i+1)/2+j]); else return(sa[j*(j+1)/2+i]); } 二、稀疏矩阵 有较多值相同元素或较多零元素，且值相同元素或者零元素分布没有一定规律的矩阵称为稀疏矩阵。 基本操作 CreateSMatrix(M) 创建稀蔬矩阵M； DestroySMatrix(M) 销毁稀蔬矩阵M； PrintSMatrix(M) 输出稀蔬矩阵M； CopySMatrix(M,T) 复制稀蔬矩阵M到T； AddSMatrix(M,N,Q) 求Q=M+N； SubtSMatrix(M,N,Q) 求Q=M-N; MultSMatrix(M,N,Q) 求Q=M*N; TransposeSMatrix(M,T) 求M的转置阵T 稀疏矩阵的压缩存储 只存储稀疏矩阵的非零元，可由表示非零元的三元组及其行列数惟一确定(i,j,aij)。 三元组的顺序表 假设以顺序存储结构来表示三元组表，则可得稀疏矩阵的一种压缩存储方式——我们称之为三元组顺序表(行序表示)。 转置运算算法 转置运算是一种最常用的矩阵运算。对于一个 m 行 n 列的矩阵 M，它的转置矩阵 T是一个n行m列的矩阵。 例如，下图中的矩阵M和T互为转置矩阵。 算法分析： （1）将矩阵的行数和列数的值交换 （2）将每一个三元组的i 和 j相互调换 （3）重排三元组之间的次序 算法实现 十字键表存储压缩稀疏矩阵 在链表中，每个非零元可用一个含5个域的结点表示，其中i,j,e用来表示非零元的行、列、值，向右域right用以链接同一行中下一个非零元，向下域down用以链接同一列中下一个非零元。再建两个头结点分别指示行和列。 第四节 广义表的定义 概念 广义表也称为列表，是线性表的一种扩展，也是数据元素的有限序列。 记作：LS= (d0, d1, d2, …dn-1)。其中di既可以是单个元素，也可以是广义表。 说明 广义表的定义是一个递归定义，因为在描述广义表时又用到了广义表； 在线性表中数据元素是单个元素，而在广义表中， 元素可以是单个元素, 称为单元素(原子)，也可以是广义表，称为广义表的子表； n