鏈表作為存儲結(jié)構(gòu)時(shí)，不能進(jìn)行數(shù)據(jù)元素隨機(jī)訪問，但優(yōu)點(diǎn)是插入和刪除操作時(shí)候不需要移動(dòng)大量數(shù)據(jù)。

常用的鏈表結(jié)構(gòu)：

1. 雙向鏈表：每個(gè)節(jié)點(diǎn)包含兩個(gè)指針，指明直接前趨和后繼，可在兩個(gè)方向遍歷鏈表。
2. 循環(huán)鏈表：表尾的指針指向第一個(gè)節(jié)點(diǎn)。
3. 靜態(tài)鏈表：借助數(shù)組來描述線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。

1. 棧和隊(duì)列

棧

只能通過訪問它一端來實(shí)現(xiàn)數(shù)據(jù)存儲和檢索的一種線性數(shù)據(jù)結(jié)構(gòu)。它是先進(jìn)后出的原則FILO。

棧典型的應(yīng)用包括表達(dá)式求值、括號匹配等。在計(jì)算機(jī)語言的實(shí)現(xiàn)以及將遞歸過程轉(zhuǎn)變?yōu)榉沁f歸過程的處理中，棧都很重要

隊(duì)列

隊(duì)列是一種先進(jìn)先出（FIFO）的線性表，它只允許在表的一端插入元素，表的另一端刪除元素。

• 數(shù)組、矩陣和廣義表

1. 數(shù)組

n維數(shù)組是一種“同構(gòu)”的數(shù)據(jù)結(jié)構(gòu)，其每一個(gè)元素類型相同，結(jié)構(gòu)一致。數(shù)組是定長線性表在維數(shù)上的擴(kuò)張，即線性表中的元素又是一個(gè)線性表。

數(shù)組結(jié)構(gòu)特點(diǎn)：數(shù)據(jù)元素?cái)?shù)目固定、數(shù)據(jù)元素具有相同的類型、數(shù)據(jù)元素的下標(biāo)關(guān)系具有上下界的約束且下標(biāo)有序。

一旦定義了數(shù)組，結(jié)構(gòu)中元素個(gè)數(shù)和元素之間的關(guān)系就不再發(fā)生改變，因此數(shù)組適用于采用順序存儲結(jié)構(gòu)。

因?yàn)橛?jì)算機(jī)內(nèi)存結(jié)構(gòu)是一維線性的，因此存儲多維數(shù)組時(shí)必須按照某種方式進(jìn)行降維處理。

1. 矩陣

特殊矩陣：若矩陣中元素（或非0元素）的分部有一定規(guī)律，則為特殊矩陣。（如 三角矩陣、對稱矩陣、對角矩陣）

稀疏矩陣：若非零的元素遠(yuǎn)遠(yuǎn)小于零元素的個(gè)數(shù)，且非零元素的分部沒有規(guī)律，則為稀疏矩陣。

1. 廣義表

廣義表是線性表的推廣，由0個(gè)或者多個(gè)單元素或子表所組成的有限序列。

廣義表長度是元素的個(gè)數(shù)，深度指廣義表展開后所含括號的最大層數(shù)。

• 樹

樹是n(n>=0)個(gè)節(jié)點(diǎn)的有限集合，n=0時(shí)稱為空樹，在任意非空樹中：

1. 有且僅有一個(gè)稱為根的節(jié)點(diǎn)。
2. 其余的節(jié)點(diǎn)可分為m（m>=0）個(gè)互不相交的子集T1，T2...Tm，其中每個(gè)子集本身又是一棵樹，并稱為根節(jié)點(diǎn)的子樹。

樹由若干子樹構(gòu)成，子樹又由子樹構(gòu)成。

1. 雙親和孩子：節(jié)點(diǎn)的子樹的跟稱為該節(jié)點(diǎn)的孩子，該節(jié)點(diǎn)稱為其子節(jié)點(diǎn)的雙親。
2. 兄弟：具有相同雙親的節(jié)點(diǎn)互為兄弟。
3. 節(jié)點(diǎn)的度：一個(gè)節(jié)點(diǎn)的子樹的個(gè)數(shù)記為該節(jié)點(diǎn)的度。
4. 葉子結(jié)點(diǎn)：也稱為終端節(jié)點(diǎn)，指度為0的節(jié)點(diǎn)。

等...

1. 二叉樹

二叉樹binary tree是n(n>=0)個(gè)節(jié)點(diǎn)的有限集合，它或者是空樹(n=0)，或者是由一個(gè)根節(jié)點(diǎn)及兩棵互不相交的、分別稱為左子樹和右子樹的二叉樹所組成。

二叉樹節(jié)點(diǎn)最大度為2，而普通樹不限制節(jié)點(diǎn)的度數(shù)。

二叉樹基本運(yùn)算時(shí)是遍歷，他有如下性質(zhì)：

1. 二叉樹第i層上的節(jié)點(diǎn)數(shù)目最多為 2 的 (i-1)次方。(i>=1)
2. 深度為k的二叉樹至多 （2的k次方）-1 個(gè)節(jié)點(diǎn)。(i>=1)
3. 在任意一顆二叉樹中，若終端節(jié)點(diǎn)數(shù)為n0，度為2的節(jié)點(diǎn)數(shù)為n2，則n0 = n2+1。

等...

二叉樹的遍歷

二叉樹分為根節(jié)點(diǎn)、左子樹和右子樹，按照左子樹必須遍歷在右子樹之前，所以分為前序、中序、后續(xù)。

也可以層序遍歷，從樹的根節(jié)點(diǎn)出發(fā)，依次訪問第一層節(jié)點(diǎn)，從左往右依次訪問第二層的節(jié)點(diǎn)，以此類推，自上而下，自左往右。

• 圖

圖G是由兩個(gè)集合V和E構(gòu)成的二元組，記作G=(V,E)，其中V是圖中頂點(diǎn)的非空有限集合，E是圖中邊的有限集合。從數(shù)據(jù)結(jié)構(gòu)邏輯關(guān)系看，圖中任意頂點(diǎn)都與其他頂點(diǎn)有關(guān)，而圖中所有頂點(diǎn)都有可能與某一頂點(diǎn)有關(guān)。在圖中，數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素用頂點(diǎn)表示，數(shù)據(jù)元素之間的關(guān)系則用邊表示。

1. 有向圖：若圖中每條邊都是有方向的，則稱G為有向圖。
2. 無向圖：若圖中每一條邊都是無方向的。
3. 無向完全圖：若一個(gè)圖像圖具有n個(gè)頂點(diǎn)，若每一個(gè)頂點(diǎn)與其他n-1個(gè)頂點(diǎn)之間都有邊，則稱為無向完全圖。顯然含n個(gè)頂點(diǎn)的無向完全圖共有n(n-1)/2條邊。
4. 有向完全圖：有n個(gè)頂點(diǎn)的有向完全圖中孤的數(shù)目為n(n-1)，即任何兩個(gè)不同頂點(diǎn)之間都有方向相反的兩條弧存在。

等...

圖的遍歷分為：

1. 深度優(yōu)化遍歷 DFS：從圖G任意一個(gè)頂點(diǎn)v出發(fā)。設(shè)計(jì)搜索指針，指向旁邊未訪問的頂點(diǎn)。
2. 廣度優(yōu)化遍歷：BFS：從頂點(diǎn)v出發(fā)，訪問v旁邊都未訪問過的頂點(diǎn)。