咋样建设网站广告公司取名字参考大全
算法导论程序22--指针和对象的实现(Python)
算法导论程序22--指针和对象的实现(Python)
对象的多数组表示：
next数组：
key数组：
prev数组：
三个数组项key[x],next[x],prev[x]一起表示链表中的一个对象。
变量L：表头元素的下标。
对象的分配和释放：
假设多数组表示法中的各数组长度为m，且在某一时刻该动态集合含有n<=m个元素。则n个对象代表现存于该动态集合中的元素，而余下的m-n个对象是自由的。这些自由对象可用来表示将要插入该动态集合的元素。
我们把自有对象保存在一个单链表中，称为自由表(free list)。自由表只使用next数组，该数组只存储表中的next指针。自由表的表头保存在全局变量free中。
自由表类似于一个栈：下一个被分配的对象就是最后被释放的那个。
以下程序中实现了上图中的a和b
class pointer_object:
def __init__(self,L,free,key,l_next,prev):
self.L=L
self.free=free
self.key=key
self.l_next=l_next
self.prev=prev
def allocate_object(self):
if self.free==None:
print("out of space")
else:
x=self.free
print("x:",x)
self.free=self.l_next[x-1]
print("x.next:",self.free)
return x
def free_object(self,x):
self.l_next[x-1]=self.free
self.free=x
def list_insert(self,x):
self.l_next[x-1]=self.L
if self.L!=None:
self.prev[self.L-1]=x
self.L=x
self.prev[x-1]=None运行结果：
>>> L=7
>>> free=4
>>> key=[None,4,1,None,16,None,9,None]
>>> l_next=[-1,3,-1,8,2,1,5,6]
>>> prev=[None,5,2,None,7,None,-1,None]
>>> po=pointer_object(L,free,key,l_next,prev)
>>> po.allocate_object()
x: 4
x.next: 8
4
>>> po.key[3]=25
>>> po.list_insert(4)
>>> po.l_next
[-1, 3, -1, 7, 2, 1, 5, 6]
>>> po.key
[None, 4, 1, 25, 16, None, 9, None]
>>> po.prev
[None, 5, 2, None, 7, None, 4, None]
>>>
算法导论程序22--指针和对象的实现(Python)相关教程