数据结构 2014年3月.

Presentation on theme: "数据结构 2014年3月."— Presentation transcript:

1 数据结构 2014年3月

2 第五章 数组与广义表 基本内容： 多维数组和广义表是对线性表的扩展：线性表中的数据元素本身又是一个多层次的线性表。 5.1 数组的定义
第五章　数组与广义表 　　　多维数组和广义表是对线性表的扩展：线性表中的数据元素本身又是一个多层次的线性表。 基本内容： 5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.4 广义表的定义 5.5 广义表的存储结构

3 5.1 数组的定义 ADT Array{ 数据对象：ji=0,…,bi-1,i=1,2,…,n,
5.1 数组的定义 ADT Array{ 数据对象：ji=0,…,bi-1,i=1,2,…,n, D={aj1j2…jn| n(>0)称为数组的维数，bi是数组第i维的长度，ji是数组元素的第i维下标，aj1j2…jn∈ElemSet} 数据关系：R={R1,R2,…,Rn} Ri={<aj1…ji…jn,aj1…ji+1…jn>| 0≤jk≤bk-1, 1≤k≤n 且k≠i,0≤ji≤bi-2, aj1…ji…jn,aj1…ji+1…jn∈D,i=2,…n}

4 一、二维数组的线性表理解： Amn= typedef elemtype array2[m][n]; 等价于：
可以看成是由个行向量组成的向量，也可以看成是个列向量组成的向量。在C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型，也就是说， typedef elemtype array2[m][n]; 等价于： typedef elemtype array1[n]; typedef array1 array2[m]; a0,0 a1,2 … a1,n a2,1 a2,2 … a2,n … … … … am,1 am,2 … am,n Amn=

5 二、二维数组的基本操作： 对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。

6 5.2 数组的顺序表示和实现 (1)多维数组用一维的存储单元存放需约定次序。PASCAL和C语言是以行序为主序，FORTRAN以列序为主序。
5.2 数组的顺序表示和实现 (1)多维数组用一维的存储单元存放需约定次序。PASCAL和C语言是以行序为主序，FORTRAN以列序为主序。 (2)给定维数和各维长度，数组的存储空间确定。 (3)二维数组中任一元素aij的存储地址: Loc(i,j)=Loc(0,0)+(b2*i+j)*L (4)n维数组：教材p93 Loc（j1,j2,…,jn)=Loc(0,0,…,0)+ ∑ciji 其中 cn=L, ci-1=bi*ci, 1<i≤n

7 5.3 矩阵的压缩存储 矩阵一般可用二维数组实现，特殊矩阵采用压缩存储。 压缩存储：为多个值相同的元只分配一个存储空间， 对零元不分配空间。
5.3 矩阵的压缩存储 矩阵一般可用二维数组实现，特殊矩阵采用压缩存储。 压缩存储：为多个值相同的元只分配一个存储空间， 对零元不分配空间。 特殊矩阵：值相同的元素或者零元素在矩阵中的分布有 一定规律 稀疏矩阵：非零元较零元少，且分布没有一定规律的矩 阵

8 一、特殊矩阵的存储 1、对称矩阵： 在一个n阶方阵A中，若元素满足下述性质： aij=aji0≦i,j≦n-1则称A为对称矩阵。如图5.1便是一个5阶对称矩阵。 a00 a10 a 11 a20 a a23 ……………….. an-1 0 a n-1 1 a n-1 2 …a n-1 n-1 压缩存储方法：对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间。

9 下三角矩阵中，第i行恰有i+1个元素，元素总数为：(i+1)=n(n+1)/2，将这些元素存放在一个向量sa[0
下三角矩阵中，第i行恰有i+1个元素，元素总数为：(i+1)=n(n+1)/2，将这些元素存放在一个向量sa[0..n(n+1)/2-1]中。必须在aij和sa[k]之间找一个对应关系。 若i≧j，则ai j在下三角形中。 ai j之前的i行（从第0行到第i-1行）一共有1+2+…+i=i(i+1)/2个元素，在第i行上， ai j之前恰有j个元素（即ai0,ai1,ai2,…,aij-1），因此有： k=i*(i+1)/2+j ≦k<n(n+1)/2 若i<j，则aij是在上三角矩阵中。因为aij=aji，所以只要交换上述对应关系式中的i和j即可得到： k=j*(j+1)/2+i ≦ k<n(n+1)/2

10 a00 a10 a11 a20 …… an-1 0 an-1,n-1 k= n(n-1)/ n(n-1)/2-1 例如a21和a12均存储在 sa[4]中，这是因为 k=I*(I+1)/2+J=2*(2+1)/2+1=4 2、三角矩阵 以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵如图所示，它的下三角（不包括主对角线）中的元素均为常数。下三角矩阵正好相反，它的主对角线上方均为常数，如图所示。在大多数情况下，三角矩阵常数为零。

11 a00 a01 … a 0 n a00 c … c c a11 … a 1 n a10 a11 … c ………………… …………….. c c … a n-1 n an-1 0 an-1 1 … an-1 n-1 (a)上三角矩阵 (b)下三角矩阵 以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵如图所示，它的下三角（不包括主对角线）中的元素均为常数。下三角矩阵正好相反，它的主对角线上方均为常数，如图所示。在大多数情况下，三角矩阵常数为零。

12 三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到向量sa[0
三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到向量sa[0..n(n+1)/2]中，其中c存放在向量的最后一个分量中。 上三角矩阵中，主对角线之上的第p行(0≦p<n)恰有n-p个元素，按行优先顺序存放上三角矩阵中的元素aij时，aij之前的i行一共有(n-p)=i(2n-i+1)/2 个元素，在第i行上，aij前恰好有j-i个元素：aij,aij+1,…aij-1。因此，sa[k]和aij的对应关系是： i(2n-i+1)/2+j-i 当i≦j n(n+1)/ 当i>j 下三角矩阵的存储和对称矩阵类似，sa[k]和aij对应关系是： i(i+1)/2+j i≧j n(n+1)/ i>j

13 3、对角矩阵 对角矩阵中，所有的非零元素集中在以主对角线为了中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。下图给出了一个三对角矩阵， a00 a01 a10 a11 a12 a21 a22 a23 …. ….. …. an-2 n-3 an-2 n-2 an-2 n-1 an-1 n-2 an-1 n-1

14 上例中，a34对应着sa[10]。k=2*i+j=2*3+4=10 a21对应着sa[5] k=2*2+1=5
在一个nn的三对角矩阵中，只有n+n-1+n-1个非零元素，故只需3n-2个存储单元即可，零元已不占用存储单元。故可将nn三对角矩阵A压缩存放到只有3n-2个存储单元的s向量中，假设仍按行优先顺序存放。 a00 a01 a10 a11 a12 a21 … a n-1 n-2 a n-1 n-1 K= … … 3n n-1 数组sa中的元素sa[k]与三对角带状矩阵中的元素aij存在一一对应关系，在aij之前有i行,共有3*i-1个非零元素，在第i行，有j-i+1个非零元素，这样，非零元素aij的地址为：LOC(i,j)=LOC(0,0)+[3*i-1+(j-i+1)]*d =LOC(0,0)+(2i+j)*d 上例中，a34对应着sa[10]。k=2*i+j=2*3+4=10 a21对应着sa[5] k=2*2+1=5 由此，我们称sa[0..3*n-2]是阶三对角带状矩阵A的压缩存储表示。

15 二、稀疏矩阵的存储 1．三元组表 在压缩存放稀疏矩阵的非零元同时，若还存放此非零元所在的行号和列号，则称为三元组表法，即称稀疏矩阵可用三元组表进行压缩存储，但它是一种顺序存储（按行优先顺序存放）。一个非零元有行号、列号、值，为一个三元组，整个稀疏矩阵中非零元的三元组合起来称为三元组表。

16 此时，数据类型可描述如下： #define MAXSIZE 12500 /*定义非零元的最大数目*/
Typedef struct { /*定义三元组*/ int i , j; /*非零元行、列号*/ Elemtype e; /*非零元值*/ }Triple; Typedef struct { /*定义稀疏矩阵*/ int mu,nu,tu; /*稀疏矩阵行、列数、非零元个数*/ Triple data[MAXSIZE+1]; /*三元组表*/ }TSMatrix;

17 M= T= TSMatrix M； M.mu=７ m.nu=６ m.tu=8 m.data[]= 3 1 -3 6 1 15 2 1 12
–7 – M= T= 图5.4 稀疏矩阵M和转置矩阵T TSMatrix M； M.mu=７ m.nu=６ m.tu=8 m.data[]= i j v 1 2 3 4 5 6 7 TSMatrix M； M.mu=6 m.nu=7 m.tu=8 m.data[]= i j v 1 2 3 4 5 6 7 转置

18 2、举例：如何求矩阵的转置矩阵？ （1）普通转置：基本思想是：对A中的每一列col(0≦col≦n-1)，通过从头至尾扫描三元表a.data，找出所有列号等于col的那些三元组，将它们的行号和列号互换后依次放入b.data中，即可得到B的按行优先的压缩存储表示。 Status TransposeSMatrix(TSMatrix M, TSMatrix &T) { // 采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵T int p, q, col; T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; if (T.tu) { q = 1; for (col=1; col<=M.nu; ++col) for (p=1; p<=M.tu; ++p) if (M.data[p].j == col) { T.data[q].i=M.data[p].j;T.data[q].j =M.data[p].i; T.data[q].e =M.data[p].e; ++q; } } return OK;

19 （2）快速转置 基本思想： 先求得矩阵M中的每一列中非零元素的个数，预先确定出矩阵M中的每一列的第一个非零元素在数组B中应在的位置，（其中第1列第1个非零元在数组B中也是第1个位置，矩阵M中每一列的第一个非零元素在数组B中的位置等于前一列第一个非零元素的位置加上前列非零元素的个数。），这样，顺序扫描一遍数组A就可以把所有元素放到数组B中恰当的位置。为此，需要设置两个一维数组num[0..n]和cpot[0..n]，num[0..n]：统计M中每列非零元素的个数，num[col]的值可以由A的第二列求得。cpot[0..n]：由递推关系得出M中的每列第一个非零元素在B中的位置。

20 算法通过cpot数组建立位置对应关系： cpot[1]=1 cpot[col]=cpot[col-1]+num[col-1] 2<=cpl<=a.n 例如：图中的矩阵M和相应的三元组A可以求得num[col]和 cpot[col]的值如下： col num[col] cpot[col]

21 Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T) {// 采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵T
int col, t, p, q; int num[20], cpot[20]; T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; if (T.tu) { for (col=1; col<=M.nu; ++col) num[col] = 0; for (t=1; t<=M.tu; ++t) // 求 M 中每一列所含非零元的个数 ++num[M.data[t].j]; cpot[1] = 1; // 求 M 中每一列的第一个非零元在 b.data 中的序号 for (col=2; col<=M.nu; ++col) cpot[col] = cpot[col-1]+num[col-1]; for (p=1; p<=M.tu; ++p) { col = M.data[p].j; q = cpot[col]; T.data[q].i =M.data[p].j; T.data[q].j =M.data[p].i; T.data[q].e =M.data[p].e; ++cpot[col]; } // for } // if return OK; } // FastTransposeSMatrix

22 3、十字链表---数组的链式存储 （1）当矩阵中非零元素的个数和位置经过运算后变化较大时，就不宜采用顺序存储结构，而应采用链式存储结构来表示三元组。 （2）稀疏矩阵的链接表示采用十字链表：行链表与列链表十字交叉。 （3）行链表与列链表都是带表头结点的循环链表。用表头结点表征是第几行，第几列。

23 right——指向同一行中下一个非零元素的指针（向右域）
元素结点 right——指向同一行中下一个非零元素的指针（向右域） down——指向同一列中下一个非零元素的指针（向下域） 表头结点 行表头结点 列表头结点 next用于表示头结点的链接 i j val down right

24 1 3 4 5 2 -1 ^

25 5.4 广义表的定义 一、定义 1、广义表是n(n>=0)个元素a1,a2,a3,…,an的有限序列，其中ai或者是原子项，或者是一个广义表。通常记作LS=（a1,a2,a3,…,an)。LS是广义表的名字，n为它的长度。若ai是广义表，则称它为LS的子表。 例如: A = ( ) F = (d, (e)) D = ((a,(b,c)), F) C = (A, D, F) B = (a, B) = (a, (a, (a,  , ) ) )

26 （1）表头 Head(LS) =1 第1个元素本身
二、广义表的运算 （1）表头 Head(LS) =1 第1个元素本身 （2）表尾 Tail(LS) = ( 2, …, n) 除第1个元素外其余元素所构成的广义表。 例如: D = ( E, F ) = ((a, (b, c))，F ) Head( D ) = E Tail( D ) = ( F ) Head( E ) = a Tail( E ) = ( ( b, c) ) Head( (( b, c)) ) = ( b, c) Tail( (( b, c)) ) = ( ) Head( ( b, c) ) = b Tail( ( b, c) ) = ( c ) Head( ( c ) ) = c Tail( ( c ) ) = ( )

27 三、广义表的存储结构 表结点: tag=1 hp tp 原子结点： tag=0 data 表头、表尾分析法:空表 ls = NIL
指向表头的指针 指向表尾的指针 非空表 ls

28 L=(a,(x,y),((x))) L 1 1 1  1   1  0 a 1  0 x

29 作业： 5-1 按行优先存储方式，写出二维数组A[10][8]在内存中的地址计算公式（假设每个数组元素占用L个字节的内存单元，a[0][0]的内存地址为Loc(a[0][0])）。 5-2 按列优先存储方式，写出二维数组A[10][8]在内存中的地址计算公式（假设每个数组元素占用L个字节的内存单元，a[0][0]的内存地址为Loc(a[0][0])）。 5-3 设有上三角矩阵Ann，它的下三角部分全为0，将其上三角元素按行优先存储方式存入数组B[m]中(m足够大)，使得B[k]=a[i][j]，且有k=f1(i)+f2(j)+c。试推出函数f1、f2及常数c（要求f1和f2中不含常数项）。