数据结构第5章数组与广义表.

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

1、数据结构（C语言版） 第5章 数组与广义表 本章主要知识点 数组 特殊矩阵的压缩存储 稀疏矩阵 广义表 数组 1.数组的定义 数组是由类型相同的数据元素构成 的 有序集合，每个数据元素称为一个数组 元 素（简称元素）,每个元素受个线性关系 的约束，每个元素在个线性关系中的序 号 称为该元素的下标，并称该数组为维数 组，称为该数组的维数。 特点: （1）数组中的数据元素具有相同数据类型 。 （2）数组是一种随机存取结构，给定一 组下标，就可以访问与其对应的数据元 素。 （3）数组中的数据元素个数是固定的。 一旦定义了数组，它的维数和元素数目 也就确定了。 数组中通常只有两种操作： (1) 存取：

2、给定一组下标，存取相应的数 据元素； (2) 修改：给定一组下标，修改相应的数 据元素的值。 2.数组的顺序表示 数组一般都是采用顺序存储的方法来表示。 数组通常有两种顺序存储方式： (1) 行优先顺序(Row Major Order) ：将 数组元素按行排列，第i+1个行向量紧接在 第i个行向量后面。对二维数组，按行优 先顺序存储的线性序列为： (2) 列优先顺序(Column Major Order) ：将数组元素按列向量排列，第j+1个 列向量紧接在第j个列向量之后，对二 维数组，按列优先顺序存储的线性序 列为： 设有二维数组A=(aij)mn，若每个元 素占用L个存储单元，a11作为该

3、数组的第 一个元素，LOCa11表示元素a11的首地 址，即数组的首地址。 以“行优先顺序”存储: (1) 第1行中的每个元素对应的(首)地址是： LOCa1j=LOCa11+(j-1) L (2) 第2行中的每个元素对应的(首)地址是 ： LOCa2j=LOCa11+nL +(j-1) L (3) 第m行中的每个元素对应的(首)地址是 ： LOCamj=LOCa11+(m-1) nL +(j-1) L 二维数组中任一元素aij的(首)地址是： LOCaij=LOCa11+(i-1) n +(j-1) L 三维数组中任一元素aijk的(首)地址是： LOC(aijk)=LOCa111+(i-1

4、)np+(j- 1)p+(k-1) L n维数组中任一元素aj1j2jn的(首)地址是： LOCaj1j2jn=LOCa11 1+(b2bn)(j1-1)+ (b3bn) (j2- 1)+ + bn(jn-1-1)+ (jn-1) L 以“列优先顺序”存储： (1) 第1列中的每个元素对应的(首)地址是 ： LOCaj1=LOCa11+(j-1) L (2) 第2列中的每个元素对应的(首)地址 是： LOCaj2=LOCa11+mL +(j-1) L (3) 第n列中的每个元素对应的(首)地址 是： LOCajn=LOCa11+ (n-1) mL +(j -1) L 二维数组中任一元素aij的

5、(首)地址是： LOCaij=LOCa11+(i-1)m+(j-1)L 例 若6行5列的数组以列序为主序顺序存 储，基地址为1000，每个元素占2个 存储单元，则第3行第4列的元素（假 定无第0行第0列）的地址是多少? 解 LOC(a34)= LOCa11+(3-1)6+(4- 1)2=1000+(3-1)6+(4-1)2=1030 特殊矩阵的压缩存储 矩阵：是一个由mn个元素排成的m行 （横向）n列（纵向）的表。 特殊矩阵是指元素值的排列具有一定 规律的矩阵。常见的这类矩阵有：对称 矩 阵、下（上）三角矩阵、对角线矩阵等 等。 可以利用它的规律来进行压缩存储， 即为多个值相同的元素只分配一个

6、存储 空 间，对0元素不分配存储空间，因此就不 用占用mn那么多的空间。 1 对称矩阵 若一个n阶方阵A=(aij)nn中的元素满足 性质： aij=aji 其中，1i,jn且 ij，则称A为对称矩阵 。 对称矩阵关于主对角线对称，因此只 需存储上三角或下三角部分即可。 原来需要n*n个存储单元，现在只需要 n(n+1)/2个存储单元了，节约了n(n- 1)/2个存储单元。用数组 SAn(n+1)/2来压缩存储该对称矩阵 ： 下三角中的元素aij，其特点是：ij且 1in，存储到SA中后， SA中的下标k 与i、j的关系： k=i*(i-1)/2+j-1 (kn*(n+1)/2 ) 上三角中的

7、元素aij，其特点是ij ，有 ： aij=aji 上三角中的元素在SA中的对应关系： k=j*(j-1)/2+i-1 (kn*(n+1)/2 ) 2 三角矩阵 以主对角线划分，三角矩阵有上三角 和下三角两种。如图所示。其中(a)图为 下 三角矩阵：主对角线以上均为同一个常 数；(b)图为上三角矩阵，主对角线以下 均 为同一个常数。 (1) 下三角矩阵 三角矩阵中的重复元素c可共享一个 存储空间，其余的元素正好有n(n+1)/2 个，因此，三角矩阵可压缩存储到向量 SA0n(n+1)/2中，其中c存放在向量的 最后1个分量SAn(n+1)/2中。 该存储方式可节约n*(n-1)/2-1个存 储

8、 单元。 SAk与aji 的对应关系： (2) 上三角矩阵 对于上三角矩阵，存储思想与下三角 类似，以行为主序顺序存储上三角部分 ， 最后存储对角线下方的常量。 SAk 与aji 的对应关系: 3 对角矩阵 在一个矩阵中，除了主对角线和主对 角 线上或下方若干条对角线上的元素之外 ， 其余元素皆为零或常数。即所有的非零 元 素集中在以主对角线为了中心的带状区 域 中。 以三对角矩阵为例，需存储的元素个数 总量为3n-2。 若存入的数组空间为B1.3n-2中，元 素 在一维数组B中的下标k和元素在矩阵中的 下标i和j的对应关系为： k=2(i-1)+j (1i,jn; 1k3n-2) 稀疏矩阵

9、设矩阵A是一个 m 行 n 列的矩阵含 t 个非零元素，则称 为矩阵的稀疏 因 子。如果某一矩阵的稀疏因子满足 0.05时称为稀疏矩阵。 一个稀疏矩阵里存在大量的零元素， 若 以常规方法，即以二维数组来存储稀疏 矩 阵时产生如下问题: 零值元素占了很多空间; 2) 如果进行计算，则会进行很多和零值 的运算，如是除法，还需判别除数是否 为 零。 稀疏矩阵的三元组存储 稀疏矩阵中存在大量的零元素，这些 零元素并不需要存储，所以采用压缩存 储时，只存储非零元素。为了能准确定 位该非零元素，必须存储非零元素的行 下标值、列下标值、元素值。因此，可 以用一个三元组(i, j, aij)来唯一确定稀 疏矩

10、阵的一个非零元素。 三元组结点定义： #define MAX_SIZE 101 typedef int elemtype ; typedef struct int row ; /*行下标*/ int col ; /*列下标*/ elemtype value; /*元素值*/ Triple ; 三元组顺序表定义： typedef struct int rn ; /*行数*/ int cn ; /*列数*/ int tn ; /*非0元素个数*/ Triple dataMAX_SIZE ; TMatrix ; 在压缩存储方式下如何实现稀疏 矩阵的转置操作呢？ 基本算法思想： 将矩阵的行、列下标值交

11、换； 重排三元组表中元素的顺序，即交换 后仍然是按行优先顺序排序的。 方法一： 算法思想：按稀疏矩阵A的三元组表 a.data中的列次序依次找到相应的三元组 存入b.data。每找到转置后矩阵的一个三 元组，需从头至尾扫描整个三元组表a.data 。 void TransMatrix(TMatrix a , TMatrix b) int p , q , col ; b.rn= ; =a.rn ; b.tn=a.tn ; if (b.tn=0) printf(“ The Matrix A=0n” ); else q=0; for (col=1; col= ; col+) for (p=0 ;pa

12、.tn ; p+) if (a.datap.col=col) b.dataq.row=a.datap.col ; b.dataq.col=a.datap.row ; b.dataq.value=a.datap.value; q+ ; 算法的时间复杂度为O(cntn) 传统矩阵的转置算法为： for(col=1; col=n ;+col) for(row=0 ; row=m ;+row) bcolrow=arowcol ; 时间复杂度为O(nm) 当非零元素的个数tn和mn同数量级时，算法 TransMatrix的时间复杂度为O(mn2)。 方法二(快速转置的算法) 算法思想：一遍扫描三元组表A

13、.data， 将 每个元素放到转置后的三元组表B.data 的 正确位置上 。 为了做到这一点，需求出矩阵A中每 列 第一个非零元的位置和每列非零元素的 个 数。为此，增加存放每列非零元素个数 的 一维数组number和每列第一个非零元 素 在B中位置的一维数组position 。 TSMatrix FastTransMatrix(TSMatrix A, TSMatrix B) B.m=A.n; B.n=A.m; B.len=A.len; if(A.len) for(j=1;j=A.n;j+) numberj=0; for(t=1;t=A.len;t+) numberA.datat.col+; position1=1; for(j=2;j=1)非空，则a1是LS的表 头，其余元素组成的表(a2,a3,an)称为LS的 表尾。 （1）A=（） 表A是一个空表，其长度为零。 （2）B=（e） 表B只有一个原子e，B的长度为1。 （3）C=（a,(b,c) 表C的长度为2，两个元素分别为原子a和 子表(b,c)。 （4）D=（A，B，C） 表D的长度为3，三个元素都是广义表。 （5）E=（a, E） 表E是一个递归的表，长度为2，相当于 一个无限的广义表E=(a,(a