第5部分数组和广义表.ppt

《第5部分数组和广义表.ppt》由会员分享，可在线阅读，更多相关《第5部分数组和广义表.ppt（80页珍藏版）》请在三一文库上搜索。

1、第5章 数组和广义表,元素的值并非原子类型，可以再分解，表中 元素也是一个线性表（即线性表的推广）。,数组和广义表的特点：特殊的线性表,5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.4 广义表的定义 5.5 广义表的存储结构,第5章 数组和广义表,5.1 数组的定义,数组： 由一组名字相同、下标不同的同类型的元素 组成,数组特点 数组结构固定,下标一般具有固定的上界和下界 数据元素具有统一的类型 数组运算 给定一组下标，取相应的数据元素. 给定一组下标，修改数据元素的值.,数组的处理比其它复杂的结构要简单,与高级语言中数组的区别：,1、本章所讨论的数组是一种数据

2、结构，而高级语言 中数组是一种数据类型。 2、高级语言中的数组是顺序结构；而本章的数组 既可以是顺序的，也可以是链式结构，用户可根 据需要选择。,二维数组的特点：,一维数组的特点：,1个下标，ai是ai+1的直接前驱,2个下标，每个元素aij受到两个关系（行关系和列关系）的约束：,一个mn的二维数组可以看成是由m行的一维数组组成或由n列的一维数组组成。,A0 A1 . . Am-1,Ai=(ai0, ai1, , ai,n-1) i=0,1,2,m-1,5.1 数组的定义,B0 B1 Bn-1,二维数组是一个数据元素为线性表的线性表,j=0,1,n-1,aij(1i m-2，1 j n-2)有

3、两个前驱结点ai,j-1和ai-1,j 两个后继结点ai,j+1和 ai+1,j a00没有前驱结点,称之为开始结点. am-1,n-1没有后继结点,称之为终端结点. 第0行的元素a0j(j=1,n-1) 第0列的元素ai0(i=1,m-1),我们可以把二维数组中的元素aij看成是属于两个线性表: 即第i行的线性表Ai和第j列的线性表Bj,第m-1行的元素am-1,j(j=1,n-2) 第n-1列的元素ai,n-1(i=1,m-2),同理，三维数组Amn l中每个元素属于三个线性表，每个元素 最多有三个前驱和三个后继。 ai1,i2,i3 前驱： ai1-1,i2,i3 ，ai1,i2-1,i

4、3， ai1,i2,i3-1 后继： ai1+1,i2,i3 ， ai1,i2+1,i3， ai1,i2,i3+1 推而广之 ，一个n维数组可以看成是由若干个n1维数组组成的线性表，在n维数组Ab1 b2 bn中, 每个元素ai1,i2,in(0 ij bi-1,j=1,2,n)属于n个线性表, 每个元素最多有n个前驱和n个后继。 ai1,i2,in 前驱：ai1-1,i2,in， ai1,i2-1,in，,，ai1,i2,in-1 后继：ai1+1,i2,in， ai1,i2+1,in，ai1,i2,in+1,数据对象: D = aij | aij ElemSet ，0ib1-1, 0 jb

5、2-1 数据关系: R = ROW, COL ROW = | 0ib1-1, 0jb2-2 COL = | 0ib1-2, 0jb2-1,二维数组的 定义:,InitArray(&A, n, bound1, ., boundn) 操作结果：若维数 n 和各维长度合法，则构造相应 的数组A，并返回OK。,基本操作：,DestroyArray(&A) 操作结果：销毁数组A。,Value(A, &e, index1, ., indexn)/取数组元素 初始条件：A是n维数组，e为元素变量，随后是n 个下标值。 操作结果：若各下标不超界，则e赋值为所指定的 A 的元素值，并返回OK。,基本操作：,As

6、sign(&A, e, index1, ., indexn)/修改数组元素 初始条件：A是n维数组，e为元素变量，随后是 n 个下标值。 操作结果：若下标不超界，则将e的值赋给所指 定的A的元素，并返回OK。,5.2 数组的顺序存储表示和实现,问题：计算机的存储结构一般是一维的，而n维数组(n2)一般是多维的，怎样存放？ 解决办法：事先约定按某种次序将数组元素排成一序 列，然后将这个线性序列存入存储器中。 例如：在二维数组中，我们既可以规定按行存储，也可以规定按列存储。,若规定好了次序，则数组中任意一个元素的存放地址便有 规律可寻，可形成地址计算公式； 约定的次序不同，则计算元素地址的公式也有

7、所不同； C和PASCAL中一般采用行优先顺序；FORTRAN采用列优先。,按行序为主序存放,0,1,n-1,m*n-1,n,计算二维数组元素地址的通式,二维数组列优先存储的通式为： LOC(aij)=LOC(a00)+(b1*j+i)*L,则行优先存储时的地址公式为： LOC(aij)=LOC(a00)+(b2*i+j)*L,设一般的二维数组是A0b1-1, 0b2-1,计算三维数组元素地址的通式,设一般的三维数组是A0b1-1, 0b2-1，0b3-1,按“行优先顺序”存储，其任一元素Aijk地址计算函数为： LOC(aijk)=LOC(a000)+(i*b2*b3+j*b3+k)*L,若

8、是N维数组，其中任一元素的地址该如何计算？,开始结点的存放地址（即基地址） 维数和每维的上、下界； 每个数组元素所占用的单元数,其中Cn=L, Ci-1=biCi， 1in（递归）,Loc(j1,j2,jn)=LOC(0,0,0),5.3 矩阵的压缩存储,在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编制程序时，将一个矩阵描述为一个二维数组。矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单。 但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费，为了节省存储空间， 我

9、们可以对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。,并非所有的矩阵都可以压缩,对称矩阵 三角矩阵 稀疏矩阵,5.3.1 特殊矩阵,在一个n阶方阵A中，若元素满足下述性质： aij=aji 0i,jn-1,1 5 1 3 7 a00 5 0 8 0 0 a10 a 11 1 8 9 2 6 a20 a21 a22 3 0 2 5 1 7 0 6 1 3 an-1 0 an-1 1 an-1 2 an-1 n-1 对称矩阵,1、对称矩阵,sak,按行序为主序：,1）对称矩阵的存储方式,在对称矩阵中，第i行恰有i+1个元素，元素总数为： 可以将这些元素存放在

10、一个向量 中,1、对称矩阵,2）为了便于访问对称矩阵A中的元素，我们必须在aij和sak之间找一个对应关系。 若ij，则aij在下三角形中。aij之前的i行（从第0行到第i-1行）一共有1+2+i=i*(i+1)/2个元素，在第i行上，aij之前恰有j个元素（即ai0,ai1,ai2,aij-1），因此有： k=i*(i+1)/2+j 0kn(n+1)/2-1 若ij，则aij是在上三角矩阵中。因为aij=aji，所以只要交换上述对应关系式中的i和j即可得到： k=j*(j+1)/2+i 0kn(n+1)/2-1,1、对称矩阵,2、三角矩阵,以主对角线划分，三角矩阵有上三角和下三角两种。 上三

11、角矩阵中主对角线以下的元素均为常数(a) 。 下三角矩阵正好相反，主对角线以上的元素均为常数(b)。,可以用向量sa0n(n+1)/2存储，将常量存入第一或最后一个单元,5.3.2 稀疏矩阵,1、什么是稀疏矩阵？ 设矩阵A中有s个非零元素，若s远远小于矩阵元素的总数（即smn),则称A为稀疏矩阵。 有s个非零元素。令e=s/(mn)，称e为矩阵的稀疏因子。通常认为e0.05时为稀疏矩阵。,稀疏矩阵的压缩存储方法,一、三元组顺序表,二、行逻辑联接的顺序表,三、 十字链表,存储稀疏矩阵时，为了节省存储单元，使用压缩 存储方法。 非零元素的分布一般是没有规律的，因此在存储 非零元素的同时，还必须同时

12、记下它所在的行和 列的位置（i,j)。 一个三元组(i,j,aij)唯一确定了矩阵A的一个非零 元。因此，稀疏矩阵可由表示非零元的三元组及 其行列数唯一确定。,一、三元组顺序表,例如，下列稀疏矩阵,5.3.2 稀疏矩阵,可由三元组表(1,2,12),(1,3,9),(3,1,-3), (3,6,14),(4,3,24),(5,2,18), (6,1,15),(6,4,-7)和矩阵 维数（6,7）唯一确定,一、三元组顺序表,#define MAXSIZE 12500 typedef struct int i, j; /该非零元的行下标和列下标 ElemType e; / 该非零元的值 Tripl

13、e; / 三元组类型,typedef struct Triple dataMAXSIZE+1; int mu, nu, tu; (mu行数,nu列数,tu非零元个数) TSMatrix; / 稀疏矩阵类型,三元组表表示法：,注意：三元组表中的元素按行（或列）排列。,稀疏矩阵压缩存储的缺点：将失去随机存取功能,求转置矩阵算法,用常规的二维数组表示时的算法,其时间复杂度为: O(munu),for (c=1; c=nu; +c) for (r=1; r=mu; +r) Tcr = Mrc;,三元组表示的转置,三 元 组 表 M.data,三 元 组 表 T.data,不正确！ （1）每个元素的行下

14、标和列下标互换（即三元组中的i和j 互换）； （2）T的总行数mu和总列数nu与M值不同（互换）； （3）重排三元组内元素顺序，使转置后的三元组也按行 （或列）为主序有规律的排列。,上述（1）和（2）容易实现，难点在（3）。,提问：若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种说法正确吗？,有两种实现方法,压缩转置 (压缩)快速转置,方法1：压缩转置,思路：反复扫描M.data中的列序，从小到大依次进行转置。,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=

15、1,col=2,Status TransPoseSMatrix(TSMatrix M, TSMatrix /TranposeSMatrix,压缩转置算法描述：,1、主要时间消耗在查找M.datap.j=col的元素，由两重循环完成: for(col=1; col=M.nu; col+) 循环次数nu for(p=1; p=M.tu; p+) 循环次数tu 所以该算法的时间复杂度为O(nu*tu) -即M的列数与M中非零元素的个数之积 最坏情况：M中全是非零元素，此时tu=mu*nu， 时间复杂度为 O(nu2*mu ) 注：若M中基本上是非零元素时，即使用非压缩传统转置算法的时间复杂度也不过是

16、O(nu*mu) 结论：压缩转置算法不能滥用。 前提：仅适用于非零元素个数很少（即tumu*nu）的情况。,压缩转置算法的效率分析,方法2 快速转置,三 元 组 表 M.data,三 元 组 表 T.data,思路：依次把M.data中的元素直接送入T.data的恰当位置上（即M三元组的p指针不回溯）。,关键：怎样寻找T.data的“恰当”位置？,q,3,5,如果能预知M矩阵中每一列(即T的每一行)的非零元素个数，又能预知每一列第一个非零元素在T.data中的位置,则扫描M.data时便可以将每个元素准确定位。,设计思路：,注意：根据M.data的特征，每列第一个非零元素必 定先被扫描到。,令

17、：M中的列变量用col表示； num col ：存放M中第col 列中非0元素个数， cpot col ：存放M中第col列的第一个非0元素的位置， （即T.data中待计算的“恰当”位置所需参考点）,规律: cpot(1)1 cpotcol cpotcol-1 + numcol-1,M=,3,col 1 2 3 4 5 6,5,9,8,7,6 6 8,1 3 -3,1 6 15,2 1 12,2 5 18,3 1 9,3 4 24,4 6 -7,5 3 14,4,6,2,9,7,5,3,Status FastTransposeSMatrix（TSMatirx M, TSMatirx ,快速转

18、置算法描述：,/M用顺序存储表示，求M的转置矩阵T,/先统计每列非零元素个数,/再生成每列首元位置辅助向量表,/p指向a.data，循环次数为非0元素总个数tu,/查辅助向量表得q，即T中位置,/修改向量表中列坐标值，供同一列下一非零元素定位之用！,1. 与常规算法相比，增加了2个长度为列长的辅助数组(num 和cpot ）。,快速转置算法的效率分析：,2. 从时间上，此算法用了4个并列的单循环，而且其中前3个单循环都是用来产生辅助数组的。 for(col = 1; col =M.nu; col+) 循环次数nu; for( i = 1; i =M.tu; i +) 循环次数tu; for(c

19、ol = 2; col =M.nu; col+) 循环次数nu; for( p=1; p =M.tu ; p + ) 循环次数tu; 该算法的时间复杂度(nu*2)+(tu*2)=O(nu+tu）,传统转置：O(mu*nu) 压缩转置：O(mu*tu) 压缩快速转置：O(nu+tu)牺牲空间效率换时 间效率。,小结：,讨论：最坏情况是tu=nu*mu(即矩阵中全部是非零元素），而此时的时间复杂度也只是O(mu*nu)，并未超过传统转置算法的时间复杂度。,三元组顺序表又称有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。然而，若需随机存取某一行中的非零元

20、，则需从头开始进行查找。,二、行逻辑联接的顺序表,#define MAXSIZE 500 typedef struct Triple dataMAXSIZE + 1; /三元组表 int rposMAXMN + 1; /每一行非零元的位置表 int mu, nu, tu; RLSMatrix; / 行逻辑链接顺序表类型,二、行逻辑联接的顺序表,M=,例如：给定一组下标，求矩阵的元素值,ElemType value(RLSMatrix M, int r, int c) p=M.rposr;/第r行第一个非零值的位置 while (M.datap.i=r / value,三、 十字链表,用途：方便

21、稀疏矩阵的加减运算； 方法：每个非0元素占用5个域。,同一列中下一非零元素的指针,同一行中下一非零元素的指针,十字链表的特点： 每行非零元素链接成带表头结点的线性链表； 每列非零元素也链接成带表头结点的线性链表。 则每个非零元素既是行链表中的一个结点；又是列链表中的一个结点，即呈十字链状。,3 0 0 5 0 -1 0 0 2 0 0 0,1,1,3,1,4,5,2,2,-1,3,2,2,稀疏矩阵的十字链表存储表示,Typedef struct OLNode int i,j; /非零元素下标 ElemType e; struct OLNode *right, *down; OLNode; *O

22、link; Typedef struct Olink *rhead, *chead; int mu,nu,tu; CrossList;,建立稀疏矩阵（算法5.4）,Status CreateSMtrix_OL(CrossList /插入到第一个,else for(q=M.rheadi; (q-right) /CreateSMtrix_OL,输入： m=4,n=3 1,1,3 2,2,5 2,3,4 4,1,8 2,1,7,rhead1,rhead2,rhead3,rhead4,chead1,chead2,chead3,矩阵相加算法,A=,B=,A=A+B,A=,对于每一行做如下处理,A.che

23、ad,A.rhead,1,1,3,1,4,5,2,2,-1,3,1,2,2,2,1,1,4,-1,1,2,2,2,4,2,3,4,4,B.rhead,B.chead,A,B,pa=A.rhead1;pb=B.rhead1;pre=NULL; for(j=1;j=A.nu;+j) hlj=A.cheadj;,if(pa-jj) pre=pa;pa=pa-right;,A.chead,A.rhead,1,1,3,1,4,5,2,2,-1,3,1,2,2,2,1,1,4,-1,1,2,2,2,4,2,3,4,4,B.rhead,A,B,pre,pb,h1,h3,h4,h2,if(pa-jpb-j)

24、复制pb所指的结点赋值为p； if(pre=NULL) A.rheadp-i=p; else pre-right=p; p-right=pa;pre=p; pb=pb-right;,pa,A.chead,A.rhead,1,1,3,1,4,5,2,2,-1,3,1,2,2,2,1,1,4,-1,2,4,2,3,4,4,B.rhead,B.chead,M,N,pa,pb,1,2,2,pre,hl1,hl3,hl4,hl2,if(A.cheadp-j=NULL ,p,A.chead,A.rhead,1,1,3,1,4,5,2,2,-1,3,1,2,2,2,1,1,4,-1,2,4,2,3,4,4,

25、B.rhead,B.chead,A,B,pa,pb,1,2,2,pre,hl1,hl3,hl4,hl2,A.chead,A.rhead,1,1,3,1,4,5,2,2,-1,3,1,2,2,2,1,1,4,-1,2,4,2,3,4,4,B.rhead,B.chead,A,B,pa,pb,1,2,2,pre,hl1,hl3,hl4,hl2,If(Pa-j=pb-j) pa-e+=pa-e; if(e!=0)pre=pa; pa=pa- right;pb=pb-right; else 删除A中该结点,A.chead,A.rhead,1,1,3,1,4,4,2,2,-1,3,1,2,2,2,1,1,

26、4,-1,2,4,2,3,4,4,B.rhead,B.chead,A,B,Pa=NULL,1,2,2,hl1,hl3,hl4,hl2,pre,Pb=NULL,A.chead,A.rhead,1,1,3,1,4,4,2,2,-1,3,1,2,2,2,1,1,4,-1,2,4,2,3,4,4,B.rhead,B.chead,A,B,1,2,2,hl1,hl3,hl4,hl2,pa,pb,A.chead,A.rhead,1,1,3,1,4,4,2,2,-1,3,1,2,2,2,1,1,4,-1,2,4,2,3,4,4,B.rhead,B.chead,A,B,1,2,2,hl1,hl3,hl4,hl2

27、,pa,pb,A.chead,A.rhead,1,1,3,1,4,4,2,2,-1,3,1,2,2,2,1,1,4,-1,2,4,2,3,4,4,B.rhead,B.chead,A,B,1,2,2,hl1,hl3,hl4,hl2,p,pb,Pa=NULL,A.chead,A.rhead,1,1,3,1,4,4,2,2,-1,3,1,2,2,2,1,1,4,-1,2,4,2,3,4,4,B.rhead,B.chead,A,B,1,2,2,hl1,hl3,hl4,hl2,p,pb,Pa=NULL,A.chead,A.rhead,1,1,3,1,4,4,3,1,2,2,2,1,1,4,-1,2,4,

28、2,3,4,4,B.rhead,B.chead,A,B,1,2,2,hl1,hl3,hl4,hl2,pb,Pa=NULL,5.4 广义表的定义,广义表是线性表的推广，也称为列表（lists）广义表中元素既可以是原子类型，也可以是列表。 记为： LS = ( a1 , a2 , ， an ),广义表名 a1是表头(Head） （ a2 ,an ）是表尾 (Tail),1、定义：,n是表长, 第一个元素是表头，而其余元素组成的表称为表尾； 所以任何一个非空表，表头可能是原子，也可能是 列表；但表尾一定是列表。 约定：用小写字母表示原子类型，用大写字母表示 列表。,在广义表中约定：,2、特点：,1）

29、次序性：一个直接前驱和一个直接后继 2）长度：表中最外层包含元素个数 3）深度：当广义表全部用原子代替后，表中括号的最大重数 空表（ ）的深度为1，长度为0 ，原子的深度为0. 4）可递归：自己可以作为自己的子表。 例E=(a, E) 递归表的深度是无穷值，长度是2。 5）可共享: 可以为其它广义表所共享的表。 6）任何一个非空广义表 LS = ( 1, 2, , n) 均可分解为 表头 GetHead(LS) = 1 和 表尾 GetTail(LS) = ( 2, , n) 两部分,E=(a,E)=(a,(a,E)= (a,(a,(a,.)，E为递归表,1）A =( ) 2）B = ( e

30、) 3）C =( a ,( b , c , d ) ) 4）D=( A , B ,C ) 5）E=(a, E),例1：求下列广义表的长度。,n=0，因为A是空表 n=1，表中元素e是原子 n=2，a 为原子，(b,c,d)为子表 n=3，3个元素都是子表 n=2，a 为原子，E为子表,D=(A,B,C)=( ),(e),(a,(b,c,d)，共享表,6)F=( ),n=1,Gethead(B)= GetTail(B)= GetHead(C)= GetTail(C)= GetHead(D)= GetTail(D)= GetHead(E)= GetTail(E)= GetHead( )= GetT

31、ail( )=,B = ( e ) C =( a ,( b , c , d ) ) D=( A , B ,C ) E=(a, E),e,( ),a,(b,c,d),A,(B,C),a,(E),例2：求下列广义表的表头和表尾。,GetTail( GetHead (a,b),(c,d),（b）, A=( a , (b, A) ),例3：试用图形表示下列广义表. （设 代表原子， 代表子表）,e, D=(A,B,C)=( ( ),(e),( a, (b,c,d) ) ),的长度为3，深度为3,的长度为2，深度为,深度括号的重数 结点的最大层数,广义表的抽象数据类型定义,ADT GList 数据对象：

32、D= ei|i=1，2，n； n0； ei AtomSet或 ei Glist, AtomSet为某个数据对象 数据关系：R1=| ei-l，ei D， 2in 基本操作： InitGList(&L) 操作结果：创建空的广义表L CreateGList(&L，S) 初始条件：s是广义表的书写形式串 操作结果：由s创建广义表L,DestroyGList(&L) 初始条件：广义表L存在。 操作结果：销毁广义表L COpyGList(&T，L) 初始条件：广义表L存在。 操作结果：由广义表L复制得到广义表T GListLength(L) 初始条件：广义表L存在。 操作结果：求广义表L的长度，即元素个

33、数。 GListDepth(L) 初始条件：广义表L存在。 操作结果：求广义表L的深度。,GListEmpty(L) 初始条件：广义表L存在。 操作结果：判定广义表L是否为空。 GetHead(L) 初始条件：广义表L存在。 操作结果：取广义表L的头。 GetTail(L) 初始条件：广义表L存在。 操作结果：取广义表L的尾。,InsertFirst_GL(&l，e) 初始条件：广义表L存在。 操作结果；插入元素e作为广义表L的第一元素。 DeleteFirst_GL(&L，&e) 初始条件：广义表L存在。 操作结果：删除广义表L的第一元素，并用e返回其值 Traverse_GL(L，Visi

34、t() 初始条件：广义表L存在。 操作结果；遍历广义标L,用函数visit处理每个元素。 ADT GList,5.5 广义表的存储结构,由于广义表的元素可以是不同结构（原子或列表），难以用顺序存储结构表示，通常用链式结构，每个元素用一个结点表示。,1.原子结点 2.表结点,注意：列表的“元素”还可以是列表，所以结点可能有两种形式,方法1：表头、表尾表示法,表结点: 原子结点：,5.5 广义表的存储结构, A =( ), C =( a ,( b , c , d ) ),例：, B=( e ),A=NULL,5.5 广义表的存储结构, E=(a, E), D=(A,B,C)= ( ),(e),(a

35、,(b,c,d),5.5 广义表的存储结构,方法2：子表表示法,指向下一结点,表结点: 原子结点：,5.5 广义表的存储结构, A =( ), C =( a ,( b , c , d ) ，e),b,0,c,0,d,0,例：, B=( e ),A=NULL,e,0,1,B,C,e,0,本章小结,理解数组的逻辑结构是线性结构的推广； 掌握数组在行优先存储和列优先存储结构中的地址计算 方法(注意我们所讲的公式前提是在数组各下界为0） 掌握对特殊矩阵进行压缩存储时的下标变换公式； 理解稀疏矩阵的三种压缩存储方法的特点和适用范围， 以三元组表示稀疏矩阵时进行矩阵转置所采用的处理方法； 掌握广义表的定义、存储结构；,书面作业: p32: 5.8题, p33: 5.10题，5.12题 p35: 5.25题 上机作业: 识别广义表的表头和表尾(p138),作 业,