使用python實現(xiàn)數(shù)組、鏈表、隊列、棧的方法
更新時間：2019年12月20日 09:27:52 作者：學(xué)海無涯苦作舟
數(shù)據(jù)結(jié)構(gòu)是指相互之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合和該集合中數(shù)據(jù)元素之間的關(guān)系組成。這篇文章主要介紹了使用python實現(xiàn)數(shù)組、鏈表、隊列、棧的相關(guān)知識,需要的朋友可以參考下
引言
什么是數(shù)據(jù)結(jié)構(gòu)？
- 數(shù)據(jù)結(jié)構(gòu)是指相互之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合和該集合中數(shù)據(jù)元素之間的關(guān)系組成。
- 簡單來說，數(shù)據(jù)結(jié)構(gòu)就是設(shè)計數(shù)據(jù)以何種方式組織并存儲在計算機(jī)中。
- 比如：列表，集合和字典等都是數(shù)據(jù)結(jié)構(gòu)
- N.Wirth：“程序=數(shù)據(jù)結(jié)構(gòu)+算法”
數(shù)據(jù)結(jié)構(gòu)按照其邏輯結(jié)構(gòu)可分為線性結(jié)構(gòu)、樹結(jié)構(gòu)、圖結(jié)構(gòu)
- 線性結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在一對一的互相關(guān)系。
- 樹結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在一對多的互相關(guān)系。
- 圖結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在多對多的互相關(guān)系。
數(shù)組
在python中是沒有數(shù)組的，有的是列表，它是一種基本的數(shù)據(jù)結(jié)構(gòu)類型。
實現(xiàn)
class Array(object): def __init__(self, size=32): """ :param size: 長度 """ self._size = size self._items = [None] * size # 在執(zhí)行array[key]時執(zhí)行 def __getitem__(self, index): return self._items[index] # 在執(zhí)行array[key] = value 時執(zhí)行 def __setitem__(self, index, value): self._items[index] = value # 在執(zhí)行l(wèi)en(array) 時執(zhí)行 def __len__(self): return self._size # 清空數(shù)組 def clear(self, value=None): for i in range(len(self._items)): self._items[i] = value # 在遍歷時執(zhí)行 def __iter__(self): for item in self._items: yield item
使用
a = Array(4) a[0] = 1 print(a[0]) # 1 a.clear() print(a[0]) # None a[0] = 1 a[1] = 2 a[3] = 4 for i in a: print(i) # 1, 2, None, 4
鏈表
鏈表中每一個元素都是一個對象，每一個對象被稱為節(jié)點，包含有數(shù)據(jù)域value和指向下一個節(jié)點的指針next。
通過各個節(jié)點直接的相互鏈接，最終串成一個鏈表。
實現(xiàn)
class Node(object):
def __init__(self, value=None, next=None):
self.value, self.next = value, next
class LinkedList(object):
def __init__(self, size=None):
"""
:param size: int or None, 如果None，則該鏈表可以無限擴(kuò)充
"""
self.size = size
# 定義一個根節(jié)點
self.root = Node()
# 尾節(jié)點始終指向最后一個節(jié)點
self.tail_node = None
self.length = 0
def __len__(self):
return self.length
def append(self, value):
# size 不為 None, 且長度大于等于size則鏈表已滿
if self.size and len(self) >= self.size:
raise Exception("LinkedList is full")
# 構(gòu)建節(jié)點
node = Node(value)
tail_node = self.tail_node
# 判斷尾節(jié)點是否為空
if tail_node is None:
# 還沒有 append 過，length = 0， 追加到 root 后
self.root.next = node
else:
# 否則追加到最后一個節(jié)點的后邊，并更新最后一個節(jié)點是 append 的節(jié)點
tail_node.next = node
# 把尾節(jié)點指向node
self.tail_node = node
# 長度加一
self.length += 1
# 往左邊添加
def append_left(self, value):
if self.size and len(self) >= self.size:
raise Exception("LinkedList is full")
# 構(gòu)建節(jié)點
node = Node(value)
# 鏈表為空，則直接添加設(shè)置
if self.tail_node is None:
self.tail_node = node
# 設(shè)置頭節(jié)點為根節(jié)點的下一個節(jié)點
head_node = self.root.next
# 把根節(jié)點的下一個節(jié)點指向node
self.root.next = node
# 把node的下一個節(jié)點指向原頭節(jié)點
node.next = head_node
# 長度加一
self.length += 1
# 遍歷節(jié)點
def iter_node(self):
# 第一個節(jié)點
current_node = self.root.next
# 不是尾節(jié)點就一直遍歷
while current_node is not self.tail_node:
yield current_node
# 移動到下一個節(jié)點
current_node = current_node.next
# 尾節(jié)點
if current_node is not None:
yield current_node
# 實現(xiàn)遍歷方法
def __iter__(self):
for node in self.iter_node():
yield node.value
# 刪除指定元素
def remove(self, value):
# 刪除一個值為value的節(jié)點，只要使該節(jié)點的前一個節(jié)點的next指向該節(jié)點的下一個
# 定義上一個節(jié)點
perv_node = self.root
# 遍歷鏈表
for current_node in self.iter_node():
if current_node.value == value:
# 把上一個節(jié)點的next指向當(dāng)前節(jié)點的下一個節(jié)點
perv_node.next = current_node.next
# 判斷當(dāng)前節(jié)點是否是尾節(jié)點
if current_node is self.tail_node:
# 更新尾節(jié)點 tail_node
# 如果第一個節(jié)點就找到了，把尾節(jié)點設(shè)為空
if perv_node is self.root:
self.tail_node = None
else:
self.tail_node = perv_node
# 刪除節(jié)點，長度減一，刪除成功返回1
del current_node
self.length -= 1
return 1
else:
perv_node = current_node
# 沒找到返回-1
return -1
# 查找元素，找到返回下標(biāo)，沒找到返回-1
def find(self, value):
index = 0
# 遍歷鏈表，找到返回index,沒找到返回-1
for node in self.iter_node():
if node.value == value:
return index
index += 1
return -1
# 刪除第一個節(jié)點
def popleft(self):
# 鏈表為空
if self.root.next is None:
raise Exception("pop from empty LinkedList")
# 找到第一個節(jié)點
head_node = self.root.next
# 把根節(jié)點的下一個節(jié)點，指向第一個節(jié)點的下一個節(jié)點
self.root.next = head_node.next
# 獲取刪除節(jié)點的value
value = head_node.value
# 如果第一個節(jié)點是尾節(jié)點, 則把尾節(jié)點設(shè)為None
if head_node is self.tail_node:
self.tail_node = None
# 長度減一，刪除節(jié)點，返回該節(jié)點的值
self.length -= 1
del head_node
return value
# 清空鏈表
def clear(self):
for node in self.iter_node():
del node
self.root.next = None
self.tail_node = None
self.length = 0
# 反轉(zhuǎn)鏈表
def reverse(self):
# 第一個節(jié)點為當(dāng)前節(jié)點，并把尾節(jié)點指向當(dāng)前節(jié)點
current_node = self.root.next
self.tail_node = current_node
perv_node = None
while current_node:
# 下一個節(jié)點
next_node = current_node.next
# 當(dāng)前節(jié)點的下一個節(jié)點指向perv_node
current_node.next = perv_node
# 當(dāng)前節(jié)點的下一個節(jié)點為空，則把根節(jié)點的next指向當(dāng)前節(jié)點
if next_node is None:
self.root.next = current_node
# 把當(dāng)前節(jié)點賦值給perv_node
perv_node = current_node
# 把下一個節(jié)點賦值為當(dāng)前節(jié)點
current_node = next_node
使用
ll = LinkedList() ll.append(0) ll.append(1) ll.append(2) ll.append(3) print(len(ll)) # 4 print(ll.find(2)) # 2 print(ll.find(-1)) # -1 ll.clear() print(len(ll)) # 0 print(list(ll)) # []
循環(huán)鏈表
雙鏈表中每一個節(jié)點有兩個指針，一個指向后面節(jié)點、一個指向前面節(jié)點。
循環(huán)鏈表實現(xiàn)
class Node(object):
def __init__(self, value=None, prev=None, next=None):
self.value = value
self.prev = prev
self.next = next
class CircularDoubleLinkedList(object):
"""
雙向循環(huán)鏈表
"""
def __init__(self, maxsize=None):
self.maxsize = maxsize
node = Node()
node.prev = node
node.next = node
self.root = node
self.length = 0
def __len__(self):
return self.length
def head_node(self):
return self.root.next
def tail_node(self):
return self.root.prev
# 遍歷
def iter_node(self):
if self.root.next is self.root:
return
current_node = self.root.next
while current_node.next is not self.root:
yield current_node
current_node = current_node.next
yield current_node
def __iter__(self):
for node in self.iter_node():
yield node.value
# 反序遍歷
def iter_node_reverse(self):
if self.root.prev is self.root:
return
current_node = self.root.prev
while current_node.prev is not self.root:
yield current_node
current_node = current_node.prev
yield current_node
def append(self, value):
if self.maxsize is not None and len(self) >= self.maxsize:
raise Exception("LinkedList is full")
node = Node(value)
tail_node = self.tail_node() or self.root
tail_node.next = node
node.prev = tail_node
node.next = self.root
self.root.prev = node
self.length += 1
def append_left(self, value):
if self.maxsize is not None and len(self) >= self.maxsize:
raise Exception("LinkedList is full")
node = Node(value)
if self.root.next is self.root:
self.root.next = node
node.prev = self.root
node.next = self.root
self.root.prev = node
else:
node.next = self.root.next
self.root.next.prev = node
self.root.next = node
node.prev = self.root
self.length += 1
def remove(self, node):
if node is self.root:
return
node.next.prev = node.prev
node.prev.next = node.next
self.length -= 1
return node
循環(huán)鏈表的使用
dll = CircularDoubleLinkedList() dll.append(0) dll.append(1) dll.append(2) assert list(dll) == [0, 1, 2] print(list(dll)) # [0, 1, 2] print([node.value for node in dll.iter_node()]) # [0, 1, 2] print([node.value for node in dll.iter_node_reverse()]) # [2, 1, 0] headnode = dll.head_node() print(headnode.value) # 0 dll.remove(headnode) print(len(dll)) # 2
隊列
隊列(Queue)是一個數(shù)據(jù)集合，僅允許在列表的一端進(jìn)行插入，另一端進(jìn)行刪除。
進(jìn)行插入的一端成為隊尾(rear)，插入動作稱為進(jìn)隊或入隊。
進(jìn)行刪除的一端稱為隊頭(front)，刪除動作稱為出隊。
隊列的性質(zhì)：先進(jìn)先出(First-in, First-out)。
基于數(shù)組實現(xiàn)環(huán)形隊列
class Array(object):
def __init__(self, size=32):
"""
:param size: 長度
"""
self._size = size
self._items = [None] * size
# 在執(zhí)行array[key]時執(zhí)行
def __getitem__(self, index):
return self._items[index]
# 在執(zhí)行array[key] = value 時執(zhí)行
def __setitem__(self, index, value):
self._items[index] = value
# 在執(zhí)行l(wèi)en(array) 時執(zhí)行
def __len__(self):
return self._size
# 清空數(shù)組
def clear(self, value=None):
for i in range(len(self._items)):
self._items[i] = value
# 在遍歷時執(zhí)行
def __iter__(self):
for item in self._items:
yield item
class ArrayQueue(object):
def __init__(self, maxsize):
self.maxsize = maxsize
self.array = Array(maxsize)
self.head = 0
self.tail = 0
def __len__(self):
return self.head - self.tail
# 入隊
def push(self, value):
if len(self) >= self.maxsize:
raise Exception("Queue is full")
self.array[self.head % self.maxsize] = value
self.head += 1
# 出隊
def pop(self):
value = self.array[self.tail % self.maxsize]
self.tail += 1
return value
使用
size = 5 q = ArrayQueue(size) for i in range(size): q.push(i) print(len(q)) # 5 print(q.pop()) # 0 print(q.pop()) # 1
基于雙向鏈表實現(xiàn)雙向隊列
class Node(object):
def __init__(self, value=None, prev=None, next=None):
self.value = value
self.prev = prev
self.next = next
class CircularDoubleLinkedList(object):
"""
雙向循環(huán)鏈表
"""
def __init__(self, maxsize=None):
self.maxsize = maxsize
node = Node()
node.prev = node
node.next = node
self.root = node
self.length = 0
def __len__(self):
return self.length
def head_node(self):
return self.root.next
def tail_node(self):
return self.root.prev
# 遍歷
def iter_node(self):
if self.root.next is self.root:
return
current_node = self.root.next
while current_node.next is not self.root:
yield current_node
current_node = current_node.next
yield current_node
def __iter__(self):
for node in self.iter_node():
yield node.value
# 反序遍歷
def iter_node_reverse(self):
if self.root.prev is self.root:
return
current_node = self.root.prev
while current_node.prev is not self.root:
yield current_node
current_node = current_node.prev
yield current_node
def append(self, value):
if self.maxsize is not None and len(self) >= self.maxsize:
raise Exception("LinkedList is full")
node = Node(value)
tail_node = self.tail_node() or self.root
tail_node.next = node
node.prev = tail_node
node.next = self.root
self.root.prev = node
self.length += 1
def append_left(self, value):
if self.maxsize is not None and len(self) >= self.maxsize:
raise Exception("LinkedList is full")
node = Node(value)
if self.root.next is self.root:
self.root.next = node
node.prev = self.root
node.next = self.root
self.root.prev = node
else:
node.next = self.root.next
self.root.next.prev = node
self.root.next = node
node.prev = self.root
self.length += 1
def remove(self, node):
if node is self.root:
return
node.next.prev = node.prev
node.prev.next = node.next
self.length -= 1
return node
# 雙向隊列
class Deque(CircularDoubleLinkedList):
# 從右邊出隊
def pop(self):
if len(self) <= 0:
raise Exception("stark is empty!")
tail_node = self.tail_node()
value = tail_node.value
self.remove(tail_node)
return value
# 從左邊出隊
def popleft(self):
if len(self) <= 0:
raise Exception("stark is empty!")
head_node = self.head_node()
value = head_node.value
self.remove(head_node)
return value
雙向隊列
兩端都可以進(jìn)行插入，刪除。
基于雙向鏈表實現(xiàn)雙向隊列
class Node(object):
def __init__(self, value=None, prev=None, next=None):
self.value = value
self.prev = prev
self.next = next
class CircularDoubleLinkedList(object):
"""
雙向循環(huán)鏈表
"""
def __init__(self, maxsize=None):
self.maxsize = maxsize
node = Node()
node.prev = node
node.next = node
self.root = node
self.length = 0
def __len__(self):
return self.length
def head_node(self):
return self.root.next
def tail_node(self):
return self.root.prev
# 遍歷
def iter_node(self):
if self.root.next is self.root:
return
current_node = self.root.next
while current_node.next is not self.root:
yield current_node
current_node = current_node.next
yield current_node
def __iter__(self):
for node in self.iter_node():
yield node.value
# 反序遍歷
def iter_node_reverse(self):
if self.root.prev is self.root:
return
current_node = self.root.prev
while current_node.prev is not self.root:
yield current_node
current_node = current_node.prev
yield current_node
def append(self, value):
if self.maxsize is not None and len(self) >= self.maxsize:
raise Exception("LinkedList is full")
node = Node(value)
tail_node = self.tail_node() or self.root
tail_node.next = node
node.prev = tail_node
node.next = self.root
self.root.prev = node
self.length += 1
def append_left(self, value):
if self.maxsize is not None and len(self) >= self.maxsize:
raise Exception("LinkedList is full")
node = Node(value)
if self.root.next is self.root:
self.root.next = node
node.prev = self.root
node.next = self.root
self.root.prev = node
else:
node.next = self.root.next
self.root.next.prev = node
self.root.next = node
node.prev = self.root
self.length += 1
def remove(self, node):
if node is self.root:
return
node.next.prev = node.prev
node.prev.next = node.next
self.length -= 1
return node
# 雙向隊列
class Deque(CircularDoubleLinkedList):
# 從右邊出隊
def pop(self):
if len(self) <= 0:
raise Exception("stark is empty!")
tail_node = self.tail_node()
value = tail_node.value
self.remove(tail_node)
return value
# 從左邊出隊
def popleft(self):
if len(self) <= 0:
raise Exception("stark is empty!")
head_node = self.head_node()
value = head_node.value
self.remove(head_node)
return value
雙向隊列的使用
dq = Deque() dq.append(1) dq.append(2) print(list(dq)) # [1, 2] dq.appendleft(0) print(list(dq)) # [0, 1, 2] dq.pop() print(list(dq)) # [0, 1] dq.popleft() print(list(dq)) # [1] dq.pop() print(len(dq)) # 0
棧
棧(Stack)是一個數(shù)據(jù)集合，可以理解為只能在一端插入或刪除操作的鏈表。
棧的特點：后進(jìn)先出(Last-in, First-out)
棧的概念：
- 棧頂
- 棧底
棧的基本操作：
- 進(jìn)棧（壓棧）：push
- 出棧：pop
基于雙向隊列實現(xiàn)
class Node(object):
def __init__(self, value=None, prev=None, next=None):
self.value = value
self.prev = prev
self.next = next
class CircularDoubleLinkedList(object):
"""
雙向循環(huán)鏈表
"""
def __init__(self, maxsize=None):
self.maxsize = maxsize
node = Node()
node.prev = node
node.next = node
self.root = node
self.length = 0
def __len__(self):
return self.length
def head_node(self):
return self.root.next
def tail_node(self):
return self.root.prev
# 遍歷
def iter_node(self):
if self.root.next is self.root:
return
current_node = self.root.next
while current_node.next is not self.root:
yield current_node
current_node = current_node.next
yield current_node
def __iter__(self):
for node in self.iter_node():
yield node.value
# 反序遍歷
def iter_node_reverse(self):
if self.root.prev is self.root:
return
current_node = self.root.prev
while current_node.prev is not self.root:
yield current_node
current_node = current_node.prev
yield current_node
def append(self, value):
if self.maxsize is not None and len(self) >= self.maxsize:
raise Exception("LinkedList is full")
node = Node(value)
tail_node = self.tail_node() or self.root
tail_node.next = node
node.prev = tail_node
node.next = self.root
self.root.prev = node
self.length += 1
def append_left(self, value):
if self.maxsize is not None and len(self) >= self.maxsize:
raise Exception("LinkedList is full")
node = Node(value)
if self.root.next is self.root:
self.root.next = node
node.prev = self.root
node.next = self.root
self.root.prev = node
else:
node.next = self.root.next
self.root.next.prev = node
self.root.next = node
node.prev = self.root
self.length += 1
def remove(self, node):
if node is self.root:
return
node.next.prev = node.prev
node.prev.next = node.next
self.length -= 1
return node
class Deque(CircularDoubleLinkedList):
def pop(self):
if len(self) <= 0:
raise Exception("stark is empty!")
tail_node = self.tail_node()
value = tail_node.value
self.remove(tail_node)
return value
def popleft(self):
if len(self) <= 0:
raise Exception("stark is empty!")
head_node = self.head_node()
value = head_node.value
self.remove(head_node)
return value
class Stack(object):
def __init__(self):
self.deque = Deque()
# 壓棧
def push(self, value):
self.deque.append(value)
# 出棧
def pop(self):
return self.deque.pop()
使用
s = Stack() s.push(0) s.push(1) s.push(2) print(s.pop()) # 2 print(s.pop()) # 1 print(s.pop()) # 0
總結(jié)
以上所述是小編給大家介紹的使用python實現(xiàn)數(shù)組、鏈表、隊列、棧的方法，希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會及時回復(fù)大家的。在此也非常感謝大家對腳本之家網(wǎng)站的支持！
如果你覺得本文對你有幫助，歡迎轉(zhuǎn)載，煩請注明出處，謝謝！
您可能感興趣的文章:
- python數(shù)據(jù)結(jié)構(gòu)算法分析
- python數(shù)據(jù)結(jié)構(gòu)之面向?qū)ο?/a>
- python數(shù)據(jù)結(jié)構(gòu)輸入輸出及控制和異常
- python數(shù)據(jù)結(jié)構(gòu):數(shù)據(jù)類型
- Python實現(xiàn)棧和隊列的簡單操作方法示例
- Python 實現(xiàn)數(shù)據(jù)結(jié)構(gòu)-堆棧和隊列的操作方法
- Python雙端隊列deque的實現(xiàn)
- python雙端隊列原理、實現(xiàn)與使用方法分析
- python數(shù)據(jù)結(jié)構(gòu)之棧、隊列及雙端隊列
相關(guān)文章
相信大家在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)時，就學(xué)習(xí)了簡單四則運(yùn)算表達(dá)式求解的一個算法，可惜一直沒有自己動手實現(xiàn)過這個算法。最近重拾數(shù)據(jù)結(jié)構(gòu)與算法，恰巧又正在用Python比較頻繁，所幸就用它來實現(xiàn)這個算法，雖然網(wǎng)上有很多代碼，不過作為一個學(xué)習(xí)者，還是應(yīng)當(dāng)親自動手實現(xiàn)。2016-11-11
這篇文章主要介紹了簡單了解Python matplotlib線的屬性,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2019-06-06
這篇文章主要介紹了pymysql模塊的使用(增刪改查)詳解,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2019-09-09
今天小編就為大家分享一篇利用arcgis的python讀取要素的X,Y方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-12-12
python執(zhí)行系統(tǒng)命令4種方法與比較
這篇文章主要介紹了python執(zhí)行系統(tǒng)命令4種方法與比較,需要的朋友可以參考下2021-04-04
Python實現(xiàn)RGB與HSI顏色空間的互換方式
今天小編就為大家分享一篇Python實現(xiàn)RGB與HSI顏色空間的互換方式，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-11-11
這篇文章主要介紹了提高python代碼運(yùn)行效率的一些建議，幫助大家優(yōu)化python代碼，提高運(yùn)行效率，感興趣的朋友可以了解下2020-09-09
這篇文章主要介紹了Python3.5文件修改操作,結(jié)合實例形式分析了Python3.5針對txt文本文件的讀寫、修改等相關(guān)操作技巧,需要的朋友可以參考下2019-05-05
Python將json文件寫入ES數(shù)據(jù)庫的方法
這篇文章主要介紹了Python將json文件寫入ES數(shù)據(jù)庫的方法，本文給大家介紹的非常詳細(xì)，具有一定的參考借鑒價值 ,需要的朋友可以參考下2019-04-04
這篇文章主要介紹了如何使用PyCharm引入需要使用的包的方法，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-09-09