12-数据结构与算法-北京大学2008-张铭-高级数据结构

数据结构与算法第12章高级数据结构本章由张铭主写://张铭，王腾蛟，赵海燕高等教育出版社，2008.6。“十一五”国家级规划教材“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。第十二章高级数据结构12.1多维数组12.2广义表和存储管理12.3Trie结构和Patricia树12.4改进的二叉搜索树“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。12.1多维数组基本概念数组的空间结构数组的存储数组的声明用数组表示特殊矩阵稀疏矩阵“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。基本概念数组（Array）是数量和元素类型固定的有序序列静态数组必须在定义它的时候指定其大小和类型动态数组可以在程序运行才分配内存空间“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。基本概念（续）多维数组（Multi-array）是向量的扩充向量的向量就组成了多维数组可以表示为：ELEMA[c1..d1][c2..d2]…[cn..dn]ci和di是各维下标的下界和上界。所以其元素个数为：niiicd1)1(“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。C/C++、Pascal行优先先排最右的下标从右向左最后最左的下标例如对于三维数组a[1..k,1..m,1..n]的元素axyz可以如下排列：“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。Pascal语言的行优先存储a111a112a113…a11na121a122a123…a12n…………………………a1m1a1m2a1m3…a1mna211a212a213…a21na221a222a223…a22n…………………………a2m1a2m2a2m3…a2mn┇ak11ak12ak13…ak1nak21ak22ak23…ak2n…………………………akm1akm2akm3…akmn12m222222222222“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。FORTRAN列优先先排最左的下标从左向右最后最右的下标例如对于三维数组a[1..k,1..m,1..n]的元素axyz可以如下排列：“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。FORTRAN的列优先存储a111a211a311…ak11a121a221a321…ak21…………………………a1m1a2m1a3m1…akm1a112a212a312…ak12a122a222a322…ak22…………………………a1m2a2m2a3m2…akm2┇a11na21na31n…ak1na12na22na32n…ak2n…………………………a1mna2mna3mn…akmn123k12m222222222222“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。C++多维数组ELEMA[d1][d2]…[dn];1212231111([,,,])([0,0,,0])[]([0,0,,0])[]nnnnnnnniknikilocAjjjlocAdjddjddjdjlocAdjdj“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。用数组表示特殊矩阵三角矩阵：上三角、下三角对称矩阵对角矩阵稀疏矩阵“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。下三角矩阵图例一维数组list[0..(n2+n)/2-1]矩阵元素ai,j与线性表相应元素的对应位置为list[(i2+i)/2+j]（i=j）000750001090018062207“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。对称矩阵元素满足性质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“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。稀疏矩阵稀疏矩阵中的非零元素非常少，而且分布也不规律6700070050150000000060170A0780002201100000000420000“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。稀疏因子在m×n的矩阵中，有t个非零元素，则稀疏因子为:当这个值小于0.05时，可以认为是稀疏矩阵三元组(i,j,aij)：输入/输出常用i是该元素的行号j是该元素的列号aij是该元素的值nmt“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。稀疏矩阵的十字链表十字链表有两组链表组成行和列的指针序列每个结点都包含两个指针：同一行的后继，同一列的后继030056200013115202列链表头指针行链表头指针126∧∧∧∧∧∧“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。经典矩阵乘法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;}“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。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)“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。稀疏矩阵乘法30050-10020000210-2400=01210102-2214∧∧∧∧∧06-10046列链表头指针行链表头指针003035∧∧11-1022∧∧∧∧-14finish“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。稀疏矩阵乘法时间代价A为p×m的矩阵，B为m×n的矩阵，乘得的结果C为p×n的矩阵若矩阵A中行向量的非零元素个数最多为ta矩阵B中列向量的非零元素个数最多为tb总执行时间降低为O((ta+tb)×p×n)经典矩阵乘法所需要的时间代价为O(p×m×n)“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。12.2广义表和存储管理广义表储存管理“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。12.2.1广义表基本概念广义表的各种类型广义表的存储广义表的周游算法“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。基本概念回顾线性表由n（n≥0）个数据元素组成的有限有序序列线性表的每个元素都具有相同的数据类型如果一个线性表中还包括一个或者多个子表，那就称之为广义表（GeneralizedLists，也称Multi-list）一般记作：L＝（x0，x1，…，xi，…，xn-1）“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。L＝（x0，x1，…，xi，…，xn-1）L是广义表的名称n为长度每个xi（0≤i≤n-1）是L的成员可以是单个元素，即原子（atom)也可以是一个广义表，即子表（sublist）广义表的深度：表中元素都化解为原子后的括号层数“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。L＝（x0，x1，…，xi，…，xn-1）表头head=x0表尾tail=（x1，…，xn-1）规模更小的表有利于存储和实现“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。广义表的各种类型纯表（purelist）从根结点到任何叶结点只有一条路径也就是说任何一个元素（原子、子表）只能在广义表中出现一次(x1,(y1,(a1,a2),y3),x3,(z1,z2))x1y1a1a2y3z1z2x3“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。广义表的各种类型（续）可重入表其元素(包括原子和子表)可能会在表中多次出现如果没有回路图示对应于一个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特例：循环表（即递归表）“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。广义表的各种类型（续）循环表包含回路循环表的深度为无穷大(L1:(L2:(L1,a)),(L2,L3:(b)),(L3,c),L4:(d,L4))L1L2L3abcL4d“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。图再入表纯表(树)线性表广义表是线性与树形结构的推广递归表是有回路的再入表广义表应用函数的调用关系内存空间的引用关系LISP语言“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。广义表存储ADT（续）不带头结点的广义表链在删除结点的时候会出现问题删除结点data就必须进行链调整111∧data0headD10∧D20∧finishdata“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。-11-11∧data0head(ref=0)D10∧head(ref=1)1-1head(ref=2)D20∧广义表存储ADT（续）增加头指针，简化删除、插入操作重入表，尤其是循环表mark标志位——图的因素“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。带表头结点的循环广义表-11-111L1∧Lx1-1Lyc0∧11∧d0-1L41∧-1b0∧L3-11∧a0-11∧L2L1“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。12.2.2存储管理技术内存管理存在的问题可利用空间表存储的动态分配和回收伙伴系统失败处理策略和无用单元回收“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。动态内存分配new和delete内存管理技术链表、广义表“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008.6。分配与回收