數據結構是計算機存儲、組織數據的方式。數據結構是指相互之間存在一種或多種特定關系的數據元素的集合。


數據結構(data structure)是帶有結構特性的數據元素的集合，它研究的是數據的邏輯結構和數據的物理結構以及它們之間的相互關系，并對這種結構定義相適應的運算，設計出相應的算法，并確保經過這些運算以后所得到的新結構仍保持原來的結構類型。簡而言之，數據結構是相互之間存在一種或多種特定關系的數據元素的集合，即帶“結構”的數據元素的集合。“結構”就是指數據元素之間存在的關系，分為邏輯結構和存儲結構。


數據的邏輯結構和物理結構是數據結構的兩個密切相關的方面，同一邏輯結構可以對應不同的存儲結構。算法的設計取決于數據的邏輯結構，而算法的實現依賴于指定的存儲結構。

數據結構的研究內容是構造復雜軟件系統的基礎，它的核心技術是分解與抽象。通過分解可以劃分出數據的3個層次；再通過抽象，舍棄數據元素的具體內容，就得到邏輯結構。類似地，通過分解將處理要求劃分成各種功能，再通過抽象舍棄實現細節，就得到運算的定義。上述兩個方面的結合可以將問題變換為數據結構。這是一個從具體（即具體問題）到抽象（即數據結構）的過程。然后，通過增加對實現細節的考慮進一步得到存儲結構和實現運算，從而完成設計任務。這是一個從抽象（即數據結構）到具體（即具體實現）的過程。

研究對象

數據的邏輯結構

指反映數據元素之間的邏輯關系的數據結構，其中的邏輯關系是指數據元素之間的前后間關系，而與他們在計算機中的存儲位置無關。邏輯結構包括：

1.集合：數據結構中的元素之間除了“同屬一個集合” 的相互關系外，別無其他關系；

2.線性結構：數據結構中的元素存在一對一的相互關系；

3.樹形結構：數據結構中的元素存在一對多的相互關系；

4.圖形結構：數據結構中的元素存在多對多的相互關系。

數據的物理結構

指數據的邏輯結構在計算機存儲空間的存放形式。

數據的物理結構是數據結構在計算機中的表示（又稱映像），它包括數據元素的機內表示和關系的機內表示。由于具體實現的方法有順序、鏈接、索引、散列等多種，所以，一種數據結構可表示成一種或多種存儲結構。

數據元素的機內表示（映像方法）： 用二進制位（bit）的位串表示數據元素。通常稱這種位串為節點（node）。當數據元素有若干個數據項組成時，位串中與個數據項對應的子位串稱為數據域（data field）。因此，節點是數據元素的機內表示（或機內映像）。

關系的機內表示（映像方法）：數據元素之間的關系的機內表示可以分為順序映像和非順序映像，常用兩種存儲結構：順序存儲結構和鏈式存儲結構。順序映像借助元素在存儲器中的相對位置來表示數據元素之間的邏輯關系。非順序映像借助指示元素存儲位置的指針（pointer）來表示數據元素之間的邏輯關系。

數據存儲結構

數據的邏輯結構在計算機存儲空間中的存放形式稱為數據的物理結構(也稱為存儲結構)。一般來說，一種數據結構的邏輯結構根據需要可以表示成多種存儲結構，常用的存儲結構有順序存儲、鏈式存儲、索引存儲和哈希存儲等。

數據的順序存儲結構的特點是：借助元素在存儲器中的相對位置來表示數據元素之間的邏輯關系；非順序存儲的特點是：借助指示元素存儲地址的指針表示數據元素之間的邏輯關系。

分類

數據結構有很多種，一般來說，按照數據的邏輯結構對其進行簡單的分類，包括線性結構和非線性結構兩類。 https://zhuanlan.zhihu.com/p/140769626/edit

線性結構

簡單地說，線性結構就是表中各個結點具有線性關系。如果從數據結構的語言來描述，線性結構應該包括如下幾點： https://zhuanlan.zhihu.com/p/140769626/edit

1、線性結構是非空集。 https://zhuanlan.zhihu.com/p/140769626/edit

2、線性結構有且僅有一個開始結點和一個終端結點。 https://zhuanlan.zhihu.com/p/140769626/edit

3、線性結構所有結點都最多只有一個直接前趨結點和一個直接后繼結點。 https://zhuanlan.zhihu.com/p/140769626/edit

線性表就是典型的線性結構，還有棧、隊列和串等都屬于線性結構。 https://zhuanlan.zhihu.com/p/140769626/edit

非線性結構

簡單地說，非線性結構就是表中各個結點之間具有多個對應關系。如果從數據結構的語言來描述，非線性結構應該包括如下幾點： https://zhuanlan.zhihu.com/p/140769626/edit

1、非線性結構是非空集。 https://zhuanlan.zhihu.com/p/140769626/edit

2、非線性結構的一個結點可能有多個直接前趨結點和多個直接后繼結點。 https://zhuanlan.zhihu.com/p/140769626/edit

在實際應用中，數組、廣義表、樹結構和圖結構等數據結構都屬于非線性結構。 https://zhuanlan.zhihu.com/p/140769626/edit

常用的數據結構

在計算機科學的發展過程中，數據結構也隨之發展。程序設計中常用的數據結構包括如下幾個。 https://zhuanlan.zhihu.com/p/140769626/edit

數組(Array)

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

棧( Stack)

棧是一種特殊的線性表，它只能在一個表的一個固定端進行數據結點的插入和刪除操作。棧按照后進先出的原則來存儲數據，也就是說，先插入的數據將被壓入棧底，最后插入的數據在棧頂，讀出數據時，從棧頂開始逐個讀出。棧在匯編語言程序中，經常用于重要數據的現場保護。棧中沒有數據時，稱為空棧。 https://zhuanlan.zhihu.com/p/140769626/edit

隊列(Queue)

隊列和棧類似，也是一種特殊的線性表。和棧不同的是，隊列只允許在表的一端進行插入操作，而在另一端進行刪除操作。一般來說，進行插入操作的一端稱為隊尾，進行刪除操作的一端稱為隊頭。隊列中沒有元素時，稱為空隊列。 https://zhuanlan.zhihu.com/p/140769626/edit

鏈表( Linked List)

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

樹( Tree)

樹是典型的非線性結構，它是包括，2個結點的有窮集合K。在樹結構中，有且僅有一個根結點，該結點沒有前驅結點。在樹結構中的其他結點都有且僅有一個前驅結點，而且可以有兩個后繼結點，m≥0。 https://zhuanlan.zhihu.com/p/140769626/edit

圖(Graph)

圖是另一種非線性數據結構。在圖結構中，數據結點一般稱為頂點，而邊是頂點的有序偶對。如果兩個頂點之間存在一條邊，那么就表示這兩個頂點具有相鄰關系。 https://zhuanlan.zhihu.com/p/140769626/edit

堆(Heap)

堆是一種特殊的樹形數據結構，一般討論的堆都是二叉堆。堆的特點是根結點的值是所有結點中最小的或者最大的，并且根結點的兩個子樹也是一個堆結構。 https://zhuanlan.zhihu.com/p/140769626/edit

散列表(Hash)

散列表源自于散列函數(Hash function)，其思想是如果在結構中存在關鍵字和T相等的記錄，那么必定在F(T)的存儲位置可以找到該記錄，這樣就可以不用進行比較操作而直接取得所查記錄。 https://zhuanlan.zhihu.com/p/140769626/edit

常用算法

數據結構研究的內容：就是如何按一定的邏輯結構，把數據組織起來，并選擇適當的存儲表示方法把邏輯結構組織好的數據存儲到計算機的存儲器里。算法研究的目的是為了更有效的處理數據，提高數據運算效率。數據的運算是定義在數據的邏輯結構上，但運算的具體實現要在存儲結構上進行。一般有以下幾種常用運算：

(1)檢索。檢索就是在數據結構里查找滿足一定條件的節點。一般是給定一個某字段的值，找具有該字段值的節點。

(2)插入。往數據結構中增加新的節點。

(3)刪除。把指定的結點從數據結構中去掉。

(4)更新。改變指定節點的一個或多個字段的值。

(5)排序。把節點按某種指定的順序重新排列。例如遞增或遞減。