課程簡(jiǎn)介課件

課程簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu)深圳大學(xué)計(jì)算機(jī)系

蔡茂國(guó)課程簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu)《數(shù)據(jù)結(jié)構(gòu)》課程簡(jiǎn)介本課程教材為：《數(shù)據(jù)結(jié)構(gòu)》(C語(yǔ)言版)嚴(yán)蔚敏，吳偉民清華大學(xué)出版社2004年11月（第28次印刷）2主要參考教材《數(shù)據(jù)結(jié)構(gòu)》課程簡(jiǎn)介本課程教材為：2主要參考教材《數(shù)據(jù)結(jié)構(gòu)》課程簡(jiǎn)介

所有課件、作業(yè)及實(shí)驗(yàn)，均上傳至：深圳大學(xué)首頁(yè)－－課程中心－－輸入學(xué)生姓名及密碼，實(shí)現(xiàn)登錄－－從《數(shù)據(jù)結(jié)構(gòu)》課程下下載3課件下載《數(shù)據(jù)結(jié)構(gòu)》課程簡(jiǎn)介所有課件、作業(yè)及實(shí)驗(yàn)，均上傳至：3課件第一章

數(shù)據(jù)結(jié)構(gòu)緒論數(shù)據(jù)結(jié)構(gòu)深圳大學(xué)計(jì)算機(jī)系

蔡茂國(guó)第一章

數(shù)據(jù)結(jié)構(gòu)緒論數(shù)據(jù)結(jié)構(gòu)一、數(shù)據(jù)5第一節(jié)數(shù)據(jù)結(jié)構(gòu)是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計(jì)算機(jī)中，被計(jì)算機(jī)程序識(shí)別和處理的符號(hào)的集合數(shù)值性數(shù)據(jù)非數(shù)值性數(shù)據(jù)第１章數(shù)據(jù)結(jié)構(gòu)緒論一、數(shù)據(jù)5第一節(jié)數(shù)據(jù)結(jié)構(gòu)是信息的載體，是描述客觀事物的數(shù)、二、數(shù)據(jù)元素（DataElement）6第一節(jié)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)的基本單位。在計(jì)算機(jī)程序中常作為一個(gè)整體進(jìn)行考慮和處理。有時(shí)一個(gè)數(shù)據(jù)元素可以由若干數(shù)據(jù)項(xiàng)(DataItem)組成（此時(shí)數(shù)據(jù)元素被稱(chēng)為記錄）數(shù)據(jù)元素又稱(chēng)為元素、結(jié)點(diǎn)、記錄第１章數(shù)據(jù)結(jié)構(gòu)緒論二、數(shù)據(jù)元素（DataElement）6第一節(jié)數(shù)據(jù)結(jié)構(gòu)數(shù)三、數(shù)據(jù)項(xiàng)（DataItem）7第一節(jié)數(shù)據(jù)結(jié)構(gòu)具有獨(dú)立含義的最小標(biāo)識(shí)單位。第１章數(shù)據(jù)結(jié)構(gòu)緒論學(xué)號(hào)姓名學(xué)院專(zhuān)業(yè)三、數(shù)據(jù)項(xiàng)（DataItem）7第一節(jié)數(shù)據(jù)結(jié)構(gòu)具有獨(dú)立含四、數(shù)據(jù)對(duì)象（DataObject）8第一節(jié)數(shù)據(jù)結(jié)構(gòu)具有相同性質(zhì)的數(shù)據(jù)元素的集合。整數(shù)數(shù)據(jù)對(duì)象N={0,1,2,…}字母字符數(shù)據(jù)對(duì)象C={‘A’,‘B’,‘C’,…‘F’}。第１章數(shù)據(jù)結(jié)構(gòu)緒論四、數(shù)據(jù)對(duì)象（DataObject）8第一節(jié)數(shù)據(jù)結(jié)構(gòu)具有五、結(jié)構(gòu)（Structure）9第一節(jié)數(shù)據(jù)結(jié)構(gòu)

結(jié)構(gòu)是元素之間的：空間位置關(guān)系相互作用和依賴(lài)關(guān)系第１章數(shù)據(jù)結(jié)構(gòu)緒論五、結(jié)構(gòu)（Structure）9第一節(jié)數(shù)據(jù)結(jié)構(gòu)結(jié)構(gòu)是元素五、結(jié)構(gòu)10第一節(jié)數(shù)據(jù)結(jié)構(gòu)

四種基本結(jié)構(gòu)集合結(jié)構(gòu)線性結(jié)構(gòu)樹(shù)形結(jié)構(gòu)圖形結(jié)構(gòu)第１章數(shù)據(jù)結(jié)構(gòu)緒論456231125436123456123456五、結(jié)構(gòu)10第一節(jié)數(shù)據(jù)結(jié)構(gòu)四種基本結(jié)構(gòu)第１章數(shù)據(jù)結(jié)構(gòu)緒六、數(shù)據(jù)結(jié)構(gòu)（DataStructure）11第一節(jié)數(shù)據(jù)結(jié)構(gòu)1.形式定義：某一數(shù)據(jù)對(duì)象的所有數(shù)據(jù)成員之間的關(guān)系。記為：Data_Structure={D,S}其中，D是某一數(shù)據(jù)對(duì)象，S是該對(duì)象中所有數(shù)據(jù)成員之間的關(guān)系的有限集合。第１章數(shù)據(jù)結(jié)構(gòu)緒論六、數(shù)據(jù)結(jié)構(gòu)（DataStructure）11第一節(jié)數(shù)據(jù)六、數(shù)據(jù)結(jié)構(gòu)12第一節(jié)數(shù)據(jù)結(jié)構(gòu)2.線性數(shù)據(jù)結(jié)構(gòu)舉例L={K,R}K={1,2,3,4,5,6}R={<1,2>,<2,3>,<3,4>,<4,5>,<5,6>}第１章數(shù)據(jù)結(jié)構(gòu)緒論123456六、數(shù)據(jù)結(jié)構(gòu)12第一節(jié)數(shù)據(jù)結(jié)構(gòu)2.線性數(shù)據(jù)結(jié)構(gòu)舉例第１章六、數(shù)據(jù)結(jié)構(gòu)13第一節(jié)數(shù)據(jù)結(jié)構(gòu)3.樹(shù)形數(shù)據(jù)結(jié)構(gòu)舉例T={K,R}K={1,2,3,4,5,6}R={<1,2>,<1,3>,<2,4>,<2,5>,<3,6>}第１章數(shù)據(jù)結(jié)構(gòu)緒論456231六、數(shù)據(jù)結(jié)構(gòu)13第一節(jié)數(shù)據(jù)結(jié)構(gòu)3.樹(shù)形數(shù)據(jù)結(jié)構(gòu)舉例第１章六、數(shù)據(jù)結(jié)構(gòu)14第一節(jié)數(shù)據(jù)結(jié)構(gòu)4.圖形數(shù)據(jù)結(jié)構(gòu)舉例G={K,R}K={1,2,3,4,5,6}R={(1,2),(1,5),(1,6),(2,3),(2,4),(2,6),(3,4),(4,5),(4,6),(5,6)}第１章數(shù)據(jù)結(jié)構(gòu)緒論123456六、數(shù)據(jù)結(jié)構(gòu)14第一節(jié)數(shù)據(jù)結(jié)構(gòu)4.圖形數(shù)據(jù)結(jié)構(gòu)舉例第１章七、應(yīng)用舉例15第一節(jié)數(shù)據(jù)結(jié)構(gòu)1.線性數(shù)據(jù)結(jié)構(gòu)舉例數(shù)據(jù)結(jié)構(gòu)學(xué)生選課名單（部分）第１章數(shù)據(jù)結(jié)構(gòu)緒論學(xué)號(hào)姓名學(xué)院專(zhuān)業(yè)2004131221黃磊信息工程學(xué)院信息工程學(xué)院2004131209熊玲玲信息工程學(xué)院信息工程學(xué)院2004131135彭智俊信息工程學(xué)院信息工程學(xué)院2004131252徐元慶信息工程學(xué)院信息工程學(xué)院2004131099吳小池信息工程學(xué)院信息工程學(xué)院2004131031陳明亮信息工程學(xué)院信息工程學(xué)院七、應(yīng)用舉例15第一節(jié)數(shù)據(jù)結(jié)構(gòu)1.線性數(shù)據(jù)結(jié)構(gòu)舉例第１章七、應(yīng)用舉例16第一節(jié)數(shù)據(jù)結(jié)構(gòu)2.樹(shù)形數(shù)據(jù)結(jié)構(gòu)舉例UNIX文件系統(tǒng)結(jié)構(gòu)圖（部分）第１章數(shù)據(jù)結(jié)構(gòu)緒論/

rootbinlibuseretcmathdsswhangxiongpan七、應(yīng)用舉例16第一節(jié)數(shù)據(jù)結(jié)構(gòu)2.樹(shù)形數(shù)據(jù)結(jié)構(gòu)舉例第１章七、應(yīng)用舉例17第一節(jié)數(shù)據(jù)結(jié)構(gòu)3.圖形數(shù)據(jù)結(jié)構(gòu)舉例深圳城市交通示意圖（部分）第１章數(shù)據(jù)結(jié)構(gòu)緒論南山福田羅湖鹽田寶安西麗梅林布吉龍華龍崗七、應(yīng)用舉例17第一節(jié)數(shù)據(jù)結(jié)構(gòu)3.圖形數(shù)據(jù)結(jié)構(gòu)舉例第１章八、數(shù)據(jù)結(jié)構(gòu)要解決的問(wèn)題18第一節(jié)數(shù)據(jù)結(jié)構(gòu)如何為應(yīng)用程序中涉及到各種各樣的數(shù)據(jù)，建立相應(yīng)的數(shù)據(jù)結(jié)構(gòu)（表、樹(shù)或圖），并依此實(shí)現(xiàn)軟件功能從廣義上講，數(shù)據(jù)結(jié)構(gòu)描述現(xiàn)實(shí)世界實(shí)體的數(shù)學(xué)模型及其上的操作在計(jì)算機(jī)中的表示和實(shí)現(xiàn)第１章數(shù)據(jù)結(jié)構(gòu)緒論八、數(shù)據(jù)結(jié)構(gòu)要解決的問(wèn)題18第一節(jié)數(shù)據(jù)結(jié)構(gòu)如何為應(yīng)用程序中一、邏輯結(jié)構(gòu)19第二節(jié)數(shù)據(jù)的結(jié)構(gòu)邏輯結(jié)構(gòu)描述數(shù)據(jù)元素之間的關(guān)系線性結(jié)構(gòu)線性表（表，棧，隊(duì)列，串等）非線性結(jié)構(gòu)樹(shù)（二叉樹(shù)，Huffman樹(shù)，二叉排序樹(shù)等）圖（有向圖，無(wú)向圖等）第１章數(shù)據(jù)結(jié)構(gòu)緒論456231123456123456一、邏輯結(jié)構(gòu)19第二節(jié)數(shù)據(jù)的結(jié)構(gòu)邏輯結(jié)構(gòu)描述數(shù)據(jù)元素之間的二、物理結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)）20第二節(jié)數(shù)據(jù)的結(jié)構(gòu)物理結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示（或映象）順序存儲(chǔ)表示（可以用C語(yǔ)言中一維數(shù)組表示）鏈接存儲(chǔ)表示（可以用C語(yǔ)言中的指針表示）索引存儲(chǔ)表示散列存儲(chǔ)表示第１章數(shù)據(jù)結(jié)構(gòu)緒論二、物理結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)）20第二節(jié)數(shù)據(jù)的結(jié)構(gòu)物理結(jié)構(gòu)是數(shù)據(jù)二、物理結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)）21第二節(jié)數(shù)據(jù)的結(jié)構(gòu)復(fù)數(shù)存儲(chǔ)結(jié)構(gòu)舉例第１章數(shù)據(jù)結(jié)構(gòu)緒論z1=3.0

-2.3i指針或鏈(地址)

…041506110613……-2.33.00415z1=3.0

-2.3i

z2=-0.7+4.8i…0300030206320634……3.0-2.3-0.74.8順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二、物理結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)）21第二節(jié)數(shù)據(jù)的結(jié)構(gòu)復(fù)數(shù)存儲(chǔ)結(jié)構(gòu)舉一、數(shù)據(jù)類(lèi)型22第三節(jié)數(shù)據(jù)類(lèi)型數(shù)據(jù)類(lèi)型是一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱(chēng)如C語(yǔ)言中的整型變量(int)，其值集為某個(gè)區(qū)間上的整數(shù)，定義在其上的操作為+,-,x,/等第１章數(shù)據(jù)結(jié)構(gòu)緒論一、數(shù)據(jù)類(lèi)型22第三節(jié)數(shù)據(jù)類(lèi)型數(shù)據(jù)類(lèi)型是一個(gè)值的集合和定義二、原子數(shù)據(jù)類(lèi)型和結(jié)構(gòu)數(shù)據(jù)類(lèi)型23第三節(jié)數(shù)據(jù)類(lèi)型1.原子數(shù)據(jù)類(lèi)型是不可分解的數(shù)據(jù)類(lèi)型如C語(yǔ)言中的整型(int)，實(shí)型(float)，字符型(char)，指針類(lèi)型(*)和空類(lèi)型(void)等第１章數(shù)據(jù)結(jié)構(gòu)緒論二、原子數(shù)據(jù)類(lèi)型和結(jié)構(gòu)數(shù)據(jù)類(lèi)型23第三節(jié)數(shù)據(jù)類(lèi)型1.原子二、原子數(shù)據(jù)類(lèi)型和結(jié)構(gòu)數(shù)據(jù)類(lèi)型24第三節(jié)數(shù)據(jù)類(lèi)型2.結(jié)構(gòu)數(shù)據(jù)類(lèi)型由若干成分（原子類(lèi)型或結(jié)構(gòu)類(lèi)型）按某種結(jié)構(gòu)組成的數(shù)據(jù)類(lèi)型結(jié)構(gòu)數(shù)據(jù)類(lèi)型可以看作是一種數(shù)據(jù)結(jié)構(gòu)和定義在其上的一組操作組成的整體如數(shù)組，由若干分量組成，每個(gè)分量可以是整數(shù)，也可以是數(shù)組（如intA[10]）第１章數(shù)據(jù)結(jié)構(gòu)緒論二、原子數(shù)據(jù)類(lèi)型和結(jié)構(gòu)數(shù)據(jù)類(lèi)型24第三節(jié)數(shù)據(jù)類(lèi)型2.結(jié)構(gòu)三、抽象數(shù)據(jù)類(lèi)型（AbstractDataType）25第三節(jié)數(shù)據(jù)類(lèi)型由用戶定義，用以表示應(yīng)用問(wèn)題的數(shù)據(jù)模型由基本的數(shù)據(jù)類(lèi)型組成,并包括一組相關(guān)的服務(wù)（或稱(chēng)操作）信息隱蔽和數(shù)據(jù)封裝，使用與實(shí)現(xiàn)相分離第１章數(shù)據(jù)結(jié)構(gòu)緒論三、抽象數(shù)據(jù)類(lèi)型（AbstractDataType）25三、抽象數(shù)據(jù)類(lèi)型（ADT）26第三節(jié)數(shù)據(jù)類(lèi)型抽象數(shù)據(jù)類(lèi)型（ADT）是一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作抽象數(shù)據(jù)類(lèi)型=數(shù)據(jù)結(jié)構(gòu)+定義在此數(shù)據(jù)結(jié)構(gòu)上的一組操作第１章數(shù)據(jù)結(jié)構(gòu)緒論三、抽象數(shù)據(jù)類(lèi)型（ADT）26第三節(jié)數(shù)據(jù)類(lèi)型抽象數(shù)據(jù)類(lèi)型（三、抽象數(shù)據(jù)類(lèi)型（ADT表示）27第三節(jié)數(shù)據(jù)類(lèi)型抽象數(shù)據(jù)類(lèi)型可用（D，S，P）三元組表示D是數(shù)據(jù)對(duì)象S是D上的關(guān)系集P是對(duì)D的基本操作集。第１章數(shù)據(jù)結(jié)構(gòu)緒論三、抽象數(shù)據(jù)類(lèi)型（ADT表示）27第三節(jié)數(shù)據(jù)類(lèi)型抽象數(shù)據(jù)類(lèi)三、抽象數(shù)據(jù)類(lèi)型（ADT定義）28第三節(jié)數(shù)據(jù)類(lèi)型ADT抽象數(shù)據(jù)類(lèi)型名{ 數(shù)據(jù)對(duì)象：〈數(shù)據(jù)對(duì)象的定義〉 數(shù)據(jù)關(guān)系：〈數(shù)據(jù)關(guān)系的定義〉 基本操作：〈基本操作(函數(shù))的定義〉 }ADT抽象數(shù)據(jù)類(lèi)型名第１章數(shù)據(jù)結(jié)構(gòu)緒論三、抽象數(shù)據(jù)類(lèi)型（ADT定義）28第三節(jié)數(shù)據(jù)類(lèi)型ADT抽三、抽象數(shù)據(jù)類(lèi)型（ADT定義舉例）29第三節(jié)數(shù)據(jù)類(lèi)型ADTTriplet{ 數(shù)據(jù)對(duì)象：D={e1,e2,e3|e1,e2,e3∈ElemSet} 數(shù)據(jù)關(guān)系：R={<e1,e2>,<e2,e3>} 基本操作：Max(T,&e)初始條件：三元組T已存在。

操作結(jié)果：用e返回T的3個(gè)元素中的最大值。Min(T,&e)初始條件：三元組T已存在。

操作結(jié)果：用e返回T的3個(gè)元素中的最小值。

}ADTTriplet第１章數(shù)據(jù)結(jié)構(gòu)緒論三、抽象數(shù)據(jù)類(lèi)型（ADT定義舉例）29第三節(jié)數(shù)據(jù)類(lèi)型ADT三、抽象數(shù)據(jù)類(lèi)型（ADT定義實(shí)現(xiàn)）30第三節(jié)數(shù)據(jù)類(lèi)型抽象數(shù)據(jù)類(lèi)型可以通過(guò)固有數(shù)據(jù)類(lèi)型(C語(yǔ)言中已實(shí)現(xiàn)的數(shù)據(jù)類(lèi)型)來(lái)實(shí)現(xiàn)抽象數(shù)據(jù)類(lèi)型類(lèi)class數(shù)據(jù)對(duì)象數(shù)據(jù)成員基本操作成員函數(shù)(方法)第１章數(shù)據(jù)結(jié)構(gòu)緒論三、抽象數(shù)據(jù)類(lèi)型（ADT定義實(shí)現(xiàn)）30第三節(jié)數(shù)據(jù)類(lèi)型抽象數(shù)一、算法（Algorithm）31第四節(jié)算法分析算法是對(duì)特定問(wèn)題求解步驟的一種描述是一有限長(zhǎng)的操作序列第１章數(shù)據(jù)結(jié)構(gòu)緒論一、算法（Algorithm）31第四節(jié)算法分析算法是對(duì)特一、算法（特性）32第四節(jié)算法分析有窮性：算法在執(zhí)行有窮步后能結(jié)束確定性：每步定義都是確切、無(wú)歧義可行性：每一條運(yùn)算應(yīng)足夠基本(已驗(yàn)算正確)輸入：有0個(gè)或多個(gè)輸入輸出：有一個(gè)或多個(gè)輸出第１章數(shù)據(jù)結(jié)構(gòu)緒論一、算法（特性）32第四節(jié)算法分析有窮性：算法在執(zhí)行有窮步一、算法（舉例）33第四節(jié)算法分析例子：選擇排序問(wèn)題：遞增排序解決方案：逐個(gè)選擇最小數(shù)據(jù)算法框架：

for(inti=0;i<n-1;i++){//n-1趟 從a[i]檢查到a[n-1]，找到最小數(shù); 若最小整數(shù)在a[k],交換a[i]與a[k]; }第１章數(shù)據(jù)結(jié)構(gòu)緒論一、算法（舉例）33第四節(jié)算法分析例子：選擇排序第１章數(shù)二、算法設(shè)計(jì)的要求34第四節(jié)算法分析正確性：滿足具體問(wèn)題的需求可讀性：便于理解和修改健壯性：當(dāng)輸入數(shù)據(jù)非法時(shí)，也能適當(dāng)反應(yīng)效率高：執(zhí)行時(shí)間少空間省：執(zhí)行中需要的最大存儲(chǔ)空間第１章數(shù)據(jù)結(jié)構(gòu)緒論二、算法設(shè)計(jì)的要求34第四節(jié)算法分析正確性：滿足具體問(wèn)題的三、時(shí)間復(fù)雜度35第四節(jié)算法分析衡量算法的效率，主要依據(jù)算法執(zhí)行所需要的時(shí)間，即時(shí)間復(fù)雜度事后統(tǒng)計(jì)法：計(jì)算算法開(kāi)始時(shí)間與完成時(shí)間差值事前統(tǒng)計(jì)法：依據(jù)算法選用何種策略及問(wèn)題的規(guī)模n，是常用的方法第１章數(shù)據(jù)結(jié)構(gòu)緒論三、時(shí)間復(fù)雜度35第四節(jié)算法分析衡量算法的效率，主要依據(jù)算三、時(shí)間復(fù)雜度36第四節(jié)算法分析時(shí)間復(fù)雜度是問(wèn)題規(guī)模n的函數(shù)f(n)，即：

T(n)=O(f(n))一般地，時(shí)間復(fù)雜度用算法中最深層循環(huán)內(nèi)的語(yǔ)句中的原操作的重復(fù)執(zhí)行次數(shù)表示第１章數(shù)據(jù)結(jié)構(gòu)緒論三、時(shí)間復(fù)雜度36第四節(jié)算法分析時(shí)間復(fù)雜度是問(wèn)題規(guī)模n的函三、時(shí)間復(fù)雜度37第四節(jié)算法分析a.{y*=x;}b.for(i=1;i<=n;i++}{y*=x;}c.for(j=1;j<=n;j++}for(i=1;i<=n;i++}{y*=x;}a,b,c三個(gè)算法中，“y*=x;”程序段的時(shí)間復(fù)雜度分別為O(1),O(n),O(n2)，分別稱(chēng)為常量階，線性階，平方階第１章數(shù)據(jù)結(jié)構(gòu)緒論三、時(shí)間復(fù)雜度37第四節(jié)算法分析a.{y*=x;}第三、時(shí)間復(fù)雜度38第四節(jié)算法分析時(shí)間復(fù)雜度除常量階[O(1)],

線性階[O(n)],平方階[O(n2)]外，還有對(duì)數(shù)階[O(logn)]，排列階[O(n!)]，指數(shù)階[O(2n)]等，是相對(duì)于問(wèn)題規(guī)模n的增長(zhǎng)率的表示方法指數(shù)階隨問(wèn)題規(guī)模增長(zhǎng)過(guò)快，一般不宜使用第１章數(shù)據(jù)結(jié)構(gòu)緒論三、時(shí)間復(fù)雜度38第四節(jié)算法分析時(shí)間復(fù)雜度除常量階[O(1三、時(shí)間復(fù)雜度39第四節(jié)算法分析如果算法的執(zhí)行有多種可能的操作順序，則求其平均時(shí)間復(fù)雜度如果無(wú)法求取平均時(shí)間復(fù)雜度，則采用最壞情況下的時(shí)間復(fù)雜度時(shí)間復(fù)雜度是衡量算法好壞的一個(gè)最重要的標(biāo)準(zhǔn)第１章數(shù)據(jù)結(jié)構(gòu)緒論三、時(shí)間復(fù)雜度39第四節(jié)算法分析如果算法的執(zhí)行有多種可能的四、空間復(fù)雜度40第四節(jié)算法分析空間復(fù)雜度指算法執(zhí)行時(shí)，所需要存儲(chǔ)空間的量度，它也是問(wèn)題規(guī)模的函數(shù)，即：

S(n)=O(f(n))第１章數(shù)據(jù)結(jié)構(gòu)緒論四、空間復(fù)雜度40第四節(jié)算法分析空間復(fù)雜度指算法執(zhí)行時(shí)，所第二章

線性表數(shù)據(jù)結(jié)構(gòu)深圳大學(xué)計(jì)算機(jī)系

蔡茂國(guó)第二章

線性表數(shù)據(jù)結(jié)構(gòu)一、線性數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)42第一節(jié)線性表在數(shù)據(jù)元素的非空有限集中１、存在惟一的一個(gè)被稱(chēng)作“第一個(gè)”的數(shù)據(jù)元素(如“１”)２、存在惟一的一個(gè)被稱(chēng)作“最后一個(gè)”的數(shù)據(jù)元素(如“６”)３、除第一個(gè)元素外，每個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū)４、除最后一個(gè)元素外，每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼(next)(如“1”的next是“2”,“2”的next是“3”)第２章線性表123456一、線性數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)42第一節(jié)線性表在數(shù)據(jù)元素的非空有限二、線性表43第一節(jié)線性表線性表是最簡(jiǎn)單的一類(lèi)線性數(shù)據(jù)結(jié)構(gòu)線性表是由n個(gè)數(shù)據(jù)元素組成的有限序列，相鄰數(shù)據(jù)元素之間存在著序偶關(guān)系，可以寫(xiě)為：(a1,a2,…ai-1,ai,ai+1,…an-1,an)其中,ai是表中元素,i表示元素ai的位置,n是表的長(zhǎng)度第２章線性表二、線性表43第一節(jié)線性表線性表是最簡(jiǎn)單的一類(lèi)線性數(shù)據(jù)結(jié)構(gòu)二、線性表44第一節(jié)線性表線性表中的元素具有相同的特性，屬于同一數(shù)據(jù)對(duì)象，如：1.26個(gè)字母的字母表:(A,B,C,D,…,Z)2.近期每天的平均溫度:(30℃,28℃,29℃,…)第２章線性表二、線性表44第一節(jié)線性表線性表中的元素具有相同的特性，屬一、順序表45第二節(jié)順序表順序表是線性表的順序表示用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素第２章線性表ABCDE…YZ

bb+1b+2b+3b+4…b+24b+25一、順序表45第二節(jié)順序表順序表是線性表的順序表示第２章一、順序表（元素位置）46第二節(jié)順序表順序表數(shù)據(jù)元素的位置：LOC(ai)=LOC(ai-1)+lLOC(ai)=LOC(a1)+(i-1)*l

l表示元素占用的內(nèi)存單元數(shù)第２章線性表a1

a2

…ai………an

12…i………n

bb+l…b+(i-1)*l………b+(n-1)*lidle一、順序表（元素位置）46第二節(jié)順序表順序表數(shù)據(jù)元素的位置二、順序表的定義47第二節(jié)順序表采用C語(yǔ)言中動(dòng)態(tài)分配的一維數(shù)組表示順序表第２章線性表#defineLIST_INIT_SIZE100 //線性表存儲(chǔ)空間的初始分配量#defineLISTINCREMENT10 //線性表存儲(chǔ)空間的分配增量Typedefstruct{ ElemType *elem; //存儲(chǔ)空間基址 int length; //當(dāng)前長(zhǎng)度 int listsize; //當(dāng)前分配的存儲(chǔ)容量(元素?cái)?shù))}Sqlist;二、順序表的定義47第二節(jié)順序表采用C語(yǔ)言中動(dòng)態(tài)分配的一維三、順序表的初始化48第二節(jié)順序表創(chuàng)建一個(gè)順序表L第２章線性表StatusInitList_Sq(Sqlist&L){ L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L.elem)exit(OVERFLOW); //存儲(chǔ)分配失敗 L.length=0; //空表長(zhǎng)度為0 L.listsize=LIST_INIT_SIZE; //初始存儲(chǔ)容量 returnOK;}//InitList_Sq三、順序表的初始化48第二節(jié)順序表創(chuàng)建一個(gè)順序表L第２章三、順序表的插入49第二節(jié)順序表順序表的插入操作是指在順序表的第i-1個(gè)數(shù)據(jù)元素和第i個(gè)數(shù)據(jù)元素之間插入一個(gè)新的數(shù)據(jù)元素，即將長(zhǎng)度為n的順序表：(a1,…ai-1,ai,…,an)

變成長(zhǎng)度為n+1的順序表：(a1,…ai-1,e,ai,…,an)第２章線性表三、順序表的插入49第二節(jié)順序表順序表的插入操作是指在順序三、順序表的插入50第二節(jié)順序表在第3個(gè)元素與第4個(gè)元素之間插入新元素b需要將最后元素n至第4元素(共7-4+1)都向后移一位置第２章線性表253457164809630123456725345750164809635050插入ei=401234567三、順序表的插入50第二節(jié)順序表在第3個(gè)元素與第4個(gè)元素之三、順序表的插入51第二節(jié)順序表第２章線性表StatusListInsert_Sq(Sqlist&L,inti,ElemTypee){if(i<1||i>L.length+1)returnERROR;if(L.length>=L.listsize){newbase=realloc(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCRMENT;} //以上皆為準(zhǔn)備階段q=&(L.elem[i-1]); //找到插入位置for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p; //右移*q=e;++L.length;returnOK;}//ListInsert_Sq //請(qǐng)注意元素位置數(shù)值較元素序號(hào)少1三、順序表的插入51第二節(jié)順序表第２章線性表Status三、順序表的插入52第二節(jié)順序表在順序表中插入一個(gè)元素，需要向后移動(dòng)元素個(gè)數(shù)為：n-i+1平均移動(dòng)元素?cái)?shù)為：n+1Eis=∑pix(n-i+1)i=1第２章線性表三、順序表的插入52第二節(jié)順序表在順序表中插入一個(gè)元素，需三、順序表的插入53第二節(jié)順序表當(dāng)插入位置等概率時(shí)，pi=1/(n+1)，因此：n+1Eis=∑[1/(n+1)]x(n-i+1)=n/2i=1順序表插入操作的時(shí)間復(fù)雜度為O(n)第２章線性表三、順序表的插入53第二節(jié)順序表當(dāng)插入位置等概率時(shí)，pi=四、順序表的刪除54第二節(jié)順序表順序表的刪除操作是指將順序表的第i個(gè)數(shù)據(jù)元素刪除，即將長(zhǎng)度為n的順序表：(a1,…ai-1,ai,ai+1,…,an)

變成長(zhǎng)度為n-1的順序表：(a1,…ai-1,ai+1,…,an)第２章線性表四、順序表的刪除54第二節(jié)順序表順序表的刪除操作是指將順序四、順序表的刪除55第二節(jié)順序表將第4個(gè)元素刪除需要將最后元素n至第5元素(共7-4)都向前移一位置第２章線性表2534574809630123456725345748096316刪除16i=401234567四、順序表的刪除55第二節(jié)順序表將第4個(gè)元素刪除第２章線四、順序表的刪除56第二節(jié)順序表第２章線性表StatusListDelete_Sq(Sqlist&L,inti,ElemTypee){if(i<1||i>L.length)returnERROR;p=&(L.elem[i-1]); //找到要?jiǎng)h除的元素位置e=*p;q=L.elem+L.length–1; //找到最后一個(gè)元素位置for(++p;p<=q;++p)*(p-1)=*p; //左移--L.length; //表長(zhǎng)減1returnOK;}//ListDelete_Sq四、順序表的刪除56第二節(jié)順序表第２章線性表Status四、順序表的刪除57第二節(jié)順序表在順序表中刪除一個(gè)元素，需要向前移動(dòng)元素個(gè)數(shù)為：n-i平均移動(dòng)元素?cái)?shù)為：nEdl=∑qix(n-i)i=1第２章線性表四、順序表的刪除57第二節(jié)順序表在順序表中刪除一個(gè)元素，需四、順序表的刪除58第二節(jié)順序表當(dāng)插入位置等概率時(shí)，qi=1/n，因此：nEdl=∑[1/n]x(n-i)=(n-1)/2i=1順序表刪除操作的時(shí)間復(fù)雜度為O(n)第２章線性表四、順序表的刪除58第二節(jié)順序表當(dāng)插入位置等概率時(shí)，qi=五、順序表的優(yōu)缺點(diǎn)59第三節(jié)鏈表

優(yōu)點(diǎn)：元素可以隨機(jī)存取元素位置可用一個(gè)簡(jiǎn)單、直觀的公式表示并求取

缺點(diǎn)：在作插入或刪除操作時(shí)，需要移動(dòng)大量元素第２章線性表五、順序表的優(yōu)缺點(diǎn)59第三節(jié)鏈表優(yōu)點(diǎn)：第２章線性表一、鏈表60第二節(jié)線性鏈表鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)表示鏈表中邏輯關(guān)系相鄰的元素不一定在存儲(chǔ)位置上相連，用一個(gè)鏈(指針)表示元素之間的鄰接關(guān)系線性表的鏈?zhǔn)酱鎯?chǔ)表示主要有三種形式：線性鏈表循環(huán)鏈表雙向鏈表第２章線性表一、鏈表60第二節(jié)線性鏈表鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)表示第２章二、線性鏈表61第二節(jié)線性鏈表線性鏈表的元素稱(chēng)為結(jié)點(diǎn)(node)結(jié)點(diǎn)除包含數(shù)據(jù)元素信息的數(shù)據(jù)域外，還包含指示直接后繼的指針域每個(gè)結(jié)點(diǎn)，在需要時(shí)動(dòng)態(tài)生成，在刪除時(shí)釋放第２章線性表datanext二、線性鏈表61第二節(jié)線性鏈表線性鏈表的元素稱(chēng)為結(jié)點(diǎn)(no二、線性鏈表62第二節(jié)線性鏈表動(dòng)態(tài)單獨(dú)生成結(jié)點(diǎn)的線性鏈表也稱(chēng)單鏈表線性鏈表可由頭指針惟一確定為了操作方便，有時(shí)在線性鏈表的第一個(gè)結(jié)點(diǎn)之前附設(shè)一個(gè)頭結(jié)點(diǎn)，其數(shù)據(jù)域可以為空，也可以為線性鏈表的長(zhǎng)度信息。第２章線性表4a1a2a3a4L二、線性鏈表62第二節(jié)線性鏈表動(dòng)態(tài)單獨(dú)生成結(jié)點(diǎn)的線性鏈表也三、線性鏈表的定義63第二節(jié)線性鏈表定義一個(gè)結(jié)點(diǎn)typedefstructLNode{ ElemType data; //數(shù)據(jù)域 structLNode *next; //后繼指針}LNode,*LinkList;第２章線性表datanext三、線性鏈表的定義63第二節(jié)線性鏈表定義一個(gè)結(jié)點(diǎn)第２章線四、找指定元素64第二節(jié)線性鏈表在線性鏈表中找第i個(gè)元素由于線性鏈表中元素的存儲(chǔ)位置具有隨機(jī)性，因此，只有從頭結(jié)點(diǎn)開(kāi)始，順鏈一步步查找第２章線性表na1aianL……四、找指定元素64第二節(jié)線性鏈表在線性鏈表中找第i個(gè)元素第四、找指定元素65第二節(jié)線性鏈表StatusGetElem_L(LinkList&L,inti,ElemType&e){ //L為帶頭結(jié)點(diǎn)的單鏈表的頭指針，e為返回值

p=L->next;j=1; //p指向第一個(gè)結(jié)點(diǎn) while(p&&j<i){p=p->next;j++;} //順指針查指 if(!p||j>i)returnERROR; //第i元素不存在 e=p->data; //取第i元素值 returnOK;}//GetElem_L第２章線性表na1aianL……四、找指定元素65第二節(jié)線性鏈表StatusGetEle四、找指定元素66第二節(jié)線性鏈表算法時(shí)間復(fù)雜度主要取決于while循環(huán)中的語(yǔ)句頻度頻度與被查找元素在單鏈表中的位置有關(guān)若1≤i≤n，則頻度為i-1，否則為n因此時(shí)間復(fù)雜度為O(n)第２章線性表na1aianL……四、找指定元素66第二節(jié)線性鏈表算法時(shí)間復(fù)雜度主要取決于w五、線性鏈表的插入67第二節(jié)線性鏈表在線性鏈表的第i-1元素與第i元素之間插入一個(gè)新元素第２章線性表ai-1ais……e插入前p…ai-1ais…e插入后ps->next=p->next;p->next=s;五、線性鏈表的插入67第二節(jié)線性鏈表在線性鏈表的第i-1元五、線性鏈表的插入68第二節(jié)線性鏈表StatusListInsert_L(LinkList&L,inti,ElemTypee){ //在帶頭結(jié)點(diǎn)的單鏈表L中第i個(gè)位置之前插入元素e p=L;j=0; while(p&&j<i-1){p=p->next;j++;} //尋找i-1結(jié)點(diǎn) if(!p||j>i-1)returnERROR; s=(LinkList)malloc(sizeof(LNode); //生成新結(jié)點(diǎn) s->data=e;s->next=p->next;p->next=s; //插入L中 returnOK;}//ListInsert_L第２章線性表五、線性鏈表的插入68第二節(jié)線性鏈表StatusList五、線性鏈表的插入69第二節(jié)線性鏈表同樣，算法時(shí)間復(fù)雜度主要取決于while循環(huán)中的語(yǔ)句頻度頻度與在線性鏈表中的元素插入位置有關(guān)因此線性鏈表插入的時(shí)間復(fù)雜度為O(n)第２章線性表五、線性鏈表的插入69第二節(jié)線性鏈表同樣，算法時(shí)間復(fù)雜度主六、線性鏈表的刪除70第二節(jié)線性鏈表將線性鏈表的第i元素刪除第２章線性表pai-1ai+1ai刪除前ai-1aiai+1pq刪除后p->next=p->next->next六、線性鏈表的刪除70第二節(jié)線性鏈表將線性鏈表的第i元素刪六、線性鏈表的刪除71第二節(jié)線性鏈表StatusListDelete_L(LinkList&L,inti,ElemType&e){ //在帶頭結(jié)點(diǎn)的單鏈表L中，刪除第i個(gè)位置的元素 p=L;j=0; while(p->next&&j<i-1){p=p->next;j++;} //尋找i結(jié)點(diǎn) if(!p->next||j>i-1)returnERROR; q=p->next;p->next=q->next; //刪除i結(jié)點(diǎn)

e=q->data;free(q); //取值并釋放結(jié)點(diǎn) returnOK;}//ListDelete_L第２章線性表六、線性鏈表的刪除71第二節(jié)線性鏈表StatusList六、線性鏈表的刪除72第二節(jié)線性鏈表同樣，算法時(shí)間復(fù)雜度主要取決于while循環(huán)中的語(yǔ)句頻度頻度與被刪除元素在線性鏈表中的位置有關(guān)因此線性鏈表刪除元素的時(shí)間復(fù)雜度為O(n)第２章線性表六、線性鏈表的刪除72第二節(jié)線性鏈表同樣，算法時(shí)間復(fù)雜度主七、靜態(tài)鏈表73第二節(jié)線性鏈表線性鏈表也可以采用靜態(tài)數(shù)組實(shí)現(xiàn)與順序表有兩點(diǎn)不同：１、每個(gè)元素包括數(shù)據(jù)域和指針域２、元素的邏輯關(guān)系由指針確定第２章線性表DCFBAE…7592^83610411012345678910…數(shù)據(jù)指針七、靜態(tài)鏈表73第二節(jié)線性鏈表線性鏈表也可以采用靜態(tài)數(shù)組實(shí)七、靜態(tài)鏈表74第二節(jié)線性鏈表與單鏈表區(qū)別：１、靜態(tài)鏈表暫時(shí)不用結(jié)點(diǎn)，鏈成一個(gè)備用鏈表２、插入時(shí)，從備用鏈表中申請(qǐng)結(jié)點(diǎn)３、刪除結(jié)點(diǎn)時(shí)，將結(jié)點(diǎn)放入備用鏈表第２章線性表七、靜態(tài)鏈表74第二節(jié)線性鏈表與單鏈表區(qū)別：第２章線性表一、循環(huán)鏈表75第三節(jié)循環(huán)鏈表循環(huán)鏈表是一種特殊的線性鏈表循環(huán)鏈表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)。第２章線性表na1aianL……一、循環(huán)鏈表75第三節(jié)循環(huán)鏈表循環(huán)鏈表是一種特殊的線性鏈表二、查找、插入和刪除76第三節(jié)循環(huán)鏈表在循環(huán)鏈表中查找指定元素，插入一個(gè)結(jié)點(diǎn)或刪除一個(gè)結(jié)點(diǎn)的操作與線性鏈表基本一致差別僅在于算法中的循環(huán)條件不是p->next或p是否為空(^)，而是它們是否等于頭指針(L)第２章線性表na1aianL……二、查找、插入和刪除76第三節(jié)循環(huán)鏈表在循環(huán)鏈表中查找指定一、雙向鏈表77第四節(jié)雙向鏈表雙向鏈表也是一種特殊的線性鏈表雙向鏈表中每個(gè)結(jié)點(diǎn)有兩個(gè)指針，一個(gè)指針指向直接后繼(next)，另一個(gè)指向直接前驅(qū)(prior)第２章線性表priordatanext指向直接前驅(qū)指向直接后繼一、雙向鏈表77第四節(jié)雙向鏈表雙向鏈表也是一種特殊的線性鏈二、雙向循環(huán)鏈表78第四節(jié)雙向鏈表雙向循環(huán)鏈表中存在兩個(gè)環(huán)(一個(gè)是直接后繼環(huán)(紅)，另一個(gè)是直接前驅(qū)環(huán)(藍(lán)))第２章線性表非空表空表LL二、雙向循環(huán)鏈表78第四節(jié)雙向鏈表雙向循環(huán)鏈表中存在兩個(gè)環(huán)三、雙向鏈表的定義79第四節(jié)雙向鏈表定義一個(gè)雙向鏈表的結(jié)點(diǎn)TypedefstructDuLNode{ ElemType data; structDuLNode *prior; structDuLNode *next;}DuLNode,*DuLinkList;第２章線性表priordatanext指向直接前驅(qū)指向直接后繼對(duì)于任何一個(gè)中間結(jié)點(diǎn)有：p=p->next->priorp=p->prior->next三、雙向鏈表的定義79第四節(jié)雙向鏈表定義一個(gè)雙向鏈表的結(jié)點(diǎn)四、雙向鏈表的插入80第四節(jié)雙向鏈表雙向鏈表的插入操作需要改變兩個(gè)方向的指針第２章線性表L314815pL31482515pss->next=p;s->prior=p->prior;p->prior->next=s;p->prior=s;四、雙向鏈表的插入80第四節(jié)雙向鏈表雙向鏈表的插入操作需要四、雙向鏈表的刪除81第四節(jié)雙向鏈表雙向鏈表的刪除操作需要改變兩個(gè)方向的指針第２章線性表L314815pL3115p->prior->next=p->next;p->next->prior=p->prior;四、雙向鏈表的刪除81第四節(jié)雙向鏈表雙向鏈表的刪除操作需要一、基于空間的比較82第五節(jié)順序表與鏈表的比較存儲(chǔ)分配的方式順序表的存儲(chǔ)空間是靜態(tài)分配的鏈表的存儲(chǔ)空間是動(dòng)態(tài)分配的存儲(chǔ)密度=結(jié)點(diǎn)數(shù)據(jù)本身所占的存儲(chǔ)量/結(jié)點(diǎn)結(jié)構(gòu)所占的存儲(chǔ)總量順序表的存儲(chǔ)密度=1鏈表的存儲(chǔ)密度<1第２章線性表一、基于空間的比較82第五節(jié)順序表與鏈表的比較存儲(chǔ)分配的方二、基于時(shí)間的比較83第五節(jié)順序表與鏈表的比較存取方式順序表可以隨機(jī)存取，也可以順序存取鏈表必須順序存取插入/刪除時(shí)移動(dòng)元素個(gè)數(shù)順序表平均需要移動(dòng)近一半元素鏈表不需要移動(dòng)元素，只需要修改指針第２章線性表二、基于時(shí)間的比較83第五節(jié)順序表與鏈表的比較存取方式第２三、基于應(yīng)用的比較84第五節(jié)順序表與鏈表的比較如果線性表主要是存儲(chǔ)大量的數(shù)據(jù)，并主要用于查找時(shí)，采用順序表較好，如數(shù)據(jù)庫(kù)如果線性表存儲(chǔ)的數(shù)據(jù)元素經(jīng)常需要做插入與刪除操作，則采用鏈表較好，如操作系統(tǒng)中進(jìn)程控制塊(PCB)的管理，內(nèi)存空間的管理等第２章線性表三、基于應(yīng)用的比較84第五節(jié)順序表與鏈表的比較如果線性表主第三章

棧和隊(duì)列數(shù)據(jù)結(jié)構(gòu)深圳大學(xué)計(jì)算機(jī)系

蔡茂國(guó)第三章

棧和隊(duì)列數(shù)據(jù)結(jié)構(gòu)一、棧86第一節(jié)棧棧是限定僅在表尾(top)進(jìn)行插入或刪除操作的線性表。允許插入和刪除的一端稱(chēng)為棧頂(top，表尾)，另一端稱(chēng)為棧底(bottom，表頭)特點(diǎn)：后進(jìn)先出(LIFO)第３章棧和隊(duì)列a1topbottoman...進(jìn)棧出棧一、棧86第一節(jié)棧棧是限定僅在表尾(top)進(jìn)行插入或刪除二、棧的實(shí)現(xiàn)87第一節(jié)棧棧的存儲(chǔ)結(jié)構(gòu)主要有兩種：1.順序棧2.鏈?zhǔn)綏５冢痴聴：完?duì)列a1topbasean...進(jìn)棧出棧top

^datanext…棧底棧頂二、棧的實(shí)現(xiàn)87第一節(jié)棧棧的存儲(chǔ)結(jié)構(gòu)主要有兩種：第３章棧一、順序棧88第二節(jié)順序棧順序棧是棧的順序存儲(chǔ)結(jié)構(gòu)利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素指針top指向棧頂元素在順序棧中的下一個(gè)位置，base為棧底指針，指向棧底的位置。第３章棧和隊(duì)列a1topbasean...進(jìn)棧出棧一、順序棧88第二節(jié)順序棧順序棧是棧的順序存儲(chǔ)結(jié)構(gòu)第３章二、順序棧的定義89第二節(jié)順表?xiàng)２捎肅語(yǔ)言中動(dòng)態(tài)分配的一維數(shù)組表示順序表第３章棧和隊(duì)列#defineSTACK_INIT_SIZE100 //棧存儲(chǔ)空間的初始分配量#defineSTACKINCREMENT10 //棧存儲(chǔ)空間的分配增量Typedefstruct{ SElemType *base //存儲(chǔ)空間基址 SElemType *top; //當(dāng)前長(zhǎng)度 int stacksize; //當(dāng)前分配的存儲(chǔ)容量(元素?cái)?shù))}SqStack;二、順序棧的定義89第二節(jié)順表?xiàng)２捎肅語(yǔ)言中動(dòng)態(tài)分配的一維三、順序棧的特性90第二節(jié)順序棧top=0或top=base表示空棧base=NULL表示棧不存在當(dāng)插入新的棧頂元素時(shí),指針top+1刪除棧頂元素時(shí)，指針top-1當(dāng)top>stacksize時(shí)，棧滿，溢出第３章棧和隊(duì)列a1topbasean...進(jìn)棧出棧三、順序棧的特性90第二節(jié)順序棧top=0或top=b四、順序棧的主要操作91第二節(jié)順序棧第３章棧和隊(duì)列ADTStack{ 數(shù)據(jù)對(duì)象：D={ai|ai∈ElemSet,i=1,2,3,…,n} 數(shù)據(jù)關(guān)系：R={<ai-1,ai>|ai-1,ai∈D} 基本操作：InitStack(&S) //構(gòu)造空棧

Push(&S,e) //進(jìn)棧

Pop(&S,&e) //出棧

GetTop(S,&e) //取棧頂元素值

StackEmpty(S) //棧是否為空

}ADTStack四、順序棧的主要操作91第二節(jié)順序棧第３章棧和隊(duì)列ADT五、創(chuàng)建順序棧92第二節(jié)順序棧第３章棧和隊(duì)列StatusInitStack(SqStack&S){

S.base=(SElemType*)malloc(STACK_INIT_SIZE* sizeof(SElemType)); if(!S.base)exit(OVERFLOW); //存儲(chǔ)分配失敗

S.top=S.base; S.stacksize=STACK_INIT_SIZE; returnOK;}//InitStacktopbase

空棧五、創(chuàng)建順序棧92第二節(jié)順序棧第３章棧和隊(duì)列Status六、進(jìn)棧（插入新元素）93第二節(jié)順序棧第３章棧和隊(duì)列StatusPush(SqStack&S,SElemTypee){ if(S.top–S.base>=S.stacksize){ //棧滿，追加存儲(chǔ)空間 S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCRMENT*sizeof(SElemType)); if(!S.base)exit(OVERFLOW);

S.top=S.base+S.stacksize; S.stacksize+=STACKINCRMENT;} *S.top++=e; returnOK;}//Pushtopbaseebae進(jìn)棧topbaseba操作前六、進(jìn)棧（插入新元素）93第二節(jié)順序棧第３章棧和隊(duì)列St七、出棧（刪除元素）94第二節(jié)順序棧第３章棧和隊(duì)列StatusPop(SqStack&S,SElemType&e){

if(S.top==S.base)returnERROR; e=*--S.top; returnOK;}//Poptopbaseebae出棧topbaseeba操作前七、出棧（刪除元素）94第二節(jié)順序棧第３章棧和隊(duì)列Sta八、取棧頂元素95第二節(jié)順序棧第３章棧和隊(duì)列StatusGetTop(SqStackS,SElemType&e){

if(S.top==S.base)returnERROR; e=*(S.top-1); returnOK;}//GetToptopbaseebae進(jìn)棧topbaseeba操作前八、取棧頂元素95第二節(jié)順序棧第３章棧和隊(duì)列Status一、數(shù)值轉(zhuǎn)換96第三節(jié)棧的應(yīng)用舉例將十進(jìn)制轉(zhuǎn)換為其它進(jìn)制(d)，其原理為：N=(N/d)*d+Nmodd例如：（1348)10=(2504)8，其運(yùn)算過(guò)程如下：

N N/8Nmod8 1348 1684 168 21 0 21 2 5 2 0 2第３章棧和隊(duì)列輸出順序計(jì)算順序一、數(shù)值轉(zhuǎn)換96第三節(jié)棧的應(yīng)用舉例將十進(jìn)制轉(zhuǎn)換為其它進(jìn)制(一、數(shù)值轉(zhuǎn)換97第三節(jié)棧的應(yīng)用舉例voidconversion(){InitStack(S); //創(chuàng)建新棧Sscanf(“%d”,N); //輸入一個(gè)十進(jìn)制數(shù)Nwhile(N){Push(S,N%8); //將余數(shù)送入棧中N=N/8; //求整除數(shù)}while(!StackEmpty(S)){ //如果棧不空Pop(S,e); //將棧中數(shù)出棧printf("%d",e);}}//conversion第３章棧和隊(duì)列一、數(shù)值轉(zhuǎn)換97第三節(jié)棧的應(yīng)用舉例voidconvers二、行編輯程序98第三節(jié)棧的應(yīng)用舉例用戶輸入一行字符允許用戶輸入出差錯(cuò)，并在發(fā)現(xiàn)有誤時(shí)，可以用退格符“#”及時(shí)更正假設(shè)從終端接受兩行字符：

whli##ilr#e（s#*s)實(shí)際有效行為：

while(*s)第３章棧和隊(duì)列二、行編輯程序98第三節(jié)棧的應(yīng)用舉例用戶輸入一行字符第３章二、行編輯程序99第三節(jié)棧的應(yīng)用舉例對(duì)用戶輸入的一行字符進(jìn)行處理，直到行結(jié)束(“\n”) ch=getchar(); //從終端輸入一個(gè)字符 while(ch!=’\n’){ switch(ch){ case’#’:Pop(S,c); break; //僅當(dāng)棧非空時(shí)退棧 default:Push(S,ch); break; //有效字符進(jìn)棧 } ch=getchar(); //從終端輸入一個(gè)字符 }

將從棧底到棧頂?shù)臈?nèi)字符傳送到調(diào)用過(guò)程的數(shù)據(jù)區(qū);第３章棧和隊(duì)列二、行編輯程序99第三節(jié)棧的應(yīng)用舉例對(duì)用戶輸入的一行字符進(jìn)三、迷宮求解100第三節(jié)棧的應(yīng)用舉例迷宮求解一般采用“窮舉法”逐一沿順時(shí)針?lè)较虿檎蚁噜弶K（一共四塊－東(右)、南(下)，西(左)、北(上)）是否可通，即該相鄰塊既是通道塊，且不在當(dāng)前路徑上用一個(gè)棧來(lái)記錄已走過(guò)的路徑第３章棧和隊(duì)列三、迷宮求解100第三節(jié)棧的應(yīng)用舉例迷宮求解一般采用“窮舉三、迷宮求解101第三節(jié)棧的應(yīng)用舉例舉例第３章棧和隊(duì)列#############三、迷宮求解101第三節(jié)棧的應(yīng)用舉例舉例第３章棧和隊(duì)列#三、迷宮求解（算法）第三節(jié)棧的應(yīng)用舉例設(shè)定當(dāng)前位置為入口位置

do{若當(dāng)前位置可通，則{

將該位置插入棧頂(Push)；若該位置是出口，則結(jié)束 否則切換當(dāng)前位置的東鄰方塊為當(dāng)前位置； }否則{ 若棧不空則｛ 如果棧頂位置的四周均不可通,則刪除棧頂位置(Pop) 并重新測(cè)試新的棧頂位置 如果找到棧頂位置的下一方向未經(jīng)探索，則將該方向 方塊設(shè)為當(dāng)前位置}}}while(棧不空)；找不到路徑；第３章棧和隊(duì)列三、迷宮求解（算法）第三節(jié)棧的應(yīng)用舉例設(shè)定當(dāng)前位置為入口位四、表達(dá)式求值103第三節(jié)棧的應(yīng)用舉例表達(dá)式由操作數(shù)、運(yùn)算符和界限符組成，它們皆稱(chēng)為單詞操作數(shù)：常數(shù)或變量運(yùn)算符：+,-,*,/等界限符：(,),#(表達(dá)式開(kāi)始及結(jié)束符)第３章棧和隊(duì)列四、表達(dá)式求值103第三節(jié)棧的應(yīng)用舉例表達(dá)式由操作數(shù)、四、表達(dá)式求值104第三節(jié)棧的應(yīng)用舉例設(shè)置兩個(gè)棧：操作數(shù)棧（OPND）運(yùn)算符棧（OPTR）第３章棧和隊(duì)列四、表達(dá)式求值104第三節(jié)棧的應(yīng)用舉例設(shè)置兩個(gè)棧：第３章四、表達(dá)式求值105第三節(jié)棧的應(yīng)用舉例運(yùn)算符的優(yōu)先級(jí)關(guān)系第３章棧和隊(duì)列+-*/()#+>><<<>>->><<<>>*>>>><>>/>>>><>>(<<<<<=出錯(cuò))>>>>出錯(cuò)>>#<<<<<出錯(cuò)=新運(yùn)算符運(yùn)算符棧頂元素四、表達(dá)式求值105第三節(jié)棧的應(yīng)用舉例運(yùn)算符的優(yōu)先級(jí)關(guān)系第四、表達(dá)式求值（算法）第三節(jié)棧的應(yīng)用舉例置運(yùn)算符棧(OPTR)和操作數(shù)棧(OPND)為空 ’#’插入OPTR棧； 取表達(dá)式第一個(gè)單詞；

while(單詞或OPTR棧頂元素不為’#’){ 若單詞是操作數(shù)，則插入OPND棧頂，且取下一個(gè)單詞 否則｛OPTR棧頂元素優(yōu)先級(jí)與新運(yùn)算符優(yōu)先級(jí)關(guān)系為： 小于，則插入OPTR棧頂，取下一單詞 等于，則刪除OPTR棧頂元素，取下一單詞 大于，則從OPND棧頂依次取出兩個(gè)操作數(shù)，用從OPTR 棧頂取出的元素進(jìn)行計(jì)算，結(jié)果插入OPND棧頂}}第３章棧和隊(duì)列從棧頂取出元素，包括取值及刪除棧頂元素兩個(gè)過(guò)程四、表達(dá)式求值（算法）第三節(jié)棧的應(yīng)用舉例置運(yùn)算符棧(OPT一、隊(duì)列107第四節(jié)隊(duì)列隊(duì)列是只允許在表的一端進(jìn)行插入，而在另一端刪除元素的線性表。在隊(duì)列中，允許插入的一端叫隊(duì)尾（rear），允許刪除的一端稱(chēng)為對(duì)頭(front)。特點(diǎn)：先進(jìn)先出(FIFO)第３章棧和隊(duì)列a1

a2

a3

an出隊(duì)入隊(duì)隊(duì)頭隊(duì)尾一、隊(duì)列107第四節(jié)隊(duì)列隊(duì)列是只允許在表的一端進(jìn)行插入，而二、順序隊(duì)列108第四節(jié)隊(duì)列順序隊(duì)列：采用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)從隊(duì)列頭到隊(duì)列尾的元素順序隊(duì)列有兩個(gè)指針：隊(duì)頭指針front和隊(duì)尾指針rear第３章棧和隊(duì)列二、順序隊(duì)列108第四節(jié)隊(duì)列順序隊(duì)列：采用一組地址連續(xù)的存三、順序隊(duì)列的進(jìn)隊(duì)和出隊(duì)原則109第四節(jié)隊(duì)列進(jìn)隊(duì)時(shí)，新元素按rear指針位置插入，然后隊(duì)尾指針增一，即rear=rear+1出隊(duì)時(shí)，將隊(duì)頭指針位置的元素取出，然后隊(duì)頭指針增一，即front=front+1隊(duì)頭指針始終指向隊(duì)列頭元素隊(duì)尾指針始終指向隊(duì)列尾元素的下一個(gè)位置第３章棧和隊(duì)列三、順序隊(duì)列的進(jìn)隊(duì)和出隊(duì)原則109第四節(jié)隊(duì)列進(jìn)隊(duì)時(shí)，新元素四、順序隊(duì)列的進(jìn)隊(duì)和出隊(duì)舉例110第四節(jié)隊(duì)列第３章棧和隊(duì)列frontrear空隊(duì)列frontrearA,B,C,D進(jìn)隊(duì)ABCDfrontrearA退隊(duì)BCDfrontrearB退隊(duì)CDfrontrearE,F,G進(jìn)隊(duì)CDEFGCDEFGfrontrearH進(jìn)隊(duì),溢出四、順序隊(duì)列的進(jìn)隊(duì)和出隊(duì)舉例110第四節(jié)隊(duì)列第３章棧和隊(duì)五、順序隊(duì)列存在的問(wèn)題111第四節(jié)隊(duì)列當(dāng)隊(duì)尾指針指向隊(duì)列存儲(chǔ)結(jié)構(gòu)中的最后單元時(shí)，如果再繼續(xù)插入新的元素，則會(huì)產(chǎn)生溢出當(dāng)隊(duì)列發(fā)生溢出時(shí)，隊(duì)列存儲(chǔ)結(jié)構(gòu)中可能還存在一些空白位置（已被取走數(shù)據(jù)的元素）解決辦法之一：將隊(duì)列存儲(chǔ)結(jié)構(gòu)首尾相接，形成循環(huán)(環(huán)形)隊(duì)列第３章棧和隊(duì)列五、順序隊(duì)列存在的問(wèn)題111第四節(jié)隊(duì)列當(dāng)隊(duì)尾指針指向隊(duì)列存一、循環(huán)隊(duì)列112第五節(jié)循環(huán)隊(duì)列循環(huán)隊(duì)列采用一組地址連續(xù)的存儲(chǔ)單元將整個(gè)隊(duì)列的存儲(chǔ)單元首尾相連第３章棧和隊(duì)列C0123456frontMAXQSIZE-1DEABCrear一、循環(huán)隊(duì)列112第五節(jié)循環(huán)隊(duì)列循環(huán)隊(duì)列采用一組地址連續(xù)的二、循環(huán)隊(duì)列空與滿113第五節(jié)循環(huán)隊(duì)列front=rear，循環(huán)隊(duì)列空(rear+1)%MAXQSIZE=front，循環(huán)隊(duì)列滿第３章棧和隊(duì)列C0123456frontMAXQSIZE-1rear隊(duì)列空CDEFGBCH0123456frontMAXQSIZE-1rear隊(duì)列滿二、循環(huán)隊(duì)列空與滿113第五節(jié)循環(huán)隊(duì)列front=re三、循環(huán)隊(duì)列定義114第五節(jié)循環(huán)隊(duì)列#defineMAXQSIZE100Typedefstruct{ QElemType*base; int front; int rear;}SqQueue;第３章棧和隊(duì)列CDEFC0123456frontbaserear三、循環(huán)隊(duì)列定義114第五節(jié)循環(huán)隊(duì)列#defineMAX三、循環(huán)隊(duì)列插入元素115第五節(jié)循環(huán)隊(duì)列StatusEnQueue(SqQueue&Q,QElemTypee){ if((Q.rear+1)%MAXQSIZE==Q.front)returnERROR;//隊(duì)滿 Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAXQSIZE; returnOK;}第３章棧和隊(duì)列CDEFGBCH0123456frontMAXQSIZE-1rear三、循環(huán)隊(duì)列插入元素115第五節(jié)循環(huán)隊(duì)列StatusEn三、循環(huán)隊(duì)列刪除元素116第五節(jié)循環(huán)隊(duì)列StatusDeQueue(SqQueue&Q,QElemTypee){ if(Q.rear==Q.front)returnERROR;//隊(duì)空 e=Q.base[Q.front]; Q.front=(Q.front+1)%MAXQSIZE; returnOK;}第３章棧和隊(duì)列C0123456frontrear三、循環(huán)隊(duì)列刪除元素116第五節(jié)循環(huán)隊(duì)列StatusDe一、鏈隊(duì)列117第六節(jié)鏈隊(duì)列鏈隊(duì)列采用鏈表存儲(chǔ)單元鏈隊(duì)列中，有兩個(gè)分別指示隊(duì)頭和隊(duì)尾的指針。鏈?zhǔn)疥?duì)列在進(jìn)隊(duì)時(shí)無(wú)隊(duì)滿問(wèn)題，但有隊(duì)空問(wèn)題。第３章棧和隊(duì)列datanextfrontrear一、鏈隊(duì)列117第六節(jié)鏈隊(duì)列鏈隊(duì)列采用鏈表存儲(chǔ)單元第３章二、鏈隊(duì)列指針變化狀況118第六節(jié)鏈隊(duì)列鏈隊(duì)列是鏈表操作的子集第３章棧和隊(duì)列frontrearxy^元素y入隊(duì)frontrearx^y元素x出隊(duì)frontrear^空隊(duì)列^二、鏈隊(duì)列指針變化狀況118第六節(jié)鏈隊(duì)列鏈隊(duì)列是鏈表操作的第四章

串?dāng)?shù)據(jù)結(jié)構(gòu)深圳大學(xué)計(jì)算機(jī)系

蔡茂國(guó)第四章

串?dāng)?shù)據(jù)結(jié)構(gòu)一、字符串（string）120第一節(jié)字符串字符串是n(≥0)個(gè)字符的有限序列，記作：

S=‘a(chǎn)1a2a3…an’其中，S是串名字‘a(chǎn)1a2a3…an’是串值

ai

是串中字符

n是串的長(zhǎng)度(串中字符的個(gè)數(shù))例如,S=“ShenzhenUniversity”第４章串一、字符串（string）120第一節(jié)字符串字符串是n(≥二、字符串術(shù)語(yǔ)121第一節(jié)字符串空串：不含任何字符的串，串長(zhǎng)度=0空格串：僅由一個(gè)或多個(gè)空格組成的串子串：由串中任意個(gè)連續(xù)的字符組成的子序列。主串：包含子串的串。如：A=’ShenzhenUniversity’B=’University’A為主串，B為子串。第４章串二、字符串術(shù)語(yǔ)121第一節(jié)字符串空串：不含任何字符的串，串二、字符串術(shù)語(yǔ)122第一節(jié)字符串位置：字符在序列中的序號(hào)。子串在主串中的位置以子串第一個(gè)字符在主串中的位置來(lái)表示。串相等的條件：當(dāng)兩個(gè)串的長(zhǎng)度相等且各個(gè)對(duì)應(yīng)位置的字符都相等時(shí)才相等。模式匹配：確定子串在主串中首次出現(xiàn)的位置的運(yùn)算

第４章串二、字符串術(shù)語(yǔ)122第一節(jié)字符串位置：字符在序列中的序號(hào)。三、字符串與線性表的關(guān)系123第一節(jié)字符串串的邏輯結(jié)構(gòu)和線性表極為相似，它們都是線性結(jié)構(gòu)串中的每個(gè)字符都僅有一個(gè)前驅(qū)和一個(gè)后繼第４章串三、字符串與線性表的關(guān)系123第一節(jié)字符串串的邏輯結(jié)構(gòu)和線三、字符串與線性表的關(guān)系124第一節(jié)字符串串與線性表又有區(qū)別，主要表現(xiàn)為：串的數(shù)據(jù)對(duì)象約定是字符集在線性表的基本操作中，以“單個(gè)元素”作為操作對(duì)象在串的基本操作中，通常以“串的整體”作為操作對(duì)象，如：在串中查找某個(gè)子串、在串的某個(gè)位置上插入一個(gè)子串等。第４章串三、字符串與線性表的關(guān)系124第一節(jié)字符串串與線性表又有一、定長(zhǎng)順序存儲(chǔ)表示125第二節(jié)串的表示和實(shí)現(xiàn)用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)字符序列如C語(yǔ)言中的字符串定義(以“\0”為串結(jié)束標(biāo)志)charStr[MAXSTRLEN+1];定義了長(zhǎng)度為MAXSTRLEN字符存儲(chǔ)空間字符串長(zhǎng)度可以是小于MAXSTRLEN的任何值（最長(zhǎng)串長(zhǎng)度有限制，多余部分將被截?cái)啵┑冢凑麓弧⒍ㄩL(zhǎng)順序存儲(chǔ)表示125第二節(jié)串的表示和實(shí)現(xiàn)用一組地址連二、堆分配存儲(chǔ)表示126第二節(jié)串的表示和實(shí)現(xiàn)在程序執(zhí)行過(guò)程中，動(dòng)態(tài)分配（malloc）一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)字符序列在C語(yǔ)言中，由malloc()和free()動(dòng)態(tài)分配與回收的存儲(chǔ)空間稱(chēng)為堆堆分配存儲(chǔ)結(jié)構(gòu)的串既有順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)，處理方便,操作中對(duì)串長(zhǎng)又沒(méi)有限制,更顯靈活第４章串二、堆分配存儲(chǔ)表示126第二節(jié)串的表示和實(shí)現(xiàn)在程序執(zhí)行過(guò)程三、鏈存儲(chǔ)表示127第二節(jié)串的表示和實(shí)現(xiàn)采用鏈表方式存儲(chǔ)串值每個(gè)結(jié)點(diǎn)中，可以存放一個(gè)字符，也可以存放多個(gè)字符第４章串Hell0^SSShend^a##三、鏈存儲(chǔ)表示127第二節(jié)串的表示和實(shí)現(xiàn)采用鏈表方式存儲(chǔ)串一、求子串位置函數(shù)Index()128第三節(jié)串的匹配算法子串的定位操作通常稱(chēng)做串的模式匹配算法（窮舉法）：從主串的指定位置開(kāi)始，將主串與模式（要查找的子串）的第一個(gè)字符比較，1.若相等，則繼續(xù)逐個(gè)比較后續(xù)字符；2.若不等，從主串的下一個(gè)字符起再重新和模式的字符比較第４章串一、求子串位置函數(shù)Index()128第三節(jié)串的匹配算法子一、求子串位置函數(shù)Index()129第三節(jié)串的匹配算法IntIndex(SstringS,SstringT,intpos){ //S為主串，T為模式，串的第0位置存放串長(zhǎng)度；串采用順序存儲(chǔ)結(jié)構(gòu) i=pos;j=1; //從第一個(gè)位置開(kāi)始比較 while(i<=S[0]&&j<=T[0]){ if(S[i]==T[j]){++i;++j;} //繼續(xù)比較后繼字符 else{i=i–j+2;j=1;} //指針后退重新開(kāi)始匹配 } if(j>T[0])returni-T[0]; //返回與模式第一字符相等 elsereturn0; //匹配不成功 //的字符在主串中的序號(hào)}第４章串一、求子串位置函數(shù)Index()129第三節(jié)串的匹配算法I一、求子串位置函數(shù)Index()130第三節(jié)串的匹配算法在最好的情況下，除比較成功的位置外，其余位置僅需比較一次（模式第一個(gè)字符），其時(shí)間復(fù)雜度為：O(n+m)(n，m分別為主串和模式的長(zhǎng)度)但在最壞的情況下，如模式為‘00000001’，主串為‘0000000000000000000000000000000001’,則每次模式的前7個(gè)0都要與主串逐一比較，因此，其時(shí)間復(fù)雜度為：O(n*m)第４章串一、求子串位置函數(shù)Index()130第三節(jié)串的匹配算法在二、KMP算法131第三節(jié)串的匹配算法是index函數(shù)的一種改進(jìn),由D.E.Knuth(克努特)－J.H.Morris(莫里斯)－V.R.Pratt(普拉特)發(fā)現(xiàn)當(dāng)一趟匹配過(guò)程中出現(xiàn)字符比較不等(失配)時(shí)1.不需回溯i指針2.利用已經(jīng)得到的“部分匹配”的結(jié)果3.將模式向右“滑動(dòng)”盡可能遠(yuǎn)的一段距離(next[j])后，繼續(xù)進(jìn)行比較第４章串二、KMP算法131第三節(jié)串的匹配算法是index函數(shù)的一二、KMP算法(舉例)132第三節(jié)串的匹配算法假設(shè)主串a(chǎn)babcabcacbab,模式abcac,改進(jìn)算法的匹配過(guò)程如下 ↓i=3第一趟匹配 ababcabcacbab abc ↑j=3 ↓i=3----7第二趟匹配ababcabcacbab abcac ↑j=1 ↓i=7--10第三趟匹配 ababcabcacbab abcac ↑j=2第４章串二、KMP算法(舉例)132第三節(jié)串的匹配算法假設(shè)主串a(chǎn)b二、KMP算法133第三節(jié)串的匹配算法假設(shè)主串為‘s1s2s3…sn’,模式串為‘p1p2p3…pm’若主串中第i個(gè)字符與模式串中第j個(gè)字符“失配”(si!=pj),需要與模式串中第k(k<j)個(gè)字符比較,則有以下關(guān)系成立：

‘p1p2…pk-1’=‘si-k+1si-k+2…si-1’而已經(jīng)得到的“部分匹配”結(jié)果為：

‘pj-k+1pj-k+2…pj-1’=‘si-k+1si-k+2…si-1’第４章串二、KMP算法133第三節(jié)串的匹配算法假設(shè)主串為‘s1s2二、KMP算法134第三節(jié)串的匹配算法從而有下式成立：

‘p1p2…pk-1’=‘pj-k+1pj-k+2…pj-1’上式是只依賴(lài)于模式串的關(guān)系式上式說(shuō)明,在主串中第i個(gè)字符“失配”時(shí),僅需與模式串中的第k個(gè)字符再開(kāi)始比較（不需要回溯）第４章串二、KMP算法134第三節(jié)串的匹配算法從而有下式成立：第４二、KMP算法135第三節(jié)串的匹配算法或者換言之,在模式串中第j個(gè)字符“失配”時(shí),模式串第k個(gè)字符再同主串中對(duì)應(yīng)的失配位置(i)的字符繼續(xù)進(jìn)行比較

‘p1p2…pk-1’=‘pj-k+1pj-k+2…pj-1’k值可以在作串的匹配之前求出一般用next函數(shù)求取k值第４章串二、KMP算法135第三節(jié)串的匹配算法或者換言之,在模式串二、KMP算法(next函數(shù))136第三節(jié)串的匹配算法next函數(shù)定義為： 0 當(dāng)j=1時(shí)next[j]=max{k|1<k<j且‘p1…pk-1’=‘pj-k+1…pj-1’ 1 其它情況如k=2,則p1=pj-1(有1個(gè)字符相同)[除j=2外];k=3,則p1p2=pj-2pj-1(有2個(gè)字符相同);第４章串二、KMP算法(next函數(shù))1