數(shù)據(jù)結構筆記

文檔可能無法思考全面，請瀏覽后下載!數(shù)據(jù)結構筆記1/2文檔可能無法思考全面，請瀏覽后下載!數(shù)據(jù)結構筆記全文共31頁，當前為第1頁。數(shù)據(jù)結構筆記數(shù)據(jù)結構筆記全文共31頁，當前為第1頁?；A：數(shù)據(jù)結構與算法數(shù)據(jù)結構基本概念數(shù)據(jù)（data）：是對客觀事物的符號表示，在計算機科學中是指所有能輸入到計算機中并被計算機程序處理的符號總稱數(shù)據(jù)元素（dataelement）：是數(shù)據(jù)的基本單位，在計算機中通常被當做一個整體進行考慮和處理數(shù)據(jù)對象（dataobject）：性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集數(shù)據(jù)結構（datastructure）：相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合4類基本結構：集合、線性結構、樹形結構、圖形（網(wǎng)狀）結構數(shù)據(jù)結構的形式定義為數(shù)據(jù)結構是一個二元組DataStructure=（D,S），其中D是數(shù)據(jù)元素的有限集，S是D上關系的有限集數(shù)據(jù)結構定義中的“關系”描述的是數(shù)據(jù)元素之間的邏輯關系，因此又稱為數(shù)據(jù)的邏輯結構數(shù)據(jù)結構在計算機中的表示（映像）稱為物理結構（存儲結構）計算機中表示信息的最小單位是二進制中的一位，叫做位（bit），一到若干位組成一個位串表示一個數(shù)據(jù)元素，這個位串稱為元素或結點數(shù)據(jù)結構之間關系在計算機中的表示有兩種：順序映像、非順序映像，并由此得到兩種存儲結構：順序存儲、鏈式存儲，前者運用相對位置表示數(shù)據(jù)元素間的邏輯結構，后者借助指針任何一個算法的設計取決于數(shù)據(jù)（邏輯）結構，而實現(xiàn)依賴于存儲結構數(shù)據(jù)類型是一個值的集合和定義在這個值集上的一組操作的總稱數(shù)據(jù)類型分兩種：原子類型、結構類型，前者不可分解（例如int、char、float、void），后者結構類型由若干成分按某種結構組成，可分解，成分既可以是非結構的也可以是結構的（例：數(shù)組）數(shù)據(jù)結構筆記全文共31頁，當前為第2頁。抽象數(shù)據(jù)類型（AbstractDataType）：是指一個數(shù)學模型及定義在該模型上的一組操作（P8）數(shù)據(jù)結構筆記全文共31頁，當前為第2頁。抽象數(shù)據(jù)類型格式如下：ADT抽象數(shù)據(jù)類型名{數(shù)據(jù)對象：<數(shù)據(jù)對象的定義>數(shù)據(jù)關系：<數(shù)據(jù)關系的定義>數(shù)據(jù)操作：<數(shù)據(jù)操作的定義>}ADT抽象數(shù)據(jù)類型名基本操作格式如下：基本操作名（參數(shù)表）初始條件：<初始條件描述>操作結果：<操作結果描述>多形數(shù)據(jù)類型（polymorphicdatatype）：是指其值得成分不確定的數(shù)據(jù)類型（P9）抽象數(shù)據(jù)類型可由固有數(shù)據(jù)類型來表示和實現(xiàn)算法（概念）和算法分析（時、空性能）算法（algorithm）：對特定問題求解步驟的一種描述算法5特性：有窮、確定、可行、輸入、輸出1、有窮性：算法必須在可接受的時間內(nèi)執(zhí)行有窮步后結束2、確定性：每條指令必須要有確切含義，無二義性，并且只有唯一執(zhí)行路徑，即對相同的輸入只能得相同輸出3、可行性：算法中的操作都可通過已實現(xiàn)的基本運算執(zhí)行有限次來完成4、輸入：一個算法有一到多個輸入，并取自某個特定對象合集數(shù)據(jù)結構筆記全文共31頁，當前為第3頁。5、輸出：一個算法有一到多個輸出，這些輸出與輸入有著某些特定關系的量數(shù)據(jù)結構筆記全文共31頁，當前為第3頁。算法設計要求（好算法）：正確性、可讀性、健壯性、效率與低存儲需求健壯性是指對于規(guī)范要求以外的輸入能夠判斷出這個輸入不符合規(guī)范要求，并能有合理的處理方式。算法效率的度量：事后統(tǒng)計：程序運行結束后借助計算機內(nèi)部計時功能，缺點一是必須先運行依據(jù)算法編制的程序，二是受限于計算機軟硬件，導致掩蓋了算法本身的優(yōu)劣事前分析估計：消耗時間影響因素：算法策略、問題規(guī)模、編程語言、編譯程序產(chǎn)生的機器碼質(zhì)量、機器執(zhí)行指令的速度撇開各種影響因素只考慮問題的規(guī)模（通常用整數(shù)量n表示），記為問題規(guī)模的函數(shù)算法時間取決于控制結構（順序，分支，循環(huán)）和固有數(shù)據(jù)類型操作的綜合效果書寫格式：T（n）=O（f（n））f（n）為n的某個函數(shù)時間復雜度：算法的漸近時間復雜度（asymptotictimecomplexity），它表示隨問題規(guī)模的增大，算法執(zhí)行時間的增長率和f（n）的增長率相同以循環(huán)最深層原操作為度量基準頻度：該語句重復執(zhí)行的次數(shù)算法的存儲空間需求：空間復雜度（spacecomplexity）：算法所需存儲空間度量，記作S（n）=O（f（n）），其中n為問題規(guī)模的大小數(shù)據(jù)結構筆記全文共31頁，當前為第4頁。數(shù)據(jù)結構筆記全文共31頁，當前為第4頁。一、線性表線性表基本概念線性表（linear_list）：n個數(shù)據(jù)元素的有限序列結構特點：存在唯一的被稱作“第一個”、“最后一個”的數(shù)據(jù)元素，且除了第一個以外每個元素都有唯一前驅(qū)，除最后一個以外都有唯一后繼在復雜線性表中存在：數(shù)據(jù)項->記錄->文件，例如每個學生情況為一個記錄，它由學號、性別數(shù)據(jù)項組成，多個學生記錄組成一個文件在形如（a1，...，ai-1，ai，ai+1，...，an）中，ai-1領先于ai，ai領先于ai+1，且形成直接前驅(qū)元素，直接后繼元素關系元素個數(shù)n定義為線性表長度，n=0為空表相關操作算法見書（P20）線性表順序存儲結構和鏈式存儲結構（1）線性表順序表示和實現(xiàn)數(shù)據(jù)結構筆記全文共31頁，當前為第5頁。線性表順序存儲在一組連續(xù)的存儲單元中，鏈式存儲則不要求；順序結構可以隨機訪問，鏈式結構可以無限擴容數(shù)據(jù)結構筆記全文共31頁，當前為第5頁。確定存儲位置（計算公式）：第i個元素：LOC（ai）=LOC（a1）+（i-1）*LL是偏移量，即每個元素占用存儲單元第ai+1個元素：LOC（ai+1）=LOC（ai）+La1（起始位置或基位置）C語言下標從“0”開始，則表中第i個元素是L.elem[i-1]當對線性表進行操作時，被操作元素后面的元素角標會相應變化（前移、后移），算法（P24）（2）線性表鏈式表示和實現(xiàn)特點：用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素（存儲單元不一定連續(xù)）結點存儲數(shù)據(jù)元素及直接后繼的存儲位置信息，兩個域：數(shù)據(jù)域和指針域，指針域中存儲的信息稱為指針或鏈，僅含有一個指針域故又稱線性鏈表或單鏈表鏈表的插入：先增加一條指針再修改原指針頭指針指向第一個數(shù)據(jù)元素的存儲位置，最后一個結點的指針為空（NULL）鏈表表示方法及算法（P28）單鏈表第一個結點前加一個頭結點Head，其數(shù)據(jù)域可為空也可存儲一些附加信息（鏈長等）假設p是指向線性表中i個元素（ai）的指針，則p->next是指向i+1個數(shù)據(jù)元素在單鏈表中，取得第i個元素必須從頭指針開始尋找，因此單鏈表是非隨機的存儲結構線性表指邏輯結構，從抽象數(shù)據(jù)層面來說順序表和鏈表指物理存儲結構邏輯結構：離散、線性、層次、網(wǎng)狀應用見書算法數(shù)據(jù)結構筆記全文共31頁，當前為第6頁。二、棧和隊列數(shù)據(jù)結構筆記全文共31頁，當前為第6頁。棧的基本概念棧（stack）是限定僅在表尾進行插入或刪除操作的線性表表尾為棧頂，表頭為棧底，遵循后進先出原理（（lastinfirston，LIFO），不含元素則為空棧操作：在棧頂插入（入棧）和刪除（出棧），棧初始化、判空、取棧頂元素（算法P45）棧的順序存儲和鏈式存儲順序棧，即棧的順序存儲結構是利用一組連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時附設指針top指示棧頂元素在順序棧中的位置初始棧時不應限定棧的最大容量，基本做法是先為棧分配一個基本容量，然后在應用過程中，不夠用再逐段擴大（算法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）隊列隊列先進先出（firstinfirstout，F(xiàn)IFO），隊尾一端插入，隊首一端刪除元素（日常排隊）數(shù)據(jù)結構筆記全文共31頁，當前為第7頁。隊列與棧均有八種基本操作（P59），隊列一般用鏈表實現(xiàn)，棧用順序表實現(xiàn)數(shù)據(jù)結構筆記全文共31頁，當前為第7頁。雙端隊列（限定操作的隊列）（P60）棧和隊列的應用鏈隊列、循環(huán)隊列（P60），離散事件模擬（銀行接待工作（P65））特殊矩陣的壓縮存儲如何存儲矩陣的元，使矩陣的運算有效進行。高級語言常用二維數(shù)組存儲陣元面對如高階矩陣，多值相同矩陣和多零元素矩陣進行壓縮存儲節(jié)省空間壓縮存儲：為多個值相同的元只分配一個空間，對零元不分配值相同元素或零元素具有分布規(guī)律則稱為特殊矩陣，反之為稀疏矩陣具體應用與算法（P95）三、樹與二叉樹樹的基本概念樹是非線性數(shù)據(jù)結構，以分支關系定義的層次結構樹是n（n>=0）個結點的有限集詳見（P118），基本術語（P120）二叉樹二叉樹的定義及其主要特征：二叉樹是每個結點最多有兩個子樹的樹結構。通常子樹被稱作“左子樹”（leftsubtree）和“右子樹”（rightsubtree）。性質(zhì)：數(shù)據(jù)結構筆記全文共31頁，當前為第8頁。1.數(shù)據(jù)結構筆記全文共31頁，當前為第8頁。2.3.滿二叉樹：完全二叉樹：4.5.二叉樹的順序存儲結構和鏈式存儲結構順序存儲，用一組位置連續(xù)的存儲單元依次自上而下、自左至右存儲完全二叉樹上的結點元素，即將完全二叉樹上編號為i的結點依次存儲在如上定義的一位數(shù)組下標為i-1的分量中。123456789鏈式存儲，每個結點中至少包含三個域,[左指針，數(shù)據(jù)，右指針]，稱作“二叉鏈表”增加一個雙親指針域，則稱作“三叉鏈表”詳見P126-127二叉樹的遍歷遍歷二叉樹，每個結點均被訪問一次，且僅有一次。在限定先左后右的訪問序列后，有三種遍歷方式：先序（DLR），中序（LDR）,后續(xù)（LRD）P129算法6.1（波蘭式）層次遍歷，無論那種遍歷方式，對含n個結點的二叉樹，時間復雜度都為O（n），空間復雜度也為O（n）。線索二叉樹的基本概念和構造摘要：對于n個結點的二叉樹，在二叉鏈存儲結構中有n+1（2n-（n-1））個空鏈域，利用這些空鏈域存放在某種遍歷次序下該結點的前驅(qū)結點和后繼結點的指針，這些指針稱為線索數(shù)據(jù)結構筆記全文共31頁，當前為第9頁。概念：加上了線索的二叉鏈表稱為線索鏈表，相應的二叉樹稱為線索二叉樹(ThreadedBinaryTree)。數(shù)據(jù)結構筆記全文共31頁，當前為第9頁。構造方法：樹與森林樹的存儲結構鏈表結構：1.雙親表示法2.孩子表示法3.孩子兄弟表示法詳見P135森林與二叉樹轉(zhuǎn)換左孩子右兄弟樹與森林的遍歷先序、中序遍歷，詳見P139當以二叉鏈表做樹的存儲結構時，樹的先序=二叉樹先序、樹的后序=二叉樹中序數(shù)據(jù)結構筆記全文共31頁，當前為第10頁。樹與二叉樹的應用數(shù)據(jù)結構筆記全文共31頁，當前為第10頁。二叉排序樹二叉排序樹（BinarySortTree），又稱二叉查找樹（BinarySearchTree），亦稱二叉搜索樹。定義：二叉排序樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：（1）若左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；（2）若右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；（3）左、右子樹也分別為二叉排序樹；（4）沒有鍵值相等的節(jié)點。查找：步驟：若根結點的\t"bbbs://baike.baiduaaa/item/%E4%BA%8C%E5%8F%89%E6%8E%92%E5%BA%8F%E6%A0%91/_blank"關鍵字值等于查找的關鍵字，\t"bbbs://baike.baiduaaa/item/%E4%BA%8C%E5%8F%89%E6%8E%92%E5%BA%8F%E6%A0%91/_blank"成功。否則，若小于根結點的關鍵字值，\t"bbbs://baike.baiduaaa/item/%E4%BA%8C%E5%8F%89%E6%8E%92%E5%BA%8F%E6%A0%91/_blank"遞歸查左子樹。若大于根結點的關鍵字值，遞歸查右子樹。若子樹為空，查找不成功。平衡二叉樹(AVL)定義：它或者是一顆空樹，或者具有以下性質(zhì)的二叉樹：它的左子樹和右子樹的深度數(shù)據(jù)結構筆記全文共31頁，當前為第11頁。之差(平衡因子)的絕對值不超過1，且它的左子樹和右子樹都是一顆平衡二叉樹。數(shù)據(jù)結構筆記全文共31頁，當前為第11頁。平衡因子(bf)：結點的左子樹的深度減去右子樹的深度，那么顯然-1<=bf<=1圖一，圖二都是BST，但只有圖一是AVLtree哈夫曼（Huffman）樹和哈夫曼編碼哈夫曼樹是一類帶權路徑長度最短的樹，又稱最優(yōu)樹。路徑和路徑長度概念：從樹中一個結點到另一個結點之間的分支構成這兩個結點之間的路徑，路徑上的分支數(shù)目稱為路徑長度。樹的路徑長度是從樹根到每一結點的路徑長度之和。推廣到一般情況，考慮帶權結點：結點的帶權路徑長度為從該結點到樹根之間的路徑長度與結點上的權值的乘積，樹的帶權路徑長度為樹中所有葉子結點的帶權路徑長度之和，記作WPL=△帶權路徑長度WPL最小的二叉樹稱為最優(yōu)二叉樹或哈夫曼樹哈夫曼算法構造哈夫曼樹（P145）數(shù)據(jù)結構筆記全文共31頁，當前為第12頁。哈夫曼編碼數(shù)據(jù)結構筆記全文共31頁，當前為第12頁。前綴編碼：設計長短不等的編碼，任一字符的編碼都不是另一個字符的編碼的前綴利用二叉樹來設計前綴編碼約定左分支表示字符“0”右分支表示字符“1”則從根結點到葉子結點的路徑上分支字符組成的字符串作為該葉子結點字符的編碼。數(shù)據(jù)結構筆記全文共31頁，當前為第13頁。一般情況，當帶有權值時，本質(zhì)上就是設計一棵哈夫曼樹，得到二進制前綴編碼=哈夫曼編碼算法詳見P147數(shù)據(jù)結構筆記全文共31頁，當前為第13頁。圖圖的基本概念圖是一種數(shù)據(jù)結構，加上一組基本操作，構成的一種抽象數(shù)據(jù)類型詳見（P156）途中數(shù)據(jù)元素通常稱為頂點，V是頂點的有窮非空集合；VR是兩個頂點的關系集合，若<v，w>屬于VR，則<v,w>表示從v到w的弧，稱v為弧尾（初始點），w尾弧頭（終結點）此時圖是有向圖，若<v，w>屬于VR必有<w，v>屬于VR，則以無序?qū)?lt;v，w>，表示v和w的一條邊，此時稱圖為無向圖完全圖有向完全圖邊或弧很少（e<nlogn）的圖，稱為稀疏圖，反之為稠密圖邊或弧所具有的相關數(shù)稱為權，帶權的圖稱為網(wǎng)子圖連通圖數(shù)據(jù)結構筆記全文共31頁，當前為第14頁。（二）圖的存儲及基本操作數(shù)據(jù)結構筆記全文共31頁，當前為第14頁。1.鄰接矩陣法用兩個數(shù)組分別存儲數(shù)據(jù)元素（頂點）的信息，和數(shù)據(jù)元素之間的關系（邊或弧）的信息算法詳見（P161）鄰接表法鄰接表是圖的一種鏈式存儲結構。算法詳見（P163）（三）圖的遍歷1.深度優(yōu)先搜索（DFS）類似于樹的先根遍歷，可把圖轉(zhuǎn)化為樹操作。圖示及算法（P168）2.廣度優(yōu)先搜索類似于樹的層次遍歷，可把圖轉(zhuǎn)為樹操作。詳見（P169）（四）圖的基本應用1.最小（代價）生成樹（P173）普里姆算法構造最小生成樹：克魯斯卡爾算法構造最小生成樹：數(shù)據(jù)結構筆記全文共31頁，當前為第15頁。2.最短路徑（P186）數(shù)據(jù)結構筆記全文共31頁，當前為第15頁。在圖中從頂點A到B，找一條所含邊（弧）最少的路徑，從A開始做廣度優(yōu)先搜索，直到B結束，則稱為最短路徑?？赏茝V的含權值的情形，此時最短路徑度量是路徑上權值之和帶權有向圖：源點->終點迪杰斯特拉算法：3.拓撲排序由某個集合上的偏序得到該集合的全序偏序：若集合X上的關系R是自反的、反對稱的和傳遞的，則稱R是集合X上的偏序關系；設R是集合上的偏序，如果對每個x，y屬于X必有xRy或yRx，則稱R是集合X上的全序關系。詳見（P180）4.關鍵路徑（最長路徑）（P183）數(shù)據(jù)結構筆記全文共31頁，當前為第16頁。查找數(shù)據(jù)結構筆記全文共31頁，當前為第16頁。查找的基本概念在一些（有序的/無序的）\t"bbbs://baike.baiduaaa/item/%E6%9F%A5%E6%89%BE/_blank"數(shù)據(jù)元素中，通過一定的方法找出與給定關鍵字相同的數(shù)據(jù)元素的過程叫做查找。也就是根據(jù)給定的某個值，在\t"bbbs://baike.baiduaaa/item/%E6%9F%A5%E6%89%BE/_blank"查找表中確定一個\t"bbbs://baike.baiduaaa/item/%E6%9F%A5%E6%89%BE/_blank"關鍵字等于給定值的記錄或數(shù)據(jù)元素。順序查找法順序查找：

核心：從數(shù)據(jù)的第一個元素開始，依次比較，直到找到目標數(shù)據(jù)或查找失敗。

1.從表中的第一個元素開始，依次與關鍵字比較。

2.若某個元素匹配關鍵字，則查找成功。

3.若查找到最后一個元素還未匹配關鍵字，則查找失敗。時間復雜度：順序查找平均關鍵字匹配次數(shù)為表長的一半，其時間復雜度為O(n)。3.順序查找的評估：順序查找的優(yōu)點是對表無要求，插入數(shù)據(jù)可在O(1)內(nèi)完成。缺點是時間復雜度較大，數(shù)據(jù)規(guī)模較大時，效率較低。折半查找法算法要求：折半查找要求線性表必須采用順序存儲結構，而且表中元素按關鍵字有序排列。數(shù)據(jù)結構筆記全文共31頁，當前為第17頁。查找過程：首先，假設表中元素是按升序排列，將表中間位置記錄的\t"bbbs://baike.baiduaaa/item/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/_blank"關鍵字與查找關鍵字比較，如果兩者相等，則查找成功數(shù)據(jù)結構筆記全文共31頁，當前為第17頁。否則利用中間位置\t"bbbs://baike.baiduaaa/item/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/_blank"記錄將表分成前、后兩個子表，如果中間位置記錄的關鍵字大于查找關鍵字，則進一步查找前一子表，否則進一步查找后一子表。重復以上過程，直到找到滿足條件的\t"bbbs://baike.baiduaaa/item/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE/_blank"記錄，使查找成功，或直到子表不存在為止，此時查找不成功。散列（Hash）表哈希表定義：是根據(jù)關鍵碼值(Keyvalue)而直接進行訪問的\t"bbbs://baike.baiduaaa/item/%E5%93%88%E5%B8%8C%E8%A1%A8/_blank"數(shù)據(jù)結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數(shù)叫做\t"bbbs://baike.baiduaaa/item/%E5%93%88%E5%B8%8C%E8%A1%A8/_blank"散列函數(shù)，存放記錄的\t"bbbs://baike.baiduaaa/item/%E5%93%88%E5%B8%8C%E8%A1%A8/_blank"數(shù)組叫做\t"bbbs://baike.baiduaaa/item/%E5%93%88%E5%B8%8C%E8%A1%A8/_blank"散列表。給定表M，存在函數(shù)f(key)，對任意給定的關鍵字值key，代入函數(shù)后若能得到包含該關鍵字的記錄在表中的位置，則稱表M為哈希(Hash）表，函數(shù)f(key)為哈希(Hash)函數(shù)。基本概念：若關鍵字為k，則其值存放在f(k)的存儲位置上。由此，不需比較便可直接取得所查記錄。稱這個對應關系f為散列函數(shù)，按這個思想建立的表為散列表。對不同的關鍵字可能得到同一散列位置，即k1≠k2，而f(k1)=f(k2)，這種現(xiàn)象稱為沖突（英語：Collision）。具有相同函數(shù)值的關鍵字對該散列函數(shù)來說稱做同義詞。綜上所述，根據(jù)散列函數(shù)f(k)和處理沖突的方法將一組關鍵字映射到一個有限的連續(xù)的位置集（區(qū)間）上，并以關鍵字在位置集中的“像”作為記錄在表中的存儲位置，這種表便稱為散列表，這一映射過程稱為散列造表或散列，所得的存儲位置稱散列位置。若對于關鍵字集合中的任一個關鍵字，經(jīng)散列函數(shù)映象到位置集合中任何一個位置的概率是相等的，則稱此類散列函數(shù)為均勻散列函數(shù)（UniformHashfunction），這就是使關鍵字經(jīng)過散列函數(shù)得到一個“隨機的位置”，從而減少沖突。字符串模式匹配子串的定位操作是要在主串S中找出一個與子串T相同的子串，通常把主串S稱為目標，把子串T稱為模式，把從目標S中查找模式為T的子串的過程稱為“模式匹配”。數(shù)據(jù)結構筆記全文共31頁，當前為第18頁。Brute-Force算法的設計思想

Brute-Force是普通的模式匹配算法。將主串S的第1個字符和模式T的第1個字符比較，若相等，繼續(xù)逐個比較后續(xù)字符；若不等，從主串的下一字符起，重新與模式的第一個字符比較，直到主串的一個連續(xù)子串字符序列與模式相等，返回值為S中與T匹配的子序列第一個字符的序號，即匹配成功；否則，匹配失敗，返回值0。數(shù)據(jù)結構筆記全文共31頁，當前為第18頁。Brute-Force算法的特點：

每次遇到匹配不成功的情況，指針i都要移到本次匹配的開始位置的下一位，稱這樣的指針移動為回溯。指針的回溯越多，簡單模式匹配的執(zhí)行次數(shù)越多Brute-Force匹配算法的最壞時間復雜度為O(n*m)，一般情況下BF算法的時間復雜度為O(n+m)3.KMP算法的改進

每當一趟匹配過程中出現(xiàn)字符比較不等時，不需回溯指針i，而是利用已經(jīng)得到的“部分匹配”的結果將模式向右“滑動”盡可能遠的一段距離后，繼續(xù)比較

KMP算法的時間復雜度可以達到O(m+n)

4.KMP算法的設計思想假設以指針i和j分別指示主串和模式中正待比較的字符，令i的初值為0，j的初值為0

若在匹配過程中，Si=Pj，則i和j分別增1，否則i不變，而j退到next[j]的位置再比較，若相等，則指針各自增1，否則j再退到下一個next值的位置，依次類推

若令next[j]=k，則next[j]表明當模式中第j個字符與主串中相應字符失配時，在模式中需重新和主串中該字符進行比較的字符的位置

模式串的next函數(shù)定義為數(shù)據(jù)結構筆記全文共31頁，當前為第19頁。數(shù)據(jù)結構筆記全文共31頁，當前為第19頁。查找算法的分析及應用排序排序的基本概念將雜亂無章的數(shù)據(jù)元素，通過一定的方法按關鍵字順序排列的過程叫做排序。分\t"bbbs://baike.baiduaaa/item/%E6%8E%92%E5%BA%8F/_blank"內(nèi)部排序和\t"bbbs://baike.baiduaaa/item/%E6%8E%92%E5%BA%8F/_blank"外部排序，若整個排序過程不需要訪問外存便能完成，則稱此類排序問題為內(nèi)部排序。反之，若參加排序的記錄數(shù)量很大，整個序列的排序過程不可能在\t"bbbs://baike.baiduaaa/item/%E6%8E%92%E5%BA%8F/_blank"內(nèi)存中完成，則稱此類排序問題為外部排序。內(nèi)部排序的過程是一個逐步擴大記錄的有序序列長度的過程。

插入排序數(shù)據(jù)結構筆記全文共31頁，當前為第20頁。直接插入排序基本思想是每一步將一個待排序的記錄，插入到前面已經(jīng)排好序的有序序列中去，直到插完所有元素為止。數(shù)據(jù)結構筆記全文共31頁，當前為第20頁。氣泡排序冒泡排序的基本思想是，對相鄰的元素進行兩兩比較，順序相反則進行交換，這樣，每一趟會將最小或最大的元素“浮”到頂端，最終達到完全有序數(shù)據(jù)結構筆記全文共31頁，當前為第21頁。數(shù)據(jù)結構筆記全文共31頁，當前為第21頁。簡單選擇排序簡單選擇排序是最簡單直觀的一種算法，基本思想為每一趟從待排序的數(shù)據(jù)元素中選擇最?。ɑ蜃畲螅┑囊粋€元素作為首元素，直到所有元素排完為止，簡單選擇排序是不穩(wěn)定排序。在算法實現(xiàn)時，每一趟確定最小元素的時候會通過不斷地比較交換來使得首位置為當前最小，交換是個比較耗時的操作。其實我們很容易發(fā)現(xiàn)，在還未完全確定當前最小元素之前，這些交換都是無意義的。我們可以通過設置一個變量min，每一次比較僅存儲較小元素的數(shù)組下標，當輪循環(huán)結束之后，那這個變量存儲的就是當前最小元素的下標，此時再執(zhí)行交換操作即可。代碼實現(xiàn)很簡單，一起來看下。希爾排序希爾排序是基于插入排序的，首先回顧一下插入排序，假設插入是從左向右執(zhí)行的，待插入元素的左邊是有序的，且假如待插入元素比左邊的都小，就需要挪動左邊的所有元素，如下圖所示：數(shù)據(jù)結構筆記全文共31頁，當前為第22頁。數(shù)據(jù)結構筆記全文共31頁，當前為第22頁。數(shù)據(jù)結構筆記全文共31頁，當前為第23頁。數(shù)據(jù)結構筆記全文共31頁，當前為第23頁。數(shù)據(jù)結構筆記全文共31頁，當前為第24頁。數(shù)據(jù)結構筆記全文共31頁，當前為第24頁。相比簡單插入排序，大間隔地做插入排序有兩個好處：一、大間隔直接導致需要挪動的數(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...）希爾排序的效率：“沒有理論上分析希爾排序的效率的結論，各種基于實驗的評估，估計它的時間級從O(N^(3/2))到O(N^(7/6))”--[1]。數(shù)據(jù)結構筆記全文共31頁，當前為第25頁?？焖倥判驍?shù)據(jù)結構筆記全文共31頁，當前為第25頁?？焖倥判蛩惴ǖ牟呗允沁@樣的：首先把數(shù)組用某個值分為兩個子數(shù)組，且稱這個值為分組值，一個子數(shù)組中的元素均小于分組值，另一子數(shù)組則均大于等于分組值，這里的子組內(nèi)并不排序；然后，再分別對兩個子組進行再分組，重復遞歸這個過程，直到最后每兩個元素作為一組進行再分組，整個數(shù)組就排好序了。分組過程具體如下：同時從左往右和從右往左掃描數(shù)組，記掃描標記位為LP和RP。在LP一邊，若發(fā)現(xiàn)元素小于分組值則跳過（即向右移動一位檢查下一個元素），否則等待RP的掃描；RP若發(fā)現(xiàn)元素大于等于分組值跳過，直到找到小于分組值的元素，然后LP和RP位置的元素交換，重復這個過程，直到LP和RP相遇。如圖7,8所示，以11號元素為分組值，LP停在0號位置，RP跳過10號，停在圖7中的9號位置（粉色柱），然后0號和9號交換，后續(xù)重復這個過程。數(shù)據(jù)結構筆記全文共31頁，當前為第26頁。數(shù)據(jù)結構筆記全文共31頁，當前為第26頁。分組值的選擇，可以想見，理想的分組值應該是待分組元素的中值，這樣分組后子組在數(shù)量少幾乎是一半對一半，不過找中值無疑增加了算法的工作量。圖7中采用了更簡單的方式，直接選數(shù)組最右邊的元素為分組值，分組結束后，再把這個值交換到LP和RP相遇的位數(shù)據(jù)結構筆記全文共31頁，當前為第27頁。置，假如初始數(shù)組是從大到小排序的，這種情況下，選擇最右邊的元素作為分組值，其區(qū)分度就很差了。更好用的方法是所謂的取首尾中三項數(shù)據(jù)的中值或者平均值。數(shù)據(jù)結構筆記全文共31頁，當前為第27頁。數(shù)據(jù)結構筆記全文共31頁，當前為第28頁。通過對算法過程的描述可知，其時間復雜度應該為：O(N*logN)，比簡單排序和希爾排序都要快。數(shù)據(jù)結構筆記全文共31頁，當前為第28頁。堆排序堆排序是利用堆這種數(shù)據(jù)結構而設計的一種排序算法，堆排序是一種選擇排序，它的最壞，最好，平均時間復雜度均為O(nlogn)，它也是不穩(wěn)定排序。首先簡單了解下堆結構。堆是具有以下性質(zhì)的完全二叉樹：每個結點的值都大于或等于其左右孩子結點的值，稱為大頂堆；或者