Python数据结构与算法之链表定义与用法实例详解【单链表、循环链表】
本文实例讲述了Python数据结构与算法之链表定义与用法。分享给大家供大家参考,具体如下:
本文将为大家讲解:
(1)从链表节点的定义开始,以类的方式,面向对象的思想进行链表的设计
(2)链表类插入和删除等成员函数实现时需要考虑的边界条件,
prepend(头部插入)、pop(头部删除)、append(尾部插入)、pop_last(尾部删除)
2.1插入:
空链表
链表长度为1
插入到末尾
2.2删除
空链表
链表长度为1
删除末尾元素
(3)从单链表到单链表的一众变体:
带尾节点的单链表
循环单链表
双链表
1.链表节点的定义
classLNode: def__init__(self,elem,next_=None): self.elem=elem self.next=next_
2.单链表的实现
重点理解插入、删除的实现及其需要考虑的边界条件:
classLinkedListUnderflow(ValueError): pass classLList: def__init__(self): self._head=None defis_empty(self): returnself._headisNone defprepend(self,elem): self._head=LNode(elem,self._head) defpop(self): ifself._headisNone: raiseLinkedListUnderflow('inpop') e=self._head.elem self._head=self._head.next returne defappend(self,elem): ifself._headisNone: self._head=LNode(elem) return p=self._head whilep.nextisnotNone: p=p.next p.next=LNode(elem) defpop_last(self): ifself._headisNone: raiseLinkedListUnderflow('inpop_last') p=self._head ifp.nextisNone: e=p.elem self._head=None returne whilep.next.nextisnotNone: p=p.next e=p.next.elem p.next=None returne
简单总结:
(0)能够访问p.next.next的前提是p.next不为空;
(1)尾部插入,如果链表不为空,需且仅需改变的是尾部节点的指针;
(2)尾部删除,如果链表长度不为空,需且仅需改变的是倒数第二个节点的指针。
单链表的简单变形:具有尾部节点的单链表
classLList1(LList): def__init__(self): LList.__init__(self) self._rear=None ...
我们仅需重写的是:头部的插入、尾部的插入、尾部的删除
defprepend(self,elem): ifself._headisNone: self._head=LNode(elem) self._rear=self._head else: self._head=LNode(elem,self._head) defappend(self,elem): ifself._headisNone: self._head=LNode(elem) self._rear=self._head else: self._rear.next=LNode(elem) self._rear=self._rear.next defpop_last(self): ifself._headisNone: raiseLinkedListUnderflow('inpop_last') p=self._head ifp.nextisNone: e=p.elem self._head=None returne whilep.next.nextisnotNone: p=p.next e=p.next.elem self._rear=p p.next=None returne
单链表的变体:循环单链表
classLCList: def__init__(self): self._rear=None defprepend(self,elem): ifself._rearisNone: self._rear=LNode(elem) self._rear.next=self._rear else: self._rear.next=LNode(elem,self._rear.next) defappend(self,elem): self.prepend(elem) self_rear=self._rear.next defpop(self): ifself._rearisNone: raiseLinkedListUnderflow('inpop') p=self._rear.next ifpisNone: self._rear=None else: self._rear.next=p.next returnp.elem defprintall(self): ifself._rearisNone: raise... p=self._rear.next whileTrue: print(p.elem) ifpisself._rear: break p=p.next
更多关于Python相关内容可查看本站专题:《Python数据结构与算法教程》、《PythonSocket编程技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总》
希望本文所述对大家Python程序设计有所帮助。