基本數據結構梳理

NO IMAGE

一、前文

數據結構這個東西,一般在實際開發過程中,很容易顧不上那麼多性能或者內存佔用問題,但往往在大數據操作的情況下這些就是引發性能問題的關鍵。

二、基本的數據結構類型

數據結構從大的概念來說可以分為四大類:

  1. 線性表,結構中所有數據都是按線性排列的,常用的比如數組、鏈表、棧都屬於線性表的一種,更具體點,比如說java中的ArrayList就屬於線性表的一種
  2. 樹,指結構中所有數據都交錯有著某種關係,都有父節點、子節點,類似一棵樹的結構,主要分為兩大類,比如二叉樹和圖。
  3. 散列表,是根據鍵值和散列函數映射地址,直接訪問在內存中的數據,查詢速度較快
  4. 集合,結構中所有元素之間都沒有聯繫,所有元素都是平等的,集合和集合之間有包括和被包括的關係,類似數學中集合的概念。

三、雜談

### 線性表

線性表有很多種,線性表分為順序表和鏈表,而鏈表又分為單鏈表、雙鏈表和循環鏈表等。此外還有靜態鏈表,是集合順序表和鏈表兩者特徵的存儲結構。
#### 順序表
順序表指結構中所有元素在內存中都按照順序排列,所以在查詢過程中的性能和在尾部添加、刪除的性能非常高,但是如果再順序表當中進行刪、加操作,就需要把要修改的元素後方所有元素進行前移或者後移,就大大降低了性能,我們所熟知的ArrayList和數組就是採取類似的存儲結構
![線性表](http://img.blog.csdn.net/20171221230606894?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxNDMwMzAwMw==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast)
#### 鏈表

鏈表分為單鏈表、雙鏈表以及循環鏈表,單鏈表即每個元素會記錄下一個元素的位置,但是這樣的缺點就是,當遍歷數據的時候,只能從頭開始遍歷,所以就產生了雙鏈表,元素不但會記錄下一個元素的位置,還會記錄上一個元素的位置,所以我們就可以雙向遍歷,不過還有一個問題,就是如果遍歷到最後一個元素,就不能繼續遍歷,所以就產生了循環遍歷,最後一個元素會指向第一個元素。
![這裡寫圖片描述](http://img.blog.csdn.net/20171226112720411?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvdTAxNDMwMzAwMw==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast)

靜態鏈表

而靜態鏈表則是在數組的前提下,增加遊標指針,我們成為curPos,指向下一個腳標。空的靜態鏈表如下圖所示,每個遊標都會指向下一個腳標,最後一個遊標指向第一個腳標。靜態鏈表由於要實現該特性,所以它往往需要比實際空間更大的內存空間來操作。

基本數據結構梳理

填入數據後如圖所示

基本數據結構梳理

我們向乙後面插入數據戊,就會變成如下圖所示

基本數據結構梳理

紅色為發生更改的變量,我們可以看到乙的遊標指向了5,5的遊標指向了3,這樣就成功插入了戊在乙之後。

樹分為二叉樹和圖,二叉樹一般有一個根節點和兩個子節點,圖則是錯綜複雜的關係連線。

二叉樹

二叉樹也有很多種,分為滿二叉樹和完全二叉樹,而完全二叉樹滿足一定規則就叫做堆。二叉樹也可以根據規則來編程紅黑樹。樹的查找在某些情況很很多優勢。因為樹的存在就衍生出來了廣度優先遍歷算法和深度優先遍歷算法。

廣度優先遍歷算法即從最頂點開始遍歷,隨層級下降,優先遍歷每一層的頂點。

深度優先遍歷算法即從頂點開始遍歷,一直遍歷左節點,當走到頭之後,再遍歷就進的右節點,依次類推

Java中的TreeSet就是紅黑樹的實現

基本數據結構梳理

樹是圖的基礎,樹是一種更簡單意義上的圖。為了方便認識,這裡我把圖分到了樹的一種。圖因為元素之間關係相對複雜,所以開始也需要花些時間才能運用熟練。圖按照有無方向可以分為有向圖和無向圖。按照存儲結構可以分為鄰接矩陣、鄰接表、十字鏈表和鄰接多重表。

有向圖和無向圖

基本數據結構梳理

根據功能的不同,圖經常運用在最短路徑、拓撲排序,也可以用作深度/廣度優先搜索等實際應用。拓撲排序簡單來說,就相當於遊戲裡面,很多角色的技能樹排序,得要學了前置技能才能學習高級技能的這種排序。

想詳細瞭解鄰接矩陣、鄰接表、十子表和鄰接多重表可以參照 這篇文章 講的比較詳細。

散列表

我把散列表單獨分出來是因為他的存儲結構與其他基類都是不同的,散列表是依靠key-value進行數據存儲的,即通過key直接尋址獲得value,在查找上面有一定的優勢。使用的過程類似於java的HashMap。

集合

集合元素是不能重複的。元素是沒有順序的。所以它不能基於位置訪問元素。Java中很多數據結構都有集合的一些特性。類似於TreeSet、HashSet。

個人github地址: github.com/Kongdy
個人掘金主頁:juejin.im/user/595a64…
csdn主頁:blog.csdn.net/u014303003

相關文章

在微信小程序中使用阿里OSS(alioss)接口上傳圖片至阿里雲對象存儲(OSS)

Python讓你的Web應用程飛起來全家桶之Sanic

讓你的Python(Web應用)飛起來,(異步/協程)全家桶

vuevuexvuerouter後臺項目——權限路由(超詳細簡單版)