W3Cschool
恭喜您成為首批注冊用戶
獲得88經驗值獎勵
常見的數據結構包括數組、鏈表、棧、隊列、哈希表、樹、堆、圖,它們可以從“邏輯結構”和“物理結構”兩個維度進行分類。
邏輯結構揭示了數據元素之間的邏輯關系。在數組和鏈表中,數據按照順序依次排列,體現了數據之間的線性關系;而在樹中,數據從頂部向下按層次排列,表現出祖先與后代之間的派生關系;圖則由節(jié)點和邊構成,反映了復雜的網絡關系。
如圖 3-1 所示,邏輯結構可被分為“線性”和“非線性”兩大類。線性結構比較直觀,指數據在邏輯關系上呈線性排列;非線性結構則相反,呈非線性排列。
圖 3-1 線性與非線性數據結構
非線性數據結構可以進一步被劃分為樹形結構和網狀結構。
在計算機中,內存和硬盤是兩種主要的存儲硬件設備。硬盤主要用于長期存儲數據,容量較大(通??蛇_到 TB 級別)、速度較慢。內存用于運行程序時暫存數據,速度較快,但容量較?。ㄍǔ?GB 級別)。
在算法運行過程中,相關數據都存儲在內存中。圖 3-2 展示了一個計算機內存條,其中每個黑色方塊都包含一塊內存空間。我們可以將內存想象成一個巨大的 Excel 表格,其中每個單元格都可以存儲一定大小的數據,在算法運行時,所有數據都被存儲在這些單元格中。
系統(tǒng)通過內存地址來訪問目標位置的數據。如圖 3-2 所示,計算機根據特定規(guī)則為表格中的每個單元格分配編號,確保每個內存空間都有唯一的內存地址。有了這些地址,程序便可以訪問內存中的數據。
圖 3-2 內存條、內存空間、內存地址
內存是所有程序的共享資源,當某塊內存被某個程序占用時,則無法被其他程序同時使用了。因此在數據結構與算法的設計中,內存資源是一個重要的考慮因素。比如,算法所占用的內存峰值不應超過系統(tǒng)剩余空閑內存;如果缺少連續(xù)大塊的內存空間,那么所選用的數據結構必須能夠存儲在離散的內存空間內。
如圖 3-3 所示,物理結構反映了數據在計算機內存中的存儲方式,可分為連續(xù)空間存儲(數組)和離散空間存儲(鏈表)。物理結構從底層決定了數據的訪問、更新、增刪等操作方法,同時在時間效率和空間效率方面呈現出互補的特點。
圖 3-3 連續(xù)空間存儲與離散空間存儲
值得說明的是,所有數據結構都是基于數組、鏈表或二者的組合實現的。例如,棧和隊列既可以使用數組實現,也可以使用鏈表實現;而哈希表的實現可能同時包含數組和鏈表。
基于數組實現的數據結構也被稱為“靜態(tài)數據結構”,這意味著此類數據結構在初始化后長度不可變。相對應地,基于鏈表實現的數據結構被稱為“動態(tài)數據結構”,這類數據結構在初始化后,仍可以在程序運行過程中對其長度進行調整。
Tip
如果你感覺物理結構理解起來有困難,建議先閱讀下一章“數組與鏈表”,然后再回顧本節(jié)內容。
Copyright©2021 w3cschool編程獅|閩ICP備15016281號-3|閩公網安備35020302033924號
違法和不良信息舉報電話:173-0602-2364|舉報郵箱:jubao@eeedong.com
掃描二維碼
下載編程獅App
編程獅公眾號
聯(lián)系方式:
更多建議: