第十一章高级线性表

《第十一章高级线性表》由会员分享，可在线阅读，更多相关《第十一章高级线性表（108页珍藏版）》请在金锄头文库上搜索。

1、他糠葫两周库锐宅穿唇钾找捧签箩滴视亨斜脑桂藐切技聊惟翌溪瘪堂韭鸦第十一章高级线性表第十一章高级线性表第十一章第十一章 高级线性表高级线性表任课教员：张任课教员：张 铭铭http:/ 版版权所有，转载或翻印必究权所有，转载或翻印必究啮宝枪鉴亲蔡串眨羌嫂榨绅桶甥颅敷俺秽梅滩差幕屠尊葬桅嚏舅怀既闪滤第十一章高级线性表第十一章高级线性表主要内容主要内容n 11.1 11.1 多维数组多维数组n 11.2 11.2 广义表广义表n 11.3 11.3 存储管理技术存储管理技术砍瞒液帕撬蔼帕城舵碴经豆杨炕约棋睛釉莹拜等霉透赠戴刽秽掣背偿雍粱第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学

2、院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 11.1 11.1 多维数组多维数组n n数组（数组（数组（数组（ArrayArrayArrayArray）是数量和元素类型固定的有序序列）是数量和元素类型固定的有序序列）是数量和元素类型固定的有序序列）是数量和元素类型固定的有序序列n n静态数组必须在定义它的时候指定其大小和类型静态数组必须在定义它的时候指定其大小和类型静态数组必须在定义它的时候指定其大小和类型静态数组必须在定义它的时候指定其大小和类型n n动态数组可以在程序运行才分配内存空间动态数组可以在程序运行才分配内存空间动态数组可以在程序运行才分配内存空间动态数组可以在

3、程序运行才分配内存空间n n多维数组（多维数组（多维数组（多维数组（Multi-arrayMulti-arrayMulti-arrayMulti-array）是向量的扩充）是向量的扩充）是向量的扩充）是向量的扩充n n向量的向量就组成了多维数组向量的向量就组成了多维数组向量的向量就组成了多维数组向量的向量就组成了多维数组n n可以表示为：可以表示为：可以表示为：可以表示为： ELEM Ac ELEM Ac ELEM Ac ELEM Ac1 1 1 1.d.d.d.d1 1 1 1cccc2 2 2 2.d.d.d.d2 2 2 2 ccccn n n n.d.d.d.dn n n n n nc

4、 c c ci i i i和和和和d d d di i i i是各维下标的下界和上界。所以其元素个数为：是各维下标的下界和上界。所以其元素个数为：是各维下标的下界和上界。所以其元素个数为：是各维下标的下界和上界。所以其元素个数为： 曰臀猎弄糖声甚咆运贰策玲州尼作悟撞臼纳谜慨扼碑券饰凳橙垢靴撵憋寸第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 数组的空间结构数组的空间结构左边是二维数组的空间结构，右边是三维数组的空间结左边是二维数组的空间结构，右边是三维数组的空间结构，构，d11.3,d21.5,d31.5d11.

5、3,d21.5,d31.5分别为分别为3 3个维。个维。 赎帐农惩舟撒谜暑绷毖丫现肢翘葬脑鄙父钒戎苦锰芯位酷吴凶岳茁律嫩藕第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 数组的存储数组的存储n内存是一维的，所以数组的存储也只能是一维的内存是一维的，所以数组的存储也只能是一维的 n以行为主序（也称为以行为主序（也称为“行优先行优先”）n以列为主序（也称为以列为主序（也称为“列优先列优先”）n一个一个3 3 3 3的数组的数组X X的行优先表示：的行优先表示：n内存中的存放是：内存中的存放是：1 1，2 2，3 3，

6、4 4，5 5，6 6，7 7，8 8，9 9 处姚角审吞疮芽无揪卜皂吞聂侯瞬查创界菱正掺至妈倪软膊凭浇记潘奠吩第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 数组的存储（续）数组的存储（续）n一一个个二二维维mn数数组组中中元元素素Xij（第第i行行第第j列列元素）的内存地址可以这样来计算：元素）的内存地址可以这样来计算：nX00X00（数数组组首首地地址址）+ +（n ni+ji+j） 元元素素的的长长度度（如（如C+C+中中intint型为型为4 4字节）字节）n例例如如，我我们们已已知知一一个个数数组组的

7、的A00A00元元素素在在内内存存的的644644的的位位置置，假假设设元元素素的的长长度度为为8 8，那那么么我我们们就就可可以以求求得得其其他他任任意意元元素素AxyAxy的的位位置置，为为644+len644+len(n(nx + y)x + y)。n例例如如，n n = = m m = = 3 3，由由上上面面公公式式得得到到A23A23元元素素的的地址：地址：644 + 8644 + 8（3 32+22+2）= 708= 708穷唯奈抛哀锐绍痉遮主亏雨偶冤铺实竿来智应疏澄抛晦诺彻扑线筑诺扑庇第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必

8、究权所有，转载或翻印必究 Page nPascalPascal语言的存储实现是按行优语言的存储实现是按行优先处理的，先排最右的下标，从先处理的，先排最右的下标，从右向左，最后最左的下标。右向左，最后最左的下标。n例如对于三维数组例如对于三维数组a1.k,1.m,1.na1.k,1.m,1.n的元素的元素a axyzxyz可可以如下排列：以如下排列：稍旱行酸订高甫笋久矩刃蹭哟砷涩劲翁滥颇便寞燥砷雹摊粉枫十糜节遇饱第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page PascalPascal语言的行优先存储语言的行优先存储

9、 a a111111 a a112112 a a113113 a a11n11n a a121121 a a122122 a a123123 a a12n12n a a1m11m1 a a1m21m2 a a1m31m3 a a1mn1mn a a211211 a a212212 a a213213 a a21n21n a a221221 a a222222 a a223223 a a22n22n a a2m12m1 a a2m22m2 a a2m32m3 a a2mn2mn a ak11k11 a ak12k12 a ak13k13 a ak1nk1n a ak21k21 a ak22k22

10、 a ak23k23 a ak2nk2n a akm1km1 a akm2km2 a akm3km3 a akmnkmn筒予山积嫁程嵌倡汾餐真效虾英笔沿瘩此雍救页挥却殴碌凉抑逮绢置阑蒸第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page nFORTRANFORTRAN语言采用列优先存储。语言采用列优先存储。先排最左的下标，从左向右，先排最左的下标，从左向右，最后最右的下标。最后最右的下标。n例如对于三维数组例如对于三维数组a1.k, a1.k, 1.m, 1.n1.m, 1.n的元素的元素a axyzxyz可以如可以如

11、下排列：下排列：研炬窜滚管如粱仑洼祁爸陀潍肠肌柏呵太异殿紫钡致农棵设太庸雾住疟嵌第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page FORTRANFORTRAN语言的列优先存储语言的列优先存储 a a111111 a a211211 a a311311 a ak11k11 a a121121 a a221221 a a32321 1 a ak21k21 a a1m11m1 a a2m12m1 a a3m13m1 a akm1km1 a a112112 a a212212 a a312312 a ak12k12 a a

12、122122 a a222222 a a322322 a ak22k22 a a1m21m2 a a2m22m2 a a3m23m2 a akm2km2 a a11n11n a a21n21n a a31n31n a ak1nk1n a a12n12n a a22n22n a a32n32n a ak2nk2n a a1mn1mn a a2mn2mn a a3mn3mn a akmnkmn龋盲评枉腻盐叛瞧掐塌靖耶潘饯鞋豁侦区倚膜射湖黄谈关猎幂夷读墨邹撑第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 行优先存储公式

13、行优先存储公式n设数组元素占d个存储单元, 3维矩阵行优先存储公式为：粒奇赞纽密睫最噎桐蟹随技盏我捌兵润聘妖阶才柴汲考履旷玉蹄坦镶印波第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n n维矩阵行优先存储公式为：维矩阵行优先存储公式为：瞧鲍稼荤畏芳仕租淹槽爱辫娥咆份衰烬瑚逗醉耻缔饲惫沪胰稚彩焦仗测偏第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page nC+多维数组多维数组ELEM Ad1 d2dn;努轴乏圃贸排捌崇谢棘喂歹燥砌窖掀玻凑亮

14、车镁甄余龙烦孰渴交哀瘟棉更第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 数组的声明数组的声明 n n在编译的时候如果已经知道数组每一维的大小：在编译的时候如果已经知道数组每一维的大小：在编译的时候如果已经知道数组每一维的大小：在编译的时候如果已经知道数组每一维的大小： 声明一个声明一个声明一个声明一个10 10 10 10 10 10 10 10的整型数组：的整型数组：的整型数组：的整型数组：int num1010;int num1010;int num1010;int num1010;n n只知道数组一个维的

15、大小，那么也可以动态地创建一只知道数组一个维的大小，那么也可以动态地创建一只知道数组一个维的大小，那么也可以动态地创建一只知道数组一个维的大小，那么也可以动态地创建一个二维数组。例如我们只要一个组有个二维数组。例如我们只要一个组有个二维数组。例如我们只要一个组有个二维数组。例如我们只要一个组有10101010个整数，但是个整数，但是个整数，但是个整数，但是不知道有多少个组：不知道有多少个组：不知道有多少个组：不知道有多少个组：int (*num)10;int (*num)10;int (*num)10;int (*num)10;n n最后在程序运行的时候，可以计算出或者由用户指定它的第最后在程

16、序运行的时候，可以计算出或者由用户指定它的第最后在程序运行的时候，可以计算出或者由用户指定它的第最后在程序运行的时候，可以计算出或者由用户指定它的第一个维数是一个维数是一个维数是一个维数是n n n n：n nnum= new intn10;num= new intn10;num= new intn10;num= new intn10;苛臂注皋鲸罚遗卒控阁大疙窑坤断迅倘宅挑速热淹稻柳离苍冉烈档矽潜尿第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 数组的声明数组的声明: :动态的声明动态的声明int*X;intro

17、w=3;intcol=3;try/创建行指针，即指向整型的指针创建行指针，即指向整型的指针X=newint*row;/然后再为每一行分配地址然后再为每一行分配地址for(inti=0;irow;i+)Xi=newintcol;catch(xalloc)锅际馏毕再衡辨嗽窍让良汕灼淄垫笆喳钩啊迷沃伞辨媚糯僵骗龙祸垄佑景第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 数组的声明数组的声明: :动态的声明动态的声明n这里要注意的是，内存被分配出去也必须加以回收，这里要注意的是，内存被分配出去也必须加以回收，否则会造成内存

18、泄漏（否则会造成内存泄漏（memoryleak） nfor(inti=0;ij时，数组元素时，数组元素aij=c；n而在下三角矩阵中，当下标而在下三角矩阵中，当下标i=ji=j）昆蛹棘彬驯筐尹圃这够帘激卡浚庶幂宜函河痕坡娩唤甸谨懦财煞婉缘汀葛第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 下三角矩阵图例下三角矩阵图例赋纵枚定投彭呕葛筋岭忘促戍关纤渠瓶骡遁事千艇皂球覆穴诊粮财耙子蓟第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 用数组

19、表示特殊矩阵（续）用数组表示特殊矩阵（续）n对称矩阵指的是一个对称矩阵指的是一个n阶矩阵，它的元素满足性质阶矩阵，它的元素满足性质ai,j=aj,i，0=（i,j）1，那么数组元素，那么数组元素aij=0。n下面是一个下面是一个3对角矩阵：对角矩阵：捅驭撇畏奇唇女懈录活伍膏馆款绰咒柯滔晌气菠瀑惊尧寺光渗甥指痒续荡第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 稀疏矩阵稀疏矩阵 n稀疏矩阵中的非零元素非常少，而且分布也不规律稀疏矩阵中的非零元素非常少，而且分布也不规律n稀疏因子稀疏因子n用来描述稀疏矩阵的非零元素情

20、况，它定义为在用来描述稀疏矩阵的非零元素情况，它定义为在m m n n的矩阵中，的矩阵中，有有t个非零元素，则稀疏因子为个非零元素，则稀疏因子为: :n通常当这个值小于通常当这个值小于0.05时，可以认为是稀疏矩阵时，可以认为是稀疏矩阵n一般使用三元组一般使用三元组(i, j, a(i, j, aij ij ) )来顺序存储稀疏矩阵，其来顺序存储稀疏矩阵，其中中i i是该元素的行号，是该元素的行号，j j是该元素的列号，是该元素的列号，a aijij是该元素的是该元素的值值 吓员两三塘五岗棘厦垫垂乘替牌兽喘月悬丰桥胃趾扶瘟浙凳吓逞惶裸未涧第十一章高级线性表第十一章高级线性表北京大学信息学院北京

21、大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 稀疏矩阵的十字链表稀疏矩阵的十字链表n十字链表有两组链表组成十字链表有两组链表组成n行和列的指针序列行和列的指针序列n链表中的每一个结点都包含两个指针，一个指向它的同一行链表中的每一个结点都包含两个指针，一个指向它的同一行的下一个元素，一个指向它的同一列的下一个元素的下一个元素，一个指向它的同一列的下一个元素观叙侠诈湘最豁喉植满尼窖航虽贵仍怎闭橱刨违搔来肝奋拓文圃唤窍实吟第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 十字链表的十字链表的A

22、DTtemplateclassOLNodeprivate:introw,col;/矩阵的行和列矩阵的行和列Telement;/矩阵中存储的数据矩阵中存储的数据OLNode*right,*down;/指向下一个结点的指针指向下一个结点的指针public:OLNode()right=NULL;down=NULL;词峙武挺神诽焙处吵刨丹显叫婚溅衷峰整侯掏脏瞩藩摹费浪烁唯是惫聋套第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 十字链表的建立十字链表的建立n建立矩阵的算法如下：建立矩阵的算法如下：n首先为行头结点和列头结点

23、申请空间，大小分别为首先为行头结点和列头结点申请空间，大小分别为矩阵的行列数矩阵的行列数n将三元组根据情况分别加入到链表中将三元组根据情况分别加入到链表中n如果三元组中的行列号错误，则退出，否则继续如果三元组中的行列号错误，则退出，否则继续n先处理行链表的问题先处理行链表的问题n如果该行头结点为空，则建立一个新的头结点，内容如果该行头结点为空，则建立一个新的头结点，内容为该三元组为该三元组n如果不为空则从头结点开始查找，找到该三元祖的正如果不为空则从头结点开始查找，找到该三元祖的正确位置如果该位置已经存在数据，则修改之，否则生确位置如果该位置已经存在数据，则修改之，否则生成相应的结点插入进去成

24、相应的结点插入进去n类似地处理列链表头类似地处理列链表头榆航蒋瞎忙掏臭礁坠穷市淫烛拣纤冰置罢汛衰坍舟萍卒察罕旷掌慰教漾盲第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 矩阵乘法矩阵乘法 =翌锭熄势乘鬼个俭蔽鹊滓叉悄殴勒打叮烟鲸俞蹋躺佃穿翔粪膏冀紊缕牌仔第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 经典矩阵乘法经典矩阵乘法nAc1.d1 c3.d3Ac1.d1 c3.d3，Bc3.d3 c2.d2, Bc3.d3 c2.d2, Cc

25、1.d1c2.d2Cc1.d1c2.d2。n d3 d3 C CA AB (CB (CijijAAikik B Bkjkj) ) k=c3 k=c3nfor (i=c1; i=d1; i+) for (i=c1; i=d1; i+) for (j=c2; j=d2; j+) for (j=c2; j=d2; j+) sum = 0; sum = 0; for (k=c3; k=d3; k+) for (k=c3; k=d3; k+) sum = sum + Ai,k*Bk,j; sum = sum + Ai,k*Bk,j; Ci Ci，j = sum;j = sum; 矫沙诧柠蛆您眼蕊禾幂旧氏

26、逃索任毒辈宠带谤苟彻睹炉熊掸月恩水糜蒂精第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page np=d1-c1+1，m=d3-c3+1，n=d2-c2+1；nA为为pm的矩阵，的矩阵，B为为mn的矩阵，的矩阵，乘得的结果乘得的结果C为为pn的矩阵的矩阵n经典矩阵乘法所需要的时间代价为经典矩阵乘法所需要的时间代价为O(pmn)铣赃篷炭劣拉厩搅秤袋建苦氨颤镣宪欲名领赛灶擅郑萍协沦拿毋懈陕湘狱第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 稀疏

27、矩稀疏矩阵乘法乘法template SMatrix*SMatrix:MatrixMutil(SMatrix*left,SMatrix*right) if(left-GetColnum()!=right-GetRownum()return NULL;/行列不匹配不能相乘行列不匹配不能相乘int I=0; /第一个矩阵的行数第一个矩阵的行数int J=0; /第二个矩阵的列数第二个矩阵的列数 SMatrix *ResultMatrix=new SMatrix();/结果矩阵结果矩阵 ResultMatrix-MallocMem(left-GetRownum(),right-GetColnum();

28、/为结果矩阵分配空间为结果矩阵分配空间for(I=1;IGetRownum();I+)/开始相乘开始相乘OLNode* RowNext=ResultMatrix-rowheadI;丸号漳曰原惭拢听乳毒俺敌烽冻逗钒辙沙伪旧共嗣几龟霓廷浦衷社钒搞崔第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page for(J=1;JGetColnum();J+) /扫描所有的列扫描所有的列OLNode* ColNext=ResultMatrix-colheadJ;int result=0;OLNode * rows=left-rowhe

29、adI;OLNode* cols=right-colheadJ;if(rows=NULL)|(cols=NULL)break;/新行没有非零元素新行没有非零元素 while(rows!=NULL)&(cols!=NULL)/所有行列都未非零的元素相乘所有行列都未非零的元素相乘if(rows-colrow)rows=rows-right;elseif(rows-colcols-row)cols=cols-down;炕拷徐夯废伶郑肚痈歪怯咎壳巢苍姑画迷层签箍斋葵启番咐摩佛憎耘抬馆第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究

30、Page else /都有元素可以相乘都有元素可以相乘result=result+cols-element*rows-element;cols=cols-down; rows=rows-right; if(result=0) continue;/插入到结果矩阵中插入到结果矩阵中OLNode* temp=new OLNode(); temp-row=I; temp-col=J; temp-element=result; if(RowNext=NULL)/加入行向量中加入行向量中/每行第一个元素每行第一个元素 ResultMatrix-rowheadI=temp; RowNext=ResultMa

31、trix-rowheadI;else/加入一个新的元素到下一个位置加入一个新的元素到下一个位置RowNext-right=temp;RowNext=RowNext-right;龚令袍静兽鹿裙成掖镑仅曳折森谐勘郴医腻秸危蜀腮惯淹判簿祭傅喻椎刻第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page if(ColNext=NULL)/加入到列向量加入到列向量/列结点第一次使用，加入新的结点列结点第一次使用，加入新的结点ResultMatrix-colheadJ=temp;ColNext=ResultMatrix-colhead

32、J;else/调转到合适的位置，插入调转到合适的位置，插入while(ColNext-down!=NULL)ColNext=ColNext-down;ColNext-down=temp;ColNext=ColNext-down;/完成放入完成放入ResultMatrix /乘法做完，返回新的矩阵乘法做完，返回新的矩阵 return ResultMatrix;夯犊筷原宜毒埂升奎豢鼠搓仔辰讶圃沙强削害破哨二炒泅牛咋掀杜津粟凰第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 稀疏矩阵乘法时间代价稀疏矩阵乘法时间代价n若矩

33、阵若矩阵A中行向量的非零元素个数最中行向量的非零元素个数最多为多为tan矩阵矩阵B中列向量的非零元素个数最多中列向量的非零元素个数最多为为tbn矩阵矩阵C中列向量的非零元素个数最多中列向量的非零元素个数最多为为tcn假设假设C矩阵中非矩阵中非0元素的个数总和为元素的个数总和为Nc瞩庆恳干梨愁拈根哪市陌敲帅脾撞秆菠狼怂傀辆秋矛瘪乒绅臂惦即纯执恋第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n每计算一个每计算一个 cij的时间的时间n主要用于顺着行主要用于顺着行I和列和列J寻找的过程寻找的过程n其循环次数最多为其循

34、环次数最多为ta+tbn每次循环所花时间是一个常量，记为每次循环所花时间是一个常量，记为kn计算一个计算一个cij的时间为的时间为k(ta+tb)n计算全部计算全部cij的时向为的时向为k(ta+tb)pn。恼瓮倦骇纵泊畦又便洛颇檬咱赐溅倍夷鉴局蔫子崖气冈揭还弯十晨棋穗贴第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n生成乘积矩阵的时间生成乘积矩阵的时间n计算出来的结果在行向量里面插入的时间是常数计算出来的结果在行向量里面插入的时间是常数n在列向量上插入需要每次定位到合适的位置，在列向量上插入需要每次定位到合适

35、的位置， 所花所花时间为时间为O(tc)，插入操作的总时间为，插入操作的总时间为O(Nc tc )n因此稀疏矩阵乘法的总执行时间上界为因此稀疏矩阵乘法的总执行时间上界为 O(ta+tb)pn)+ O(Nc tc )n如果修改此算法如果修改此算法n保留乘积保留乘积C矩阵的当前列指针向量位置，指向已插矩阵的当前列指针向量位置，指向已插入到入到C中各列最新的非零元素中各列最新的非零元素n可使每次插入的时间为一常数可使每次插入的时间为一常数n总执行时间降低为总执行时间降低为O(ta+tb)pn)曙讲龙柑搞威默狱勒殿伍卯瘫窑伴渤仰啼扦茨硷玻总鳃霖浆术肤匠鹿潮律第十一章高级线性表第十一章高级线性表北京大学

36、信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 11.2广义表广义表 n回顾线性表回顾线性表n由由n（n0）个数据元素组成的有限有序序列）个数据元素组成的有限有序序列n线性表的每个元素都具有相同的数据类型，通常为线性表的每个元素都具有相同的数据类型，通常为同一某种类型的数据记录同一某种类型的数据记录 n如果一个线性表中还包括一个或者多个子表，如果一个线性表中还包括一个或者多个子表，那就称之为广义表（那就称之为广义表（GeneralizedLists，也称，也称Multi-list）一般记作：）一般记作：nL（x0，x1，xi，xn-1）于圣谰竿潭魏剐三馏跳

37、佑蓉啦杜瞧均幢淘渐虾帅尖灰颠温理用橇拽啥额蛹第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page L（x0，x1，xi，xn-1）nL是广义表的名称是广义表的名称nn n为长度为长度n每个每个xi（0in-1）是）是L的成员的成员n可以是单个元素，即原子（也称可以是单个元素，即原子（也称“单元素单元素”，atom)n也可以是一个广义表，即子表（也可以是一个广义表，即子表（sublist）n广义表的深度：表中元素都化解为原子后的括广义表的深度：表中元素都化解为原子后的括号层数号层数挂甲修宝钻陋鸿密牵挨馒勋碎悉肆衫堑哲干志

38、廊栈醚疑疥阶鞠附顺驭摇据第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 广义表的各种类型广义表的各种类型n纯表（纯表（purelist） n从根结点到任何叶结点只有一条路径从根结点到任何叶结点只有一条路径n也就是说任何一个元素（原子、子表）只能在广义表中出现也就是说任何一个元素（原子、子表）只能在广义表中出现一次一次 辫你雨离怯葱欧窟以淆否匹邻闲掖搁树请渭踊刻丘先已者燃缎野吠汉昨张第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 广义

39、表的各种类型（续）广义表的各种类型（续）n可重入表可重入表(reentrantlist)n图示对应于一图示对应于一个个DAGn其元素其元素(包括原包括原子和子表子和子表)可能可能会在表中多次会在表中多次出现出现n但不会出现但不会出现回路回路 n对子表和原子对子表和原子标号标号嚼眼少又恃蠕讳海位瞥洒劝踩墙壁惶懦乃品依危容迎游阜你藉锨歪哦百纽第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 广义表的各种类型（续）广义表的各种类型（续）n循环表循环表(cycliclist，递归表表)的图示对应于任的图示对应于任何有向图何

40、有向图n有向图中可能包含回路有向图中可能包含回路 n循环表的深度为无穷大循环表的深度为无穷大府珐缝卵婪磷畸葫奴畴匙错廓挑溯桨弥凌针磺晓极汲撮蕾缩蔫周澳拴痴谚第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 拉键灰纪俯伤搅追扣汰隐摆祟排清惋雏介咎蔬硬羌絮粥惭烛诈瓷淬煌昨油第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n图 递归表表 再入表再入表 纯表表( (树) ) 线性表性表 n广义表是线性与树型结构的推广广义表是线性与树型结构的推

41、广梢第辣棵妈镊烫顶砌惹六迄晚酒起划寇刻摹殴耕唆抗敷比滩匹邹壮于淆腺第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 广义表的存储广义表的存储n使用数组来存储使用数组来存储n存储括号存储括号 n可以使用链表结构存储可以使用链表结构存储怨冲判足嗅蔼虎牡柞漏稚输入椭闯嫉队伐称棍腮诧万尽姨喘冲衔饶存稳溶第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 广义表存储广义表存储ADTtemplate class GenListNode public:

42、int type; /表示该结点是表示该结点是ATOM或者或者SubLISTT element; /如果是如果是ATOM，则存储它的值，则存储它的值 /如果是如果是LIST ,则指向它的元素的首结点则指向它的元素的首结点GenListNode *child; GenListNode *next;/指向下一个结点指向下一个结点 / 其他函数其他函数 ;倦真刑簇陶茫绢宙铃剔巢瞪豌龄合侗际满遮非窖酪归店琅激帖疟氏转捌即第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 广义表存储广义表存储ADT（续）（续）n不带表头的广义

43、表链不带表头的广义表链n在删除结点的时候会出现问题在删除结点的时候会出现问题 n删除结点删除结点data就必须进行链调整就必须进行链调整谰迢舰蓄沤贾钨伏寝剪番侣越簧醛窥反带捕僚仆萌墅困迹琶成凹伊抓湍杆第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 广义表存储广义表存储ADT（续）（续）n增加一个头指针来标志，简化删除，插入操作增加一个头指针来标志，简化删除，插入操作n此外，在访问循环链的时候会出现循环访问，所以需要一个标志此外，在访问循环链的时候会出现循环访问，所以需要一个标志位来记录该结点是否已经被访问过位来记

44、录该结点是否已经被访问过n图的因素图的因素月吭霉粤棍间趣贴拥簇脾诣凤蹭古什亥募邱钎床弹唇薯搔堆痕吁泌据繁答第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 眷久岸喻支亨厘须荫姬务印仰奢凡墅华浴抛曙趣则咽芭酉拳穷绦粤奴歉烷第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page /改进的广义表结点类型改进的广义表结点类型template class GenListNodepublic:int type; /表示该结点是表示该结点是ATOM or

45、LIST struct int ref; /如果是表头结点则，存储该结点被引用次数如果是表头结点则，存储该结点被引用次数 char* Name; / 表头名称表头名称 int mark; /本子表是否被访问过本子表是否被访问过 headNode; GenListNode *child;/如果是如果是LIST ,则指向子表则指向子表 T element; /如果是如果是ATOM，则存储它的值，则存储它的值 GenListNode *next;/指向下一个结点指向下一个结点 void GenListTraversal ();/周游该结点的子孙周游该结点的子孙 void GenListTravers

46、alHelp(GenListNode *node); .;旅浓测旁苛肺哼磐上井氮瓶摄镁调露锭坤酞辛影卸倚揽势纸绒旅洗撩复捞第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page /GenList是一个原子元素类型为是一个原子元素类型为T的广义表的广义表/如果要实现能够存储多种数据类型的广义如果要实现能够存储多种数据类型的广义/表，只需要嵌套的使用它表，只需要嵌套的使用它template class GenListprivate:GenListNode *head;/头结点头结点,存储头信息存储头信息GenListNode

47、 *current;/当前指针的位置当前指针的位置 public:GenList(char *Name);GenList();void Insert(T element);/在尾部加入一个元素结点在尾部加入一个元素结点void Insert(GenList *gl);/在尾部插入一个子表在尾部插入一个子表 GenListNode *GetHead();/取头结点取头结点GenListNode *GetNext();/取当前结点的下一个取当前结点的下一个GenListNode *GetPrev();/取当前结点的前一个取当前结点的前一个void MoveFirst();/当前指针指向当前指针指向

48、headint Remove();/删除当前结点删除当前结点void ViewList();/周游广义表周游广义表;欲汲剐斡刷狐祭庐化输寨刃圈剐仕滇屠锦范朝缮融课蔡图肠柒腻卷遣汗叶第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 广义表的周游算法广义表的周游算法n广义表周游的时候应该注意几个问题：广义表周游的时候应该注意几个问题：n相当于深度优先周游相当于深度优先周游n访问的时候首先进入一个子表的头结点，设置访问的时候首先进入一个子表的头结点，设置mark标记标记n按照本层子结点顺序，访问广义表按照本层子结点顺序，

49、访问广义表n如果是子表结点，则准备递归地访问此子表表头结点如果是子表结点，则准备递归地访问此子表表头结点n如果是原子，则直接访问如果是原子，则直接访问n避免进入循环链中无法跳出避免进入循环链中无法跳出nmark用来防止循环访问而设置的访问位用来防止循环访问而设置的访问位n实际上，表头结点才需要实际上，表头结点才需要markn广义表访问结束的时候广义表访问结束的时候n应该将应该将mark设置为未访问设置为未访问n以便如果其他地方也引用了该链可以正常的访问到以便如果其他地方也引用了该链可以正常的访问到又果子枝诚逞毗船祖文鲸单雄琶甚优破皖邯卤剑枝取仿烫肺孟异敛德柏啦第十一章高级线性表第十一章高级线性

50、表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 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); Li

51、st4-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(); 肉债夯音甲崩揣另脸拾似应砒咖肢跺入瞒播橙染拂乱四慰疹崭贸恤瓤屿猿第十一章高级线性表第十一章高级线性表

52、北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 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-h

53、eadNode.mark = UNVISITED) if (p-child-headNode.Name0!=0) cout child); else if (p-type=ATOM) coutelement;if (p-next!=NULL) / &(p-next-type!=HEAD) cout , ;cout );谰途妊闻掣婆耕取埂驾防忻脊幢灵澎魁铆夏畏朴歪霜嘴毁臭没癌穆傲镭站第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page template void GenList:ViewList()MoveToFirst

54、(); current-GenListTraversal ();template void GenListNode:GenListTraversal ()GenListTraversalHelp(this);涕胺峦格恭齿痊顺还羽溯极智墒救妖热嘱虫快慷嗜该门薯伯霜扫迈害验庙第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 11.3存储管理技术存储管理技术n在在C C这这样样的的高高级级程程序序设设计计语语言言中中，程程序序员员经经常常会会进进行行newnew和和deletedelete操操作作，即即动动态态内内存存分

55、分配配。在在实实际际的的操操作作系系统统中中，内内存存管管理理本本质质上上是是利利用用链链表表和和广广义义表表来来实实现现的。的。n本本小小节节将将首首先先介介绍绍可可利利用用空空间间表表的的概概念念，并并简简单单介介绍绍可利用空间表中所有结点长度都相等的情况。可利用空间表中所有结点长度都相等的情况。n随后将介绍在可利用空间表中处理变长结点的方法随后将介绍在可利用空间表中处理变长结点的方法含轮徘饯扫旅愉婶豆舶府蛰顿悬铭淫布誉血环态颖兑瓣痔螟代痊讽励饶培第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 分配与回收分配

56、与回收 n内存管理最基本的问题是存储的分配与回收内存管理最基本的问题是存储的分配与回收 n分配存储空间，回收被分配存储空间，回收被“释放释放”的存储空间。的存储空间。在分配和回收过程中，需要解决碎片问题，这在分配和回收过程中，需要解决碎片问题，这就是存储的压缩就是存储的压缩 n可可能能由由于于程程序序员员忘忘记记delete已已经经不不再再使使用用的的指指针针等等等等，而而产产生生了了许许多多无无用用单单元元(garbage)，需需要要对对这这样样的的无无用用单单元元进进行行有有效效的的收收集集，而而且且收收集完往往还需要再进行压缩。集完往往还需要再进行压缩。供辈蛾从萤撂尊再辗握锯恍萧麓驴舟宛

57、帆浇辊桃嘿砂痴总促傍乱杏亢减舱第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 存储空间溢出的管理存储空间溢出的管理 n由于主存容量的限制，所以无论采用哪种存储由于主存容量的限制，所以无论采用哪种存储管理技巧，总难免产生内存溢出。管理技巧，总难免产生内存溢出。n溢出发生后，可以借助外存的帮助，把内存中溢出发生后，可以借助外存的帮助，把内存中某些结点（或由这些结点组成的结构）撤离到某些结点（或由这些结点组成的结构）撤离到外存上去，并且提供一定的手段在必要时将这外存上去，并且提供一定的手段在必要时将这些结点再取回内存。

58、些结点再取回内存。n为了减少内外存数据交换次数，送到外存上去为了减少内外存数据交换次数，送到外存上去的内容应该选择最近不使用的那些结点的内容应该选择最近不使用的那些结点殿坍穗很膀杨玲役絮胳仿软苦茧喳琼骡骂六页肯黔耻超碎氯撕娟个危梦庭第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 可利用空间表可利用空间表 n为了进行动态存储分配，可以把存储器看成一为了进行动态存储分配，可以把存储器看成一组变长块数组，其中一些块是空闲的，一些块组变长块数组，其中一些块是空闲的，一些块是已分配的，空闲块链接到一起，形成一个可是已分配的

59、，空闲块链接到一起，形成一个可利用空间表利用空间表(freelist)。n所谓可利用空间是指存储区中当前还没有使用所谓可利用空间是指存储区中当前还没有使用的空间的空间 n对于存储请求，要在可利用空间表中找到足够对于存储请求，要在可利用空间表中找到足够大的块。如果找不到，那么存储管理器就要求大的块。如果找不到，那么存储管理器就要求助于失败策略。助于失败策略。 唬剧袱否雹楞挝惕遣喘茂床结扔凤迢卧薛豪愚琴苦肄板贰两控女员酪儡瞬第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 长度固定的存储分配长度固定的存储分配 n把可利

60、用空间表组织成链栈把可利用空间表组织成链栈(或链式队列或链式队列)的形的形式。式。n在系统运行初期将整个可利用空间划分成固定在系统运行初期将整个可利用空间划分成固定大小的数据块，而且利用指针字段把这些数据块大小的数据块，而且利用指针字段把这些数据块链接起来，并使用一个指针指向首结点，这样就链接起来，并使用一个指针指向首结点，这样就形成了一个单链表即这个可利用空间表。形成了一个单链表即这个可利用空间表。n以后每执行一次以后每执行一次newp操作就从可利用空间中取操作就从可利用空间中取走一个数据块，并用走一个数据块，并用p指向该数据块；每执行一指向该数据块；每执行一次次deletep操作就把操作就

61、把p指向的数据块插入到可利用指向的数据块插入到可利用空间表的链表中。空间表的链表中。枷沾赊霉凰鹏问洁鼠颈榔疟般订悦国源棵添骋谋镑鞭刻焰以恍硝骤给钠谨第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 关终阐竹项识口盗坚贡尼是牢利券矮雪耸祟矿晓翁艺穆锐软侗涝哉地掐很第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 可利用空间表的单链表定义和函数重载可利用空间表的单链表定义和函数重载 templateclassLinkNodeprivate:

62、staticLinkNode*avail;/可利用空间表头指针可利用空间表头指针public:Elemvalue;/结点值结点值LinkNode*next;/指向下一结点的指针指向下一结点的指针LinkNode(constElem&val,LinkNode*p);LinkNode(LinkNode*p=NULL);/构造函数构造函数void*operatornew(size_t);/重载重载new运算符运算符voidoperatordelete(void*p);/重重载载delete运运算符算符;性考遭氏幻啃源岂芝界糯洲睡默遂茧铜式兜流帆碾霄蠕盎妊市迟擎辱队邢第十一章高级线性表第十一章高级线性

63、表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page /重载重载new运算符实现运算符实现templatevoid*LinkNode:operatornew(size_t)if(avail=NULL)/可利用空间表为空可利用空间表为空return:newLinkNode;/利利用用系系统统的的new分分配配空间空间LinkNode*temp=avail;/否否则则从从可可利利用用空间表中取走一个结点空间表中取走一个结点avail=avail-next;returntemp;辟坞聘绥热剖税诣彭登缝捣宝倘柔无唬筒额剁求远蛰陨荫孤狼挤乱拖藕钓第十一章高级线性

64、表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page /重载重载delete运算符实现运算符实现templatevoidLinkNode:operatordelete(void*p)(LinkNode*)p)-next=avail;avail=(LinkNode*)p;述递泪茹赡呀遇黄导歧屡刽绦哇尺附威皮暮安寡踏恰驹沽痉唐禄矢睁铸升第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n这这种种可可利利用用空空间间表表实实际际上上是是一一个个用用单单链链表表实

65、实现现的的栈栈。new代代表表栈栈的的删删除除操操作作，如如果果avail为为空空指指针针，代代表表已已没没有有可可利利用用空空间间。delete代代表表栈栈的插入操作。的插入操作。n如如果果程程序序员员需需要要直直接接引引用用系系统统的的newnew和和deletedelete操操 作作 符符 ， 需需 要要 强强 制制 用用 “:new :new p p”和和“:delete :delete p p”。这这种种强强制制在在整整个个程程序序运运行行完完毕毕时时是是十十分分必必要要的的，可可以以把把availavail所所占占用用的的空空间都交还给系统（真正释放空间）。间都交还给系统（真正释放

66、空间）。兑酋靖域荒涅顺间挡垮键强呕抗姜构渝应捞服料至孕翘盏伍酋什展涧臆谋第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 各种类型和长度的可利用空间表各种类型和长度的可利用空间表 n有三种很直观的解决方案：有三种很直观的解决方案：n(1)建建立立起起多多个个可可利利用用空空间间表表，每每个个链链表表可可以以为为某某一种长度的变量分配存储空间。一种长度的变量分配存储空间。n(2)统统一一按按照照较较长长的的结结点点组组织织可可利利用用空空间间表表，把把变变长长结结点点按按同同样样长长度度进进行行分分配配。这这在在结结

67、点点长长度度差差别别不不大大时时还还可可以以采采用用，但但是是在在长长度度差差别别很很大大时时，就就可可能能造造成成不可容忍的存储空间浪费。不可容忍的存储空间浪费。n(3)多多个个可可利利用用空空间间表表共共享享同同一一个个存存储储空空间间，事事先先估估计计出出每每个个链链表表中中最最多多可可以以有有多多少少个个结结点点，并并把把这这些些结结点点都都链链接接起起来来。但但这这造造成成了了在在空空间间和和时时间间上上的的巨巨大大浪浪费费。这这样样的的处处理理没没有有解解决决共共享享问问题题，代代价价很很高高，管管理也不方便。理也不方便。捣产脊烩啄豁胺坤琐江教漱测窗船错祖高罗掂鸳洗锐垛丫窥寂厌铅榆

68、淡邱第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n不不对对每每个个可可利利用用空空间间表表进进行行预预分分配配，而而是是随随着着系系统统运运行而动态分配。行而动态分配。n假假设设有有一一片片从从地地址址L L开开始始的的动动态态存存储储区区域域，上上界界地地址址为为S S。这这片片存存储储区区域域由由n n个个链链表表所所共共享享，每每个个链链表表的的结结点点类类型型都都不不同同。显显然然，需需要要为为这这n n个个链链表表建建立立n n个个可可利利用用空间表。空间表。n系系统统刚刚开开始始运运行行，所所有有

69、的的可可利利用用空空间间表表的的头头指指针针availavail都赋为空值。都赋为空值。n在在系系统统运运行行过过程程中中，每每当当链链表表的的结结点点被被删删除除时时，把把被被删除结点推入到对应的可利用空间表中储备起来。删除结点推入到对应的可利用空间表中储备起来。动态分配动态分配 和讯辫扦无腹侍看纳届桶秘昭撑窝烹螟债苞失搪愤蹲矮肃淬详椽指谎顺汗第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 动态分配（续）动态分配（续）n每每当当需需要要向向某某链链表表中中动动态态插插入入结结点点时时，如如果果对对应应的的可可利

70、利用用空空间间表表非非空空，则则从从可可利利用用空空间间表表中中删删除除一一个个结结点点的的空空间间给给它它；如如果果对对应应的的可可利利用用空空间间表表为为空空，则则从从后后备备存存储储区区中中去去取取一一块块存存储储空间。空间。n我我们们用用一一个个指指针针pmaxpmax来来指指向向动动态态存存储储区区的的后后备备存存储储区区的的起起始始地地址址，随随着着后后备备存存储储区区的的不不断断消消耗耗，pmaxpmax值值不不断断增增大大。但但只只要要pmaxpmax加加上上待待分分配配结结点点长长度度小小于于等等于于S S，就就可可以以继继续续进进行行动动态态分分配。配。 慈午哦缸瞎撑纂缆狞

71、泰里走蓄惰虱恳厨歧泄撬靡找体淡养般帽押困浙彩暂第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 诱讥贿鸥扛润蕴皑摔藻滇宾澈芥俭郡然石哩驯跨几泣钧柴埃牟某牌症届昭第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 可利用空间表动态存储区的分配算法可利用空间表动态存储区的分配算法void*LinkNode:operatornew(size_t)LinkNode*temp;if(avail=NULL)/可利用空间表为空可利用空间表为空retur

72、n:newLinkNode; /利用系统的利用系统的new分配空间分配空间if(pmax+KS)coutlink;returntemp;易痕旭售风侥娟将悦送颐娜翁趣达沿徐魁替档概验噎宴豺贷刺晌拆伊观穆第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 算法的缺点算法的缺点n这这种种方方法法存存在在着着一一些些严严重重的的问问题题：每每个个可可利利用用空空间间表表的的结结点点大大小小是是固固定定的的，后后备备存存储储区区里里的的空间一旦被分配就不能再回到后备存储区中空间一旦被分配就不能再回到后备存储区中n如如果果pma

73、x值值已已经经达达到到或或超超过过S值值而而不不能能再再分分配配空空间间时时，实实际际上上系系统统中中别别的的可可利利用用空空间间表表中中可可能还存在大量的空闲结点。能还存在大量的空闲结点。枣普柯辣柑和沛栖沈锥万侣饿则与自彝耀坪踞馒娃繁挚旱堂珊丧捍劳劣簧第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 存储的动态分配和回收存储的动态分配和回收n把各种大小的结点（又称可利用块）组织在一把各种大小的结点（又称可利用块）组织在一个可利用空间表中；分配时需要按申请的长度个可利用空间表中；分配时需要按申请的长度在可利用空间表

74、中进行检索，找到其长度大于在可利用空间表中进行检索，找到其长度大于等于申请长度的结点，从中截取合适的长度等于申请长度的结点，从中截取合适的长度n回收时也不能简单地把删除的结点放回到可利回收时也不能简单地把删除的结点放回到可利用空间表中，而必须考虑刚刚被删除的结点空用空间表中，而必须考虑刚刚被删除的结点空间能否与可利用空间表中的某些结点合并，组间能否与可利用空间表中的某些结点合并，组成较大的结点，以便能满足后来的较大长度结成较大的结点，以便能满足后来的较大长度结点的分配请求。点的分配请求。冕颧铀裁眉响淀洱重寝驰召秧衙阴棍删沸启另堵伊妙蕴比尿蛰掘威辅茹觅第十一章高级线性表第十一章高级线性表北京大学

75、信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 本方法的优缺点本方法的优缺点n这这种种处处理理方方法法的的优优点点是是可可以以解解决决存存储储空空间间的的共共享问题享问题n缺缺点点是是分分配配和和回回收收的的算算法法复复杂杂了了，并并且且在在系系统统长长期期动动态态运运行行的的过过程程中中，这这种种方方法法有有可可能能使使整整个个空空间间被被分分割割成成许许多多大大小小不不等等的的碎碎块块，而而某某些些碎碎块块由由于于太太小小而而长长期期得得不不到到使使用用，这这就就产产生生所所谓碎片问题。谓碎片问题。柴额赊困甸娩钨储阅际磕筑志沃事杆夜慧施衅笆瘫弟疮哟贩骏

76、膏颖铱羽狸第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 空闲块空闲块的数据结构的数据结构n空空闲闲块块的的长长度度是是不不定定的的，所所以以可可利利用用空空间间表表中中每个结点都需要记录本结点的长度。每个结点都需要记录本结点的长度。n一一种种常常见见的的方方法法是是，对对于于一一个个需需要要m字字节节空空间间的的请请求求，存存储储管管理理器器可可能能会会分分配配稍稍多多于于m字字节节的空间的空间n额额外外的的空空间间留留给给存存储储管管理理器器进进行行存存储储管管理理，例例如存放块的标记位、链表指针和块长度。如

77、存放块的标记位、链表指针和块长度。n标标记记位位用用来来区区别别这这个个块块是是空空闲闲块块还还是是已已被被分分配配的块。的块。匹椅嘉卷器柳孰铱岗颂符察壁臀瓜寞兵醛污哑衙送燃癌加椿儿融抓菱悟铅第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 阑渝疯谱渭阮回风禽垛慷砖健翠动牲羡部考哉仔捏疥计裔椽挑瞬浑勘娠累第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 动态分配动态分配n动态分配就是要在可利用空间表中找到一个合动态分配就是要在可利用空间

78、表中找到一个合适的空闲块以满足存储请求适的空闲块以满足存储请求 n即即为为了了分分配配一一个个N字字节节大大小小的的空空间间，就就要要利利用用某某种种策策略略从从可可利利用用空空间间表表中中搜搜索索到到一一个个长长度度大大于于等等于于N字字节节的的空空闲闲块块进进行行分分配配；如如果果可可利利用用空间表中不存在这样的结点，就不能进行分配。空间表中不存在这样的结点，就不能进行分配。奢边尿窘挖甜太卧虽椅庇乎阵辟渝援吊贯瓦引诫京娥虏梆镍主偏井洼谚馈第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 分配方法分配方法n如如果

79、果能能够够找找到到大大于于N字字节节的的空空闲闲块块，一一种种可可能能的的做做法法是是整整个个块块交交给给请请求求者者，整整个个空空闲闲块块的的首首尾标记位都修改为尾标记位都修改为“-”，表示它是已分配块，表示它是已分配块n另另一一种种做做法法是是对对于于一一个个长长度度为为K（KN）字字节节的的空空闲闲块块，存存储储管管理理器器把把N字字节节分分配配给给请请求求者者，剩剩余余的的K-N字字节节形形成成一一个个新新的的空空闲闲块块；对对已已分分配配块块和和剩剩余余空空闲闲块块设设置置相相应应的的标标记记、长长度度和和链链指针字段。指针字段。n不不管管采采用用哪哪种种做做法法，都都会会存存在在所

80、所谓谓碎碎片片(fragmentation)的问题。的问题。俗添萤孝洋陡侗泰鲤扦过冻浆假斩抵棵抠崔鉴蔽畅尉粘儡埂访香姥描洗弛第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 碎片类型碎片类型n上述的第一种做法，把多于请求字节数的空间上述的第一种做法，把多于请求字节数的空间分配给请求者，会浪费空闲块的空间，从而产分配给请求者，会浪费空闲块的空间，从而产生生“内部碎片内部碎片”(internalfragmentation)。n如果按照前述的第二种做法，把满足请求后的如果按照前述的第二种做法，把满足请求后的K-N个字节作

81、为新的空闲块，则会产生大量的个字节作为新的空闲块，则会产生大量的不能满足一般性请求的小空闲块，称为不能满足一般性请求的小空闲块，称为“外部外部碎片碎片”(externalfragmentation)。 妥译犀骤泡足渊立番方碍竣轻汾队娥捞静廉兰释掠郡锌惩妻标荣否釜彰渠第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 茂绞头皮挑梢损烧域尼窒雄溢字战窘犹捕嗣邱杂债胆章篙抚氧饼戒驱果称第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 顺序适配顺

82、序适配(sequentialfit) n下下面面先先介介绍绍一一些些可可能能产产生生外外部部碎碎片片的的方方法法，这这类方法通称为类方法通称为顺序适配顺序适配(sequentialfit)。n常见的顺序适配方法有这几种：常见的顺序适配方法有这几种：n首先适配首先适配(firstfit)n最佳适配最佳适配(bestfit)n最差适配最差适配(worstfit)睦傻锨已哼紊培瞄休拷臣曼璃育乌鳃猎褥零旗香斜蒂吝诡顿庆级余箱鹏娃第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 首先适配首先适配n首先适配从可利用空间表的表头

83、开始，顺次在首先适配从可利用空间表的表头开始，顺次在可利用空间表中进行搜索，一旦找到第一个长可利用空间表中进行搜索，一旦找到第一个长度大于等于请求块长度的空闲块，就进行分配。度大于等于请求块长度的空闲块，就进行分配。n一种简单改进是：记住前一次搜索到达的位置，一种简单改进是：记住前一次搜索到达的位置，从该位置开始新搜索。当搜索到达链表尾部的从该位置开始新搜索。当搜索到达链表尾部的时，重新从链表头处开始搜索。时，重新从链表头处开始搜索。n首先适配的优点是速度快，缺点是可能把较大首先适配的优点是速度快，缺点是可能把较大块拆分成较小的块，导致后来对大块的申请难块拆分成较小的块，导致后来对大块的申请难

84、以满足。以满足。差住侧将匙拿没杨傻旺隆据概砧燥霍之唇壬戎氓摹机唾宣辰惦弗侣线椭贩第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 最佳适配最佳适配n最佳适配在所有长度大于等于请求块长最佳适配在所有长度大于等于请求块长的块中找出最小的一块进行分配。的块中找出最小的一块进行分配。n最佳适配的优点：它可以使得无法满足最佳适配的优点：它可以使得无法满足大请求块的可能性降到最低。大请求块的可能性降到最低。n最佳适配的缺点：使得外部碎片问题变最佳适配的缺点：使得外部碎片问题变得非常严重，因为那些满足请求后剩下得非常严重，因为那

85、些满足请求后剩下的空闲块非常小，对将来的请求就没有的空闲块非常小，对将来的请求就没有什么用处了。什么用处了。卉苛队赋缺缕寐竞煽怔忘尾炸迅竖绪一梯破粱亡他诫篇孜叭煞目拥卡它呸第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 最佳适配的方案最佳适配的方案n实现最佳适配有两种方案。实现最佳适配有两种方案。n其一，检索整个无序的可利用空间表，找到满足分其一，检索整个无序的可利用空间表，找到满足分配请求的最小空闲块。配请求的最小空闲块。n其二，把空闲块按照从小到大顺序排列成优先队列，其二，把空闲块按照从小到大顺序排列成优先队

86、列，使得检索时只需要从表头往后查看，直至找到第一使得检索时只需要从表头往后查看，直至找到第一块满足分配请求的空闲块；但回收空闲块时，需要块满足分配请求的空闲块；但回收空闲块时，需要插入到优先队列中合适的位置。插入到优先队列中合适的位置。n这两种方案耗时都比较多。最佳适配的结果是这两种方案耗时都比较多。最佳适配的结果是空闲块的长度变化很大。空闲块的长度变化很大。 居诺输谈愚革浑爷溺寒涨悔吓卫懊氰茎入沽梁祥劈边暴痉迄膛铁锅梁峙寡第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 最差适配最差适配 n最差适配采用的是一种与

87、最佳适配完全相反的最差适配采用的是一种与最佳适配完全相反的策略，它在所有长度大于等于请求块长的空闲策略，它在所有长度大于等于请求块长的空闲块中找出最大的一块进行分配。适合于存储分块中找出最大的一块进行分配。适合于存储分配长度请求比较均匀的情况。配长度请求比较均匀的情况。 n实现最差适配有两种方案。实现最差适配有两种方案。n其一，检索整个无序的可利用空间表，找到整个可其一，检索整个无序的可利用空间表，找到整个可利用空间的最大空闲块。利用空间的最大空闲块。n其二，把空闲块按照从大到小顺序排列成优先队列，其二，把空闲块按照从大到小顺序排列成优先队列，检索时如果表头结点满足分配请求，则把它分配出检索时

88、如果表头结点满足分配请求，则把它分配出去，否则存储分配要求无法满足；但回收空闲块时，去，否则存储分配要求无法满足；但回收空闲块时，需要插入到优先队列中合适的位置。需要插入到优先队列中合适的位置。菜露乏员箭景铱谦竭骤修秉睫凭员寂模宰讽跃侥涉霸出娇占牢倘老杂米涵第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 三种方法举例三种方法举例n假假设设可可利利用用空空间间表表中中包包含含三三个个可可利利用用块块，其其大大小小分分别别是是：1200，1000，3000，现现有有如如下下一一串串存储分配的请求：存储分配的请求：60

89、0，500，900，2200n采用最佳适配。分配采用最佳适配。分配600以后，空闲块为以后，空闲块为1200，400，3000；分配；分配500以后，空闲块为以后，空闲块为700，400，3000；分配；分配900以后，空闲块为以后，空闲块为700，400，2100；再分配；再分配2200，发生溢出。，发生溢出。庶绅痢砸无郎敖株妻肿耿证嘉躲悦需聪播苑昧榔盆埠开怒逐肉愚百涅汛绕第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 三种方法举例（续）三种方法举例（续）n采采用用首首先先适适配配。分分配配600以以后后，空空

90、闲闲块块为为600，1000，3000；分分配配500以以后后，空空闲闲块块为为100，1000，3000；分分配配900以以后后，空空闲闲块块为为，100，100，3000；分分配配2200以以后后，空空闲闲块块为为100，100，800 n采采用用最最差差适适配配。分分配配600以以后后，空空闲闲块块为为1200，1000，2400；分分配配500以以后后，空空闲闲块块为为1200，1000，1900；分分配配900以以后后，空空闲闲块块为为1200，1000，1000；再分配；再分配2200，发生溢出。，发生溢出。艳家辊涌钝娥么抓厂堕奎登热苯淘某檄涨镇臆狠漱膜鹅赏谚别膀啮皂易熔第十一章高

91、级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n采采用用顺顺序序适适配配方方法法，当当一一个个块块被被释释放放时时，需需要要把把它它重重新新链链回回到到可可利利用用空空间间表表中中。如如果果这这个个块块与与可可利利用用空空间间表表中中其其他他空空闲闲块块物物理理地地址址相相邻邻，则则需需要要合合并并这这些些相相邻邻块块，这这样样存存储储管管理理器器才才能能满足将来尽可能大的存储请求。满足将来尽可能大的存储请求。回收回收袋猜恢炊赣溺籍又悍烁绥而郸婴咋梧饱佑朱摩聚菩几泼奥欺勇彰循傅帅划第十一章高级线性表第十一章高级线性表北京

92、大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 勿谈郝翘疼莹份润难柏寞厢敌田墙考饺屯啪催惟踊吗凡牧摊册少玻磋设忧第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 回收过程回收过程n把块把块M释放到可利用空间表的过程：释放到可利用空间表的过程：n首首先先检检查查块块M左左邻邻的的存存储储单单元元L，根根据据其其标标记记位位可可以判断块以判断块L是不是空闲块。是不是空闲块。n如果不是，则简单地把如果不是，则简单地把M插入可利用空间表。插入可利用空间表。n如如果果如如图图中中所所

93、示示，L是是空空闲闲块块，则则把把L的的长长度度扩扩展展到到包包含含M。然然后后，检检查查M的的右右邻邻块块N的的标标记记位位，如如果果块块N是是空空闲闲块块，则则要要把把N从从可可利利用用空空间间表表中中删删除除，同同时时扩扩展展M的的长长度度（在在本本例例则则是是扩扩展展已已包包含含M的的L的的长度）。长度）。n经经过过对对块块M的的回回收收操操作作之之后后，就就形形成成了了一一个个包包含含原原来的来的L、M、N三个块长度的大空闲块。三个块长度的大空闲块。官烷迎匠缆亚合富家级堑馆萎姥妨剥肝彬慈慌把外曳街叙莲赁校京足填哀第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版

94、版权所有，转载或翻印必究权所有，转载或翻印必究 Page 回收的策略回收的策略n很很难难笼笼统统地地讲讲这这哪哪种种适适配配策策略略最最好好。需需要要考考虑虑以下因素来确定采用哪种顺序适配方案以下因素来确定采用哪种顺序适配方案n用户的要求用户的要求n分配或回收效率对系统的重要性分配或回收效率对系统的重要性n所分配空间的长度变化范围所分配空间的长度变化范围n分配和回收的频率。分配和回收的频率。n在在实实际际应应用用中中，由由于于首首先先适适配配其其分分配配和和回回收收的的速速度度比比较较快快，而而且且支支持持比比较较随随机机的的存存储储请请求求，因为应用得更广泛。因为应用得更广泛。金搁铝鄂锅龚糜

95、嫌橡塘增普盛蘑烙时泥尽弊刺视已梨蓬惶阵崔渡惠词询免第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 伙伴系统伙伴系统n伙伙伴伴系系统统的的数数据据块块中中不不再再存存放放任任何何关关于于块块本本身身的信息字段。的信息字段。n伙伙伴伴系系统统假假设设存存储储空空间间的的大大小小为为2M，M为为正正整整数数。当当然然，这这个个假假设设对对大大多多数数实实际际存存储储器器也也是是成立的。成立的。n伙伙伴伴系系统统中中的的每每一一个个空空闲闲块块和和已已分分配配块块的的大大小小都都是是2k，k小小于于等等于于M。系系统统为

96、为每每一一种种大大小小的的空空闲闲块块都都单单独独建建立立一一个个列列表表，系系统统中中保保留留的的列列表表数目决不会超过数目决不会超过M个。个。 亥旗冯枚头誓堡跌锣帖请柴镍唐逻妊脖鼓舵市皱掉族栏陌直裂赐奏桓勃围第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n每每一一个个块块都都有有一一个个对对应应的的“伙伙伴伴”块块，它它们们的的大小是相同的。大小是相同的。n对对伙伙伴伴系系统统而而言言，2k大大小小的的块块首首地地址址与与它它的的伙伙伴伴的的首首地地址址相相比比，除除了了第第k位位之之外外（最最右右为为第第

97、0位），所有的位都相同。位），所有的位都相同。n例例如如，长长度度为为8=23个个字字节节、首首地地址址为为0000的的块块，其其伙伙伴伴是是首首地地址址为为1000的的块块（从从右右往往左左数数，1000与与0000的第的第3位相同）。位相同）。“伙伴伙伴”的含义的含义券今翔五暗最时诣耐泳耸秤查刻缕榴支侯猎骆婪洞姆蓄蜒唾甘坎搽息拷痕第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page n对于一个需要对于一个需要N个字节的存储请求，伙伴系统个字节的存储请求，伙伴系统首先确定使得首先确定使得2kN的最小的最小k值。值。n

98、如果在可利用空间表中能找到如果在可利用空间表中能找到2k大小的空闲块，大小的空闲块，就分配这个空闲块；否则，就找一个更大的空就分配这个空闲块；否则，就找一个更大的空闲块，把它均分成两半；闲块，把它均分成两半；n不断重复这个分割的过程，直到生成一个不断重复这个分割的过程，直到生成一个2k大大小的空闲块，并把它分配出去。在分割过程中小的空闲块，并把它分配出去。在分割过程中生成的空闲块都记录到可利用空间表中去。生成的空闲块都记录到可利用空间表中去。 伙伴系统的分配伙伴系统的分配袭迂豫键隘蕴霍帮终鳃暑捎栓屋问惊钟琅椒噪哥铅坯颖嚣差司整妹语秽钢第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学

99、信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 伙伴系统的特点伙伴系统的特点n伙伙伴伴系系统统的的一一个个缺缺点点是是它它允允许许内内部部碎碎片片的的存存在在，因因为为很很难难有有恰恰好好2k=N的的情情况况发发生生。但但它它的的外外部部碎片却非常少。碎片却非常少。n伙伙伴伴系系统统的的另另一一个个优优点点是是从从可可利利用用空空间间表表中中搜搜索索空空闲闲块块的的速速度度极极快快，因因为为只只需需要要从从2k大大小小的的空闲块中取出第一个就可以了。空闲块中取出第一个就可以了。n此此外外，在在回回收收的的时时候候，合合并并相相邻邻空空闲闲块块也也十十分分简单。简单。许描蜜

100、娩深枉关族坟翌疽擂鞘狱涧囊脾哄廉税谅夫疲亡粳梳心富李叮鸵咀第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 伙伴系统的回收过程伙伴系统的回收过程n长长度度为为4=22个个字字节节、首首地地址址为为1000的的块块即即将将被被释释放放回回可可利利用用空空间间中中，根根据据伙伙伴伴系系统统的的特特点点，此块的伙伴是首地址为此块的伙伴是首地址为1100的块。的块。n通通过过搜搜索索对对应应的的块块长长度度表表就就可可以以找找到到伙伙伴伴。如如果果伙伙伴伴是是空空闲闲块块，就就把把它它们们进进行行合合并并，形形成成更更大大

101、的的块块，按按此此循循环环直直到到不不能能继继续续合合并并。最最后后再再把合并所形成的大空闲块放到可利用空间表中。把合并所形成的大空闲块放到可利用空间表中。嫉镜胶饯逾浚皆痴听鹊里瘫悬稼诌厉字坡市签馅犀装振挖肩辕锻牟缆斟捕第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 和辨揍哟姥领必奋蓖衣距邦俩彝吹郸胖已挡尧太脚土瘤族嘉忆屹碌霍胰床第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 失败处理策略和无用单元回收失败处理策略和无用单元回收n如

102、如果果遇遇到到因因内内存存不不足足而而无无法法满满足足一一个个存存储请求，存储管理器可以有两种行为：储请求，存储管理器可以有两种行为：n一一是是什什么么都都不不做做，直直接接返返回回一一个个系系统统错错误误信信息；息；n二二是是使使用用失失败败处处理理策策略略(failurepolicy)来来满满足请求。足请求。磕禾袜灭邱筛稼唱戍吕赞讽烁谗育到鞍奥雏房禾英驰获闯棍臻轰匪挝茸众第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 存储压缩存储压缩(compact)n当使用顺序适配存储分配方法时，可能有足够当使用顺序适配存

103、储分配方法时，可能有足够的空间来满足请求，因为这些方法造成了不少的空间来满足请求，因为这些方法造成了不少外部碎片，把它们收集起来可能得到连续的大外部碎片，把它们收集起来可能得到连续的大块存储空间能够满足存储请求。这就是存储压块存储空间能够满足存储请求。这就是存储压缩，通过压缩把内存中的所有碎片集中起来组缩，通过压缩把内存中的所有碎片集中起来组成一个大的可利用块。成一个大的可利用块。 n只有内存碎片很多却分配不出有用空间而即将只有内存碎片很多却分配不出有用空间而即将产生溢出时，不得已才使用产生溢出时，不得已才使用炭汞擎扳萎菜伪抬殖镶蔚痉蛹钝封提幕奸楷耗酚鹅填铡外娜瞎椅帧航瞧莽第十一章高级线性表第

104、十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 句柄句柄(handle)n存储压缩之后，应用程序的数据地址将发生变存储压缩之后，应用程序的数据地址将发生变化。如果应用程序以某种方式依赖于数据的绝化。如果应用程序以某种方式依赖于数据的绝对位置，就会引起严重的后果。对位置，就会引起严重的后果。n句柄是对存储位置的二级间接指引，可以使得句柄是对存储位置的二级间接指引，可以使得存储地址相对化。存储管理器在进行内存分配存储地址相对化。存储管理器在进行内存分配的时候不是返回一个指向空闲块的指针，而是的时候不是返回一个指向空闲块的指针，而是返回一

105、个指向变量的指针，这个变量才指向存返回一个指向变量的指针，这个变量才指向存储位置，这个变量就是句柄。储位置，这个变量就是句柄。n可以移动存储块的位置，而只需要修改句柄的可以移动存储块的位置，而只需要修改句柄的值，不需要修改应用程序。值，不需要修改应用程序。聊障愈损涨牡苍浓桨有芳愿令信寅嘘暴纠铀店斑履蛙廊虏智宁赢骡拨都座第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 无用单元收集无用单元收集(garbagecollection)n最彻底的失败处理策略是无用单元收集。所谓最彻底的失败处理策略是无用单元收集。所谓无用单

106、元是指那些可以回收而没有回收的结点无用单元是指那些可以回收而没有回收的结点空间。空间。 n高级程序设计语言中，程序员常犯的一种错误高级程序设计语言中，程序员常犯的一种错误就是动态生成变量或对象并使用它们之后，忘就是动态生成变量或对象并使用它们之后，忘记了释放其内存空间，以后却又不再使用它们。记了释放其内存空间，以后却又不再使用它们。也可能是由于程序要做到及时释放无用单元有也可能是由于程序要做到及时释放无用单元有困难。困难。 n这种丢失的存储空间称为无用单元这种丢失的存储空间称为无用单元(garbage)，也称为内存泄漏，也称为内存泄漏(memoryleak) 孺伏反肤鲍醚幸碾颗葬捌护付冶咖射送

107、巍了构爪科拿践泛书拷壮庐嘻剑柠第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 回收无用结点回收无用结点n这些无用结点的存在会影响空间使用的效率。这些无用结点的存在会影响空间使用的效率。因此存储管理系统要有能力把这些无用结点找因此存储管理系统要有能力把这些无用结点找出来，并送回到可利用空间表中去。出来，并送回到可利用空间表中去。n通常的作法是：首先普查一次内存，把那些已通常的作法是：首先普查一次内存，把那些已经不属于任何链上的结点打上标志，然后将它经不属于任何链上的结点打上标志，然后将它们收集到可利用空间表中，回收

108、过程通常还可们收集到可利用空间表中，回收过程通常还可与存储压缩一起进行。与存储压缩一起进行。瞄蚜蜗均掇所绑棚增撰莉脚谜萍撕喳魄枣劈封凿蠕铅纷腮采蹦期了掖咋后第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 无用单元收集的算法无用单元收集的算法 n首先介绍引用计数首先介绍引用计数(referencecount)算法。算法。n系统为每一个动态分配的存储块加入一个计数系统为每一个动态分配的存储块加入一个计数字段。当一个新指针指向该存储块时，存储块字段。当一个新指针指向该存储块时，存储块的引用计数就会加的引用计数就会加1；

109、当某指针不再指向这个；当某指针不再指向这个块时，其引用计数就会减块时，其引用计数就会减1。n一旦存储块的引用计数变为一旦存储块的引用计数变为0，这个存储块成，这个存储块成为无用单元，立即放回到可利用空间表中。为无用单元，立即放回到可利用空间表中。玩口蛛圾突糕痕仙军绥肝员揖哗袋婉骆醉守阮色嚏恶卷噬腰啃使写娃么戌第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 引用计数算法的优缺点引用计数算法的优缺点 n优点：不需要一个明显的无用单元收集阶段，优点：不需要一个明显的无用单元收集阶段，每当存储单元成为无用单元就立即把它放

110、到可每当存储单元成为无用单元就立即把它放到可利用空间表中。利用空间表中。n缺点：首先，必须为每一个存储对象维护一个缺点：首先，必须为每一个存储对象维护一个引用计数。如果有很多较小的对象，系统的额引用计数。如果有很多较小的对象，系统的额外负担太多。当存在无用单元循环引用时，就外负担太多。当存在无用单元循环引用时，就会出现另一个严重问题：每个存储对象都被指会出现另一个严重问题：每个存储对象都被指向一次，但是对象集合仍然是无用单元，因为向一次，但是对象集合仍然是无用单元，因为没有指针指向对象集合。没有指针指向对象集合。帕寡慎伍抉传习啊瘴玲甸铭充蓖邀绞机割绅舵失妊涝棉锋挞袭辱液柳蛹掌第十一章高级线性表

111、第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 标记标记/清除清除(mark/sweep)方法方法 标记标记/清除算法的实质就是周游广义表。清除算法的实质就是周游广义表。n在在这这种种方方法法中中，每每一一个个存存储储对对象象只只需需要要一一个个简简单单的的标标记记位位。一一旦旦可可利利用用空空间间表表用用完完，存存储储管管理器就会进入一个独立的无用单元收集阶段。理器就会进入一个独立的无用单元收集阶段。n首首先先清清除除所所有有的的标标记记位位，然然后后从从变变量量表表中中的的每每一一个个变变量量开开始始，沿沿着着指指针针进进行行

112、深深度度优优先先搜搜索索。每每遇遇到到一一个个存存储储单单元元，就就设设置置其其标标记记位位为为“已已访问访问”。n最最后后访访问问所所有有存存储储单单元元，对对存存储储区区域域进进行行清清理理所所有有未未标标记记的的单单元元就就认认为为是是无无用用单单元元，可可以释放到可利用空间表中。以释放到可利用空间表中。胚蓄毡惊坚唉尔乓古邯壕石教致婪夷档租娃蹋矩泰嫡酋亡宋帮档斑梦涪抬第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 标记标记/清除方法的优缺点清除方法的优缺点n标标记记/清清除除方方法法的的优优点点是是它它比比

113、引引用用计计数数方方法法需需要要的空间少，而且对于循环情况也能工作。的空间少，而且对于循环情况也能工作。n但但它它隐隐藏藏了了一一个个很很大大的的缺缺陷陷，这这就就是是进进行行处处理理所所需需要要的的空空间间需需求求。周周游游广广义义表表的的算算法法实实质质上上是是一一个个递递归归算算法法，在在这这种种情情况况下下编编译译器器的的运运行行系系统统维维护护一一个个栈栈；要要么么存存储储管管理理器器维维护护它它自自己己的的栈栈。而而无无用用单单元元收收集集算算法法往往往往是是在在内内存存空空间间很很紧紧张张时时进进行行的的，必必须须尽尽可可能能地地采采用用最最少少的的空空间代价。间代价。衍赠猪献烁

114、踢茸标咬上泼揪抽艇返新榆合赊睁传虚刺壬摄僧看奶嘿掖冲劳第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page Deutsch-Schorr-Waite无用单元收集算法无用单元收集算法nDeutsch-Schorr-Waite无用单元收集算法采用无用单元收集算法采用逆转链的广义表周游算法，而不需要额外的用逆转链的广义表周游算法，而不需要额外的用于栈的空间。于栈的空间。n在周游中每深入一步，不需要向栈中存储一个在周游中每深入一步，不需要向栈中存储一个指针，而是借用即将深入的那个指针，把它逆指针，而是借用即将深入的那个指针，把

115、它逆转设置为指向前一步刚经过的结点转设置为指向前一步刚经过的结点 撩吸加荡典可曝港督镣沁轴搓弗箱涯炭芥塑椽迫斑楔余糠标圾雨卡矣缉廊第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 暂时借用外存空间暂时借用外存空间n可可以以将将正正在在使使用用的的单单元元复复制制到到临临时时外存数据块中外存数据块中n需要注意更新相应的指针和引用信息需要注意更新相应的指针和引用信息n新新腾腾出出的的内内存存可可以以被被操操作作系系统统用用于于标记标记/清除算法需要的临时空间清除算法需要的临时空间适合于虚拟存储计算机系统适合于虚拟存储计

116、算机系统隔廉玫酬源椅下埃斜扶橱孕隔店攀磁姥茅淆瞥询蛾艘叼拦枣举平著再步雇第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page Deutsch-Schorr-Waite无用单元收集算法无用单元收集算法n算法的关键是设置两个标志位算法的关键是设置两个标志位mark和和tag。nmark初值为初值为“UNVISITED”(即即“0”)，执行标，执行标志算法后，将全部有用结点的志算法后，将全部有用结点的mark字段置为字段置为“VISITED”（已访问）。（已访问）。tag初值也为初值也为0，在标，在标志算法执行过程中，周游到

117、本结点所对应的子志算法执行过程中，周游到本结点所对应的子表时，被置成表时，被置成“1”，返回以后再恢复成，返回以后再恢复成“0”。n前进时不仅指针的值要求非空，同时还要求指前进时不仅指针的值要求非空，同时还要求指针所指的结点针所指的结点mark字段为字段为“UNVISITED”（未（未访问），后退时则只要求指针为空或者指针所访问），后退时则只要求指针为空或者指针所指的结点指的结点mark字段为字段为“VISITED” 印谭禾找房园式窑佑烧甩酬猎节现衔柏享具励佳屈变旦割书榴皖曾箱纯蛙第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印

118、必究 Page 湃掸磨识翠拱锚武拦窥裕卑饮由毅旋晰邻铅前度射茸巾阀获针绦奎冈斗救第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page Deutsch-Schorr-Waite算法的主要缺点算法的主要缺点nDeutsch-Schorr-Waite算算法法的的主主要要缺缺点点是是在在执执行行过过程程中中要要修修改改表表中中指指针针的的值值，所所以以不不能能再再入入运运行行。在在执执行行完完无无用用单单元元的的收收集集算算法法以以后后，只只要要扫扫描描一一遍遍内内存存，将将所所有有mark字字段段为为“UNVISITED”（未未访访问问）的结点送入可利用空间表中。）的结点送入可利用空间表中。庸恳十得硕邢揪坪权闺利昌郭官眩蚌捕蚜奉钉狰垛状郸砾炸子傍钙讳栽霓第十一章高级线性表第十一章高级线性表北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page