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

[随性而为]

我还是更倾向于用数组的

struct a{

    int data;

    int used;

    int start

}

struct a[2^32]，一开始a.used都为0，表示未分配

malloc B L时先查找a到a[B+L],如果有一个used为1则不成功,否则a到a[B+L]中used都为1，start都为B,返回B，如果需要记录什么数据就a[B+i]=?;

access p就是先看a[p].used,再判断是否读a[p].data;

free p就是看a[p].start是否为p,如果是的话就把之后start为p的重置了；

list就是int start,count把整个数组遍历一遍综合看a[p].used和a[p].start，每次走完一段就输出start和count，然后刷新这两个变量

（还没学操作系统，基本上就这样？可能有些地方理解错误了，望指出，动脑是不可能动的，这辈子都不可能的）

 

四月 17, 2020，由随性而为修改

[随性而为]

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

这个程序，嗯怎么说呢

你没发现你记这个东西所需要的内存空间比32位程序的地址空间还大么

这我倒没想到，既然这样就去下载64位程序啊

 

四月 17, 2020，由随性而为修改

[随性而为]

用二叉树的思路：

struct{

  int max，min/*代表这一段地址的开始和结束*/，*p/*可以用p=new int[max-min]来存储这一段地址中的数据*/；

  struct btree *lchild，*rchild，*parent；

  int base/*判断是否是最底层，每当创造新结点就令该结点的base为1，令其父结点base变0*/

}btree

基本的结构：结点A表示的地址段和其左右结点的地址段的大小关系为  左子树地址段<父节点地址段<右子树地址段

malloc B L：struct *temp1，将B从根节点开始逐层比较，在这个过程中如果出现（结点A.min<B<结点A.max）则表示需要分配的地址重复，函数执行失败，否则，若A.min>B则temp=A.lchild,若A.max<B则temp=A.rchild，直到最底层，同理struct *temp1对B+L也如此操作，若temp==temp1表明他们在同一个未被分配的地址区间，创造一个结点New和已有的树建立联系,,New.min=B,New.max=B+L,同时New.p=new int[New.max-New.min]，若temp!=temp1，说明max和min之间夹杂着已被分配的空间，函数执行失败.

access p:没什么好说的……，就是逐层判断，看p在那个结点的max和min之间，然后访问那个结点的数组，如果找不到对应的max和min，说明未被分配，函数失败

free p：如果p必须是一开始分配时的基地址时，则逐层和min比较，找到了，则将该结点右子树数据复制给该结点，然后释放该结点的右子树（这样做不会改变基本的结构），如果p没什么严格要求的话，就逐层判断p是否在min，max之间，找到了，则该结点的max=p。如果以上两种情况都i没有找到，则函数执行失败

list ：如果是这个结构的话好像就是树的中序遍历？当然要是也要显示free的起始和长度的话可以在btree结构体中加一个变量，但这样对这个变量操作有点烦，不如创一个数组记录每段的min和max，排序一下再遍历输出