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

1、22.3.322.3.322.3.322.3.3从逻辑结构上，数组可以看作从逻辑结构上，数组可以看作是一般线性表的扩充。一维数组是一般线性表的扩充。一维数组即为线性定义表，而二维数组可即为线性定义表，而二维数组可以为以为“其数据元素为一维数组其数据元素为一维数组（线性表）（线性表）”的线性表。依此类的线性表。依此类推，即可得到多维数组的定义。推，即可得到多维数组的定义。22.3.322.3.3以二维数组为例：以二维数组为例：22.3.322.3.322.3.322.3.322.3.322.3.3ADT Array 数据对象数据对象： D = aD = aj1 j2j1 j2jnjn| | n(

2、0)n(0)称为数组的维数，称为数组的维数， j ji i是数组元素第是数组元素第i i维的下标，维的下标， j ji i= = 0,1,0,1,b,bi i-1 , i=1,2,-1 , i=1,2,n, bi,n, bi是数组第是数组第i i维的长度，维的长度，a aj1 j2j1 j2jnjn ElemSetElemSet 数据关系数据关系： R = R1, R2, R = R1, R2, , , RnRn Ri Ri=a=| 0 0j jk k b bk k-1 -1 ，1 1 k k n n且且kiki， 0 0 j ji i b bi i-2-2， a aj1j1jijijn,jn

3、,a aj1j1ji+ji+1 1jnjnDD ,i=,i=2,2,n,n22.3.322.3.3基本操作：InitAarray( &A,n,bound1,boundn )操作结果：若维数操作结果：若维数n和各维数长度合法，和各维数长度合法，则构造相应的数组则构造相应的数组A，并返回，并返回OK。DestroyArray(&A)操作结果：销毁数组操作结果：销毁数组A。22.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.3a00 a01 a0,n-1a10 a11 a1,n-1 am-1,0 am-1,0 am-1,n-1A=二维数组的表

4、示形式二维数组的表示形式行优先顺序存储行优先顺序存储a00a01 a0n-1第第 1行行a10 a11 a1,n-1第第 2行行am-1,0 am-1,1 am-1,n-1 第第 m行行a00 a10 am-1,0第第 1列列a01 a11 am-1,1第第 2列列a0,n-1 a1,n-1 am-1,n-1第第 n列列列优先顺序存储列优先顺序存储22.3.322.3.3基地址或基址基地址或基址22.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.31 2 3

5、 1 5 -5 2 2 -13 1 6 3 4 8 4 1 -44 5 7 2 1 3 5 1 -5 2 2 -1 1 3 6 4 3 8 1 4 -4 5 4 7 22.3.322.3.31 2 3 1 5 -5 2 2 -13 1 6 3 4 8 4 1 -44 5 7 2 1 3 1 3 6 5 1 -51 4 -4 2 2 -1 2 1 3 1 3 62 2 -1 4 3 8 4 3 8 1 4 -4 5 1 -55 4 7 5 4 7 Col 1 2 3 4 5Num 0+1+1 0+1+1 0 0+1 0+1+1 cPot 1 1+2=3 3+2=5 5+0=5 5+1=6pq47

6、222.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.31 2 3 1 5 -5 2 2 -13 1 6 3 4 8 4 1 -44 5 7 2 1 3 1 3 6 5 1 -51 4 -4 2 2 -1 2 1 3 1 3 62 2 -1 4 3 8 4 3 8 1 4 -4 5 1 -55 4 7 5 4 7 Col 1 2 3 4 5Num 0+1+1 0+1+1 0 0+1 0+1+1 cPot 1 1+2=3 3+2=5 5+0=5 5+1=6pq22.3.322.3.31 2 21 5 3 2 2 -12 3 53

7、1 43 4 73 5 6 1 2 3 2 1 22 2 4 3 1 1 5 2 -2 4 3 -3 22.3.322.3.322.3.322.3.322.3.322.3.31 2 21 5 3 2 2 -12 3 53 1 43 4 73 5 6 1 2 3 2 1 22 2 4 3 1 1 5 2 -2 4 3 -3 0+4 =40+8 +(-6) =20 +(-2) +5 =30 -31 1 4 1 2 2 2 1 3 2 2 -44 1 -3 pq0+(-4) =-4 0+12+(-12) =0 ctemp22.3.322.3.322.3.322.3.322.3.322.3.322.3

8、.322.3.322.3.322.3.322.3.322.3.3 对于稀疏矩阵，当非对于稀疏矩阵，当非0元素的个数和位元素的个数和位置在操作过程中变化较大时，采用链式存置在操作过程中变化较大时，采用链式存储结构表示比三元组的线性表更方便。储结构表示比三元组的线性表更方便。 矩阵中非矩阵中非0元素的结点所含的域有：元素的结点所含的域有：行行、列列、值值、行指针行指针(指向同一行的下一个非指向同一行的下一个非0元元)、列指针列指针(指向同一列的下一个非指向同一列的下一个非0元元)。其次，十字交叉链表还有一个头结点其次，十字交叉链表还有一个头结点。22.3.322.3.30 12 0 0 00 12

9、 0 0 00 0 0 0 -40 0 0 0 -40 5 0 0 00 5 0 0 00 0 3 0 00 0 3 0 0稀疏稀疏矩阵矩阵A A) 稀疏稀疏矩阵的十字交叉链表矩阵的十字交叉链表A.cheadA.rchead 1 2 12 3 2 5 2 5 -4 4 3 3 22.3.322.3.322.3.322.3.3abecdEFD( )( )22.3.322.3.322.3.322.3.322.3.322.3.322.3.322.3.3基本操作基本操作22.3.322.3.3标志标志tag=0 tag=0 原子的值原子的值datadata 标志标志tagtag=1 =1 表头指针表头指针hphp 表尾指针表尾指针tptp 表结点：表结点：原子结点：原子结点：22.3.322.3.31 1表头表头表尾表尾0 data0 data 22.3.322.3.3a(x,y),(x)(x,y)( (x) )x(y)y( ) (x)( ) (x)( )x( )22.3.322.3.31 1L1 1(x,y)(x,y),(x)( (x)0