🔥码云GVP开源项目 12k star Uniapp+ElementUI 功能强大 支持多语言、二开方便! 广告
# 一、概念 1.对象的多重数组表示:对一组具有相同域的对象,每一个对象都可以用一个数组来表示 ![](https://box.kancloud.cn/2016-02-02_56b02bd08e4b5.gif) 2.对象的单数组表示:一个对象占据存储中的一组连续位置 ![](https://box.kancloud.cn/2016-02-02_56b02bd09dadc.gif) # 二、代码 ~~~ int Allocate_Object() { if(free == NULL) { cout<<"error:out of space"<<endl; exit(0); } else { int x = free; free = next[x]; return x; } } void Free_Object(int x) { next[x] = free; free = x; } ~~~ # 三、练习 10.3-1 多重数组 key :13, 4, 8, 19, 5, 11 next:1, 2, 3, 4, 5, -1 pre:-1, 0, 1, 2, 3, 4 单数组: 13, 3, -1, 4, 6, 3, 8, 9, 6, 19, 12, 9, 5, 15, 12, 11, 18, 15 10.3-2 ~~~ ALLOCATE-OBJECT() 1 if free = NIL 2 then error "out of space" 3 else x <- free 4 free <- A[x+1] 5 return x FREE-OBJECT(x) 1 A[x+1] <- free 2 free <- x ~~~ 10.3-3 在这里prev域没有 在这里在这里prev域没有意义,用不到 10.3-4 见[算法导论-10.3-4](http://blog.csdn.net/mishifangxiangdefeng/article/details/7707149) 假设当前的数组是紧凑的,即数组中有f个元素,都位于数组的前f个位置 分配一个新的元素时,把f+1的位置分配给它 删除一个元素时,假设待删除的元素的位置是i,先修改元素prev[i]的next指针和元素next[i]的prev指针,删除这个元素。这里数组中间就留下一个空位,让第f个元素填充这个空位,具体方法是修改元素prev[f]的next指针和元素next[f]和prev指针 10.3-5 与10.3-4类似