數據結構期末復習速成，沒有很詳細的知識點，只是對照常考的題目提醒，把關鍵的一些基礎題目設計到的知識點重新梳理了一遍，靜下心把這些都快速的過一遍，相信你能收獲不少，每天復習一點就會持續更新一點！期末不掛科！

數據和數據結構

定義

數據

數據元素：數據的基本組織單位

數據項：數據元素的組成部分

數據對象：具有相同性質的數據元素的集合

數據的結構分為數據邏輯結構和數據存儲結構

數據邏輯結構

4種基本數據邏輯結構類型：

集合

線性結構

數據元素之間是一對一關系

樹形結構

數據元素之間是一對多關系

圖形結構

數據元素之間是多對多關系，任意兩個結點都可以鄰接

數據存儲結構(物理結構)

包括數據元素的表示和數據元素之間的關系的表示

4中基本數據存儲方式

順序存儲

鏈式存儲

索引存儲

哈希（散列）存儲

---

線性表

是一種最基本的數據結構，

在計算機中可以用順序存儲和鏈式存儲兩種存儲結構表示

順序表

特點：

邏輯上相鄰的數據元素在物理存儲位置上也相鄰

存儲密度高，需要先分配足夠的存儲空間

便于隨機存取（一中存儲結構具有隨機存取特性是指，對于給定的序號i，在O(1)時間內找到對應的元素值）

插入刪除操作不便

鏈表

特點：

邏輯上相鄰的數據元素在物理存儲位置上不一定相鄰

只能進行順序存取

便于執行插入刪除操作

單鏈表

一個結點中只包含一個指針域的鏈表為單鏈表

單鏈表中邏輯上相鄰的元素的物理位置不一定相鄰

雙向鏈表

循環鏈表

---

棧和隊列

棧和隊列屬于線性結構，可以看成是特殊的線性表

（棧插入刪除操作在棧頂，隊列插入在隊尾，刪除在隊首）

棧

順序棧和鏈棧

特性：后進先出（羽毛球筒）

出棧序列：后出先入逆序

隊列

順序隊和鏈隊

循環隊列結構可以解決非循環隊列的“假溢出”問題

特性：先進先出

串

定義

字符串（串）是一種特殊的線性表，串中數據元素類型一定是字符型

子串：串中任意個連續的字符組成的子序列

位序號：0到n

兩個串相等的充要條件：長度相等且對應位置的字符也相等

長度為0的串是空串，即空串不包含任何字符

包含一個及以上空白（空格）字符的串是空白串

模式匹配操作

即查找定位操作：在當前串中尋找子串的過程（找到返回首字符在主串中的位序號，失敗返回-1）

---

數組

稀疏矩陣

定義：具有較多零元素且非零元素的分布無規律的矩陣

稀疏矩陣的壓縮存儲的原則是非零元素分配存儲空間，零元素不分配存儲空間

壓縮方式：三元組的數組存儲結構和十字鏈表存儲結構

特點：稀疏矩陣壓縮后和直接采用二維數組存儲相比會失去隨機存取的特性

---

樹

定義

樹根節點沒有前驅結點，其余每個結點有且僅有1個前驅結點

葉子節點沒有后繼結點，其余每個結點可以有任意多個后繼結點

結點的層次：從0開始

數的深(高)度：從1開始

雙親結點：即父結點

數的度：所有結點度的最大值

結點的度：幾個兒子幾個度

求最小生成樹

Kruskal

把邊從小到大排序，每次選一條邊，只要不構成回路就行

Prim

隨機從一點出發，從鄰接的邊中選最小邊，然后得到一個點，兩個點鄰接的邊再選最小，以此類推

求某點到其余頂點的最短路徑

Dijkstra

求每一對頂點之間的最短路徑

Floyd

關鍵路徑

從源點到匯點最長路徑的長度（完成整個工程的最短時間）

---

二叉樹

二叉樹的遍歷

先根遍歷DLR：根左右

中根遍歷LDR：左根右

后根遍歷LRD：左右根

提供二叉樹的兩個遍歷序列，只要其中一個是中根遍歷就可 以唯一確定該二叉樹

哈夫曼樹（最優二叉樹）

帶權路勁長度最小的二叉樹

畫圖結點是用加法區別于離散的哈斯圖

二叉樹的性質

第i層上的結點數最多為2ⁱ

深度為h的二叉樹中最多有2^h-1個結點

葉子結點數=2度結點數+1

n個結點的完全二叉樹，深度為log₂n+1

具有n個結點的二叉樹有(2n)!/n!(n+1)！種形態（卡特蘭數Catalan數）

所有度數之和=結點數 - 1

小練習

高度為5的二叉樹最多有31個結點（滿二叉樹，1+2+4+8+16）

高度為5的二叉樹至少有5個結點（單分支樹）

高度為8的完全二叉樹至少有64個結點（高度8，即共7層，求最少就是6層全滿+7層一個，2⁶=64)

高度為8的完全二叉樹至多有128個結點（高度為8，即共7層，全滿，2⁷=128)

線索二叉樹

引入線索二叉樹的目的是加快查找結點的前驅或者后繼結點的速度

---

圖

定義

圖是一種非線性結構

簡單路徑：頂點不重復出現的路徑

圖的遍歷：從圖中某頂點出發以某種順序訪問圖中所有頂點且僅訪問一次

連通圖的生成樹是圖的極小連通子圖，包含圖中全部頂點，但只有構成一棵樹的邊

（一個連通圖的生成樹不是唯一的）

強連通圖：在有向圖中，任意兩個點均連通的圖

性質

在無向圖中，結點的度數之和等于變數的2倍

n個結點的無向圖最多有 n(n-1)/2 條邊

n個結點的無向圖最少有 0 條邊

n個結點的有向圖最多有 n(n-1) 條邊

n個結點無向連通圖至少有 n-1 條邊

n個結點的連通圖的生成樹有 n-1 條邊

n個結點的有向圖，構成強連通圖至少有 **n ** 條邊（一個環）

一個n個頂點的無向圖，采用鄰接矩陣表示，大小為 n²

鄰接矩陣

鄰接矩陣是用來表示點與點之間相鄰關系的矩陣（相鄰為1，不相鄰為0）

無向圖的鄰接矩陣是對稱矩陣，有向圖的鄰接矩陣一般不對稱

深度優先遍歷（先根遍歷）

圖的深度優先遍歷必須列不一定是唯一的。

廣度優先遍歷（層次遍歷）

排序

排序的穩定性：經過排序后，關鍵字相同的元素保持原順序中的相對位置不變

{5,2,3,3,1}排序后兩個3的位置沒有變化就是穩定的，變化了就是不穩定的，兩個3有區別

內排序

插入排序

直接插入排序(穩定)

希爾排序（不穩定）

交換排序

冒泡排序（穩定）

快速排序（不穩定）

選擇排序

直接(簡單)選擇排序（不穩定）

樹形選擇排序

堆排序（不穩定）

歸并排序、基數排序（穩定）

---

外排序

---

查找

順序查找

順序查找既適用于順序表也適用于單鏈表，對表中數據元素次序無要求

折半查找

二分查找必須是順序存儲的有序表

分塊查找

數據的組織方式為數據分成若干塊，每塊內數據不必有序，但塊間必須有序，每塊內的最大（或最小）關鍵字組成索引塊

哈希表查找

常用的哈希函數

• 除留取余法
• 直接地址法
• 數字分析法
• 平方取中法
• 折疊法
• 隨機數法

處理沖突的方法

• 開放地址法（線性探測法、二次探測法、雙哈希函數探測法）
• 鏈地址法
• 公共區溢出法
• 再哈希法

---

雜知識點

遞歸算法轉換為非遞歸算法時，通常借助于棧來實現

總結

以上是生活随笔為你收集整理的数据结构期末复习速成的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。