常見數(shù)據(jù)結(jié)構(gòu)的 Python 實現(xiàn)（建議收藏）

數(shù)據(jù)結(jié)構(gòu)作為計算機基礎(chǔ)的必修內(nèi)容，也是很多大型互聯(lián)網(wǎng)企業(yè)面試的必考題。可想而知，它在計算機領(lǐng)域的重要性。

然而很多計算機專業(yè)的同學(xué)，都僅僅是了解數(shù)據(jù)結(jié)構(gòu)的相關(guān)理論，卻無法用代碼實現(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)

單鏈表

'''
遇到問題沒人解答？小編創(chuàng)建了一個Python學(xué)習交流QQ群：××× 
尋找有志同道合的小伙伴，互幫互助,群里還有不錯的視頻學(xué)習教程和PDF電子書！
'''
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é)點
        temp=self.head
        for i in data_list[1:]: #逐個為 data 內(nèi)的數(shù)據(jù)創(chuàng)建結(jié)點, 建立鏈表
            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):  #獲取鏈表的長度
        temp=self.head #臨時變量指向隊列頭部
        length=0 #計算鏈表的長度變量
        while temp!=None:
            length=length+1
            temp=temp.next
        return length #返回鏈表的長度
    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é)點后, 在其后面插入結(jié)點
            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é)點
            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é)點
    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):
        # 返回鏈表的長度
        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é)點
            node.next = self._head
            # 將_head的頭節(jié)點的prev指向node
            self._head.prev = node
            # 將_head 指向node
            self._head = node
    def append(self, item):
        # 尾部插入元素
        node = Node(item)
        if self.is_empty():
            # 如果是空鏈表，將_head指向node
            self._head = node
        else:
            # 移動到鏈表尾部
            cur = self._head
            while cur.next != None:
                cur = cur.next
            # 將尾節(jié)點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é)點
        if pos <= 0:
            self.add(item)
        elif pos > (self.length()-1):
            self.append(item)
        else:
            node = Node(item)
            cur = self._head
            count = 0
            # 移動到指定位置的前一個位置
            while count < (pos-1):
                count += 1
                cur = cur.next
            # 將node的prev指向cur
            node.prev = cur
            # 將node的next指向cur的下一個節(jié)點
            node.next = cur.next
            # 將cur的下一個節(jié)點的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é)點的元素即是要刪除的元素
                if cur.next == None:
                    # 如果鏈表只有這一個節(jié)點
                    self._head = None
                else:
                    # 將第二個節(jié)點的prev設(shè)置為None
                    cur.next.prev = None
                    # 將_head指向第二個節(jié)點
                    self._head = cur.next
                return
            while cur != None:
                if cur.item == item:
                    # 將cur的前一個節(jié)點的next指向cur的后一個節(jié)點
                    cur.prev.next = cur.next
                    # 將cur的后一個節(jié)點的prev指向cur的前一個節(jié)點
                    cur.next.prev = cur.prev
                    break
                cur = cur.next

隊列（鏈表形式實現(xiàn)）

'''
遇到問題沒人解答？小編創(chuàng)建了一個Python學(xué)習交流QQ群：××× 
尋找有志同道合的小伙伴，互幫互助,群里還有不錯的視頻學(xué)習教程和PDF電子書！
'''
class Node(object):
    def __init__(self,elem,next=None):
        self.elem = elem #表示對應(yīng)的元素值
        self.next=next #表示下一個鏈接的鏈點
class Queue(object):
    def __init__(self):
        self.head = None #頭部鏈點為 None
        self.rear = None #尾部鏈點為 None
    def is_empty(self):
        return self.head is None #判斷隊列是否為空
    def enqueue(self, elem):
        p = Node(elem) #初始化一個新的點
        if self.is_empty():
            self.head = p #隊列頭部為新的鏈點
            self.rear = p #隊列尾部為新的鏈點
        else:
            self.rear.next = p #隊列尾部的后繼是這個新的點
            self.rear =p #然后讓隊列尾部指針指向這個新的點
    def dequeue(self):
        if self.is_empty(): #判斷隊列是否為空
            print('Queue_is_empty') #若隊列為空，則退出 dequeue 操作
        else:
            result = self.head.elem #result為隊列頭部元素
            self.head = self.head.next #改變隊列頭部指針位置
            return result #返回隊列頭部元素
    def peek(self):
        if self.is_empty(): #判斷隊列是否為空
            print('NOT_FOUND') #為空則返回 NOT_FOUND
        else:
            return self.head.elem #返回隊列頭部元素
    def print_queue(self):
        print("queue:")
        temp=self.head
        myqueue=[] #暫時存放隊列數(shù)據(jù)
        while temp is not None:
            myqueue.append(temp.elem)
            temp=temp.next
        print(myqueue)

隊列（數(shù)組形式實現(xiàn)）

class Queue():
    def __init__(self):
        self.entries = [] #表示隊列內(nèi)的參數(shù)
        self.length = 0 #表示隊列的長度
        self.front=0 #表示隊列頭部位置
    def enqueue(self, item):
        self.entries.append(item) #添加元素到隊列里面
        self.length = self.length + 1 #隊列長度增加 1
    def dequeue(self):
        self.length = self.length - 1 #隊列的長度減少 1
        dequeued = self.entries[self.front] #隊首元素為dequeued
        self.front-=1 #隊首的位置減少1
        self.entries = self.entries[self.front:] #隊列的元素更新為退隊之后的隊列
        return dequeued
    def peek(self):
        return self.entries[0] #直接返回隊列的隊首元素

二叉樹

'''
遇到問題沒人解答？小編創(chuàng)建了一個Python學(xué)習交流QQ群：××× 
尋找有志同道合的小伙伴，互幫互助,群里還有不錯的視頻學(xué)習教程和PDF電子書！
'''
class Node(object):
    def __init__(self,item):
        self.item=item #表示對應(yīng)的元素
        self.left=None #表示左節(jié)點
        self.right=None #表示右節(jié)點
    def __str__(self):
        return str(self.item)  #print 一個 Node 類時會打印 __str__ 的返回值
class Tree(object):
    def __init__(self):
        self.root=Node('root')  #根節(jié)點定義為 root 永不刪除，作為哨兵使用。
    def add(self,item):
        node = Node(item)
        if self.root is None:  #如果二叉樹為空，那么生成的二叉樹最終為新插入樹的點
            self.root = node
        else:
            q = [self.root] # 將q列表，添加二叉樹的根節(jié)點
            while True:
                pop_node = q.pop(0)
                if pop_node.left is None: #左子樹為空則將點添加到左子樹
                    pop_node.left = node
                    return
                elif pop_node.right is None: #右子樹為空則將點添加到右子樹
                    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é)點沒有父節(jié)點
        tmp = [self.root] # 將tmp列表，添加二叉樹的根節(jié)點
        while tmp:
            pop_node = tmp.pop(0)
            if pop_node.left and pop_node.left.item == item: #某點的左子樹為尋找的點
                return pop_node #返回某點，即為尋找點的父節(jié)點
            if pop_node.right and pop_node.right.item == item: #某點的右子樹為尋找的點
                return pop_node #返回某點，即為尋找點的父節(jié)點
            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é)點
            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指向右子樹的最后一個葉子
                        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

字典樹

'''
遇到問題沒人解答？小編創(chuàng)建了一個Python學(xué)習交流QQ群：××× 
尋找有志同道合的小伙伴，互幫互助,群里還有不錯的視頻學(xué)習教程和PDF電子書！
'''
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):
        #初始化一個空堆，使用數(shù)組來在存放堆元素，節(jié)省存儲
        self.data_list = []
    def get_parent_index(self,index):
        #返回父節(jié)點的下標
        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ù)組中的兩個元素
        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é)點大，則交換，直到最后
        self.data_list.append(data)
        index = len(self.data_list) -1 
        parent = self.get_parent_index(index)
        #循環(huán)，直到該元素成為堆頂，或小于父節(jié)點（對于大頂堆) 
        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):
        #刪除堆頂元素，然后將最后一個元素放在堆頂，再從上往下依次堆化
        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