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

1、數(shù)據(jù)結(jié)構(gòu)筆記基礎(chǔ)：數(shù)據(jù)結(jié)構(gòu)與算法(一) 數(shù)據(jù)結(jié)構(gòu)基本概念數(shù)據(jù)( data )：是對客觀事物的符號表示， 在計算機(jī)科學(xué)中是指所有能輸入到計算機(jī)中并被 計算機(jī)程序處理的符號總稱 數(shù)據(jù)元素( data element )：是數(shù)據(jù)的基本單位，在計算機(jī)中通常被當(dāng)做一個整體進(jìn)行考慮 和處理 數(shù)據(jù)對象( data object )：性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集 數(shù)據(jù)結(jié)構(gòu)( data structure )：相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合 4 類基本結(jié)構(gòu)：集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖形(網(wǎng)狀)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的形式定義為數(shù)據(jù)結(jié)構(gòu)是一個二元組Data Structure =(D,S)，

2、其中D是數(shù)據(jù)元素的有限集，S是D上關(guān)系的有限集數(shù)據(jù)結(jié)構(gòu)定義中的 “關(guān)系” 描述的是數(shù)據(jù)元素之間的邏輯關(guān)系， 因此又稱為數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中的表示(映像)稱為物理結(jié)構(gòu)(存儲結(jié)構(gòu)) 計算機(jī)中表示信息的最小單位是二進(jìn)制中的一位， 叫做 位( bit )，一到若干位組成一個位 串表示一個數(shù)據(jù)元素，這個位串稱為元素或結(jié)點 數(shù)據(jù)結(jié)構(gòu)之間關(guān)系在計算機(jī)中的表示有兩種： 順序映像、 非順序映像， 并由此得到兩種存儲 結(jié)構(gòu)： 順序存儲、鏈?zhǔn)酱鎯?，前者運(yùn)用相對位置表示數(shù)據(jù)元素間的邏輯結(jié)構(gòu)，后者借助指針 任何一個算法的設(shè)計取決于數(shù)據(jù)(邏輯)結(jié)構(gòu)，而實現(xiàn)依賴于存儲結(jié)構(gòu) 數(shù)據(jù)類型是一個值的集合和定義在這個值

3、集上的一組操作的總稱 數(shù)據(jù)類型分兩種：原子類型、結(jié)構(gòu)類型，前者不可分解(例如 int 、char 、float 、void )， 后者結(jié)構(gòu)類型由若干成分按某種結(jié)構(gòu)組成， 可分解， 成分既可以是非結(jié)構(gòu)的也可以是結(jié)構(gòu)的(例：數(shù)組)抽象數(shù)據(jù)類型( Abstract Data Type )：是指一個數(shù)學(xué)模型及定義在該模型上的一組操作( P8)抽象數(shù)據(jù)類型格式如下：ADT抽象數(shù)據(jù)類型名數(shù)據(jù)對象： <數(shù)據(jù)對象的定義 > 數(shù)據(jù)關(guān)系： <數(shù)據(jù)關(guān)系的定義 > 數(shù)據(jù)操作： <數(shù)據(jù)操作的定義 > ADT抽象數(shù)據(jù)類型名基本操作格式如下：基本操作名(參數(shù)表)初始條件： <初始條

4、件描述 > 操作結(jié)果： <操作結(jié)果描述 >多形數(shù)據(jù)類型( polymorphic data type )：是指其值得成分不確定的數(shù)據(jù)類型(P9)抽象數(shù)據(jù)類型可由固有數(shù)據(jù)類型來表示和實現(xiàn)(二) 算法(概念)和算法分析(時、空性能)算法(algorithm ):對特定問題求解步驟的一種描述算法5特性：有窮、確定、可行、輸入、輸出1有窮性：算法必須在可接受的時間內(nèi)執(zhí)行有窮步后結(jié)束2、確定性：每條指令必須要有確切含義，無二義性，并且只有唯一執(zhí)行路徑，即對相同的 輸入只能得相同輸出3、可行性：算法中的操作都可通過已實現(xiàn)的基本運(yùn)算執(zhí)行有限次來完成4、輸入：一個算法有一到多個輸入，并取自某

5、個特定對象合集5、輸出：一個算法有一到多個輸出，這些輸出與輸入有著某些特定關(guān)系的量 算法設(shè)計要求(好算法)：正確性、可讀性、健壯性、效率與低存儲需求健壯性是指對于規(guī)范要求以外的輸入能夠判斷出這個輸入不符合規(guī)范要求，并能有合理的處理方式。算法效率的度量：(1)事后統(tǒng)計：程序運(yùn)行結(jié)束后借助計算機(jī)內(nèi)部計時功能，缺點一是必須先運(yùn)行依據(jù)算法編制的程序，二是受限于計算機(jī)軟硬件，導(dǎo)致掩蓋了算法本身的優(yōu)劣(2 )事前分析估計：消耗時間影響因素：算法策略、問題規(guī)模、編程語言、編譯程序產(chǎn)生的機(jī)器碼質(zhì)量、機(jī)器執(zhí)行指令的速度撇開各種影響因素只考慮問題的規(guī)模(通常用整數(shù)量n表示)，記為問題規(guī)模的函數(shù)算法時間取決于控制結(jié)

6、構(gòu)(順序，分支，循環(huán))和固有數(shù)據(jù)類型操作的綜合效果書寫格式：T (n) = O( f (n) f(n)為n的某個函數(shù)時間復(fù)雜度：算法的漸近時間復(fù)雜度(asymptotic timecomplexity )，它表示隨冋題規(guī)模的增大，算法執(zhí)行時間的增長率和f (n)的增長率相冋以循環(huán)最深層原操作為度量基準(zhǔn)頻度：該語句重復(fù)執(zhí)行的次數(shù)算法的存儲空間需求：空間復(fù)雜度(space complexity ):算法所需存儲空間度量，記作S (n) = 0(f (n),其中n為問題規(guī)模的大小排序?qū)７〞r間復(fù)親度空冏復(fù)聽 度復(fù)雜性平均汁況R*.壞襯-；比貞按捕入搏 序o(n2>o（ir）0(100(1)帝爾誹

7、序0(1)較？.雜O(n">0(11*)0(100(1)O(u5< ?(EtfOg2U)不雄宅較覽雜0(1內(nèi)0(1)簡單堆排序0( ill ogn)O(hl0$2ll)0(1)不穂支較更雜歸扌非序Oflllo £211)0(1110 C211)O(n)雖就44序卄卄)b勺口 csc：ri.co較更雜rn/wh usl9i-、線性表（一）線性表基本概念線性表（linear list） : n個數(shù)據(jù)兀素的有限序列結(jié)構(gòu)特點：存在唯一的被稱作“第一個”、“最后個”的數(shù)據(jù)兀素，且除了第一個以外每個兀素都有唯一前驅(qū)，除最后一個以外都有唯一后繼在復(fù)雜線性表中存在：數(shù)據(jù)項 -&

8、gt; 記錄-> 文件，例如每個學(xué)生情況為一個記錄，它由學(xué)號、性別. 數(shù)據(jù)項組成，多個學(xué)生記錄組成一個文件在形如（al, . , ai-1 , ai , ai+1 , . , an）中，ai-1 領(lǐng)先于 ai , ai 領(lǐng)先于 ai+1，且形 成直接前驅(qū)元素，直接后繼元素關(guān)系元素個數(shù)n定義為線性表長度，n=0為空表相關(guān)操作算法見書（P20）（二）線性表順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)（1 ）線性表順序表示和實現(xiàn)線性表順序存儲在一組連續(xù)的存儲單元中，鏈?zhǔn)酱鎯t不要求；順序結(jié)構(gòu)可以隨機(jī)訪問，鏈?zhǔn)浇Y(jié)構(gòu)可以無限擴(kuò)容確定存儲位置（計算公式）：第i個元素：LOC（ai）= LOC（a1）+（i-1）*L

9、L 是偏移量，即每個元素占用存儲單元第ai+1個元素：LOC（ai+1）= LOC（ai） +L al（起始地址或基地址）C語言下標(biāo)從"0”開始，則表中第i個元素是L.elem i-1當(dāng)對線性表進(jìn)行操作時，被操作元素后面的元素角標(biāo)會相應(yīng)變化（前移、后移），算法（P24）（2 ）線性表鏈?zhǔn)奖硎竞蛯崿F(xiàn)特點：用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素（存儲單元不一定連續(xù)）結(jié)點存儲數(shù)據(jù)元素及直接后繼的存儲位置信息，兩個域：數(shù)據(jù)域和指針域，指針域中存儲的信息稱為指針或鏈，僅含有一個指針域故又稱線性鏈表或單鏈表鏈表的插入：先增加一條指針再修改原指針頭指針指向第一個數(shù)據(jù)兀素的存儲位置，最后一個結(jié)點的

10、指針為空（NULL鏈表表示方法及算法（P28）單鏈表第一個結(jié)點前加一個頭結(jié)點Head,其數(shù)據(jù)域可為空也可存儲一些附加信息（鏈長等）假設(shè)p是指向線性表中i個元素（ai ）的指針，則p->next是指向i+1個數(shù)據(jù)元素 在單鏈表中，取得第i個元素必須從頭指針開始尋找，因此單鏈表是非隨機(jī)的存儲結(jié)構(gòu) 線性表指邏輯結(jié)構(gòu)，從抽象數(shù)據(jù)層面來說順序表和鏈表指物理存儲結(jié)構(gòu)邏輯結(jié)構(gòu)：離散、線性、層次、網(wǎng)狀應(yīng)用見書算法二、棧和隊列（一）棧的基本概念棧（stack ）是限定僅在表尾進(jìn)行插入或刪除操作的線性表表尾為棧頂，表頭為棧底，遵循后進(jìn)先出原理（last in first on, LIFO），不含元素則為空棧

11、操作：在棧頂插入（入棧）和刪除（出棧），棧初始化、判空、取棧頂元素（算法P45）（二）棧的順序存儲和鏈?zhǔn)酱鎯樞驐?，即棧的順序存儲結(jié)構(gòu)是利用一組連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元 素，同時附設(shè)指針top指示棧頂元素在順序棧中的位置初始棧時不應(yīng)限定棧的最大容量，基本做法是先為棧分配一個基本容量，然后在應(yīng)用過程中，不夠用再逐段擴(kuò)大（算法P46）（三）遞歸棧與遞歸的實現(xiàn)：一個直接調(diào)用自己或通過一系列的調(diào)用語句間接地調(diào)用自己的函數(shù)，稱為遞歸函數(shù)階乘函數(shù)、2階Fibonacci數(shù)列、Ackerman函數(shù)、3階Hanoi問題（多階呢？）（ P54）函數(shù)調(diào)用函數(shù)執(zhí)行過程筆記（P56）（四）隊列隊列先

12、進(jìn)先出（first in first out，F(xiàn)IFO），隊尾一端插入，隊首一端刪除元素（日常 排隊）隊列與棧均有八種基本操作（P59）,隊列一般用鏈表實現(xiàn)，棧用順序表實現(xiàn)雙端隊列（限定操作的隊列）（P60)（五）棧和隊列的應(yīng)用鏈隊列、循環(huán)隊列（P60）,離散事件模擬（銀行接待工作（P65）（六）特殊矩陣的壓縮存儲如何存儲矩陣的元，使矩陣的運(yùn)算有效進(jìn)行。高級語言常用二維數(shù)組存儲陣元 面對如高階矩陣，多值相同矩陣和多零元素矩陣進(jìn)行壓縮存儲節(jié)省空間 壓縮存儲：為多個值相同的元只分配一個空間，對零元不分配值相同元素或零元素具有分布規(guī)律則稱為特殊矩陣，反之為稀疏矩陣具體應(yīng)用與算法（P95）三、樹與二叉

13、樹（一）樹的基本概念樹是非線性數(shù)據(jù)結(jié)構(gòu)，以分支關(guān)系定義的層次結(jié)構(gòu)樹是n （ n>=0）個結(jié)點的有限集詳見（P118）,基本術(shù)語（P120）（二）二叉樹1. 二叉樹的定義及其主要特征：二叉樹是每個結(jié)點最多有兩個子樹的樹結(jié)構(gòu)。通常子樹被稱作“左子樹” （left subtree ）和“右子樹”（(right subtree )。性質(zhì)：1.2.3. J滿二叉樹：完全二叉樹:4.5.2.二叉樹的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)順序存儲，用一組地址連續(xù)的存儲單兀依次自上而下、自左至右存儲完全二叉樹上的結(jié)點兀素，即將完全二叉樹上編號為i的結(jié)點依次存儲在如上定義的一位數(shù)組下標(biāo)為i-1的分量中。1 23456

14、789鏈?zhǔn)酱鎯?，每個結(jié)點中至少包含三個域,左指針，數(shù)據(jù)，右指針，稱作“二叉鏈表”增加一個雙親指針域，則稱作“三叉鏈表”詳見P126-1273.二叉樹的遍歷遍歷二叉樹，每個結(jié)點均被訪問一次，且僅有一次。在限定先左后右的訪問序列后，有三種遍歷方式：先序（DLR，中序（LDR ,后續(xù)（LRD）P129算法6.1 （波蘭式層次遍歷，無論那種遍歷方式，對含n個結(jié)點的二叉樹，時間復(fù)雜度都為0（n ）,空間摘要：對于n個結(jié)點的二叉樹，在二叉鏈存儲結(jié)構(gòu)中有n+1 (2n- (n-1 )個空鏈域，利用這些空鏈域存放在某種遍歷次序下該結(jié)點的前驅(qū)結(jié)點和后繼結(jié)點的指針，這些指針稱為線索概念：加上了線索的二叉鏈表稱為線

15、索鏈表，相應(yīng)的二叉樹稱為線索二叉樹(ThreadedBin aryTree)。構(gòu)造方法：(三) 樹與森林1. 樹的存儲結(jié)構(gòu)鏈表結(jié)構(gòu)：1.雙親表示法 2.孩子表示法 3.孩子兄弟表示法詳見P1352. 森林與二叉樹轉(zhuǎn)換 左孩子右兄弟3. 樹與森林的遍歷先序、中序遍歷，詳見P139當(dāng)以二叉鏈表做樹的存儲結(jié)構(gòu)時，樹的先序=二叉樹先序、樹的后序=二叉樹中序(四) 樹與二叉樹的應(yīng)用1. 二叉排序樹二叉排序樹(Bi nary Sort Tree )，又稱二叉查找樹(Bin ary Search Tree )，亦稱二叉 搜索樹。定義：二叉排序樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：(1) 若左子樹不空

16、，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；(2) 若右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；(3 )左、右子樹也分別為二叉排序樹；(4 )沒有鍵值相等的節(jié)點。此圖是B5T3.8/91圖二1068BST,但只有圖一是 AVL tree圖一，圖二都是哈夫曼（Huffman ）樹和哈夫曼編碼6/At_ 一(4 )(72> (T)此圖是B5T查找：步驟：若根結(jié)點的關(guān)鍵字值等于查找的關(guān)鍵字，成功。 否則，若小于根結(jié)點的關(guān)鍵字值，遞歸查左子樹。 若大于根結(jié)點的關(guān)鍵字值，遞歸查右子樹。若子樹為空，查找不成功。2. 平衡二叉樹（AVL）定義：它或者是一顆空樹， 或者具有以下性質(zhì)的二叉

17、樹：它的左子樹和右子樹的深度之差（平衡因子）的絕對值不超過 1且它的左子樹和右子樹都是一顆平衡二叉樹。平衡因子（bf）:結(jié)點的左子樹的深度減去右子樹的深度，那么顯然-1<=bf<=1哈夫曼樹是一類帶權(quán)路徑長度最短的樹，又稱最優(yōu)樹。路徑和路徑長度概念：從樹中一個結(jié)點到另一個結(jié)點之間的分支構(gòu)成這兩個結(jié)點之間的路徑，路徑上的分支數(shù)目稱為路徑長度。樹的路徑長度是從樹根到每一結(jié)點的路徑長度之和。推廣到一般情況，考慮帶權(quán)結(jié)點：結(jié)點的帶權(quán)路徑長度為從該結(jié)點到樹根之間的路徑長度與結(jié)點上的權(quán)值的乘積，樹的帶權(quán)路徑長度為樹中所有葉子結(jié)點的帶權(quán)路徑長度之和，記作WPL=帶權(quán)路徑長度WPL最小的二叉樹稱為

18、最優(yōu)二叉樹或哈夫曼樹利用二叉樹來設(shè)計前綴編碼哈夫曼算法構(gòu)造哈夫曼樹（P145）約定左分支表示字符“ 0” 右分支表示字符“ 1 ” 則從根結(jié)點到葉子結(jié)點 的路徑上分支字符組成 的字符串作為該葉子結(jié) 點字符的編碼。一般情況，當(dāng)帶有權(quán)值時，本質(zhì)上就是設(shè)計一棵哈夫曼樹，得到二進(jìn)制前綴編碼=哈夫曼編碼算法詳見P147四、圖（一）圖的基本概念圖是一種數(shù)據(jù)結(jié)構(gòu)，加上一組基本操作，構(gòu)成的一種抽象數(shù)據(jù)類型詳見（P156）途中數(shù)據(jù)元素通常稱為頂點，V是頂點的有窮非空集合；VR是兩個頂點的關(guān)系集合， 若v,w屬于VR則v,w表示從v到w的弧，稱v為弧尾（初始點），w尾弧頭（終結(jié)點）此時圖是有向圖，若 v，w屬于V

19、R必有w, v屬于VR則以無序?qū)，w，表示v和w的 一條邊，此時稱圖為無向圖完全圖有向完全圖邊或弧很少（enlogn ）的圖，稱為稀疏圖，反之為稠密圖 邊或弧所具有的相關(guān)數(shù)稱為權(quán)，帶權(quán)的圖稱為網(wǎng)子圖連通圖（二）圖的存儲及基本操作1. 鄰接矩陣法用兩個數(shù)組分別存儲數(shù)據(jù)元素（頂點）的信息，和數(shù)據(jù)元素之間的關(guān)系（邊或弧）的信息 算法詳見（P161）2. 鄰接表法鄰接表是圖的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)。算法詳見（P163）（三）圖的遍歷1. 深度優(yōu)先搜索（DFS圖示及算法（P168）詳見（P169）類似于樹的先根遍歷，可把圖轉(zhuǎn)化為樹操作。2. 廣度優(yōu)先搜索類似于樹的層次遍歷，可把圖轉(zhuǎn)為樹操作。（四）圖的基本應(yīng)

20、用1. 最?。ù鷥r）生成樹（P173）普里姆算法構(gòu)造最小生成樹：克魯斯卡爾算法構(gòu)造最小生成樹:2. 最短路徑（P186）在圖中從頂點 A到B,找一條所含邊（弧）最少的路徑，從A開始做廣度優(yōu)先搜索，直到B結(jié)束，則稱為最短路徑。可推廣的含權(quán)值的情形，此時最短路徑度量是路徑上權(quán)值之和帶權(quán)有向圖：源點-> 終點迪杰斯特拉算法：3. 拓?fù)渑判蛴赡硞€集合上的偏序得到該集合的全序偏序：若集合X上的關(guān)系R是自反的、反對稱的和傳遞的， 則稱R是集合X上的偏序關(guān) 系；設(shè)R是集合上的偏序，如果對每個x, y屬于X必有xRy或yRx,則稱R是集合X上的全序關(guān)系。詳見（P180）4. 關(guān)鍵路徑（最長路徑）（P18

21、3）五、查找（一）查找的基本概念在一些（有序的/無序的）數(shù)據(jù)元素中，通過一定的方法找出與給定關(guān)鍵字相同的數(shù)據(jù)元 素的過程叫做查找。 也就是根據(jù)給定的某個值， 在查找表中確定一個關(guān)鍵字等于給定值的 記錄或數(shù)據(jù)元素。（二）順序查找法1順序查找：核心：從數(shù)據(jù)的第一個元素開始，依次比較，直到找到目標(biāo)數(shù)據(jù)或查找失敗。1. 從表中的第一個元素開始，依次與關(guān)鍵字比較。2. 若某個元素匹配關(guān)鍵字，則查找成功。3. 若查找到最后一個元素還未匹配關(guān)鍵字，則查找失敗。2. 時間復(fù)雜度：順序查找平均關(guān)鍵字匹配次數(shù)為表長的一半，其時間復(fù)雜度為0(n)。3順序查找的評估：順序查找的優(yōu)點是對表無要求，插入數(shù)據(jù)可在0(1)內(nèi)

22、完成。缺點是時間復(fù)雜度較大，數(shù)據(jù)規(guī)模較大時，效率較低。(三) 折半查找法算法要求：折半查找要求線性表必須采用順序存儲結(jié)構(gòu)，而且表中元素按關(guān)鍵字有序排列。 查找過程：首先，假設(shè)表中元素是按升序排列，將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比 較，如果兩者相等，則查找成功否則利用中間位置記錄將表分成前、后兩個子表，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一子表，否則進(jìn)一步查找后一子表。重復(fù)以上過程，直到找到滿足條件的記錄， 使查找成功，或直到子表不存在為止， 此時查找不成功。(四) 散列(Hash)表哈希表定義：是根據(jù)關(guān)鍵碼值 (Key value)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。也就是說，它

23、通過把關(guān)鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。 這個映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。給定表M存在函數(shù)f(key)，對任意給定的關(guān)鍵字值 key，代入函數(shù)后若能得到包含該 關(guān)鍵字的記錄在表中的地址，則稱表M為哈希(Hash )表，函數(shù)f(key)為哈希(Hash)函數(shù)?；靖拍睿喝絷P(guān)鍵字為k,則其值存放在f(k)的存儲位置上。由此，不需比較便可直接取得所查記 錄。稱這個對應(yīng)關(guān)系f為散列函數(shù)，按這個思想建立的表為散列表。對不同的關(guān)鍵字可能得到同一散列地址，即k1承2，而f(k1)=f(k2)，這種現(xiàn)象稱為沖突(英語：Collisio n )。具有相同函數(shù)值的關(guān)鍵字對

24、該散列函數(shù)來說稱做同義詞。綜 上所述，根據(jù)散列函數(shù) f(k)和處理沖突的方法將一組關(guān)鍵字映射到一個有限的連續(xù)的 地址集(區(qū)間)上，并以關(guān)鍵字在地址集中的像”作為記錄在表中的存儲位置，這種表便稱為散列表，這一映射過程稱為散列造表或散列，所得的存儲位置稱散列地址。若對于關(guān)鍵字集合中的任一個關(guān)鍵字，經(jīng)散列函數(shù)映象到地址集合中任何一個地址的概率是相等的，則稱此類散列函數(shù)為均勻散列函數(shù)(Uniform Hash function )，這就是使關(guān)鍵字經(jīng)過散列函數(shù)得到一個隨機(jī)的地址”從而減少沖突。(五) 字符串模式匹配子串的定位操作是要在主串S中找出一個與子串T相同的子串，通常把主串S稱為目標(biāo)，把子串T稱為

25、模式，把從目標(biāo)S中查找模式為T的子串的過程稱為 模式匹配”1. Brute-Force算法的設(shè)計思想Brute-Force 是普通的模式匹配算法。將主串S的第1個字符和模式T的第1個字符比較，若相等，繼續(xù)逐個比較后續(xù)字符；若不等，從主串的下一字符起，重新與模式的第一個字符比較，直到主串的一個連續(xù)子串字符序列與模式相等，返回值為S中與T匹配的子序列第一個字符的序號，即匹配成功；否則，匹配失敗，返回值0。2. Brute-Force 算法的特點：每次遇到匹配不成功的情況，指針i都要移到本次匹配的開始位置的下一位，稱這樣的指針移動為回溯。指針的回溯越多，簡單模式匹配的執(zhí)行次數(shù)越多Brute-Forc

26、e 匹配算法的最壞時間復(fù)雜度為0(n*m), 般情況下BF算法的時間復(fù)雜度為0(n+m)3. KMP算法的改進(jìn)每當(dāng)一趟匹配過程中出現(xiàn)字符比較不等時，不需回溯指針i，而是利用已經(jīng)得到的部分匹配”的結(jié)果將模式向右滑動”盡可能遠(yuǎn)的一段距離后，繼續(xù)比較KMP算法的時間復(fù)雜度可以達(dá)到0(m+n)4. KMP 算法的設(shè)計思想假設(shè)以指針i和j分別指示主串和模式中正待比較的字符，令i的初值為0, j的初值為0若在匹配過程中，Si=Pj，則i和j分別增1否則i不變，而j退到nextj的位置再 比較，若相等，則指針各自增1否則j再退到下一個next值的位置，依次類推若令nextj=k ，則nextj表明當(dāng)模式中第

27、j個字符與主串中相應(yīng)字符失配時，在模式中 需重新和主串中該字符進(jìn)行比較的字符的位置模式串的next函數(shù)定義為f 0j=1nextjl='* "日* k I Xk<j H,P1P2,.P(+j.k+2-Pj*if UJ_|當(dāng)此集合不空時I 1英他情況例如：j12345678模式串a(chǎn)baabcacnextj01122312第一逍主串模式* i= 2a c a 11孔曰b shr日右a bt ； = 2 nejctZl = 1主串* i=2第二趟acabaabaabcacaabc模式af ; = 1 rtejtzElJ O主串I i = 3 4 »=8第三趟acab

28、aabaabcacaabc模式a b a a b cf j = l一f j = 6= 3第四軸主串模式| *呂 |= 14cabaabaAbcacaabc(a b)a # b c a c f > = 3* t ； = S利用模式的next函數(shù)進(jìn)行匹配的過程示例（六）查找算法的分析及應(yīng)用六、排序（一）排序的基本概念將雜亂無章的數(shù)據(jù)元素，通過一定的方法按關(guān)鍵字順序排列的過程叫做排序。分內(nèi)部排序和外部排序， 若整個排序過程不需要訪問外存便能完成，則稱此類排序問題為內(nèi)部排序。反之，若參加排序的記錄數(shù)量很大，整個序列的排序過程不可能在內(nèi)存中完成， 則稱此類排序問題為外部排序。內(nèi)部排序的過程是一個逐

29、步擴(kuò)大記錄的有序序列長度的過 程。（二）插入排序直接插入排序基本思想是每一步將一個待排序的記錄，插入到前面已經(jīng)排好序的有序序列中去，直到插完所有元素為止。有序I待排序I對待排序的序列逐亍SS入，完為止I怖有元養(yǎng)全部播入.排吊完施（三）氣泡排序冒泡排序的基本思想是，對相鄰的兀素進(jìn)行兩兩比較，順序相反則進(jìn)行交換，這樣，每一趟會將取小或取大的兀素浮"到頂端，最終達(dá)到完全有序相鄰元素兩兩比SE.反序則交換第一影完畢.將最大元累9浮到數(shù)組頂端同理,SI二輪將第二大元素B俘到數(shù)坦頂端排序完成（四）簡單選擇排序簡單選擇排序是最簡單直觀的一種算法，基本思想為每一趟從待排序的數(shù)據(jù)兀素中選擇最小（或最大

30、）的一個兀素作為首兀素，直到所有兀素排元為止，間單選擇排序是不穩(wěn)疋排序。在算法實現(xiàn)時，每一趟確定最小元素的時候會通過不斷地比較交換來使得首位置為當(dāng)前 最小，交換是個比較耗時的操作。 其實我們很容易發(fā)現(xiàn)， 在還未完全確定當(dāng)前最小元素之 前，這些交換都是無意義的。我們可以通過設(shè)置一個變量min，每一次比較僅存儲較小元素的數(shù)組下標(biāo)，當(dāng)輪循環(huán)結(jié)束之后，那這個變量存儲的就是當(dāng)前最小元素的下標(biāo)，此時再執(zhí)行交換操作即可。代碼實現(xiàn)很簡單，一起來看下。（五）希爾排序希爾排序是基于插入排序的，首先回顧一下插入排序，假設(shè)插入是從左向右執(zhí)行的，待插入兀素的左邊是有序的， 且假如待插入兀素比左邊的都小，就需要挪動左邊的

31、所有兀素，如下圖所示：圉t札圖丄：產(chǎn)人石邊的怕rriy王琵要o曰除l己立左邊的七個圧子書問芒那抑1圏M所示,狷btai入時,酥排施足祥個眄:刃國走叵隔羽元春做擂入轉(zhuǎn)序,然后環(huán)叵陽r車 哥研SA帶亭r直亂聞關(guān)瞌小如”II 1 III. 1T九為inn*iniW-Filllll帕ftf1ojtsrlefrininnrir亙3和妙；octe L_E叩rni刨】社匱淚主子恃描人啡.學(xué)數(shù)1G星木的圖形乖心遊更昏曷形藏堆把囲商錦1 r Mffism r軻元SE施等于1C» ；rr40匱5和蛋6 :石鬲分別為知和12執(zhí)行完插入徘帛后丙效需相比簡單插入排序，大間隔地做插入排序有兩個好處:一、大間隔直

32、接導(dǎo)致需要挪動的數(shù)據(jù)稀少，且數(shù)據(jù)挪動的效率高，圖5中一次挪動可以跨越40個位置；二、 經(jīng)過前一步大間隔的插入排序后，整個數(shù)組從整體上粗略地看已經(jīng)有了明顯的順序，后一步小間隔的插入排序時，一部分操作是不需要挪動數(shù)據(jù)的，再次減少了挪動數(shù)據(jù)的次數(shù)。間隔的序列：間隔的常用序列，通過遞歸表示：h=3*h+1。( 1,4,13,40,121)各種基于實驗的評估，估計它希爾排序的效率：“沒有理論上分析希爾排序的效率的結(jié)論,的時間級從0們?nèi)?3/2)到0們?nèi)?7/6) ” -1。(六) 快速排序快速排序算法的策略是這樣的： 首先把數(shù)組用某個值分為兩個子數(shù)組，且稱這個值為分組值,一個子數(shù)組中的元素均小于分組值，

33、另一子數(shù)組則均大于等于分組值，這里的子組內(nèi)并不排序；然后，再分別對兩個子組進(jìn)行再分組，重復(fù)遞歸這個過程，直到最后每兩個元素作為一 組進(jìn)行再分組，整個數(shù)組就排好序了。分組過程具體如下：同時從左往右和從右往左掃描數(shù)組，記掃描標(biāo)記位為LP和RP。在LP 一邊，若發(fā)現(xiàn)元素小于分組值則跳過（即向右移動一位檢查下一個元素），否則等待RP的掃描；RP若發(fā)現(xiàn)元素大于等于分組值跳過，直到找到小于分組值的元素，然后LP和RP位置的元素交換，重復(fù)這個過程，直到 LP和RP相遇。如圖7,8所示，以11號元素為分組值，LP停在0號位置，RP跳過10號，停在圖7中 的9號位置（粉色柱），然后 0號和9號交換，后續(xù)重復(fù)這個

34、過程。nghlScanEntering qukckSortQ; will partition flO-11)Aleftpivotright 日 canWill scan圍7和屋8 :以11號柱作為分裁1.0號#匸夕號哇子將交渙要9： 100個元春蘭數(shù)自涇過兩丸井組話蘭致果分組值的選擇，可以想見，理想的分組值應(yīng)該是待分組元素的中值，這樣分組后子組在數(shù)量少幾乎是一半對一半，不過找中值無疑增加了算法的工作量。圖7中采用了更簡單的方式，直接選數(shù)組最右邊的元素為分組值，分組結(jié)束后，再把這個值交換到 LP和RP相遇的位置，假如初始數(shù)組是從大到小排序的，這種情況下，選擇最右邊的元素作為分組值，其區(qū)分 度就很

35、差了。更好用的方法是所謂的取首尾中三項數(shù)據(jù)的中值或者平均值。通過對算法過程的描述可知，其時間復(fù)雜度應(yīng)該為：O(N*logN)，比簡單排序和希爾排序都要快。(七) 堆排序堆排序是利用堆這種數(shù)據(jù)結(jié)構(gòu)而設(shè)計的一種排序算法，堆排序是一種選擇排序，它的最壞，最好，平均時間復(fù)雜度均為O(nlogn)，它也是不穩(wěn)定排序。首先簡單了解下堆結(jié)構(gòu)。堆是具有以下性質(zhì)的完全二叉樹：每個結(jié)點的值都大于或等于其左右孩子結(jié)點的值，稱為大頂堆；或者每個結(jié)點的值都小于或等于其左右孩子結(jié)點的值，稱為小頂堆。如下圖：大頂堆小頂堆同時，我們對堆中的結(jié)點按層進(jìn)行編號，將這種邏輯結(jié)構(gòu)映射到數(shù)組中就是下面這個樣子nD5Q4540202535301015該數(shù)組從邏輯上講就是一個堆結(jié)構(gòu)，我們用簡單的公式來