《第十一章高级线性表.ppt》由会员分享，可在线阅读，更多相关《第十一章高级线性表.ppt（108页珍藏版）》请在三一文库上搜索。
1、第十一章 高级线性表,任课教员：张 铭 http:/ 北京大学信息科学与技术学院 网络与信息系统研究所 版权所有，转载或翻印必究,北京大学信息学院 版权所有，转载或翻印必究 Page 2,主要内容,11.1 多维数组 11.2 广义表 11.3 存储管理技术,北京大学信息学院 版权所有，转载或翻印必究 Page 3,11.1 多维数组,数组（Array）是数量和元素类型固定的有序序列 静态数组必须在定义它的时候指定其大小和类型 动态数组可以在程序运行才分配内存空间 多维数组（Multi-array）是向量的扩充 向量的向量就组成了多维数组 可以表示为： ELEM Ac1d1c2d2cndn
2、ci和di是各维下标的下界和上界。所以其元素个数为：,北京大学信息学院 版权所有，转载或翻印必究 Page 4,数组的空间结构,左边是二维数组的空间结构，右边是三维数组的空间结构，d113,d215,d315分别为3个维。,北京大学信息学院 版权所有，转载或翻印必究 Page 5,数组的存储,内存是一维的，所以数组的存储也只能是一维的 以行为主序（也称为“行优先”） 以列为主序（也称为“列优先”） 一个3 3的数组X的行优先表示： 内存中的存放是：1，2，3，4，5，6，7，8，9,北京大学信息学院 版权所有，转载或翻印必究 Page 6,数组的存储（续）,一个二维m n数组中元素Xij（第i
3、行第j列元素）的内存地址可以这样来计算： X00（数组首地址）+（ni+j） 元素的长度（如C+中int型为4字节） 例如，我们已知一个数组的A00元素在内存的644的位置，假设元素的长度为8，那么我们就可以求得其他任意元素Axy的位置，为644+len(nx + y)。 例如，n = m = 3，由上面公式得到A23元素的地址：644 + 8（32+2）= 708,北京大学信息学院 版权所有，转载或翻印必究 Page 7,Pascal语言的存储实现是按行优先处理的，先排最右的下标，从右向左，最后最左的下标。 例如对于三维数组a1k,1m,1n的元素axyz可以如下排列：,北京大学信息学院 版
4、权所有，转载或翻印必究 Page 8,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,北京大学信息学院 版权所有，转载或翻印必究 Page 9,FORTRAN语言采用列优先存储。先排最左的下标，从左向右，最后最右的下标。 例如对于三维数组a1k, 1m, 1
5、n的元素axyz可以如下排列：,北京大学信息学院 版权所有，转载或翻印必究 Page 10,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,北京大学信息学院 版权所有，转载或翻印必究 Page 11,行优先存储公式,设数组元素占d个存储单元, 3维矩阵行优
6、先存储公式为：,北京大学信息学院 版权所有，转载或翻印必究 Page 12,n维矩阵行优先存储公式为：,北京大学信息学院 版权所有，转载或翻印必究 Page 13,C+多维数组ELEM Ad1 d2dn;,北京大学信息学院 版权所有，转载或翻印必究 Page 14,数组的声明,在编译的时候如果已经知道数组每一维的大小： 声明一个10 10的整型数组：int num1010; 只知道数组一个维的大小，那么也可以动态地创建一个二维数组。例如我们只要一个组有10个整数，但是不知道有多少个组：int (*num)10; 最后在程序运行的时候，可以计算出或者由用户指定它的第一个维数是n： num= ne
7、w intn10;,北京大学信息学院 版权所有，转载或翻印必究 Page 15,数组的声明:动态的声明,int *X; int row=3; int col=3; try /创建行指针，即指向整型的指针 X= new int*row; /然后再为每一行分配地址 for(int i=0; irow;i+) Xi=new intcol; catch(xalloc),北京大学信息学院 版权所有，转载或翻印必究 Page 16,数组的声明:动态的声明,这里要注意的是，内存被分配出去也必须加以回收，否则会造成内存泄漏（memory leak） for(int i=0;irow;i+) delete Xi
8、; delete X; 对于3维或者更高维的数组，过程是类似的,北京大学信息学院 版权所有，转载或翻印必究 Page 17,用数组表示特殊矩阵,二维数组可以被看作是矩阵，所以它也经常被用来表示矩阵 三角矩阵可以被分为上三角矩阵和下三角矩阵，它是指n阶矩阵中的下(上)三角的元素都是0或者一个常数 在上三角矩阵中，当数组的下标ij时，数组元素aij=c； 而在下三角矩阵中，当下标i=j）,北京大学信息学院 版权所有，转载或翻印必究 Page 18,下三角矩阵图例,北京大学信息学院 版权所有，转载或翻印必究 Page 19,用数组表示特殊矩阵（续）,对称矩阵指的是一个n阶矩阵，它的元素满足性质ai,
9、j=aj,i，0=（i, j）n。在用数组存储的时候，元素aij=aji,北京大学信息学院 版权所有，转载或翻印必究 Page 20,为了节省空间，存储其下三角的值，而对角线之上的值通过对称关系映射过去。 以一维数组sa0n(n+1)/2作为n阶对称矩阵A的存储结构，则sak和矩阵元ai,j之间存在着一一对应的关系 ：,北京大学信息学院 版权所有，转载或翻印必究 Page 21,用数组表示特殊矩阵（续）,对角矩阵是指所有的非零元素都集中在主对角线及以它为中心的其他对角线上。如果|i-j|1，那么数组元素aij=0。 下面是一个3对角矩阵：,北京大学信息学院 版权所有，转载或翻印必究 Page
10、22,稀疏矩阵,稀疏矩阵中的非零元素非常少，而且分布也不规律 稀疏因子 用来描述稀疏矩阵的非零元素情况，它定义为在m n的矩阵中，有t个非零元素，则稀疏因子为: 通常当这个值小于0.05时，可以认为是稀疏矩阵 一般使用三元组(i, j, aij )来顺序存储稀疏矩阵，其中i是该元素的行号，j是该元素的列号，aij是该元素的值,北京大学信息学院 版权所有，转载或翻印必究 Page 23,稀疏矩阵的十字链表,十字链表有两组链表组成 行和列的指针序列 链表中的每一个结点都包含两个指针，一个指向它的同一行的下一个元素，一个指向它的同一列的下一个元素,北京大学信息学院 版权所有，转载或翻印必究 Page
11、 24,十字链表的ADT,template class OLNode private: int row,col;/矩阵的行和列 T element;/矩阵中存储的数据 OLNode* right,*down;/指向下一个结点的指针 public: OLNode()right=NULL;down=NULL; ;,北京大学信息学院 版权所有，转载或翻印必究 Page 25,十字链表的建立,建立矩阵的算法如下： 首先为行头结点和列头结点申请空间，大小分别为矩阵的行列数 将三元组根据情况分别加入到链表中 如果三元组中的行列号错误，则退出，否则继续 先处理行链表的问题 如果该行头结点为空，则建立一个新的
12、头结点，内容为该三元组 如果不为空则从头结点开始查找，找到该三元祖的正确位置如果该位置已经存在数据，则修改之，否则生成相应的结点插入进去 类似地处理列链表头,北京大学信息学院 版权所有，转载或翻印必究 Page 26,矩阵乘法,=,北京大学信息学院 版权所有，转载或翻印必究 Page 27,经典矩阵乘法,Ac1d1 c3d3，Bc3d3 c2d2, Cc1d1c2d2。 d3 CAB (CijAik 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 + Ai,k
13、*Bk,j; Ci，j = sum; ,北京大学信息学院 版权所有，转载或翻印必究 Page 28,p=d1-c1+1，m=d3-c3+1，n=d2-c2+1； A为pm的矩阵，B为mn的矩阵，乘得的结果C为pn的矩阵 经典矩阵乘法所需要的时间代价为O(pmn),北京大学信息学院 版权所有，转载或翻印必究 Page 29,稀疏矩阵乘法,template SMatrix*SMatrix:MatrixMutil(SMatrix*left,SMatrix*right) if(left-GetColnum()!=right-GetRownum() return NULL;/行列不匹配不能相乘 int
14、I=0; /第一个矩阵的行数 int J=0; /第二个矩阵的列数 SMatrix *ResultMatrix=new SMatrix();/结果矩阵 ResultMatrix-MallocMem(left-GetRownum(),right-GetColnum();/为结果矩阵分配空间 for(I=1;IGetRownum();I+) /开始相乘 OLNode* RowNext=ResultMatrix-rowheadI;,北京大学信息学院 版权所有，转载或翻印必究 Page 30,for(J=1;JGetColnum();J+) /扫描所有的列 OLNode* ColNext=Result
15、Matrix-colheadJ; int result=0; OLNode * rows=left-rowheadI; OLNode* cols=right-colheadJ; if(rows=NULL)|(cols=NULL) break;/新行没有非零元素 while(rows!=NULL) ,北京大学信息学院 版权所有，转载或翻印必究 Page 31,else /都有元素可以相乘 result=result+cols-element*rows-element; cols=cols-down; rows=rows-right; if(result=0) continue; /插入到结果矩阵
16、中 OLNode* temp=new OLNode(); temp-row=I; temp-col=J; temp-element=result; if(RowNext=NULL)/加入行向量中 /每行第一个元素 ResultMatrix-rowheadI=temp; RowNext=ResultMatrix-rowheadI; else /加入一个新的元素到下一个位置 RowNext-right=temp; RowNext=RowNext-right; ,北京大学信息学院 版权所有，转载或翻印必究 Page 32,if(ColNext=NULL)/加入到列向量 /列结点第一次使用，加入新的结
17、点 ResultMatrix-colheadJ=temp; ColNext=ResultMatrix-colheadJ; else /调转到合适的位置，插入 while(ColNext-down!=NULL) ColNext=ColNext-down; ColNext-down=temp; ColNext=ColNext-down; /完成放入ResultMatrix /乘法做完，返回新的矩阵 return ResultMatrix; ,北京大学信息学院 版权所有，转载或翻印必究 Page 33,稀疏矩阵乘法时间代价,若矩阵A中行向量的非零元素个数最多为ta 矩阵B中列向量的非零元素个数最多为
18、tb 矩阵C中列向量的非零元素个数最多为tc 假设C矩阵中非0元素的个数总和为Nc,北京大学信息学院 版权所有，转载或翻印必究 Page 34,每计算一个 cij的时间 主要用于顺着行I和列J寻找的过程 其循环次数最多为ta+tb 每次循环所花时间是一个常量，记为k 计算一个cij的时间为k(ta+tb) 计算全部cij的时向为k(ta+tb)pn。,北京大学信息学院 版权所有，转载或翻印必究 Page 35,生成乘积矩阵的时间 计算出来的结果在行向量里面插入的时间是常数 在列向量上插入需要每次定位到合适的位置， 所花时间为O(tc)，插入操作的总时间为O(Nc tc ) 因此稀疏矩阵乘法的总
19、执行时间上界为 O(ta+tb)pn)+ O(Nc tc ) 如果修改此算法 保留乘积C矩阵的当前列指针向量位置，指向已插入到C中各列最新的非零元素 可使每次插入的时间为一常数 总执行时间降低为O(ta+tb)pn),北京大学信息学院 版权所有，转载或翻印必究 Page 36,11.2 广义表,回顾线性表 由n（n0）个数据元素组成的有限有序序列 线性表的每个元素都具有相同的数据类型，通常为同一某种类型的数据记录 如果一个线性表中还包括一个或者多个子表，那就称之为广义表（Generalized Lists，也称Multi-list）一般记作： L（x0，x1，xi，xn-1）,北京大学信息学院
20、 版权所有，转载或翻印必究 Page 37,L（x0，x1，xi，xn-1） L是广义表的名称 n为长度 每个xi（0in-1）是L的成员 可以是单个元素，即原子（也称“单元素”，atom ) 也可以是一个广义表，即子表（sublist） 广义表的深度：表中元素都化解为原子后的括号层数,北京大学信息学院 版权所有，转载或翻印必究 Page 38,广义表的各种类型,纯表（pure list） 从根结点到任何叶结点只有一条路径 也就是说任何一个元素（原子、子表）只能在广义表中出现一次,北京大学信息学院 版权所有，转载或翻印必究 Page 39,广义表的各种类型（续）,可重入表( reentrant
21、 list ) 图示对应于一个DAG 其元素(包括原子和子表)可能会在表中多次出现 但不会出现回路 对子表和原子标号,北京大学信息学院 版权所有，转载或翻印必究 Page 40,广义表的各种类型（续）,循环表( cyclic list ，递归表)的图示对应于任何有向图 有向图中可能包含回路 循环表的深度为无穷大,北京大学信息学院 版权所有，转载或翻印必究 Page 41,北京大学信息学院 版权所有，转载或翻印必究 Page 42,图递归表再入表纯表(树)线性表 广义表是线性与树型结构的推广,北京大学信息学院 版权所有，转载或翻印必究 Page 43,广义表的存储,使用数组来存储 存储括号 可以
22、使用链表结构存储,北京大学信息学院 版权所有，转载或翻印必究 Page 44,广义表存储ADT,template class GenListNode public: int type; /表示该结点是ATOM或者SubLIST T element; /如果是ATOM，则存储它的值 /如果是LIST ,则指向它的元素的首结点 GenListNode *child; GenListNode *next;/指向下一个结点 / 其他函数 ;,北京大学信息学院 版权所有，转载或翻印必究 Page 45,广义表存储ADT（续）,不带表头的广义表链 在删除结点的时候会出现问题 删除结点data就必须进行链调
23、整,北京大学信息学院 版权所有，转载或翻印必究 Page 46,广义表存储ADT（续）,增加一个头指针来标志，简化删除，插入操作 此外，在访问循环链的时候会出现循环访问，所以需要一个标志位来记录该结点是否已经被访问过 图的因素,北京大学信息学院 版权所有，转载或翻印必究 Page 47,北京大学信息学院 版权所有，转载或翻印必究 Page 48,/改进的广义表结点类型 template class GenListNode public: int type; /表示该结点是ATOM or LIST struct int ref; /如果是表头结点则，存储该结点被引用次数 char* Name;
24、/ 表头名称 int mark; /本子表是否被访问过 headNode; GenListNode *child;/如果是LIST ,则指向子表 T element; /如果是ATOM，则存储它的值 GenListNode *next;/指向下一个结点 void GenListTraversal ();/周游该结点的子孙 void GenListTraversalHelp(GenListNode *node); ;,北京大学信息学院 版权所有，转载或翻印必究 Page 49,/GenList是一个原子元素类型为T的广义表 /如果要实现能够存储多种数据类型的广义 /表，只需要嵌套的使用它 tem
25、plate 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();/取当前结点的前一个 voi
26、d MoveFirst();/当前指针指向head int Remove();/删除当前结点 void ViewList();/周游广义表 ;,北京大学信息学院 版权所有，转载或翻印必究 Page 50,广义表的周游算法,广义表周游的时候应该注意几个问题： 相当于深度优先周游 访问的时候首先进入一个子表的头结点，设置mark标记 按照本层子结点顺序，访问广义表 如果是子表结点，则准备递归地访问此子表表头结点 如果是原子，则直接访问 避免进入循环链中无法跳出 mark用来防止循环访问而设置的访问位 实际上，表头结点才需要mark 广义表访问结束的时候 应该将mark设置为未访问 以便如果其他地方
27、也引用了该链可以正常的访问到,北京大学信息学院 版权所有，转载或翻印必究 Page 51,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“); Lis
28、t4-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();,北京大学信息学院 版权所有，转载或翻印必究 P
29、age 52,template void GenListNode:GenListTraversalHelp(GenListNode *node) GenListNode *p; node-headNode.mark=VISITED; cout next; p!=NULL; p=p-next) /进入一个子表结点，准备递归访问它的表头结点 if (p-type=LIST) ,北京大学信息学院 版权所有，转载或翻印必究 Page 53,template void GenList:ViewList() MoveToFirst(); current-GenListTraversal (); templ
30、ate void GenListNode:GenListTraversal () GenListTraversalHelp(this); ,北京大学信息学院 版权所有，转载或翻印必究 Page 54,11.3 存储管理技术,在C这样的高级程序设计语言中，程序员经常会进行new和delete操作，即动态内存分配。在实际的操作系统中，内存管理本质上是利用链表和广义表来实现的。 本小节将首先介绍可利用空间表的概念，并简单介绍可利用空间表中所有结点长度都相等的情况。 随后将介绍在可利用空间表中处理变长结点的方法,北京大学信息学院 版权所有，转载或翻印必究 Page 55,分配与回收,内存管理最基本的问
31、题是存储的分配与回收 分配存储空间，回收被“释放”的存储空间。在分配和回收过程中，需要解决碎片问题，这就是存储的压缩 可能由于程序员忘记delete已经不再使用的指针等等，而产生了许多无用单元(garbage)，需要对这样的无用单元进行有效的收集，而且收集完往往还需要再进行压缩。,北京大学信息学院 版权所有，转载或翻印必究 Page 56,存储空间溢出的管理,由于主存容量的限制，所以无论采用哪种存储管理技巧，总难免产生内存溢出。 溢出发生后，可以借助外存的帮助，把内存中某些结点（或由这些结点组成的结构）撤离到外存上去，并且提供一定的手段在必要时将这些结点再取回内存。 为了减少内外存数据交换次数
32、，送到外存上去的内容应该选择最近不使用的那些结点,北京大学信息学院 版权所有，转载或翻印必究 Page 57,可利用空间表,为了进行动态存储分配，可以把存储器看成一组变长块数组，其中一些块是空闲的，一些块是已分配的，空闲块链接到一起，形成一个可利用空间表(freelist)。 所谓可利用空间是指存储区中当前还没有使用的空间 对于存储请求，要在可利用空间表中找到足够大的块。如果找不到，那么存储管理器就要求助于失败策略。,北京大学信息学院 版权所有，转载或翻印必究 Page 58,长度固定的存储分配,把可利用空间表组织成链栈(或链式队列)的形式。 在系统运行初期将整个可利用空间划分成固定大小的数据
33、块，而且利用指针字段把这些数据块链接起来，并使用一个指针指向首结点，这样就形成了一个单链表即这个可利用空间表。 以后每执行一次new p操作就从可利用空间中取走一个数据块，并用p指向该数据块；每执行一次delete p操作就把p指向的数据块插入到可利用空间表的链表中。,北京大学信息学院 版权所有，转载或翻印必究 Page 59,北京大学信息学院 版权所有，转载或翻印必究 Page 60,可利用空间表的单链表定义和函数重载,template class LinkNode private: static LinkNode *avail; /可利用空间表头指针 public: Elem value;
34、 /结点值 LinkNode * next; /指向下一结点的指针 LinkNode(const Elem ,北京大学信息学院 版权所有，转载或翻印必究 Page 61,/重载new运算符实现 template void * LinkNode:operator new(size_t) if(avail = NULL) /可利用空间表为空 return :new LinkNode; /利用系统的new分配空间 LinkNode * temp = avail; /否则从可利用空间表中取走一个结点 avail = avail-next; return temp; ,北京大学信息学院 版权所有，转载或
35、翻印必究 Page 62,/重载delete运算符实现 template void LinkNode:operator delete(void * p) (LinkNode *) p)-next = avail; avail = (LinkNode *)p; ,北京大学信息学院 版权所有，转载或翻印必究 Page 63,这种可利用空间表实际上是一个用单链表实现的栈。new代表栈的删除操作，如果avail为空指针，代表已没有可利用空间。delete代表栈的插入操作。 如果程序员需要直接引用系统的new和delete操作符，需要强制用“:new p”和“:delete p”。这种强制在整个程序运行
36、完毕时是十分必要的，可以把avail所占用的空间都交还给系统（真正释放空间）。,北京大学信息学院 版权所有，转载或翻印必究 Page 64,各种类型和长度的可利用空间表,有三种很直观的解决方案： (1) 建立起多个可利用空间表，每个链表可以为某一种长度的变量分配存储空间。 (2) 统一按照较长的结点组织可利用空间表，把变长结点按同样长度进行分配。这在结点长度差别不大时还可以采用，但是在长度差别很大时，就可能造成不可容忍的存储空间浪费。 (3) 多个可利用空间表共享同一个存储空间，事先估计出每个链表中最多可以有多少个结点，并把这些结点都链接起来。但这造成了在空间和时间上的巨大浪费。这样的处理没有
37、解决共享问题，代价很高，管理也不方便。,北京大学信息学院 版权所有，转载或翻印必究 Page 65,不对每个可利用空间表进行预分配，而是随着系统运行而动态分配。 假设有一片从地址L开始的动态存储区域，上界地址为S。这片存储区域由n个链表所共享，每个链表的结点类型都不同。显然，需要为这n个链表建立n个可利用空间表。 系统刚开始运行，所有的可利用空间表的头指针avail都赋为空值。 在系统运行过程中，每当链表的结点被删除时，把被删除结点推入到对应的可利用空间表中储备起来。,动态分配,北京大学信息学院 版权所有，转载或翻印必究 Page 66,动态分配（续）,每当需要向某链表中动态插入结点时，如果对
38、应的可利用空间表非空，则从可利用空间表中删除一个结点的空间给它；如果对应的可利用空间表为空，则从后备存储区中去取一块存储空间。 我们用一个指针pmax来指向动态存储区的后备存储区的起始地址，随着后备存储区的不断消耗，pmax值不断增大。但只要pmax加上待分配结点长度小于等于S，就可以继续进行动态分配。,北京大学信息学院 版权所有，转载或翻印必究 Page 67,北京大学信息学院 版权所有，转载或翻印必究 Page 68,可利用空间表动态存储区的分配算法,void * LinkNode:operator new(size_t) LinkNode * temp; if(avail = NULL)
39、 /可利用空间表为空 return :new LinkNode; /利用系统的new分配空间 if (pmax + K S) coutlink; return temp; ,北京大学信息学院 版权所有，转载或翻印必究 Page 69,算法的缺点,这种方法存在着一些严重的问题：每个可利用空间表的结点大小是固定的，后备存储区里的空间一旦被分配就不能再回到后备存储区中 如果pmax值已经达到或超过S值而不能再分配空间时，实际上系统中别的可利用空间表中可能还存在大量的空闲结点。,北京大学信息学院 版权所有，转载或翻印必究 Page 70,存储的动态分配和回收,把各种大小的结点（又称可利用块）组织在一个
40、可利用空间表中；分配时需要按申请的长度在可利用空间表中进行检索，找到其长度大于等于申请长度的结点，从中截取合适的长度 回收时也不能简单地把删除的结点放回到可利用空间表中，而必须考虑刚刚被删除的结点空间能否与可利用空间表中的某些结点合并，组成较大的结点，以便能满足后来的较大长度结点的分配请求。,北京大学信息学院 版权所有，转载或翻印必究 Page 71,本方法的优缺点,这种处理方法的优点是可以解决存储空间的共享问题 缺点是分配和回收的算法复杂了，并且在系统长期动态运行的过程中，这种方法有可能使整个空间被分割成许多大小不等的碎块，而某些碎块由于太小而长期得不到使用，这就产生所谓碎片问题。,北京大学信息学院 版权所有，转载或翻印必究 Page 72,空闲块的数据结构,空闲块的长度是不定的，所以可利用空间表中每个结点都需要记录本结点的长度。 一种常见的方法是，对于一个需要m字节空间的请求，存储管理器可能会分配稍多于m字节的空间 额外的空间留给存储管理器进行存储管理，例如存放块的标记位、链表指针和块长度。 标记位用来区别这个块是空闲块还是已被分配的块。,北京大学信息学院 版权所有，转载或翻印必究 Page 73,北京大学信息学院