北大数据结构与算法课件11高级线性表

数据结构与算法第十一章高级线性表信息科学与技术学院网络与信息系统研究所北京大学信息学院张铭编写©版权所有，转载或翻印必究Page2主要内容„11.1多维数组„11.2广义表„11.3存储管理技术北京大学信息学院张铭编写©版权所有，转载或翻印必究Page311.1多维数组„基本概念„„数组的空间结构数组的空间结构„„数组的存储数组的存储„„数组的声明数组的声明„用数组表示特殊矩阵„稀疏矩阵北京大学信息学院张铭编写©版权所有，转载或翻印必究Page4基本概念„„数组（数组（ArrayArray）是数量和元素类型固定的）是数量和元素类型固定的有序序列有序序列„„静态数组必须在定义它的时候指定其静态数组必须在定义它的时候指定其大小和类型大小和类型„„动态数组可以在程序运行才分配内存动态数组可以在程序运行才分配内存空间空间北京大学信息学院张铭编写©版权所有，转载或翻印必究Page5基本概念（续）„„多维数组（多维数组（MultiMulti--arrayarray））是向量的扩充是向量的扩充„„向量的向量就组成了多维数组向量的向量就组成了多维数组„„可以表示为：可以表示为：ELEMA[cELEMA[c11..d..d11][c][c22..d..d22]]……[[ccnn..d..dnn]]„„ccii和和ddii是各维下标的下界和上界。所以其元是各维下标的下界和上界。所以其元素个数为：素个数为：∏=+−niiicd1)1(北京大学信息学院张铭编写©版权所有，转载或翻印必究Page6数组的空间结构数组的空间结构d1=3,d2=5,d3=5d1d2a[2][2]d1d2d3a[2][3][3]二维数组三维数组d1[1..3],d2[1..5],d3[1..5]分别为3个维北京大学信息学院张铭编写©版权所有，转载或翻印必究Page7数组的存储数组的存储„内存是一维的，所以数组的存储也只能是一维的„以行为主序（也称为“行优先”）„以列为主序（也称为“列优先”）X=123456789北京大学信息学院张铭编写©版权所有，转载或翻印必究Page8„C/C++、Pascal行优先„先排最右的下标„从右向左„最后最左的下标„例如对于三维数组a[1..k,1..m,1..n]的元素axyz可以如下排列：北京大学信息学院张铭编写©版权所有，转载或翻印必究Page9PascalPascal语言的行优先存储语言的行优先存储a111a112a113…a11na121a122a123…a12n…………………………a1m1a1m2a1m3…a1mna211a212a213…a21na221a222a223…a22n…………………………a2m1a2m2a2m3…a2mn┇ak11ak12ak13…ak1nak21ak22ak23…ak2n…………………………akm1akm2akm3…akmn123nC12m222222222222北京大学信息学院张铭编写©版权所有，转载或翻印必究Page10„FORTRAN列优先„先排最左的下标„从左向右„最后最右的下标„例如对于三维数组a[1..k,1..m,1..n]的元素axyz可以如下排列：北京大学信息学院张铭编写©版权所有，转载或翻印必究Page11FORTRANFORTRAN的列优先存储的列优先存储a111a211a311…ak11a121a221a321…ak21…………………………a1m1a2m1a3m1…akm1a112a212a312…ak12a122a222a322…ak22…………………………a1m2a2m2a3m2…akm2┇a11na21na31n…ak1na12na22na32n…ak2n…………………………a1mna2mna3mn…akmn123kC12m222222222222北京大学信息学院张铭编写©版权所有，转载或翻印必究Page12„„C++C++多维数组多维数组ELEMA[dELEMA[d11][d][d22]]……[[ddnn];];1212231111([,,,])([0,0,,0])[]([0,0,,0])[]nnnnnnnniknikilocAjjjlocAdjddjddjdjlocAdjdj−−==+=+⋅⋅⋅⋅+⋅⋅⋅++⋅+=+⋅+∑∏………………北京大学信息学院张铭编写©版权所有，转载或翻印必究Page13用数组表示特殊矩阵„三角矩阵：上三角、下三角„对称矩阵„对角矩阵„稀疏矩阵北京大学信息学院张铭编写©版权所有，转载或翻印必究Page14下三角矩阵图例„一维数组list[0..(n2+n)/2-1]„矩阵元素ai,j与线性表相应元素的对应位置为list[(i2+i)/2+j]（i=j）000750001090018062207北京大学信息学院张铭编写©版权所有，转载或翻印必究Page15对称矩阵„元素满足性质ai,j=aj,i，0=（i,j）n„例如无向图的相邻矩阵„存储其下三角的值，对称关系映射„存储于一维数组sa[0..n(n+1)/2-1]„sa[k]和矩阵元ai,j之间存在着一一对应的关系：⎪⎪⎩⎪⎪⎨⎧≥++++=jijiijiijjk当当,2)1(,2)1(315344000000006156⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦北京大学信息学院张铭编写©版权所有，转载或翻印必究Page16对角矩阵„对角矩阵是指所有的非零元素都集中在主对角线及以它为中心的其他对角线上。如果|i-j|1，那么数组元素a[i][j]=0。„下面是一个3对角矩阵：a0,0a1,1a0,1a1,0an-1,n-2an-1,n-1an-2,n-1a1,200………………北京大学信息学院张铭编写©版权所有，转载或翻印必究Page17稀疏矩阵„稀疏矩阵中的非零元素非常少，而且分布也不规律×⎛⎞⎜⎟⎜⎟⎜⎟−=⎜⎟⎜⎟⎜⎟⎜⎟⎜⎟⎝⎠6700070050150000000060170A0780002201100000000420000北京大学信息学院张铭编写©版权所有，转载或翻印必究Page18„稀疏因子„在m×n的矩阵中，有t个非零元素，则稀疏因子为:„当这个值小于0.05时，可以认为是稀疏矩阵„三元组(i,j,aij)：输入/输出常用„i是该元素的行号„j是该元素的列号„aij是该元素的值nmt×=δ北京大学信息学院张铭编写©版权所有，转载或翻印必究Page19稀疏矩阵的十字链表„十字链表有两组链表组成„行和列的指针序列„每个结点都包含两个指针：同一行的后继，同一列的后继030056200013115202列链表头指针行链表头指针126∧∧∧∧∧∧北京大学信息学院张铭编写©版权所有，转载或翻印必究Page20十字链表的建立„建立矩阵的算法如下：„首先为行头结点和列头结点申请空间，大小分别为矩阵的行列数„将三元组根据情况分别加入到链表中„如果三元组中的行列号错误，则退出，否则继续„先处理行链表的问题„如果该行头结点为空，则建立一个新的头结点，内容为该三元组„如果不为空则从头结点开始查找，找到该三元祖的正确位置如果该位置已经存在数据，则修改之，否则生成相应的结点插入进去„类似地处理列链表头013115202列链表头指针行链表头指针126∧∧∧∧∧∧北京大学信息学院张铭编写©版权所有，转载或翻印必究Page21经典矩阵乘法„A[c1..d1][c3..d3]，B[c3..d3][c2..d2],C[c1..d1][c2..d2]。„d3C＝A×B(Cij＝∑Aik·Bkj)k=c3„for(i=c1;i=d1;i++)for(j=c2;j=d2;j++){sum=0;for(k=c3;k=d3;k++)sum=sum+A[i,k]*B[k,j];C[i，j]=sum;}北京大学信息学院张铭编写©版权所有，转载或翻印必究Page22„p=d1-c1+1，m=d3-c3+1，n=d2-c2+1；„A为p×m的矩阵，B为m×n的矩阵，乘得的结果C为p×n的矩阵„经典矩阵乘法所需要的时间代价为O(p×m×n)北京大学信息学院张铭编写©版权所有，转载或翻印必究Page23稀疏矩阵乘法30050-1002000⎡⎣⎢⎤⎦⎥0210-2400⎡⎣⎢⎢⎤⎦⎥⎥×=01210102-2214∧∧∧∧∧06-1004⎡⎣⎢⎤⎦⎥6列链表头指针行链表头指针003035∧∧11-1022∧∧∧∧-14北京大学信息学院张铭编写©版权所有，转载或翻印必究Page24稀疏矩阵乘法时间代价„A为p×m的矩阵，B为m×n的矩阵，乘得的结果C为p×n的矩阵„若矩阵A中行向量的非零元素个数最多为ta„矩阵B中列向量的非零元素个数最多为tb„总执行时间降低为O((ta+tb)×p×n)„经典矩阵乘法所需要的时间代价为O(p×m×n)北京大学信息学院张铭编写©版权所有，转载或翻印必究Page25稀疏矩阵的应用„一元多项式iniinnnxaxaxaxaaxP∑==++++=02210)(北京大学信息学院张铭编写©版权所有，转载或翻印必究Page2611.2广义表„基本概念„广义表的各种类型„广义表的存储„广义表的周游算法北京大学信息学院张铭编写©版权所有，转载或翻印必究Page27基本概念„回顾线性表„由n（n≥0）个数据元素组成的有限有序序列„线性表的每个元素都具有相同的数据类型„如果一个线性表中还包括一个或者多个子表，那就称之为广义表（GeneralizedLists，也称Multi-list）一般记作：„L＝（x0，x1，…，xi，…，xn-1）北京大学信息学院张铭编写©版权所有，转载或翻印必究Page28L＝（x0，x1，…，xi，…，xn-1）„L是广义表的名称„n为长度„每个xi（0≤i≤n-1）是L的成员„可以是单个元素，即原子（atom)„也可以是一个广义表，即子表（sublist）„广义表的深度：表中元素都化解为原子后的括号层数北京大学信息学院张铭编写©版权所有，转载或翻印必究Page29广义表的各种类型„纯表（purelist）„从根结点到任何叶结点只有一条路径„也就是说任何一个元素（原子、子表）只能在广义表中出现一次(x1,(y1,(a1,a2),y3),x3,(z1,z2))x1y1a1a2y3z1z2x3北京大学信息学院张铭编写©版权所有，转载或翻印必究Page30广义表的各种类型（续）„可重入表„其元素(包括原子和子表)可能会在表中多次出现„如果没有回路图示对应于一个DAG„对子表和原子标号(L1:(a,b),(L1,c,L2:(d)),(L2,e,L3:(f,g)),L3)(((a,b)),((a,b),c,d),(d,e,f,g),(f,g))L1L2L3abdefgc特例：循环表（即递归表）北京大学信息学院张铭编写©版权所有，转载或翻印必究Page31广义表的各种类型（续）„循环表„包含回路„循环表的深度为无穷大(L1:(L2:(L1,a)),(L2,L3:(b)),(L3,c),L4:(d,L4))L1L2L3abcL4d北京大学信息学院张铭编写©版权所有，转载或翻印必究Page32北京大学信息学院张铭编写©版权所有，转载或翻印必究Page33„图⊇再入表⊇纯表(树)⊇线性表„广义表是线性与树形结构的推广„递归表是有回路的再入表„广义表应用„函数的调用关系„内存空间的引用关系„LISP语言北京大学信息学院张铭编写©版权所有，转载或翻印必究Page34广义表的存储„使用数组来存储„存储括号„可以使用链表结构存储(x1(y1(a1a2)y3)x3(z1z2))北京大学信息学院张铭编写©版权所有，转载或翻印必究Page35广义表存储ADTtemplateclassTclassGenListNode{public:inttype;//表示该结点是ATOM或者SubLISTTelement;//如果是ATOM，则存储它的值//如果是LIST,则指向它的元素的首结点GenListNodeT*child;GenListNodeT*next;//指向下一个结点…//其他函数};北京大学信息学