内存管理是所有操作系统必备的功能。为深入研究内存管理功能、实现内存的有效使用,某研究小组计划开发一个实验性内存管理器,实现对内存的分配、释放和整理。对应的接口为 new 、 delete 和 defrag ,使用语法为:
new size :分配 size 字节大小的内存块,返回该内存块的句柄 handle , size 为正整数;
new start size :同 new size ,从指定首地址 start 处分配 size 字节大小的内存块;
delete handle :释放句柄 handle 指向的内存块;
defrag :整理内存碎片,将所有已分配内存块按地址从低到高的顺序迁移,使空闲内存碎片在高地址端拼接在一起;
初始内存为 initSize 字节大小的整片空闲内存,编号为 1 到 initSize 。
new size 操作中,若存在不小于 size 的连续空闲内存,则按照小地址优先的原则从空闲内存区域中分配 size 大小的内存块,标记该内存块状态为已分配,并返回指向该内存块的句柄。若无法分配,则返回 NULL 。
new start size 操作与 new size 类似,但分配的起始位置由 start 指定。
delete handle 操作释放由 handle 标记的内存块,标记被释放的内存状态为空闲。若 handle 为无效句柄,则返回 ILLEGAL_OPERATION 。
defrag 完成内存整理工作,无返回值。
根据设计,每次成功内存分配返回的句柄为一个正整数,从 1 开始,依次计数。失败的存储分配操作不影响计数。
请帮助编写上述内存管理程序,并输出 new 操作的返回值。对于操作失败的 delete 操作,请输出 ILLEGAL_OPERATION 。本程序编写不限制函数使用。
输入
输入数据的第一行为两个正整数 T 和 MaxMem ( 1<=T<=10000, 1<=MaxMem<=10000 ),其中 T 为开展的内存操作数, MaxMem 为初始内存大小(单位为字节)。
其后有 T 行操作指令,如题面所述。
输出
按操作顺序输出操作结果。对每个成 new 操作,将其返回句柄值单独输出一行,失败输出 NULL 。若 delete 操作失败,输出 ILLEGAL_OPERATION 。
样例输入
25 1000
new 73
new 74
new 814 55
delete 1
new 989 10
delete -22233
new 76
defrag
new 93
new 20
new 43
defrag
new 989 10
delete 5
delete -1
new 989 110
defrag
new 50
new 1001
defrag
new 220
new 43 85
defrag
delete 10
new 49
样例输出
1
2
3
4
ILLEGAL_OPERATION
5
6
7
8
9
ILLEGAL_OPERATION
NULL
10
NULL
11
NULL
12
可以用Java写也可以用c/c++
我是用java写的,但是只能通过上面的测试用例,还有两个用例是保密的,我也不知的是什么样的输入和输出。求帮忙
我的代码:
import java.util.LinkedList;
import java.util.Scanner;
public class Main {
private static int[] mm;
private static int count;
private static LinkedList<Node> part;//空闲分区表
private static LinkedList<Node> reqd;//已分配的内存
private static int maxMem;
private static class Node {
int start;
int end;
int size;
int idx;
public Node() {
}
public Node(int start, int end, int size, int idx) {
this.end = end;
this.size = size;
this.start = start;
this.idx = idx;
}
public Node clon() {
return new Node(this.start, this.end, this.size, this.idx);
}
}
//请求指定大小内存,返回一个句柄
private static int mm_require(int size) {
if (size <= 0)
return -1;
for (Node p : part) {
if (p.size >= size) {
p.size -= size;
Node r = new Node();
r.start = p.start;
r.end = p.start + size - 1;
r.size = size;
r.idx = ++count;
reqd.add(r);
if (p.size == 0) {
part.remove(p);
} else {
p.start += size;
}
return r.idx;
}
}
return -1;
}
//从某一位置开始分配请求大小的内存
private static int mm_require(int start, int size) {
int id = 0;
if (start < 0 || size <= 0)
return -1;
for (Node p : part) {
if (p.start <= start && start + size - 1 <= p.end) {
Node r = new Node();
r.start = start;
r.end = start + size - 1;
r.size = size;
r.idx = ++count;
reqd.add(r);
if (p.start == start) {
p.size -= size;
if (p.size == 0) {
part.remove(p);
} else {
p.start += size;
}
} else {
int tend = p.end;
p.end = start - 1;
p.size = p.end - p.start + 1;
if (start + size - 1 != p.end) {
Node temp = new Node();
temp.start = start + size;
temp.end = tend;
temp.size = temp.end - temp.start + 1;
part.add(id + 1, temp);
}
}
return r.idx;
}
id++;
}
return -1;
}
//释放句柄指向的内存空间
private static boolean mm_release(int handle) {
for (Node r : reqd) {
if (r.idx == handle) {
reqd.remove(r);
for (int i = 0; i < part.size(); i++) {
Node p = part.get(i);
if (p.end + 1 == r.start) {
p.end = r.end;
p.size = p.end - p.start + 1;
initpart();
return true;
} else if (r.end + 1 == p.start) {
p.start = r.start;
// defrag();
return true;
}
}
Node temp = new Node();
temp.start = r.start;
temp.end = r.end;
temp.size = r.size;
for (int j = 0; j < part.size(); j++) {
if (temp.start < part.get(j).start) {
part.add(j, temp);
break;
}
}
return true;
}
}
return false;
}
//碎片整理
private static void defrag() {
Node temp = new Node();
for (Node p : part) {
temp.size += p.size;
}
temp.end = maxMem - 1;
temp.start = maxMem - temp.size;
part.clear();
part.add(temp);
LinkedList<Node> newreq = new LinkedList<Node>();
for (int i = 1; i < reqd.size(); i++) {
for (int j = i + 1; j <= reqd.size(); j++) {
Node temp1 = reqd.get(i - 1);
Node temp2 = reqd.get(j - 1);
if (temp1.start > temp2.start) {
Node clon = temp1.clon();
temp1.idx = temp2.idx;
temp1.end = temp2.end;
temp1.size = temp2.size;
temp1.start = temp2.start;
temp2.idx = clon.idx;
temp2.end = clon.end;
temp2.size = clon.size;
temp2.start = clon.start;
}
}
}
Node firstr = new Node();
firstr.start = 0;
for (Node p : reqd) {
Node t = new Node();
t.start = firstr.start;
t.end = firstr.start + p.size - 1;
t.size = p.size;
t.idx = p.idx;
newreq.add(t);
firstr.start += p.size;
}
reqd = newreq;
}
private static void initpart() {
for (int j = 0; j < part.size() - 1; j++) {
Node temp1 = part.get(j);
Node temp2 = part.get(j + 1);
if (temp1.end + 1 == temp2.start) {
part.remove(temp2);
temp1.end = temp2.end;
}
}
}
private static void init() {
part = new LinkedList<Node>();
reqd = new LinkedList<Node>();
Node first = new Node();
first.start = 0;
first.end = maxMem - 1;
first.size = maxMem;
first.idx = 0;
part.add(first);
count = 0;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
int t = in.nextInt();
maxMem = in.nextInt();
mm = new int[maxMem];
init();
while (t > 0) {
String instruct = in.nextLine();
if (!instruct.equals("")) {
int n1 = instruct.indexOf(" ");
if (n1 != -1) {
String op = instruct.substring(0, n1);
if ("new".equals(op)) {
int n2 = instruct.indexOf(" ", n1 + 1);
if (n2 != -1) {
int start = Integer.valueOf(instruct.substring(
n1 + 1, n2));
int size = Integer.valueOf(instruct
.substring(n2 + 1));
int handle = mm_require(start, size);
if (handle != -1)
System.out.println(handle);
else
System.out.println("NULL");
} else {
int size = Integer.valueOf(instruct
.substring(n1 + 1));
int handle = mm_require(size);
if (handle != -1)
System.out.println(handle);
else
System.out.println("NULL");
}
} else if ("delete".equals(op)) {
int handle = Integer
.valueOf(instruct.substring(n1 + 1));
if (!mm_release(handle)) {
System.out.println("ILLEGAL_OPERATION");
}
}
} else {
defrag();
}
t--;
}
}
}
}