对于"边界标识法"的一个疑问，感觉foot节点是多余的
严蔚敏的<<数据结构>>第8.3是将边界标识法，(boundary tag method)，我没搞清楚foot节点到底有什么作用:既然可分配空间是用双向链表标识的，我们都知道双向聊表可以双向访问，那么当前结点通过llink访问前驱节点，通过rlink访问后继节点，就完全可以了。
那么foot节点存在的意义是什么? 我认为不是必须存在的，因为要求下一个节点的位置，直接llink或者rlink跳转就可以了，为什么还要foot呢?
还请指教!
回复 1# cdsfiui
确实不是必须的，从图上看，只是为了方便找到空闲块的头。BTW，Glibc malloc 用的就是 boundary tag method，可以找出来参考下。 回复 2# MMMIX
要找到空闲块的头，用llink/rlink查找前驱/后继节点就可以了啊，为什么用这个foot能方便查找呢?
谢谢。 本帖最后由 MMMIX 于 2016-07-09 15:24 编辑
cdsfiui 发表于 2016-07-09 14:06 static/image/common/back.gif
回复 2# MMMIX
要找到空闲块的头，用llink/rlink查找前驱/后继节点就可以了啊，为什么用这个foot能方便查找呢?
你要是只有一个空闲块的结尾地址呢？没有它的大小，你怎么找到该块的开头？ 例如说在释放一个块的时候，若是要检查是否要和前面的块合并，这时候有 foot 就很方便了，不然的话你还得在空闲列表中搜索一遍。 回复 4# MMMIX
看是否要和前面的块合并，我通过llink找到前面块的head，看它的tag就行了。并不需要重新查找一遍空闲块列表吧?
还是没有太跟上你的节奏，可否继续解释一下? cdsfiui 发表于 2016-07-09 22:58 static/image/common/back.gif
回复 4# MMMIX
看是否要和前面的块合并，我通过llink找到前面块的head，看它的tag就行了。并不需要重新查找一遍空闲块列表吧?
我说的前面的块，是在内存（地址）中和当前块挨着的块，不是链表中的前面的块。
页:
[1]