数据结构之线性表（python版）
单链表
1.1 定义表节点
# 定义表节点
class LNode():
def __init__(self,elem,next = None): self.elem = elem
self.next = next_1.2 单向链表
# LList 类的定义 单链表 （单向） class LList():
def __init__(self): # 这里并没有继承 LNode类 在加入数据时候引用了 LNode类 self.head = None def is_empty(self):
return self._head is None def prepend(self,elem): # 在表头插入数据 # 时间复杂度是O(1) self._head = LNode(elem,self._head) # 这里体现了基于节点类LNode 定义 def pop(sefl):
''' 返回表头的数据，并删除该数据
时间复杂度是 O(1) '''
if self._head is None: # 无节点
raise LinkedListUnderflow("in pop .")
e = self._head.elem
self._head = self._head.next
return e def append(self,elem):
# 尾端操作数据 首先要找到尾端节点
# 时间复杂度O(n) ，n 是节点的个数
if self._head is None :
self._head = LNode(elem)
return
p = self._head
while p.next :
p = p.next
p.next = LNode(elem) def pop_last(self):
# 弹出尾端数据，并删除
# 时间复杂度是 O(n),n 是节点个数
if self._head is None :
raise LinkedUnderflow(" in pop_last . ")
p = self._head
if p.next is None : # 表中只有一个数据
e = p.elem
self._head = None
return e
while p.next.next : # 这里的逻辑容易搞混，注意判断条件
p = p.next
e = p.next.elem
p.next = None
return e def find(self,pred):
# 查找满足条件的元素
# 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):
# for_each 是类似于 map zip 函数
# proc 是可以作用于表元素的函数 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 def rev(self):
p = None
while self._head :
q = self._head
self._head = q.next
q.next = p
p = q
self._head = p1.3 单向链表变形
1.31 增加尾节点引用域_rear LList1 单链表变形类# 增加尾节点引用域_rear LList1 单链表变形类 class LList1(LList): # 比单纯的单链表类 增加了尾节点引用域_rear def __init__(self):
LList.__init__(self)
self._rear = None def prepend(self,elem): # 前端插入
self._head = LNode(elem)
if 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._rear = self._head
else :
self._rear.next = LNode(elem)
self._rear = self._rear.next def pop_last(self): # 尾端弹出
if self._head is None :
raise LinkedUnderflow(" in pop_last() . ")
p = self._head
if p.next is None : # 如果只有一个元素
e = self._head
self._head = None
return e
while p.next.next :
p = p.next
e = p.next.elem
p.next = None
self._rear = p
return e1.32 循环单链表类的定义 LCList
# 循环单链表类的定义 LCList class LCList():
'''
循环单链表中的 _rear 在逻辑上始终引用着表的结尾
'''
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): # 后端插入
prepend(elem)
slef._rear = self._rear.next def pop(self): # 前端弹出
if self._rear is None :
raise LinkedUnderflow(" 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
while True :
print(p.elem)
if p is self._rear :
break
p = p.next双链表
双链表与单链表的区别在于，双链表比单链表多了个反向引用域 prev2.1 双链表类节点的定义 DLNode
# 双链表节点类 DLNode class DLLNode(LNode):
''' 双链表节点类 '''
def __init__(self,elem,prev=None,next_=None):
LNode.__init__(self,elem,next_)
self.prev = prev # 反向引用域2.2 双链表的定义
基于单链表类 LList1 派生出 DLList ，个别方法不需要重新定义# 双链表节点类 DLNode class DLLNode(LNode):
'''
双链表节点类
'''
def __init__(self,elem,prev=None,next_=None) :
LNode.__init__(self,elem,next_)
self.prev = prev # 定义双链表 DDList class DLList(LList1): # 有两个引用域，一个是next 另一个是反向 prev def __init__(self):
LList.__init__(self) def perpend(sefl,elem) : # 前端加入
p = DLNode(elem,None,self._head) # 这里已经做了 p.next_=self._head
if self._head is None :
self._rear = p
else :
p.next.prev = p
# p.next = self._head 这一步在加入elem元素时就做了
self._head = p def append(self,elem): # 后端加入
p = DLNode(elem,self._rear,None) # 这里已经做了 p.prev = self._rear
if self._head is None : # 空表
self._head = p
else : # 非空表 设置 next 引用
p.prev.next = p
self._rear = p def pop(self): # 前端弹出
if self._head is None :
raise LinkedUnderflow(" in pop of DLList . ")
e = self._head.elem
self._head = self._head.next
if self._head :
self._head.prev = None
return e def pop_last(self) : # 尾端弹出
if self._head is None :
raise LinkedUnderflow(" in pop_last of DLList . ")
e = self._rear.elem
self._rear = self._rear.prev
if self._rear is None :
self._head = None # 设置_head=None 保证is_empty正常工作
else :
self._rear.next = None
return e2.3 循环双链表