《数据结构之数组与广义表课件》由会员分享，可在线阅读，更多相关《数据结构之数组与广义表课件（44页珍藏版）》请在金锄头文库上搜索。
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) + (i*
3、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 1
4、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开始.,若 i=j 时 , k=i*(i+1)/2+j 当 ij 时 , k=n*(n+1)/2 例: 元素A3, 2, 对应的地址 k=3*4/2 + 2=8,3.稀疏矩阵的压缩存储,若一个
5、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： 非0元素的行号 j： 非0元素的列号 Ai, j：非0元素的值 如上例矩阵用三元组表示成： (1,2,2), (1,3,-1), (3,1,-1
6、), (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元素个数*/ tritype datamaxn; /*非0元素的三元组表*/ tmatrix;,把M压缩后，存储成： 行数 rn 列数 cn 非0数 tn 行号 列号
7、元素值,例: 求M的转置矩阵. s: t:,基本思想： 把S转置成T，就是把S中的每一个三元组的行号和列号（row 和col）交换，并存储在T中。但是，这样的结果是按列优先存储的稀疏矩阵T，所以，还必须重新排列三元组的顺序。 由于S的列是T的行，因此，应按S中列的顺序扫描,即先扫描第1列所有非0元素，然后第2列所有非0元素,，最后得到的结果就是按行优先顺序存储的。,算法如下：Inttrmatrix(tmatrix s, t) int i, j, k; t.rn=; /*列数变行数*/ =s.rn; /*行数变列数*/ t.tn=s.tn； /*非0元素个数赋值*/,if (t.tn!=0) j
8、=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);,稀疏矩阵的十字链表 当矩阵的非零元素的位置和个数经常变动时, 三元组就不适用于稀疏矩阵的存储了. 例: A=A+B 把矩阵B加到A上, 则会产生大量的数据移动, 此时, 采用十字链
9、表存储更合适. 对一个 m*n 的稀疏矩阵, 对每一个非零元素, 用一个结点表示.,结点的结构如下:其中: row 非零元素所在行 col 非零元素所在行 value 非零元素的值 down 指向同列中的下一个非零元素 right 指向同行中的下一个非零元素,可以看出: 一个结点它既是某行链表中的一个结点, 又是某列链表中的一个结点, 所以, 称为十字链表或十字交叉链表. 除了上述结点的定义外, 还要定义链表的头结点.,链表的头结点如下:其中: r n 所在行的非零元素个数 cn 所在列的非零元素个数 tn 矩阵中非零元素的个数 down 指向该列中的第一个非零元素 right 指向该行中的第一个非零元素,
