帐号 密码  
 
多路树查找-外部查找(B树)【源代码】

多路树查找-外部查找(B树)【下载及演示说明】

双向链表演示程序【下载及演示说明】

循环链表演示程序【下载及演示说明】

链表【讲解】

动态存储分配之边界标识法演示程序【下载及演示说明】

动态存储分配之边界标识法【讲解】

首次适应算法和最佳适应算法【讲解】

动态存储分配之边界标识法【源代码】

振荡排序算法【讲解】

振荡排序演示程序【下载及演示说明】

树和二叉树相互转化【讲解】

深度优先搜索【下载及演示说明】

深度优先搜索【源代码】

朴素字符串匹配演示程序【下载及演示说明】

当前1/4页
首页 上一页 下一页 尾页

算法讲堂

    本栏目所有文章由本站组织业内技术专家原创而成,用汇编语言向学习者讲解经典问题的编程思想和编程方法。

    本栏目所有文章的版权归本站所有,转载请注明出处为汇编网<www.asmedu.net> 。

    现本栏目的内容处于不断添加中,请随时关注。
算法讲堂-》动态存储分配之边界标识法【讲解】
    1.概述
边界标识法是动态存储分配的一种算法。它的特点就是,在内存块的头部和底部分别设上标识。这样,在回收内存块的时候,更容易判断物理位置上,在它前面和后面的内存块的空闲占用情况,以便合并成一个尽可能大的内存块。
2.内存块的结构
每个内存块的头部四个字和底部两个字记录内存块的信息。
头部四个字的信息包括:前驱内存块的地址(*llink),内存块空闲占用标志(tag),内存块的大小(size),后继内存块的地址(*rlink)
底部两个字的信息包括:本内存块的地址(*uplink),内存块空闲占用标志(tag)
在头部和底部之间的空间为供用户使用的空间。所有的空闲内存块链接起来形成双重循环链表结构。
内存块的结构如下图所示:
 图
3.分配算法
找到一个空闲的内存块,作为起始搜索内存块,搜索算法我们可以采用首次拟合法和最佳拟合法。下面我们针对首次拟合的分配算法进行一下介绍。
我们设申请空间的大小为size_n,搜索内存块的指针为pointer_pav。首先获取当前内存块头部信息中内存块的大小size,如果内存块的大小size大于或者等于申请空间的大小size_n,则将此内存块的一部分或整个分配给用户。如果内存块的大小size小于申请空间的大小size_n,则将搜索内存块的指针pointer_pav指向下一个空闲的内存块。继续比较,直到找到或搜索完所有的空闲内存块为止。
为了避免产生无法使用的内存碎片,我们定义一个常量size_e。如果分配给用户后内存块剩余空间的大小小于常量size_e,则将整个内存块全部分配给用户。否则,只分配申请空间的大小。
另外,如果搜索指针的位置固定从某一个内存块开始,势必产生内存分布不均,一些地方密集,而一些地方稀疏。为了解决这个问题,我们将搜索指针指向每次释放后的内存块。
时间复杂度的讨论:
该算法的时间主要花费在查找第一个满足条件的内存块(简称命中块)上。而查找时间的长短又由链表的长度和命中块在链表中的位置决定。设链表的长度为n,命中块在链表中的位置为i:
当i=0时,其时间复杂度为O(1) ,这是最好情况
当i=n-1时,其时间复杂度为O(n) , 这是最差情况
因为命中块的位置是任意的,所以我们分析一下平均时间复杂度。
我们假设每一个内存块满足条件的概率是均等的,都为1/n,那么n的值越大花费的时间越长。因此查找算法的平均时间复杂度为O(n)。
4.回收算法
回收算法是将用户不用的内存块回收,以便再次分配。
根据内存块物理上左右邻区的空闲占用情况分为四种情况:
左右邻区都为空闲的情况;
左右邻区都为占用的情况;
左邻区为空闲,右邻区为占用的情况;
左邻区为占用,右邻区为空闲的情况。
每一种情况对应一种回收算法。下面对每一种回收算法分别进行一下介绍:
第一种:左右邻区都为空闲的情况
为了让三个空闲块合并成一个空闲块,可以修改左邻块的空间大小,然后,将右邻块从链表中删除,再修改合并后内存块的底部信息。
第二种:左右邻区都为占用的情况
这种情况比较简单,只要将释放块插入到空闲块链表中即可。因为链表是无序的,所以插入位置是任意的。
第三种:左邻区为空闲,右邻区为占用的情况
修改左邻块的空间大小,然后修改底部信息,将此释放块和左邻块合并成一个内存块。
第四种:左邻区为占用,右邻区为空闲的请况
修改释放块的头部信息,然后修改释放块的底部信息。
时间复杂度的讨论:
    由于在每个内存块的头部和底部都设立标识,所以不需要进行查找来找到与它毗邻的空闲块进行合并;其次,链表中内存块的位置是无序的,所以不需要查找链表进行插入。总之,不管哪种情况释放算法的时间复杂度都为常量。

[07/10/25]

Copyright C 2006-2024 ASMEDU.NET All Rights Reserved
Email: asmedu@163.com