表的抽象数据类型
ADT list: #一个表的抽象数据类型
List(self) #表的构造操作,创建一个空表
is_empty(self) #判断self是否为一个空表
len(self) #获得self的长度
prepend(self, elem) #将元素elem加入表中作为第一个元素
append(self, elem) #将元素elen加入表中作为最后一个元素
insert(self, elem, i) #将elem加入表中作为第i个元素,其他元素的顺序不变
del_first(self) #删除表中的首元素
del_last(self) #删除表中的尾元素
del(self, i) #删除表中第i个元素
search(self, elem) #查找元素elem在表中出现的位置,不出现时返回-1
forall(self, op) #对表中的每个元素执行操作op
1、构建结点对象
class LNode:
def __init__(self, elem, next_ = None):
self.elem = elem
self.next = next_
2、单链表的实现
class LList:
def __init__(self):
self._head = None def is_empty(self):
return self._head is None def len(self):
p = self._head
l = 0
while p is not None:
l += 1
p = p.next
return l def prepend(self, elem):
self._head = LNode(elem, self._head) def append(self, elem):
if self._head is None:
self._head = LNode(elem)
return
p = self._head
while p.next is not None:
p = p.next
p.next = LNode(elem) def insert(self, elem, i):
if i<0 or i > self.len():
raise ValueError
if i == 0:
self.prepend(elem)
else:
p = self._head
while p is not None and i > 1:
i -= 1
p = p.next
p.next = LNode(elem, p.next) def del_first(self):
if self._head is None:
raise ValueError
e = self._head.elem
self._head = self._head.next
return e def del_last(self):
if self._head is None:
raise ValueError
p = self._head
if p.next is None:
self._head = None
return p.elem
while p.next.next is not None:
p = p.next
e = p.next.elem
p.next = None
return e def del_(self, i):
if i<0 or i >= self.len() or self._head is None:
raise ValueError
if i == 0:
self.del_first()
else:
p = self._head
while p is not None and i > 1:
i -= 1
p = p.next
e = p.elem
p.next = p.next.next
return e def search(self, elem):
p = self._head
i = 0
while p is not None:
if p.elem == elem:
return i
i += 1
p = p.next
return -1 def forall(self, op):
p = self._head
while p is not None:
op(p.elem)
p = p.next