Python链表笔记

class LNode: def __init__(self,elem,next_=None): self.elem = elem self.next = next_ list1 = LNode(1) p = list1 for i in range(2,11): p.next = LNode(i) p = p.next p = list1 while p : print(p.elem,end=' ') p = p.next print("单链表定义及测试完成！") class LinkedListUnderflow(ValueError): pass class LList: def __init__(self): self._head = None def is_empty(self): return self._head is None def prepend(self,elem): self._head = LNode(elem,self._head) def pop(self): if self._head is None: raise LinkedListUnderflow("in pop") e = self._head.elem self._head = self._head.next return e 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 pop_last(self): if self._head is None: raise LinkedListUnderflow("in pop_last") p = self._head if p.next is None: e = p.elem self._head = None return e while p.next.next is not None: p = p.next e = p.next.elem p.next = None return e def find(self,pred): p = self._head while p is not None: if pred(p.elem): return p.elem p = p.next def printall(self): p = self._head while p is not None: print(p.elem,end='') if p.next is not None: print(', ',end='') p = p.next print('') def elements(self): p = self._head while p is not None: yield p.elem p = p.next def filter(self,pred): p = self._head while p is not None: if pred(p.elem): yield p.elem p = p.next def rev(self): p = None while self._head is not None: q = self._head self._head = q.next q._next = p p = q self._head = p mlist1 = LList() for i in range(10): mlist1.prepend(i) for i in range(10,20): mlist1.append(i) #mlist1.printall() for x in mlist1.elements(): print(x,end=" ") print("单链表使用测试完成！") class LList1(LList): def __init__(self): LList.__init__(self) self._rear = None def prepend(self,elem): if self._head is None: self._head = LNode(elem,self._head) self._rear = self._head else: self._head = LNode(elem,self._head) def append(self,elem): if self._head is None: self._head = LNode(elem.self._head) self._rear = self._head else: self._rear.next = LNode(elem) self._rear = self._rear.next def pop_last(self): if self._head is None: raise LinkedListUnderflow("in pop_last") p = self._head if p.next is None: e = p.elem self._head = None return e while p.next.next is not None: p = p.next e = p.next.elem p.next = None self._rear = p return e def find(self,pred): p = self._head while p: if pred(p.elem): return p.elem p = p.next def printall(self): p = self._head while p: print(p.elem,end=" ") if p.next: print(',',end=" ") p = p.next print(" ") def for_each(self,proc): #p的实参应该是可以作用与表元素的操作函数 p = self._head while p : proc(p.elem) p = p.next def elements(self): p = self._head while p: yield p.elem p = p.next def filter(self,pred): p = self._head while p: if pred(p.elem): yield p.elem p = p.next #mlist1 = LList1() #mlist1.prepend(99) #for i in range(11,20): # mlist1.append(i) #print(mlist1) #for x in mlist1.filter(lambda y : y % 2 == 0): # print(x,end=" ") mlist1 = LList() for i in range(10): mlist1.prepend(i) for i in range(11,20): mlist1.append(i) mlist1.printall() for x in mlist1.elements(): print(x) print("单链表变形，增加一个尾节点引用域_rear") class LList2(LList): def __init(self): LList.__init__(self) self._rear = None def prepend(self,elem): if self._head is None: self._head = LNode(elem,self._head) self._rear = self._head else: self._head = LNode(elem,self._head) def append(self,elem): if self._head is None: self._head = LNode(elem,self._head) self._rear = self._head else: self._rear.next = LNode(elem) self._rear = self._rear.next def pop_last(self): if self._head is None: raise LinkedListUnderflow("in pop_last") p = self._head if p.next is None: e = p.elem self._head = None return e while p.next.next is not None: p = p.next e = p.next.elem p.next = None self._rear = p return e mlist1 = LList2() mlist1.prepend(99) for i in range(11,20): mlist1.append(i) for x in mlist1.filter(lambda y:y % 2 == 0): print(x) #循环单链表 class LCList: def __init__(self): self._rear = None def is_empty(self): return self._rear is None def prepend(self,elem): p = LNode(elem) if self._rear is None: p.next = p self._rear = p else: p.next = self._rear.next self._rear.next =p def append(self,elem): self.prepend(elem) self._rear = self._rear.next def pop(self): if self._rear is None: raise LinkedListUnderflow("in pop of CLList") p = self._rear.next if self._rear is p: self._rear = None else: self._rear.next = p.next return p.elem def printall(self): if self.is_empty(): return p = self._rear.next while True: print(p.elem) if p is self._rear: break p = p.next #双链表 class DLNode(LNode): def __init__(self,elem,prev=None,next_=None): LNode.__init__(self,elem,next_) self.prev = prev class DLList(LList2): def __init__(self): LList2.__init__(self) def prepend(self,elem): p = DLNode(elem,None,self._head) if self._head is None: self._rear = p else: p.next.prev = p self._head = p def append(self,elem): p = DLNode(elem,self._rear,None) if self._head is None: self._head = p else: p.prev.next = p self._rear = p def pop(self): if self._head is None: raise LinkedListUnderflow("in pop of DLList") e = self._head.elem self._head = self._head.next if self._head is not None: self._head.prev = None def pop_last(self): if self._head is None: raise LinkedListUnderflow("in pop_last of DLList") e = self._head.elem self._rear = self._rear.prev if self._rear is None: self._head = None return e