python删除链表满足pred的元素_python 数据结构一 之 线性表
python數據結構教程第一課
從這里將會正式開始講解python的一些實用的數據結構，原理加上實例源碼。
一、簡介
二、線性表的抽象數據類型
三、順序表的實現
四、鏈接表的實現
1.單鏈表
2.帶尾指針的單鏈表
3.循環單鏈表
4.雙鏈表
5.循環雙鏈表
五、線性表的應用—Josephus問題
1.順序表解法
2.循環單鏈表解法
##一、簡介 ##
在程序里經常需要將一組數據元素作為整體管理和使用，需要創建這種元素組，用變量記錄它們，一組數據中包含的元素個數可能發生變化，也可能會用元素在序列里的位置和順序，表示實際應用中的某種有意義信息。線性表就是這樣一組元素的抽象，其具體實現方式有兩種，順序表和鏈接表
二、線性表的抽象數據類型(ADT)
線性表的基本操作應當有創建空表、返回長度信息、插入、刪除等操作，其基本的ADT如下：
ADT List：
List(self) #創建一個新表
is_empty(self) #判斷self是否是一個空表
len(self) #返回表長度
prepend(self,elem) #在表頭插入元素
append(self,elem) #在表尾加入元素
insert(self,elem,i) #在表的位置i處插入元素
del_first(self) #刪除第一個元素
def_last(self) #刪除最后一個元素
del(self,i) #刪除第I個元素
search(self,elem) #查找元素在表中第一次出現的位置
forall(self,op) #對表元素的遍歷操作，op操作
三、順序表的實現##
python內部的tuple與list采用的就是順序表結構，其不同點在于tuple是固定結構，一旦創建就無法進行改動，而list則支持變動操作，具有上述ADT所描述的全部操作，這里不再具體重寫類代碼，其主要使用命令如下
list1 = list([1,2,3,4,5]) #創建新表
list1.append(6) #在尾部添加新元素 6
k = len(list1) #返回表長度
list1.insert(k,7) #在位置k插入7
list1.pop() #返回并刪除尾部元素
print(list1) #輸出表的全部元素
list2 = list1[2:] #表的切片操作
順序表的優勢在于O(1)時間的定位元素訪問，很多簡單的操作效率也比較高，比較麻煩的地方在于，表中間位置元素的插入刪除操作，由于元素在順序表的存儲區里連續排列，插入／刪除操作可能要移動很多元素，代價很高
四、鏈接表的實現##
基于鏈接技術實現的線性表稱為鏈接表或者鏈表，用鏈接關系顯式表示元素之間的順序關系，鏈接表結構的基本思想如下：
1.把表中的元素分別存儲在一批獨立的存儲塊(結點)里
2.保證從組成表結構中的任一個結點可找到與其相關的下一個結點
3.在前一結點里用鏈接的方式顯式地記錄與下一結點之間的關聯
在python里鏈表的實現有諸多方式和變形，接下來將選取主要的結構進行源碼講解
1.單鏈表
單鏈表是最基本也是最常用的鏈表結構，以下描述了鏈表的各種方法，包括，插入、排序、刪除、融合等
import copy
#單鏈表結點類
class LNode:
def __init__(self, elem,next_=None):
self.elem = elem
self.next = next_
#鏈表位置定位錯誤
class LinkedListUnderflow(ValueError):
pass
#單鏈表類的具體實現
class LList:
def __init__(self): #初始化操作
self._head = None
self.num = 0 #num記錄結點數
def is_empty(self): #空表判定
return self._head is None
def len(self): #返回表長
return self.num
#定位到鏈表的第loc個元素
def located(self,loc):
if (loc > self.num or loc < 1):
raise LinkedListUnderflow('in located')
temp = self._head
i = 1
if loc == 1:
return temp
else:
while i < loc:
temp = temp.next
i += 1
return temp
#在鏈表的第loc個位置添加元素elem
def located_add(self,loc,elem):
temp = self.located(loc)
node = LNode(elem)
if loc == 1:
node.next = self._head
self._head = node
else:
node.next = temp.next
temp.next = node
self.num += 1
#在鏈表的第loc個位置刪除元素
def located_del(self,loc):
temp = self.located(loc)
if loc == 1:
self._head = self._head.next
else:
temp.next = temp.next.next
self.num -= 1
#表頭插入元素
def prepend(self,elem):
self._head = LNode(elem,self._head)
self.num += 1
#返回并刪除表頭元素
def pop(self):
if self._head is None:
raise LinkedListUnderflow('in pop')
e = self._head.elem
self._head = self._head.next
self.num -= 1
return e
#在表尾添加元素
def append(self,elem):
if self._head is None:
self._head = LNode(elem)
self.num += 1
return
p = self._head
while p.next is not None:
p = p.next
p.next = LNode(elem)
self.num += 1
#返回并刪除表尾元素
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
self.num -= 1
return e
while p.next.next is not None:
p = p.next
e = p.next.elem
p.next = None
self.num -= 1
return e
#返回表中所有滿足pred()操作的元素
def filter(self,pred):
p = self._head
while p is not None:
if pred(p.elem):
yield 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('')
#對表中的所有元素執行proc操作
def for_each(self,proc):
p = self._head
while p is not None:
proc(p.elem)
p = p.next
#使鏈表支持iterator操作
def elements(self):
p = self._head
while p is not None:
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
#鏈表從小到大排序
def sort(self):
if self._head is None:
return
crt = self._head.next
while crt is not None:
x = crt.elem
p = self._head
while p is not crt and p.elem <= x:
p = p.next
while p is not crt:
y = p.elem
p.elem = x
x = y
p = p.next
crt.elem = x
crt = crt.next
#第二種排序算法
def sort1(self):
p = self._head
if p is None or p.next is None:
return
rem = p.next
p.next = None
while rem is not None:
p = self._head
q = None
while rem is not None and p.elem <= rem.elem:
q = p
p = p.next
if q is None:
self._head = rem
else:
q.next = rem
q = rem
rem = rem.next
q.next = p
#第三種排序算法
def sort2(self):
list1 = copy.deepcopy(self)
if list1._head.next is None:
return
list1._head.next.next = None
if list1._head.next.elem < list1._head.elem:
a = list1._head
list1._head = list1._head.next
list1._head.next = a
list1._head.next.next = None
temp = self._head.next.next
while temp is not None:
p = list1._head
q = list1._head.next
if temp.elem < list1._head.elem:
a = temp.next
temp.next = list1._head
list1._head = temp
temp = a
if temp is not None:
print(temp.elem)
list1.printall()
elif temp.elem >= list1._head.elem:
while q is not None:
if q.elem >= temp.elem:
a = temp.next
temp.next = q
p.next = temp
temp = a
break
elif q.elem < temp.elem:
q = q.next
p = p.next
if q is None:
p.next = temp
a = temp.next
temp.next = None
temp = a
self._head = list1._head
#鏈表深拷貝操作
def deep_copy(self):
Co = copy.deepcopy(self)
return Co
#鏈表相等判斷
def __eq__(self,List1):
Co1 = self.deep_copy()
Co2 = List1.deep_copy()
Co1.sort()
Co2.sort()
temp1 = Co1._head
temp2 = Co2._head
while Co1.len() == Co2.len() and temp1 is not None and temp2 is not None and temp1.elem == temp2.elem:
temp1 = temp1.next
temp2 = temp2.next
return temp1 is None and temp2 is None
#鏈表按字典序，< 運算函數
def __lt__(self,other):
temp1 = self._head
temp2 = other._head
while temp1 is not None and temp2 is not None:
if temp1.elem < temp2.elem:
return True
elif temp1.elem > temp2.elem:
return False
else:
temp1 = temp1.next
temp2 = temp2.next
if temp1 is None and temp2 is not None:
return True
else:
return False
#鏈表按字典序，=< 運算函數
def __le__(self,other):
temp1 = self._head
temp2 = other._head
while temp1 is not None and temp2 is not None:
if temp1.elem < temp2.elem:
return True
elif temp1.elem > temp2.elem:
return False
else:
temp1 = temp1.next
temp2 = temp2.next
if temp1 is None:
return True
else:
return False
#鏈表按字典序 >= 運算函數
def __ge__(self,other):
temp1 = self._head
temp2 = other._head
while temp1 is not None and temp2 is not None:
if temp1.elem > temp2.elem:
return True
elif temp1.elem < temp2.elem:
return False
else:
temp1 = temp1.next
temp2 = temp2.next
if temp2 is None:
return True
else:
return False
#鏈表按字典序，> 運算函數
def __gt__(self,other):
temp1 = self._head
temp2 = other._head
while temp1 is not None and temp2 is not None:
if temp1.elem > temp2.elem:
return True
elif temp1.elem < temp2.elem:
return False
else:
temp1 = temp1.next
temp2 = temp2.next
if temp2 is None and temp1 is not None:
return True
else:
return False
#鏈表反向遍歷，執行對每個元素執行op操作
def rev_visit(self,op):
temp = copy.deepcopy(self)
temp.rev()
head = temp._head
while head is not None:
op(head.elem)
head = head.next
#刪除表中的elem
def del_elem(self,elem):
a = self._head
b = self._head.next
if a is None:
return
if a.elem == elem:
self._head = b
while b is not None:
if b.elem == elem:
a.next = b.next
a = a.next
b = b.next
#刪除表中最小元素
def del_minimal(self):
temp = copy.deepcopy(self)
temp.sort()
elem = temp._head.elem
self.del_elem(elem)
#刪除表中所有滿足pred操作的元素
def del_if(self,pred):
temp = self._head
while temp is not None:
if pred(temp.elem):
self.del_elem(temp.elem)
temp = temp.next
#返回一個字典，字典記錄了表中每個元素出現的次數
def elem_num(self):
temp = self._head
adict = dict()
while temp is not None:
if temp.elem not in adict:
adict[temp.elem] = 1
else:
adict[temp.elem] += 1
temp = temp.next
return adict
#刪除鏈表中出現的重復項，第一次不變
def del_duplicate(self):
temp1 = self._head
temp2 = self._head.next
adict = self.elem_num()
if adict[temp1.elem] > 1:
adict[temp1.elem] *= -1
while temp2 is not None:
if adict[temp2.elem] > 1:
adict[temp2.elem] *= -1
temp1 = temp1.next
elif adict[temp2.elem] < 0:
temp1.next = temp2.next
else:
temp1 = temp1.next
temp2 = temp2.next
print(adict)
#兩個鏈表的交叉融合為一個鏈表
def interleaving(self,another):
temp1 = self._head
temp2 = another._head
while temp1 is not None and temp2 is not None:
p = temp1.next
temp1.next = temp2
q = temp2.next
temp2.next = p
temp1 = p
temp2 = q
if temp1 is None:
p = self._head
while p.next is not None:
p = p.next
p.next = temp1
以上描述了單鏈表的眾多方法，單鏈表還存在很多別的形態，可以讓很多操作變的簡潔有效率
2.帶尾結點的單鏈表
單鏈表對尾部結點的訪問效率是十分低下的，需要遍歷表中之前的全部結點，當單鏈表帶上尾部指針時，這種操作就會變的有效率很多
#帶尾結點的單鏈表，繼承自單鏈表，支持其的全部屬性和方法
class LList1(LList):
def __init__(self): #初始化，新添了—rear作為尾結點
LList.__init__(self)
self._rear = None
#首部結點插入方法
def prepend(self,elem):
self._head = LNode(elem,self._head)
if self._rear is None:
self._rear = 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
3.循環單鏈表
使單鏈表的尾指針指向首結點，就構成了循環單鏈表，其與單鏈表的不同在于，其掃描循環結束的控制判斷
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,end = " ")
if p is self._rear:
break
p = p.next
#兩個鏈表交叉融合為一個鏈表
def interleaving(self,another):
temp1 = self._rear.next
temp2 = another._rear.next
while temp1 is not self._rear and temp2 is not another._rear:
a = temp2.next
temp2.next = temp1.next
temp1.next = temp2
temp2 = a
temp1 = temp1.next.next
if temp1 is self._rear:
while temp2 is not another._rear:
self.append(temp2.elem)
temp2 = temp2.next
4.雙鏈表
在單鏈表中，除了首結點和尾結點外，每個元素不但指向它的下一個結點，還會指向它的上一個結點，雙鏈表支持更簡單的反向遍歷操作，雙鏈表需要雙結點類支持
#雙結點類
class DLNode(LNode):
def __init__(self,elem,prev = None,next_ = None):
LNode.__init__(self,elem,next_)
self.prev = prev
#雙鏈表繼承自帶首尾指針的單鏈表，不過需要重寫添加和刪除方法
class DLList(LList1):
def __init__(self): #初始化
LList1.__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 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
return e
#尾端返回并刪除
def pop_last(self):
if self._head is None:
raise LinkedListUnderflow('in pop_last of DLList')
e = self._rear.elem
self._rear = self._rear.prev
if self._rear is None:
self._head = None
else:
self._rear.next = None
return e
5.循環雙鏈表
雙鏈表的尾部首部互指，構成循環雙鏈表
class DCLList():
def __init__(self): #雙鏈表類
self._head = None
self.__num = 0
#尾端插入
def append(self,elem):
p = DLNode(elem,None,None)
if self._head is None:
p.next = p
p.prev = p
self._head = p
else:
p.prev = self._head.prev
p.next = self._head
self._head.prev.next = p
self._head.prev = p
self.__num += 1
#尾部返回并刪除
def pop(self):
if self._head is None:
raise LinkedListUnderflow('in pop_last of DCLList')
elem = self._head.prev.elem
self._head.prev.prev.next = self._head
self._head.prev = self._head.prev.prev
self.__num -= 1
return elem
#返回長度
def len(self):
return self.__num
#鏈表倒置
def reverse(self):
q = self._head
p = self._head.prev
n = 1
while p is not q and n <= self.len()/2:
t = p.elem
p.elem = q.elem
q.elem = t
q = q.next
p = p.prev
n += 1
#鏈表元素排序
def sort(self):
i = 0
while i < self.len():
j = 0
p = self._head
while j < self.len()-i-1:
if p.elem > p.next.elem:
t = p.elem
p.elem = p.next.elem
p.next.elem = t
j += 1
p = p.next
self.printall()
i += 1
#鏈表倒置算法2
def reverse1(self):
li = DCLList()
p = self._head.prev
for i in range(self.len()):
li.append(p.elem)
p = p.prev
i += 1
self._head = li._head
#鏈表排序算法2
def sort1(self):
i = 0
while i < self.len()-1:
j = 0
p = self._head.next
while j < self.len()-i-2:
if p.elem > p.next.elem:
a = p.prev
b = p.next.next
c = p.next
a.next = c
c.prev = a
c.next = p
p.prev = c
p.next = b
b.prev = p
else:
p = p.next
j += 1
i += 1
i = 0
p = self._head.next
elem = self._head.elem
while i < self.len()-1:
if p.elem <= elem and p.next.elem > elem:
a = self._head
b = self._head.prev
c = self._head.next
b.next = c
c.prev = b
a.next = p.next
p.next.prev = a
p.next = a
a.prev = p
self._head = c
break
i += 1
p = p.next
if i == self.len()-1:
self._head = self._head.next
#輸出鏈表元素
def printall(self):
p = self._head
for i in range(self.len()):
print(p.elem,end = ' ')
p = p.next
print()
以上介紹了鏈表的眾多基本與高級操作，以及鏈表的各種形態變形，鏈表的優勢在于，表元素之間的順序由它們所在的結點之間的鏈接顯式表示，因此表結點可以任意安排位置，靈活的調整結構。
同時，為了實現鏈接表，每個結點都增加了一個鏈接域，付出了額外的空間代價，鏈表的位置訪問代價很高，需要一個個結點的遍歷，使用鏈表最合理的方式是前端操作和順序訪問
五、線性表的應用—Josephus問題
這里舉出一個經典的問題來描述鏈表的用法
Josephus問題：
假設有n個人圍坐一圈，現要求從第k個人開始報數，報到第m個數的人退出。然后從下一個人開始繼續報數并按同樣的規則退出，直至所有人退出，要求按順序輸出各出列人的編號
方法1.我們可以用list實現算法：
def josephus_A(n,k,m):
people = list(range(1,n+1))
i = k - 1
for num in range(n):
count = 0
while count < m:
if people[i] > 0:
count += 1
if count == m:
print(people[i],end = ' ')
people[i] = 0
i = (i+1) % n
if num < n - 1:
print(',',end = '')
else:
print('')
return
方法2.如果我們該用循環單鏈表，會發現問題簡單了很多：
class Josephus(LCList):
def turn(self,m):
for i in range(m):
self._rear = self._rear.next
def __init__(self,n,k,m):
LCList.__init__(self)
for i in range(n):
self.append(i+1)
self.turn(k-1)
while not self.is_empty():
self.turn(m-1)
print(self.pop(),end = ('\n' if self.is_empty() else ','))
假設有13個人，從第5個人開始報數，數為6，則兩種算法的使用和結果為：
算法1:
josephus_A(13,5,6)
算法2:
Josephus(13,5,6)
總結
以上是生活随笔為你收集整理的python删除链表满足pred的元素_python 数据结构一 之 线性表的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： python制作题库网站_Python解
- 下一篇： python写快排_python 实现快