基礎(chǔ)知識
基本概念
程序 = 算法 + 數(shù)據(jù)結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)是計算機(jī)存儲、組織數(shù)據(jù)的方式。
數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。
通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運(yùn)行或者存儲效率。
數(shù)據(jù)結(jié)構(gòu)往往同高效的檢索算法和索引技術(shù)有關(guān)。
常見數(shù)據(jù)結(jié)構(gòu)
集合：set，multiset
線性結(jié)構(gòu)：數(shù)組、鏈表、隊列、棧
樹形結(jié)構(gòu)：二叉樹及其變型，線段樹，巴拉巴拉
圖形結(jié)構(gòu)：各種圖
棧和隊列
棧Stack
先進(jìn)后出(FILO)
FILO
隊列Queue
先進(jìn)先出(FIFO)
FIFO
樹和堆
樹的定義
樹（tree）是包含n（n>0）個結(jié)點的有窮集，其中：
- 每個元素稱為結(jié)點（node）
- 有一個特定的結(jié)點被稱為根結(jié)點或樹根（root）
- 除根結(jié)點之外的其余數(shù)據(jù)元素被分為m（m≥0）個互不相交的集合T1，T2，……Tm-1，其中每一個集合Ti（1<=i<=m）本身也是一棵樹，被稱作原樹的子樹（subtree）。
- 空集也是一棵樹
樹去掉根節(jié)點叫做森林
樹的定義的等價命題
- 設(shè)G=<V,E>是n階m條邊的無向圖，則下面各命題是等價的：
- G 是樹.
- G 中任意兩個頂點之間存在惟一的路徑.
- G 中無回路且 m=n-1.
- G 是連通的且 m=n-1.
- G 是連通的且 G 中任何邊均為橋.
- G 中沒有回路，但在任何兩個不同的頂點之間加一條新邊，在所得圖中得到惟一的一個含新邊的圈.
樹的性質(zhì)
- 如果G是樹，那么邊數(shù)=頂點數(shù)-1
- 樹中任意兩點存在唯一路徑
- 樹是連通的而且任何邊均為橋
- 在樹中不同兩點加上一個邊會得到唯一一個圈
二叉樹
二叉樹
- 二叉樹是每個節(jié)點最多有兩個子樹的樹結(jié)構(gòu)。通常子樹被稱作“左子樹”和“右子樹”。二叉樹常被用于實現(xiàn)二叉查找樹和二叉堆。
- 一棵深度為k，且有2(k-1)個節(jié)點稱之為滿二叉樹，一棵二叉樹第i層最多有2(i-1)個節(jié)點；
- 深度為k，有n個節(jié)點的二叉樹，當(dāng)且僅當(dāng)其每一個節(jié)點都與深度為k的滿二叉樹中，序號為1至n的節(jié)點對應(yīng)時，稱之為完全二叉樹。
任何一個包含n個節(jié)點完全二叉樹(滿足從根節(jié)點開始，依次從上往下，從左往右遍歷子節(jié)點，進(jìn)行標(biāo)記。如上圖)，對于任何下標(biāo)為i的節(jié)點來說，1≤i≤n 有：
- 當(dāng)i≠1時，parent(i)在?i/2?.i=1時,i是樹根，沒有父節(jié)點。
- 當(dāng)2i≤n時，lchild(i)在2i。2i>n，i沒有左孩子。
- 當(dāng)2i+1≤n時，rchild(i)在2i+1.2i+1>n,i沒有右孩子。
堆(Heap)
- 最大堆:每個節(jié)點的值都大于等于它的孩子節(jié)點。
- 最小堆:每個節(jié)點的值都小于等于它的孩子節(jié)點。
堆的存儲
- 可以理解為二叉樹的一種，是節(jié)點間有序關(guān)系的完全二叉樹，所以可以用數(shù)組來表示。
- 對于下標(biāo)為i的節(jié)點，它的子樹的左節(jié)點的下標(biāo)為2i,右節(jié)點為2i+1，父親的節(jié)點下標(biāo)為i/2（向下取整）。
- 在程序設(shè)計中，使用位運(yùn)算來代替直接*2可以提高運(yùn)行速度。-
- 某些編譯器中會把一些特定的乘法運(yùn)算改寫為位運(yùn)算。
前綴、中綴、后綴表達(dá)式轉(zhuǎn)換與求值
- 前綴表達(dá)式：運(yùn)算符位于操作數(shù)之前。
- 中綴表達(dá)式：操作符處于操作數(shù)的中間。中綴表達(dá)式是人們常用的算術(shù)表示方法。(但是計算機(jī)計算中綴表達(dá)式是復(fù)雜的，所以一般需要將中綴表達(dá)式轉(zhuǎn)換成前綴或者后綴表達(dá)式)
- 后綴表達(dá)式：運(yùn)算符位于操作數(shù)之后。
舉例：
(3+4)×5-6 中綴表達(dá)式
-×+3456 前綴表達(dá)式
34+5×6- 后綴表達(dá)式
前綴表達(dá)式的計算機(jī)求值：
從右至左掃描表達(dá)式，遇到數(shù)字時，將數(shù)字壓入堆棧，遇到運(yùn)算符時，彈出棧頂?shù)膬蓚€數(shù)，用運(yùn)算符對它們做相應(yīng)的計算（棧頂元素 op 次頂元素），并將結(jié)果入棧；重復(fù)上述過程直到表達(dá)式最左端，最后運(yùn)算得出的值即為表達(dá)式的結(jié)果。
例如前綴表達(dá)式“- × + 3 4 5 6”：
- 從右至左掃描，將6、5、4、3壓入堆棧；
- 遇到+運(yùn)算符，因此彈出3和4（3為棧頂元素，4為次頂元素，注意與后綴表達(dá)式做比較），計算出3+4的值，得7，再將7入棧；
- 接下來是×運(yùn)算符，因此彈出7和5，計算出7×5=35，將35入棧；
- 最后是-運(yùn)算符，計算出35-6的值，即29，由此得出最終結(jié)果。
后綴表達(dá)式的計算機(jī)求值：
與前綴表達(dá)式類似，只是順序是從左至右：
從左至右掃描表達(dá)式，遇到數(shù)字時，將數(shù)字壓入堆棧，遇到運(yùn)算符時，彈出棧頂?shù)膬蓚€數(shù)，用運(yùn)算符對它們做相應(yīng)的計算（次頂元素 op 棧頂元素），并將結(jié)果入棧；重復(fù)上述過程直到表達(dá)式最右端，最后運(yùn)算得出的值即為表達(dá)式的結(jié)果。
例如后綴表達(dá)式“3 4 + 5 × 6 -”：
- 從左至右掃描，將3和4壓入堆棧；
- 遇到+運(yùn)算符，因此彈出4和3（4為棧頂元素，3為次頂元素，注意與前綴表達(dá)式做比較），計算出3+4的值，得7，再將7入棧；
- 將5入棧；
- 接下來是×運(yùn)算符，因此彈出5和7，計算出7×5=35，將35入棧；
- 將6入棧；
- 最后是-運(yùn)算符，計算出35-6的值，即29，由此得出最終結(jié)果。
將中綴表達(dá)式轉(zhuǎn)換為前綴表達(dá)式：
- 初始化兩個棧：運(yùn)算符棧S1和儲存中間結(jié)果的棧S2；
- 從右至左掃描中綴表達(dá)式；
- 遇到操作數(shù)時，將其壓入S2；
- 遇到運(yùn)算符時，比較其與S1棧頂運(yùn)算符的優(yōu)先級：
- 如果S1為空，或棧頂運(yùn)算符為右括號“)”，則直接將此運(yùn)算符入棧；
- 否則，若優(yōu)先級比棧頂運(yùn)算符的較高或相等，也將運(yùn)算符壓入S1；
- 否則，將S1棧頂?shù)倪\(yùn)算符彈出并壓入到S2中，再次轉(zhuǎn)到4-1與S1中新的棧頂運(yùn)算符相比較；
- 遇到括號時：
- 如果是右括號“)”，則直接壓入S1；
- 如果是左括號“(”，則依次彈出S1棧頂?shù)倪\(yùn)算符，并壓入S2，直到遇到右括號為止，此時將這一對括號丟棄；
- 重復(fù)步驟(2)至(5)，直到表達(dá)式的最左邊；
- 將S1中剩余的運(yùn)算符依次彈出并壓入S2；
- 依次彈出S2中的元素并輸出，結(jié)果即為中綴表達(dá)式對應(yīng)的前綴表達(dá)式。
將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式：
- 初始化兩個棧：運(yùn)算符棧S1和儲存中間結(jié)果的棧S2；
- 從左至右掃描中綴表達(dá)式；
- 遇到操作數(shù)時，將其壓入S2；
- 遇到運(yùn)算符時，比較其與S1棧頂運(yùn)算符的優(yōu)先級：
- 如果S1為空，或棧頂運(yùn)算符為左括號“(”，則直接將此運(yùn)算符入棧；
- 否則，若優(yōu)先級比棧頂運(yùn)算符的高，也將運(yùn)算符壓入S1（注意轉(zhuǎn)換為前綴表達(dá)式時是優(yōu)先級較高或相同，而這里則不包括相同的情況）；
- 否則，將S1棧頂?shù)倪\(yùn)算符彈出并壓入到S2中，再次轉(zhuǎn)到4-1與S1中新的棧頂運(yùn)算符相比較；
- 遇到括號時：
- 如果是左括號“(”，則直接壓入S1；
- 如果是右括號“)”，則依次彈出S1棧頂?shù)倪\(yùn)算符，并壓入S2，直到遇到左括號為止，此時將這一對括號丟棄；
- 重復(fù)步驟(2)至(5)，直到表達(dá)式的最右邊；
- 將S1中剩余的運(yùn)算符依次彈出并壓入S2；
- 依次彈出S2中的元素并輸出，結(jié)果的逆序即為中綴表達(dá)式對應(yīng)的后綴表達(dá)式（轉(zhuǎn)換為前綴表達(dá)式時不用逆序）。
