使用python實(shí)現(xiàn)數(shù)組、鏈表、隊(duì)列、棧的方法
引言
什么是數(shù)據(jù)結(jié)構(gòu)?
- 數(shù)據(jù)結(jié)構(gòu)是指相互之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合和該集合中數(shù)據(jù)元素之間的關(guān)系組成。
- 簡單來說,數(shù)據(jù)結(jié)構(gòu)就是設(shè)計(jì)數(shù)據(jù)以何種方式組織并存儲在計(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)類型。
實(shí)現(xiàn)
class Array(object): def __init__(self, size=32): """ :param size: 長度 """ self._size = size self._items = [None] * size # 在執(zhí)行array[key]時(shí)執(zhí)行 def __getitem__(self, index): return self._items[index] # 在執(zhí)行array[key] = value 時(shí)執(zhí)行 def __setitem__(self, index, value): self._items[index] = value # 在執(zhí)行l(wèi)en(array) 時(shí)執(zhí)行 def __len__(self): return self._size # 清空數(shù)組 def clear(self, value=None): for i in range(len(self._items)): self._items[i] = value # 在遍歷時(shí)執(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é)點(diǎn),包含有數(shù)據(jù)域value和指向下一個節(jié)點(diǎn)的指針next。
通過各個節(jié)點(diǎn)直接的相互鏈接,最終串成一個鏈表。
實(shí)現(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é)點(diǎn) self.root = Node() # 尾節(jié)點(diǎn)始終指向最后一個節(jié)點(diǎn) 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é)點(diǎn) node = Node(value) tail_node = self.tail_node # 判斷尾節(jié)點(diǎn)是否為空 if tail_node is None: # 還沒有 append 過,length = 0, 追加到 root 后 self.root.next = node else: # 否則追加到最后一個節(jié)點(diǎn)的后邊,并更新最后一個節(jié)點(diǎn)是 append 的節(jié)點(diǎn) tail_node.next = node # 把尾節(jié)點(diǎn)指向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é)點(diǎn) node = Node(value) # 鏈表為空,則直接添加設(shè)置 if self.tail_node is None: self.tail_node = node # 設(shè)置頭節(jié)點(diǎn)為根節(jié)點(diǎn)的下一個節(jié)點(diǎn) head_node = self.root.next # 把根節(jié)點(diǎn)的下一個節(jié)點(diǎn)指向node self.root.next = node # 把node的下一個節(jié)點(diǎn)指向原頭節(jié)點(diǎn) node.next = head_node # 長度加一 self.length += 1 # 遍歷節(jié)點(diǎn) def iter_node(self): # 第一個節(jié)點(diǎn) current_node = self.root.next # 不是尾節(jié)點(diǎn)就一直遍歷 while current_node is not self.tail_node: yield current_node # 移動到下一個節(jié)點(diǎn) current_node = current_node.next # 尾節(jié)點(diǎn) if current_node is not None: yield current_node # 實(shí)現(xiàn)遍歷方法 def __iter__(self): for node in self.iter_node(): yield node.value # 刪除指定元素 def remove(self, value): # 刪除一個值為value的節(jié)點(diǎn),只要使該節(jié)點(diǎn)的前一個節(jié)點(diǎn)的next指向該節(jié)點(diǎn)的下一個 # 定義上一個節(jié)點(diǎn) perv_node = self.root # 遍歷鏈表 for current_node in self.iter_node(): if current_node.value == value: # 把上一個節(jié)點(diǎn)的next指向當(dāng)前節(jié)點(diǎn)的下一個節(jié)點(diǎn) perv_node.next = current_node.next # 判斷當(dāng)前節(jié)點(diǎn)是否是尾節(jié)點(diǎn) if current_node is self.tail_node: # 更新尾節(jié)點(diǎn) tail_node # 如果第一個節(jié)點(diǎn)就找到了,把尾節(jié)點(diǎn)設(shè)為空 if perv_node is self.root: self.tail_node = None else: self.tail_node = perv_node # 刪除節(jié)點(diǎn),長度減一,刪除成功返回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é)點(diǎn) def popleft(self): # 鏈表為空 if self.root.next is None: raise Exception("pop from empty LinkedList") # 找到第一個節(jié)點(diǎn) head_node = self.root.next # 把根節(jié)點(diǎn)的下一個節(jié)點(diǎn),指向第一個節(jié)點(diǎn)的下一個節(jié)點(diǎn) self.root.next = head_node.next # 獲取刪除節(jié)點(diǎn)的value value = head_node.value # 如果第一個節(jié)點(diǎn)是尾節(jié)點(diǎn), 則把尾節(jié)點(diǎn)設(shè)為None if head_node is self.tail_node: self.tail_node = None # 長度減一,刪除節(jié)點(diǎn),返回該節(jié)點(diǎn)的值 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é)點(diǎn)為當(dāng)前節(jié)點(diǎn),并把尾節(jié)點(diǎn)指向當(dāng)前節(jié)點(diǎn) current_node = self.root.next self.tail_node = current_node perv_node = None while current_node: # 下一個節(jié)點(diǎn) next_node = current_node.next # 當(dāng)前節(jié)點(diǎn)的下一個節(jié)點(diǎn)指向perv_node current_node.next = perv_node # 當(dāng)前節(jié)點(diǎn)的下一個節(jié)點(diǎn)為空,則把根節(jié)點(diǎn)的next指向當(dāng)前節(jié)點(diǎn) if next_node is None: self.root.next = current_node # 把當(dāng)前節(jié)點(diǎn)賦值給perv_node perv_node = current_node # 把下一個節(jié)點(diǎn)賦值為當(dāng)前節(jié)點(diǎn) 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é)點(diǎn)有兩個指針,一個指向后面節(jié)點(diǎn)、一個指向前面節(jié)點(diǎn)。
循環(huán)鏈表實(shí)現(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
隊(duì)列
隊(duì)列(Queue)是一個數(shù)據(jù)集合,僅允許在列表的一端進(jìn)行插入,另一端進(jìn)行刪除。
進(jìn)行插入的一端成為隊(duì)尾(rear),插入動作稱為進(jìn)隊(duì)或入隊(duì)。
進(jìn)行刪除的一端稱為隊(duì)頭(front),刪除動作稱為出隊(duì)。
隊(duì)列的性質(zhì):先進(jìn)先出(First-in, First-out)。
基于數(shù)組實(shí)現(xiàn)環(huán)形隊(duì)列
class Array(object): def __init__(self, size=32): """ :param size: 長度 """ self._size = size self._items = [None] * size # 在執(zhí)行array[key]時(shí)執(zhí)行 def __getitem__(self, index): return self._items[index] # 在執(zhí)行array[key] = value 時(shí)執(zhí)行 def __setitem__(self, index, value): self._items[index] = value # 在執(zhí)行l(wèi)en(array) 時(shí)執(zhí)行 def __len__(self): return self._size # 清空數(shù)組 def clear(self, value=None): for i in range(len(self._items)): self._items[i] = value # 在遍歷時(shí)執(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 # 入隊(duì) def push(self, value): if len(self) >= self.maxsize: raise Exception("Queue is full") self.array[self.head % self.maxsize] = value self.head += 1 # 出隊(duì) 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
基于雙向鏈表實(shí)現(xiàn)雙向隊(duì)列
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 # 雙向隊(duì)列 class Deque(CircularDoubleLinkedList): # 從右邊出隊(duì) 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 # 從左邊出隊(duì) 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
雙向隊(duì)列
兩端都可以進(jìn)行插入,刪除。
基于雙向鏈表實(shí)現(xiàn)雙向隊(duì)列
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 # 雙向隊(duì)列 class Deque(CircularDoubleLinkedList): # 從右邊出隊(duì) 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 # 從左邊出隊(duì) 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
雙向隊(duì)列的使用
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ù)集合,可以理解為只能在一端插入或刪除操作的鏈表。
棧的特點(diǎn):后進(jìn)先出(Last-in, First-out)
棧的概念:
- 棧頂
- 棧底
棧的基本操作:
- 進(jìn)棧(壓棧):push
- 出棧:pop
基于雙向隊(duì)列實(shí)現(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實(shí)現(xiàn)數(shù)組、鏈表、隊(duì)列、棧的方法,希望對大家有所幫助,如果大家有任何疑問請給我留言,小編會及時(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實(shí)現(xiàn)棧和隊(duì)列的簡單操作方法示例
- Python 實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)-堆棧和隊(duì)列的操作方法
- Python雙端隊(duì)列deque的實(shí)現(xiàn)
- python雙端隊(duì)列原理、實(shí)現(xiàn)與使用方法分析
- python數(shù)據(jù)結(jié)構(gòu)之棧、隊(duì)列及雙端隊(duì)列
相關(guān)文章
Python實(shí)現(xiàn)簡單的四則運(yùn)算計(jì)算器
相信大家在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)時(shí),就學(xué)習(xí)了簡單四則運(yùn)算表達(dá)式求解的一個算法,可惜一直沒有自己動手實(shí)現(xiàn)過這個算法。最近重拾數(shù)據(jù)結(jié)構(gòu)與算法,恰巧又正在用Python比較頻繁,所幸就用它來實(shí)現(xiàn)這個算法,雖然網(wǎng)上有很多代碼,不過作為一個學(xué)習(xí)者,還是應(yīng)當(dāng)親自動手實(shí)現(xiàn)。2016-11-11python執(zhí)行系統(tǒng)命令4種方法與比較
這篇文章主要介紹了python執(zhí)行系統(tǒng)命令4種方法與比較,需要的朋友可以參考下2021-04-04Python實(shí)現(xiàn)RGB與HSI顏色空間的互換方式
今天小編就為大家分享一篇Python實(shí)現(xiàn)RGB與HSI顏色空間的互換方式,具有很好的參考價(jià)值,希望對大家有所幫助。一起跟隨小編過來看看吧2019-11-11Python將json文件寫入ES數(shù)據(jù)庫的方法
這篇文章主要介紹了Python將json文件寫入ES數(shù)據(jù)庫的方法,本文給大家介紹的非常詳細(xì),具有一定的參考借鑒價(jià)值 ,需要的朋友可以參考下2019-04-04