資料結構與算法--常用資料結構與進階資料結構

常用的資料結構

數組

優點：

建構一個數組非常簡單

根據小标查找的複雜度是o(1)

缺點：

建構時必須配置設定一段連續的空間

查詢某個元素是否存在時要周遊整個數組，複雜度為o(n)

删除和添加某個元素，時間複雜度為o(n)

連結清單

優點：

靈活的配置設定記憶體空間

能在o(1)的時間複雜度内删除或者添加元素

缺點：

查詢元素需要o(n)的時間

棧

特點：

後進先出

隊列

特點：

先進先出

常用場景：

廣度優先搜尋

樹

樹的共性：

結構直覺

通過樹問題來考察 遞歸算法

面試中常見的樹的形狀：

普通二叉樹

平衡二叉樹

完全二叉樹

二叉搜尋樹

四叉樹

多叉樹

周遊：

前序周遊

中序周遊

後序周遊

進階資料結構

優先隊列

與普通隊列的差別：

保證每次取出的元素是隊列中優先級别最高的

優先級可自定義

常用的場景：

從雜亂無章的資料中按一定順序（或者優先級）篩選資料

圖

基本知識點：

階、度

樹、森林、環

有向圖、無相圖、完全有向圖、完全無向圖

連通圖、連通分量

圖的存儲和表達方式：鄰接矩陣和鄰接連結清單

必須熟練掌握的知識點

圖的存儲和表達方式：鄰接矩陣 鄰接連結清單

圖的周遊：深度優先 廣度優先

二部圖的檢測、樹的檢測、環的檢測、有向圖、無向圖

拓撲排序

聯合-查找算法

最短路徑

字首樹

也稱字典樹，廣泛運用在字典查找中

重要性質：

children：數組或者集合，羅列出每個分支當中包含的所有字元

isEnd：布爾值，表示該節點是否為某字元串的結尾

最基本的操作：

建立

搜尋

線段樹

一種按照二叉樹形式存儲的資料結構，每個節點儲存的都是數組裡某一段的總和

樹狀數組

基本特征：

利用數組來表示多叉樹的結構

優先隊列是用數組來表示完全二叉樹，而樹狀數組是多叉樹