這篇文章將為大家詳細(xì)講解有關(guān)如何使用python實(shí)現(xiàn)數(shù)組、鏈表、隊(duì)列、棧,小編覺(jué)得挺實(shí)用的,因此分享給大家做個(gè)參考,希望大家閱讀完這篇文章后可以有所收獲。
創(chuàng)新互聯(lián)專注于臨猗網(wǎng)站建設(shè)服務(wù)及定制,我們擁有豐富的企業(yè)做網(wǎng)站經(jīng)驗(yàn)。 熱誠(chéng)為您提供臨猗營(yíng)銷型網(wǎng)站建設(shè),臨猗網(wǎng)站制作、臨猗網(wǎng)頁(yè)設(shè)計(jì)、臨猗網(wǎng)站官網(wǎng)定制、成都微信小程序服務(wù),打造臨猗網(wǎng)絡(luò)公司原創(chuàng)品牌,更為您提供臨猗網(wǎng)站排名全網(wǎng)營(yíng)銷落地服務(wù)。引言
什么是數(shù)據(jù)結(jié)構(gòu)?
數(shù)據(jù)結(jié)構(gòu)是指相互之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合和該集合中數(shù)據(jù)元素之間的關(guān)系組成。
簡(jiǎn)單來(lái)說(shuō),數(shù)據(jù)結(jié)構(gòu)就是設(shè)計(jì)數(shù)據(jù)以何種方式組織并存儲(chǔ)在計(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)中的元素存在一對(duì)一的互相關(guān)系。
樹結(jié)構(gòu):數(shù)據(jù)結(jié)構(gòu)中的元素存在一對(duì)多的互相關(guān)系。
圖結(jié)構(gòu):數(shù)據(jù)結(jié)構(gòu)中的元素存在多對(duì)多的互相關(guān)系。
數(shù)組
在python中是沒(méi)有數(shù)組的,有的是列表,它是一種基本的數(shù)據(jù)結(jié)構(gòu)類型。
實(shí)現(xiàn)
class Array(object): def __init__(self, size=32): """ :param size: 長(zhǎng)度 """ 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
鏈表
鏈表中每一個(gè)元素都是一個(gè)對(duì)象,每一個(gè)對(duì)象被稱為節(jié)點(diǎn),包含有數(shù)據(jù)域value和指向下一個(gè)節(jié)點(diǎn)的指針next。
通過(guò)各個(gè)節(jié)點(diǎn)直接的相互鏈接,最終串成一個(gè)鏈表。
實(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,則該鏈表可以無(wú)限擴(kuò)充 """ self.size = size # 定義一個(gè)根節(jié)點(diǎn) self.root = Node() # 尾節(jié)點(diǎn)始終指向最后一個(gè)節(jié)點(diǎn) self.tail_node = None self.length = 0 def __len__(self): return self.length def append(self, value): # size 不為 None, 且長(zhǎng)度大于等于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: # 還沒(méi)有 append 過(guò),length = 0, 追加到 root 后 self.root.next = node else: # 否則追加到最后一個(gè)節(jié)點(diǎn)的后邊,并更新最后一個(gè)節(jié)點(diǎn)是 append 的節(jié)點(diǎn) tail_node.next = node # 把尾節(jié)點(diǎn)指向node self.tail_node = node # 長(zhǎng)度加一 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)的下一個(gè)節(jié)點(diǎn) head_node = self.root.next # 把根節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指向node self.root.next = node # 把node的下一個(gè)節(jié)點(diǎn)指向原頭節(jié)點(diǎn) node.next = head_node # 長(zhǎng)度加一 self.length += 1 # 遍歷節(jié)點(diǎn) def iter_node(self): # 第一個(gè)節(jié)點(diǎn) current_node = self.root.next # 不是尾節(jié)點(diǎn)就一直遍歷 while current_node is not self.tail_node: yield current_node # 移動(dòng)到下一個(gè)節(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): # 刪除一個(gè)值為value的節(jié)點(diǎn),只要使該節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的next指向該節(jié)點(diǎn)的下一個(gè) # 定義上一個(gè)節(jié)點(diǎn) perv_node = self.root # 遍歷鏈表 for current_node in self.iter_node(): if current_node.value == value: # 把上一個(gè)節(jié)點(diǎn)的next指向當(dāng)前節(jié)點(diǎn)的下一個(gè)節(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 # 如果第一個(gè)節(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),長(zhǎng)度減一,刪除成功返回1 del current_node self.length -= 1 return 1 else: perv_node = current_node # 沒(méi)找到返回-1 return -1 # 查找元素,找到返回下標(biāo),沒(méi)找到返回-1 def find(self, value): index = 0 # 遍歷鏈表,找到返回index,沒(méi)找到返回-1 for node in self.iter_node(): if node.value == value: return index index += 1 return -1 # 刪除第一個(gè)節(jié)點(diǎn) def popleft(self): # 鏈表為空 if self.root.next is None: raise Exception("pop from empty LinkedList") # 找到第一個(gè)節(jié)點(diǎn) head_node = self.root.next # 把根節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn),指向第一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn) self.root.next = head_node.next # 獲取刪除節(jié)點(diǎn)的value value = head_node.value # 如果第一個(gè)節(jié)點(diǎn)是尾節(jié)點(diǎn), 則把尾節(jié)點(diǎn)設(shè)為None if head_node is self.tail_node: self.tail_node = None # 長(zhǎng)度減一,刪除節(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): # 第一個(gè)節(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: # 下一個(gè)節(jié)點(diǎn) next_node = current_node.next # 當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指向perv_node current_node.next = perv_node # 當(dāng)前節(jié)點(diǎn)的下一個(gè)節(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 # 把下一個(gè)節(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)鏈表
雙鏈表中每一個(gè)節(jié)點(diǎn)有兩個(gè)指針,一個(gè)指向后面節(jié)點(diǎn)、一個(gè)指向前面節(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)是一個(gè)數(shù)據(jù)集合,僅允許在列表的一端進(jìn)行插入,另一端進(jìn)行刪除。
進(jìn)行插入的一端成為隊(duì)尾(rear),插入動(dòng)作稱為進(jìn)隊(duì)或入隊(duì)。
進(jìn)行刪除的一端稱為隊(duì)頭(front),刪除動(dòng)作稱為出隊(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: 長(zhǎng)度 """ 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)是一個(gè)數(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
關(guān)于“如何使用python實(shí)現(xiàn)數(shù)組、鏈表、隊(duì)列、?!边@篇文章就分享到這里了,希望以上內(nèi)容可以對(duì)大家有一定的幫助,使各位可以學(xué)到更多知識(shí),如果覺(jué)得文章不錯(cuò),請(qǐng)把它分享出去讓更多的人看到。
網(wǎng)站標(biāo)題:如何使用python實(shí)現(xiàn)數(shù)組、鏈表、隊(duì)列、棧-創(chuàng)新互聯(lián)
文章分享:http://m.rwnh.cn/article48/dsdghp.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供外貿(mào)網(wǎng)站建設(shè)、商城網(wǎng)站、網(wǎng)站設(shè)計(jì)、App設(shè)計(jì)、網(wǎng)站改版、網(wǎng)站營(yíng)銷
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請(qǐng)盡快告知,我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如需處理請(qǐng)聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時(shí)需注明來(lái)源: 創(chuàng)新互聯(lián)
猜你還喜歡下面的內(nèi)容