數(shù)據(jù)結(jié)構(gòu)與算法
定義：數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)唱星、組織數(shù)據(jù)的方式愧旦。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合铛只。
傳統(tǒng)上埠胖，把數(shù)據(jù)結(jié)構(gòu)分為 邏輯結(jié)構(gòu) 和 物理結(jié)構(gòu) 。
邏輯結(jié)構(gòu)：指反映數(shù)據(jù)元素之間的邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)淳玩，其中的邏輯關(guān)系是指數(shù)據(jù)元素之間的前后間關(guān)系直撤，而與他們?cè)谟?jì)算機(jī)中的存儲(chǔ)位置無(wú)關(guān)。
物理結(jié)構(gòu)：指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間的存放形式蜕着。
-
數(shù)據(jù)結(jié)構(gòu) = 邏輯結(jié)構(gòu) + 存儲(chǔ)結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu) = 邏輯結(jié)構(gòu) + 存儲(chǔ)結(jié)構(gòu) + （在存儲(chǔ)結(jié)構(gòu)上的）運(yùn)算/操作
數(shù)據(jù)的運(yùn)算:檢索谋竖、排序、插入、刪除蓖乘、修改等锤悄。
邏輯結(jié)構(gòu)
- 分類：線性結(jié)構(gòu) 和 非線性結(jié)構(gòu) 。
- 線性結(jié)構(gòu)：有且只有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)驱敲，并且所有結(jié)點(diǎn)都最多只有一個(gè)直接前驅(qū)和一個(gè)直接后繼铁蹈。
- 分類：線性結(jié)構(gòu) 和 非線性結(jié)構(gòu) 。
- 線性結(jié)構(gòu)：線性表 众眨、棧 握牧、隊(duì)列 、串及數(shù)組 娩梨。
- 非線性結(jié)構(gòu)：樹形結(jié)構(gòu) 沿腰、圖形結(jié)構(gòu) 。
線性表（Linear List）
- 一個(gè)線性表是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列狈定。
- 邏輯結(jié)構(gòu)為線性表的結(jié)構(gòu)颂龙，存儲(chǔ)結(jié)構(gòu)的順序表，鏈表都可以實(shí)現(xiàn)纽什。
鏈表(Linked List)
- 單向鏈表
- 雙向鏈表
- 循環(huán)鏈表
棧和隊(duì)列(Stack & Queue)
棧 (Stack)
- 特點(diǎn)：先進(jìn)后出
隊(duì)列(Queue)
- 特點(diǎn)：先進(jìn)先出
樹(Tree)
結(jié)點(diǎn)的度：節(jié)點(diǎn)擁有的子樹的數(shù)目稱為 度 措嵌。
度為0的結(jié)點(diǎn)稱為 葉子結(jié)點(diǎn) 或 終端結(jié)點(diǎn) 。
度不為0的結(jié)點(diǎn)稱為 非終端結(jié)點(diǎn) 或 分支結(jié)點(diǎn) 芦缰。除跟之外的分支結(jié)點(diǎn)也稱為 內(nèi)部結(jié)點(diǎn) 企巢。
數(shù)內(nèi)各結(jié)點(diǎn)的度的最大值稱為 樹的度 。
結(jié)點(diǎn)的 層次 從根開始定義让蕾，層次數(shù)為1的結(jié)點(diǎn)是 根節(jié)點(diǎn) 浪规，其子樹的根的層次數(shù)為 2 。
樹中結(jié)點(diǎn)的最大層次稱為樹的 深度 或 高度 探孝。
-
父親：一個(gè)結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)笋婿。
兒子：一個(gè)結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)。
兄弟：同一個(gè)父親結(jié)點(diǎn)的其他結(jié)點(diǎn)顿颅。
m叉樹：樹中所有結(jié)點(diǎn)最大度數(shù)為 m 的有序樹稱為 m叉數(shù)
二叉樹（Binary Tree）
定義：每個(gè)結(jié)點(diǎn)的度均不超過2的有序樹缸濒，稱為二叉樹（binary tree）。
-
分類：滿二叉樹 粱腻、 完全二叉樹绍填。
滿二叉樹：
? a. 高度為k，并且有 2^（k+1） - 1栖疑。
b.每一層結(jié)點(diǎn)個(gè)數(shù)，都是上面全部層結(jié)點(diǎn)數(shù)+1滔驶。完全二叉樹：
? a.若在一顆滿二叉樹中遇革，在最下層從最右側(cè)起去掉相鄰的若干葉子結(jié)點(diǎn)，得到的二叉樹即為完全二叉數(shù)。
? b.滿二叉樹必為完全二叉樹萝快，而完全二叉樹不一定是滿二叉樹锻霎。
二叉樹的存儲(chǔ)結(jié)構(gòu)： 1. 順序存儲(chǔ)結(jié)構(gòu) 和 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。
-
二叉樹的遍歷：按照某種次序訪問樹中的所有結(jié)點(diǎn)揪漩，且每個(gè)結(jié)點(diǎn)恰好訪問一次旋恼。
- 先序遍歷： 根 左子樹 右子樹
- 中序遍歷：左子樹 根 右子樹
- 后序遍歷：左子樹 右子樹 根
-
二叉查找樹（Binary Search Tree）/二叉搜索樹/二叉排序樹（Binary Sort Tree）
a.特點(diǎn)：左子樹（left subtree）上所有結(jié)點(diǎn)的值 均小于它的根結(jié)點(diǎn)（root）的值，右子樹（right subtree）均大于它的根結(jié)點(diǎn)（root）的值奄容。
b.對(duì)二叉查找樹進(jìn)行中序遍歷冰更，就可以得到有序集合。
平衡二叉樹（Self-balancing binary search tree）：左右兩個(gè)子樹的高度差（平衡因子）的絕對(duì)值 不超過1 昂勒。
紅黑樹（Red-Black Tree）：一種特殊的 平衡二叉樹 蜀细。
圖（Graph）
物理結(jié)構(gòu)
- 物理結(jié)構(gòu)：物理結(jié)構(gòu)又叫存儲(chǔ)結(jié)構(gòu)，指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間的存放形式戈盈。
- 分類：**順序存儲(chǔ) ** 鏈?zhǔn)酱鎯?chǔ) 索引存儲(chǔ) 散列存儲(chǔ) 奠衔。
- 順序存儲(chǔ)：把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置上相鄰的存儲(chǔ)單元中，結(jié)點(diǎn)之間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)塘娶。
- 鏈?zhǔn)酱鎯?chǔ)：計(jì)算機(jī)中用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素(這組存儲(chǔ)單元可以是連續(xù)的,也可以是不連續(xù)的)归斤。
- 索引存儲(chǔ)：所有的存儲(chǔ)結(jié)點(diǎn)存放在一個(gè)區(qū)域。另設(shè)置一個(gè)索引區(qū)域存儲(chǔ)結(jié)點(diǎn)之間的關(guān)系刁岸。
- 散列存儲(chǔ)：又稱hash存儲(chǔ)脏里，是一種力圖將數(shù)據(jù)元素的存儲(chǔ)位置與關(guān)鍵碼之間建立確定對(duì)應(yīng)關(guān)系的查找技術(shù)。
