数据结构第五章数组稀疏矩阵 和广 义表.ppt

《数据结构第五章数组稀疏矩阵 和广 义表.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构第五章数组、特殊矩阵和广义表重庆一中葛静数组的逻辑结构一维数组就是一个线性表二维数组可以看成是数组元素为一维数组的一维数组三维数组可以看成是数组元素为二维数组的一维数组N维数组可以看成是数组元素为n-1维数组的一维数组由此：数组是一种抽象数据结构，它一旦被规定，其每一维的大小、上下界即被规定。通过数组元素的唯一下标来取数组元素，完成，数组元素的取值、赋值操作。数组的物理结构（存储映像）注意：内存的地址空间是一维状态，即连续的。一维数组可以直接存储，那多维数组呢？如何把一个多维下标映射成一维下标？行优先：即先行后列，如：b

2、asicpascalc列优先：即先列后行，如：fortranA11A12A13A21A22A23A11A12A13A21A22A23行优先存储：A11A21A12A22A13A23列优先存储：计算数组元素的存储地址？已知：数组存储的起始地址（基地址）pos(A11)，每个数组元素占P个单元（内存按字节编址），求AijAij之前有i-1行,j-1列，故Aij=pos(A11)+((i-1)*n+(j-1))*pA11A12…A1nA21A22…A2n…Ai1…Aiji-1行j-1列推而广之：三维数组A[b..c][d..e][

3、f..g]的pos(A111)和P已知。Aijk=pos(A111)+((i-b)*(e-d+1)*(g-f+1)+(j-d)*(g-f+1)+k-f)*pAijki-1稀疏矩阵稀疏矩阵：矩阵中多数元素为0的矩阵。二维数组存储的缺点：浪费空间，访问耗时。故有：1、稀疏矩阵的三元组存储2、稀疏矩阵的链接存储稀疏矩阵的三元组存储三元组：（5，5，4），（2，5，1），（3，1，6），（4，2，3），（5，4，-4）第一组数（5，5，4），表示5行5列，4个非零元素。后面的（2，5，1），表示第2行第5列上的数是10000000001

4、000003000000-401234552345551244163-4稀疏矩阵的链式存储就是把三元组线性表进行链接存储1、结点类型可定义为：Typematnode=recordrow,col:integer;val:elemtype;next:^matnode;end;1220201000301000003000200-401412332512、把具有相同行号的三元组节点顺序链接成一个单链表，每行一个单链表，则还需定义单链表的表头指针：typevectype=array[1..t]of^matnode;t为行数，也是单链表的个

5、数。122141^233251^316^423^51254-4稀疏矩阵的转置运算矩阵转置的定义设A为n×m阶矩阵（即n行m列），第i行j列的元素是a(i,j)。定义A的转置为这样一个m×n阶矩阵B，满足B=a(j,i)，即B(i,j)=A(j,i)（B的第i行第j列元素是A的第j行第I列元素），记A'=B。(有些书记为AT=B，这里T为A的上标）直观来看，将A的所有元素绕着一条从第1行第1列元素出发的右下方45度的射线作镜面反转，即得到A的转置。基本性质(A±B)'=A'±B'(A×B)'=B'×A'(A')'=A稀疏矩阵的转置

6、运算——朴素算法行列值0201000301000003000200-4011223455243512142131632-4算法步骤：1、第一次扫描列，把列值=1的三元组，按从左到右的顺序依次写入数组B2、第二次扫描列，把列值=2的三元组，按从左到右的顺序依次写入数组B3、……扫描m趟，每次要访问t个元素（t为元素总个数）。O(m*t)数组A，存储n*m的矩阵行列值1122344535142152622331-41数组B，存储m*n的矩阵0060220030030001000-401000稀疏矩阵的转置运算——优秀算法算法思想：对

7、数组A仅扫描两次，第一次，统计各列上元素的个数，则对应到B上即是行上的元素个数。由此求出A中每列的第一个元素在数组B中的位置。第二次，把A中的每个三元组写入数组B中。Col:12345Num:Pot:13568行列值11223455243512142131632-4数组A，存储n*m的矩阵22121算法描述：Procedurefastrans(A,B);Beginm:=A[0,1];n:=a[0,2];t:=a[0,3];b[0,1]:=n;b[0,2]:=m;b[0,3]:=t;ift=0thenreturn;forcol:=

8、1tondonum[col]:=0;fori:=1totdonum[A[i,2]]:=num[A[i,2]]+1;{计算各A中各列上的元素个数}pot[1]:=1;forcol:=2tondopot[col]:=pot[col-1]+num[col-1];{计算