python数据结构与算法之单链表

表的抽象数据类型

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
上一篇:Luogu P1082 同余方程(exgcd模版)


下一篇:docker容器中Postgresql 数据库备份