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

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

偽代碼

流程圖

算法

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

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

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

哈希（Hash）

鍵值對： { '鍵' : '值' } ==> Array / Object

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

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

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

隊列（queue）

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

棧（stack）

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

鏈表（Linked List）

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

• 數(shù)組無法直接刪除中間的一項驮捍，但是鏈表可以疟呐，鏈表是動態(tài)數(shù)組

• Hash 實現(xiàn)鏈表，head 表示第一個 Hash 东且，所有的 Hash 都是節(jié)點（node）

樹

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

• 特點：

  1. 每個節(jié)點有零個或多個子節(jié)點
  2. 沒有父節(jié)點的節(jié)點稱為根節(jié)點
  3. 每一個非根節(jié)點有且只有一個父節(jié)點
  4. 除了根節(jié)點外珊泳，每個子節(jié)點可以分為多個不相交的子樹

• 術(shù)語：

  1. 節(jié)點的層次：從根開始定義起鲁冯，根為第1層拷沸，根的子節(jié)點為第2層，以此類推薯演；
  2. 深度：對于任意節(jié)點n,n的深度為從根到n的唯一路徑長撞芍，根的深度為0；
  3. 節(jié)點的度：一個節(jié)點含有的子樹的個數(shù)稱為該節(jié)點的度跨扮；
  4. 樹的度：一棵樹中序无，最大的節(jié)點的度稱為樹的度；
  5. 葉節(jié)點或終端節(jié)點：度為零的節(jié)點衡创；

• 二叉樹（Binary tree）：每個節(jié)點最多含有兩個子樹的樹稱為二叉樹

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

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

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

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

• 滿二叉樹：所有葉節(jié)點都在最底層的完全二叉樹

  1. 一棵深度為k菱皆，且有2的( k+1 )次冪 - 1個節(jié)點的二叉樹须误，稱為滿二叉樹（Full Binary Tree）

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

說明：用數(shù)組存儲滿二叉樹和完全二叉樹，用Hash存儲其他的樹

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

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

分類：

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

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

3. 貪婪算法：常見的近似求解思路疲陕。當(dāng)問題的整體最優(yōu)解不是（或無法證明是）由局部最優(yōu)解組成方淤，且對解的最優(yōu)性沒有要求的時候，可以采用的一種方法

4. 線性規(guī)劃法：見詞條

5. 簡并法：把一個問題通過邏輯或數(shù)學(xué)推理蹄殃，簡化成與之等價或者近似的携茂、相對簡單的模型，進(jìn)而求解的方法

排序算法

• 冒泡排序：它重復(fù)地走訪過要排序的數(shù)列诅岩，一次比較兩個元素讳苦，如果他們的順序錯誤就把他們交換過來带膜。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說該數(shù)列已經(jīng)排序完成鸳谜。
  這個算法的名字由來是因為越大的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端膝藕，故名。

• 選擇排序：首先在未排序序列中找到最懈琅ぁ（大）元素芭挽，存放到排序序列的起始位置，然后草描，再從剩余未排序元素中繼續(xù)尋找最欣缆獭（大）元素，然后放到已排序序列的末尾穗慕。以此類推饿敲，直到所有元素均排序完畢。

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

• 基數(shù)排序：將整數(shù)按位數(shù)切割成不同的數(shù)字硕并，然后按每個位數(shù)分別比較法焰。將所有待比較數(shù)值（正整數(shù)）統(tǒng)一為同樣的數(shù)位長度，數(shù)位較短的數(shù)前面補(bǔ)零倔毙。然后埃仪，從最低位開始，依次進(jìn)行一次排序陕赃。這樣從最低位排序一直到最高位排序完成以后卵蛉，數(shù)列就變成一個有序序列。

• 快速排序：快速排序使用分治法（Divide and conquer）策略來把一個序列（list）分為兩個子序列（sub-lists）么库。
  步驟為：
  1. 從數(shù)列中挑出一個元素傻丝，稱為"基準(zhǔn)"（pivot），
  2. 重新排序數(shù)列诉儒，所有比基準(zhǔn)值小的元素擺放在基準(zhǔn)前面桑滩，所有比基準(zhǔn)值大的元素擺在基準(zhǔn)后面（相同的數(shù)可以到任何一邊）。在這個分區(qū)結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置运准。這個稱為分區(qū)（partition）操作幌氮。
  3. 遞歸地（recursively）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。
     遞歸到最底部時胁澳，數(shù)列的大小是零或一该互，也就是已經(jīng)排序好了。這個算法一定會結(jié)束韭畸，因為在每次的迭代（iteration）中宇智，它至少會把一個元素擺到它最后的位置去。