北邮算法与数据结构.ppt

《北邮算法与数据结构.ppt》由会员分享，可在线阅读，更多相关《北邮算法与数据结构.ppt（40页珍藏版）》请在三一办公上搜索。

1、数据结构-第五章 数组和广义表,1,第五章 数组和广义表,5.1 数组和线性表的关系以及数组的运算5.2 数组的顺序存储结构 5.3 矩阵的压缩存储5.4 广义表的定义和表示方法5.5 广义表的存储结构5.6 广义表的递归算法本章学习要点、习题与上机作业,本质上是非线性结构。扩展的线性表：表中的数据元素本身也是一个数据结构。,数据结构-第五章 数组和广义表,2,5.1 数组和线性表的关系以及数组的运算,任何数组A都可以看作一个线性表 A=(a1,a2,ai,an)二维数组mn时，ai是数组中第i行所有元素，0im-1，表中每一个元素是一个一维数组；三维数组时，表中每一个元素是一个二维数组；n维

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

3、troyArray(&A)(3)取得指定下标的数组元素值 Value(A,&e,index1,indexn)(4)为指定下标的数组元素重新赋值 Assign(&A,e,index1,indexn),数据结构-第五章 数组和广义表,5,5.2 数组的顺序存储结构,一维数组,b,基地址,L个单元,a0,a1,ai,LOCi=LOC0+iL=b+i L=c0+c1 ic1=Lc0=b=LOC0,an-1,ElemType 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

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

5、0.9,1.6,5.12 设每数组元素占用8个存储单元，起始地址为1000,求按低下标优先（类似行优先）顺序存储时，LOC6,1,4,7=？,ElemType ab1b2.bn;,数据结构-第五章 数组和广义表,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,0+c1j1+c2j2+c3j3+c4j4=1000+c1j1+c2j2+c3j3+82=1000+c1j1+

6、c2j2+883+82=1000+c1j1+6461+883+82=1000+384103+6461+883+82=13112,数据结构-第五章 数组和广义表,9,5.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-1 当ij,a11 a21 a22 a31 aij(aji)ann,k 0 1 2 3 n(n+1)/2-1,sa,aij,aji,数据结构-第五章 数

7、组和广义表,10,5.3.2 三角矩阵,特点 对角线以下(或者以上)的数据元素(不包括对角线)全部为常数c。存储方法 重复元素c共享一个元素存储空间，共占用n(n+1)/2+1个元素空间:sa0.n(n+1)/2。sa0=C 上三角矩阵 下三角矩阵 k=(i-1)(2n-i+2)/2+j-i+1 ij k=i(i-1)/2+j ij 0 ij 0 ij,数据结构-第五章 数组和广义表,11,5.3.3 带状矩阵（对角矩阵）,特点 在nn的方阵中，非零元素集中在主对角线及其两侧共L(奇数)条对角线的带状区域内 L对角矩阵。存储方法 只存储带状区内的元素。1）以对角线的顺序存储,共n*L个元素。1

8、 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 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)/2,k 0 n*L-1,sa,数据结构-第五章 数组和广义表,12,2）只存储带状区内的元素。除首行和末行，按每行 L个元素，共(n-2)L+(L+1)=(n-1)L+1 个元素。sa0.(n-1)L

9、,存储地址计算：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 2 8 3,8 2 3/4 2 0 3 5 7,7 6 8 9 6 9 1 5 6 1,4 2/2 8 3,sa,k 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,数据结构-第五章 数组和广义表,13,5.3.4 随机稀疏矩阵,特点 大多数元素为零。常用存储方法 记录每一非零元素(i,j,ai

10、j)节省空间，但丧失随机存取功能顺序存储：三元组表链式存储：十字(正交)链表 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 0 0 0 0 0 0 28 0 0 0,=t/(mn)0.05,数据结构-第五章 数组和广义表,14,5.3.4.1 三元组表,类型定义,#define MAXSIZE 1000/设定非零元素最大值typedef struct int i,j;ElemType e;Triple;typedef struct Triple dataMAXSIZE+1;/三元组表，data0未用int mu,nu,tu;/

11、行数、列数、非零元个数TSMatrix;,数据结构-第五章 数组和广义表,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 28,a.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-15,b.data,数据结构-第五章 数组和广义表,16,算法1 O(nt),void TransMatrix(TSMatrix/修正q值/TransMatrix,数据结构-第五章 数组和广义表,17,算法2 快速

12、转置法 O(n+t),引入两个辅助向量：num1:a.n：a中每列的非零元素个数cpot1:a.n：a中每列的第一个非零元素在b中的位置a中的列号 col numcol cpotcol 1 2 1 2 1 3 3 2 4 4 2 6 5 0 8 6 1 8,cpot1=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 28,a,转置,i j e1 1 1 152 1 5 913 2 2 224 3 2 35 3 6 286 4 1 227 4 3

13、-68 6 1-15,b,数据结构-第五章 数组和广义表,18,Statue FastTransMatrix(TSMatrix/FastTransMatrix,数据结构-第五章 数组和广义表,19,5.3.4.2 行逻辑链接的表,便于随机存取任意一行的非零元素。,typedef struct Triple dataMAXSIZE+1;int rposMAXRC+1;int mu,nu,tu;RLSMatrix;,RLSMatrix M;,这种方式可以便于某些运算，如：稀疏矩阵相乘等。,数据结构-第五章 数组和广义表,20,5.3.4.3 十字（正交）链表,特点在行、列两个方向上，将非零元素链接

14、在一起。克服三元组表在矩阵的非零元素位置或个数经常变动时的使用不便。类型定义,i j e down right,typedef struct OLNode int i,j;ElemType e;struct OLNode*right,*down;OLNode,*OLink;typedef struct OLink*rhead,*chead;int mu,nu,tu;CrossList;,数据结构-第五章 数组和广义表,21,4 7,CrossList M;,数据结构-第五章 数组和广义表,22,算法示例 从终端接收信息建立稀疏矩阵的十字链表,算法思想：1）赋值矩阵的行数mu、列数nu和非零元素

15、个数tu；2）申请行、列头指针向量，将各行、列链表置为空链表；3）读入一个非零元素的行号i、列号j、值e 3.1）建立该元素的结点，赋值其三元组 3.2）寻找该结点在行表中的插入位置并插入 3.3）寻找该结点在列表中的插入位置并插入 3.4）存在下一个非零元素，转3；否则，结束。,数据结构-第五章 数组和广义表,23,5.4 广义表（列表）的定义和表示方法,概念 广义表是由零个或多个原子或者子表组成的有限序列。可以记作：LS=(d1,d2,dn)原子：逻辑上不能再分解的元素。子表：作为广义表中元素的广义表。与线性表的关系 广义表中的元素全部为原子时即为线性表。线性表是广义表的特例，广义表是线性

16、表的推广。,数据结构-第五章 数组和广义表,24,广义表的表示方法和相关术语,表长 表深 表头 表尾 A=()0 1-B=(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),a,b,A,B=(A,c),B,D=(a,D),a,D,L=(A,B),L,A,B,a,b,c,

17、A,a,b,c,表,原子,含有递归,含有共享,数据结构-第五章 数组和广义表,26,规定所有表都有名字时，广义表的表示方法例 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

18、(1,10),(2,6)B=y(D,2),(2,1)D=x(3,5),数据结构-第五章 数组和广义表,27,基本操作 结构的创建和销毁 InitGList(,数据结构-第五章 数组和广义表,28,抽象数据类型定义ADT GList 数据对象：D=ei|i=1,2,n;n0;eiAtomSet 或 eiGList,AtomSet为某个数据对象 数据关系：R=|ei-1,ei D,2i n 基本操作：InitGList(初始条件：S是广义表的书写形式串。操作结果：由S创建广义表L。ADT GList,数据结构-第五章 数组和广义表,29,5.5 广义表的存储结构,5.5.1 方法头尾链表形式 类型

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

20、,0 a,B=(a,A),C=(a,b),c,d),D=(a,D),(A),(D),(a,b),(c,d),(d),(b),GList1 A,B,C,D,数据结构-第五章 数组和广义表,31,5.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;stru

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

22、TH（LS）=1 当LS为空表时 DEPTH（LS）=0 当LS为原子时 归纳项：DEPTH（LS）=1+maxDEPTH(ai)n1算法描述,1in,数据结构-第五章 数组和广义表,34,int 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;/GListDepth,LS=(a1,a2,an)表头：a1 表尾：(a2,an),数据结构

23、-第五章 数组和广义表,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)return dep1;else return dep2;/GListDepth,数据结构-第五章 数组和广义

24、表,36,示例2 复制广义表复制操作的递归定义 基本项：InitGList(NEWLS)当LS为空表时；复制单原子结点 当LS为原子时；归纳项：建表结点；复制表头；复制表尾；算法描述CopyGLists,LS=NULL NEWLS=NULL,数据结构-第五章 数组和广义表,37,Status CopyGList(GList1/CopyGList,数据结构-第五章 数组和广义表,38,了解数组类型的特点以及在高级编程语言中的两种存储表示和实现方法，并熟练掌握数组在以行为主的存储结构中的地址计算方法。掌握广义表的结构特点及其存储表示方法，学会对非空广义表进行分解的两种分析方法：即可将一个非空广义表

25、分解为表头和表尾两部分或者分解为n个子表。巩固递归算法的设计思想。,本章学习要点,数据结构-第五章 数组和广义表,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能否相加矩阵相加运算打印运算结果,