資料結構概念考點
- 在資料結構按邏輯結構可以分為：線性結構和非線性結構
- 根據資料元素之間關系的不同特性，基本邏輯結構分為集合、線性結構、樹形結構、圖形結構
- 資料的基本單位是資料元素，資料的最小單位是資料項
線性表
- 線性結構中元素之間存在一對一的關系
- 線性表采用鏈式存盤時，其地址連續與否都可以；采用順序存盤時，其地址必須是連續的
鏈表
- 單鏈表中設定頭結點的作用是在表頭進行插入或洗掉操作時無需進行額外操作
- 回圈鏈表的主要優點是從任一結點出發可以訪問整個鏈表
堆疊
- 堆疊是一種操作受限的線性表，只能在線性表的一端進行插入和洗掉操作，訪問按照先進后出的原則
- n的元素以某種順序入堆疊，所有可能的出堆疊序列總和為\({1\over{n+1}}C^n_{2n}\) (卡特蘭數)
佇列
-
佇列也是一種操作受限的線性表，僅允許在表的一端進行插入，另一端進行洗掉，插入端稱為隊尾rear，洗掉端稱為隊頭font
-
佇列操作的原則是先進先出(FIFO)
-
回圈佇列的判空條件
Q.front==Q.rear，隊滿條件(Q.rear+1)%Maxsize== Q.front
矩陣的壓縮存盤
- 稀疏矩陣一般的壓縮存盤方法主要有：三元組和十字鏈表
樹
-
樹形結構中元素之間存在一對多的關系
-
總分支數=總結點數-1
二叉樹
-
\(n_0=n_2+1\)
-
任何一顆二叉樹的葉子節點在前序、中序、后序遍歷序列中的相對次序不變
-
如果二叉樹T2由樹T1轉換而來，則樹的先序對應二叉樹的先序
-
n個結點的二叉鏈表存盤的二叉樹中，空鏈域的個數為n+1
完全二叉樹
-
一棵深度為 k 且有\(2^k-1\)個結點的二叉樹稱為滿二叉樹
-
高度為 h，有 n 個結點的二叉樹，當且僅當其每個結點都與高度為h的滿二叉樹中編號為 1~n 的結點一 一對應時，稱為完全二叉樹
-
具有 n 個結點的完全二叉樹的深度為\(\lfloor log_2n \rfloor+1\)
-
若\(i \leq \lfloor n/2 \rfloor\)，則結點 i 為分支結點，否則為葉子結點
線索二叉樹
- 線索二叉樹的左線索指向前驅結點，右線索指向后繼結點
T->ltag=1表示T所指結點沒有左子樹，T->lchild指向結點的直接前驅
二叉排序樹BST
-
定義：二叉排序樹或是空樹，或是滿足以下性質的二叉樹
-
若它的左子樹不為空，則左子樹上所有關鍵字的值均不大于根關鍵字的值
-
若它的右子樹不為空，則右子樹上所有關鍵字的值均不小于根關鍵字的值
-
左右子樹各是一顆二叉排序樹
-
-
對二叉排序樹進行中序遍歷，可以得到一個遞增有序序列
平衡二叉樹
-
左右子樹的高度差的絕對值不超過1的二叉排序樹
-
平均查找長度\(O(log_2n)\)
哈夫曼樹
- 帶權路徑長度WPL最短的二叉樹稱為哈夫曼樹
- n個權值構成的哈夫曼樹共有2n-1個結點
- 前綴編碼：沒有一個編碼是另一個編碼的前綴
圖
- 圖型結構中元素之間存在多對多的關系
圖的基本概念
-
有向完全圖
具有 n(n-1) 條邊的有向圖
-
無向完全圖
具有n(n-1)/2條邊的無向圖
-
連通圖
任意兩個頂點之間都連通
n個頂點的無向連通圖至少有n-1條邊
-
連通分量
即極大連通子圖
-
強連通圖
任意兩個頂點之間都有路徑，否則將其中的極大強連通子圖稱為強連通分量
-
簡單路徑、簡單回路
在路徑序列中，頂點不重復出現的路徑稱為簡單路徑；除第一個和最后一個頂點外，其余頂點不重復出現的回路稱為簡單回路
圖的存盤
鄰接矩陣
- 若使用鄰接矩陣表示某有向圖，則矩陣中非零元素的個數等于圖中邊的數目；若為無向圖，則為邊的數目的兩倍
鄰接表
- n個頂點，e條邊的有向圖，建立圖的演算法的時間復雜度為\(O(n+e)\)
- 所需存盤空間：無向圖\(O(|V|+2|E|)\)，有向圖\(O(|V|+|E|)\)
圖的遍歷
廣度優先搜索BFS
-
需要輔助佇列，n個頂點均需入隊一次，最壞情況下空間復雜度\(O(|V|)\)
-
采用鄰接表存盤時，時間復雜度\(O(|V|+|E|)\)
-
采用鄰接矩陣存盤時，時間復雜度\(O(|V|^2)\)
深度優先搜索DFS
-
連通圖的深度優先搜索可以采用堆疊來暫存剛訪問過的頂點，空間復雜度\(O(|V|)\)
-
采用鄰接表存盤時，時間復雜度\(O(|V|+|E|)\)
-
采用鄰接矩陣存盤時，時間復雜度\(O(|V|^2)\)
最小生成樹
- 帶權無向圖的最小生成樹不唯一，僅當各邊權值都不相等時最小生成樹唯一
- 最小生成樹的邊的權值之和總是唯一的，而且是最小的
- 最小生成樹的邊數為頂點數減1
- Prim演算法時間復雜度為\(O(|V|^2)\)，不依賴于|E|，適用于邊稠密圖，
- Krustkal演算法時間復雜度為\(O(|E|log|E|)\)，更適合邊稀疏圖
拓撲排序
- 拓撲排序可以判斷一個有向圖是否有環
關鍵路徑
-
在AOE網中，完成工程的最短時間是從源點到匯點的最長路徑的長度
-
若網中有幾條關鍵路徑，提高一條關鍵路徑上的活動的速度，不能導致整個工程縮短工期，除非是公共活動
查找
順序查找
- 每個元素的平均查找長度為\((n+1)/2\)，時間復雜度為O(n)
折半查找
- 時間復雜度\(O(\log_2(n))\)
- 折半查找要求線性表必須以順序方式存盤，且結點按關鍵字有序排序
B-樹
- m階B-樹中每個結點最多有m棵子樹，m-1個關鍵字，非根非葉結點至少有\(\lceil m/2 \rceil\)棵子樹
- B-樹和B+樹都能有效地支持隨機查找，B+樹還可以支持順序查找
- 插入元素程序中若引起樹根結點的分裂，則新樹高度為原樹高度加 1
- B樹是所有結點的平衡因子均等于0的多路平衡查找樹
散列/哈希表
-
評判一個散列函式優劣的兩個主要條件是：計算方便 和散列地址分布均勻
-
在哈希查找方法中，要解決兩方面的問題，分別是構造一個合適的哈希函式和確定解決地址沖突的辦法
-
沖突：散列函式把兩個或兩個以上的不同關鍵字映射到同一地址
排序
-
不穩定排序口訣：快些選一堆朋友（快速排序、希爾排序、簡單選擇排序，堆排序）
-
快些以\(nlog_2n\)速度歸隊
(快速排序、希爾排序、歸并排序、堆排序時間復雜度\(O(nlog_2n)\)
| 最好 | 平均 | 最壞 | 空間 | 穩定性 | |
|---|---|---|---|---|---|
| 直接插入 | \(O(n)\) | \(O(n^2)\) | \(O(n^2)\) | \(O(1)\) | √ |
| 冒泡排序 | \(O(n)\) | \(O(n^2)\) | \(O(n^2)\) | \(O(1)\) | √ |
| 簡單選擇 | \(O(n^2)\) | \(O(n^2)\) | \(O(n^2)\) | \(O(1)\) | × |
| 希爾排序 | \(O(1)\) | × | |||
| 快速排序 | \(O(nlog_2n)\) | \(O(nlog_2n)\) | \(O(n^2)\) | \(O(log_2n)\) | × |
| 堆排序 | \(O(nlog_2n)\) | \(O(nlog_2n)\) | \(O(nlog_2n)\) | \(O(1)\) | × |
| 2路歸并 | \(O(nlog_2n)\) | \(O(nlog_2n)\) | \(O(nlog_2n)\) | \(O(n)\) | √ |
| 基數排序 | \(O(d(n+r))\) | \(O(d(n+r))\) | \(O(d(n+r))\) | \(O(r)\) | √ |
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/538375.html
標籤：其他