返回主目录.ppt

《返回主目录.ppt》由会员分享，可在线阅读，更多相关《返回主目录.ppt（52页珍藏版）》请在三一文库上搜索。

1、返回主目录,本 章 说 明 5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.4 广义表的定义 5.5 广义表的存贮结构 本 章 小 结,学习目标 理解数组类型的特点及其在高级编程语言中的存储表示和实现方法，并掌握数组在“以行为主” 、“以列为主”的存储表示中的地址计算方法。 掌握特殊矩阵的存储压缩表示方法。 理解稀疏矩阵的两类存储压缩方法的特点及其适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算所采用的处理方法。,本章说明,重点和难点 重点是学习数组类型的定义及其存储表示。 知识点 数组的类型定义、数组的存储表示、特殊矩阵的压缩存储表示方法、随机稀疏矩阵的压缩存储

2、表示方法。,本章说明,5.1 数组的定义,数组是线性表的推广 数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表。,数组的抽象数据类型定义,ADT Array 数据对象：ji=0,., bi-1, i=1,2,n Daj1,j2,.jn|n(0)为数组的维数，bi为数组第i维的长度， ji为数组元素的第i维下标， aj1,j2,.jn ElemSet 数据关系：RR1, R2, ., Rn Ri | 0jkbk-1, 1kn 且ki, 0jibi-2, aj1,，ji, ,jn, aj1,，ji+1, ,jn D, i=2,.,n ,5.1 数组的定义,基本操作: InitA

3、rray(&A, n, bound1, ., boundn) 操作结果：若维数 n 和各维长度合法，则构造相应的数组A。 DestroyArray(&A) 初始条件：数组 A 已经存在。 操作结果：销毁数组 A。 Value(A, &e, index1, ., indexn) 初始条件：A 是 n 维数组，e 为元素变量，随后是 n 个下标值。 操作结果：若各下标不超界，则e赋值为所指定的A的元素值，并返回OK。 Assign(&A, e, index1, ., indexn) 初始条件：A 是 n 维数组，e 为元素变量，随后是 n 个下标值。 操作结果：若下标不超界，则将 e 的值赋给A中

4、指定下标的元素。 ADT Array,5.1 数组的定义,5.2 数组的顺序表示和实现,用一组连续的存储单元来表示数组。 有两种映象方法： “以行(序)为主(序)” ：对二维数组进行“按行切分”，即将数组中的数据元素“按行依次排放”在存储器中 “以列(序)为主(序)”对二维数组进行“按列切分”，即将数组中的数据元素“按列依次排放“在存储器中。,按行序为主序存放,am-1,n-1,am-1,1,am-1,0,a1,n-1,a11,a10,a0,n-1,.,a01,a00,5.2 数组的顺序表示和实现,按列序为主序存放,am-1 ,n-1,a1,n-1,a0,n-1,.,am-1,1,a11,a0

5、1,am-1,1,.,a10,a00,5.2 数组的顺序表示和实现,按行序为主序存放,每个数据元素占L个存储单元; LOC(0,0)表示数据元素a00的存储地址 是数组的起始地址（基地址）; LOC(i,j)表示下标为(i,j)的数据元素 aij的存储地址 LOC(i,j)=LOC(0,0)+(i*n+j)*L,5.2 数组的顺序表示和实现,按列序为主序存放,每个数据元素占L个存储单元; LOC(0,0)表示数据元素a00的存储地址， 是数组的起始地址（基地址） LOC(i,j)表示下标为(i,j)的数据元素 aij的存储地址 LOC(i,j)=LOC(0,0)+(j*m+i)*L,5.2 数

6、组的顺序表示和实现,5.3 矩阵的压缩存储,压缩存储 为多个值相同的矩阵元只分配一个存储空间；对零元不分配空间。,5.3.1 特殊矩阵,特殊矩阵 值相同的元素或者零元素在矩阵中的分布有一定规律,对称矩阵,n阶矩阵； aij=aji 1i,j n,5.3 矩阵的压缩存储,特殊矩阵 值相同的元素或者零元素在矩阵中的分布有一定规律,三角矩阵,n阶矩阵； 下（上）三角矩阵：矩阵的上（下）三角（不包括对角线）中的元均为常数c或零。,5.3 矩阵的压缩存储,特殊矩阵 值相同的元素或者零元素在矩阵中的分布有一定规律,对角矩阵,n阶矩阵 所有的非零元都集中在以主对角线为中心的带状区域中,5.3 矩阵的压缩存储

7、,压缩存储对称矩阵,按行序为主序：,仅存储下三角,ann,an1,a32,a31,a22,a21,a11,5.3 矩阵的压缩存储,压缩存储下三角矩阵,按行序为主序：,ann,an1,a32,a31,a22,a21,a11,仅存储下三角,1,5.3 矩阵的压缩存储,压缩存储对角矩阵,仅存储主对角线非0元素,按行序为主序：,an,n,an,n-1,a23,a22,a21,a12,a11,5.3 矩阵的压缩存储,5.3.2 稀疏矩阵,稀疏矩阵 非零元较零元少，且分布没有一定规律的矩阵。 压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值。,矩阵维数 （6,7） 非零元 (1,2,12) (

8、1,3,9) (3,1,-3) (3,6,14),(4,3,24) (5,2,18) (6,1,15) (6,4,-7),5.3 矩阵的压缩存储,1.压缩存储稀疏矩阵(三元组顺序表),以顺序存储结构来表示三元组。 稀疏矩阵的三元组顺序表存储表示 #define MAXSIZE 12500 /假设非零元个数的最大值为12500 typedef struct int i,j; /该非零元的行下标和列下标 ElemType e; Triple; typedef struct Triple dataMAXSIZE+1; /非零元三元组表，data0未用 int mu, nu, tu; /矩阵的行数、列

9、数和非零元个数 TSMatrix ;,行序,5.3 矩阵的压缩存储,6 7 8,1 2 12,1 3 9,3 1 -3,3 6 14,4 3 24,5 2 18,6 1 15,6 4 -7,data0.i,data0.j,data0.e分别存放矩阵行列维数和非零元个数,5.3 矩阵的压缩存储,求转置矩阵,问题描述 已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表。 解决思路 将矩阵行、列维数互换； 将每个三元组中的i和j相互调换； 重排三元组次序。,5.3 矩阵的压缩存储,?,5.3 矩阵的压缩存储,方法一：按矩阵的列序转置 按T.data中三元组次序依次在M.data中找到相应的三元组

10、进行转置,7 6 8,1 3 -3,1 6 15,2 1 12,2 5 18,3 1 9,3 4 24,4 6 -7,6 3 14,col=1,col=2,5.3 矩阵的压缩存储,Col从1n在M中找每1列,5.3 矩阵的压缩存储,按矩阵的列序转置的算法思想 (1)令T.mu=M.nu, T.nu=M.mu, T.tu=M.tu, col=1，q=1(T的三元组下标初始化，指向转置后的第1个位置)，p=1 (指向M的第1个位置) (2)如p所指元素的列下标=col，则送q所指位置，q+ (3)p+,若p=M.tu(1最后1个非0元),则(2),否(4) (4)col+，如果col=M.nu，转

11、(2)，否(5) (5)结束,适用于tumu*nu,时间复杂度为O(nutu),算法5.1,算法实现：,方法二：按矩阵的行序转置 按M.data中三元组次序转置，转置结果放入T.data中恰当位置。 此法关键是要预先确定M.data中每一列第一个非零元在T.data中位置。(cpotcol) 为确定这些位置，转置前应先求得M.data的每一列中非零元个数。(numcol),5.3 矩阵的压缩存储,设numcol记录M中第col列中非0元个数，cpotcol记录M中第col列的第1个非0元在T中的恰当位置，有： cpot1=1; cpotcol=cpotcol-1+numcol-1 2colM.

12、mu,7 6 8,1 3 -3,1 6 15,2 1 12,2 5 18,3 1 9,3 4 24,4 6 -7,6 3 14,4,6,2,9,7,5,3,8,5.3 矩阵的压缩存储,方法二:按矩阵的行序转置的实现,用空间换取时间,时间复杂度为O(nu+tu),算法5.2,5.3 矩阵的压缩存储,三元组顺序表的特点,优点 非零元在表中按行序有序存储，便于进行依行序处理的矩阵运算。 缺点 若需按行号存取某一行的非零元，则需从头开始进行查找。,5.3 矩阵的压缩存储,2.压缩存储稀疏矩阵(行逻辑链接的的顺序表),为了便于随机存储任意一行的非零元，需要知道每一行的第一个非零元在三元组表中的位置 解决

13、方法：将cpot固定在稀疏矩阵的存储结构中。,#define MAXSIZE 12500 /假设非零元个数的最大值为12500 typedef struct int i,j; /该非零元的行下标和列下标 ElemType e; Triple; typedef struct Triple dataMAXSIZE+1; /非零元三元组表，data0未用 int rposMAXRC+1; /各行第一个非零元的位置表 int mu,nu,tu; /矩阵的行数、列数和非零元个数 RLSMatrix ;,5.3 矩阵的压缩存储,矩阵乘法运算,如何求？,5.3 矩阵的压缩存储,(1)稀疏矩阵MxN,只需在M

14、、N中找到相应的各对非0元素相乘,即M.data中的j值和N.data中的i值相等的各对非0元素相乘。例如M中的(1,1,3)p=1和N中的(1,1,0) 、(1,2,2)q=1相乘。为此,设两个:numbrow表示N中第brow行的非0元个数,rposbrow表示N中第brow行的第1个非0元在N.data中的位置,N.rpos1=1, N.rposbrow=rposbrow-1上一行+numbrow-1上一行,2brown。N.rposbrow、M.rposarow称为行逻辑链接的顺序表。(并在进入下面的算法前,预先求得一维数组rpos的值。 (2)乘积矩阵Q中每个元素的值是个累计和(也可

15、能为和),对每个元素设一中间变量,temp列数,初值为0,将相应非0元素的乘积累加。例如,Ma中的(1,1,3)1与Nb中的(1,1,1)1的乘积,以及Ma中的(1,3,4)2与Nb中的(3,1,-2)3的乘积累加为Q中的(1,1,-5)1 (3)因(M)是“以行为主”排列,(Q)也应“以行为主”排列,故对Q逐行处理。中间变量ctemp最大为Q的列数存放Q的一行,检查这行中各元素是否零,然后,再将非0元素(结果)存到Q.data中。,5.3 矩阵的压缩存储,1,2,3,1 2 6,2 1 -1,3 2 4,3 2 0,arow=1,arow=2,arow=3,6,-1,4,5.3 矩阵的压缩存

16、储,5.3 矩阵的压缩存储,算法思想 初始化(行数Q=M,列数Q=N赋值,Q的下标Q.tu=0,准备接收); for(arow=1;arow=M.mu;+arow),处理M的每一行; 中间变量一维数组ctemp(行)清0(例子中,Q一行只有2列,故ctemp1,ctemp2即2)。顺便记下Q当前行非0元的起始位置Q.tu 对M的当前行中的非0元,(逐个)做:(ptp) 取M中当前非0元的列号(j),即为N中的i(N中的行号brow);,根据N的行号,对该行的非0元逐个做:(有几个就做几次)(qt) 取N中当前非0元的列号为Q的列号(Q的列号为ccol); M、N中相应的非0元相乘,并累加到ct

17、empQ的列号ccol中; 逐个将当前Q的一行中的非0元素存入Q中。,矩阵相乘算法实现,算法5.3,5.3 矩阵的压缩存储,算法时间复杂度 累加器ctemp初始化的时间复杂度为： O(M.muN.nu) 求Q的所有非0元的时间复杂度为： O(M.nuN.tu/N.mu) 压缩存储的时间复杂度为： O(M.muN.nu) 所以，总的时间复杂度为： O(M.muN.nu+M.tuN.tu/N.mu),3.压缩存储稀疏矩阵(十字链表),引入原因 当矩阵的非零元的个数发生变化时，不宜采用三元组表。如A=A+B，非零元的插入或删除将会引起A.data中的数据移动，这是顺序结构三元组的弱势。 十字链表结点

18、形式,非零元的行、列、值,同一列下一个非零元,同一行下一个非零元,typedef struct OLNode int i,j; ElemType e; struct OLNode *right,*down; OLNod; *OLink; typedef struct Olink *rhead,*chead; int mu, nu, tu; CrossList;,5.3 矩阵的压缩存储,列链表头指针,行链表头指针,5.3 矩阵的压缩存储,建立十字链表的思想,m=4,n=3,t=5,1,1,3,2,2,5,2,3,4,4,1,8,2,1,7,5.3 矩阵的压缩存储,建立十字链表的算法思想 （1）初

19、始化 （2）循环输入各非0元的(i,j,e)，直到最后一个，重复做： （3）申请结点，赋值 （4）寻找行i插入位置，插入 （5）寻找列j插入位置，插入,时间复杂度为O( t*s) ，s=max(m.n),5.3 矩阵的压缩存储,建立十字链表的算法实现,算法5.4,5.4 广义表的定义,广义表(列表) 是线性表的推广，广泛地应用于人工智能等领域的表处理语言LISP语言。 一般记作LS=(a1,a2,an) (n0) 名称：LS； 长度：n； 原子：ai是单个元素，一般用小写字母表示； 子表：ai是广义表，一般用大写字母表示。 表头(Head)：非空广义表 LS的第一个数据元素a1； 表尾(Tai

20、l)：非空广义表 LS除第一个数据元素外的其余数据元素构成的广义表 (a2,an) 。,广义表特性,A=() F=(b,(c,d,e) E=(b,(c),(d,e) D=(E,A,F) C=(A,D,F) B=(a,B)=(a,(a,(a,v.),广义表中的数据元素有固定的相对次序 广义表的元素可以是子表，而子表的元素还可是子表 广义表可以为其它列表共享 广义表可以是一个递归的表,广义表与数组的区别,5.4 广义表的定义,操作长度,A=() F=(b,(c,d,e) E=(b,(c),(d,e) D=(E,A,F) C=(A,D,F) B=(a,B)=(a,(a,(a,v.),广义表中元素的“

21、长度“应由最外层括弧中的“逗号“来定。,A的长度为0 F的长度为2 E的长度为3 D的长度为3 C的长度为3 B的长度为2,5.4 广义表的定义,操作取表头、取表尾 F=(b,(c,d,e),GetHead(F)=b GetTail(F)=(c,d,e)=F1 GetHead(F1)=(c,d,e)=F2，GetTail(F1)=( ) GetHead(F2)=c，GetTail(F2)=(d,e)=F3 GetHead(F3)=d，GetTail(F3)=(e)=F4 GetHead(F4)=e，GetTail(F4)=( ),两个操作只对非空表有意义； 取表头的结果可能是原子，也可能是个广

22、义表； 取表尾“必定“是个广义表，但可能是个空的广义表。,5.4 广义表的定义,5.5 广义表的存储结构,采用链式存储结构。 两种结构的结点 表结点：用来表示列表； 原子结点：用来表示子表。,标志域,标志域,表头指针,表尾指针,值域,A=() B=(e) C=(a,(b,c,d) D=(A,B,C) E=(a,E),A,B,C,D,E,5.5 广义表的存储结构,另一种结点结构,标志域,标志域,表头指针,值域,下一个元素指针,下一个元素指针,5.5 广义表的存储结构,A=() B=(e) C=(a,(b,c,d) D=(A,B,C) E=(a,E),B,C,D,E,A,5.5 广义表的存储结构,

23、本章小结,了解数组的类型定义及其在高级语言中实现的方法。 数组的特点是一种多维的线性结构，并只进行存取或修改某个元素的值，因此它只需要采用顺序存储结构。 介绍了稀疏矩阵的三种表示方法。至于在具体应用问题中采用哪一种表示法这取决于该矩阵主要进行什么样的运算。 广义表是一种递归定义的线性结构，因此它兼有线性结构和层次结构的特点。,基础知识题(数组部分),假设有二维数组 A68，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置(基地址)为 1000，计算： 数组 A 的存储； 数组 A 的最后一个元素 a5,7 的第一个字节的地址; 按行存储时，元素 a1,4 的第一个字节的地址

24、; 按列存储时，元素 a4,7 的第一个字节的地址。,基础知识题(广义表部分),求下列广义表操作的结果： GetHead(p,h,w); GetTail(b,k,p,h); GetHead(a,b),(c,d); GetTail(a,b),(c,d); GetHead(GetTail(a,b),(c,d); GetTail(GetHead(a,b),(c,d); GetHead(GetTail(GetHead(a,b),(c,d); GetTail(GetHead(GetTail(a,b),(c,d)。,利用广义表的 GetHead 和 GetTail 操作写出函数表达式，把原子 banana

25、 分别从下列广义表中分离出来。 L1 = (apple,pear,banana,orange); L2 = (apple,pear),(banana,orange); L3 = (apple),(pear),(banana),(orange); L4 = (apple,(pear),(banana),(orange); L5 = (apple),(pear),(banana),orange); L6 = (apple),pear),banana),orange); L7 = (apple,(pear,(banana),orange);,基础知识题(广义表部分),画出下列广义表的存储结构图。 ( ), a, (b, c), ( ), d), (e) (a), b), ( ), (d), (e, f) 已知右侧各图为广义表的存储结构图，写出各图表示的广义表。,基础知识题(广义表部分),