您好,欢迎访问三七文档
当前位置:首页 > 行业资料 > 能源与动力工程 > 数据结构第五章数组稀疏矩阵和广义表
数据结构第五章数组、特殊矩阵和广义表重庆一中葛静数组的逻辑结构一维数组就是一个线性表二维数组可以看成是数组元素为一维数组的一维数组三维数组可以看成是数组元素为二维数组的一维数组N维数组可以看成是数组元素为n-1维数组的一维数组由此:数组是一种抽象数据结构,它一旦被规定,其每一维的大小、上下界即被规定。通过数组元素的唯一下标来取数组元素,完成,数组元素的取值、赋值操作。数组的物理结构(存储映像)注意:内存的地址空间是一维状态,即连续的。一维数组可以直接存储,那多维数组呢?如何把一个多维下标映射成一维下标?行优先:即先行后列,如:basic\pascal\c列优先:即先列后行,如: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][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列上的数是100000000016000003000000-401234552345551244163-4稀疏矩阵的链式存储就是把三元组线性表进行链接存储1、结点类型可定义为:Typematnode=recordrow,col:integer;val:elemtype;next:^matnode;end;12202010003016000003000200-401412332512、把具有相同行号的三元组节点顺序链接成一个单链表,每行一个单链表,则还需定义单链表的表头指针:typevectype=array[1..t]of^matnode;t为行数,也是单链表的个数。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稀疏矩阵的转置运算——朴素算法行列值02010003016000003000200-4011223455243512142131632-4算法步骤:1、第一次扫描列,把列值=1的三元组,按从左到右的顺序依次写入数组B2、第二次扫描列,把列值=2的三元组,按从左到右的顺序依次写入数组B3、……扫描m趟,每次要访问t个元素(t为元素总个数)。O(m*t)数组A,存储n*m的矩阵行列值1122344535142152622331-41数组B,存储m*n的矩阵0060220030030001000-401000稀疏矩阵的转置运算——优秀算法算法思想:对数组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:=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];{计算该列元素在B中的起始位置}fori:=1totdobegincol:=A[i,2];q:=pot[col];B[q,1]:=A[i,2];B[q,2]:=A[i,1];B[q,3]:=A[i,3];pot[col]:=pot[col]+1;end;End;时间复杂度O(n+t)特殊矩阵的压缩存储一、对称矩阵的存储,只存一半即可。二、即时计算的矩阵动态规划解题的时候,可以使用滚动数组来存储。即在计算第i行的状态时,用数组A保存i-1行状态,数组B保存第i行的状态,而后随着i的增加,数组A、B进行滚动。三、稀疏矩阵的压缩存储:如三元组。广义表的定义广义表是线性表的推广。一个广义表示n个元素的序列,n=0是为空表,n0时为非空表,其元素可以是一个子表,也可以是一个确定类型的对象(单元素)。广义表是一种递归的数据结构。用小写字母表示单元素,大写字母表示表元素A()长度为0的空表B(e)长度为1,且有一个元素的广义表C(a,(b,c,d))长度为2的广义表D(A,B,C)D((),(e),(a,(b,c,d)))长度为3的广义表E((a,(a,b),((a,b),c)))长度为1的广义表广义表的深度:括号嵌套的重数,也是子表的最大深度+1。广义表的定义:广义表表示一种递归的数据结构,最好使用动态链接结构。如:E((a,(a,b),((a,b),c)))深度为511^0a11^0a0b^0c^0a0b^求广义表的深度Functiondepth(ls):integer;{ls指向广义表的首结点}beginmax:=0;whilelsnildobeginifls^.tag=1thenbegindep:=depth(ls^.sublist);ifdepmaxthenmax:=dep;end;ls:=ls^.next;end;depth:=max+1;End;本章知识点1、掌握多维数组地址的计算2、稀疏矩阵的存储及高效的转置计算方法3、特殊矩阵的压缩存储方法4、广义表的含义及深度计算课后作业练习5
本文标题:数据结构第五章数组稀疏矩阵和广义表
链接地址:https://www.777doc.com/doc-3381663 .html