娱乐 每 日 算 法 挑 战 【第8期】

[yhz012]

是咱最不擅长的操作系统

最坏情况下做成有序链表然后暴力查找是能做的……不过感觉这个效率会比较低

做成平衡树结构似乎会好一点吧……？

[yhz012]

22 分钟前, Mr.K 018 说道:

对付这个题有不少数据结构都能用，平衡树啊，B树啊，B+树啥的都能用

其实实际上我们需要的操作只有

find(x)，找到元素x

findPrev(x)，找到离x最近且不大于x的元素

findNext(x)，找到离x最近且不小于x的元素

add(x)，加入元素x并保持有序

delete(x)，删除元素x并保持有序

这样mallo B L实际上就是findPrev(B) 然后检查B是否在范围内，findNext(B) 然后检查B+L是否在范围内，如果都安全，就add(B)

access p 实际上就是findPrev(p) 然后检查p是否在范围内

free p 实际上就是find(p)，然后安全的话就delelte(p)

list 遍历一遍就好了

剩下的无非就是尽可能让这些操作效率更高就好了

[yhz012]

15 小时前, Mr.K 018 说道:

是的，基本上就是这样

不过在free那里有一个空区域合并的细节

啊……咱的想法是没分配的直接就不保留信息了，所以空区域的长度是取决于后面一个分配的区域的基址的，当然如果后面没有分配的区域了，就直接用2^32带走就好了