北京大学：《数据结构与算法》课程教学资源（实验班讲义）第十一章 高级线性表

数据结构与算法 主要内容 中第十一章高级线性表 1.1多维数组 112广义表 任课教员:张铭 http://db.pku.edu.cn/mzhang/ds/ Q1.3存储管理技术 zhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 @版权所有,转载或翻印必究 够写 4111多维数组 基本概念 令基本概念 数组( Array)是数量和元素类型固定的 数组的空间结构 有序序列 数组的存储 静态数组必须在定义它的时候指定其 大小和类型 ○数组的声明 ■动态数组可以在程序运行才分配内存 令用数组表示特殊矩阵 ◇稀疏矩阵 北张■写 基本概念(续) 数组的空间结构 多维数组( Multi-aray)是向量的扩充 向量的向量就组成了多维数组 可以表示为: ELEM A[.d][c2., ,].[cn,.d,] c1和d是各维下标的下界和上界。所以其元 21 素个数为 二维数组 三维数组 (d1-c1+1) d1[1.3],d2[1..5],d3[1..5]分别为3个维

1 数据结构与算法 第十一章 高级线性表 任课教员：张 铭 http://db.pku.edu.cn/mzhang/DS/ mzhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 ©版权所有，转载或翻印必究 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 2 主要内容 „ 11.1 多维数组 „ 11.2 广义表 „ 11.3 存储管理技术 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 3 11.1 多维数组 „ 基本概念 „ 数组的空间结构 „ 数组的存储 „ 数组的声明 „ 用数组表示特殊矩阵 „ 稀疏矩阵 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 4 基本概念 „ 数组（Array）是数量和元素类型固定的 有序序列 „ 静态数组必须在定义它的时候指定其 大小和类型 „ 动态数组可以在程序运行才分配内存 空间 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 5 基本概念（续） „ 多维数组（Multi-array）是向量的扩充 „ 向量的向量就组成了多维数组 „ 可以表示为： ELEM A[c1..d1][c2..d2]…[cn..dn] „ ci和di是各维下标的下界和上界。所以其元 素个数为： ∏= − + n i i i d c 1 ( 1) 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 6 数组的空间结构 d1=3,d2=5,d3=5 d1 d2 a[2][2] d1 d2 d3 a[2][3][3] 二维数组 三维数组 d1[1..3],d2[1..5],d3[1..5]分别为3个维

数组的存储 ■内存是一维的,所以数组的存储也只能 C/C++、 Pascal行优先 是一维的 先排最右的下标 以行为主序(也称为“行优先”) ■从右向左 以列为主序(也称为“列优先”) 最后最左的下标 123 ■例如对于三维数组 456 a[1.k,1m1.n]的元素axy2可以 789 如下排列 写 够写 4Paa言的行优先存储 FORTRAN列优先 先排最左的下标 a1128213…an a218282 从左向右 最后最右的下标 ak11 a*12 8*13 ■例如对于三维数组a[1.k,1.m, 8121 ak22 823 1.n]的元素a可以如下排列: 北大息 北大啦孔写 叔新有命剑 FORTRAN的列优先存储 all a211 aa11 ■C++多维数组 ELEM A[d1][d2].[dn loc(A[1,12…,JnD)=lc(40,0,…,0] [1·d2……dn+j2·d3……dn 十, loc(400…,0)+d∑∏d+ =1k=i+1 北大学到

2 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 7 数组的存储 „ 内存是一维的，所以数组的存储也只能 是一维的 „ 以行为主序（也称为“行优先”） „ 以列为主序（也称为“列优先”） X= 1 2 3 4 5 6 7 8 9 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 8 „ C/C++、 Pascal行优先 „ 先排最右的下标 „ 从右向左 „ 最后最左的下标 „ 例如对于三维数组 a[1..k,1..m,1..n]的元素axyz可以 如下排列： 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 9 Pascal语言的行优先存储 a111 a112 a113 … a11n a121 a122 a123 … a12n ………………………… a1m1 a1m2 a1m3 … a1mn a211 a212 a213 … a21n a221 a222 a223 … a22n ………………………… a2m1 a2m2 a2m3 … a2mn ┇ ak11 ak12 ak13 … ak1n ak21 ak22 ak23 … ak2n ………………………… akm1 akm2 akm3 … akmn 12 3 n C 1 2 m 2 2 2 2 2 2 2 2 2 2 2 2 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 10 „ FORTRAN列优先 „ 先排最左的下标 „ 从左向右 „ 最后最右的下标 „ 例如对于三维数组a[1..k, 1..m, 1..n]的元素axyz可以如下排列： 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 11 FORTRAN的列优先存储 a111 a211 a311 … ak11 a121 a221 a321 … ak21 ………………………… a1m1 a2m1 a3m1 … akm1 a112 a212 a312 … ak12 a122 a222 a322 … ak22 ………………………… a1m2 a2m2 a3m2 … akm2 ┇ a11n a21n a31n … ak1n a12n a22n a32n … ak2n ………………………… a1mn a2mn a3mn … akmn 12 3 k C 1 2 m 2 2 2 2 2 2 2 2 2 2 2 2 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 12 „ C++多维数组ELEM A[d1][ d2]…[dn]; 1 2 12 23 1 1 1 1 ( [ , , , ]) ( [0,0, ,0]) [ ] ( [0,0, ,0]) [ ] n n n n nn n n i kn i k i loc A j j j loc A d jd d j d d jdj loc A d j d j − − = = + = +⋅ ⋅ ⋅ ⋅ + ⋅ ⋅ ⋅ ++ ⋅+ = +⋅ + ∑ ∏ … … … … … …

用数组表示特殊矩阵 下三角矩阵图例 三角矩阵:上三角、下三角 一维数组list[0.(n2+n)/2-1] 1+2:G> 应元素的对应位量为 ■对称矩阵 对角矩阵 ■稀疏矩阵 7090 0102 帖國写 03015 3040 对称矩阵 0406 对角矩阵 元素满足性质aa1,0(j)60 对角矩阵是指所有的非零元亲都集中在主对角 例如无向图的相邻矩阵 线及以它为中心的其他对角线上。如果 存储其下三角的值,对称关系映射 ij1,那么数组元素 aille=0。 ■存储于一维数组sa0.n(n+1)2-1 下面是一个3对角矩阵 sa和矩阵元之间存在着一一对应的关 f(+1) 北京大息啦_张铭写 权有。印乡究 北大啦孔写 叔新有命剑 稀疏矩阵 稀疏矩阵中的非零元素非常少,而且分布也不 ■稀疏因子 规律 0007005 雋为的矩阵中,有个非零元票,则稀疏 01500000 m xn 当这个值小于005时,可以认为是稀疏矩阵 三元组〔i,j,a1):输入/输出常用 078000220 1是该元素的行 j是该元素的列号 是该元素的值 00420 北大学到

3 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 13 用数组表示特殊矩阵 „ 三角矩阵：上三角、下三角 „ 对称矩阵 „ 对角矩阵 „ 稀疏矩阵 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 14 下三角矩阵图例 „ 一维数组list[0..(n2+n)/2-1] „ 矩阵元素ai,j与线性表相应元素的对应位置为 list[(i2+i)/2 + j]（i>=j） 0 0 0 7 5 0 0 0 1 0 9 0 0 1 8 0 6 2 2 0 7 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 15 对称矩阵 „ 元素满足性质ai,j=aj,i，01，那么数组元素a[i][j]=0。 „ 下面是一个3对角矩阵： a0,0 a1,1 a0,1 a1,0 an-1,n-2 an-1,n-1 an-2,n-1 a1,2 0 0 …… …… …… 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 17 稀疏矩阵 „ 稀疏矩阵中的非零元素非常少，而且分布也不 规律 × ⎛ ⎞ ⎜ ⎟ − = ⎝ ⎠ 6 7 0 0 0 7005 0 15 0 0 0 0 0 0 0 0 6 0 17 0 A 0 78 0 0 0 22 0 11 0 0 0 0 0 0 0 0 42 0 0 0 0 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 18 „ 稀疏因子 „ 在m ×n的矩阵中，有t个非零元素，则稀疏 因子为: „ 当这个值小于0.05时，可以认为是稀疏矩阵 „ 三元组(i, j, aij )：输入/输出常用 „ i是该元素的行号 „ j是该元素的列号 „ aij是该元素的值 m n t × δ =

稀硫矩阵的十字链表+字链表的建立 十字链表有两组链表组成 行和列的抛针序列 建立矩阵的算法如下:习 每个结点都包合两个指针:同一行的后繼,同一列的后繼 首先为行头结点和列头结点申请空间,大小分别为 列睡表买指针 矩阵的行列数 将三元组根据情况分别加入到链豪中 如果三元组中的行列号错误,则退出,否则继绘 030 行表头指 头结点为空,则建立一个新的头结点,内容 056 还如案位数息开维要挠魏波元智的廷 处理列链衰头 单息张帖篇写 经典矩阵乘法 [c1..d1][c3.d3],B[c3..d3][ c[c1..d1][c2.d2]。 p=d1-c1+1,m=d3-c3+1, n=d2c2+1; C=AXB (C1=EAlk Bx] ■A为p×m的矩阵,B为mxn的矩 for (i=cl: i<d1: 1++) 阵,乘得的结果C为p×n的矩阵 for(j=c2;j<=2;j++) 经典矩阵乘法所需要的时间代价为 for (k=c3: k<=d3 k+ o(pXmXn cli, sum+ ali, k]*Bkk, j]: 北京大息 权有。印乡究 北大啦孔写 叔新有命剑 稀疏矩阵乘法 稀疏矩阵乘法时间代价 05 ■A为p×m的矩阵,B为m×n的矩阵, 乘得的结果C为p×n的矩阵 若矩阵A中行向量的非零元素个数最多为 ■矩阵B中列向量的非零元素个数最多为t 总执行时间降低为o(t+tb)Xp×n) B ■经典矩阵乘法所需要的时间代价为 o(pXm×n) 大息驰 北大学到

4 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 19 稀疏矩阵的十字链表 „ 十字链表有两组链表组成 „ 行和列的指针序列 „ 每个结点都包含两个指针：同一行的后继，同一列的后继 0 3 0 0 5 6 2 0 0 0 1 3 1 1 5 2 0 2 列链表头指针 行 链 表 头 指 针 1 2 6 ∧ ∧ ∧ ∧ ∧ ∧ 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 20 十字链表的建立 „ 建立矩阵的算法如下： „ 首先为行头结点和列头结点申请空间，大小分别为 矩阵的行列数 „ 将三元组根据情况分别加入到链表中 „ 如果三元组中的行列号错误，则退出，否则继续 „ 先处理行链表的问题 „ 如果该行头结点为空，则建立一个新的头结点，内容 为该三元组 „ 如果不为空则从头结点开始查找，找到该三元祖的正 确位置如果该位置已经存在数据，则修改之，否则生 成相应的结点插入进去 „ 类似地处理列链表头 0 1 3 1 1 5 2 0 2 列链表头指针 行 链 表 头 指 针 1 2 6 ∧ ∧ ∧ ∧ ∧ ∧ 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 21 经典矩阵乘法 „ A[c1..d1][ c3..d3]，B[c3..d3][ c2..d2], C[c1..d1][c2..d2]。 „ d3 C＝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; } 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 22 „ 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) 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 23 稀疏矩阵乘法 3 0 0 5 0 -1 0 0 2 0 0 0 ⎡ ⎣ ⎢ ⎤ ⎦ ⎥ 0 2 1 0 -2 4 0 0 ⎡ ⎣ ⎢ ⎢ ⎤ ⎦ ⎥ ⎥ × = 0 1 2 1 0 1 0 2 -2 2 1 4 ∧ ∧ ∧ ∧ ∧ 0 6 -1 0 0 4 ⎡ ⎣ ⎢ ⎤ ⎦ ⎥ 6 列链表头指针 行 链 表 头 指 针 0 0 3 0 3 5 ∧ ∧ 1 1 -1 0 2 2 ∧ ∧ ∧ ∧ -1 4 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 24 稀疏矩阵乘法时间代价 „ A为p×m的矩阵，B为m×n的矩阵， 乘得的结果C为p×n的矩阵 „ 若矩阵A中行向量的非零元素个数最多为 ta „ 矩阵B中列向量的非零元素个数最多为tb „ 总执行时间降低为O((ta+tb)×p×n) „ 经典矩阵乘法所需要的时间代价为 O(p×m×n)

4稀疏矩阵的应用12广义表 一元多项式 基本概念 P(x)=a,+a-r+a,x +.+a,x 广义表的各种类型 广义表的存储 广义表的周游算法 rawvegree 帖國写 基本概念 回顾线性表 ..,X: ■由n(n≥0)个数据元素组成的有限有序序列 L是广义表的名称 线性表的每个元素都具有相同的数据类型 n为长度 如果一个线性表中还包括一个或者多个子 每个x.(0≤i≤n1)是L的成员 表,那就称之为广 Lists,也称 Multi-list)一般记作: 可以是单个元素,即原子(atom) ■也可以是一个广义表,即子表( sublist) 广义表的深度:表中元素都化解为原子 后的括号层数 北京大息啦_张铭写 权有。印乡究 北大啦孔写 叔新有命剑 广义表的各种类型 广义表的各种类型(续) 纯表( pure list) 可重入表特例:循环表(即递归表 从根结点到任何叶结点只有一条路径 也就是说任何一个元素(原子、子豪)只能在广义 霜 (a,b),(a,b),cd),(d,e,f,g),(f,g) 豪中出现 次 (xl, (yl, (al a2 ) y3), x3, (z1, z2)) 和原 (Ll:(a,b),Ll,c,JL2:(d),(L2,e,L3:(,g)),L3) 北大学到第■写 5

5 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 25 稀疏矩阵的应用 „ 一元多项式 i n i i n n n a x P x a a x a x a x ∑= = = + + + + 0 2 0 1 2 ( ) " 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 26 11.2 广义表 „ 基本概念 „ 广义表的各种类型 „ 广义表的存储 „ 广义表的周游算法 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 27 基本概念 „ 回顾线性表 „ 由n（n≥0）个数据元素组成的有限有序序列 „ 线性表的每个元素都具有相同的数据类型 „ 如果一个线性表中还包括一个或者多个子 表，那就称之为广义表（Generalized Lists，也称Multi-list）一般记作： „ L＝（x0，x1，…，xi ，…，xn-1） 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 28 L＝（x0，x1，…，xi ，…，xn-1） „ L是广义表的名称 „ n为长度 „ 每个xi （0≤i≤n-1）是L的成员 „ 可以是单个元素，即原子（atom ) „ 也可以是一个广义表，即子表（sublist） „ 广义表的深度：表中元素都化解为原子 后的括号层数 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 29 广义表的各种类型 „ 纯表（pure list） „ 从根结点到任何叶结点只有一条路径 „ 也就是说任何一个元素（原子、子表）只能在广义 表中出现一次 (x1, (y1 ,(a1 ,a2 ), y3), x3 ,(z1 ,z2)) x1 y1 a1 a2 y3 z1 z2 x3 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 30 广义表的各种类型（续） „ 可重入表 „ 其元素(包括 原子和子表) 可能会在表 中多次出现 „ 如果没有回 路图示对应 于一个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)) L1 L2 L3 a b d e f g c 特例：循环表（即递归表）

广义表的各种类型(续)g 循环表 线性表 包含回路 循环表的深度为无旁大 纯表 (L:(L2:(Ll,a),(L2,L3(b),(L3,c),L4:d,L4) 再入表 单息张帖篇写 斗广义表的存储 图→再入表→纯表(树)线性表 使用数组来存储 广义表是线性与树形结构的推广 递归表是有回路的再入表 口x1yaas3saab 义表应用 函数的调用关系 内存空间的引用关系 可以使用链表结构存储 LISP语言 北京大息啦_张铭写 权有。印乡究 北大啦孔写 叔新有命剑 广义表存储ADT 广义表存储ADT(续 template ■不带表头的广义表链 在删除结点的时候会出现问题 int type;/表示该姑点是AToM取者 SublIST 删除结点data就必须进行链调整 T element://如果是AToM,则存储它的值 /如果是LIsT,则指向它的元囊的首蜡点 GenListNode*child; Gen ListNodenext//指向下一个站点 其他函

6 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 31 广义表的各种类型（续） „ 循环表 „ 包含回路 „ 循环表的深度为无穷大 (L1:(L2:(L1, a)), (L2, L3:(b)), (L3, c), L4:(d,L4)) L1 L2 L3 a b c L4 d 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 32 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 33 „ 图⊇再入表⊇纯表(树)⊇线性表 „ 广义表是线性与树形结构的推广 „ 递归表是有回路的再入表 „ 广义表应用 „ 函数的调用关系 „ 内存空间的引用关系 „ LISP语言 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 34 广义表的存储 „ 使用数组来存储 „ 存储括号 „ 可以使用链表结构存储 ( x1 ( y1 ( a1 a2 ) y3 ) x3 ( z1 z2 ) ) 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 35 广义表存储ADT template class GenListNode { public: int type; //表示该结点是ATOM或者SubLIST T element; //如果是ATOM，则存储它的值 //如果是LIST ,则指向它的元素的首结点 GenListNode *child; GenListNode *next;//指向下一个结点 … // 其他函数 }; 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 36 广义表存储ADT（续） „ 不带表头的广义表链 „ 在删除结点的时候会出现问题 „ 删除结点data就必须进行链调整 1 1 1 ∧ 0 data head 0 D1 ∧ 0 D2 ∧

广义表存储ADT(续) 带表头结点的循环广义表 head(ref-0) 口中陘中F D 重入表,尤其是循环表 标志位一图的因章 中因 单息张帖篇写 能够存储多种数舞类型 攻进的广义衰第点类烈 lass Gen List pu int type/示该的点是 ATOM or LIST enListNodehea山//头鰭点存头僧 GenListNode* current//当前指针的 ref;J/如果是衰头增点则,存情该点教引用次歌 int mark/本于囊是否被悄同过 y hea element/如最是AToM,则存它的值 void Insert(T element;//在尾邮加入一个元蜻点 n计0>c!入一个子表 点的下一个 GenListNode* GetPrevO;/取当前结点的前一个 void viewList(;/周 北京大息啦_张铭写 权有。印乡究 北大盒驰张着写 叔新有命剑 GenList和ist1 GenList(Ll enL ist *uist? anew Genuistcchar">12 广义表的周游算法 st3->Insert b); 广义表周游的时候应该注意几个问题 相当于深度优先周游 访问的时候首先进入一个子表的头结点,设量 按照本层子结点顺序,访问广义衰 如果是子表结点,则备递归地访向此子变表头晴点 List->-ViewListO; (Ll:(L2:(,Lla),(L2,L3(b),(L3,c),L4:(d,4) 避免进入循环链中无法跳 实际上,表头面设置的访问位 广义表访问结束的时候 应该将mark设置为未访问 大等如果其伸地方也引用了该饶可以正常的访向到

7 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 37 -1 1 -1 1 ∧ 0 data head(ref=0) head(ref=1) 1 0 D1 ∧ -1 head(ref=2) 0 D2 ∧ 广义表存储ADT（续） „ 增加头指针，简化删除、插入操作 „ 重入表，尤其是循环表 „ mark标志位——图的因素 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 38 带表头结点的循环广义表 -1 1 -1 1 1 L 1 ∧ Lx 1 -1 Ly 0 c ∧ 1 1 ∧ L4 -1 0 d 1 ∧ -1 0 b ∧ L3 -1 0 a 1 ∧ -1 1 ∧ L2 L1 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 39 //改进的广义表结点类型 template class GenListNode { public: int type; //表示该结点是ATOM or LIST struct { int ref; //如果是表头结点则，存储该结点被引用次数 char* Name; // 表头名称 int mark; //本子表是否被访问过 } headNode; GenListNode *child;//如果是LIST ,则指向子表 T element; //如果是ATOM，则存储它的值 GenListNode *next;//指向下一个结点 void GenListTraversal ();//周游该结点的子孙 void GenListTraversalHelp(GenListNode *node); ...... }; 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 40 //GenList是一个原子元素类型为T的广义表 //如果要实现能够存储多种数据类型的广义 //表，只需要嵌套的使用它 template class GenList { private: GenListNode *head;//头结点,存储头信息 GenListNode *current;//当前指针的位置 public: GenList(char *Name); ~GenList(); void Insert(T element);//在尾部加入一个元素结点 void Insert(GenList *gl);//在尾部插入一个子表 GenListNode *GetHead();//取头结点 GenListNode *GetNext();//取当前结点的下一个 GenListNode *GetPrev();//取当前结点的前一个 void MoveFirst();//当前指针指向head int Remove();//删除当前结点 void ViewList();//周游广义表 }; 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 41 GenList *List=new GenList("List"); GenList *List1=new GenList("L1"); GenList *List2=new GenList("L2"); GenList *List3=new GenList("L3"); GenList *List4=new GenList("L4"); GenList *Listx=new GenList(""); GenList *Listy=new GenList(""); List3->Insert("b"); List4->Insert("d"); List4->Insert(List4); Listy->Insert(List3); Listy->Insert("c"); List2->Insert("a"); List2->Insert(List1); List1->Insert(List2); Listx->Insert(List2); Listx->Insert(List3); List->Insert(List1); List->Insert(Listx); List->Insert(Listy); List->Insert(List4); List->ViewList(); (L1:(L2:(, L1 a)), (L2, L3:(b)), (L3, c), L4:(d,L4)) L1 L2 L3 a b c L4 d 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 42 广义表的周游算法 „ 广义表周游的时候应该注意几个问题： „ 相当于深度优先周游 „ 访问的时候首先进入一个子表的头结点，设置 mark标记 „ 按照本层子结点顺序，访问广义表 „ 如果是子表结点，则准备递归地访问此子表表头结点 „ 如果是原子，则直接访问 „ 避免进入循环链中无法跳出 „ mark用来防止循环访问而设置的访问位 „ 实际上，表头结点才需要mark „ 广义表访问结束的时候 „ 应该将mark设置为未访问 „ 如果其他地方也引用了该链可以正常的访问到

void GenListNode: GenListTraversalHelp(GenListNode adNode. mark= VISITED; for(p node NULL; P: H(六个表1准图边同白的处亮 GenList: ViewListo rsto: eadNode. mark = UNVISITED)( current->GenListTraversal o GenListTraversalHelp(p->child) template } void GenListNode: GenListTraversal o it te if next pullo& P- next- bpel EAD D) GenListTraversalHelp(this); ut<<"y"; 中强写 113存储管理技术 内存管理存在的问题 m动态内存分配 Q可利用空间表 ■neW 和 delete 存储的动态分配和回收 ■内存管理技术 伙伴系统 链表、广义表 失败处理策略和无用单元回收 北京大息啦_张铭写 权有。印乡究 北大啦孔写 叔新有命剑 虚拟存储:内存溢出的管理 斗分配与回收 虚拟地址空间 物理内存地址 内存管理最基本的问题 4k-8k 分配存储空间 回收被“释放”的存储空间 16k-20k 片问 存储的压缩 无用单元收集 无用单元:可以回收而没有回收的空间 内存泄漏( memory leak 程序员忘记 delete已经不再使用的指针 溢出发生后,把内存中某些数据暂存到外存 选择最近不使用的那些结点

8 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 43 template void GenListNode::GenListTraversalHelp(GenListNode *node) { GenListNode *p; node->headNode.mark=VISITED; cout next; p!=NULL; p=p->next) { //进入一个子表结点，准备递归访问它的表头结点 if ((p->type==LIST)&&(p->child!=NULL)) { cout child->headNode.Name; if (p->child->headNode.mark == UNVISITED) { if (p->child->headNode.Name[0]!='\0') cout child); } } else if (p->type==ATOM) coutelement; if ((p->next!=NULL)) // &&(p->next->type!=HEAD)) cout void GenList::ViewList() { MoveToFirst(); current->GenListTraversal (); } template void GenListNode::GenListTraversal () { GenListTraversalHelp(this); } 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 45 11.3 存储管理技术 „ 内存管理存在的问题 „ 可利用空间表 „ 存储的动态分配和回收 „ 伙伴系统 „ 失败处理策略和无用单元回收 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 46 „ 动态内存分配 „ new和delete „ 内存管理技术 „ 链表、广义表 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 47 分配与回收 „ 内存管理最基本的问题 „ 分配存储空间 „ 回收被“释放”的存储空间 „ 碎片问题 „ 存储的压缩 „ 无用单元收集 „ 无用单元：可以回收而没有回收的空间 „ 内存泄漏( memory leak ) „ 程序员忘记delete已经不再使用的指针 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 48 虚拟存储：内存溢出的管理 „ 溢出发生后，把内存中某些数据暂存到外存 „ 选择最近不使用的那些结点 0-4k 4k-8k 8k-12k 12k-16k 16k-20k 0-4k 4k-8k 8k-12k 12k-16k 16k-20k 20k-24k 24k-28k 28k-32k 32k-36k 36k-40k 虚拟地址空间 物理内存地址 1 3 0 4 2

可利用空间表 ava ■把存储器看成一组变长块数组 些块是已分配的 链接空闲块,形成可利用空间表 freelist 存储分配和回收 a new p从可利用空间分配 delete p把p指向的数据块返回可利用空间 表 2)氯能适行一段对闻 1)初地状态的可利用型同表 ■空间不够,则求助于失败策略 点等长的可利用空间变 帖國写 4可利用空间表的函数重载4 template class LinkNodel ∥载new运算符实现 private: template static LinkNode* avail;川可利用空间表头指针 void* Link Node:: operator new(size t)i public: avl-NULL)/可利用空间表为空 Elem value;∥结点值 return: new LinkNode;/利用系统的new分配空间 LinkNode*next;∥指向下一结点的指针 LinkNodecElem> 否则从可利用 空间表中取走一个结点 NULL);∥造函数 availe avail->next t;/载new运算符 return temp; →p)/载 delete运算符 北京大息啦_张铭写 权有。印乡究 北大啦孔写 叔新有命剑 载 delete运算符实现 可利用空间表:单链表栈 gnew即栈的删除操作 void LinkNode:: operator delete(void* p)i delete即栈的插入操作 ((LinkNode*)p)->next=avail; avail=(LinkNode*) 襄用系统的p7和1:作 ■例如,程序运行完毕时,把avai1所占用的 空间都交还给系统(真正释放空间) 北大学到

9 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 49 可利用空间表 „ 把存储器看成一组变长块数组 „ 一些块是已分配的 „ 链接空闲块，形成可利用空间表(freelist) „ 存储分配和回收 „ new p 从可利用空间分配 „ delete p 把p指向的数据块返回可利用空间 表 „ 空间不够，则求助于失败策略 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 50 avail avail （1）初始状态的可利用空间表 （2）系统运行一段时间后 的可利用空间表 结点等长的可利用空间表 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 51 可利用空间表的函数重载 template class LinkNode{ private: static LinkNode *avail; //可利用空间表头指针 public: Elem value; //结点值 LinkNode * next; //指向下一结点的指针 LinkNode(const Elem & val, LinkNode * p); LinkNode(LinkNode * p = NULL);//构造函数 void * operator new(size_t);//重载new运算符 void operator delete(void * p);//重载delete运算符 }; 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 52 //重载new运算符实现 template void * LinkNode::operator new(size_t){ if(avail == NULL) //可利用空间表为空 return ::new LinkNode;//利用系统的new分配空间 LinkNode * temp = avail; //否则从可利用 空间表中取走一个结点 avail = avail->next; return temp; } 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 53 //重载delete运算符实现 template void LinkNode::operator delete(void * p){ ((LinkNode *) p)->next = avail; avail = (LinkNode *)p; } 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 54 „ 可利用空间表：单链表栈 „ new即栈的删除操作 „ delete即栈的插入操作 „ 直接引用系统的new和delete操作符，需 要强制用“::new p”和“::delete p” „ 例如，程序运行完毕时，把avail所占用的 空间都交还给系统（真正释放空间）

存储的动态分配和回收 pmax值已经 变常可利用块 达到或超过S 分配 值,则不能再 动态存儲区 ■找到其长度大于等于申请长度的结点 分配空间 ■从中截取合适的长度 回收 考虑刚刚被删除的结点空间能否与邻接合并 存区 以便能满足后来的较大长度结点的分配请求 帖國写 空闲块的数据结构 碎片问题 内部碎片:多于请求字节数的空间 外部碎片:小空闲块 (a)空闲块的结构 b)已分配块的结构 北京大息啦_张铭写 权有。印乡究 北大啦孔写 叔新有命剑 顺序适配 (sequential fit) 顺序适配(2) 空闲块分配方法 问题:三个块1200,1000,3000 常见的顺序适配方法 请求序列:600,500,900,2200 ■首先适配( (first fit) 首先适配: 3000 最佳适配( best fit) 最差适配( worst fit 600|500100900|1 2200 800 10

10 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 55 „ pmax值已经 达到或超过S 值，则不能再 分配空间 可利用 avail2 单链表 head2 可利用 avai11 单链表 head1 L 静态区 后备 存储区 info 单链表 1 的结点 link 单链表 2 的结点 info link 静态区 pmax S 动态存储区 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 56 存储的动态分配和回收 „ 变常可利用块 „ 分配 „ 找到其长度大于等于申请长度的结点 „ 从中截取合适的长度 „ 回收 „ 考虑刚刚被删除的结点空间能否与邻接合并 „ 以便能满足后来的较大长度结点的分配请求 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 57 空闲块的数据结构 块长度 标记位 标记位 指针 标记位 块长度 块长 标记位 度 + k k + - k - （a）空闲块的结构 （b）已分配块的结构 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 58 碎片问题 „ 内部碎片：多于请求字节数的空间 „ 外部碎片：小空闲块 外部碎片 内部碎片 外部碎片和内部碎片 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 59 顺序适配(sequential fit) „ 空闲块分配方法 „ 常见的顺序适配方法： „ 首先适配(first fit) „ 最佳适配(best fit) „ 最差适配(worst fit) 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 60 顺序适配（2） „ 问题: 三个块 1200，1000，3000 请求序列：600，500，900，2200 „ 首先适配： 1200 1000 3000 600 500600100 900 100 2200 800