數據結構初識
- 2020 年 7 月 15 日
- 筆記
- 數據結構 & 演算法
數據結構
二、數據結構是指相互之間存在一種或多種特定關係的數據元素的集合
註： 精心選擇的數據結構可以帶來更高的運行或者存儲效率。數據結構往往同高效的檢索演算法和索引技術有關
研究對象
一、數據的邏輯結構
指反映數據元素之間的邏輯關係的數據結構，其中的邏輯關係是指數據元素之間的前後間關係，而與他們在電腦中的存儲位置無關。邏輯結構包括：
1.集合：數據結構中的元素之間除了「同屬一個集合」 的相互關係外，別無其他關係；
2.線性結構：數據結構中的元素存在一對一的相互關係；
3.樹形結構：數據結構中的元素存在一對多的相互關係；
4.圖形結構：數據結構中的元素存在多對多的相互關係。
二、數據的物理結構
指數據的邏輯結構在電腦存儲空間的存放形式。
數據的物理結構是數據結構在電腦中的表示（又稱映像），它包括數據元素的機內表示和關係的機內表示。由於具體實現的方法有順序、鏈接、索引、散列等多種，所以，一種數據結構可表示成一種或多種存儲結構。
數據元素的機內表示（映像方法）： 用二進位位（bit）的位串表示數據元素。通常稱這種位串為節點（node）。當數據元素有若干個數據項組成時，位串中與各個數據項對應的子位串稱為數據域（data field）。因此，節點是數據元素的機內表示（或機內映像）。
關係的機內表示（映像方法）：數據元素之間的關係的機內表示可以分為順序映像和非順序映像，常用兩種存儲結構：順序存儲結構和鏈式存儲結構。順序映像藉助元素在存儲器中的相對位置來表示數據元素之間的邏輯關係。非順序映像藉助指示元素存儲位置的指針（pointer）來表示數據元素之間的邏輯關係。
三、數據存儲結構
數據的邏輯結構在電腦存儲空間中的存放形式稱為數據的物理結構(也稱為存儲結構)。一般來說，一種數據結構的邏輯結構根據需要可以表示成多種存儲結構，常用的存儲結構有順序存儲、鏈式存儲、索引存儲和哈希存儲等。
數據的順序存儲結構的特點是：藉助元素在存儲器中的相對位置來表示數據元素之間的邏輯關係；非順序存儲的特點是：藉助指示元素存儲地址的指針表示數據元素之間的邏輯關係。
分類
數據結構有很多種，一般來說，按照數據的邏輯結構對其進行簡單的分類，包括線性結構和非線性結構兩類。
一、線性結構
簡單地說，線性結構就是表中各個結點具有線性關係。如果從數據結構的語言來描述，線性結構應該包括如下幾點：
1、線性結構是非空集。
2、線性結構有且僅有一個開始結點和一個終端結點。
3、線性結構所有結點都最多只有一個直接前趨結點和一個直接後繼結點。
4、線性表就是典型的線性結構，還有棧、隊列和串等都屬於線性結構。
二、非線性結構
簡單地說，非線性結構就是表中各個結點之間具有多個對應關係。如果從數據結構的語言來描述，非線性結構應該包括如下幾點：
1、非線性結構是非空集。
2、非線性結構的一個結點可能有多個直接前趨結點和多個直接後繼結點。
在實際應用中，數組、廣義表、樹結構和圖結構等數據結構都屬於非線性結構。
常用的數據結構
在電腦科學的發展過程中，數據結構也隨之發展。程式設計中常用的數據結構包括如下幾個。
一、數組(Array)
數組是一種聚合數據類型，它是將具有相同類型的若干變數有序地組織在一起的集合。數組可以說是最基本的數據結構，在各種程式語言中都有對應。一個數組可以分解為多個數組元素，按照數據元素的類型，數組可以分為整型數組、字元型數組、浮點型數組、指針數組和結構數組等。數組還可以有一維、二維以及多維等表現形式。
二、棧( Stack)
棧是一種特殊的線性表，它只能在一個表的一個固定端進行數據結點的插入和刪除操作。棧按照後進先出的原則來存儲數據，也就是說，先插入的數據將被壓入棧底，最後插入的數據在棧頂，讀出數據時，從棧頂開始逐個讀出。棧在彙編語言程式中，經常用於重要數據的現場保護。棧中沒有數據時，稱為空棧。
三、隊列(Queue)
隊列和棧類似，也是一種特殊的線性表。和棧不同的是，隊列只允許在表的一端進行插入操作，而在另一端進行刪除操作。一般來說，進行插入操作的一端稱為隊尾，進行刪除操作的一端稱為隊頭。隊列中沒有元素時，稱為空隊列。
四、鏈表( Linked List)
鏈表是一種數據元素按照鏈式存儲結構進行存儲的數據結構，這種存儲結構具有在物理上存在非連續的特點。鏈表由一系列數據結點構成，每個數據結點包括數據域和指針域兩部分。其中，指針域保存了數據結構中下一個元素存放的地址。鏈表結構中數據元素的邏輯順序是通過鏈表中的指針鏈接次序來實現的。
五、樹( Tree)
樹是典型的非線性結構，它是包括，2個結點的有窮集合K。在樹結構中，有且僅有一個根結點，該結點沒有前驅結點。在樹結構中的其他結點都有且僅有一個前驅結點，而且可以有兩個後繼結點，m≥0。
六、樹( Tree)
圖是另一種非線性數據結構。在圖結構中，數據結點一般稱為頂點，而邊是頂點的有序偶對。如果兩個頂點之間存在一條邊，那麼就表示這兩個頂點具有相鄰關係。
七、堆(Heap)
堆是一種特殊的樹形數據結構，一般討論的堆都是二叉堆。堆的特點是根結點的值是所有結點中最小的或者最大的，並且根結點的兩個子樹也是一個堆結構。
八、散列表(Hash)
散列表源自於散列函數(Hash function)，其思想是如果在結構中存在關鍵字和T相等的記錄，那麼必定在F(T)的存儲位置可以找到該記錄，這樣就可以不用進行比較操作而直接取得所查記錄。
常用演算法
數據結構研究的內容：就是如何按一定的邏輯結構，把數據組織起來，並選擇適當的存儲表示方法把邏輯結構組織好的數據存儲到電腦的存儲器里。演算法研究的目的是為了更有效的處理數據，提高數據運算效率。數據的運算是定義在數據的邏輯結構上，但運算的具體實現要在存儲結構上進行。一般有以下幾種常用運算： [3]
(1)檢索。檢索就是在數據結構里查找滿足一定條件的節點。一般是給定一個某欄位的值，找具有該欄位值的節點。
(2)插入。往數據結構中增加新的節點。
(3)刪除。把指定的結點從數據結構中去掉。
(4)更新。改變指定節點的一個或多個欄位的值。
(5)排序。把節點按某種指定的順序重新排列。例如遞增或遞減。
