?2016-2026 Matools All rights reserved,
粵ICP備17059708號(hào)
數(shù)據(jù)結(jié)構(gòu)作為計(jì)算機(jī)基礎(chǔ)的必修內(nèi)容，也是很多大型互聯(lián)網(wǎng)企業(yè)面試的必考題?？上攵?，它在計(jì)算機(jī)領(lǐng)域的重要性。
然而很多計(jì)算機(jī)專業(yè)的同學(xué)，都僅僅是了解數(shù)據(jù)結(jié)構(gòu)的相關(guān)理論，卻無法用代碼實(shí)現(xiàn)各種數(shù)據(jù)結(jié)構(gòu)。
棧
class Stack(object): def __init__(self, limit=10): self.stack = [] #存放元素
self.limit = limit #棧容量極限 def push(self, data): #判斷棧是否溢出 if len(self.stack) >=
self.limit: print('StackOverflowError') pass self.stack.append(data) def
pop(self): if self.stack: return self.stack.pop() else: raise IndexError('pop
from an empty stack') #空棧不能被彈出 def peek(self): #查看堆棧的最上面的元素 if self.stack:
return self.stack[-1] def is_empty(self): #判斷棧是否為空 return not bool(self.stack)
def size(self): #返回棧的大小 return len(self.stack)
單鏈表
class Node: def __init__(self, data): self.data = data self.next = None class
Linked_List: def __init__(self): self.head = None def initlist(self,data_list):
#鏈表初始化函數(shù) self.head=Node(data_list[0]) #創(chuàng)建頭結(jié)點(diǎn) temp=self.head for i in
data_list[1:]: #逐個(gè)為 data 內(nèi)的數(shù)據(jù)創(chuàng)建結(jié)點(diǎn), 建立鏈表 node=Node(i) temp.next=node
temp=temp.next # def is_empty(self): #判斷鏈表是否為空 if self.head.next==None:
print("Linked_list is empty") return True else: return False def
get_length(self): #獲取鏈表的長(zhǎng)度 temp=self.head #臨時(shí)變量指向隊(duì)列頭部 length=0 #計(jì)算鏈表的長(zhǎng)度變量 while
temp!=None: length=length+1 temp=temp.next return length #返回鏈表的長(zhǎng)度 def
insert(self,key,value): #鏈表插入數(shù)據(jù)函數(shù) if key<0 or key>self.get_length()-1:
print("insert error") temp=self.head i=0 while i<=key: #遍歷找到索引值為 key 的結(jié)點(diǎn)后,
在其后面插入結(jié)點(diǎn) pre=temp temp=temp.next i=i+1 node=Node(value) pre.next=node
node.next=temp def print_list(self): #遍歷鏈表，并將元素依次打印出來 print("linked_list:")
temp=self.head new_list=[] while temp is not None: new_list.append(temp.data)
temp=temp.next print(new_list) def remove(self,key): #鏈表刪除數(shù)據(jù)函數(shù) if key<0 or
key>self.get_length()-1: print("insert error") i=0 temp=self.head while temp
!=None: #遍歷找到索引值為 key 的結(jié)點(diǎn) pre=temp temp=temp.next i=i+1 if i==key:
pre.next=temp.next temp=None return True pre.next=None def reverse(self):
#將鏈表反轉(zhuǎn) prev = None current = self.head while current: next_node = current.next
current.next = prev prev = current current = next_node self.head = prev
雙鏈表
class Node(object): # 雙向鏈表節(jié)點(diǎn) def __init__(self, item): self.item = item
self.next = None self.prev = None class DLinkList(object): # 雙向鏈表 def
__init__(self): self._head = None def is_empty(self): # 判斷鏈表是否為空 return
self._head == None def get_length(self): # 返回鏈表的長(zhǎng)度 cur = self._head count = 0
while cur != None: count=count+1 cur = cur.next return count def travel(self):
# 遍歷鏈表 cur = self._head while cur != None: print(cur.item) cur = cur.next
print("") def add(self, item): # 頭部插入元素 node = Node(item) if self.is_empty(): #
如果是空鏈表，將_head指向node self._head = node else: # 將node的next指向_head的頭節(jié)點(diǎn) node.next =
self._head # 將_head的頭節(jié)點(diǎn)的prev指向node self._head.prev = node # 將_head 指向node
self._head = node def append(self, item): # Python學(xué)習(xí)交流QQ群：857662006 # 尾部插入元素
node = Node(item) if self.is_empty(): # 如果是空鏈表，將_head指向node self._head = node
else: # 移動(dòng)到鏈表尾部 cur = self._head while cur.next != None: cur = cur.next #
將尾節(jié)點(diǎn)cur的next指向node cur.next = node # 將node的prev指向cur node.prev = cur def
search(self, item): # 查找元素是否存在 cur = self._head while cur != None: if cur.item
== item: return True cur = cur.next return False def insert(self, pos, item): #
在指定位置添加節(jié)點(diǎn) if pos <= 0: self.add(item) elif pos > (self.length()-1):
self.append(item) else: node = Node(item) cur = self._head count = 0 #
移動(dòng)到指定位置的前一個(gè)位置 while count < (pos-1): count += 1 cur = cur.next #
將node的prev指向cur node.prev = cur # 將node的next指向cur的下一個(gè)節(jié)點(diǎn) node.next = cur.next #
將cur的下一個(gè)節(jié)點(diǎn)的prev指向node cur.next.prev = node # 將cur的next指向node cur.next = node
def remove(self, item): # 刪除元素 if self.is_empty(): return else: cur =
self._head if cur.item == item: # 如果首節(jié)點(diǎn)的元素即是要?jiǎng)h除的元素 if cur.next == None: #
如果鏈表只有這一個(gè)節(jié)點(diǎn) self._head = None else: # 將第二個(gè)節(jié)點(diǎn)的prev設(shè)置為None cur.next.prev = None #
將_head指向第二個(gè)節(jié)點(diǎn) self._head = cur.next return while cur != None: if cur.item ==
item: # 將cur的前一個(gè)節(jié)點(diǎn)的next指向cur的后一個(gè)節(jié)點(diǎn) cur.prev.next = cur.next #
將cur的后一個(gè)節(jié)點(diǎn)的prev指向cur的前一個(gè)節(jié)點(diǎn) cur.next.prev = cur.prev break cur = cur.next
隊(duì)列（鏈表形式實(shí)現(xiàn)）
class Node(object): def __init__(self,elem,next=None): self.elem = elem
#表示對(duì)應(yīng)的元素值 self.next=next #表示下一個(gè)鏈接的鏈點(diǎn) class Queue(object): def __init__(self):
self.head = None #頭部鏈點(diǎn)為 None self.rear = None #尾部鏈點(diǎn)為 None def is_empty(self):
return self.head is None #判斷隊(duì)列是否為空 def enqueue(self, elem): p = Node(elem)
#初始化一個(gè)新的點(diǎn) if self.is_empty(): #Python學(xué)習(xí)交流QQ群：857662006 self.head = p #隊(duì)列頭部為新的鏈點(diǎn)
self.rear = p #隊(duì)列尾部為新的鏈點(diǎn) else: self.rear.next = p #隊(duì)列尾部的后繼是這個(gè)新的點(diǎn) self.rear =p
#然后讓隊(duì)列尾部指針指向這個(gè)新的點(diǎn) def dequeue(self): if self.is_empty(): #判斷隊(duì)列是否為空
print('Queue_is_empty') #若隊(duì)列為空，則退出 dequeue 操作 else: result = self.head.elem
#result為隊(duì)列頭部元素 self.head = self.head.next #改變隊(duì)列頭部指針位置 return result #返回隊(duì)列頭部元素
def peek(self): if self.is_empty(): #判斷隊(duì)列是否為空 print('NOT_FOUND') #為空則返回
NOT_FOUND else: return self.head.elem #返回隊(duì)列頭部元素 def print_queue(self):
print("queue:") temp=self.head myqueue=[] #暫時(shí)存放隊(duì)列數(shù)據(jù) while temp is not None:
myqueue.append(temp.elem) temp=temp.next print(myqueue)
隊(duì)列（數(shù)組形式實(shí)現(xiàn)）
class Queue(): def __init__(self): self.entries = [] #表示隊(duì)列內(nèi)的參數(shù) self.length = 0
#表示隊(duì)列的長(zhǎng)度 self.front=0 #表示隊(duì)列頭部位置 def enqueue(self, item):
self.entries.append(item) #添加元素到隊(duì)列里面 self.length = self.length + 1 #隊(duì)列長(zhǎng)度增加 1
def dequeue(self): self.length = self.length - 1 #隊(duì)列的長(zhǎng)度減少 1 dequeued =
self.entries[self.front] #隊(duì)首元素為dequeued self.front-=1 #隊(duì)首的位置減少1 self.entries =
self.entries[self.front:] #隊(duì)列的元素更新為退隊(duì)之后的隊(duì)列 return dequeued def peek(self):
return self.entries[0] #直接返回隊(duì)列的隊(duì)首元素
二叉樹
class Node(object): def __init__(self,item): self.item=item #表示對(duì)應(yīng)的元素
self.left=None #表示左節(jié)點(diǎn) self.right=None #表示右節(jié)點(diǎn) def __str__(self): return
str(self.item) #print 一個(gè) Node 類時(shí)會(huì)打印 __str__ 的返回值 class Tree(object):
#Python學(xué)習(xí)交流QQ群：857662006 def __init__(self): self.root=Node('root') #根節(jié)點(diǎn)定義為
root 永不刪除，作為哨兵使用。 def add(self,item): node = Node(item) if self.root is None:
#如果二叉樹為空，那么生成的二叉樹最終為新插入樹的點(diǎn) self.root = node else: q = [self.root] #
將q列表，添加二叉樹的根節(jié)點(diǎn) while True: pop_node = q.pop(0) if pop_node.left is None:
#左子樹為空則將點(diǎn)添加到左子樹 pop_node.left = node return elif pop_node.right is None:
#右子樹為空則將點(diǎn)添加到右子樹 pop_node.right = node return else: q.append(pop_node.left)
q.append(pop_node.right) def get_parent(self, item): if self.root.item == item:
return None # 根節(jié)點(diǎn)沒有父節(jié)點(diǎn) tmp = [self.root] # 將tmp列表，添加二叉樹的根節(jié)點(diǎn) while tmp: pop_node
= tmp.pop(0) if pop_node.left and pop_node.left.item == item: #某點(diǎn)的左子樹為尋找的點(diǎn)
return pop_node #返回某點(diǎn)，即為尋找點(diǎn)的父節(jié)點(diǎn) if pop_node.right and pop_node.right.item ==
item: #某點(diǎn)的右子樹為尋找的點(diǎn) return pop_node #返回某點(diǎn)，即為尋找點(diǎn)的父節(jié)點(diǎn) if pop_node.left is not
None: #添加tmp 元素 tmp.append(pop_node.left) if pop_node.right is not None:
tmp.append(pop_node.right) return None def delete(self, item): if self.root is
None: # 如果根為空，就什么也不做 return False parent = self.get_parent(item) if parent:
del_node = parent.left if parent.left.item == item else parent.right # 待刪除節(jié)點(diǎn) if
del_node.left is None: if parent.left.item == item: parent.left =
del_node.right else: parent.right = del_node.right del del_node return True
elif del_node.right is None: if parent.left.item == item: parent.left =
del_node.left else: parent.right = del_node.left del del_node return True else:
# 左右子樹都不為空 tmp_pre = del_node tmp_next = del_node.right if tmp_next.left is
None: # 替代 tmp_pre.right = tmp_next.right tmp_next.left = del_node.left
tmp_next.right = del_node.right else: while tmp_next.left: # 讓tmp指向右子樹的最后一個(gè)葉子
tmp_pre = tmp_next tmp_next = tmp_next.left # 替代 tmp_pre.left = tmp_next.right
tmp_next.left = del_node.left tmp_next.right = del_node.right if
parent.left.item == item: parent.left = tmp_next else: parent.right = tmp_next
del del_node return True else: return False
字典樹
class TrieNode: def __init__(self): self.nodes = dict() # 構(gòu)建字典 self.is_leaf =
False def insert(self, word: str): curr = self for char in word: if char not in
curr.nodes: curr.nodes[char] = TrieNode() curr = curr.nodes[char] curr.is_leaf
= True def insert_many(self, words: [str]): for word in words:
self.insert(word) def search(self, word: str): curr = self for char in word: if
char not in curr.nodes: return False curr = curr.nodes[char] return curr.is_leaf
堆
class heap(object): def __init__(self): #初始化一個(gè)空堆，使用數(shù)組來在存放堆元素，節(jié)省存儲(chǔ)
self.data_list = [] def get_parent_index(self,index): #返回父節(jié)點(diǎn)的下標(biāo) if index == 0
or index > len(self.data_list) -1: return None else: return (index -1) >> 1 def
swap(self,index_a,index_b): #交換數(shù)組中的兩個(gè)元素 #Python學(xué)習(xí)交流QQ群：857662006
self.data_list[index_a],self.data_list[index_b] =
self.data_list[index_b],self.data_list[index_a] def insert(self,data):
#先把元素放在最后，然后從后往前依次堆化 #這里以大頂堆為例，如果插入元素比父節(jié)點(diǎn)大，則交換，直到最后 self.data_list.append(data)
index = len(self.data_list) -1 parent = self.get_parent_index(index)
#循環(huán)，直到該元素成為堆頂，或小于父節(jié)點(diǎn)（對(duì)于大頂堆) while parent is not None and self.data_list[parent]
< self.data_list[index]: #交換操作 self.swap(parent,index) index = parent parent =
self.get_parent_index(parent) def removeMax(self):
#刪除堆頂元素，然后將最后一個(gè)元素放在堆頂，再從上往下依次堆化 remove_data = self.data_list[0]
self.data_list[0] = self.data_list[-1] del self.data_list[-1] #堆化
self.heapify(0) return remove_data def heapify(self,index): #從上往下堆化，從index
開始堆化操作 (大頂堆) total_index = len(self.data_list) -1 while True: maxvalue_index =
index if 2*index +1 <= total_index and self.data_list[2*index +1] >
self.data_list[maxvalue_index]: maxvalue_index = 2*index +1 if 2*index +2 <=
total_index and self.data_list[2*index +2] > self.data_list[maxvalue_index]:
maxvalue_index = 2*index +2 if maxvalue_index == index: break
self.swap(index,maxvalue_index) index = maxvalue_index
熱門工具 換一換