一浪册、緒論
1.1 數(shù)據(jù)結構的基本概念
邏輯結構：線性、非線性（樹岗照、圖村象、網(wǎng)、集合）
非線性數(shù)據(jù)結構：其邏輯特征是一個結點元素可能有多個直接前驅和多個直接后繼
存儲密度
“單鏈表的存儲密度小于1攒至。原因：“存儲密度=單鏈表數(shù)據(jù)項所占空間/結點所占空間”厚者，而“ 結點所占空間＝數(shù)據(jù)項所占空間＋存放后繼結點地址的鏈域”；所以迫吐，存儲密度小于1库菲。”
1.2算法和算法評價
算法五大特征：
輸入志膀、輸出熙宇、有窮性、確定性和可行性
二溉浙、線性表
2.1 定義
廣義表對應樹
Q:假定一棵樹的廣義表表示為A（C烫止，D（E，F(xiàn)戳稽，G）馆蠕，H（I，J））惊奇，則樹的長度互躬、深度為？
A: 3赊时，2吨铸。
2.2 線性表的順序表示
2.3 線性表的鏈式表示
三、棧和隊列
3.1 棧
3.2 隊列
數(shù)組Q[0…n]用來表示一個循環(huán)隊列祖秒，f為當前隊頭元素的前一位置诞吱，r為隊尾元素的位置舟奠，假定隊列中元素的個數(shù)總小于n，計算：
注意：區(qū)別表達式——
隊空房维、隊滿沼瘫、隊中元素數(shù)量
犧牲一個單元時：
隊空：Q.f=Q.r
隊滿：(Q.r+1)%n=Q.f
隊列中元素個數(shù):(n+Q.r-Q.f)% n
波蘭式（前綴）
是在通常的表達式中，二元運算符總是置于與之相關的兩個運算對象之前咙俩，所以耿戚，這種表示法也稱為前綴表達式。
棧和隊列都是線性表阿趁？·
他們是受限線性表膜蛔。線性表（linear list）是數(shù)據(jù)結構的一種，一個線性表是n個具有相同特性的數(shù)據(jù)元素的有限序列脖阵，分一般線性表和受限線性表皂股。
3.3 棧和隊列的應用
括號匹配
表達式求值P92
在運算符優(yōu)先原則下，畫出運算符棧和操作數(shù)棧的變化過程：
檢測到括號命黔，則可以彈出呜呐。。悍募。
遞歸
層次遍歷
計算機系統(tǒng)
3.4 特殊矩陣的壓縮存儲
四蘑辑、串
4.1 串的定義和實現(xiàn)
Q：兩個字符串相等的充要條件？
A：長度相等坠宴；對應位置字符相同洋魂。
4.2 串的模式匹配
Next數(shù)組：
| 序號 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 模式串M | a | b | a | b | a | a | a | b | a |
| Next[j] | 0 | 1 | 1 | 1 | 2 | 3 | 4 | 2 | 3 |
| Nextval[j] | 0 | 1 | 0 | 1 | 0 | 4 | 2 | 1 | 0 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
M同，nextval=next指向的nv;
M不同喜鼓，nextval=自己的next
數(shù)組下標忧设，不說就是0，0起颠通，說了一般是1址晕，1起
五、樹與二叉樹
5.1 樹的基本概念
5.2 二叉樹的概念
Q：二叉樹是不是樹的特殊形式?
不是!雖然二叉樹也屬于一種樹結構,但它 是另外單獨定義的一種樹,并非一般樹的特例顿锰。
它的子樹有順序規(guī)定,分為左子樹和右子樹谨垃。不能隨意顛倒。
二叉樹公式合集：
n個結點：n-1個非空指針域（n1+2n2）
n0=n2+1
H=[down log2n]+1 = [up log2(n+1)]
葉子數(shù)n0 = [up n/2] = [奇數(shù) (n+1)/2] = [偶數(shù) n/2]
雙親序號= [down i/2]
孩子序號= [left 2i] = [right 2i+1]
完全二叉樹_編號最小的葉子結點 = [n=奇數(shù) n2+1] = [n=偶數(shù) n2+2]
5.3 二叉樹的遍歷與線索二叉樹
二叉鏈表的空指針：左前驅硼控，右后繼
5.4 樹刘陶、森林
樹的存儲結構
樹有0（空樹）或1個根節(jié)點：
定義：樹是N個結點的有限集合，N=0時為空樹牢撼，任意非空樹應滿足：
1.僅有一個根結點
2.當N>1時匙隔，其余結點又分為互不相交的有限集合，為根結點子樹
樹熏版、森林纷责、二叉樹的轉換
樹轉 二叉樹：左孩子右兄弟：形態(tài)唯一
二叉樹轉 森林：右孩子變兄弟捍掺，右孩子的右孩子也變兄弟
樹和森林的遍歷
普通樹：某個節(jié)點可能有多個孩子，沒有中根遍歷
森林：由多棵樹組成再膳，邏輯上沒有后序遍歷
5.5 樹與二叉樹的應用
二叉排序樹
平衡二叉樹
目的：避免樹增高過快
平衡因子：h左-h右
LL（右單旋轉）
RR（左單旋轉）
這里的LL挺勿、RR指的是初始狀態(tài)而不是操作動作，因為動作和狀態(tài)是反著來的
LR喂柒、RL旋轉則不會引起歧義
5.5.3 哈夫曼樹和哈夫曼編碼
- 哈夫曼樹：n1=0
WPL最小的二叉樹
WPL=(W1L1+W2L2+W3L3+...+WnLn)
n = 2n0-1個結點（n0為葉子數(shù)）
H_max = n2+1 = n0
H_min = [up log2(n+1)]
- 哈夫曼編碼
末端矩形內(nèi)容：字符+出現(xiàn)次數(shù)
只有度為0不瓶、1的結點！（若有000灾杰，必有001）
六蚊丐、圖
6.1圖的基本概念
關節(jié)點
如果一個連通的無向圖中的任一頂點被刪除后，剩下的圖仍然連通艳吠，那么這樣的無向連通圖就稱作是雙連通的(biconnected)吠撮。(上圖的無向圖是雙連通的)
如果一個圖不是雙連通的，也就是說存在一些頂點讲竿，將其刪除后圖將不在連通，我們把那些頂點稱為割點或者關節(jié)點(articulation point)弄屡。
6.2圖的存儲與基本操作
存儲結構：
鄰接矩陣法O(n^2)
鄰接表法O(n+e)
6.3圖的遍歷
6.3.1 BFS
6.3.2 DFS
Q：深度優(yōu)先生成樹怎么畫题禀？
A：可以有多個兒子，不一定是二叉樹膀捷，所以隨意畫就行迈嘹；
注意，連通圖才有生成樹全庸，非連通圖產(chǎn)生生成森林秀仲。
6.3.4 圖的遍歷與圖的連通性
無向圖的最小生成樹：包含所有V，不成環(huán)壶笼，保持有連通最少的邊
無向圖的連通分量：極大連通子圖神僵，一定成環(huán)
無向圖：度=邊的2倍
無向連通圖至少有n個結點
無向非連通圖至少有n+1個結點
有向連通圖至少有n個結點
有向非連通圖至少有n+1個結點
6.4圖的應用
任何一個無向連通圖的最小生成樹為什么有一棵或多棵呢？
一棵：只有兩個結點
多棵：保持連通即可
6.4.1 最小生成樹：
6.4.1.1 Prim普里姆算法（稠密）：不斷加頂點覆劈、邊
O(V^2)
邊數(shù)較多可以用普里姆算法保礼，因為它是每次加一個頂點，對邊數(shù)多的適用责语。
6.4.1.2 Kruskal克魯斯卡爾算法（稀疏）：不斷連邊
O(ElogE)
邊數(shù)較少可以用Kruskal克魯斯卡爾算法炮障，因為克魯斯卡爾算法算法每次查找最短的邊。
6.4.2 最短路徑
6.4.2.1 Dijkstra（單源最短路徑）
每一輪新加入一個頂點到集合S中坤候，之后該頂點的行標記打鉤胁赢，即不更新。
6.4.2.2 Floyd（每對頂點的最短路徑）
逐步嘗試在原路徑加入頂點k作為中間頂點白筹，若新路徑短于原路徑智末，則代替之谅摄。
6.4.4 拓撲排序
6.4.5 關鍵活動
AOE網(wǎng)
有向邊代表活動
七、查找
7.1查找
靜態(tài)查找
動態(tài)查找：二叉排序樹
動態(tài)查找的過程中對表的操作會多兩個動作：如果某特定的關鍵字在表中不存在吹害，則按照一定的規(guī)則將其插入表中螟凭；如果已經(jīng)存在，則可以對其執(zhí)行刪除操作它呀。動態(tài)查找的過程雖然只是多了“插入”和“刪除”的操作螺男。
7.2 順序查找與折半查找
鏈表是不知道地址的，不能隨機訪問數(shù)據(jù)纵穿，所以用二分查找是不合適的下隧。
總的查找次數(shù)是n/2+n/4+n/8+n/16 +........≈ n
在腦海中想象一下最大值的二分查找，每個數(shù)其實都查找了一遍谓媒。
另外淆院，這里說的比較次數(shù)，如果查找次數(shù)不算是比較次數(shù)的話句惯，那比較次數(shù)應該是你說的log2n.
7.3 B樹和B+樹
判定樹：
查找成功ASL
查找失敗ASL
7.4 散列表
散列表的基本概念
建立關鍵字和地址的直接映射關系
散列函數(shù)的構造方法
散列表處理沖突的方法：
開放定址：
H_i = ( H(key) + d_i ) % m
線性探測法：d_i為常數(shù)
H(key)=key%P土辩，P一般取質數(shù)
平方探測法（二次探測法，平方再散列）：di=1^2,-1^2,2^2,-2^2......
再散列法（雙散列法）：Hi=(H(key) + i*Hash_2(key) ) % m抢野，用第二個散列函數(shù)計算關鍵字地址的增量拷淘，每一次增加1也可以，叫做線性探測再散列
偽隨機序列法：d_i為隨機數(shù)序列
拉鏈法
八指孤、排序
8.1 排序的基本概念
基本有序：
Q:在第i 趟直接插入排序中,要進行 i-1 次關鍵字的比較嗎?
8.2 插入排序
直接插入排序：
折半插入排序
希爾排序
8.3 交換排序
冒泡排序：
沒有發(fā)生交換启涯，提前結束，不會做多余運算
希爾排序
8.4 選擇排序
簡單選擇排序
堆排序
8.5 歸并排序和基數(shù)排序
8.6 各種內(nèi)部排序的應用和比較
8.7 外部排序
九恃轩、數(shù)組和廣義表
數(shù)組：沒說開頭序號结洼，開頭序號就是0,0
廣義表：
GetTail取最后一個元素，尾巴多(一個)括號叉跛；
GetHead 取第一個元素
