数据结构之线性表（python版）
-
单链表
1.1 定义表节点
1 # 定义表节点 2 class LNode(): 3 def __init__(self,elem,next = None): 4 5 self.elem = elem 6 self.next = next_
1.2 单向链表
1 # LList 类的定义 单链表 （单向） 2 3 class LList(): 4 def __init__(self): 5 6 # 这里并没有继承 LNode类 在加入数据时候引用了 LNode类 7 8 self.head = None 9 10 def is_empty(self): 11 return self._head is None 12 13 def prepend(self,elem): # 在表头插入数据 14 15 # 时间复杂度是O(1) 16 17 self._head = LNode(elem,self._head) # 这里体现了基于节点类LNode 定义 18 19 def pop(sefl): 20 ''' 返回表头的数据，并删除该数据 21 时间复杂度是 O(1) ''' 22 if self._head is None: # 无节点 23 raise LinkedListUnderflow("in pop .") 24 e = self._head.elem 25 self._head = self._head.next 26 return e 27 28 def append(self,elem): 29 # 尾端操作数据 首先要找到尾端节点 30 # 时间复杂度O(n) ，n 是节点的个数 31 if self._head is None : 32 self._head = LNode(elem) 33 return 34 p = self._head 35 while p.next : 36 p = p.next 37 p.next = LNode(elem) 38 39 def pop_last(self): 40 # 弹出尾端数据，并删除 41 # 时间复杂度是 O(n),n 是节点个数 42 if self._head is None : 43 raise LinkedUnderflow(" in pop_last . ") 44 p = self._head 45 if p.next is None : # 表中只有一个数据 46 e = p.elem 47 self._head = None 48 return e 49 while p.next.next : # 这里的逻辑容易搞混，注意判断条件 50 p = p.next 51 e = p.next.elem 52 p.next = None 53 return e 54 55 def find(self,pred): 56 # 查找满足条件的元素 57 # pred 是可以作用于表元素的函数 58 p = self._head 59 while p: 60 if pred(p.elem): 61 return p.elem 62 p = p.next 63 64 def printall(self): # 打印表中所有元素 65 p = self._head 66 while p : 67 print(p.elem,end=" ") 68 if p.next : 69 print(', ',end="") 70 p = p.next 71 print('') 72 73 def for_each(self,proc): 74 # for_each 是类似于 map zip 函数 75 # proc 是可以作用于表元素的函数 76 77 p = self._head 78 while p : 79 proc(p.elem) 80 p = p.next 81 82 def elements(self): 83 ''' 84 定义生成器 函数 85 ''' 86 p = self._head 87 while p : 88 yield p.elem 89 p = p.next 90 91 def filter(self,pred): 92 ''' 93 定义筛选生成器 函数 94 ''' 95 p = self._head 96 while p : 97 if pred(p.elem) : 98 yield p.elem 99 p = p.next 100 101 def rev(self): 102 p = None 103 while self._head : 104 q = self._head 105 self._head = q.next 106 q.next = p 107 p = q 108 self._head = p
1.3 单向链表变形
1.31 增加尾节点引用域_rear LList1 单链表变形类1 # 增加尾节点引用域_rear LList1 单链表变形类 2 3 class LList1(LList): 4 5 # 比单纯的单链表类 增加了尾节点引用域_rear 6 7 def __init__(self): 8 LList.__init__(self) 9 self._rear = None 10 11 def prepend(self,elem): # 前端插入 12 self._head = LNode(elem) 13 if self._head : 14 self._rear = self._head 15 else : 16 self._head = LNode(elem,self._head) 17 18 def append(self,elem): # 尾端插入 19 if self._head is None : 20 self._head = LNode(elem) 21 self._rear = self._head 22 else : 23 self._rear.next = LNode(elem) 24 self._rear = self._rear.next 25 26 def pop_last(self): # 尾端弹出 27 if self._head is None : 28 raise LinkedUnderflow(" in pop_last() . ") 29 p = self._head 30 if p.next is None : # 如果只有一个元素 31 e = self._head 32 self._head = None 33 return e 34 while p.next.next : 35 p = p.next 36 e = p.next.elem 37 p.next = None 38 self._rear = p 39 return e
1.32 循环单链表类的定义 LCList1 # 循环单链表类的定义 LCList 2 3 class LCList(): 4 ''' 5 循环单链表中的 _rear 在逻辑上始终引用着表的结尾 6 ''' 7 def __init__(self): 8 self._rear = None 9 10 def is_empty(self): 11 return self._rear is None 12 13 def prepend(self,elem): # 前端插入 14 p = LNode(elem) 15 if self._rear is None : # 建立一个节点的环 16 p.next = p 17 self._rear = p 18 else : 19 p.next = self._rear.next 20 self._rear.next = p 21 22 def append(self,elem): # 后端插入 23 prepend(elem) 24 slef._rear = self._rear.next 25 26 def pop(self): # 前端弹出 27 if self._rear is None : 28 raise LinkedUnderflow(" in pop of CLList . ") 29 p = self._rear.next 30 if self._rear is p : 31 self._rear = None 32 else : 33 self._rear.next = p.next 34 return p.elem 35 36 def printall(self): # 输出表元素 37 if self.is_empty(): 38 return 39 p = self._rear 40 while True : 41 print(p.elem) 42 if p is self._rear : 43 break 44 p = p.next
-
双链表
双链表与单链表的区别在于，双链表比单链表多了个反向引用域 prev
2.1 双链表类节点的定义 DLNode1 # 双链表节点类 DLNode 2 3 class DLLNode(LNode): 4 ''' 双链表节点类 ''' 5 def __init__(self,elem,prev=None,next_=None): 6 LNode.__init__(self,elem,next_) 7 self.prev = prev # 反向引用域
2.2 双链表的定义
基于单链表类 LList1 派生出 DLList ，个别方法不需要重新定义1 # 双链表节点类 DLNode 2 3 class DLLNode(LNode): 4 ''' 5 双链表节点类 6 ''' 7 def __init__(self,elem,prev=None,next_=None) : 8 LNode.__init__(self,elem,next_) 9 self.prev = prev 10 11 # 定义双链表 DDList 12 13 class DLList(LList1): 14 15 # 有两个引用域，一个是next 另一个是反向 prev 16 17 def __init__(self): 18 LList.__init__(self) 19 20 def perpend(sefl,elem) : # 前端加入 21 p = DLNode(elem,None,self._head) # 这里已经做了 p.next_=self._head 22 if self._head is None : 23 self._rear = p 24 else : 25 p.next.prev = p 26 # p.next = self._head 这一步在加入elem元素时就做了 27 self._head = p 28 29 def append(self,elem): # 后端加入 30 p = DLNode(elem,self._rear,None) # 这里已经做了 p.prev = self._rear 31 if self._head is None : # 空表 32 self._head = p 33 else : # 非空表 设置 next 引用 34 p.prev.next = p 35 self._rear = p 36 37 def pop(self): # 前端弹出 38 if self._head is None : 39 raise LinkedUnderflow(" in pop of DLList . ") 40 e = self._head.elem 41 self._head = self._head.next 42 if self._head : 43 self._head.prev = None 44 return e 45 46 def pop_last(self) : # 尾端弹出 47 if self._head is None : 48 raise LinkedUnderflow(" in pop_last of DLList . ") 49 e = self._rear.elem 50 self._rear = self._rear.prev 51 if self._rear is None : 52 self._head = None # 设置_head=None 保证is_empty正常工作 53 else : 54 self._rear.next = None 55 return e
2.3 循环双链表