数据结构第5章数组和广义表课件

1、数据结构第5章数组和广义表5.1 数组类型 5.1.1 数组的类型定义数组的类型定义ADT Array 数据对象：数据对象：Daj1,j2,.,ji ,.jN |ji =0,., bi-1, i=1,2,.,N,称 N(0) 为数组的维数， bi为数组第 i 维的长度，ji 为数组元素的第i维下标，a j1,.,jN ElemSet 数据关系：数据关系：RR1, R2, ., RNRi |0jkbk-1, 1kN 且k= i,0ji bi-2,a j1,.,ji,.,jn , a j1,.ji+1,.,jn D, i=2,.,N 数据结构第5章数组和广义表基本操作：基本操作：InitArray

2、(&A, n, bound1, ., boundn)操作结果：若维数 n 和各维长度合法则构造相应数组 A。 DestroyArray(&A)初始条件：数组 A 已经存在。操作结果：销毁数组 A。 Value(A, &e, index1, ., indexn)初始条件：A 是 n 维数组，e 为元素变量， n 个下标值。操作结果：若各下标不超界，则e赋值为所指定的A的元 素值，并返回OK。 Assign(&A, e, index1, ., indexn)初始条件：A 是 n 维数组，e 为元素变量，n 个下标值。操作结果：若下标不超界，则将 e 的值赋给A中指定

3、 下标的元素。 ADT Array 数据结构第5章数组和广义表5.1.2 数组的数组的顺序存储顺序存储表示表示通常有两种映象方法： “以行(序)为主(序)”的映象方法 “以列(序)为主(序)”的映象方法 如：二维数组：“以行为主“的映象方法：“以列为主“的映象方法：数据结构第5章数组和广义表 假设二维数组 Rmn 每个数据元素占L个存储地址LOC(i,j) 表示下标为 (i,j) 的数据元素的存储地址， 则 LOC(i,j) 在“以行为主”的顺序映象中的存储地址为： LOC(i,j) = LOC(0,0) + (in+j) L在“以列为主”的顺序映象中的存储地址为： LOC(i,j) = LO

4、C(0,0) + (jm+i) L基地址 或基址 数据结构第5章数组和广义表 假设三维数组 Rpmn 中每个数据元素占 L 个存储地址，并以 LOC(i,j,k) 表示下标为(i,j,k) 的数据元素的存储地址， 则该数组中任何一对下标(i,j,k) 对应的数据元素在“以行为主”的顺序映象中的存储地址为： LOC(i,j,k) = LOC(0,0,0) + (imn + jn+k)L 数据结构第5章数组和广义表5.2 矩阵的压缩存储 5.2.1 特殊矩阵的压缩存储方法特殊矩阵的压缩存储方法特殊矩阵:矩阵中值相同的元素或零元素在矩阵中的分布有一定规律。大致有这样三类特殊矩阵： 对称矩阵：若 n

5、阶方阵A中的元素满足特性aij =aji 1i, jn则称为 n 阶对称矩阵； 三角矩阵：若 n 阶方阵中下(上)三角(不包括对角线)中的元均为常量 c 或 0，则称为上(下)三角矩阵；1.对角矩阵：若n阶方阵中的非零值元都集中在以主对角线为中心的(由k条对角线组成的)带状区域中，则称为k对角矩阵。 数据结构第5章数组和广义表三角矩阵对角矩阵 对称矩阵中 n2 个元压缩存储到 n(n+1)/2 个存储空间中 假设以一维数组 san(n+1)/2 压缩存储n阶对称方阵A，则一维数组中的数据元素和方阵中的元 aij 之间存在着下列一一对应的关系： 数据结构第5章数组和广义表5.2.2 稀疏矩阵的压

6、缩存储方法稀疏矩阵的压缩存储方法 如果矩阵中只有少量的非零值元，并且这些非零值元在矩阵中的分布没有一定规律，则称为随机稀疏矩阵，简称为稀疏矩阵 假设在 m n 的矩阵中有 t 个非零值元， 令 =t /（mn），称 为矩阵的稀疏因子，则通常认定 0.05的矩阵为稀疏矩阵。 数据结构第5章数组和广义表 如何存储稀疏矩阵中的非零值元？ 仍然采用二维数组表示稀疏矩阵，它的弊病是 一、浪费空间 二、浪费时间 由此解决稀疏矩阵压缩存储的目标是： 1)尽可能减少或不存储零值元； 2)尽可能不作和零值元进行的运算； 3)便于进行矩阵运算，即易于从一对行列号 找到矩阵的元，易于找到同一行或同一列的非零值元。数

7、据结构第5章数组和广义表 一个三元组 唯一确定了矩阵A中的一个非零值元,由此可以其数据元素为上述三元组的线性表表示稀疏矩阵,并且非零元在三元组线性表中是以行为主有序排列的 例如表示矩阵 三元组线性表为：(1,3,9),(1,5,-7),(3,4,8),(4,1,5),(4,6,2),(5,2,16) 数据结构第5章数组和广义表一、三元组顺序表一、三元组顺序表 以顺序存储结构作为三元组线性表的存储结构，由此得到的稀疏矩阵的一种压缩存储方法.稀疏矩阵的三元组顺序表的结构定义稀疏矩阵的三元组顺序表的结构定义const MAXTERMS=12500; / 非零个数的最大值为12500typedef s

8、truct int i, j; / 该非零元的行号和列号ElemType e; / 该非零元的值 Triple; / 三元组typedef struct Triple dataMAXTERMS + 1; / data0 未用int rows, cols, terms;/ 矩阵的行数、列数和非零元的个数 TSMatrix;/ 三元组顺序表 数据结构第5章数组和广义表 当以三元组顺序表表示稀疏矩阵时，是否仍然便于进行运算呢？在此以“转置”运算为例讨论算法。假设前面所列举的矩阵M的转置矩阵为 T，则按照矩阵转置的定义 数据结构第5章数组和广义表M的三元组顺序表为： T 的三元组顺序表为： 转置的主要

9、操作就是要确定M中的每个非零元在T的三元组顺序表中的位序 数据结构第5章数组和广义表以下表格中的三行依次为： col M 的列号、 numcol M 中各列非零元的总数rposcol T 中每一行第一个非零元在 T.data 中的序号：rpos 中的值可递推求得：rpos1 = 1;rposcol = rposcol-1+numcol-1数据结构第5章数组和广义表由此，转置算法的操作步骤为：1.求 M 矩阵的每一列中非零元的个数；2.确定T的每一行中第一个非零元在 T.data 中的序号；3.将 M.data 中每个元素依次复制到 T.data 中相应位置。 算法算法 5.1void Fast

10、TransposeSMatrix(TSMatrix M, TSMatrix &T) / 采用三元组顺序表存储表示，求稀疏矩阵采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵的转置矩阵 TT.rows = M.cols;T.cols = M.rows;T.terms = M.terms;数据结构第5章数组和广义表 if (T.terms) for (col=1; col=M. cols; +col)numcol = 0;for (t=1; t=M. terms; +t)+numM.datat.j;/ 求 M 中每一列所含非零元的个数rpos1 = 1;for (col=2; col=M.

11、 cols; +col)rposcol = rposcol-1 + numcol-1;/ 求T中每一行的第一个非零元在T.data中的序号数据结构第5章数组和广义表 for (p=1; p=M.terms; +p) / 转置矩阵元素col = M.datap.j; q = rposcol;T.dataq.i =M.datap.j;T.dataq.j =M.datap.i;T.dataq.e =M.datap.e;+rposcol; / for / if / FastTransposeSMatrix 上述算法的时间复杂度为O (M.cols+M.terms)。 数据结构第5章数组和广义表5.3

12、广义表的定义5.3.1 广义表的定义 广义表是线性表的推广，有人称之为列表（lists）抽象数据类型定义参见教材p107 LS=（a1，a2，.，an） 表头（head）表尾（tail）LS 为广义表的名称n为广义表的长度ai可以是单个元素（原子），也可以是广义表（子表）数据结构第5章数组和广义表下面列举一些广义表的例子：1.A=（）-A是一个空表，长度为0。2.B=（e）-列表B只有一个原子e，长度为1。3.C=（a，（b，c，d）-列表C的长度为2。 两个元素分别是原子a和子表（b，c，d）。4.D=（A，B，C，）-列表D的长度为3， 三个元素都是列表广义表的深度：定义为广义表中括号的重数由上述的例子可以得出列表的三个结论： 1）列表的元素可以是子表，而子表的