課程簡介課件

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

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

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

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

蔡茂國第一章

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

結(jié)構(gòu)是元素之間的：空間位置關(guān)系相互作用和依賴關(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)樹形結(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ù)對象的所有數(shù)據(jù)成員之間的關(guān)系。記為：Data_Structure={D,S}其中，D是某一數(shù)據(jù)對象，S是該對象中所有數(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ù)據(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ù)據(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é)號姓名學(xué)院專業(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ù)據(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ù)據(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)要解決的問題18第一節(jié)數(shù)據(jù)結(jié)構(gòu)如何為應(yīng)用程序中涉及到各種各樣的數(shù)據(jù)，建立相應(yīng)的數(shù)據(jù)結(jié)構(gòu)（表、樹或圖），并依此實現(xiàn)軟件功能從廣義上講，數(shù)據(jù)結(jié)構(gòu)描述現(xiàn)實世界實體的數(shù)學(xué)模型及其上的操作在計算機中的表示和實現(xiàn)第１章數(shù)據(jù)結(jié)構(gòu)緒論八、數(shù)據(jù)結(jié)構(gòu)要解決的問題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)線性表（表，棧，隊列，串等）非線性結(jié)構(gòu)樹（二叉樹，Huffman樹，二叉排序樹等）圖（有向圖，無向圖等）第１章數(shù)據(jù)結(jié)構(gòu)緒論456231123456123456一、邏輯結(jié)構(gòu)19第二節(jié)數(shù)據(jù)的結(jié)構(gòu)邏輯結(jié)構(gòu)描述數(shù)據(jù)元素之間的二、物理結(jié)構(gòu)（存儲結(jié)構(gòu)）20第二節(jié)數(shù)據(jù)的結(jié)構(gòu)物理結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計算機中的表示（或映象）順序存儲表示（可以用C語言中一維數(shù)組表示）鏈接存儲表示（可以用C語言中的指針表示）索引存儲表示散列存儲表示第１章數(shù)據(jù)結(jié)構(gòu)緒論二、物理結(jié)構(gòu)（存儲結(jié)構(gòu)）20第二節(jié)數(shù)據(jù)的結(jié)構(gòu)物理結(jié)構(gòu)是數(shù)據(jù)二、物理結(jié)構(gòu)（存儲結(jié)構(gòu)）21第二節(jié)數(shù)據(jù)的結(jié)構(gòu)復(fù)數(shù)存儲結(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順序存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu)二、物理結(jié)構(gòu)（存儲結(jié)構(gòu)）21第二節(jié)數(shù)據(jù)的結(jié)構(gòu)復(fù)數(shù)存儲結(jié)構(gòu)舉一、數(shù)據(jù)類型22第三節(jié)數(shù)據(jù)類型數(shù)據(jù)類型是一個值的集合和定義在這個值集上的一組操作的總稱如C語言中的整型變量(int)，其值集為某個區(qū)間上的整數(shù)，定義在其上的操作為+,-,x,/等第１章數(shù)據(jù)結(jié)構(gòu)緒論一、數(shù)據(jù)類型22第三節(jié)數(shù)據(jù)類型數(shù)據(jù)類型是一個值的集合和定義二、原子數(shù)據(jù)類型和結(jié)構(gòu)數(shù)據(jù)類型23第三節(jié)數(shù)據(jù)類型1.原子數(shù)據(jù)類型是不可分解的數(shù)據(jù)類型如C語言中的整型(int)，實型(float)，字符型(char)，指針類型(*)和空類型(void)等第１章數(shù)據(jù)結(jié)構(gòu)緒論二、原子數(shù)據(jù)類型和結(jié)構(gòu)數(shù)據(jù)類型23第三節(jié)數(shù)據(jù)類型1.原子二、原子數(shù)據(jù)類型和結(jié)構(gòu)數(shù)據(jù)類型24第三節(jié)數(shù)據(jù)類型2.結(jié)構(gòu)數(shù)據(jù)類型由若干成分（原子類型或結(jié)構(gòu)類型）按某種結(jié)構(gòu)組成的數(shù)據(jù)類型結(jié)構(gòu)數(shù)據(jù)類型可以看作是一種數(shù)據(jù)結(jié)構(gòu)和定義在其上的一組操作組成的整體如數(shù)組，由若干分量組成，每個分量可以是整數(shù)，也可以是數(shù)組（如intA[10]）第１章數(shù)據(jù)結(jié)構(gòu)緒論二、原子數(shù)據(jù)類型和結(jié)構(gòu)數(shù)據(jù)類型24第三節(jié)數(shù)據(jù)類型2.結(jié)構(gòu)三、抽象數(shù)據(jù)類型（AbstractDataType）25第三節(jié)數(shù)據(jù)類型由用戶定義，用以表示應(yīng)用問題的數(shù)據(jù)模型由基本的數(shù)據(jù)類型組成,并包括一組相關(guān)的服務(wù)（或稱操作）信息隱蔽和數(shù)據(jù)封裝，使用與實現(xiàn)相分離第１章數(shù)據(jù)結(jié)構(gòu)緒論三、抽象數(shù)據(jù)類型（AbstractDataType）25三、抽象數(shù)據(jù)類型（ADT）26第三節(jié)數(shù)據(jù)類型抽象數(shù)據(jù)類型（ADT）是一個數(shù)學(xué)模型以及定義在該模型上的一組操作抽象數(shù)據(jù)類型=數(shù)據(jù)結(jié)構(gòu)+定義在此數(shù)據(jù)結(jié)構(gòu)上的一組操作第１章數(shù)據(jù)結(jié)構(gòu)緒論三、抽象數(shù)據(jù)類型（ADT）26第三節(jié)數(shù)據(jù)類型抽象數(shù)據(jù)類型（三、抽象數(shù)據(jù)類型（ADT表示）27第三節(jié)數(shù)據(jù)類型抽象數(shù)據(jù)類型可用（D，S，P）三元組表示D是數(shù)據(jù)對象S是D上的關(guān)系集P是對D的基本操作集。第１章數(shù)據(jù)結(jié)構(gòu)緒論三、抽象數(shù)據(jù)類型（ADT表示）27第三節(jié)數(shù)據(jù)類型抽象數(shù)據(jù)類三、抽象數(shù)據(jù)類型（ADT定義）28第三節(jié)數(shù)據(jù)類型ADT抽象數(shù)據(jù)類型名{ 數(shù)據(jù)對象：〈數(shù)據(jù)對象的定義〉 數(shù)據(jù)關(guān)系：〈數(shù)據(jù)關(guān)系的定義〉 基本操作：〈基本操作(函數(shù))的定義〉 }ADT抽象數(shù)據(jù)類型名第１章數(shù)據(jù)結(jié)構(gòu)緒論三、抽象數(shù)據(jù)類型（ADT定義）28第三節(jié)數(shù)據(jù)類型ADT抽三、抽象數(shù)據(jù)類型（ADT定義舉例）29第三節(jié)數(shù)據(jù)類型ADTTriplet{ 數(shù)據(jù)對象：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個元素中的最大值。Min(T,&e)初始條件：三元組T已存在。

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

}ADTTriplet第１章數(shù)據(jù)結(jié)構(gòu)緒論三、抽象數(shù)據(jù)類型（ADT定義舉例）29第三節(jié)數(shù)據(jù)類型ADT三、抽象數(shù)據(jù)類型（ADT定義實現(xiàn)）30第三節(jié)數(shù)據(jù)類型抽象數(shù)據(jù)類型可以通過固有數(shù)據(jù)類型(C語言中已實現(xiàn)的數(shù)據(jù)類型)來實現(xiàn)抽象數(shù)據(jù)類型類class數(shù)據(jù)對象數(shù)據(jù)成員基本操作成員函數(shù)(方法)第１章數(shù)據(jù)結(jié)構(gòu)緒論三、抽象數(shù)據(jù)類型（ADT定義實現(xiàn)）30第三節(jié)數(shù)據(jù)類型抽象數(shù)一、算法（Algorithm）31第四節(jié)算法分析算法是對特定問題求解步驟的一種描述是一有限長的操作序列第１章數(shù)據(jù)結(jié)構(gòu)緒論一、算法（Algorithm）31第四節(jié)算法分析算法是對特一、算法（特性）32第四節(jié)算法分析有窮性：算法在執(zhí)行有窮步后能結(jié)束確定性：每步定義都是確切、無歧義可行性：每一條運算應(yīng)足夠基本(已驗算正確)輸入：有0個或多個輸入輸出：有一個或多個輸出第１章數(shù)據(jù)結(jié)構(gòu)緒論一、算法（特性）32第四節(jié)算法分析有窮性：算法在執(zhí)行有窮步一、算法（舉例）33第四節(jié)算法分析例子：選擇排序問題：遞增排序解決方案：逐個選擇最小數(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è)計的要求34第四節(jié)算法分析正確性：滿足具體問題的需求可讀性：便于理解和修改健壯性：當(dāng)輸入數(shù)據(jù)非法時，也能適當(dāng)反應(yīng)效率高：執(zhí)行時間少空間?。簣?zhí)行中需要的最大存儲空間第１章數(shù)據(jù)結(jié)構(gòu)緒論二、算法設(shè)計的要求34第四節(jié)算法分析正確性：滿足具體問題的三、時間復(fù)雜度35第四節(jié)算法分析衡量算法的效率，主要依據(jù)算法執(zhí)行所需要的時間，即時間復(fù)雜度事后統(tǒng)計法：計算算法開始時間與完成時間差值事前統(tǒng)計法：依據(jù)算法選用何種策略及問題的規(guī)模n，是常用的方法第１章數(shù)據(jù)結(jié)構(gòu)緒論三、時間復(fù)雜度35第四節(jié)算法分析衡量算法的效率，主要依據(jù)算三、時間復(fù)雜度36第四節(jié)算法分析時間復(fù)雜度是問題規(guī)模n的函數(shù)f(n)，即：

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

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

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

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

蔡茂國第二章

線性表數(shù)據(jù)結(jié)構(gòu)一、線性數(shù)據(jù)結(jié)構(gòu)的特點42第一節(jié)線性表在數(shù)據(jù)元素的非空有限集中１、存在惟一的一個被稱作“第一個”的數(shù)據(jù)元素(如“１”)２、存在惟一的一個被稱作“最后一個”的數(shù)據(jù)元素(如“６”)３、除第一個元素外，每個數(shù)據(jù)元素均只有一個前驅(qū)４、除最后一個元素外，每個數(shù)據(jù)元素均只有一個后繼(next)(如“1”的next是“2”,“2”的next是“3”)第２章線性表123456一、線性數(shù)據(jù)結(jié)構(gòu)的特點42第一節(jié)線性表在數(shù)據(jù)元素的非空有限二、線性表43第一節(jié)線性表線性表是最簡單的一類線性數(shù)據(jù)結(jié)構(gòu)線性表是由n個數(shù)據(jù)元素組成的有限序列，相鄰數(shù)據(jù)元素之間存在著序偶關(guān)系，可以寫為：(a1,a2,…ai-1,ai,ai+1,…an-1,an)其中,ai是表中元素,i表示元素ai的位置,n是表的長度第２章線性表二、線性表43第一節(jié)線性表線性表是最簡單的一類線性數(shù)據(jù)結(jié)構(gòu)二、線性表44第一節(jié)線性表線性表中的元素具有相同的特性，屬于同一數(shù)據(jù)對象，如：1.26個字母的字母表:(A,B,C,D,…,Z)2.近期每天的平均溫度:(30℃,28℃,29℃,…)第２章線性表二、線性表44第一節(jié)線性表線性表中的元素具有相同的特性，屬一、順序表45第二節(jié)順序表順序表是線性表的順序表示用一組地址連續(xù)的存儲單元依次存儲線性表的數(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語言中動態(tài)分配的一維數(shù)組表示順序表第２章線性表#defineLIST_INIT_SIZE100 //線性表存儲空間的初始分配量#defineLISTINCREMENT10 //線性表存儲空間的分配增量Typedefstruct{ ElemType *elem; //存儲空間基址 int length; //當(dāng)前長度 int listsize; //當(dāng)前分配的存儲容量(元素數(shù))}Sqlist;二、順序表的定義47第二節(jié)順序表采用C語言中動態(tài)分配的一維三、順序表的初始化48第二節(jié)順序表創(chuàng)建一個順序表L第２章線性表StatusInitList_Sq(Sqlist&L){ L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L.elem)exit(OVERFLOW); //存儲分配失敗 L.length=0; //空表長度為0 L.listsize=LIST_INIT_SIZE; //初始存儲容量 returnOK;}//InitList_Sq三、順序表的初始化48第二節(jié)順序表創(chuàng)建一個順序表L第２章三、順序表的插入49第二節(jié)順序表順序表的插入操作是指在順序表的第i-1個數(shù)據(jù)元素和第i個數(shù)據(jù)元素之間插入一個新的數(shù)據(jù)元素，即將長度為n的順序表：(a1,…ai-1,ai,…,an)

變成長度為n+1的順序表：(a1,…ai-1,e,ai,…,an)第２章線性表三、順序表的插入49第二節(jié)順序表順序表的插入操作是指在順序三、順序表的插入50第二節(jié)順序表在第3個元素與第4個元素之間插入新元素b需要將最后元素n至第4元素(共7-4+1)都向后移一位置第２章線性表253457164809630123456725345750164809635050插入ei=401234567三、順序表的插入50第二節(jié)順序表在第3個元素與第4個元素之三、順序表的插入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;} //以上皆為準備階段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 //請注意元素位置數(shù)值較元素序號少1三、順序表的插入51第二節(jié)順序表第２章線性表Status三、順序表的插入52第二節(jié)順序表在順序表中插入一個元素，需要向后移動元素個數(shù)為：n-i+1平均移動元素數(shù)為：n+1Eis=∑pix(n-i+1)i=1第２章線性表三、順序表的插入52第二節(jié)順序表在順序表中插入一個元素，需三、順序表的插入53第二節(jié)順序表當(dāng)插入位置等概率時，pi=1/(n+1)，因此：n+1Eis=∑[1/(n+1)]x(n-i+1)=n/2i=1順序表插入操作的時間復(fù)雜度為O(n)第２章線性表三、順序表的插入53第二節(jié)順序表當(dāng)插入位置等概率時，pi=四、順序表的刪除54第二節(jié)順序表順序表的刪除操作是指將順序表的第i個數(shù)據(jù)元素刪除，即將長度為n的順序表：(a1,…ai-1,ai,ai+1,…,an)

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

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

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

p=L->next;j=1; //p指向第一個結(jié)點 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é)線性鏈表算法時間復(fù)雜度主要取決于while循環(huán)中的語句頻度頻度與被查找元素在單鏈表中的位置有關(guān)若1≤i≤n，則頻度為i-1，否則為n因此時間復(fù)雜度為O(n)第２章線性表na1aianL……四、找指定元素66第二節(jié)線性鏈表算法時間復(fù)雜度主要取決于w五、線性鏈表的插入67第二節(jié)線性鏈表在線性鏈表的第i-1元素與第i元素之間插入一個新元素第２章線性表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é)點的單鏈表L中第i個位置之前插入元素e p=L;j=0; while(p&&j<i-1){p=p->next;j++;} //尋找i-1結(jié)點 if(!p||j>i-1)returnERROR; s=(LinkList)malloc(sizeof(LNode); //生成新結(jié)點 s->data=e;s->next=p->next;p->next=s; //插入L中 returnOK;}//ListInsert_L第２章線性表五、線性鏈表的插入68第二節(jié)線性鏈表StatusList五、線性鏈表的插入69第二節(jié)線性鏈表同樣，算法時間復(fù)雜度主要取決于while循環(huán)中的語句頻度頻度與在線性鏈表中的元素插入位置有關(guān)因此線性鏈表插入的時間復(fù)雜度為O(n)第２章線性表五、線性鏈表的插入69第二節(jié)線性鏈表同樣，算法時間復(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é)點的單鏈表L中，刪除第i個位置的元素 p=L;j=0; while(p->next&&j<i-1){p=p->next;j++;} //尋找i結(jié)點 if(!p->next||j>i-1)returnERROR; q=p->next;p->next=q->next; //刪除i結(jié)點

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

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

蔡茂國第三章

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

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

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

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

StackEmpty(S) //棧是否為空

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

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

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

空棧五、創(chuàng)建順序棧92第二節(jié)順序棧第３章棧和隊列Status六、進棧（插入新元素）93第二節(jié)順序棧第３章棧和隊列StatusPush(SqStack&S,SElemTypee){ if(S.top–S.base>=S.stacksize){ //棧滿，追加存儲空間 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進棧topbaseba操作前六、進棧（插入新元素）93第二節(jié)順序棧第３章棧和隊列St七、出棧（刪除元素）94第二節(jié)順序棧第３章棧和隊列StatusPop(SqStack&S,SElemType&e){

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

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

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

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

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

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

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

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

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

a2

a3

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

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

蔡茂國第四章

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

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

ai

是串中字符

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

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

‘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時next[j]=max{k|1<k<j且‘p1…pk-1’=‘pj-k+1…pj-1’ 1 其它情況如k=2,則p1=pj-1(有1個字符相同)[除j=2外];k=3,則p1p2=pj-2pj-1(有2個字符相同);第４章串二、KMP算法(next函數(shù))1