八個程序員都必須知道的常見數據結構

作者：佚名 2024-09-03 13:24:12

開發前端

在軟件開發領域中，數據結構是我們能夠有效地組織、存儲和操作數據的基本構建塊。無論你是初學者還是經驗豐富的開發人員，掌握常見的數據結構對于編寫高效且優化代碼都至關重要。

在今天的文章中，我們將探討每個程序員都應該熟悉的8種基本數據結構，并提供清晰的解釋和相關示例，以幫助你了解它們的重要性和應用。

1. 數組：多功能主力

什么是數組？

數組可能是編程中最基本、使用最廣泛的數據結構。將數組視為存儲在連續內存位置的項目集合。它就像學校里一排儲物柜，每個儲物柜（元素）按順序編號，可容納一個物品。

數組如何工作？

數組基于索引的訪問原理工作。數組中的每個元素都與一個索引相關聯，通常從 0 開始。這樣可以快速直接地訪問數組中的任何元素。

示例：書架類比

假設你有一個書架，上面有 5 個插槽，編號為 0 到 4。每個插槽可以容納一本書。這類似于大小為 5 的數組。

# Creating an array (bookshelf) in Python
bookshelf = ["Harry Potter", "Lord of the Rings", "Pride and Prejudice", "1984", "To Kill a Mockingbird"]


# Accessing elements
print(bookshelf[0])  # Output: Harry Potter
print(bookshelf[2])  # Output: Pride and Prejudice


# Modifying an element
bookshelf[1] = "The Hobbit"
print(bookshelf)  # Output: ['Harry Potter', 'The Hobbit', 'Pride and Prejudice', '1984', 'To Kill a Mockingbird']

數組的優點

快速訪問：元素可以使用其索引立即訪問。
空間效率：數組使用連續的內存塊，因此內存效率高。
簡單：易于理解和使用。

數組的局限性

固定大小：在許多語言中，數組具有固定大小，創建后無法更改。
插入和刪除：這些操作可能很昂貴，尤其是對于大型數組。

實際應用

存儲和操作圖像像素數據
實現用于科學計算的矩陣
管理用戶界面中的項目列表

2. 鏈表：靈活的鏈

什么是鏈表？

鏈表是一種線性數據結構，其中元素存儲在節點中。每個節點包含一個數據字段和對序列中下一個節點的引用（或鏈接）。與數組不同，鏈表不會將元素存儲在連續的內存位置中。

鏈表如何工作？

鏈表通過指針連接節點來工作。每個節點都知道序列中的下一個節點，從而形成鏈式結構。這允許在列表中的任何位置高效地插入和刪除元素。

示例：火車類比

將鏈表想象成一列火車。每節火車車廂（節點）都載有一些貨物（數據）并與下一節車廂相連。你可以輕松地在火車的任何位置添加或刪除車廂。

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.head = None


    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node


    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")


# Creating a linked list
train = LinkedList()
train.append("Engine")
train.append("Passenger Car")
train.append("Dining Car")
train.append("Cargo Car")


train.display()  # Output: Engine -> Passenger Car -> Dining Car -> Cargo Car -> None

鏈表的優點

動態大小：鏈表在執行過程中可以增大或縮小大小。
插入和刪除效率高：添加或刪除元素速度很快，尤其是在列表的開頭。
靈活的內存分配：節點可以存儲在內存中的任何位置。

鏈表的局限性

順序訪問：要到達第 n 個元素，你需要從頭開始遍歷。
額外內存：每個節點都需要額外的內存來存儲對下一個節點的引用。

實際應用

在應用程序中實現撤消功能
管理音樂播放列表（可以輕松添加或刪除歌曲）
實現哈希表以解決沖突

3. 堆棧：后進先出冠軍

什么是堆棧？

堆棧是一種遵循后進先出 (LIFO) 原則的線性數據結構。可以將其視為一疊盤子：您只能從頂部添加或移除盤子。

堆棧如何工作？

堆棧通過兩個主要操作進行操作：

推送：將元素添加到堆棧頂部。
彈出：從堆棧中刪除頂部元素。

示例：瀏覽器歷史記錄類比

你的 Web 瀏覽器的后退按鈕功能是堆棧的完美現實示例。當你訪問新頁面時，它們會被推送到堆棧上。當你點擊后退按鈕時，你會將頁面從堆棧中彈出。

class BrowserHistory:
    def __init__(self):
        self.history = []


    def visit(self, url):
        self.history.append(url)
        print(f"Visited: {url}")


    def back(self):
        if len(self.history) > 1:
            self.history.pop()
            print(f"Went back to: {self.history[-1]}")
        else:
            print("Can't go back further!")


# Using our browser history stack
browser = BrowserHistory()
browser.visit("google.com")
browser.visit("youtube.com")
browser.visit("github.com")
browser.back()
browser.back()
browser.back()
browser.back()


# Output:
# Visited: google.com
# Visited: youtube.com
# Visited: github.com
# Went back to: youtube.com
# Went back to: google.com
# Can't go back further!

堆棧的優點

簡單高效：堆棧操作簡單快捷。
內存管理：可用于管理函數調用和遞歸。
撤消機制：輕松在應用程序中實現撤消功能。

堆棧的局限性

訪問受限：任何時候都只能訪問頂部元素。
固定大小（在某些實現中）：可能有最大大小限制。

實際應用

編程語言中的函數調用管理
表達式求值和語法解析
文本編輯器中的撤消-重做功能

4. 隊列：先進先出組織者

什么是隊列？

隊列是一種遵循先進先出 (FIFO) 原則的線性數據結構。這就像一隊人在等公共汽車：排在隊伍第一個的人就是第一個上車的人。

隊列如何工作？

隊列主要通過兩個操作進行操作：

入隊：將元素添加到隊列后面。
出隊：從隊列中刪除前面的元素。

示例：打印隊列類比

打印機隊列是隊列運行的經典示例。打印作業按接收順序進行處理。

from collections import deque


class PrinterQueue:
    def __init__(self):
        self.queue = deque()


    def add_job(self, document):
        self.queue.append(document)
        print(f"Added '{document}' to the print queue")


    def print_job(self):
        if self.queue:
            document = self.queue.popleft()
            print(f"Printing: {document}")
        else:
            print("No jobs in the queue")


    def display_queue(self):
        print("Current queue:", list(self.queue))


# Using our printer queue
printer = PrinterQueue()
printer.add_job("Annual Report")
printer.add_job("Meeting Minutes")
printer.add_job("Employee Handbook")
printer.display_queue()
printer.print_job()
printer.print_job()
printer.display_queue()


# Output:
# Added 'Annual Report' to the print queue
# Added 'Meeting Minutes' to the print queue
# Added 'Employee Handbook' to the print queue
# Current queue: ['Annual Report', 'Meeting Minutes', 'Employee Handbook']
# Printing: Annual Report
# Printing: Meeting Minutes
# Current queue: ['Employee Handbook']

隊列的優點

公平性：確保先到先得的處理。
可預測性：元素按已知順序處理。
解耦：適用于管理進程之間的異步數據傳輸。

隊列的局限性

訪問受限：只有前部和后部元素易于訪問。
可能出現瓶頸：如果入隊操作比出隊操作快，則隊列可以無限增長。

實際應用

操作系統中的任務調度
處理 Web 服務器中的請求
圖遍歷中的廣度優先搜索算法

5. 哈希表：閃電般快速的查找大師

什么是哈希表？

哈希表，也稱為哈希映射，是存儲鍵值對并提供快速數據檢索的數據結構。它們使用哈希函數計算存儲桶數組的索引，從中可以找到所需的值。

哈希表如何工作？

哈希函數將鍵作為輸入并生成索引。
鍵值對存儲在與此索引對應的存儲桶中。
要檢索值，需要再次對鍵進行哈希處理以找到正確的存儲桶。

示例：圖書館目錄類比

想象一個圖書館，其中書籍（值）根據從書名派生的唯一代碼（鍵）存儲在書架（存儲桶）中。此代碼由特殊公式（哈希函數）生成。

class SimpleHashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(self.size)]


    def _hash(self, key):
        return sum(ord(char) for char in key) % self.size


    def insert(self, key, value):
        index = self._hash(key)
        for item in self.table[index]:
            if item[0] == key:
                item[1] = value
                return
        self.table[index].append([key, value])


    def get(self, key):
        index = self._hash(key)
        for item in self.table[index]:
            if item[0] == key:
                return item[1]
        raise KeyError(key)


    def display(self):
        for i, bucket in enumerate(self.table):
            print(f"Bucket {i}: {bucket}")


# Using our simple hash table
library = SimpleHashTable(10)
library.insert("Moby Dick", "Shelf A")
library.insert("Pride and Prejudice", "Shelf B")
library.insert("The Great Gatsby", "Shelf C")
library.insert("To Kill a Mockingbird", "Shelf D")


library.display()
print("Location of 'The Great Gatsby':", library.get("The Great Gatsby"))


# Output might look like:
# Bucket 0: []
# Bucket 1: []
# Bucket 2: [['Moby Dick', 'Shelf A']]
# Bucket 3: []
# Bucket 4: [['Pride and Prejudice', 'Shelf B']]
# Bucket 5: [['The Great Gatsby', 'Shelf C']]
# Bucket 6: []
# Bucket 7: [['To Kill a Mockingbird', 'Shelf D']]
# Bucket 8: []
# Bucket 9: []
# Location of 'The Great Gatsby': Shelf C

哈希表的優點

快速查找：插入、刪除和搜索的平均時間復雜度為 O(1)。
靈活的鍵：可以使用各種數據類型作為鍵，而不僅僅是整數。
空間效率：可以有效地表示稀疏數據。

哈希表的局限性

沖突：不同的鍵可能會散列到同一個索引，需要解決沖突。
無序：不保持插入順序。
調整大小：隨著它們的增長可能需要調整大小，這可能會很昂貴。

實際應用

用編程語言實現字典
數據庫索引以實現更快的查詢
Web 應用程序中的緩存機制

6. 樹：分層組織者

什么是樹？

樹是由通過邊連接的節點組成的分層數據結構。它們從根節點開始，然后分支到子節點，形成類似于倒置樹的結構。

樹如何工作？

樹以父子關系組織數據。每個節點可以有多個子節點，但只能有一個父節點（根節點除外）。此結構允許高效搜索和組織分層數據。

示例：家譜類比

家譜是樹形數據結構在現實世界中的完美示例。每個人都是一個節點，上面是父母，下面是孩子。

class FamilyMember:
    def __init__(self, name):
        self.name = name
        self.children = []


    def add_child(self, child):
        self.children.append(child)


    def display(self, level=0):
        print("  " * level + self.name)
        for child in self.children:
            child.display(level + 1)


# Creating a family tree
grandparent = FamilyMember("Grandparent")
parent1 = FamilyMember("Parent 1")
parent2 = FamilyMember("Parent 2")
child1 = FamilyMember("Child 1")
child2 = FamilyMember("Child 2")
grandchild1 = FamilyMember("Grandchild 1")


grandparent.add_child(parent1)
grandparent.add_child(parent2)
parent1.add_child(child1)
parent1.add_child(child2)
child1.add_child(grandchild1)


# Displaying the family tree
grandparent.display()


# Output:
# Grandparent
#   Parent 1
#     Child 1
#       Grandchild 1
#     Child 2
#   Parent 2

樹的優點

層次表示：非常適合表示層次關系。
高效搜索：支持快速搜索操作，尤其是在平衡樹中。
靈活的結構：可用于實現其他數據結構，如堆和集合。

樹的局限性

復雜性：樹操作的實現和維護可能很復雜。
內存使用：可能比線性數據結構占用更多內存。

實際應用

操作系統中的文件系統
Web 瀏覽器中的 HTML DOM（文檔對象模型）
AI 決策樹和游戲樹

7. 圖：關系映射器

什么是圖？

圖是多功能數據結構，表示一組對象（頂點或節點），其中一些對象對通過鏈接（邊）連接。它們是建模復雜關系和網絡的理想選擇。

圖如何工作？

圖由頂點（節點）和邊（節點之間的連接）組成。邊可以是有向的（單向）或無向的（雙向）。可以使用鄰接矩陣或鄰接列表來實現圖形。

示例：社交網絡類比

社交網絡是現實世界中圖形的完美示例。每個人都是一個頂點，友誼是連接這些頂點的邊。

class SocialNetwork:
    def __init__(self):
        self.network = {}


    def add_person(self, name):
        if name not in self.network:
            self.network[name] = set()


    def add_friendship(self, person1, person2):
        self.add_person(person1)
        self.add_person(person2)
        self.network[person1].add(person2)
        self.network[person2].add(person1)


    def display_network(self):
        for person, friends in self.network.items():
            print(f"{person}: {', '.join(friends)}")


# Creating a social network
social_net = SocialNetwork()
social_net.add_friendship("Alice", "Bob")
social_net.add_friendship("Alice", "Charlie")
social_net.add_friendship("Bob", "David")
social_net.add_friendship("Charlie", "David")
social_net.add_friendship("Eve", "Alice")


social_net.display_network()


# Output:
# Alice: Bob, Charlie, Eve
# Bob: Alice, David
# Charlie: Alice, David
# David: Bob, Charlie
# Eve: Alice

圖形的優勢

關系建模：非常適合表示復雜的關系和連接。
多功能性：可以模擬各種各樣的現實場景。
強大的算法：存在許多用于解決復雜問題的圖形算法。

圖形的局限性

復雜性：對于大型數據集，實現和管理可能很復雜。
內存密集型：存儲連接可能需要大量內存。
遍歷挑戰：某些圖形問題的計算成本很高。

現實世界的應用

社交網絡分析
GPS 和地圖系統
網絡路由協議
推薦系統

8. 堆：高效的優先級管理器

什么是堆？

堆是滿足堆屬性的專用樹型數據結構。在最大堆中，對于任何給定節點，節點的值大于或等于其子節點的值。在最小堆中，節點的值小于或等于其子節點的值。

堆如何工作？

堆保持元素的部分排序。它們提供對最大（對于最大堆）或最小（對于最小堆）元素的有效訪問，使其成為優先級隊列實現的理想選擇。

示例：急診室分診類比

想象一個急診室，根據患者病情的嚴重程度對其進行治療。該系統可以使用最大堆進行建模，其中優先級最高（病情最嚴重）的患者始終位于最頂部。

import heapq


class EmergencyRoom:
    def __init__(self):
        self.patients = []
        self.patient_count = 0


    def add_patient(self, name, priority):
        # We use negative priority for max heap behavior
        heapq.heappush(self.patients, (-priority, self.patient_count, name))
        self.patient_count += 1
        print(f"Patient {name} added with priority {priority}")


    def treat_next_patient(self):
        if self.patients:
            _, _, name = heapq.heappop(self.patients)
            print(f"Treating patient: {name}")
        else:
            print("No patients in waiting.")


    def display_queue(self):
        print("Current queue (Higher number means higher priority):")
        sorted_patients = sorted(self.patients)
        for priority, _, name in sorted_patients:
            print(f"  {name}: Priority {-priority}")


# Using our emergency room
er = EmergencyRoom()
er.add_patient("John", 3)
er.add_patient("Alice", 5)
er.add_patient("Bob", 1)
er.add_patient("Eve", 4)


er.display_queue()
er.treat_next_patient()
er.treat_next_patient()
er.display_queue()


# Output:
# Patient John added with priority 3
# Patient Alice added with priority 5
# Patient Bob added with priority 1
# Patient Eve added with priority 4
# Current queue (Higher number means higher priority):
#   Alice: Priority 5
#   Eve: Priority 4
#   John: Priority 3
#   Bob: Priority 1
# Treating patient: Alice
# Treating patient: Eve
# Current queue (Higher number means higher priority):
#   John: Priority 3
#   Bob: Priority 1

堆的優點

高效的優先級管理：快速訪問最高（或最低）優先級元素。
快速插入：插入的時間復雜度為 O(log n)。
空間效率：可以高效地實現為數組。

堆的局限性

訪問受限：只有頂部元素易于訪問。
不適合搜索：搜索特定元素可能效率低下。
實現復雜：在操作期間維護堆屬性可能很棘手。

實際應用

操作系統中的任務調度程序
數據壓縮中的哈夫曼編碼
用于在圖中查找最短路徑的 Dijkstra 算法
編程語言中的內存管理

結論

對于任何希望編寫高效且優化的代碼的程序員來說，了解這8個基本數據結構都至關重要。每個結構都有自己的優點和缺點，使其適用于不同的場景：

數組擅長隨機訪問，非常適合大小已知且固定的場景。
鏈表在需要頻繁插入和刪除的情況下大放異彩。
堆棧非常適合管理函數調用和實現撤消機制。
隊列非常適合以先到先得的原則管理任務。
哈希表提供閃電般的快速查找，非常適合實現字典和緩存。
樹非常適合表示分層數據并實現高效搜索。
圖形在建模復雜關系和網絡方面無與倫比。
堆是優先級隊列實現和某些排序算法的首選結構。

通過掌握這些數據結構，你將能夠更好地選擇合適的工具來完成工作，從而為各種編程挑戰提供更高效、更優雅的解決方案。

請記住，成為一名熟練程序員的關鍵不僅在于了解這些結構，還在于了解何時以及如何在代碼中有效地應用它們。

在繼續編程之旅時，練習從頭開始實現這些數據結構并在各種場景中使用它們。這種實踐經驗可以加深你對它們的理解，并幫助你培養在不同情況下使用哪種結構的直覺。

責任編輯：華軒來源： web前端開發

軟件開發數據結構