結(jié)構(gòu)化編程

1. 一行一行執(zhí)行
2. 有條件控制語(yǔ)句 if...else...
3. 有循環(huán)控制語(yǔ)句 while(exp) do...

偽代碼

流程圖

算法

1. 輸入：一個(gè)算法必須有零個(gè)或以上輸入量。
2. 輸出：一個(gè)算法應(yīng)有一個(gè)或以上輸出量，輸出量是算法計(jì)算的結(jié)果。
3. 明確性：算法的描述必須無(wú)歧義，以保證算法的實(shí)際執(zhí)行結(jié)果是精確地 匹配要求或期望，通常要求實(shí)際運(yùn)行結(jié)果是確定的。
4. 有限性：依據(jù)圖靈的定義，一個(gè)算法是能夠被任何圖靈完備系統(tǒng)模擬的一串運(yùn)算，而圖靈機(jī)只有有限個(gè)狀態(tài)、有限個(gè)輸入符號(hào)和有限個(gè)轉(zhuǎn)移函數(shù)（指令）。而一些定義更規(guī)定算法必須在有限個(gè)步驟內(nèi)完成任務(wù)。
5. 有效性：又稱(chēng)可行性。能夠?qū)崿F(xiàn)，算法中描述的操作都是可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)。

數(shù)據(jù)結(jié)構(gòu)

即數(shù)據(jù)的結(jié)構(gòu)

哈希（Hash）

鍵值對(duì)： { '鍵' : '值' } ==> Array / Object

• 計(jì)數(shù)排序：計(jì)數(shù)排序使用一個(gè)額外的數(shù)組 arr （hash），其中第 i 個(gè)元素是待排序數(shù)組 Arr 中值等于 i 的元素的個(gè)數(shù)。然后根據(jù)數(shù)組 arr 來(lái)將 Arr 中的元素排到正確的位置（用到了桶，但是每個(gè)桶中只有相同的數(shù)字，空間浪費(fèi)）（所有的桶是Hash，桶里是隊(duì)列，先進(jìn)先出）。
  復(fù)雜度：n + max
  缺點(diǎn)：
  1. 需要一個(gè)哈希表示計(jì)數(shù)工具。
  2. 無(wú)法對(duì)小數(shù)和負(fù)數(shù)排序

• 桶排序：將數(shù)組分到有限數(shù)量的桶里。每個(gè)桶再個(gè)別排序，此時(shí)可以用其他排序方法（所有的桶是Hash，桶里是隊(duì)列，先進(jìn)先出）

• 基數(shù)排序：只有十個(gè)桶（0 - 9），先排個(gè)位，之后十位，依次到最高位（所有的桶是Hash，桶里是隊(duì)列，先進(jìn)先出）
  說(shuō)明：比較排序的極限 n*logN

隊(duì)列（queue）

• 特點(diǎn)：先進(jìn)先出
• 可以用數(shù)組實(shí)現(xiàn)

棧（stack）

• 特點(diǎn)：先進(jìn)后出
• 可以用數(shù)組實(shí)現(xiàn)

鏈表（Linked List）

• 是一種線(xiàn)性表，但是并不會(huì)按線(xiàn)性的順序存儲(chǔ)數(shù)據(jù)，而是在每一個(gè)節(jié)點(diǎn)里存到下一個(gè)節(jié)點(diǎn)的指針(Pointer)。使用鏈表結(jié)構(gòu)可以克服數(shù)組鏈表需要預(yù)先知道數(shù)據(jù)大小的缺點(diǎn)，鏈表結(jié)構(gòu)可以充分利用計(jì)算機(jī)內(nèi)存空間，實(shí)現(xiàn)靈活的內(nèi)存動(dòng)態(tài)管理。但是鏈表失去了數(shù)組隨機(jī)讀取的優(yōu)點(diǎn)，同時(shí)鏈表由于增加了結(jié)點(diǎn)的指針域，空間開(kāi)銷(xiāo)比較大

• 數(shù)組無(wú)法直接刪除中間的一項(xiàng)，但是鏈表可以，鏈表是動(dòng)態(tài)數(shù)組

• Hash 實(shí)現(xiàn)鏈表，head 表示第一個(gè) Hash ，所有的 Hash 都是節(jié)點(diǎn)（node）

樹(shù)

• 是一種抽象數(shù)據(jù)類(lèi)型（ADT）或是實(shí)作這種抽象數(shù)據(jù)類(lèi)型的數(shù)據(jù)結(jié)構(gòu)，用來(lái)模擬具有樹(shù)狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。它是由n（n>0）個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合

• 特點(diǎn)：

  1. 每個(gè)節(jié)點(diǎn)有零個(gè)或多個(gè)子節(jié)點(diǎn)
  2. 沒(méi)有父節(jié)點(diǎn)的節(jié)點(diǎn)稱(chēng)為根節(jié)點(diǎn)
  3. 每一個(gè)非根節(jié)點(diǎn)有且只有一個(gè)父節(jié)點(diǎn)
  4. 除了根節(jié)點(diǎn)外，每個(gè)子節(jié)點(diǎn)可以分為多個(gè)不相交的子樹(shù)

• 術(shù)語(yǔ)：

  1. 節(jié)點(diǎn)的層次：從根開(kāi)始定義起，根為第1層，根的子節(jié)點(diǎn)為第2層，以此類(lèi)推；
  2. 深度：對(duì)于任意節(jié)點(diǎn)n,n的深度為從根到n的唯一路徑長(zhǎng)，根的深度為0；
  3. 節(jié)點(diǎn)的度：一個(gè)節(jié)點(diǎn)含有的子樹(shù)的個(gè)數(shù)稱(chēng)為該節(jié)點(diǎn)的度；
  4. 樹(shù)的度：一棵樹(shù)中，最大的節(jié)點(diǎn)的度稱(chēng)為樹(shù)的度；
  5. 葉節(jié)點(diǎn)或終端節(jié)點(diǎn)：度為零的節(jié)點(diǎn)；

• 二叉樹(shù)（Binary tree）：每個(gè)節(jié)點(diǎn)最多含有兩個(gè)子樹(shù)的樹(shù)稱(chēng)為二叉樹(shù)

  1. 二叉樹(shù)的第 i 層至多擁有2的( i-1 )次冪個(gè)節(jié)點(diǎn)數(shù)

• 完全二叉樹(shù)：對(duì)于一顆二叉樹(shù)，假設(shè)其深度為d（d>1）。除了第d層外，其它各層的節(jié)點(diǎn)數(shù)目均已達(dá)最大值，且第d層所有節(jié)點(diǎn)從左向右連續(xù)地緊密排列，這樣的二叉樹(shù)被稱(chēng)為完全二叉樹(shù)

  1. 在一棵二叉樹(shù)中，除最后一層外，若其余層都是滿(mǎn)的，并且最后一層或者是滿(mǎn)的，或者是在右邊缺少連續(xù)若干節(jié)點(diǎn)，則此二叉樹(shù)為完全二叉樹(shù)（Complete Binary Tree）

  2. 具有n個(gè)節(jié)點(diǎn)的完全二叉樹(shù)的深度為log以2為底n的對(duì)數(shù)＋1。深度為k的完全二叉樹(shù)，至少有2的ｋ次冪個(gè)節(jié)點(diǎn)，至多有2的( k+1 )次冪 - 1個(gè)節(jié)點(diǎn)

• 滿(mǎn)二叉樹(shù)：所有葉節(jié)點(diǎn)都在最底層的完全二叉樹(shù)

  1. 一棵深度為k，且有2的( k+1 )次冪 - 1個(gè)節(jié)點(diǎn)的二叉樹(shù)，稱(chēng)為滿(mǎn)二叉樹(shù)（Full Binary Tree）

  2. 每一層上的節(jié)點(diǎn)數(shù)都是最大節(jié)點(diǎn)數(shù)

說(shuō)明：用數(shù)組存儲(chǔ)滿(mǎn)二叉樹(shù)和完全二叉樹(shù)，用Hash存儲(chǔ)其他的樹(shù)

算法和數(shù)據(jù)結(jié)構(gòu)結(jié)合

1. 我們要解決一個(gè)跟數(shù)據(jù)相關(guān)的問(wèn)題
2. 分析這個(gè)問(wèn)題，想出對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)
3. 分析數(shù)據(jù)結(jié)構(gòu)，想出算法
   數(shù)據(jù)結(jié)構(gòu)和算法是互相依存、不可分開(kāi)的

分類(lèi)：

1. 分治法：把一個(gè)問(wèn)題分區(qū)成互相獨(dú)立的多個(gè)部分分別求解的思路。這種求解思路帶來(lái)的好處之一是便于進(jìn)行并行計(jì)算。前端主要使用分治法

2. 動(dòng)態(tài)規(guī)劃法：當(dāng)問(wèn)題的整體最優(yōu)解就是由局部最優(yōu)解組成的時(shí)候，經(jīng)常采用的一種方法

3. 貪婪算法：常見(jiàn)的近似求解思路。當(dāng)問(wèn)題的整體最優(yōu)解不是（或無(wú)法證明是）由局部最優(yōu)解組成，且對(duì)解的最優(yōu)性沒(méi)有要求的時(shí)候，可以采用的一種方法

4. 線(xiàn)性規(guī)劃法：見(jiàn)詞條

5. 簡(jiǎn)并法：把一個(gè)問(wèn)題通過(guò)邏輯或數(shù)學(xué)推理，簡(jiǎn)化成與之等價(jià)或者近似的、相對(duì)簡(jiǎn)單的模型，進(jìn)而求解的方法

排序算法

• 冒泡排序：它重復(fù)地走訪過(guò)要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說(shuō)該數(shù)列已經(jīng)排序完成。
  這個(gè)算法的名字由來(lái)是因?yàn)樵酱蟮脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端，故名。

• 選擇排序：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最?。ù螅┰兀缓蠓诺揭雅判蛐蛄械哪┪?。以此類(lèi)推，直到所有元素均排序完畢。

• 插入排序：通過(guò)構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。插入排序在實(shí)現(xiàn)上，通常采用in-place排序（即只需用到的額外空間的排序），因而在從后向前掃描過(guò)程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間。

• 基數(shù)排序：將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個(gè)位數(shù)分別比較。將所有待比較數(shù)值（正整數(shù)）統(tǒng)一為同樣的數(shù)位長(zhǎng)度，數(shù)位較短的數(shù)前面補(bǔ)零。然后，從最低位開(kāi)始，依次進(jìn)行一次排序。這樣從最低位排序一直到最高位排序完成以后，數(shù)列就變成一個(gè)有序序列。

• 快速排序：快速排序使用分治法（Divide and conquer）策略來(lái)把一個(gè)序列（list）分為兩個(gè)子序列（sub-lists）。
  步驟為：
  1. 從數(shù)列中挑出一個(gè)元素，稱(chēng)為"基準(zhǔn)"（pivot），
  2. 重新排序數(shù)列，所有比基準(zhǔn)值小的元素?cái)[放在基準(zhǔn)前面，所有比基準(zhǔn)值大的元素?cái)[在基準(zhǔn)后面（相同的數(shù)可以到任何一邊）。在這個(gè)分區(qū)結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱(chēng)為分區(qū)（partition）操作。
  3. 遞歸地（recursively）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。
     遞歸到最底部時(shí)，數(shù)列的大小是零或一，也就是已經(jīng)排序好了。這個(gè)算法一定會(huì)結(jié)束，因?yàn)樵诿看蔚牡╥teration）中，它至少會(huì)把一個(gè)元素?cái)[到它最后的位置去。