資料結構初探

收錄： 原文位址

資料結構的分類

資料結構是指互相之間存在着一種或多種關系的資料元素的集合和該集合中資料元素之間的關系組成

簡單來說：資料結構是以某種特定的布局方式存儲資料的容器。這種“布局方式”決定了資料結構對于某些操作是高效的，而對于其他操作則是低效的。首先我們需要了解各種資料結構，才能在處理實際問題時選取最合适的資料結構。

常用的資料結構有：數組，棧，連結清單，隊列，樹，圖，堆，散清單等

1、數組

數組是可以再記憶體中連續存儲多個元素的結構，在記憶體中的配置設定也是連續的，數組中的元素通過數組下标進行通路，數組下标從0開始

NSArray *array = [NSArray arrayWithObjects:@"1",@"2",@"3",@"4", nil];
//    NSArray *array = @[@"1",@"2",@"3",@"4"];
NSLog(@"%@",array[0]);
           

優點：

• 1、按照索引查詢元素速度快
• 2、按照索引周遊數組友善

缺點：

• 1、數組的大小固定後就無法擴容了
• 2、數組隻能存儲一種類型的資料
• 3、添加，删除的操作慢，因為要移動其他的元素。

适用場景：

• 頻繁查詢，對存儲空間要求不大，很少增加和删除的情況。

2、棧

棧是一種特殊的

線性表

，僅能線上性表的一端操作，棧頂允許操作，棧底不允許操作。棧的特點是：先進後出，或者說是後進先出，從棧頂放入元素的操作叫入棧，取出元素叫出棧

線性表是最基本、最簡單、也是最常用的一種資料結構。線性表（linear list）是資料結構的一種，一個線性表是n個具有相同特性的資料元素的有限序列。

線性表中資料元素之間的關系是一對一的關系，即除了第一個和最後一個資料元素之外，其它資料元素都是首尾相接的（注意，這句話隻适用大部分線性表，而不是全部。比如，循環連結清單邏輯層次上也是一種線性表（存儲層次上屬于鍊式存儲），但是把最後一個資料元素的尾指針指向了首位結點）

3、隊列

隊列與棧一樣，也是一種線性表，不同的是，隊列可以在一端添加元素，在另一端取出元素，也就是：先進先出。從一端放入元素的操作稱為入隊，取出元素為出隊

4、連結清單

連結清單是一種實體

存儲單元

上非連續、非順序的

存儲結構

，

資料元素

的邏輯順序是通過連結清單中的

指針

連結次序實作的。連結清單由一系列結點（連結清單中每一個元素稱為結點）組成，結點可以在運作時動态生成。每個結點包括兩個部分：一個是存儲

的資料域，另一個是存儲下一個結點位址的

域。 相比于

線性表 順序結構

，操作複雜。由于不必須按順序存儲，連結清單在插入的時候可以達到

O(1)

的複雜度，比另一種線性表順序表快得多，但是查找一個節點或者通路特定編号的節點則需要

O(n)

的時間，而線性表和順序表相應的時間複雜度分别是

O(logn)和O(1)。

根據指針的指向，連結清單能形成不同的結構，例如

單連結清單

雙向連結清單

循環連結清單

等。

雙向連結清單也叫

雙連結清單

，是連結清單的一種，它的每個資料結點中都有兩個

，分别指向直接後繼和直接前驅。是以，從雙向連結清單中的任意一個結點開始，都可以很友善地通路它的前驅結點和後繼結點。一般我們都構造雙向

循環連結清單

。

連結清單的優點：

• 連結清單是很常用的一種資料結構，不需要初始化容量，可以任意加減元素；
• 添加或者删除元素時隻需要改變前後兩個元素結點的指針域指向位址即可，是以添加，删除很快；

• 因為含有大量的指針域，占用空間較大；
• 查找元素需要周遊連結清單來查找，非常耗時。

• 資料量較小，需要頻繁增加，删除操作的場景

5、樹

樹是一種資料結構，它是由

n（n>=1）

個有限節點組成一個具有層次關系的集合。把它叫做 “樹” 是因為它看起來像一棵倒挂的樹，也就是說它是根朝上，而葉朝下的。它具有以下的特點：

• 每個節點有零個或多個子節點；
• 沒有父節點的節點稱為根節點；
• 每一個非根節點有且隻有一個父節點；
• 除了根節點外，每個子節點可以分為多個不相交的子樹；

在日常的應用中，我們讨論和用的更多的是樹的其中一種結構，就是

二叉樹

二叉樹是樹的特殊一種，具有如下特點：

• 1、每個結點最多有兩顆子樹，結點的度最大為2。
• 2、左子樹和右子樹是有順序的，次序不能颠倒。
• 3、即使某結點隻有一個子樹，也要區分左右子樹。

二叉樹是一種比較有用的折中方案，它添加，删除元素都很快，并且在查找方面也有很多的算法優化，是以，二叉樹既有連結清單的好處，也有數組的好處，是兩者的優化方案，在處理大批量的動态資料方面非常有用。

二叉樹有很多擴充的資料結構，包括

平衡二叉樹

、

紅黑樹

B+樹

等，這些資料結構二叉樹的基礎上衍生了很多的功能，在實際應用中廣泛用到，例如

mysql

的資料庫索引結構用的就是

B+樹

，還有

HashMap

的底層源碼中用到了

紅黑樹

。這些二叉樹的功能強大，但算法上比較複雜，想學習的話還是需要花時間去深入的。

6、散清單

散清單，也叫哈希表

，是根據

關鍵碼

和

值 (key和value)

 直接進行通路的資料結構，通過

key

value

來映射到集合中的一個位置，這樣就可以很快找到集合中的對應元素。

記錄的存儲位置=f(key)

• 這裡的對應關系

  f

   成為

  散列函數

  ，又稱為

  哈希 (hash函數)

  ，而散清單就是把

  Key

  通過一個固定的

  算法函數

  既所謂的

  哈希函數

  轉換成一個

  整型數字

• 然後就将該數字對數組長度進行

  取餘

  ，取餘結果就當作

  數組的下标

• 将value存儲在以該數字為下标的

  數組空間裡

• 這種存儲空間可以充分利用數組的查找優勢來查找元素，是以查找的速度很快。

哈希表在應用中也是比較常見的，就如

Java

中有些集合類就是借鑒了哈希原理構造的，例如

HashMap

HashTable

等，利用hash表的優勢，對于集合的查找元素時非常友善的，然而，因為哈希表是

基于數組衍生的資料結構

，在添加删除元素方面是比較慢的，是以很多時候需要用到一種數組連結清單來做，也就是

拉鍊法

。拉鍊法是

數組結合連結清單的一種結構

，較早前的hashMap底層的存儲就是采用這種結構，直到jdk1.8之後才換成了數組加紅黑樹的結構.

iOS

中

weak表（弱引用表）

就是典型的哈希表

• 左邊很明顯是個數組，數組的每個成員包括一個指針，指向一個連結清單的頭，
• 當然這個連結清單可能為空，也可能元素很多。
• 我們根據元素的一些特征把元素配置設定到不同的連結清單中去，
• 也是根據這些特征，找到正确的連結清單，再從連結清單中找出這個元素。

哈希表的應用場景很多，當然也有很多問題要考慮，比如哈希沖突的問題，如果處理的不好會浪費大量的時間，導緻應用崩潰。

7、堆

堆是一種比較特殊的資料結構，

可以被看做一棵樹的數組對象

，具有以下的性質：

• 堆中某個節點的值總是不大于或不小于其父節點的值；
• 堆總是一棵完全二叉樹。

将根節點最大的堆叫做

最大堆或大根堆

，根節點最小的堆叫做

最小堆或小根堆

。常見的堆有

二叉堆

斐波那契堆

堆的定義如下：n個元素的序列{k1,k2,ki,…,kn}當且僅當滿足下關系時，稱之為堆。

(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4…n/2)，

滿足前者的表達式的成為

小頂堆

，滿足後者表達式的為

大頂堆

，這兩者的結構圖可以用完全二叉樹排列出來

8、圖

圖型結構也稱圖案

，指個體目标重複排列的空間形式。圖案反映了地物的空間分布特征，它可以是自然的，也可以是人為構造的。 [1] 圖形結構，簡稱“圖”，是一種複雜的

資料結構

。圖形結構中，每個結點的前驅結點數和後續結點數可以任意多個。

資料元素間的關系是任意的。其他資料結構(如樹、線性表等)都有明确的條件限制，而圖形結構中任意兩個資料元素間均可相關聯。常用來研究所學生産流程、施工計劃、各種網絡建設等問題。

• 對于【資料結構】，想更好的探讨，可以進入iOS技術圈，一起探讨交流
• 點選加入與 2000+iOS開發者一起探讨交流