在解決現(xiàn)實(shí)世界的編碼問題時(shí)，雇主和招聘人員都在尋找運(yùn)行時(shí)和資源效率。

知道哪個(gè)數(shù)據(jù)結(jié)構(gòu)最適合當(dāng)前的解決方案將提高程序的性能，并減少開發(fā)所需的時(shí)間。出于這個(gè)原因，大多數(shù)頂級(jí)公司都要求對數(shù)據(jù)結(jié)構(gòu)有很深的理解，并在編碼面試中對其進(jìn)行深入的考察。

下面是我們今天要講的內(nèi)容:

• 什么是數(shù)據(jù)結(jié)構(gòu)?
• 在Python中數(shù)組
• 隊(duì)列在Python中
• 棧在Python中
• Python中的鏈表
• Python中的循環(huán)鏈表
• Python種的樹
• 圖
• Python中的哈希表
• 接下來學(xué)什么

什么是數(shù)據(jù)結(jié)構(gòu)？

數(shù)據(jù)結(jié)構(gòu)是用于存儲(chǔ)和組織數(shù)據(jù)的代碼結(jié)構(gòu)，使修改、導(dǎo)航和訪問信息變得更加容易。數(shù)據(jù)結(jié)構(gòu)決定了如何收集數(shù)據(jù)、我們可以實(shí)現(xiàn)的功能以及數(shù)據(jù)之間的關(guān)系。

數(shù)據(jù)結(jié)構(gòu)幾乎用于計(jì)算機(jī)科學(xué)和編程的所有領(lǐng)域，從操作系統(tǒng)到前端開發(fā)，再到機(jī)器學(xué)習(xí)。

數(shù)據(jù)結(jié)構(gòu)有助于:

• 管理和利用大型數(shù)據(jù)集
• 從數(shù)據(jù)庫中快速搜索特定數(shù)據(jù)
• 在數(shù)據(jù)點(diǎn)之間建立清晰的分層或關(guān)系連接
• 簡化并加快數(shù)據(jù)處理

數(shù)據(jù)結(jié)構(gòu)是高效、真實(shí)解決問題的重要構(gòu)建模塊。數(shù)據(jù)結(jié)構(gòu)是經(jīng)過驗(yàn)證和優(yōu)化的工具，為您提供了一個(gè)簡單的框架來組織您的程序。畢竟，你沒有必要每次都重新制作輪子 (或結(jié)構(gòu))。

每個(gè)數(shù)據(jù)結(jié)構(gòu)都有一個(gè)最適合解決的任務(wù)或情況。Python有4個(gè)內(nèi)置的數(shù)據(jù)結(jié)構(gòu)、列表、字典、元組和集合。這些內(nèi)置數(shù)據(jù)結(jié)構(gòu)帶有默認(rèn)方法和幕后優(yōu)化，使其易于使用。

• List:類似數(shù)組的結(jié)構(gòu)，允許將一組相同類型的可變對象保存為變量。
• 元組:元組是不可變的列表，意味著元素不能被更改。它是用圓括號(hào)聲明的，而不是方括號(hào)。
• Set:集合是無序的集合，這意味著元素是沒有索引的，并且沒有集合序列。它們用花括號(hào)聲明。
• 字典(dict):類似于其他語言中的hashmap或哈希表，字典是鍵/值對的集合。用空花括號(hào)初始化空字典，并用冒號(hào)分隔的鍵和值填充。所有鍵都是唯一的、不可變的對象。

現(xiàn)在，讓我們看看如何使用這些結(jié)構(gòu)來創(chuàng)建面試官想要的所有高級(jí)結(jié)構(gòu)。

Arrays (Lists) in Python

Python沒有內(nèi)置數(shù)組類型，但您可以為所有相同的任務(wù)使用列表。數(shù)組是以相同名稱保存的相同類型的值的集合。

數(shù)組中的每個(gè)值都被稱為“元素”，索引表示其位置。您可以通過使用所需元素的索引調(diào)用數(shù)組名稱來訪問特定的元素。您還可以使用len()方法獲取數(shù)組的長度。

不像Java這樣的編程語言在聲明后有靜態(tài)數(shù)組，Python的數(shù)組在添加/減去元素時(shí)自動(dòng)伸縮。

例如，可以使用append()方法在現(xiàn)有數(shù)組的末尾添加一個(gè)額外的元素，而不是聲明一個(gè)新數(shù)組。

這使得Python數(shù)組特別易于使用和動(dòng)態(tài)適應(yīng)。

cars = ["Toyota", "Tesla", "Hyundai"]
print(len(cars))
cars.append("Honda")
cars.pop(1)
for x in cars:
  print(x)

優(yōu)勢:

• 創(chuàng)建和使用數(shù)據(jù)序列簡單
• 自動(dòng)縮放以滿足不斷變化的尺寸要求
• 用于創(chuàng)建更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)

缺點(diǎn):

• 未針對科學(xué)數(shù)據(jù)進(jìn)行優(yōu)化 (與NumPy的數(shù)組不同)
• 只能操作列表的最右邊

應(yīng)用:

• 相關(guān)值或?qū)ο蟮墓蚕泶鎯?chǔ)，即myDogs
• 通過循環(huán)訪問
• 數(shù)據(jù)結(jié)構(gòu)的集合，例如元組列表

Python中的常見數(shù)組面試問題

• 從列表中刪除偶數(shù)整數(shù)
• 合并兩個(gè)排序列表
• 在列表中找到最小值
• 最大總和子列表
• 打印所有元素

Python中的隊(duì)列

隊(duì)列是一種線性數(shù)據(jù)結(jié)構(gòu)，以 “先進(jìn)先出” (FIFO) 順序存儲(chǔ)數(shù)據(jù)。與數(shù)組不同，您不能按索引訪問元素，而只能提取下一個(gè)最舊的元素。這使得它非常適合訂單敏感任務(wù)，如在線訂單處理或語音郵件存儲(chǔ)。

你可以把在雜貨店排隊(duì); 收銀員不會(huì)選擇下一個(gè)結(jié)賬的人，而是會(huì)處理排隊(duì)時(shí)間最長的人。

我們可以使用帶有append()和pop()方法的Python列表來實(shí)現(xiàn)隊(duì)列。然而，這是低效的，因?yàn)楫?dāng)您向開始添加新元素時(shí)，列表必須按一個(gè)索引移動(dòng)所有元素。

相反，最好的做法是使用Python的collections模塊中的deque類。deque對追加和彈出操作進(jìn)行了優(yōu)化。deque實(shí)現(xiàn)還允許創(chuàng)建雙端隊(duì)列，該隊(duì)列可以通過popleft()和popright()方法訪問隊(duì)列的兩端。

from collections import deque
# Initializing a queue
q = deque()
# Adding elements to a queue
q.append('a')
q.append('b')
q.append('c')
print("Initial queue")
print(q)
# Removing elements from a queue
print("\nElements dequeued from the queue")
print(q.popleft())
print(q.popleft())
print(q.popleft())
print("\nQueue after removing elements")
print(q)
# Uncommenting q.popleft()
# will raise an IndexError
# as queue is now empty

優(yōu)點(diǎn):

• 按時(shí)間順序自動(dòng)處理數(shù)據(jù)
• 根據(jù)數(shù)據(jù)量大小自動(dòng)縮放
• deque類的時(shí)間效率高

缺點(diǎn):

• 只能訪問兩端的數(shù)據(jù)

應(yīng)用程序:

• 打印機(jī)或CPU核心等共享資源的操作
• 作為批處理系統(tǒng)的臨時(shí)存儲(chǔ)
• 為同等重要的任務(wù)提供一個(gè)簡單的默認(rèn)順序

Python中的常見隊(duì)列面試問題

• 反轉(zhuǎn)隊(duì)列的前k個(gè)元素
• 使用鏈表實(shí)現(xiàn)隊(duì)列
• 使用隊(duì)列實(shí)現(xiàn)堆棧

Python中的棧

棧是一種連續(xù)的數(shù)據(jù)結(jié)構(gòu)，充當(dāng)隊(duì)列的后進(jìn)先出(LIFO)版本。插入到堆棧中的最后一個(gè)元素被認(rèn)為是堆棧的頂部，并且是唯一可訪問的元素。要訪問中間元素，必須首先刪除足夠多的元素，使所需的元素位于堆棧頂部。

許多開發(fā)者將堆棧想象成一堆餐盤;你可以把盤子加到或移到盤子堆的頂部，但必須移動(dòng)整個(gè)盤子堆才能把一個(gè)放在底部。

添加元素稱為push，刪除元素稱為pop。你可以在Python中使用內(nèi)置的列表結(jié)構(gòu)來實(shí)現(xiàn)棧。對于列表實(shí)現(xiàn)，推操作使用append()方法，彈出操作使用pop()。

stack = []
# append() function to push
# element in the stack
stack.append('a')
stack.append('b')
stack.append('c')
print('Initial stack')
print(stack)
# pop() function to pop
# element from stack in 
# LIFO order
print('\nElements popped from stack:')
print(stack.pop())
print(stack.pop())
print(stack.pop())
print('\nStack after elements are popped:')
print(stack)
# uncommenting print(stack.pop())  
# will cause an IndexError 
# as the stack is now empty

優(yōu)勢:

• 提供應(yīng)用程序無法實(shí)現(xiàn)的后進(jìn)先出數(shù)據(jù)管理:
• 自動(dòng)縮放和對象清理
• 簡單可靠的數(shù)據(jù)存儲(chǔ)系統(tǒng)

缺點(diǎn):

• 堆棧內(nèi)存有限
• 堆棧上的對象太多會(huì)導(dǎo)致堆棧溢出錯(cuò)誤

應(yīng)用:

• 用于開發(fā)高吞吐量的系統(tǒng)
• 內(nèi)存管理系統(tǒng)首先使用堆棧來處理最近的請求
• 對括號(hào)匹配等問題有幫助

Python中的常見堆面試問題

• 使用棧實(shí)現(xiàn)隊(duì)列
• 使用棧計(jì)算后綴表達(dá)式
• 使用棧獲取下一個(gè)最大元素
• 使用棧創(chuàng)建min() 函數(shù)

Python中的鏈表

鏈表是數(shù)據(jù)的順序集合，使用每個(gè)數(shù)據(jù)節(jié)點(diǎn)上的關(guān)系指針鏈接到列表中的下一個(gè)節(jié)點(diǎn)。

與數(shù)組不同，鏈表在列表中沒有目標(biāo)位置。相反，它們基于節(jié)點(diǎn)串聯(lián)起來。

鏈表中的第一個(gè)節(jié)點(diǎn)稱為頭節(jié)點(diǎn)，最后一個(gè)節(jié)點(diǎn)稱為尾節(jié)點(diǎn)，其中尾節(jié)點(diǎn)的next指向?yàn)閚ull。

鏈表可以是單鏈，也可以是雙鏈，這取決于每個(gè)節(jié)點(diǎn)是只有一個(gè)指向下一個(gè)節(jié)點(diǎn)的指針，還是還有一個(gè)指向前一個(gè)節(jié)點(diǎn)的指針。

你可以把鏈表想象成一條鏈;單個(gè)鏈接只與相鄰的鏈接有一個(gè)連接，但所有鏈接一起形成一個(gè)更大的結(jié)構(gòu)。

Python沒有鏈表的內(nèi)置實(shí)現(xiàn)，因此需要實(shí)現(xiàn)一個(gè)Node類來保存數(shù)據(jù)值和一個(gè)或多個(gè)指針。

class Node:
    def __init__(self, dataval=None):
        self.dataval = dataval
        self.nextval = None
class SLinkedList:
    def __init__(self):
        self.headval = None
list1 = SLinkedList()
list1.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")
# Link first Node to second node
list1.headval.nextval = e2
# Link second Node to third node
e2.nextval = e3

優(yōu)點(diǎn):

• 新元素插入和刪除更高效
• 比數(shù)組更易于重組
• 高級(jí)數(shù)據(jù)結(jié)構(gòu) (如圖形或樹)都是基于鏈表的

缺點(diǎn):

• 每個(gè)數(shù)據(jù)點(diǎn)的指針存儲(chǔ)增加了內(nèi)存使用量
• 必須始終從頭節(jié)點(diǎn)遍歷鏈表以查找特定元素

應(yīng)用:

• 高級(jí)數(shù)據(jù)結(jié)構(gòu)的構(gòu)建塊
• 需要頻繁添加和刪除數(shù)據(jù)的解決方案

Python中的常見鏈表面試問題

• 打印給定鏈表的中間元素
• 從已排序的鏈表中刪除重復(fù)元素
• 檢查單鏈接列表是否為回文
• 合并K排序鏈表
• 查找兩個(gè)鏈表的交點(diǎn)

Python中的循環(huán)鏈表

標(biāo)準(zhǔn)鏈表的主要缺點(diǎn)是，您總是必須從Head節(jié)點(diǎn)開始。循環(huán)鏈表通過將Tail節(jié)點(diǎn)的空指針替換為指向Head節(jié)點(diǎn)的指針來解決這個(gè)問題。當(dāng)遍歷時(shí)，程序?qū)⒏S指針，直到到達(dá)它開始的節(jié)點(diǎn)。

這種設(shè)置的優(yōu)點(diǎn)是，您可以從任何節(jié)點(diǎn)開始遍歷整個(gè)列表。它還允許您通過設(shè)置結(jié)構(gòu)中所需的循環(huán)次數(shù)來使用鏈表作為一個(gè)可循環(huán)結(jié)構(gòu)。循環(huán)鏈表對于長時(shí)間循環(huán)的進(jìn)程非常有用，比如操作系統(tǒng)中的CPU分配。

優(yōu)點(diǎn):

• 可以從任何節(jié)點(diǎn)開始遍歷整個(gè)列表
• 使鏈表更適合循環(huán)結(jié)構(gòu)

缺點(diǎn):

• 如果沒有空標(biāo)記，將更難找到列表的Head和Tail節(jié)點(diǎn)

應(yīng)用:

• 定期循環(huán)解決方案，如CPU調(diào)度

Python中常見的循環(huán)鏈表面試問題

• 在鏈表中檢測循環(huán)
• 反轉(zhuǎn)循環(huán)鏈表
• 給定大小的組中的反向圓形鏈表

Python中的樹形結(jié)構(gòu)

樹是另一種基于關(guān)系的數(shù)據(jù)結(jié)構(gòu)，專門用于表示層次結(jié)構(gòu)。與鏈表一樣，它們也被Node對象填充，Node對象包含一個(gè)數(shù)據(jù)值和一個(gè)或多個(gè)指針，用于定義其與直接節(jié)點(diǎn)的關(guān)系。

每棵樹都有一個(gè)根節(jié)點(diǎn)，所有其他節(jié)點(diǎn)都從根節(jié)點(diǎn)分支出來。根節(jié)點(diǎn)包含指向它正下方所有元素的指針，這些元素被稱為它的子節(jié)點(diǎn)。這些子節(jié)點(diǎn)可以有它們自己的子節(jié)點(diǎn)。二叉樹的節(jié)點(diǎn)不能有兩個(gè)以上的子節(jié)點(diǎn)。

在同一層上的任何節(jié)點(diǎn)都稱為同級(jí)節(jié)點(diǎn)。沒有連接子節(jié)點(diǎn)的節(jié)點(diǎn)稱為葉節(jié)點(diǎn)。

二叉樹最常見的應(yīng)用是二叉搜索樹。二叉搜索樹擅長于搜索大量的數(shù)據(jù)集合，因?yàn)闀r(shí)間復(fù)雜度取決于樹的深度而不是節(jié)點(diǎn)的數(shù)量。

二叉搜索樹有四個(gè)嚴(yán)格的規(guī)則:

• 左子樹只包含元素小于根的節(jié)點(diǎn)。
• 右子樹只包含元素大于根的節(jié)點(diǎn)。
• 左右子樹也必須是二叉搜索樹。他們必須以樹的“根”來遵循上述規(guī)則。
• 不能有重復(fù)的節(jié)點(diǎn)，即不能有兩個(gè)節(jié)點(diǎn)具有相同的值。

lass Node:
    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data
    def insert(self, data):
# Compare the new value with the parent node
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data
# Print the tree
    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print( self.data),
        if self.right:
            self.right.PrintTree()
# Use the insert method to add nodes
root = Node(12)
root.insert(6)
root.insert(14)
root.insert(3)
root.PrintTree()

優(yōu)點(diǎn):

• 用于表示層次關(guān)系
• 動(dòng)態(tài)大小，規(guī)模巨大
• 快速插入和刪除操作
• 在二叉搜索樹中，插入的節(jié)點(diǎn)被立即排序。
• 二叉搜索樹的搜索效率高;長度只有O(高度)。

缺點(diǎn):

• 修改或“平衡”樹或從已知位置檢索元素的時(shí)間開銷為O(logn)
• 子節(jié)點(diǎn)在父節(jié)點(diǎn)上沒有信息，并且很難向后遍歷
• 僅適用于排序的列表。未排序的數(shù)據(jù)退化為線性搜索。

應(yīng)用:

• 非常適合存儲(chǔ)分層數(shù)據(jù)，如文件位置

Python中的常見樹面試問題

• 檢查兩棵二叉樹是否相同
• 實(shí)現(xiàn)一個(gè)二叉樹的層次順序遍歷
• 打印二叉搜索樹的周長
• 對路徑上的所有節(jié)點(diǎn)求和
• 連接二叉樹的所有兄弟

python中的圖

圖是一種數(shù)據(jù)結(jié)構(gòu)，用于表示數(shù)據(jù)頂點(diǎn)(圖的節(jié)點(diǎn))之間關(guān)系的可視化。將頂點(diǎn)連接在一起的鏈接稱為邊。

邊定義了哪些頂點(diǎn)被連接，但沒有指明它們之間的流向。每個(gè)頂點(diǎn)與其他頂點(diǎn)都有連接，這些連接以逗號(hào)分隔的列表形式保存在頂點(diǎn)上。

還有一種特殊的圖叫做有向圖，它定義了關(guān)系的方向，類似于鏈表。在建模單向關(guān)系或類似流程圖的結(jié)構(gòu)時(shí)，有向圖很有幫助。

它們主要用于以代碼形式傳達(dá)可視化的網(wǎng)絡(luò)結(jié)構(gòu)網(wǎng)絡(luò)。這些結(jié)構(gòu)可以為許多不同類型的關(guān)系建模，比如層次結(jié)構(gòu)、分支結(jié)構(gòu)，或者只是一個(gè)無序的關(guān)系網(wǎng)絡(luò)。圖形的通用性和直觀性使它們成為數(shù)據(jù)科學(xué)的寵兒。

當(dāng)以純文本形式編寫時(shí)，圖具有頂點(diǎn)和邊的列表:

V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}

在Python中，圖的最佳實(shí)現(xiàn)方式是使用字典，每個(gè)頂點(diǎn)的名稱作為鍵，邊列表作為值。

# Create the dictionary with graph elements
graph = { "a" : ["b","c"],
                 "b" : ["a", "d"],
                 "c" : ["a", "d"],
                  "d" : ["e"],
                  "e" : ["d"]
         }
# Print the graph          
print(graph)

優(yōu)點(diǎn):

• 通過代碼快速傳達(dá)視覺信息
• 可用于建模廣泛的現(xiàn)實(shí)世界問題
• 語法學(xué)習(xí)簡單

缺點(diǎn):

• 在大型圖中很難理解頂點(diǎn)鏈接
• 從圖表中解析數(shù)據(jù)的時(shí)間昂貴

應(yīng)用:

• 非常適合網(wǎng)絡(luò)或類似網(wǎng)絡(luò)的結(jié)構(gòu)建模
• 曾為Facebook等社交網(wǎng)站建模

Python中的常見圖形面試問題

• 在有向圖中檢測周期
• 在有向圖中找到一個(gè)“母頂點(diǎn)”
• 計(jì)算無向圖中的邊數(shù)
• 檢查兩個(gè)頂點(diǎn)之間是否存在路徑
• 求兩個(gè)頂點(diǎn)之間的最短路徑

Python中的哈希表

哈希表是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，能夠存儲(chǔ)大量信息并有效檢索特定元素。

此數(shù)據(jù)結(jié)構(gòu)使用鍵/值對，其中鍵是所需元素的名稱，值是存儲(chǔ)在該名稱下的數(shù)據(jù)。

每個(gè)輸入鍵都要經(jīng)過一個(gè)哈希函數(shù)，該函數(shù)將其從初始形式轉(zhuǎn)換為一個(gè)整數(shù)值，稱為哈希。哈希函數(shù)必須始終從相同的輸入產(chǎn)生相同的哈希，必須快速計(jì)算，并產(chǎn)生固定長度的值。Python包含一個(gè)內(nèi)置的hash()函數(shù)，可以加速實(shí)現(xiàn)。

然后，該表使用散列來查找所需值(稱為存儲(chǔ)桶)的一般位置。然后，程序只需要在這個(gè)子組中搜索所需的值，而不必搜索整個(gè)數(shù)據(jù)池。

除了這個(gè)通用框架之外，根據(jù)應(yīng)用程序的不同，哈希表也可能非常不同。有些可能允許來自不同數(shù)據(jù)類型的鍵，而有些可能有不同的設(shè)置桶或不同的散列函數(shù)。

下面是一個(gè)Python代碼中的哈希表示例:

import pprint
class Hashtable:
    def __init__(self, elements):
        self.bucket_size = len(elements)
        self.buckets = [[] for i in range(self.bucket_size)]
        self._assign_buckets(elements)
    def _assign_buckets(self, elements):
        for key, value in elements: #calculates the hash of each key
            hashed_value = hash(key)
            index = hashed_value % self.bucket_size # positions the element in the bucket using hash
            self.buckets[index].append((key, value)) #adds a tuple in the bucket
    def get_value(self, input_key):
        hashed_value = hash(input_key)
        index = hashed_value % self.bucket_size
        bucket = self.buckets[index]
        for key, value in bucket:
            if key == input_key:
                return(value)
        return None
    def __str__(self):
        return pprint.pformat(self.buckets) # pformat returns a printable representation of the object
if __name__ == "__main__":
     capitals = [
        ('France', 'Paris'),
        ('United States', 'Washington D.C.'),
        ('Italy', 'Rome'),
        ('Canada', 'Ottawa')
    ]
hashtable = Hashtable(capitals)
print(hashtable)
print(f"The capital of Italy is {hashtable.get_value('Italy')}"

優(yōu)點(diǎn):

• 可以將任何形式的鍵隱藏為整數(shù)索引
• 對于大型數(shù)據(jù)集非常有效
• 搜索效率高
• 每次搜索的步驟數(shù)不變，添加或刪除元素的效率不變
• 在Python 3中進(jìn)一步優(yōu)化

缺點(diǎn):

• 哈希值必須是唯一的，兩個(gè)鍵轉(zhuǎn)換為相同的哈希值會(huì)導(dǎo)致沖突錯(cuò)誤
• 碰撞錯(cuò)誤需要對哈希函數(shù)進(jìn)行全面修改
• 對于初學(xué)者來說很難構(gòu)建

應(yīng)用程序:

• 用于頻繁查詢的大型數(shù)據(jù)庫
• 根據(jù)關(guān)鍵字檢索的系統(tǒng)

Python中常見的哈希表面試問題

• 從頭開始構(gòu)建哈希表(不含內(nèi)置函數(shù))
• 找出兩個(gè)加起來是k的數(shù)
• 為沖突處理實(shí)現(xiàn)開放尋址
• 使用哈希表檢測列表是否循環(huán)

_學(xué)習(xí)愉快!

————————————————

版權(quán)聲明：本文為CSDN博主「程序員石磊」的原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議，轉(zhuǎn)載請附上原文出處鏈接及本聲明。

原文鏈接：https://blog.csdn.net/huangmingleiluo/article/details/119407531