期末數據結構復習的一點筆記

選擇 2*10 填空 1*20 主要形式為概念題和計算題 算法應用題 二叉樹序遍歷、哈夫曼樹、最短路、最小生成樹、拓撲序、關鍵路徑 畫圖解決問題+概述算法思路+復雜度分析 程序填空題 二叉樹序遍歷、拓撲排序、堆排序 暫未包含： 程序閱讀&程序設計

1

2

3

4

5

6

7

8

9

10

11

12

13

數據，對客觀事物的符號表示，圖像聲音等。

數據元素是數據的基本單位，如學生記錄。

數據項是不可分割的最小單位，如姓名學號。

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

數據結構是互相之間存在關系的數據元素的集合。數據結構={D、R}構成。

數據結構三要素：邏輯結構、存儲結構、數據運算 （羅村樹）

邏輯結構分4類：線性，樹，圖，集合。

邏輯結構包括線性（線性表、棧、隊列）和非線性（樹、圖、集合）結構。線性結構的特點：所有成員處于一個序列，有且僅有一個直接前驅和后繼。

存儲結構包括順序、鏈式、索引、散列存儲。 （順聯鎖傘）

算法的五個特征：有窮性、確定性、可行性、輸入、輸出 （有缺課出入）

線性表

按照存儲結構的不同，分為順序存儲和鏈式存儲分為2類。 1、順序表（vector） 定義：由相同類型的數據元素構成。 每個元素有且僅有一個前驅和后繼。 特點：由一組地址連續的存儲單元依次存儲。 2、鏈表 單鏈表：一個指針指向后繼節點。 雙鏈表：兩個指針指向前驅和后繼節點。 循環鏈表：沒有指向null，判空條件為next指針等于頭指針。

1

2

3

4

5

6

7

8

9

10

11

12

棧和隊列

操作受限的線性表 1、棧 后進先出，可以順序和鏈式存儲。 共享棧，即對頂棧。 2、隊列 先進先出，可以順序和鏈式存儲。 循環隊列：fr==ed

1

2

3

4

5

6

7

8

9

10

串

有多個字符組成的有限序列。 串是一種特殊的線性表，特殊性體現在數據元素可以是字符。 1、模式匹配算法： 簡單匹配，求子串在主串中的位置 改進匹配：KMP算法及優化 2、矩陣的壓縮存儲： 對稱矩陣，上下三角矩陣等 對稱矩陣，下三角放入一位數組 B[n(n+1)/2]中，Aij對應i(i-1)/2+j-1或者代換aij=aji 上三角矩陣（含常量c），n(n+1)/2+1。aij=（n+n-i+2）(i-1)/2+(j-i)

1

2

3

4

5

6

7

8

9

10

11

12

樹的基本概念（選擇題）

節點的度：節點的孩子個數。 樹的度：樹中節點的最大度數。

樹中節點數 = 總度數+1。（重要）

總度數 = 邊數的2倍。 （重要）

樹的深度是從上往下的，高度是從下往上的，值都一樣。

度為m的樹中，第i層上最多有m^i-1個節點。

高度為h的m叉樹中，最多有(m^h-1)/(m-1)個節點

有序樹左右節點無法互換。

二叉樹概念（選擇題）：

父節點編號為i/2。

葉子節點個數 = 度為2的節點數+1，即n0=n2+1。

證明， 因為n = n1+2*n2+1， 且n=n0+n1+n2。

第k層有2^k-1個節點。

存儲方式

順序存儲：構造成完全二叉樹，用0填空，層次存入數組。

鏈式存儲：指向左右孩子指針。

遍歷：先序，中序，后序，層次（大題）

樹轉二叉樹：在兄弟節點間加跟線，根節點只保留第一個孩子的連線。

森林轉二叉樹，每棵樹都先轉二叉樹，然后兄弟節點連線，保留第一跟，順時針轉45度。

幾種特殊的樹（大題）

二叉排序樹，左子樹<根節點<右子樹。

中序遍歷為從小到大排序。

哈夫曼樹

節點帶權路徑長度，為任意結點到根的總和。

樹的帶權路徑長度，為所有葉節點的帶權路徑長度之和。

圖的基本概念（選擇題）

無向完全圖邊數 = n*(n-1)/2， 有向圖不需要除2。有向帶權圖又稱為網。

度數總和 = 邊數的兩倍。

存儲結構

鄰接矩陣， 鄰接表，十字鏈表，鄰接多重表。判斷條件。

圖的遍歷

DFS，BFS，求遍歷序列。 一次dfs，連通圖。

圖的應用（大題）

最小生成樹

Prim：去掉所有的邊，任選一個頂點。選點（與當前點集最近，不構成回路）。重復直到聯通即可。

Kruskal：去掉所有的邊。 選邊（邊權最小，不構成回路）。重復直到圖聯通。

最短路

Dijkstra：將點集分為在最短路中的和不在的。每次去不在的中找距離最近的加入最短路加入最短路，并用其去松弛其余邊。

拓撲排序

AOV網，頂點表示活動，邊表示活動順序。

每次從AOV網中選擇一個沒有前驅的頂點輸出，并刪除該頂點和所有以它為起點的有向邊。

關鍵路徑

AOE網，頂點表示事件，有向邊表示活動，邊上權值表示活動開銷。

關鍵路徑：從開始點到結束點的所有路徑中，具有最大路徑長度的路徑。關鍵活動為關鍵路徑上的活動，即有向邊。

事件vk的最早發生時間為最大前驅。 ve(k) = MAX{ve(j)+weight(vj,vk)};，vj為前驅。

事件vk的最遲發生時間為最小前驅。vl(k) = MIN{vl(j)-weight(vj,vk)};，vj為前驅。

活動的最早開始時間e(i) = 為起點的最早發生時間

活動的最晚開始時間l(i) = 終點的最遲發生事件 — 活動所需時間。

求關鍵路徑：求出所有點的最早開始時間和最晚發生時間。再求出所有活動的最早和最晚發生時間。 額差d()=l()-e()。 d()=0的為關鍵路徑。

查找的考點

查找

查找表（查找結構）：用于查找的數據集合。

關鍵字：數據元素中某個數據項的值，可以標識一個數據元素。主關鍵字可以唯一標識。

平均查找長度：所有查找過程中進行關鍵字比較次數的平均值。 A S L = ∑ i = 1 n P i C i ASL=\sum_{i=1}^nP_iC_i ASL=∑i=1n Pi Ci

Pi為查找第i個元素的概率（一般每個元素都相等，即1/n），Ci為找到第i個元素需要的比較次數。

順序查找的平均查找長度為 ：成功 = ∑ i = 1 n 1 n ( n ? i + 1 ) = n + 1 2 \sum_{i=1}^n\frac{1}{n}(n-i+1) = \frac{n+1}{2} ∑i=1n n1 (n?i+1)=2n+1 ， 失敗 = n+1。

折半查找的平均查找長度為：成功 = n + 1 n l o g 2 ( n + 1 ) ? 1 \frac{n+1}{n}log_2(n+1)-1 nn+1 log2 (n+1)?1。

折半查找比較次數，可以畫出判定樹，看路過幾個節點。

散列表

一種散列存儲方法。

散列函數Hash(key) = Addr。把兩個不同關鍵詞映射到同一地址稱為同義詞。

（1）直接定址法： H(key) = a*key+b。（2）除留余數法： H(key) = key%p。

散列沖突的處理方法 & 構造散列表：（大題）

（1）開放定址法：線性探測法di=0,1,2。平方探測法di=0^2,。再散列法di=hash2(key)

查找不成功的平均查找長度 = 查找次數（1+13+12+。。2） / 散列后的地址個數（13）=7

（2）拉鏈法： 存放到線性鏈表中。 ^符號表示后繼指針為空。

散列表的查找長度取決于3個因素：散列函數，沖突處理方法，裝填因子。

裝填因子a = 表中記錄數n / 散列表長度m。 a越大，記錄越滿，沖突可能性越大。

排序的考點：

排序的概念

穩定性， 相對位置保持不變。

內部排序：元素全部在內存中。基于比較和移動。外部排序需要外存。

插入排序

直接插入排序：假設已經排好序，插入即可。

希爾排序：把相隔某個增量的記錄組成一個子表，對各個子表進行直接插入排序。整體基本有序后，整體直接插入。

空間O(1)，時間不確定，不穩定。一般初始是穩定的，優化后不穩定。

e.g，取增量d=5，組成多個子表，各排一次。再取d=3，再排一次。最后取增量d=1，即整體插入排序。

交換排序

冒泡排序。優化后快速排序。

選擇排序：

簡單選擇排序。優化后堆排序。

堆指的是：根節點比左右節點小或大的二叉樹。

構造大根堆：默認序列是二叉樹。

歸并排序

基數排序（基于關鍵字的各位大小）

先分配：先按照個位進行分類，構造鏈表。

再收集：按照順序寫到一起。

以此類推，操作十位和百位，最后就有序了。

給生日排序，基數排序是比較快的。

數據結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。