数据结构之数组与广义表课件.ppt

1、第5章 数组与广义表,5.1 数组,5.1.1 数组的定义 数组是由n个相同类型的元素组成的有序序列，并存储在一个连续的空间中。 数组的特点： 元素类型必须相同； 可对每一个元素随机访问, 数组中的元素个数是固定的。,数组分为一维数组和多维数组 一维数组 如: A10 (1行,共10个元素) 二维数组 如: B34 (3行4列, 共12个元素),5.1.2 数组的顺序存储,在计算机中，数组是按一定的规则存储在一个连续的地址空间中. 可以用下标随机的访问该数组的任意一个元素。 计算数组元素存储地址的公式称为寻址公式。 设数组为A，每个数组元素占k个存储单元，一旦定义了它的维数和各维的上、下界，就

2、可以得到数组中任一元素的寻址公式。,1. 一维数组的寻址公式,对于一维数组，若其第一个元素的首地址为Loc(a0)，下标为 i 的数组元素Ai的地址为Loc(ai)， 则 Loc(ai) = Loc(a0) + k * i ( 0in-1),2. 二维数组的寻址公式,二维数组分为以行为主序存储和以行为主序存储. 在C语言中，采用以行为主序存储 在FORTRAN语言中，采用以列为主序存储,设二维数组Amn，m、n分别表示数组的行数和列数，用 Loc (aij)表示数组元素Aij的地址. 设每个元素占用k个存储单元，则寻址公式为: 若以行为主序，则 Loc(ai,j) = Loc(a00) + (

3、i*n+j)*k 若以列为主序，则 Loc(ai,j) = Loc(a00) + (j*m+i)*k 注:假设数组从0开始编址.,例：二维数组A5, 6，设每一元素占32位，若以行序为主序存储， 1. 数组A共占多少个字节? 2. 若A的起始地址是1000，A2,5的地 址是多少？ 解：1. 共有30个元素 30*4=120 个字节 2. Loc2,5=loc0,0+(2*6+5)*4 =1068,5.2 特殊矩阵的压缩存储,1. 对称矩阵的压缩存储 一个n阶矩阵，满足 Ai,j=Aj,i 则称为对称矩阵。 例： 1 5 1 3 7 5 0 8 0 0 A= 1 8 9 2 6 3 0 2 5

4、 1 7 0 6 1 3,对称矩阵有n*n个元素，但只存储n*(n+1)/2个元素即可. 若以行序为主序，把下三角中的元素，存储在一个一维数组SAn*(n+1)/2 中，则 Ai,j 和SAk 的对应关系如下： 若 i=j , 则Ai, j在下三角中，Ai, j之前共有1+2+i+j = i*(i+1)/2+j 个元素，因此有 k= i*(i+1)/2 + j 注:假定矩阵的行和列从0开始, 一维数组的编址从0开始.,若 ij , 则Ai, j在上三角中，因为Ai,j=Aj,i, 所以交换上述公式中的i和j即可,因此有 k= j*(j+1)/2 + i,上页的矩阵对应的一维数组如下： 0 1

5、2 3 4 5 6 7 8 9 0 1 2 3 4 A3,0对应的地址：k=3*4/2+0=6 A2,4对应的地址：k=4*5/2+2=12,2. 三角矩阵的压缩存储,三角矩阵: 矩阵的上(下)三角(不包含主 角线)元素为同一个常数的方阵. 我们可用对称矩阵存储的思想存储之.,如数组A，有n*(n+1)/2+1个非零元素, 可以只存储n*(n+1)/2+2个元素即可. 1 0 0 0 A= 2 3 0 0 4 5 6 0 7 8 9 1 0 1 2 3 4 5 6 7 8 9 0,数组的第n*(n+1)/2 (最后一个元素）表示矩阵中的上三角元素0。 当 i=j 时 , k=i*(i+1)/2

6、+j 当 ij 时 , k=n*(n+1)/2 例: 元素A3, 2, 对应的地址 k=3*4/2 + 2=8,3.稀疏矩阵的压缩存储,若一个m*n矩阵，有s个非0元素， 记 e=s/(m*n) e 称为稀疏因子。 当 e0.05时，则称为稀疏矩阵。,例: 0 2 -1 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 4 0 M= 0 0 0 0 0 0 0 0 8 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 9 0,在稀疏矩阵中，非0元素的排列无规律，所以不能采用以前的压缩方法。 可用一个三元组（i, j, Ai, j）来存储非0元素。 其中 i：

7、非0元素的行号 j： 非0元素的列号 Ai, j：非0元素的值 如上例矩阵用三元组表示成： (1,2,2), (1,3,-1), (3,1,-1), (3,6,4), (5,2,8), (6,1,5), (7,6,9),稀疏矩阵的三元组定义如下: #define maxn typedef struct int row; /*行号*/ int col; /*列号*/ elementtype elements; /*元素的值*/ tritype; typedef struct int rn; /*矩阵的行数*/ int cn; /*矩阵的列数*/ int tn; /*矩阵的非0元素个数*/ tri

8、type datamaxn; /*非0元素的三元组表*/ tmatrix;,把M压缩后，存储成： 行数 rn 列数 cn 非0数 tn 行号 列号 元素值,例: 求M的转置矩阵. s: t:,基本思想： 把S转置成T，就是把S中的每一个三元组的行号和列号（row 和col）交换，并存储在T中。但是，这样的结果是按列优先存储的稀疏矩阵T，所以，还必须重新排列三元组的顺序。 由于S的列是T的行，因此，应按S中列的顺序扫描,即先扫描第1列所有非0元素，然后第2列所有非0元素,，最后得到的结果就是按行优先顺序存储的。,算法如下： Inttrmatrix(tmatrix s, t) int i, j,

9、k; t.rn=; /*列数变行数*/ =s.rn; /*行数变列数*/ t.tn=s.tn； /*非0元素个数赋值*/,if (t.tn!=0) j=0; /*三元组T（目的地）中的位置 for (i=1; i=; i+) /*为列数 for (k=0; ks.tn; k+) /*s.tn为非0元素个数 if(s.datak.col=i) /*若列号为I, 则置换 t.dataj.row=s.datak.col; t.dataj.col=s.datak.row; t.dataj.element=s.datak.element; j+; ; return(0); ,稀疏矩阵的十字链表 当矩阵的

10、非零元素的位置和个数经常变动时, 三元组就不适用于稀疏矩阵的存储了. 例: A=A+B 把矩阵B加到A上, 则会产生大量的数据移动, 此时, 采用十字链表存储更合适. 对一个 m*n 的稀疏矩阵, 对每一个非零元素, 用一个结点表示.,结点的结构如下: 其中: row 非零元素所在行 col 非零元素所在行 value 非零元素的值 down 指向同列中的下一个非零元素 right 指向同行中的下一个非零元素,可以看出: 一个结点它既是某行链表中的一个结点, 又是某列链表中的一个结点, 所以, 称为十字链表或十字交叉链表. 除了上述结点的定义外, 还要定义链表的头结点.,链表的头结点如下: 其

11、中: r n 所在行的非零元素个数 cn 所在列的非零元素个数 tn 矩阵中非零元素的个数 down 指向该列中的第一个非零元素 right 指向该行中的第一个非零元素,其结点的C语言定义如下: #define max Typedef struct node int row; int col; Elementtype value; struct node *down; struct node *right; Nnode;,Typedef struct int rn; int cn; int tn; Nnode *rhead; Nnode *chead; crosstype;,例: 2 0 0

12、4 M= 0 -2 0 0 1 0 0 0 其三元组为: (1,1,2), (1,4,4), (2,2,-2), (3,1,1,) 其十字链表为: .,5.3 广义表,广义表的定义 线性表中的数据元素的类型必须是相同的，而且必须是原子项。如果允许表中的元素具有自身的结构，就形成了广义表。,广义表是有n个元素组成的有穷序列 L=(a1,a2,an) 其中 n为广义表的长度, 若ai是单个元素, 则称ai为原子, 若ai是也是广义表, 则称ai为子表, 若L为非空表, 则称 a1 为L的表头(head), 其余元素组成的表(a2,an) 为L的 表尾(tail).,广义表的深度：广义表中括号的层数

13、。 约定: 大写字母表示广义表(子表) 小写字母表示单个元素(原子),例：A=( ) 空表，长度为0, B=(b, c) 长度为2， C=(a, (d, e, f) 长度为2，第一个元素 为原子a, 第二个元素为子表(d,e,f), D=(A,B,C) 长度为3，3个元素都是广 义表A, B, C , 代入后, 得 D=( ), (b, c), (a, (d, e, f) E=(a, E) 长度为2，是一个递归表, 也可以表示成 E=(a, (a, (a, ),广义表的树形表示: 可以看出： 1. 广义表的元素可以是原子项，也可以是广义表。 即广义表的元素类型不同。 2. 广义表是可以共享的。

14、如广义表A，B，C为E 的子表，那么，在E中就不必列出子表的值， 、 可以通过广义的名称来引用。 3. 广义表可以是递归表。 4. 广义表的表头可以是原子项，也可以是广义表。 ，但其尾必须是广义表。,广义表的存储 由于广义表的元素的类型不同, 可以是原子,也可以是广义表, 因此不能用顺序结构存储, 通常采用链式存储结构, 每个元素用一个结构表示. 采用两种结点: 一是表示原子的结点:,二是表示子表的结点: 其中 hp 指向表头的指针 tp 指向表尾的指针,其定义如下: Typedef struct glnode int tag; Union datatype data; structstruc

15、t glnode *hp, struct glnode *tp ; glist; 例: 广义表的链式存储,广义表的操作 Gethead(L):求广义表的头, 简写成H(L), Gettail(L):求广义表的尾, 简写成T(L), 例: A=( ), B=(b, c), C=(a, (d, e, f), D=(A,B,C) Gethead(B)=b Gettail(B)=(c) Gethead(C)=a Gettail(C)=(d,e,f) Gethead(D)=A Gettail(D)=(B,C),又：gettail(a,b,c)=(b, c) gethead(a, b, c), (d, e, f)=(a, b, c) gettail( (a, b, c), (d, e, f )=(d, e, f) T (H (d, e, f) =T (d, e, f)=(e, f),取表头算法: Glist gethead(glist p) if(!p) printf(“空表”); return(null); Return(p-hp): ,取表尾算法: Glist gettail(g