期末復習
目錄
- 期末復習
- 線性表
- 堆疊，佇列
- KMP演算法
- 陣列
- 關于高維陣列地址映像公示的使用
- 矩陣壓縮
- 矩陣快速轉置
- 樹
- 二叉樹
- 關于二叉樹的性質
- 先中后序遍歷
- 先中序或中后序還原二叉樹
- 哈夫曼樹
- 構造哈夫曼樹
- 哈夫曼編碼
- 優點
- 圖
- DFS
- BFS
- 最小生成樹
- 最短路徑
線性表
堆疊，佇列
堆疊：https://blog.csdn.net/qq_45775250/article/details/109064878
佇列：https://blog.csdn.net/qq_45775250/article/details/109259985
KMP演算法
本次考試基本掌握KMP的next陣列即可
例如：
a b a a a b b c c
此題答案應為：
-1 0 0 1 1 1 2 0 0
再寫next陣列時第一二位必然為
-1 0，后面的都需要進行比較，比較當前位的前一位與第一位開始有幾個相似，例如第三個a的值為1，是因為第一位a和第三位a的前一個都是a，是一樣的，而第三個b的值為2，是因為，前面是ab與第一二位ab一致，所以是2，也就是說有幾位相同，next陣列對應的值就寫幾
陣列
關于高維陣列地址映像公示的使用
例如下面這個二維陣列：
- 此題中元素個數等于維界的乘積，即5*4=20個
- 題中給出了首元素地址a[1][1]為2000，求a[3][2]的地址，那么我們可以利用公式求出：Loc[3,2] = Loc[1,1] + ( d2*(j1-1)+(j2-1))4
則可以得出式子為2000+（4（3-1）+（2-1））*4 = 2036
二維陣列的計算其實也可以在草稿本上畫出來再進行計算，但是三維以上的陣列則不能畫出空間圖形，必須借助公式如下：
1.本題中元素個數依舊是維界之積567*8=1680個
2.四維陣列知道首元素計算記憶體地址
Loc[3,4,5,4] = Loc[1,1,1,1] + ((d2d3d4)(j1-1) + (d3d4)(j2-1) + d4(j3-1) + (j4-1))*4
則式子為2000 + ((6x7x8)(3-1) + (7x8)(4-1) + 8(5-1)+(4-1))x4 = 5500
以上都是以行序為主序，那么如果以列序為主序則要做出一些小變動，如：
設有陣列A[1…8,1…10],陣列的每個元素占三個位元組，陣列從記憶體首地址BA開始以列序為主序順序存放，則陣列元素A[5,8]的存盤首地址為多少
Loc[5,8] = Loc[1,1] + (d1*(j2-1) + (j1 -1))*3
則列出式子為BA + (8x(8-1) + (5-1))*3 = BA + 180
此時我們可以看到行序與列序的區別，維界的值進行了交換，請自行對比
矩陣壓縮
矩陣壓縮后反推其原來的邏輯位置：
其運算步驟為：
矩陣快速轉置
樹
二叉樹
關于二叉樹的性質
性質1. 二叉樹中第i (i >= 0)層 上的節點數最多為2^i
性質2. 深度為h (h >= 1) 的二叉樹中最多有 (2^h) - 1個結點
性質3. 對于任何一顆二叉樹，若其葉節點的個數為n0，度為2的結點個數為n2， 則有n0 = n2 + 1
性質4. 具有n個結點的完全二叉樹，其深度為?log~2~n? + 1或?log~2~(n+1)?g
性質5. 對于具有n個結點的完全二叉樹，如果按照從上到下和從左到右的順序對二叉樹中的所有結點從1開始順序編號，則對于任意的序號為i的結點有：
先中后序遍歷
先序：若二叉樹為空，則空操作，否則如下
訪問根節點
按先序遍歷左子樹
按先序遍歷右子樹
中序：若二叉樹為空，則空操作，否則如下
按中序遍歷左子樹
訪問根節點
按中序遍歷右子樹
后序：若二叉樹為空，則空操作，否則如下
按后序遍歷左子樹
按后序遍歷右子樹
訪問根節點
例如下面這顆二叉樹：
它的先序中序后序應分別為：
先中序或中后序還原二叉樹
口訣：先序后序確定根，中序找根看左右
例如：
首先我們根據先序找出根節點為A，然后在中序中找到A可以得到，A的左邊為左子樹，右邊為右子樹，可以得出此二叉樹的右子樹只有一個C，然后回傳看先序，此時除A外的左子樹根節點為B，再看中序，中序中B的左邊DE為其左子樹，GF為其右子樹，然后回傳先序，D為B的左子樹的根節點，找到中序中的D，發現D左邊無字母，則它無左子樹，右子樹為E，同理F無右子樹，左子樹為G，此時二叉樹就畫出來了
哈夫曼樹
構造哈夫曼樹
在構造哈夫曼樹時我們首先需要找到權值，權值可以是字母等出現的頻率，也可以是其他代表值，我們需要將這個權值從小到大進行排列，排成一個陣列，然后每次都取其中最小的兩個構成一顆樹直至最后構造出完整的最優二叉樹
例如：
在這個題中，我們可以將字母出現的頻率作為權值，也可以將字母出現的次數作為權值那么我們可以得到一個陣列{4、4、4、5、6、6、6、7、9、9}，然后每次取倆最小相加，把相加之后得到的值再放入此陣列，最后可以得到一個最優二叉樹
哈夫曼編碼
構造好哈夫曼樹之后按照左零右一的原則，對每條分支進行編碼，最后可以得到每個字母的編碼
優點
1.優化流程
2.構造編碼，不會造成不能決議的編碼
圖
DFS
BFS
最小生成樹
最短路徑
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/236582.html
標籤：其他
下一篇：基于FPGA的串口實作