??個(gè)人主頁:?Aileen_0v0
??系列專欄:PYTHON學(xué)習(xí)系列專欄
??"沒有羅馬,那就自己創(chuàng)造羅馬~"??
目錄
線性數(shù)據(jù)結(jié)構(gòu)Linear DS
1.棧Stack
棧的兩種實(shí)現(xiàn)
1.左為棧頂,時(shí)間復(fù)雜度為O(n)
2.右為棧頂,時(shí)間復(fù)雜度O(1)??
2.隊(duì)列Queue
3.雙端隊(duì)列Deque
4.列表List
5.鏈表
a.無序鏈表的實(shí)現(xiàn)
b.有序鏈表的實(shí)現(xiàn)
線性數(shù)據(jù)結(jié)構(gòu)Linear DS
作用:將數(shù)據(jù)項(xiàng)以某種線性的次序組織起來
1.棧Stack
棧Stack維持了數(shù)據(jù)項(xiàng)后進(jìn)先出LIFO的次序
stack的基本操作包括push，pop，isEmpty
棧的兩種實(shí)現(xiàn)
1.左為棧頂,時(shí)間復(fù)雜度為O(n)
#左邊為頂,右邊為低
class Stack:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def push(self,item):
self.items.insert(0,item)
def pop(self):
return self.items.pop(0)
def peek(self):
return self.items[0]
def size(self):
return len(self.items)2.右為棧頂,時(shí)間復(fù)雜度O(1)??
# 左邊為低,右邊為頂--->更高效
class Stack:#Stack---->ADT
def __init__(self):
self.items =[]
def isEmpty(self):
return self.items == []
# 滿足這些屬性(行為)的是棧
def push(self,item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[len(self.items)-1]
#
def size(self):
return len(self.items)
s = Stack()鏈接??:?
2.隊(duì)列Queue
隊(duì)列Queue維持了數(shù)據(jù)項(xiàng)先進(jìn)先出FIFO的次序
queue的基本操作包括enqueue， dequeue,isEmpty 有助于構(gòu)建時(shí)序模擬
書寫表達(dá)式的方法有前綴prefix、中綴infix和后綴postfix三種由于棧結(jié)構(gòu)具有次序反轉(zhuǎn)的特性，所以棧結(jié)構(gòu)適合用于開發(fā)表達(dá)式求值和轉(zhuǎn)換的算法
“模擬系統(tǒng)”可以通過一個(gè)對(duì)現(xiàn)實(shí)世界問題進(jìn)行抽象建模，并加入隨機(jī)數(shù)動(dòng)態(tài)運(yùn)行為復(fù)雜問題的決策提供各種情況的參考隊(duì)列queue可以用來進(jìn)行模擬系統(tǒng)的開發(fā)
?鏈接??:
3.雙端隊(duì)列Deque
雙端隊(duì)列Deque可以同時(shí)具備棧和隊(duì)列的功能
deque的主要操作包括addFront，addRear, removeFront, removeRear, isEmpty
#創(chuàng)建一個(gè)雙端隊(duì)列(Dequeue)
class Dequeue:
#定義一個(gè)初始化函數(shù)然后創(chuàng)建一個(gè)空列表用于傳遞數(shù)據(jù)items
def __init__(self):
self.items = []
#判斷列表是否為空
def isEmpty(self):
return self.items == []
#在隊(duì)首加入元素items
def addFront(self,item):
self.items.append(item)
#在隊(duì)尾加入元素items
def addRear(self,item):
self.items.insert(0,item)
#從隊(duì)首移除數(shù)據(jù),返回值為移除數(shù)據(jù)項(xiàng)
def removeFront(self):
return self.items.pop()
#從隊(duì)尾移除數(shù)據(jù),返回移除數(shù)據(jù)項(xiàng)
def removeRear(self):
return self.items.pop(0)
#判斷列表是否為空
def isEmpty(self):
return self.items == []
#返回Dequeue中包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)
def size(self):
return len(self.items)
#palindrome - 回文檢查
def pal_checker (ps):
#實(shí)例化對(duì)象
d = Dequeue()
for char in ps:
d.addRear(char)
#假設(shè)元素左右相等
still_equal = True
#依次取出首尾元素進(jìn)行判斷,然后再判斷它是否滿足 :
# 奇數(shù)個(gè)元素的時(shí)候,雙端隊(duì)列里面還剩下一個(gè)元素
#偶數(shù)個(gè)元素的時(shí)候,雙端隊(duì)列里面沒有元素
while d.size() > 1 and still_equal :
#從隊(duì)首取出一個(gè)元素
first = d.removeFront()
#從隊(duì)尾取出一個(gè)元素
last = d.removeRear()
if first != last:
still_equal = False
return still_equal
print(pal_checker ("上海自來水來自海上"))
print(pal_checker ("110110"))鏈接??:?
4.列表List
列表List是數(shù)據(jù)項(xiàng)能夠維持相對(duì)位置的數(shù)據(jù)集
# 通過鏈表實(shí)現(xiàn) 無序表-列表
#列表 和 鏈表 都是無序表 unordered list
#實(shí)現(xiàn)鏈表
class Node:
def __init__(self,init_data):
self.data = init_data
self.next = None
#獲得數(shù)據(jù)項(xiàng)
def get_data(self):
return self.data
#獲得節(jié)點(diǎn)
def get_next(self):
return self.next
#設(shè)置數(shù)據(jù)項(xiàng)
def set_data(self,new_data):
self.data = new_data
#設(shè)置節(jié)點(diǎn)
def set_next(self,new_next):
self.next = new_next
#結(jié)點(diǎn)示例
temp = Node(93)
print(temp.get_data())鏈接??:?
5.鏈表
鏈表的實(shí)現(xiàn)，可以保持列表維持相對(duì)位置(保證邏輯順序)的特點(diǎn)，而不需要連續(xù)的存儲(chǔ)空間
鏈表實(shí)現(xiàn)時(shí)，其各種方法，對(duì)鏈表頭部head需要特別的處理?文章來源：http://www.zghlxwxcb.cn/news/detail-756821.html
a.無序鏈表的實(shí)現(xiàn)
# 通過鏈表實(shí)現(xiàn) 無序表-列表
#列表 和 鏈表 都是無序表 unordered list
#實(shí)現(xiàn)鏈表 -- 鏈表相當(dāng)于火車(順藤摸瓜結(jié)構(gòu),如果放在鏈表后面,找那個(gè)車廂需要從頭開始往后找)
class Node:#結(jié)點(diǎn)Node相當(dāng)于車廂
def __init__(self,init_data):
self.data = init_data
self.next = None
#獲得數(shù)據(jù)項(xiàng)
def get_data(self):
return self.data
#獲得節(jié)點(diǎn)
def get_next(self):
return self.next
#設(shè)置數(shù)據(jù)項(xiàng)
def set_data(self,new_data):
self.data = new_data#屬性
#設(shè)置節(jié)點(diǎn)
def set_next(self,new_next):
self.next = new_next#屬性
#結(jié)點(diǎn)示例
temp = Node(93)
temp2 = Node(17)
temp3 = Node(77)
print(temp.get_data())
print(temp2.get_data())
print(temp3.get_data())
# 鏈表:1.有序表 2.無序表
#鏈表實(shí)現(xiàn): 無序表 UnorderedList
#設(shè)立一個(gè)屬性head , 保存對(duì)對(duì)第一個(gè)節(jié)點(diǎn)的引用
#空表的 head 為 None
class UnorderedList:
def __init__(self):
self.head = None
# mylist = UnorderedList()
# print (mylist.head)
#為item數(shù)據(jù)項(xiàng)生成一個(gè)結(jié)點(diǎn)-Node 叫做item
def add(self,item):
#然后將這個(gè)結(jié)點(diǎn)命名為臨時(shí)變量
temp = Node(item)
#將下一個(gè)臨時(shí)結(jié)點(diǎn)設(shè)置為表頭
temp.set_next(self.head)
#表頭指向新增加的臨時(shí)結(jié)點(diǎn)
self.head = temp
def size(self):
#當(dāng)前節(jié)點(diǎn)設(shè)為表頭第一個(gè)節(jié)點(diǎn)
current = self.head
count = 0
while current != None:
count += 1
#將當(dāng)前節(jié)點(diǎn)設(shè)為下一個(gè)結(jié)點(diǎn)的結(jié)點(diǎn),循環(huán)往復(fù)
current = current.get_next()
#返回結(jié)點(diǎn)的個(gè)數(shù)
return count
def search(self,item):
current = self.head
found = False
while current != None and not found:
#判斷當(dāng)前節(jié)點(diǎn)數(shù)據(jù)項(xiàng)是否等于我想要找的數(shù)據(jù)
if current.get_data() == item:
found = True
else:
current = current.get_next()
return found
def remove(self,item):#刪除找到的元素--引用兩個(gè)指針當(dāng)前和上繼指針
current = self.head
previous = None
found = False
#先判斷是不是我要找的那個(gè)元素
while not found:
if current.get_data == item:
found = True
else:
#通過current的指針給初始沒有指針的previous指路
previous = current
#然后current指針繼續(xù)往下走
current = current.get_next
# 如果中間位置找不到,那我們?cè)倥袛啾眍^
#當(dāng)前刪除的車廂部位值item 位于頭部時(shí),可以利用 previous 指向空
if previous == None:#當(dāng)前想要?jiǎng)h除的是不是車頭處的元素
self.head = current.get_next()
else:
previous.set_next(current.get_next())#刪除的是中間元素
def traverse(self):
current = self.head
while current != None:
print(current.get_data())
current = current.get_next()
#實(shí)例化無序表:
ll = UnorderedList()
# 加入新節(jié)點(diǎn)
ll.add(7)
ll.add(9)
ll.add(6)
ll.add(8)
ll.add(10)
print(ll.search(1000))
ll.traverse()
b.有序鏈表的實(shí)現(xiàn)
class Node:#結(jié)點(diǎn)Node相當(dāng)于車廂
def __init__(self,init_data):
self.data = init_data
self.next = None
#獲得數(shù)據(jù)項(xiàng)
def get_data(self):
return self.data
#獲得節(jié)點(diǎn)
def get_next(self):
return self.next
#設(shè)置數(shù)據(jù)項(xiàng)
def set_data(self,new_data):
self.data = new_data#屬性
#設(shè)置節(jié)點(diǎn)
def set_next(self,new_next):
self.next = new_next#屬性
class Orderedlist:
def __init__(self):
self.head = None
def search(self,item):
current = self.head
found = False
stop = False
while current != None and not found and not stop:
if current.get_data() == item:
found = True
else:
if current.get_data() > item:
stop = True
else:
current = current.get_next()
return found
def add(self,item):
current = self.head#指針1
previous = None#p2
stop = False
while current != None and not stop:
#發(fā)現(xiàn)插入位置
if current.get_data() > item:
stop = True
else:
previous = current
current = current.get_next()
temp = Node(item)
#插在表頭
if previous == None:
temp.set_next(self.head)
self.head = temp
#插在表中
else:
temp.set_next(current)
previous.set_next(temp)
def size(self):
current = self.head
count = 0
while current != None:
count += 1
current = current.get_next()
return count
def remove(self, item):
current = self.head
previous = None
found = False
while not found and current != None:
if current.get_data() == item:
found = True
else:
previous = current
current = current.get_next()
if found:
if previous == None:
self.head = current.get_next()
else:
previous.set_next(current.get_next())
def traverse(self):
current = self.head
while current != None:
print(current.get_data())
current = current.get_next()
ol = Orderedlist()
ol.add(7)
ol.add(9)
ol.add(6)
ol.add(8)
ol.add(10)
print(ol.search(6))
ol.traverse()
鏈接??:文章來源地址http://www.zghlxwxcb.cn/news/detail-756821.html
到了這里，關(guān)于【Python數(shù)據(jù)結(jié)構(gòu)與算法】線性結(jié)構(gòu)小結(jié)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
