複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/數據結構/1450
複製
複製成功

數據結構

（計算機存儲、組織數據方式）

鎖定
在計算機科學中，數據結構是一種數據組織、管理和存儲的格式 [1]  。它是相互之間存在一種或多種特定關係的數據元素的集合。通常情況下，精心選擇的數據結構可以帶來更高的運行或者存儲效率。數據結構往往同高效的檢索算法和索引技術相關 [2]  。
數據結構研究的是數據的邏輯結構和數據的物理結構以及它們之間的相互關係 [3]  。它包含三個方面的內容：即數據的邏輯結構、數據的存儲結構和數據的操作，只有這三個方面的內容完全相同，才能成為完全相同的數據結構 [4]  。
中文名
數據結構
外文名
data structure
解    釋
計算機存儲、組織數據的方式
具體指向
特定關係的數據元素的集合
有關技術
檢索算法和索引技術

目錄

  1. 1 研究對象
  2. ▪ 數據邏輯結構
  3. ▪ 數據的存儲結構
  4. ▪ 數據的操作
  5. 2 常見數據結構
  1. ▪ 數組(Array)
  2. ▪ 堆棧(Stack)
  3. ▪ 隊列(Queue)
  4. ▪ 鏈表(Linked List)
  5. ▪ 樹(Tree)
  1. ▪ 圖(Graph)
  2. ▪ 堆(Heap)
  3. ▪ 散列表(Hash)

數據結構研究對象

數據結構數據邏輯結構

數據的邏輯結構是指數據元素之間存在的邏輯關係，由數據元素的集合和定義在此集合上的關係組成。數據的邏輯結構與數據的存儲無關，獨立於計算機，是從具體問題抽象出來的數學模型。數據的邏輯結構由兩個要素構成，分別是：數據元素的集合和關係的集合 [4]  。一般來説，邏輯結構包括：
1.集合：數據結構中的元素之間除了“同屬一個集合” 的相互關係外，別無其他關係 [2]  ；
2.線性結構：數據結構中的元素存在一對一的相互關係 [2]  ；
3.樹形結構：數據結構中的元素存在一對多的相互關係 [2]  ；
4.圖形結構：數據結構中的元素存在多對多的相互關係 [2]  。
數據的邏輯結構分類 數據的邏輯結構分類

數據結構數據的存儲結構

數據的邏輯結構在計算機中的存儲表示或實現叫做數據的存儲結構，也叫物理結構。數據的存儲結構依賴於計算機 [4]  。
一般來説，一種數據結構的邏輯結構根據需要可以表示成多種存儲結構，常用的存儲結構有順序存儲、鏈式存儲、索引存儲和哈希存儲等 [5]  。
數據的順序存儲結構的特點是：藉助元素在存儲器中的相對位置來表示數據元素之間的邏輯關係；非順序存儲的特點是：藉助指示元素存儲地址的指針表示數據元素之間的邏輯關係 [5]  。

數據結構數據的操作

數據操作是指對數據結構中的數據元素進行運算或處理。數據操作定義在數據的邏輯結構上，每種邏輯結構都需要一組對其數據元素進行處理以實現特定功能的操作，如插入、刪除、更新等。數據操作的實現依賴於數據的存儲結構 [4]  。
常見的數據操作有以下幾種：
（1） 創建操作
（2） 插入操作
（3） 刪除操作
（4） 查找操作
（5） 修改操作
（6） 遍歷操作

數據結構常見數據結構

在計算機科學的發展過程中，數據結構也隨之發展。程序設計中常用的數據結構包括如下幾個 [6]  。

數據結構數組(Array)

數組是一種聚合數據類型，它是將具有相同類型的若干變量有序地組織在一起的集合。數組是最基本的數據結構，在各種編程語言中都有對應。一個數組可以分解為多個數組元素，按照數據元素的類型，數組可以分為整型數組、字符型數組、浮點型數組、指針數組和結構數組等。數組還可以有一維、二維以及多維等表現形式 [6]  。

數據結構堆棧(Stack)

堆棧是一種特殊的線性表，又稱為棧。它只能在表的固定端進行數據結點的插入和刪除操作。棧按照先進後出、後進先出的原則來存儲數據，也就是説，先插入的數據將被壓入棧底，最後插入的數據在棧頂，讀出數據時，從棧頂開始逐個讀出。棧在彙編語言程序中，經常用於重要數據的現場保護。棧中沒有數據時，稱為空棧 [6]  。

數據結構隊列(Queue)

隊列和棧類似，也是一種特殊的線性表。和棧不同的是，隊列按照先進先出的原則來存儲數據。隊列只允許在表的一端進行插入操作，而在另一端進行刪除操作。一般來説，進行插入操作的一端稱為隊尾，進行刪除操作的一端稱為隊頭。隊列中沒有元素時，稱為空隊列 [6]  。

數據結構鏈表(Linked List)

鏈表是一種數據元素按照鏈式存儲結構進行存儲的數據結構，這種存儲結構具有在物理上非連續的特點。鏈表由一系列數據結點構成，每個數據結點包括數據域和指針域兩部分。其中，指針域保存了數據結構中下一個元素存放的地址。鏈表結構中數據元素的邏輯順序通過鏈表中的指針鏈接次序實現 [6]  。

數據結構樹(Tree)

樹是典型的非線性結構，它是由n（n>0）個有限結點組成的一個具有層次關係的集合。在樹結構中，有且僅有一個根結點，該結點沒有前驅結點。在樹結構中的其他結點都有且僅有一個前驅結點。

數據結構圖(Graph)

圖是另一種非線性數據結構。圖的數據結構包含一個有限的集合作為結點集合，以及一個無序對（對應無向圖）或有序對（對應有向圖）的集合作為邊的集合。如果兩個結點之間存在一條邊，那麼就表示這兩個結點具有相鄰關係 [6]  。

數據結構堆(Heap)

堆是一種特殊的樹形數據結構，一般討論的堆都是二叉堆。堆的特點是根結點的值是所有結點中最小的或者最大的，並且根結點的兩個子樹也是一個堆結構 [6]  。

數據結構散列表(Hash)

散列表源自於散列函數(Hash function)，其思想是如果在結構中存在關鍵字和T相等的記錄，那麼必定在F(T)的存儲位置可以找到該記錄，這樣就可以不用進行比較操作而直接取得所查記錄[6]。
參考資料
  • 1.    data structure  ．National Institute of Standards and Technology[引用日期2024-06-20]
  • 2.    彭軍、向毅．數據結構與算法：人民郵電出版社，2013
  • 3.    石玉強，閆大順．數據結構與算法：中國農業大學出版社，2017
  • 4.    呂雲翔，郭穎美，孟爻，陳妙然，黃鈺銘．數據結構．北京：機械工業出版社，2020
  • 5.    孟朝霞．大學計算基礎：西安電子科技大學出版社，2012
  • 6.    劉亞東,曲心慧．C/C++常用算法手冊：中國鐵道出版社，2017