天天看點

軟體開發:八大資料結構介紹

作者:小彙愛當機

資料在電腦中的儲存不是簡單的按照先來後到依次排列,而是有多種不同的非直線的排序方式,目的是為了節省空間、友善存儲和調取,由此便有“資料結構”一稱。資料結構是計算機存儲群組織資料的方式。八大基本資料結構形式有:數組(Array)、棧(Stack)、隊列(Queue)、連結清單(Linked List)、樹(Tree)、圖(Graph)、堆(Heap)、散清單(Hash)。

1、數組

數組是一種很基礎的資料結構,幾乎絕大多數程式設計語言都會支援數組這種資料結構。數組是一種線性結構,使用一組連續的記憶體空間,來存儲相同類型的資料。

軟體開發:八大資料結構介紹

2、棧

棧是一種特殊的線性表,僅能線上性表的一端操作,棧頂允許操作,棧底不允許操作。我們用一種最簡單的生活常識描述一下,比如我們往櫃子裡放東西,先放的東西是需要放到櫃子最裡邊,後放的東西在櫃子的最外邊;如果我們要取東西,先要取櫃子最外邊的東西,才能取到櫃子最裡邊的東西。這種先進後出,後進先出的結構稱為“棧”。

軟體開發:八大資料結構介紹

3、隊列

隊列是先進先出的線性結構。在具體應用中通常用連結清單或者數組來實作。隊列隻允許在後端進行插入操作,在前端進行删除操作。 隊列的操作方式和堆棧類似,唯一的差別在于隊列隻允許新資料在後端進行添加。

軟體開發:八大資料結構介紹

4、連結清單

在計算機科學中,連結清單(Linked list)是一種常見的基礎資料結構,是一種線性表,但是不一定按線性的順序存儲資料,而是在每一個節點裡存到下一個節點的指針。從結構上進行區分,連結清單可以分為:單向連結清單、雙向連結清單和循環連結清單,在一些資料裡還會有塊狀連結清單或者多重連結清單,絕大對數情況下,我們隻會用到下面三種連結清單。

軟體開發:八大資料結構介紹

5、樹

樹是一種資料結構,它是由n(n>=1)個有限結點組成一個具有層次關系的集合。把它叫做“樹”是因為它看起來像一棵倒挂的樹,也就是說它是根朝上,而葉朝下的。

軟體開發:八大資料結構介紹

6、散清單

順序存儲的結構類型需要一個一個地按順序通路元素,當這個總量很大且我們所要通路的元素比較靠後時,性能就會很低。散清單是一種空間換時間的存儲結構,是在算法中提升效率的一種比較常用的方式,但是所需空間太大也會讓人頭疼,是以通常需要在二者之間權衡。我們會在之後的具體算法章節中得到更多的領悟。

軟體開發:八大資料結構介紹

7、堆

堆就是用數組實作的二叉樹,是以它沒有使用父指針或者子指針。堆根據“堆屬性”來排序,“堆屬性”決定了樹中節點的位置。

軟體開發:八大資料結構介紹

8、圖

圖是由結點的有窮集合V和邊的集合E組成。其中,為了與樹形結構加以差別,在圖結構中常常将結點稱為頂點,邊是頂點的有序偶對,若兩個頂點之間存在一條邊,就表示這兩個頂點具有相鄰關系。

軟體開發:八大資料結構介紹

繼續閱讀