北邮算法与数据结构.ppt

《北邮算法与数据结构.ppt》由会员分享，可在线阅读，更多相关《北邮算法与数据结构.ppt（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构-第五章 数组和广义表1第五章第五章 数组和广义表数组和广义表5.1 5.1 数组和线性表的关系以及数组的运算数组和线性表的关系以及数组的运算5.2 5.2 数组的顺序存储结构数组的顺序存储结构 5.3 5.3 矩阵的压缩存储矩阵的压缩存储5.4 5.4 广义表的定义和表示方法广义表的定义和表示方法5.5 5.5 广义表的存储结构广义表的存储结构5.6 5.6 广义表的递归算法广义表的递归算法本章学习要点、习题与上机作业本章学习要点、习题与上机作业 本质上是非线性结构。扩展的线性表：本质上是非线性结构。扩展的线性表：表中的数据元素本身也是一个数据结构。表中的数据元素本身也是一个数据结构

2、。数据结构-第五章 数组和广义表25.1 数组和线性表的关系以及数组的运算数组和线性表的关系以及数组的运算任何数组任何数组A都可以看作一个线性表都可以看作一个线性表 A=(a1,a2,ai,an)二维数组mn时，ai是数组中第i行所有元素，0im-1，表中每一个元素是一个一维数组；三维数组时，表中每一个元素是一个二维数组；n维数组时，表中每一个元素是一个(n-1)维数组()()()()()()()()()=A mna00 a01 a 0,n-1a10 a11 a 1,n-1 am-1,0 am-1,1 am-1,n-1数据结构-第五章 数组和广义表3数组与线性表之间的关系数组与线性表之间的关系

3、线性表的扩展，其数据元素本身也是线性表数组的特点数组的特点数组中各元素都具有统一的类型可以认为，d维数组的非边界元素具有d个直接前趋和d个直接后继数组维数确定后，数据元素个数和元素之间的关系不再发生改变，适合于顺序存储每组有定义的下标都存在一个与其相对应的值在数组上的基本操作在数组上的基本操作给定一组下标，取得相应的数据元素值给定一组下标，修改相应的数据元素值数据结构-第五章 数组和广义表4数组的基本操作定义数组的基本操作定义(1)构造n维数组 InitArray(&A,n,bound1,boundn)(2)销毁数组A DestroyArray(&A)(3)取得指定下标的数组元素值 Value

4、(A,&e,index1,indexn)(4)为指定下标的数组元素重新赋值 Assign(&A,e,index1,indexn)数据结构-第五章 数组和广义表55.2 数组的顺序存储结构数组的顺序存储结构一维数组一维数组b基地址L个单元a0a1aiLOCi=LOC0+iL =b+i L =c0+c1 ic1=Lc0=b=LOC0an-1ElemType an；数据结构-第五章 数组和广义表6二维数组二维数组 a00 a01 a02 .a0,n-1 a10 a11 a12 .a1,n-1 :am-1,0 am-1,1 am-1,2 .am-1,n-1a=mna00a0,n-1a10aijam-1

5、,n-1ba1LOCi,j=LOC0,0+(in+j)L =c0+c1i+c2j c2=L c1=nc2=b2c2 c0=b=LOC0,0注：Pascal、C语言以行序为主序 Fortran 语言以列序为主序ElemType amn;ElemType amn;“行序为主序”即“低下标优先”“列序为主序”即“高下标优先”aij数据结构-第五章 数组和广义表7n维数组维数组 LOCj1,j2,.,jn=c0+c1j1+c2j2+.+cnjn=c0+ciji cn=L;ci-1=cibi (1in)c0=b=LOC0,0,.,0 数组是一种随机存取结构数组是一种随机存取结构:对任一元素定位时间相等对

6、任一元素定位时间相等.思考：ElemType A3.7,0.9,1.6,5.12 设每数组元素占用8个存储单元，起始地址为1000,求按低下标优先（类似行优先）顺序存储时，LOC6,1,4,7=？ElemType ab1b2.bn;数据结构-第五章 数组和广义表8 参考解答参考解答 维数维数:b1=5,b2=10,b3=6,b4=8:b1=5,b2=10,b3=6,b4=8法法1 LOC6,1,4,7 =1000+1068(6-3)+68(1-0)+8(4-1)+(7-5)8 =13112法法2相当于A0.4,0.9,0.5,0.7,求LOC3,1,3,2LOC3,1,3,2=LOC0,0,0

7、,0+c1j1+c2j2+c3j3+c4j4 =1000+c1j1+c2j2+c3j3+82 =1000+c1j1+c2j2+883+82 =1000+c1j1+6461+883+82 =1000+384103+6461+883+82 =13112数据结构-第五章 数组和广义表95.3 矩阵的压缩存储矩阵的压缩存储 目的是节省空间。5.3.1 对称矩阵对称矩阵特点特点 在nn的矩阵a中，满足如下性质：aij=aji (1 i,j n)存储方法存储方法 只存储下(或者上)三角(包括主对角线)的数据元素。共占用n(n+1)/2个元素空间。k=i(i-1)/2+j-1 当ij j(j-1)/2+i-

8、1 当ij 0 ijC Ck k 0 n(n+1)/2 0 n(n+1)/2CC上三角矩阵下三角矩阵i i j ji i j j数据结构-第五章 数组和广义表115.3.3 带状矩阵（对角矩阵）带状矩阵（对角矩阵）特点特点 在nn的方阵中，非零元素集中在主对角线及其两侧共L(奇数)条对角线的带状区域内 L对角矩阵。存储方法存储方法 只存储带状区内的元素。1）以对角线的顺序存储,共n*L个元素。1 2 3 4 5 61 8 2 3 0 0 02 4 2 0 3 0 03 5 7 7 6 8 04 0 9 6 9 1 55 0 0 6 1 4 26 0 0 0 2 8 3五对角矩阵 /3 3 8

9、5 /2 0 6 1 2 8 2 7 9 4 3 4 7 6 1 8 /5 9 6 2 /s-2.2;1.6-2-1 0 1 2 1 2 3 4 5 6 i1=i-jj1=j|i-j|(L-1)/2k 0 n*L-1sa数据结构-第五章 数组和广义表122）只存储带状区内的元素。除首行和末行，按每行 L个元素，共(n-2)L+(L+1)=(n-1)L+1 个元素。sa0.(n-1)L 存储地址计算：k=(i-1)L+(j-i)1 i,j n|i-j|(L-1)/2 8 2 3 0 0 0 4 2 0 3 0 0 5 7 7 6 8 0 0 9 6 9 1 5 0 0 6 1 4 2 0 0 0

10、 2 8 38 2 3 /4 2 0 3 5 77 6 8 9 6 9 1 5 6 1 4 2 /2 8 3sak 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 数据结构-第五章 数组和广义表135.3.4 随机稀疏矩阵随机稀疏矩阵特点特点 大多数元素为零。常用存储方法常用存储方法 记录每一非零元素(i,j,aij)节省空间，但丧失随机存取功能顺序存储：三元组表链式存储：十字(正交)链表 15 0 0 22 0 -15 0 11 3 0 0 0 0 0 0 -6 0 0 0 0 0 0 0 0 91 0

11、0 0 0 0 0 0 28 0 0 0=t/(mn)0.05数据结构-第五章 数组和广义表145.3.4.1 三元组表三元组表类型定义类型定义#define MAXSIZE 1000 /设定非零元素最大值typedef struct int i,j;ElemType e;Triple;typedef struct Triple dataMAXSIZE+1;/三元组表，data0未用int mu,nu,tu;/行数、列数、非零元个数TSMatrix;i j e1 1 151 4 221 6 -152 2 222 3 33 4 -65 1 916 3 281 12 23 34 45 56 67

12、78 8mm数据结构-第五章 数组和广义表15应用例应用例 求转置矩阵求转置矩阵 i j e1 1 1 152 1 4 223 1 6 -154 2 2 225 2 3 36 3 4 -67 5 1 918 6 3 28a.dataa.data转置转置 i j e1 1 1 152 1 5 913 2 2 224 3 2 35 3 6 286 4 1 227 4 3 -68 6 1 -15b.data数据结构-第五章 数组和广义表16算法算法1 O(nt)void TransMatrix(TSMatrix&b,TSMatrix a)b.mu=a.nu;b.nu=a.mu;b.tu=a.tu;i

13、f (b.tu )q=1;/指示b中存放数据的位置，初值为1 for(col=1;col=a.nu;col+)/对a的每一列 for(p=1;p=a.tu;p+)/对a的每个三元组检查 if (a.datap.j=col)/找列号为col的三元组 b.dataq.i=a.datap.j;b.dataq.j=a.datap.i;b.dataq.e=a.datap.e;q+;/修正q值 /TransMatrix数据结构-第五章 数组和广义表17 算法算法2 快速转置法 O(n+t)引入两个辅助向量：num1:a.n：a中每列的非零元素个数cpot1:a.n：a中每列的第一个非零元素在b中的位置a中

14、的列号 col numcol cpotcol 1 2 1 2 1 3 3 2 4 4 2 6 5 0 8 6 1 8cpot1=1cpotcol=cpotcol-1+numcol-1 (2coln)i j e1 1 1 152 1 4 223 1 6 -154 2 2 225 2 3 36 3 4 -67 5 1 918 6 3 28a a转置转置 i j e1 1 1 152 1 5 913 2 2 224 3 2 35 3 6 286 4 1 227 4 3 -68 6 1 -15b b数据结构-第五章 数组和广义表18 Statue FastTransMatrix(TSMatrix&b,

15、TSMatrix a)b.mu=a.nu;b.nu=a.mu;b.tu=a.tu;if (b.tu)for (col=1;col=a.nu;+col)/num清零 numcol=0;for(t=1;t=a.tu;+t)/对a.tu个非零元素按列号计数 +numa.datat.j;cpot1=1;/生成cpot for(col=2;col=a.nu;+col)cpotcol=cpotcol-1+numcol-1;for (p=1;p=a.tu;+p)/对a.tu个非零元素转置 col=a.datap.j;q=cpotcol;b.dataq.i=a.datap.j;b.dataq.j=a.data

16、p.i;b.dataq.e=a.datap.e;+cpotcol;return OK;/FastTransMatrix数据结构-第五章 数组和广义表195.3.4.2 行逻辑链接的表行逻辑链接的表便于随机存取任意一行的非零元素。typedef struct Triple dataMAXSIZE+1;int rposMAXRC+1;int mu,nu,tu;RLSMatrix;i j e1 1 151 4 221 6 -152 2 222 3 33 4 -65 1 916 3 28 1 4 6 0 7 8 1 2 3 4 5 612345678M.rposM.dataRLSMatrix M;这种

17、方式可以便于某些运算，如：稀疏矩阵相乘等。这种方式可以便于某些运算，如：稀疏矩阵相乘等。这种方式可以便于某些运算，如：稀疏矩阵相乘等。这种方式可以便于某些运算，如：稀疏矩阵相乘等。数据结构-第五章 数组和广义表205.3.4.3 十字（正交）链表十字（正交）链表特点特点在行、列两个方向上，将非零元素链接在一起。克服三元组表在矩阵的非零元素位置或个数经常变动时的使用不便。类型定义类型定义 i j e down righttypedef struct OLNode int i,j;ElemType e;struct OLNode *right,*down;OLNode,*OLink;typedef

18、 struct OLink *rhead,*chead;int mu,nu,tu;CrossList;数据结构-第五章 数组和广义表2134 7 60 0 80 -5 0 04 0 0 711 622 -5 31 414 8 M.rheadM.cheadCrossList M;数据结构-第五章 数组和广义表22算法示例算法示例 从终端接收信息建立稀疏矩阵的十字链表算法思想：1）赋值矩阵的行数mu、列数nu和非零元素个数tu；2）申请行、列头指针向量，将各行、列链表置为空链表；3）读入一个非零元素的行号i、列号j、值e 3.1）建立该元素的结点，赋值其三元组 3.2）寻找该结点在行表中的插入位置

19、并插入 3.3）寻找该结点在列表中的插入位置并插入 3.4）存在下一个非零元素，转3；否则，结束。数据结构-第五章 数组和广义表235.4 广义表（列表）的定义和表示方法广义表（列表）的定义和表示方法概念概念 广义表是由零个或多个原子或者子表组成的有限序列。可以记作：LS=(d1,d2,dn)原子：逻辑上不能再分解的元素。子表：作为广义表中元素的广义表。与线性表的关系与线性表的关系 广义表中的元素全部为原子时即为线性表。线性表是广义表的特例，广义表是线性表的推广。数据结构-第五章 数组和广义表24广义表的表示方法和相关术语广义表的表示方法和相关术语 表长 表深 表头 表尾 A=()0 1 -B

20、=(a,A)=(a,()2 2 a ()C=(a,b),c,d)3 2 (a,b)(c,d)D=(a,D)=(a,(a,(a,)2 a (D)表的长度表的长度 表中的元素（第一层）个数。表的深度表的深度 表中元素的最深嵌套层数。表头表头 表中的第一个元素。表尾表尾 除第一个元素外，剩余元素构成的广义表。非空广义表的表尾必定仍为广义表。数据结构-第五章 数组和广义表25广义表的图形表达方法广义表的图形表达方法 A=(a,b)abAB=(A,c)BD=(a,D)aDL=(A,B)LABabcAabc表原子含含有有递递归归含含有有共共享享数据结构-第五章 数组和广义表26规定所有表都有名字时，广义表

21、的表示方法规定所有表都有名字时，广义表的表示方法例 A(a,b)B(A(a,b),c)L(A(a,b),B(A(a,b),c)D(a,D(a,D()广义表结构的分类广义表结构的分类纯表：与树型结构对应的广义表。再入表：允许结点共享的广义表。递归表：允许递归的广义表。递归表再入表纯表线性表广义表的应用广义表的应用 如：程序的语句结构;m元多项式的表示P(x,y,z)=x10y3z2+2x6y3z2+3x5y2z+2yz+15 =(x10y3+2x6y3)z2+(3x5y2+2y)z+15P=z(A,2),(B,1),(15,0)A=y(C,3)C=x(1,10),(2,6)B=y(D,2),(2

22、,1)D=x(3,5)数据结构-第五章 数组和广义表27基本操作基本操作 结构的创建和销毁结构的创建和销毁 InitGList(&L);DestroyGList(&L);CreateGList(&L,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();数据结构-第五章 数组和广义表28抽象数据类

23、型定义抽象数据类型定义ADT GList 数据对象：数据对象：D=ei|i=1,2,n;n0;eiAtomSet 或 eiGList,AtomSet为某个数据对象 数据关系：数据关系：R=|ei-1,ei D,2i n 基本操作：基本操作：InitGList(&L);操作结果：创建空的广义表L。CreateGList(&L,S);初始条件：S是广义表的书写形式串。操作结果：由S创建广义表L。ADT GList 数据结构-第五章 数组和广义表295.5 广义表的存储结构广义表的存储结构5.5.1 方法方法头尾链表形式头尾链表形式 类型定义类型定义tag=0 atom原子结点hp:指示表头的指针t

24、p:指示表尾的指针typedef enum ATOM,LIST ElemTag;/ATOM=0:原子；LIST=1：子表typedef struct GLNodeElemTag tag;union AtomType atom;struct struct GLNode *hp,*tp;ptr;*GList1;tag=1 hp tp 表结点ptrGL=(a1,a2,an)head(GL)=a1Tail(GL)=(a2,an)数据结构-第五章 数组和广义表30示例示例A=()A=NULLBC11 0 a111 0 c0 d11 0 a0 b11 D0 aB=(a,A)C=(a,b),c,d)D=(a

25、,D)(A)(A)(D)(D)(a,b)(a,b)(c,d)(c,d)(d)(d)(b)(b)GList1 A,B,C,D数据结构-第五章 数组和广义表315.5.2 方法方法2扩展的线性链表形式扩展的线性链表形式 类型定义类型定义tag=1 hp tp 表结点tag=0 atom tp原子结点hp:指向表头的指针tp:指向同一层的下 一个结点(a1,a2,an)typedef enum ATOM,LIST ElemTag;/ATOM=0:原子；LIST=1：子表typedef struct GLNodeElemTag tag;union AtomType atom;struct struct

26、 GLNode *hp;struct GLNode *tp;*GList2;数据结构-第五章 数组和广义表32示例示例A 1 1 0 a A=()1 BB=(a,A)C=(a,b),c,d)C1 1 0 c0 d 0 a0 b 1 DD=(a,D)0 a1 a aD Da aA A(a,b)(a,b)c cd da ab bGList2 A,B,C,D数据结构-第五章 数组和广义表5.6 广义表的递归算法广义表的递归算法 广义表的特点：定义是递归的。示例约定：非递归表且无共享子表。示例示例1 计算广义表的深度方法一方法一 分析表中各元素（子表）LS=(a1,a2,an)求深度的递归函数 基本项

27、：DEPTH（LS）=1 当LS为空表时 DEPTH（LS）=0 当LS为原子时 归纳项：DEPTH（LS）=1+maxDEPTH(ai)n1算法描述1in数据结构-第五章 数组和广义表34int GListDepth(GList1 L)if (!L)return 1;/空表 if (L-tag=ATOM)return 0;/单原子 for(max=0,pp=L;pp;pp=pp-ptr.tp)dep=GListDepth(pp-ptr.hp);if(depmax)max=dep;return max+1;/GListDepthtag=1 hp tp 表结点ptrLS=(aLS=(a1 1,a

28、,a2 2,a,an n)表头：表头：a a1 1 表尾：表尾：(a(a2 2,a,an n)数据结构-第五章 数组和广义表35 方法二方法二 分析表头和表尾求深度的递归函数 1 当LS为空表 depth(LS)=0 当LS为单原子 maxdepth(head(LS)+1,depth(tail(LS)其它情况算法描述 int GListDepth(GList1 L)if (!L)return 1;/空表 if (L-tag=ATOM)return 0;/单原子 dep1=GListDepth(L-ptr.hp)+1;dep2=GListDepth(L-ptr.tp);if (dep1dep2)

29、return dep1;else return dep2;/GListDepth数据结构-第五章 数组和广义表36示例示例2 复制广义表复制操作的递归定义 基本项：InitGList(NEWLS)当LS为空表时；复制单原子结点 当LS为原子时；归纳项：建表结点；复制表头；复制表尾；算法描述CopyGListsLS=NULL NEWLS=NULLLS=NULL NEWLS=NULL1 1NEWLSNEWLSNEWLS-ptr.tpNEWLS-ptr.tpNEWLS-ptr.hpNEWLS-ptr.hp0 x0 xLSLS0 x0 xNEWLSNEWLS1 1LSLSLS-ptr.tpLS-ptr

30、.tpLS-ptr.hpLS-ptr.hp数据结构-第五章 数组和广义表37Status CopyGList(GList1&T,GList1 L)if (!L)T=NULL;/复制空表 else T=(GList1)malloc(sizeof(GLNode);if(!T)exit(OVERFLOW);T-tag=L-tag;if(L-tag=ATOM)T-atom=L-atom;/复制单原子 else CopyGList(T-ptr.hp,L-ptr.hp);CopyGList(T-ptr.tp,L-ptr.tp);return OK;/CopyGList数据结构-第五章 数组和广义表38了了

31、解解数数组组类类型型的的特特点点以以及及在在高高级级编编程程语语言言中中的的两两种种存存储储表表示示和和实实现现方方法法，并并熟熟练练掌掌握握数数组组在在以以行行为主的存储结构中的地址计算方法。为主的存储结构中的地址计算方法。掌掌握握广广义义表表的的结结构构特特点点及及其其存存储储表表示示方方法法，学学会会对对非非空空广广义义表表进进行行分分解解的的两两种种分分析析方方法法：即即可可将将一一个个非非空空广广义义表表分分解解为为表表头头和和表表尾尾两两部部分分或或者者分分解为解为n n个子表。巩固递归算法的设计思想。个子表。巩固递归算法的设计思想。本章学习要点本章学习要点数据结构-第五章 数组和

32、广义表39习题习题1.设有三对角矩阵(aij)nn，将其三条对角线上的元素存于数组B(-1:1,1:n)中，使得B(u,v)=aij，试推倒出用i、j表示u、v的下标变换公式。2.求下列广义表操作的结果：(1)HeadTailHead(a,b),(c,d)(2)TailHeadTail(a,b),(c,d)注：是函数的符号3.利用广义表的Head和Tail操作把原子c从广义表L=(a,b),(c,d)中分离出来，并求表L的长度和深度。4.画出广义表L=(a,b),(c,d)的两种存储结构图。数据结构-第五章 数组和广义表40上机作业上机作业 假设稀疏矩阵A和B均以三元组表作为存储结构，试写出矩阵相加(相乘选做)的算法，另设三元组表C存放结果矩阵。矩阵相加测试实例：0 7 0 8 0 2 0 1 0 0 A=4 0 0 0 5 B=4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 0 6 0 0 -6 0 处理过程提示：输入稀疏矩阵A和B检测A和B能否相加矩阵相加运算打印运算结果