數(shù)據(jù)結(jié)構(gòu)與算法復習提綱

數(shù)據(jù)結(jié)構(gòu)與算法復習提綱（詳細版）一、 數(shù)學知識復習1、對數(shù)（重要公式:XA=B當且僅當A=logXB；關(guān)鍵思路：將對數(shù)轉(zhuǎn)化成為指數(shù)分析）2、級數(shù)（重要公式：>Ai和JiA；關(guān)鍵思路：同時乘上某個系數(shù)再相減）3、證明方法（數(shù)學歸納法和反證法：三個關(guān)鍵步驟（歸納基礎(chǔ)、歸納假設(shè)、歸納證明））二、 C++類1、構(gòu)造函數(shù)（使用默認參數(shù)的構(gòu)造函數(shù)；初始化列表）2、訪問函數(shù)和修改函數(shù)（關(guān)鍵字const）3、接口與實現(xiàn)的分離（聲明與實現(xiàn)必須精確匹配，兩個例外：默認參數(shù)和explicit）三、 C++細節(jié)1、參數(shù)傳遞（一般情形：單向傳遞/引用：雙向傳遞/常引用：避免大對象的拷貝）2、★三大函數(shù)（當數(shù)據(jù)成員含有指針類型，三大函數(shù)必須顯式給出；避免淺復制）（1）、析構(gòu)函數(shù)（形式：?類名（）/作用：釋放資源）（2）、復制構(gòu)造函數(shù)（形式：類名（const類名rhs）/作用：利用已有對象復制一個新對象）⑶、operator=（形式：const類名operator=（const類名rhs）/作用：賦值）四、 模板1、★函數(shù)模板定義（template<typename虛擬類型comparable>通用函數(shù)定義）2、★類模板⑴、定義（template<typename類型參數(shù)object>class類模板名） </typename></typename>（2）、調(diào)用（class類模板名〈實際參數(shù)〉 對象名（參數(shù)））</實際參數(shù)〉3、函數(shù)對象(定義一個包含零個數(shù)據(jù)成員和一個成員函數(shù)的類，然后傳遞該類的實例)五、矩陣1、基本思想(矩陣利用向量的向量來實現(xiàn)，艮Pvector<vectorobject>array)2、典型代碼分析(包括構(gòu)造函數(shù)和operator]]重載)</vector>第二章算法分析一、 數(shù)學基礎(chǔ)1、重要定義、f(N)=0(g(N))(若存在正常數(shù)C和n0,使得當NNn0時，有f(N)WCg(N))⑵、f(N)=Q(g(N))、f(N)=0(g(N))和f(N)=o(g(N)))2、★重要工具⑴、性質(zhì)：logkN=O(N)⑵)、洛比塔法則：判斷兩個函數(shù)的相對增長率二、 最大子列和問題1、算法I(1)、算法思想(i表示序列起點，j表示序列終點，k從i掃描到j(luò))⑵)、★時間復雜度分析(注意分析方法：J(i：0?N-1)J(j：i~N-1)J(k：i~j))⑶、★算法的缺陷(重復計算)2、算法II算法思想(i表示序列起點，j表示序列終點(省略輔助變量k))3、算法III(1)、★分治策略(遞歸程序：傳遞數(shù)組和左右邊界，后者界定了數(shù)組要被處理的范圍/單行驅(qū)動程序：傳遞數(shù)組和0,N-1而啟動遞歸程序)⑵)、算法思想(遞歸出口分析；最大子序列和的三種可能情況)⑶)、★時間復雜度分析(重要公式：T(N)=2T(N/2)+N)4、算法IV(任何負的子序列不可能是最優(yōu)子序列的前綴)三、 折半搜索1、概念：折半查找(在已排好序的隊列中查找數(shù)X)2、算法思想(關(guān)鍵是分析low、high和mid)第二章表、棧和隊列一、 STL中的向量和表（STL,StandardTemplateLibrary，標準模板庫）1、STL定義了vector（向量）和list（雙向鏈表）兩個類模板2、★★迭代器（iterator）（1）、迭代器的作用（位置標記）⑵、迭代器的聲明（典例：vector<object>::iterator）（3） 、迭代器的重要方法（STL定義了一對方法：iteratorbegin（）、iteratorend（）（返回最后一項的后面位置）、*itr（返回itr所指位置的對象的引用））⑷、const_iterator（保證*itr返回常引用）二、 ★向量的實現(xiàn)1、 數(shù)據(jù)成員（theSize：元素個數(shù)/theCapacity：容量/objects：基本數(shù)組）2、 構(gòu)造函數(shù)和三大函數(shù)（重點分析operator二；復制構(gòu)造函數(shù)與operator=的區(qū)別與聯(lián)系）3、兩個基本操作（reserve（改變?nèi)萘浚┖蛂esize（改變大?。?、重要操作（push_back和pop_back）三、 表的實現(xiàn)1、 Node類（數(shù)據(jù)成員：data、prev和next/重點：構(gòu)造函數(shù)）2、 const_iterator類（數(shù)據(jù)成員：current/運算符重載：operator*,前后置++,二二和!二）3、iterator類（const_iterator的子類；注意兩者唯一的區(qū)別）4、list類⑴、數(shù)據(jù)成員（theSize，頭結(jié)點和尾結(jié)點（注意指向的位置））⑵）、構(gòu)造函數(shù)和三大函數(shù)（關(guān)鍵：利用init例程，創(chuàng)建空雙向鏈表）（3）、基本操作（insert和erase操作）（4） 、重要操作（push_front、push_back、pop_front和pop_back）四、 棧ADT1、棧的順序?qū)崿F(xiàn)（1）、★重要概念：base和top（base:始終指向棧底位置/top：指向棧頂元素的下一個位置）⑵、★重要條件（?？諚l件:top=base；棧滿條件：top-base=stackSize）2、棧的應(yīng)用（分析算法思想：首先創(chuàng)建一個空棧并順序讀入符號）⑴、平衡符號（關(guān)鍵：三種出錯情況）（2） 、后綴表達式（遇見數(shù)則壓棧；遇見操作符則連續(xù)兩次彈棧，計算后再壓棧）（3） 、中綴到后綴的轉(zhuǎn)換（遇見數(shù)輸出/遇見操作符，級別高則入棧，否則一直彈棧直到遇見級別更低的操作符/遇見（，入棧，直到遇見），則將（）之間的所有操作符彈棧）五、隊列ADT（循環(huán)隊列）1、★重要概念：頭指針和尾指針（front：指向?qū)︻^元素；rear：指向隊尾元素下一個位置）2、★重要操作：入隊和出隊（入隊rear++；出隊front++）3、★重要條件（隊空條件：front=rear；隊滿條件：front=（rear+1）%maxSize第四章樹一、 二叉查找樹1、二叉查找樹的概念（對于每個結(jié)點X，左子樹中的所有結(jié)點的值<x，右子樹〉 X）2、二叉查找樹結(jié)點類BinaryNode（elementsleft和right）3>★二叉查找樹的類模板⑴、數(shù)據(jù)成員（根結(jié)點root）</x，右子樹〉（2）、析構(gòu)函數(shù)和operator=（分別采用makeEmpty和clone例程）（3）、基本操作（contains、findMIn和findMax操作）（分別利用遞歸和非遞歸方式實現(xiàn)）⑷、重要操作（insert和remove操作）二、 AVL樹（平衡二叉樹）1、★AVL樹的概念和性質(zhì)（空樹的高度為-1）⑴、概念：AVL樹（雙重條件：二叉查找樹，且每個結(jié)點的左右子樹高度差至多為1）⑵、性質(zhì)（高度h的AVL樹，最少結(jié)點數(shù)s（h）=s（h-1）+s（h-2）+1））2、★★AVL樹的四種基本旋轉(zhuǎn)（關(guān)鍵：作圖分析）⑴、理論分析：（當插入一個新結(jié)點時，通過旋轉(zhuǎn)可以保持這棵樹仍然是AVL樹）⑵、實際分析：（一字形：使用單旋轉(zhuǎn)；Z字形：使用雙旋轉(zhuǎn)）⑶、典例分析：（P107：倒序插入10?16）3、★★AVL樹的插入算法⑴、AVL樹的結(jié)點類AvlNode（同標準BinaryNode相比，增加一個height字段）⑵、AVL樹的插入操作（利用height（）例程和四種基本旋轉(zhuǎn)）⑶、基本操作（右旋轉(zhuǎn)（rotateWithLeftChild）；左右旋轉(zhuǎn)（doubleWithLeftChild））三、 伸展樹1、 伸展樹的基本思想（當一個結(jié)點被訪問以后，它就要通過一系列旋轉(zhuǎn)被推至根）2、伸展樹的效率（平均攤還時間為O（logN））3、基本操作（一字形旋轉(zhuǎn)和Z字形旋轉(zhuǎn)）（通過P114典例分析）四、 樹的遍歷（使用遞歸實現(xiàn)）1、中序遍歷二叉查找樹2、 利用后序遍歷計算樹的高度五、 B樹（M叉查找樹的一種實現(xiàn)方式；磁盤的訪問代價太高）1、 重要概念：M階B樹（葉結(jié)點：數(shù)據(jù)；非葉結(jié)點：鍵/根、非根和葉結(jié)點的限制）2、基本操作（插入：分裂方式/刪除：領(lǐng)養(yǎng)和合并方式）六、 標準庫中的set和map（了解內(nèi)容）1、set（排序后的，沒有重復值的容器）2、map（排序后的，由鍵和值組成的項的集合） （典例：map<string，vector><string>::const_iteratoritr；）</string></string，vector>第五章散列一、★★鏈地址法1、基本思想（將hash值相同的所有記錄保存在同一個線性鏈表中）2、實現(xiàn)鏈地址法的HashTable類模板⑴、數(shù)據(jù)成員（thelists（鏈表數(shù)組）和currentsize（已存儲結(jié)點個數(shù)））⑵）、核心操作：myhash（）（散列到合適位置）⑶）、基本操作：makeEmpty（）和contains（）（關(guān)鍵：利用find例程）⑷、重要操作：insert（）和remove（）二、 ★★探測法1、基本思想（hi（x）=（hash（x）+f（i））modTableSize；其中f為沖突解決函數(shù)）2、線性探測法和平方探測法（f（i）=i；f（i）=i2）3、實現(xiàn)探測法的HashTable類模板⑴、數(shù)據(jù)成員（HashEntry（通過HashType）定義；數(shù)組array和currentsize）⑵、核心操作：findPos（）（若x存在，返回位置；否則返回待插入位置）⑶、基本操作：makeEmpty（）（關(guān)鍵:打上EMPTY標記）⑷、重要操作：insert（）和remove（）三、 ★再散列（3個基本步驟：備份；增容并初始化；拷貝）1、鏈地址法的再散列2、探測法的再散列數(shù)據(jù)結(jié)構(gòu)與算法復習提綱（詳細版）.doc將本文的Word文檔下載到電腦，方便復制、編輯、收藏和打印支付<i>7</i>元已有<iid="dl">10</i>人下載本文鏈接：（轉(zhuǎn)載請注明文章優(yōu)先隊列（堆）一、 ★★二叉堆1、基本概念：二叉堆（雙重條件：完全二叉樹；且堆序（任意結(jié)點小于它的所有后裔））2、二叉堆的類模板（BinaryHeap）⑴、數(shù)據(jù)成員（數(shù)組array；currentSize（當前堆的大?。?、基本操作：（插入和刪除操作必須考慮特殊情況）I、insert操作（關(guān)鍵：上濾）II、deleteMin操作（兩種格式）（關(guān)鍵：下濾；調(diào)用percolateDown例程）⑶、重要操作：buildHeap操作（從而得出構(gòu)造函數(shù)）3、重要定理:高為h的滿二叉樹的結(jié)點的高度和為2h+1-1-（h+1）（分析證明）4、基本概念：d堆（二叉堆的簡單推廣）二、 ★★左式堆I、 ★★基本概念和性質(zhì)（1）、概念：零路徑長npl（nullpathlength,theshortestpathfromxtoanodewithnullpoint）I、重要性質(zhì)：結(jié)點X的npl=min（左右孩子的npl）+1II、 初值分析：npl（null）=0；npl（葉結(jié)點；度為1的結(jié)點）=1⑵、重要概念：左式堆（雙重條件：堆序；且npl（左孩子）二npl（右孩子））（3）、定理：在右路徑上有r個結(jié)點的左式堆至少有2r-1個結(jié)點（左側(cè)全部鋪滿）2、★★左式堆的類模板（LeftistHeap）⑴、數(shù)據(jù)成員（LeftistNode*root；左式堆結(jié)點LeftistNode增加一個npl字段）⑵）、關(guān)鍵操作：merge操作（驅(qū)動程序加兩個merge完成；思想：大的合并到小的右子樹）⑶、重要操作：insert操作和deleteMin操作3、斜堆（斜堆與左式堆的關(guān)系，類似伸展樹與AVL樹的關(guān)系）⑴、概念：斜堆（具有堆序性質(zhì)的二叉樹）（即左式堆去掉npl限制）⑵）、基本操作：merge（除右路徑上最后一個結(jié)點，每次合并都必須交換）三、★★二項隊列1、基本概念和性質(zhì)（1）、概念：二項樹（雙重條件：堆序；Bk的遞歸定義）⑵）、重要概念：二項隊列（由若干棵二項樹構(gòu)成）⑶）、重要性質(zhì)（二項隊列的兩個性質(zhì)：每個高度上至多有一棵二項樹；可以用二項樹的集合唯一表示任意大小的優(yōu)先隊列）2、★★二項隊列的類模板（BinomialQueue）⑴、結(jié)點類BinomialNode（孩子兄弟表示法：leftchild指向結(jié)點最多的子樹；rightsibling）⑵、數(shù)據(jù)成員（指針數(shù)組theTrees；currentSize（按遞減方式存放））（3）、核心操作：combineTrees（同等高度的合并；保持堆序性質(zhì)）⑷、基本操作：merge（三個步驟：resize、carry和whichcase、清空（currentSize的作用））⑸、重要操作：findMinIndex（尋找最小項）和deleteMin（H2：deletedTree和deletedQueue）第七章排序一、★插入排序1、算法思想（插入到前面有序序列）2、 插入算法（關(guān)鍵：分析清楚邊界情況（i控制插入趟數(shù)，j控制每趟中的插入位置））二、 一些簡單排序算法的下界1、逆序的概念、性質(zhì)（一次相鄰結(jié)點的交換，逆序改變1；逆序數(shù)二插入算法比較次數(shù)））2、定理：N個互異元素的數(shù)組，其平均逆序數(shù)為N（N-1）/43、 定理:通過交換相鄰元素進行排序的任何算法平均需要Q（N2）時間三、 希爾排序（ShellSort，縮減增量排序）1、 算法思想（由若干趟Hk排序構(gòu)成；每趟Hk排序使用插入算法）2、 使用希爾增量的希爾排序（關(guān)鍵：三重循環(huán)（gap表Shell增量，i和j作用同插入排序）3、定理：使用希爾增量的希爾排序的最壞運行時間為Q（N2）（注意構(gòu)造和嚴格證明）四、 ★堆排序（heapSort）1、 算法思想（兩個步驟：創(chuàng)建大堆；首尾交換并下濾）2、 堆排序算法（關(guān)鍵:基于二叉堆的buildHeap和percolateDown（修改為大堆））五、 ★★歸并排序（mergeSort）1、 算法思想（分治算法；合并兩個已排序的表）2、 歸并算法（由驅(qū)動程序、mergeSort和merge構(gòu)成；關(guān)鍵：tempArray臨時數(shù)組；而merge包含三個while和一個拷貝）3、 ★算法分析（關(guān)鍵公式：T（N）=2T（N/2）+N，疊縮求和法）六、 ★★快速排序（quickSort）1、算法思想（分治算法：選取樞紐元素pivot；將S分割S1和S2；對S1和S2遞歸調(diào)用）2、快速算法（median3（關(guān)鍵：3元素中值法選取樞紐元素）；quickSort（關(guān)鍵：i向右搜索第一個Npivot的結(jié)點，j相反操作（注意i和j起始位置）；還原pivot并從i處分割）3、★★算法分析（關(guān)鍵公式：T（N）=T（i）+T（N-i-1）+CN）（i為S1中元素個數(shù)）七、其它1、 間接排序（解決comparable對象復制代價太高的問題）2、 定理：只使用元素間比較的任何排序算法需要Q（NlogN）次比較3、桶排序（前提條件（正整數(shù)）和算法思想）4、外部排序（1）、外部排序的概念（大文件的排序，排序過程中需要進行多次的內(nèi)、外存之間的交換）⑵、基本思想（歸并算法）第八章不相交集一、 基本操作1、 find（x）操作（查找操作：返回x所屬的集合）2、 unionSets（S1，S2）操作（求并操作：求集合S1和S2的并）二、 DisjSets類（不相交集類）1、基本思想（利用樹表示每個集合，根表示這個集合的名稱；整個集合表示為一顆森林）2、基本數(shù)據(jù)結(jié)構(gòu)（關(guān)鍵：雙親表示法）⑴、數(shù)據(jù)成員（數(shù)組S：（S[i]為i的雙親，其中-1表示根））⑵、構(gòu)造函數(shù)（數(shù)組S全部初始化為-1）（3）、基本操作：find（）操作和unionSets（）操作3、算法分析（unionSets操作為O（1），find操作的最壞情形為O（1））三、 靈巧求并算法第八章不相交集類一、 基本概念1、 關(guān)系R：ARelationRisdefinedonasetSisforeverypaiKa，b），a，bES，eitherTrueorFalse.2、 等價關(guān)系：滿足自反、對稱和傳遞等三條性質(zhì)的關(guān)系3、等價類（更準確的名稱為：集合S上的R關(guān)系等價類）等價類的作用：形成對集合S的一個劃分（即：根據(jù)關(guān)系R將集合S劃分為S1，S2，S3??等等）二、 基本操作1、find（x）操作：Returnthenameofsetcontainingagivenelement.2>unionSets（S1,S2）操作：（求并操作）UniontwodisjointsetsS1,S2（對兩個不相交的非空集合S1和S2求并）三、 不相交集類的基本數(shù)據(jù)結(jié)構(gòu)1、數(shù)據(jù)結(jié)構(gòu)的表示⑴、Useatreetorepresenteachset，therootcanbeusedtonametheset.（利用樹來表示每一個集合，而且利用該樹的根結(jié)點來表示這個集合的名稱）⑵、這樣，整個集合S可表示為一顆森林2、數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)采用雙親表示法實現(xiàn)（注意：雙親表示法是利用數(shù)組來存貯一棵樹）其中：⑴、S[i]表示元素i的雙親結(jié)點⑵、若i是根結(jié)點，則S[i]=—13、★★不相交集類的算法實現(xiàn)（包括類的定義、構(gòu)造函數(shù)的實現(xiàn)以及兩個基本操作 find和unionSets的實現(xiàn)）4、★算法分析⑴、unionSets操作的時間復雜度為O（1）⑵）、find操作的最壞時間復雜度為O（N）I、unionSets操作和find操作在算法效率上是一對矛盾的操作II、 連續(xù)的求并操作，在最壞情況下會建立起一棵深度為N-1的樹III、 一般情況下，運行時間使針對連續(xù)混和使用M個指令來計算的在這種情況下，M次連續(xù)操作在最壞情形下可能花費O（MN）時間四、 算法的改進1、unionSets操作的改進（1）、按大小求并（與按高度求并非常類似）⑵）、按高度求并（保證將比較淺的子樹并入比較深的子樹）思路1：可利用每個根的數(shù)據(jù)元素來存貯整顆子樹高度的負值思路2：為了同原算法類定義和構(gòu)造函數(shù)實現(xiàn)的兼容，我們假定只有一個根結(jié)點的樹的高度為一1，依此類推（3）、★算法分析兩種算法都將find操作的時間復雜度改進為O（logN）（給出詳細的證明）（另外的一個結(jié)論是：對于連續(xù)M個指令，平均需要O（M）時間，但最壞情形還是O（MlogN））2、find操作的改進一路徑壓縮（Pathcompression）⑴、路徑壓縮的概念：Everynodeonthepathfromxtotheroothasitsparentchangedtotheroot.（從x到根的路徑上每一個結(jié)點都使它的父結(jié)點變成根）⑵、★路徑壓縮的算法實現(xiàn)（3）、結(jié)論：路徑壓縮與按大小求并完全兼容，與按高度求并部分兼容五、 按秩求并和路徑壓縮的最壞情形1、秩（rank）的概念：一個結(jié)點的秩，是指以該結(jié)點為根結(jié)點的子樹的高度2、幾個重要引理⑴、引理1：當執(zhí)行一系列union指令以后，一個秩為r的結(jié)點必然至少有2r個后裔結(jié)點（包括它自己）⑵）、引理2：秩為r的結(jié)點至多有N/2r個（3）、引理3：在求并查找算法的任意時刻，從樹葉到根結(jié)點路徑上的結(jié)點的秩單調(diào)增加3、★重要定理：當使用求并探測法和路徑壓縮時，算法在最壞情況下需要的時間為O（a（M，N））其中，a（M，N）是Ackermann函數(shù)的逆（推論：任意次序的M=Q（N）次union/find操作花費的總運行時間為O（Mlog*N））六、 迷宮問題1、算法思想：對于隨機選中的一堵墻，使用union/find操作2、算法分析：時間復雜度為O（Nlog*N）圖論算法一、圖的表示1、鄰接矩陣（adjacentmatrix）表示法（分析優(yōu)缺點）2、★鄰接表（adjacencylist）I、對每一個頂點，使用一個鏈表來存放與之鄰接的所有頂點II、圖的鄰接表的一種簡單的表示方式：Vector<vertex>array（使用一個數(shù)組來存放所有的頂點）</vertex>二、 拓撲排序1、 概念：拓撲排序是對有向無環(huán)圖的頂點的一種排序2、 ★★拓撲排序的算法思想（可以使用Stack或者Queue來實現(xiàn)）（1）、計算每一個頂點的入度（2） 、將所有入度為0的頂點放入一個初始為空的隊列中（3） 、若隊列非空，則v出隊，且所有與v鄰接的頂點的入度減1（4）、若有頂點的入度降為0,則該頂點入隊3、★拓撲排序的算法（使用偽碼描述）（注意：利用一個輔助變量來判斷是否出現(xiàn)回路）4、★算法分析：時間復雜度為O（|E|+|V|）三、 最短路徑1、 無權(quán)最短路徑（加權(quán)最短路徑的特殊情形）⑴、采用廣度優(yōu)先搜索（BreadthCFirstSearch）的策略（層次遍歷的推廣）（2）、★Vertex的數(shù)據(jù)結(jié)構(gòu)I、known:當一個頂點被訪問以后，其known置為trueII、dist:從s到該頂點的距離III、path:引起dist變化的最后頂點（通過追溯path，可以得到s到該頂點的完整最短路徑）⑶、★無權(quán)最短路徑的算法思想和算法（關(guān)鍵：使用一個隊列來實現(xiàn)）4）、算法分析：時間復雜度為O（|E|+|V|）2、 加權(quán)最短路徑（1）、貪心算法（greedalgorithm）I、 Solvetheprobleminstages（分階段進行）II、每個階段都把出現(xiàn)的方案當成最優(yōu)的解決方案（2）、、★★Dijkstra算法思想和算法I、對所有結(jié)點初始化II、 在所有known標記為false的結(jié)點中，尋找一個其dist值最小的結(jié)點III、掃描與v鄰接的所有known標記為false的結(jié)點w,分析是否有必要update其dist值IV、更新w的path⑶、★★Dijkstra的算法分析I、 常規(guī)方法：通過掃描存放頂點的數(shù)組來尋找最小值，時間是O（|E|+|V|2）II、使用優(yōu)先隊列的deleteMin方法尋找最小值：，其時間是O（|E|log|V|+|V|log|V|）3、 具有負邊值的圖（1）、★算法思想和算法：綜合了無權(quán)最短路徑（采用隊列）和Dijkstra算法（需要update）的思想I、不需要再設(shè)置known來判斷結(jié)點是否已經(jīng)被訪問過II、 掃描與v鄰接的所有結(jié)點w,分析是否有必要update其dist值，再分析w是否入隊⑵、★算法分析：時間是O（|E|x|V|）（給出詳細證明）4、 無環(huán)圖（1）、★算法思想以Dijkstra算法作為基礎(chǔ)，但是頂點的選取采用拓撲原則（而不是尋找dist值最小的頂點）⑵、基本概念：動作結(jié)點圖和事件結(jié)點圖（注意：兩者的轉(zhuǎn)換方法）⑶）、基本概念：最早完成時間，最晚完成時間，松弛時間（分析其計算公式）⑷、基本概念：關(guān)鍵路徑一由零松弛邊組成的路徑四、 網(wǎng)絡(luò)流問題1、概念：最大流問題設(shè)有向圖G=（V，E）的每條邊表示邊容量，求從給定的源點s到匯點t可通過的最大流量2、算法思想（1）、輔助工具：流圖（初始：每條邊均為0）和殘余圖（初始：等于原圖）⑵、從殘余圖中選擇一條增長路徑（關(guān)鍵：對流圖和殘余圖進行調(diào)整）⑶、算法一直運行到?jīng)]有增長路徑為止五、 最小生成樹1、基本概念和性質(zhì)(1)、生成樹的概念和性質(zhì)概念：SpanningtreeisatreeformedfromgraphedgesthatconnectsallverticesofG.性質(zhì)：生成樹的邊數(shù)為N—1⑵、最小生成樹的概念和性質(zhì)MST性質(zhì)：若（u,v）是一條具有最小權(quán)值的邊，其中uEU,vEV—U,則必存在一棵包含邊（u,v）的最小生成樹2、 Prim算法⑴、*Prim算法的基本思想：設(shè)G=（V,E）,TE是G上最小生成樹的邊的集合I、初始：U={u0},TE={）II、從所有的（u,v）中尋找一條代價最小的邊（u0,v0）,其中u0EU,v0EV—UIII、U=UU{u0},TE=TEU（u0,v0）IV、上述操作一直做到U=V為止⑵、★★Prim算法I、 同Dijkstra算法非常類似，唯一區(qū)別在于dv的含義和更新方法不同（這里dv是指從v到所有known頂點的最短邊）II、 注意：如何獲取最后的最小生成樹和計算出其代價3、 Kruskal算法（1）、★★Kruskal算法的基本思想和算法I、使用優(yōu)先隊列來存放所有的邊II、利用等價類的思想來決定（u,v）邊是應(yīng)該添加還是舍棄⑵）、Kruskal的算法分析：同Prim算法一樣，其時間復雜度為（|E|log|V|）六、深度優(yōu)先搜索的應(yīng)用1、深度優(yōu)先搜索（DFS,Depth-firstsearch）（DFS是對前序遍歷的推廣）⑴、★DFS算法思想和算法通常情況下，DFS算法均由兩個模板構(gòu)成I、外圍模板：針對整個圖G進行（初始化，再掃描結(jié)點，若unvisited則調(diào)用核心模板）II、核心模板：是一個從指定頂點開始的，非常簡練的DFS遞歸程序⑵、DFS算法分析：時間復雜度為O（|E|+|V|）2、 無向圖（1）、★概念：前序編號（對圖G進行DFS，圖中的各個頂點被依次訪問的順序編號）⑵、★概念：DFS樹（深度優(yōu)先生成樹）對圖G進行DFS以后，圖中的所有邊被分成兩大類：前向邊和后向邊其中所有的前向邊構(gòu)成了DFS樹（3） 、算法思想和算法（分析以上概念的算法實現(xiàn)）3、 無向圖的雙連通性⑴、概念：雙連通性和割點⑵）、★low（V）的概念和計算方法Low（V）是頂點v可到達的最低頂點編號（關(guān)鍵：計算low的三條法則）⑶、割點的判斷條件若頂點v存在一個孩子結(jié)點w，有l(wèi)ow（w）=num（V），則v必然是一個割點⑷、★算法：尋找連通圖中的所有割點該算法通過對圖的兩次遍歷而實現(xiàn)（一次前序遍歷和一次后序遍歷）I、結(jié)點Vertex包含以下域：visited，num，low，parentII、首先計算圖G的每個頂點的前序編號（計算出num和parent）III、利用一趟后序遍歷對各個頂點計算low，并判斷是否割點4、 歐拉回路（1）、概念：歐拉環(huán)游和歐拉回路⑵）、歐拉定理：任何一個連通圖存在歐拉回路的充分必要條件是圖中所有頂點的度為偶數(shù)⑶、★歐拉回路的算法思想I、 數(shù)據(jù)結(jié)構(gòu)的設(shè)計：遍歷的路徑采用鏈表保存；為避免重復掃描鄰接表，對每一個鄰接表必須保留最后掃描到的邊II、 對給定的頂點進行一次DFSIII、 選定一個拼接點，從該頂點開始進行DFSIV、上述步驟重復進行，直到所有的邊都被遍歷（4） 、歐拉回路的算法和算法分析：時間復雜度為O（|E|+|V|）5、 有向圖⑴、按照與無向圖相同的策略，對有向圖進行DFS(若圖G非強連通的，則產(chǎn)生DFS森林)、有向圖DFS的虛邊有三種類型(無向圖只有一種，即后向邊)后向邊、前向邊和交叉邊、對有向圖進行DFS的一個作用是：判斷該有向圖是否無環(huán)圖法則如下：一個有向圖是無環(huán)圖當且僅當它沒有后向邊6、查找強分支(1)、★查找強分支的算法思想：兩次DFSI、 首先對圖G進行第一次DFS，得到DFS森林(通過對DFS的后序遍歷得到每個頂點的后序編號；并且將G的所有邊反向得到GR)II、再對GR進行第二次DFS，總是在編號最高的頂點開始一次新的深度優(yōu)先搜索⑵、★定理：按照上述算法生成的DFS森林中的每棵樹都是一個強連通的分支(分析其證明)七、NP完全性介紹1、P問題指保證以多項式時間運行的算法2、不可判定問題(1)、可以證明：計算機不可能解決所有的問題，這些不可能解出的問題稱為不可判定問題⑵、著名的不可判定問題：停機問題I、什么是停機問題？II、 停機問題的實質(zhì)是：一個程序很難檢查它自己3、NP類(1)、NP類代表非確定型多項式時間這類問題在難度上稍遜于不可判定問題⑵、判斷一個問題是否NP問題的方法如果我們能在多項式時間內(nèi)證明一個問題的任意“是”的實例是正確的，那么這個問題就屬于NP類典例：哈密爾頓回路問題就是一個NP問題⑶、NP類同其它集合的關(guān)系I、性質(zhì)：NP類包括P類，即包括所有具有多項式時間解的問題II、性質(zhì)：不是所有的可判定問題都是NP問題(即NP問題并不是不可判定問題的補集）典例：無哈密爾頓回路問題顯然是一個可判定問題，但不是NP問題4、NP完全問題（1）、NP完全問題是NP問題的一個子集⑵、重要性質(zhì)：NP中的任何一個問題都可以多項式地歸約成NP完全問題⑶、證明一個問題是NP完全問題的方法I、首先證明該問題是NP問題II、然后將一個適當?shù)腘P問題變換到此問題典例：假設(shè)哈密爾頓回路問題是一個NP完全問題，證明旅行商問題也是一個NP完全問題第十章算法設(shè)計技巧一、貪心算法1、 ★貪心算法（greedalgorithm）⑴、Solvetheprobleminstages（分階段進行）⑵、每個階段都把出現(xiàn)的方案當成最優(yōu)的解決方案（當算法終止時，希望局部最優(yōu)成為全局最優(yōu)）2、 調(diào)度問題（1） 、★調(diào)度問題的概念：將作業(yè)平均完成的時間最小化（假設(shè)：非搶占調(diào)度，即一旦開始一個作業(yè)，就必須把該作業(yè)運行完）⑵、多處理器情形I、實現(xiàn)步驟：（首先排序，然后按順序開始作業(yè)，處理器之間輪流分配作業(yè)）II、證明：按照這種算法思想實現(xiàn)的，一定是最優(yōu)解⑶）、將最后完成時間最小化（這是一個NP完全問題）3、 赫夫曼（Huffman）編碼⑴、概念：滿樹和前綴碼（2） 、赫夫曼編碼的算法思想（頻率出現(xiàn)高的字符編碼要短）⑶、★赫夫曼編碼的算法和算法分析（采用優(yōu)先隊列時，運行時間為O（ClogC））4、 裝箱問題（1）、基本概念I(lǐng)、★概念：裝箱問題（將物品裝到最少數(shù)量的箱子中）II、 ★概念：聯(lián)機裝箱（每一件物品必須放入一個箱子之后才能處理下一個物品）⑵、聯(lián)機算法I、重要性質(zhì)：對于聯(lián)機裝箱問題不存在最優(yōu)算法（分析其證明）II、★定理一：任意聯(lián)機裝箱算法的下界為4M/3（分析其證明）⑶、下項適配I、下項適配的基本思想（能放入當前箱子則放，否則開辟一個新的箱子）II、★定理二：下項適配算法的上界為2M（分析其證明）⑷、首次適配I、首次適配的基本思想（掃描并尋找第一個能放入的箱子，否則開辟一個新箱子）II、定理三：首次適配算法的上界為17M/10⑸、最佳適配最佳適配的基本思想和上界分析（放入所有能夠容納它的最滿的箱子中）⑹、脫機裝箱I、★首次適配遞減的算法思想（首先排序，然后再使用首次適配算法）II、引理一：大小至多是1/3（分析其證明）III、 引理二、個數(shù)至多是M-1（放入其它箱子中的物品個數(shù)至多是M-1，分析其證明）IV、★定理四、首次適配遞減算法的上界是（4M+1）/3V、定理五、首次適配遞減算法的上界可以縮減為11M/9+4二、分治算法1、 分治算法（divideandconquer）（1）、★分治算法的基本思想：分治算法由兩個階段構(gòu)成I、分：遞歸解決較小的問題II、治：從子問題的解構(gòu)建原問題的解⑵）、分治算法的特性（至少含有兩個遞歸調(diào)用，且子問題是不相交的）2、 分治算法的運行時間K⑴、★定理六：方程T（N）=aT（N/b）+O（N）的解（分析其證明)KP⑵、定理七：方程T(N)=aT(N/b)+O(NlogN)的解(定理六的推廣)⑶、定理八：若Jail,T(N)=JT(aiN)+O(N)的解為T(N)=O(N)3、 最近點問題(1)、★概念：最近點問題(對于平面上的點列P，找出一對最近的點)⑵)、關(guān)鍵性質(zhì)：在26x26區(qū)域上，考察點必為常數(shù)情形⑶、最近點算法的基本思想4、 選擇問題⑴、★概念：選擇問題(從含有N個元素的集合S中尋找第K個最小的元素)⑵、概念：五分化中項的中項(分析其作用)⑶)、定理：使用“五分化中項的中項”的快速選擇算法的運行時間為O(N)5、 一些算術(shù)問題的理論改進⑴、整數(shù)相乘I、 概念：實現(xiàn)兩個N位數(shù)X和Y相乘II、 ★基本思想：分治算法(將X和Y拆分為兩半：將遞歸調(diào)用次數(shù)從4降為3)⑵)、矩陣相乘(同上分析)三、動態(tài)規(guī)劃1、 動態(tài)規(guī)劃的基礎(chǔ)知識(1)、★重要性質(zhì)：所有數(shù)學遞推公式都可以直接翻譯成遞歸算法(2)、★動態(tài)規(guī)劃的概念和作用I、概念：動態(tài)規(guī)劃是解遞歸的一種技術(shù)(關(guān)鍵：將中間的計算結(jié)果保存下來)II、作用：避免直接翻譯引起的低效(關(guān)鍵：存在著大量的冗余計算)⑶、典例分析：Fibonacci算法I、遞歸程序(分析運行時間，以及算法低效的原因)II、非遞歸程序(分析算法效率改進的原因)2、 矩陣乘法的順序安排(1)、基本知識：矩陣A(M1*M2)與矩陣B(M2*M3)相乘所需的乘法次數(shù)⑵、性質(zhì)一：T(N)的計算公式(表示順序的個數(shù))⑶、性質(zhì)二：M(Left，Right)的計算公式(M(Left，Right)為矩陣A(Left)A(Left-1)?A(Right-1)A(Right)的相乘次數(shù))⑷、★矩陣相乘的算法思想和算法3、 最優(yōu)二叉查找樹(1)、★最優(yōu)二叉查找樹的概念I(lǐng)、概念：給定一組單詞w1，w2，w3，?wn，以及它們出現(xiàn)的固定概率pl，p2,p3,?pn，如何在一棵二叉查找樹中安放這些單詞，使得總的期望訪問時間最小II、最優(yōu)二叉查找樹與Huffman樹的區(qū)別(數(shù)據(jù)不僅僅出現(xiàn)在葉結(jié)點上，而且必須滿足二叉查找樹的性質(zhì))⑵)、★重要公式：最優(yōu)二叉查找樹的開銷C(Left，Right)⑶、最優(yōu)二叉查找樹的算法思想(同矩陣相乘很類似)4、 所有點對最短路徑⑴、概念：D(k，i，j)(從頂點Vi到頂點Vj只使用Vl，V2,V3,?Vk作為中間頂點的最短路徑的權(quán))⑵)、★重要公式：D(k，i，j)的計算公式⑶、★所有點對最短路徑的基本思想和算法四、隨機化算法1、 ★隨機化算法的概念和性質(zhì)(1)、概念：隨機化算法(在算法期間，隨機數(shù)至少有一次用于決策)⑵)、性質(zhì)：特定的輸入不再重要，重要的是隨機數(shù)2、 隨機數(shù)生成器(1)、真正的隨機數(shù)和偽隨機數(shù)⑵)、★線性同余數(shù)生成器：X(i+1)=AX(i)modMI、概念：種子(為了開始這個序列，X0必須給定；根據(jù)種子來生成X1，X2,X3,?)II、概念：周期和全周期(若M為素數(shù)，存在一些對A的選擇，使得序列以某個周期循環(huán))⑶、★隨機數(shù)生成器的類模板(分析存在的問題及其改進)3、 跳躍表I（1）、概念：帶有到前面2個表元素的鏈的鏈表（這個概念較為復雜，最好通過一個典型的例子來掌握）⑵、跳躍表I、 概念：K階結(jié)點（帶有k個鏈的結(jié)點）II、 性質(zhì)：任意k階結(jié)點上的第i階鏈，鏈接到的下一個結(jié)點至少具有i階III、★概念：跳躍表（利用k階結(jié)點的條件取代前面苛刻的限制性條件）IV、★算法思想：跳躍表的查找操作和插入操作4、素性測試P-1（1）、★費馬定理：如果P是素數(shù)，且0II、關(guān)鍵思想：這個算法偶爾會出錯，但是可以讓出錯的幾率任意?、疲?、★定理：如果P是素數(shù)，且0<x></p，那么x*x三1（mod></x>五、回溯算法1、回溯算法（1）、★概念：回溯算法（相當于窮舉搜索的巧妙實現(xiàn)，但性能往往不太理想）⑵、★概念：裁剪（在一步內(nèi)刪除一大組可能性的做法）2、公路收費點重建問題（1）、概念：公路收費點重建問題（從距離重建一個點集）⑵）、★公路收費點重建問題算法：驅(qū)動例程（D是距離集，X是點集）I、選定X=0；X[N]=D.deleteMax（）//先把頭尾兩個頂點的位置確定下來II、不妨假定X[N-1]=D.deleteMax（）//確定第三個頂點III、判斷X[N]-X[N-1]ED（3）、★★公路收費點重建問題算法：回溯的步驟I、關(guān)鍵：分析[Left..Right]中的各個點的Place位置（即假設(shè)[1..Left-1]和[Left+1..Right]中各個點已放入正確位置）II、若D為空，則返回True；否則dmax=D.findMax（）〃取出D中目前的最大值III、判斷dmax的可能位置//或者在最右邊，或者在最左邊（即X[Right]=dmax，或X[Left]=X[N]-dmax）IV、以在最右邊（X[Right]=dmax）為例：A、修改X集合B、修改D集合C、遞歸調(diào)用PlaceD、若遞歸調(diào)用的返回值為false；則回溯（將剛才刪除的D集合中的邊添加回來）V、同樣分析最左邊情形3、博弈（1）、極小極大策略I、 使用一個求值函數(shù)來對一個位置的好壞進行量化（計算機追求極大化，而人追求極小化）II、 概念：終端位置（能夠根據(jù)盤面判斷勝負的位置）；位置P的后繼位置III、在復雜的情況下，我們到達遞歸的某個深度后只能停止搜索（這就是所謂，計算機能向前看的步數(shù)）⑵、*a-p裁剪的概念I(lǐng)、概念：a裁剪findCompMove將其嘗試性的極大值a傳遞給findHumanMove，若findHumanMove嘗試性極小值低于a，則findHumanMove立即返回（最好根據(jù)圖來理解此概念）II、概念：p裁剪第十一章攤還分析一、 攤還分析的基本概念1、★概念：攤還時間界（任意順序的M次操作的最壞情形時間界）2、性質(zhì)：攤還時間界比對應(yīng)的最壞情形時間界要弱（對任意單次操作提供不了保障）二、 二項隊列1、★★重要定理：N個元素的二項隊列可以通過N次相繼插入而以時間O（N）建成（分析證明）（1）、引理：花費C個時間單位的一次插入導致在森林中凈增加2-C棵樹（2）、假設(shè)：Ci表示第i次插入的代價，Ti表示第i次插入之后樹的棵數(shù)，分析其公式2、位勢的概念和如何選擇位勢（1）、★概念：位勢（位勢可以看成是一個儲蓄帳戶，如果一次操作的時間少于指定的時間