汇编语言5.ppt

1、第五章第五章数组和广义表数组和广义表5.1 数组的类型定义数组的类型定义5.3 稀疏矩阵的压缩存储稀疏矩阵的压缩存储 5.2 数组的顺序表示和实现数组的顺序表示和实现5.4 广义表的类型定义广义表的类型定义5.5 广义表的表示方法广义表的表示方法5.1 数组的类型定义数组的类型定义ADT Array 数据对象数据对象：Daj1,j2,.,ji,jn|ji=0,.,bi-1,i=1,2,.,n 数据关系数据关系：RR1,R2,.,Rn Ri|0 jk bk-1,1 k n 且k i,0 ji bi-2,i=2,.,n ADT Array 基本操作基本操作:二维数组的定义二维数组的定义:数据对象数

2、据对象:D=aij|0ib1-1,0 jb2-1数据关系数据关系:R=ROW,COL ROW=|0ib1-2,0jb2-1 COL=|0ib1-1,0 jb2-2基本操作基本操作：InitArray(&A,n,bound1,.,boundn)DestroyArray(&A)Value(A,&e,index1,.,indexn)Assign(&A,e,index1,.,indexn)InitArray(&A,n,bound1,.,boundn)操作结果：操作结果：若维数 n 和各维长度合法，则构造相应的数组A，并 返回OK。DestroyArray(&A)操作结果：操作结果：销毁数组A。Valu

3、e(A,&e,index1,.,indexn)初始条件：初始条件：A是n维数组，e为元素变量，随后是n 个下标值。操作结果：操作结果：若各下标不超界，则e赋值为 所指定的A 的元素值，并返 回OK。Assign(&A,e,index1,.,indexn)初始条件：初始条件：A是n维数组，e为元素变量，随后是n 个下标值。操作结果：操作结果：若下标不超界，则将e的值赋 给所指定的A的元素，并返回 OK。5.2 数组的顺序表示和实现数组的顺序表示和实现类型特点类型特点:1)只有引用型操作，没有加工型操作；2)数组是多维的结构，而存储空间是 一个一维的结构。有两种顺序映象的方式有两种顺序映象的方式:

4、1)以行序为主序(低下标优先)；2)以列序为主序(高下标优先)。例如：例如：称为基地址基地址或基址。以以“行序为主序行序为主序”的存储映象的存储映象二维数组A中任一元素ai,j 的存储位置 LOC(i,j)=LOC(0,0)+(b2ij)a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L L 推广到一般情况，可得到 n 维数组数据元素存储位置的映象关系 称为 n 维数组的映象函数。数组元素数组元素的存储位置是其下标的线性函数。的存储位置是其下标的线性函数。其中 cn=L，ci-1=bi ci,1 i n。LOC(j1,j2,.,jn)=LOC(0

5、,0,.,0)+ci ji i=1n 二维数组二维数组 三维数组三维数组行向量行向量 下标下标 i 页向量页向量 下标下标 i列向量列向量 下标下标 j 行向量行向量 下标下标 j 列向量列向量 下标下标 k假设 m 行 n 列的矩阵含 t 个非零元素，则称 为稀疏因子稀疏因子。通常认为通常认为 0.05 的矩阵为稀疏矩阵。的矩阵为稀疏矩阵。5.3 稀疏矩阵的压缩存储稀疏矩阵的压缩存储何谓稀疏矩阵？以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的问题问题:1)零值元素占了很大空间零值元素占了很大空间;2)计算中进行了很多和零值的运算，计算中进行了很多和零值的运算，遇除法，还需判别除数是否为零

6、遇除法，还需判别除数是否为零。1)尽可能少存或不存零值元素；解决问题的原则解决问题的原则:2)尽可能减少没有实际意义的运算；3)操作方便。即：能尽可能快地找到与 下标值(i，j)对应的元素，能尽可能快地找到同 一行或同一列的非零值元素。1)特殊矩阵特殊矩阵 非零元在矩阵中的分布有一定规则 例如:三角矩阵 对角矩阵2)随机稀疏矩阵随机稀疏矩阵 非零元在矩阵中随机出现有两类稀疏矩阵有两类稀疏矩阵：随机稀疏矩阵的压缩存储方法随机稀疏矩阵的压缩存储方法:一、三元组顺序表一、三元组顺序表二、行逻辑联接的顺序表二、行逻辑联接的顺序表三、三、十字链表十字链表#define MAXSIZE 12500 typ

7、edef struct int i,j;/该非零元的行下标和列下标 ElemType e;/该非零元的值 Triple;/三元组类型三元组类型一、三元组顺序表一、三元组顺序表typedef union Triple dataMAXSIZE+1;int mu,nu,tu;TSMatrix;/稀疏矩阵类型稀疏矩阵类型如何求转置矩阵？如何求转置矩阵？用常规的二维数组表示时的算法 其时间复杂度为其时间复杂度为:O(munu)for(col=1;col=nu;+col)for(row=1;row=mu;+row)Tcolrow=Mrowcol;用“三元组”表示时如何实现？1 2 141 5 -52 2

8、-73 1 363 4 282 1 145 1 -52 2 -71 3 364 3 28 首先应该确定每一行的第一个非零元在三元组中的位置。cpot1=1;for(col=2;col=M.nu;+col)cpotcol=cpotcol-1+numcol-1;Status FastTransposeSMatrix(TSMatrix M,TSMatrix&T)T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu)for(col=1;col=M.nu;+col)numcol=0;for(t=1;t=M.tu;+t)+numM.datat.j;cpot1=1;for(col=2;

9、col=M.nu;+col)cpotcol=cpotcol-1+numcol-1;for(p=1;p=M.tu;+p)/if return OK;/FastTransposeSMatrix 转置矩阵元素Col=M.datap.j;q=cpotcol;T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;+cpotcol 分析算法FastTransposeSMatrix的时间复杂度：时间复杂度为时间复杂度为:O(M.nu+M.tu)for(col=1;col=M.nu;+col)for(t=1;t=M.tu;+t)for(col=

10、2;col=M.nu;+col)for(p=1;p=M.tu;+p)三元组顺序表又称有序的双下标有序的双下标法法，它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序便于进行依行顺序处理的矩阵运算处理的矩阵运算。然而，若需随机存取某一行中的非零元，则需从头开始进行查找。二、行逻辑联接的顺序表二、行逻辑联接的顺序表#define MAXMN 500 typedef struct Triple dataMAXSIZE+1;int rposMAXMN+1;int mu,nu,tu;RLSMatrix;/行逻辑链接顺序表类型 修改前述的稀疏矩阵的结构定义，增加一个数据成员rpos，其值在稀疏矩

11、阵的初始化函数中确定。例如：给定一组下标，求矩阵的元素值ElemType value(RLSMatrix M,int r,int c)p=M.rposr;while(M.datap.i=r&M.datap.j c)p+;if(M.datap.i=r&M.datap.j=c)return M.datap.e;else return 0;/value矩阵乘法的经典算法矩阵乘法的经典算法:for(i=1;i=m1;+i)for(j=1;j=n2;+j)Qij=0;for(k=1;k=n1;+k)Qij+=Mik*Nkj;其时间复杂度为其时间复杂度为:O(m1n2n1)Q初始化；if Q是非零矩阵 /

12、逐行求积 for(arow=1;arow=M.mu;+arow)/处理M的每一行 ctemp=0;/累加器清零 计算Q中第arow行的积并存入ctemp 中；将ctemp 中非零元压缩存储到Q.data；/for arow /if 两个稀疏矩阵相乘（两个稀疏矩阵相乘（Q M N）的过程可大致描述如下：的过程可大致描述如下：Status MultSMatrix (RLSMatrix M,RLSMatrix N,RLSMatrix&Q)if(M.nu!=N.mu)return ERROR;Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;if(M.tu*N.tu!=0)/Q是非零矩阵 for(

13、arow=1;arow=M.mu;+arow)/处理M的每一行 /for arow /if return OK;/MultSMatrix ctemp=0;/当前行各元素累加器清零 Q.rposarow=Q.tu+1;for(p=M.rposarow;pM.rposarow+1;+p)/对当前行中每一个非零元 brow=M.datap.j;if(brow N.nu)t=N.rposbrow+1;else t=N.tu+1 for(q=N.rposbrow;q t;+q)ccol=N.dataq.j;/乘积元素在Q中列号 ctempccol+=M.datap.e*N.dataq.e;/for q

14、/求得Q中第crow(=arow)行的非零元 for(ccol=1;ccol MAXSIZE)return ERROR;Q.dataQ.tu=arow,ccol,ctempccol;/if处理 的每一行M三、三、十字链表十字链表3 0 0 50-1 0 02 0 0 01 1 31 4 52 2-13 1 2 5.4 广义表的类型定义广义表的类型定义ADT Glist 数据对象数据对象：Dei|i=1,2,.,n;n0;eiAtomSet 或 eiGList,AtomSet为某个数据对象 数据关系：数据关系：LR|ei-1,eiD,2in ADT Glist基本操作基本操作:广义表是递归递归定

15、义的线性结构线性结构，LS=(1,2,n)其中：i 或为原子 或为广义表例如例如:A=()F=(d,(e)D=(a,(b,c),F)C=(A,D,F)B=(a,B)=(a,(a,(a,)广义表是一个多层次多层次的线性结构线性结构例如：例如：D=(E,F)其中:E=(a,(b,c)F=(d,(e)DEFa()d()bce广义表广义表 LS=(1,2,n)的结构特的结构特点点:1)广义表中的数据元素有相对次序次序；2)广义表的长度长度定义为最外层包含元素个数；3)广义表的深度深度定义为所含括弧的重数；注意：“原子”的深度为 0 “空表”的深度为 1 4)广义表可以共享共享；5)广义表可以是一个递归

16、递归的表。递归表的深度是无穷值，长度是有限值。6)任何一个非空广义表非空广义表 LS=(1,2,n)均可分解为 表头表头 Head(LS)=1 和 表尾表尾 Tail(LS)=(2,n)两部分。例如例如:D=(E,F)=(a,(b,c)，F)Head(D)=E Tail(D)=(F)Head(E)=a Tail(E)=(b,c)Head(b,c)=(b,c)Tail(b,c)=()Head(b,c)=b Tail(b,c)=(c)Head(c)=c Tail(c)=()结构的创建和销毁结构的创建和销毁 InitGList(&L);DestroyGList(&L);CreateGList(&L,

17、S);CopyGList(&T,L);基基本本操操作作 状态函数状态函数 GListLength(L);GListDepth(L);GListEmpty(L);GetHead(L);GetTail(L);插入和删除操作插入和删除操作 InsertFirst_GL(&L,e);DeleteFirst_GL(&L,&e);遍历遍历 Traverse_GL(L,Visit();5.5 广义表的表示方法广义表的表示方法通常采用头、尾指针的链表结构表结点表结点:原子结点：原子结点：tag=1 hp tptag=0 data1)表头、表尾分析法：构造存储结构的两种分析方法构造存储结构的两种分析方法:若表头

18、为原子，则为若表头为原子，则为空表空表 ls=NIL非空表非空表 lstag=1 指向表头的指针指向表尾的指针tag=0 data否则，依次类推。否则，依次类推。L=(a,(x,y),(x)a(x,y)()1 LL=()0 a 1 1 1 1 1 0 a ()x2)子表分析法：若子表为原子，则为若子表为原子，则为空表空表 ls=NIL非空表非空表 1 指向子表1 的指针tag=0 data否则，依次类推。否则，依次类推。1 指向子表2 的指针 1 指向子表n 的指针ls 例如例如:a (x,y)(x)LS=(a,(x,y),(x)ls1.1.了了解解数数组组的的两两种种存存储储表表示示方方法法

19、，并并掌掌握握数数组组在在以以行行为为主主的的存存储储结结构构中中的的地地址址计算方法。计算方法。2.2.掌掌握握对对特特殊殊矩矩阵阵进进行行压压缩缩存存储储时时的的下下标变换公式。标变换公式。3.3.了了解解稀稀疏疏矩矩阵阵的的两两类类压压缩缩存存储储方方法法的的特特点点和和适适用用范范围围，领领会会以以三三元元组组表表示示稀稀疏矩阵时进行矩阵运算采用的处理方法疏矩阵时进行矩阵运算采用的处理方法。本章小结本章小结4.4.掌握广义表的结构特点及其存储表掌握广义表的结构特点及其存储表示方法，读者可根据自己的习惯熟练掌示方法，读者可根据自己的习惯熟练掌握任意一种结构的链表，学会对非空广握任意一种结

20、构的链表，学会对非空广义表进行分解的两种分析方法：即可将义表进行分解的两种分析方法：即可将一个非空广义表分解为表头和表尾两部一个非空广义表分解为表头和表尾两部分或者分解为分或者分解为n n个子表。个子表。5.5.学习利用分治法的算法设计思想编学习利用分治法的算法设计思想编制递归算法的方法。制递归算法的方法。本章小结本章小结1.假设有假设有二维数组二维数组 A68，每个元素用相邻的每个元素用相邻的 6 个字节个字节存储，存储器按字节编址。已知存储，存储器按字节编址。已知 A 的起始存储位置的起始存储位置(基地基地址址)为为 1000，计算：，计算：(1)数组数组 A 的体积（即存储量）的体积（即

21、存储量）;(2)数组数组 A 的最后一个元素的最后一个元素 a57 的第一个字节的地址的第一个字节的地址;(3)按行存储时，元素按行存储时，元素 a14 的第一个字节的地址的第一个字节的地址;(4)按列存储时，元素按列存储时，元素 a47 的第一个字节的地址。的第一个字节的地址。习习 题题2.假设按低下标优先存储整数数组假设按低下标优先存储整数数组A9358时，第一时，第一个元素的字节地址是个元素的字节地址是 100，每个整数占四个字节。问，每个整数占四个字节。问下列元素的存储地址是什么？下列元素的存储地址是什么？(1)a0000(2)a1111(3)a3125(4)a8247 3.按高下标优

22、先存储方式按高下标优先存储方式(以最右的下标为主序以最右的下标为主序)，顺，顺序列出数组序列出数组 A2233 中所有元素中所有元素 aijkl，为了简化表，为了简化表达，可以只列出达，可以只列出(i,j,k,l)的序列。的序列。习习 题题4.设有上三角矩阵设有上三角矩阵(aij)nn，将其上三角元素逐行存，将其上三角元素逐行存于数组于数组 Bm 中中(m 充分大充分大)，使得，使得 Bk=aij 且且 k=f1(i)+f2(j)+c。试推导出函数。试推导出函数 f1，f2 和常数和常数 c(要求要求 f1 和和 f2 中不含常数项中不含常数项)。5.设有三对角矩阵设有三对角矩阵(aij)nn，将其三条对角线上的元素将其三条对角线上的元素存于数组存于数组 B3n 中，使得元素中，使得元素 Buv=aij，试推导试推导出从出从(i,j)到到(u，v)的下标变换公式。的下标变换公式。习习 题题6.设有三对角矩阵设有三对角矩阵(aij)nn，将其三条对角线上的元素将其三条对角线上的元素逐行地存于数组逐行地存于数组 B3n-2 中，使得中，使得 Bk=aij，求：求：(1)用用 i,j 表示表示 k 的下标变换公式；的下标变换公式；(2)用用 k 表示表示 i，j 的下标变换公式。的下标变换公式。习习 题题