基礎(chǔ)知識(shí)
基本概念
程序 = 算法 + 數(shù)據(jù)結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)置蜀、組織數(shù)據(jù)的方式芭析。
數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合苛萎。
通常情況下座舍，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運(yùn)行或者存儲(chǔ)效率港令。
數(shù)據(jù)結(jié)構(gòu)往往同高效的檢索算法和索引技術(shù)有關(guān)。
常見數(shù)據(jù)結(jié)構(gòu)
集合：set秕磷，multiset
線性結(jié)構(gòu)：數(shù)組诵闭、鏈表、隊(duì)列澎嚣、棧
樹形結(jié)構(gòu)：二叉樹及其變型疏尿，線段樹，巴拉巴拉
圖形結(jié)構(gòu)：各種圖
棧和隊(duì)列
棧Stack
先進(jìn)后出(FILO)
FILO
隊(duì)列Queue
先進(jìn)先出(FIFO)
FIFO
樹和堆
樹的定義
樹（tree）是包含n（n>0）個(gè)結(jié)點(diǎn)的有窮集易桃，其中：
- 每個(gè)元素稱為結(jié)點(diǎn)（node）
- 有一個(gè)特定的結(jié)點(diǎn)被稱為根結(jié)點(diǎn)或樹根（root）
- 除根結(jié)點(diǎn)之外的其余數(shù)據(jù)元素被分為m（m≥0）個(gè)互不相交的集合T1褥琐，T2，……Tm-1晤郑，其中每一個(gè)集合Ti（1<=i<=m）本身也是一棵樹敌呈，被稱作原樹的子樹（subtree）贸宏。
- 空集也是一棵樹
樹去掉根節(jié)點(diǎn)叫做森林
樹的定義的等價(jià)命題
- 設(shè)G=<V,E>是n階m條邊的無向圖，則下面各命題是等價(jià)的：
- G 是樹.
- G 中任意兩個(gè)頂點(diǎn)之間存在惟一的路徑.
- G 中無回路且 m=n-1.
- G 是連通的且 m=n-1.
- G 是連通的且 G 中任何邊均為橋.
- G 中沒有回路磕洪，但在任何兩個(gè)不同的頂點(diǎn)之間加一條新邊吭练，在所得圖中得到惟一的一個(gè)含新邊的圈.
樹的性質(zhì)
- 如果G是樹，那么邊數(shù)=頂點(diǎn)數(shù)-1
- 樹中任意兩點(diǎn)存在唯一路徑
- 樹是連通的而且任何邊均為橋
- 在樹中不同兩點(diǎn)加上一個(gè)邊會(huì)得到唯一一個(gè)圈
二叉樹
二叉樹
- 二叉樹是每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹的樹結(jié)構(gòu)析显。通常子樹被稱作“左子樹”和“右子樹”鲫咽。二叉樹常被用于實(shí)現(xiàn)二叉查找樹和二叉堆。
- 一棵深度為k谷异，且有2(k-1)個(gè)節(jié)點(diǎn)稱之為滿二叉樹浑侥，一棵二叉樹第i層最多有2(i-1)個(gè)節(jié)點(diǎn)；
- 深度為k晰绎，有n個(gè)節(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)節(jié)點(diǎn)都與深度為k的滿二叉樹中括丁，序號(hào)為1至n的節(jié)點(diǎn)對(duì)應(yīng)時(shí)荞下，稱之為完全二叉樹。
任何一個(gè)包含n個(gè)節(jié)點(diǎn)完全二叉樹(滿足從根節(jié)點(diǎn)開始史飞，依次從上往下尖昏，從左往右遍歷子節(jié)點(diǎn)，進(jìn)行標(biāo)記构资。如上圖)抽诉，對(duì)于任何下標(biāo)為i的節(jié)點(diǎn)來說，1≤i≤n 有：
- 當(dāng)i≠1時(shí)吐绵，parent(i)在?i/2?.i=1時(shí),i是樹根迹淌，沒有父節(jié)點(diǎn)。
- 當(dāng)2i≤n時(shí)己单，lchild(i)在2i唉窃。2i>n，i沒有左孩子纹笼。
- 當(dāng)2i+1≤n時(shí)纹份，rchild(i)在2i+1.2i+1>n,i沒有右孩子。
堆(Heap)
- 最大堆:每個(gè)節(jié)點(diǎn)的值都大于等于它的孩子節(jié)點(diǎn)廷痘。
- 最小堆:每個(gè)節(jié)點(diǎn)的值都小于等于它的孩子節(jié)點(diǎn)蔓涧。
堆的存儲(chǔ)
- 可以理解為二叉樹的一種，是節(jié)點(diǎn)間有序關(guān)系的完全二叉樹笋额，所以可以用數(shù)組來表示元暴。
- 對(duì)于下標(biāo)為i的節(jié)點(diǎn)，它的子樹的左節(jié)點(diǎn)的下標(biāo)為2i,右節(jié)點(diǎn)為2i+1兄猩，父親的節(jié)點(diǎn)下標(biāo)為i/2（向下取整）昨寞。
- 在程序設(shè)計(jì)中瞻惋，使用位運(yùn)算來代替直接*2可以提高運(yùn)行速度。-
- 某些編譯器中會(huì)把一些特定的乘法運(yùn)算改寫為位運(yùn)算援岩。
前綴歼狼、中綴、后綴表達(dá)式轉(zhuǎn)換與求值
- 前綴表達(dá)式：運(yùn)算符位于操作數(shù)之前享怀。
- 中綴表達(dá)式：操作符處于操作數(shù)的中間羽峰。中綴表達(dá)式是人們常用的算術(shù)表示方法。(但是計(jì)算機(jī)計(jì)算中綴表達(dá)式是復(fù)雜的添瓷，所以一般需要將中綴表達(dá)式轉(zhuǎn)換成前綴或者后綴表達(dá)式)
- 后綴表達(dá)式：運(yùn)算符位于操作數(shù)之后梅屉。
舉例：
(3+4)×5-6 中綴表達(dá)式
-×+3456 前綴表達(dá)式
34+5×6- 后綴表達(dá)式
前綴表達(dá)式的計(jì)算機(jī)求值：
從右至左掃描表達(dá)式，遇到數(shù)字時(shí)鳞贷，將數(shù)字壓入堆棧坯汤，遇到運(yùn)算符時(shí)，彈出棧頂?shù)膬蓚€(gè)數(shù)搀愧，用運(yùn)算符對(duì)它們做相應(yīng)的計(jì)算（棧頂元素 op 次頂元素）惰聂，并將結(jié)果入棧；重復(fù)上述過程直到表達(dá)式最左端咱筛，最后運(yùn)算得出的值即為表達(dá)式的結(jié)果搓幌。
例如前綴表達(dá)式“- × + 3 4 5 6”：
- 從右至左掃描，將6迅箩、5溉愁、4、3壓入堆棧饲趋；
- 遇到+運(yùn)算符拐揭，因此彈出3和4（3為棧頂元素，4為次頂元素奕塑，注意與后綴表達(dá)式做比較）投队，計(jì)算出3+4的值，得7爵川，再將7入棧敷鸦；
- 接下來是×運(yùn)算符，因此彈出7和5寝贡，計(jì)算出7×5=35扒披，將35入棧；
- 最后是-運(yùn)算符圃泡，計(jì)算出35-6的值碟案，即29，由此得出最終結(jié)果颇蜡。
后綴表達(dá)式的計(jì)算機(jī)求值：
與前綴表達(dá)式類似价说，只是順序是從左至右：
從左至右掃描表達(dá)式辆亏，遇到數(shù)字時(shí)，將數(shù)字壓入堆棧鳖目，遇到運(yùn)算符時(shí)扮叨，彈出棧頂?shù)膬蓚€(gè)數(shù)，用運(yùn)算符對(duì)它們做相應(yīng)的計(jì)算（次頂元素 op 棧頂元素）领迈，并將結(jié)果入棧彻磁；重復(fù)上述過程直到表達(dá)式最右端，最后運(yùn)算得出的值即為表達(dá)式的結(jié)果狸捅。
例如后綴表達(dá)式“3 4 + 5 × 6 -”：
- 從左至右掃描衷蜓，將3和4壓入堆棧；
- 遇到+運(yùn)算符尘喝，因此彈出4和3（4為棧頂元素磁浇，3為次頂元素，注意與前綴表達(dá)式做比較）朽褪，計(jì)算出3+4的值置吓，得7，再將7入棧鞍匾；
- 將5入棧；
- 接下來是×運(yùn)算符骑科，因此彈出5和7橡淑，計(jì)算出7×5=35，將35入棧咆爽；
- 將6入棧梁棠；
- 最后是-運(yùn)算符，計(jì)算出35-6的值斗埂，即29符糊，由此得出最終結(jié)果。
將中綴表達(dá)式轉(zhuǎn)換為前綴表達(dá)式：
- 初始化兩個(gè)棧：運(yùn)算符棧S1和儲(chǔ)存中間結(jié)果的棧S2呛凶；
- 從右至左掃描中綴表達(dá)式男娄；
- 遇到操作數(shù)時(shí)，將其壓入S2漾稀；
- 遇到運(yùn)算符時(shí)模闲，比較其與S1棧頂運(yùn)算符的優(yōu)先級(jí)：
- 如果S1為空，或棧頂運(yùn)算符為右括號(hào)“)”崭捍，則直接將此運(yùn)算符入棧尸折；
- 否則，若優(yōu)先級(jí)比棧頂運(yùn)算符的較高或相等殷蛇，也將運(yùn)算符壓入S1实夹；
- 否則橄浓，將S1棧頂?shù)倪\(yùn)算符彈出并壓入到S2中，再次轉(zhuǎn)到4-1與S1中新的棧頂運(yùn)算符相比較亮航；
- 遇到括號(hào)時(shí)：
- 如果是右括號(hào)“)”荸实，則直接壓入S1；
- 如果是左括號(hào)“(”塞赂，則依次彈出S1棧頂?shù)倪\(yùn)算符泪勒，并壓入S2，直到遇到右括號(hào)為止宴猾，此時(shí)將這一對(duì)括號(hào)丟棄圆存；
- 重復(fù)步驟(2)至(5)，直到表達(dá)式的最左邊仇哆；
- 將S1中剩余的運(yùn)算符依次彈出并壓入S2沦辙；
- 依次彈出S2中的元素并輸出，結(jié)果即為中綴表達(dá)式對(duì)應(yīng)的前綴表達(dá)式讹剔。
將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式：
- 初始化兩個(gè)棧：運(yùn)算符棧S1和儲(chǔ)存中間結(jié)果的棧S2油讯；
- 從左至右掃描中綴表達(dá)式；
- 遇到操作數(shù)時(shí)延欠，將其壓入S2陌兑；
- 遇到運(yùn)算符時(shí)，比較其與S1棧頂運(yùn)算符的優(yōu)先級(jí)：
- 如果S1為空由捎，或棧頂運(yùn)算符為左括號(hào)“(”兔综，則直接將此運(yùn)算符入棧；
- 否則狞玛，若優(yōu)先級(jí)比棧頂運(yùn)算符的高软驰，也將運(yùn)算符壓入S1（注意轉(zhuǎn)換為前綴表達(dá)式時(shí)是優(yōu)先級(jí)較高或相同，而這里則不包括相同的情況）心肪；
- 否則锭亏，將S1棧頂?shù)倪\(yùn)算符彈出并壓入到S2中，再次轉(zhuǎn)到4-1與S1中新的棧頂運(yùn)算符相比較硬鞍；
- 遇到括號(hào)時(shí)：
- 如果是左括號(hào)“(”慧瘤，則直接壓入S1；
- 如果是右括號(hào)“)”固该，則依次彈出S1棧頂?shù)倪\(yùn)算符碑隆，并壓入S2，直到遇到左括號(hào)為止蹬音，此時(shí)將這一對(duì)括號(hào)丟棄上煤；
- 重復(fù)步驟(2)至(5)，直到表達(dá)式的最右邊著淆；
- 將S1中剩余的運(yùn)算符依次彈出并壓入S2劫狠；
- 依次彈出S2中的元素并輸出拴疤，結(jié)果的逆序即為中綴表達(dá)式對(duì)應(yīng)的后綴表達(dá)式（轉(zhuǎn)換為前綴表達(dá)式時(shí)不用逆序）。
