教學(xué)課件：《數(shù)據(jù)結(jié)構(gòu)與算法(第2版)

1、數(shù)據(jù)結(jié)構(gòu)與算法1第1章 概述 1節(jié)2內(nèi)容提要2基本概念和算法表現(xiàn)形式了解即可算法評價標(biāo)準(zhǔn)、正確性、時間復(fù)雜性最壞情況和平均情況，很重要 主要內(nèi)容：數(shù)據(jù)結(jié)構(gòu)和算法的基本概念算法的表現(xiàn)形式和評價方法3內(nèi)容提要3抽象數(shù)據(jù)類型結(jié)合對表樹圖的類化示例加以理解 難點：抽象數(shù)據(jù)類型算法時間復(fù)雜性的計算算法時間復(fù)雜性的計算方法通過后續(xù)各章對眾多算法的分析、評價、時間空間復(fù)雜性計算，逐步加以理解41.1 基本概念41數(shù)據(jù)和數(shù)據(jù)結(jié)點 數(shù)據(jù)是對客觀事物的描述形式和編碼形式的統(tǒng)稱 是計算機(jī)算法和程序的處理對象（輸入數(shù)據(jù)）和計算結(jié)果（輸出數(shù)據(jù)） 1.1.1 數(shù)據(jù)結(jié)構(gòu)的概念51.1 基本概念1.1.1 數(shù)據(jù)結(jié)構(gòu)的概念5數(shù)

2、據(jù)的種類數(shù)值型數(shù)據(jù)（整數(shù)、實數(shù)等）文字型數(shù)據(jù)（字符、字符串、程序代碼）矩陣、記錄聲音、圖像數(shù)據(jù)總是以某種編碼形式出現(xiàn)的61.1 基本概念1.1.1 數(shù)據(jù)結(jié)構(gòu)的概念6數(shù)據(jù)元素（data element）數(shù)據(jù)結(jié)點，簡稱結(jié)點（node）描述一個獨(dú)立事物的名稱、數(shù)量、特征、性質(zhì)的一組相關(guān)信息組成一個數(shù)據(jù)結(jié)點通常，一個結(jié)點含有多個數(shù)據(jù)項（data item） 結(jié)點的類型：結(jié)構(gòu)型關(guān)鍵字（key） 單值類型的結(jié)點：只含一個數(shù)據(jù)項71.1.1 數(shù)據(jù)結(jié)構(gòu)的概念2數(shù)據(jù)結(jié)構(gòu)的定義 數(shù)據(jù)結(jié)構(gòu)（data structure） B = ( D，R)7數(shù)據(jù)結(jié)構(gòu)有窮的結(jié)點集合D中結(jié)點間的有窮關(guān)系集合數(shù)據(jù)的邏輯結(jié)構(gòu)（logic

3、al form ）存儲形式：物理結(jié)構(gòu)（physical form ）81.1.1 數(shù)據(jù)結(jié)構(gòu)的概念8物理結(jié)構(gòu)存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的存儲形式（存儲表示）存儲數(shù)據(jù)結(jié)點和結(jié)點之間的關(guān)系順序存儲、非順序存儲存儲結(jié)點用于存儲一個數(shù)據(jù)結(jié)點的存儲單元一個數(shù)據(jù)結(jié)點對應(yīng)一個存儲結(jié)點數(shù)據(jù)結(jié)點和存儲結(jié)點統(tǒng)稱結(jié)點 空白結(jié)點（空結(jié)點、自由結(jié)點） 預(yù)留的存儲結(jié)點（即尚未存儲數(shù)據(jù)的存儲結(jié)點）91.1.1 數(shù)據(jù)結(jié)構(gòu)的概念2數(shù)據(jù)結(jié)構(gòu)的定義數(shù)據(jù)結(jié)構(gòu)與算法研究的對象9數(shù)據(jù)元素的集合元素之間的關(guān)系對數(shù)據(jù)集合進(jìn)行哪些運(yùn)算實現(xiàn)運(yùn)算的算法算法效率10示例設(shè)D為某專業(yè)開設(shè)的計算機(jī)課程，R是定義在D上的關(guān)系 D=C1、C2、C3、C4、C5 R=(

4、x,y)|x課程是y課程的先修課，x,y D若R1=(C1,C2), (C2,C3), (C3,C4), (C4,C5)，則DS=(D,R1)就是一種數(shù)據(jù)結(jié)構(gòu)（線性表）若R2=(C1,C2), (C2,C3), (C2,C4), (C2,C5), (C3,C5),，則DS=(D,R2)也是一種數(shù)據(jù)結(jié)構(gòu)10數(shù)據(jù)元素、結(jié)點邏輯結(jié)構(gòu)111.1.1 數(shù)據(jù)結(jié)構(gòu)的概念3數(shù)據(jù)結(jié)構(gòu)的種類11表結(jié)構(gòu)、樹結(jié)構(gòu)、圖結(jié)構(gòu)、散結(jié)構(gòu) 表：描述結(jié)點之間簡單的先后次序關(guān)系樹：描述結(jié)點之間的層次關(guān)系、嵌套關(guān)系圖：描述結(jié)點之間的“多對多”關(guān)系散結(jié)構(gòu)：結(jié)點之間松散的 “無關(guān)關(guān)系” 比如散列表 一對一的關(guān)系，比如學(xué)生成績單比如城市交

5、通網(wǎng) 一對多的關(guān)系，比如某部門的組織機(jī)構(gòu) 121.1.1 數(shù)據(jù)結(jié)構(gòu)的概念3數(shù)據(jù)結(jié)構(gòu)的種類12圖示：圓圈表示結(jié)點，連線表示結(jié)點之間關(guān)系 樹、散是圖的特例，表是樹的特例131.1.2 抽象數(shù)據(jù)類型 1抽象的意義 抽取事物的共性，忽略個性 體現(xiàn)外部特征，掩蓋具體細(xì)節(jié) 132抽象數(shù)據(jù)類型的含義 ADT（Abstract Data Types）將數(shù)據(jù)連同對其的處理操作封裝在一起 3抽象數(shù)據(jù)類型的實現(xiàn)方法 封裝法、半封裝法、分散法141.1.3 算法的概念 1算法的定義 14計算機(jī)科學(xué)家D.E.Knuth（克努特）在其經(jīng)典巨著計算機(jī)程序設(shè)計藝術(shù)(The Art of Computer Programmin

6、g)第一卷中對算法的定義 算法，就是有窮規(guī)則的集合，其中的規(guī)則規(guī)定了解決某特定類型問題的運(yùn)算序列有窮性、確定性、可行性、輸入、輸出151.1.3 算法的概念 15有窮性：一個算法在執(zhí)行有限步之后必須結(jié)束確定性：算法的每一步驟必須確切定義。執(zhí)行者可根據(jù)該算法的每一步要求進(jìn)行操作，并最終得出正確的結(jié)果（即無歧義）可行性：算法中所有的運(yùn)算都可以精確地實現(xiàn)輸入：算法有零個或多個輸入，即在算法開始之前，對算法給定的初始量輸出：算法有一個或多個輸出，即與輸入有某個特定關(guān)系的量，簡單地說就是算法的最終結(jié)果161.1.3 算法的概念 2算法、數(shù)據(jù)結(jié)構(gòu)與程序的關(guān)系 1616給定問題設(shè)計求解問題的算法 抽象出數(shù)據(jù)

7、，建立數(shù)據(jù)結(jié)構(gòu) 滿意？ 正確？有錯 交付使用正確 對算法不滿意對數(shù)據(jù)結(jié)構(gòu)不滿意不滿意滿意 對算法的性能進(jìn)行評價 將算法分解成對數(shù)據(jù)結(jié)構(gòu)的運(yùn)算 編程實現(xiàn)，并上機(jī)調(diào)試 16 本 節(jié) 結(jié) 束17第1章 概述 1節(jié)數(shù)據(jù)結(jié)構(gòu)與算法18第1章 概述 2節(jié)191.2 算法的描述和評價 191描述形式 自然語言流程圖（flowchart） 類語言偽代碼（pseudocode） 1.2.1 算法的描述 描述形式、 程序形式（算法的實現(xiàn)形式）程序中含有算法2. 示例 20示例1-1 自然選擇排序算法（1）文字?jǐn)⑹鰪膎個數(shù)據(jù)中選出一個最小元素作為第一項再從剩下的n-1個數(shù)據(jù)中選出一個最小元素作為第二項重復(fù)上述，直至

8、選擇最后一項不依賴數(shù)據(jù)結(jié)構(gòu)，不考慮如何存儲數(shù)據(jù) 21示例1-1 自然選擇排序算法（1）文字?jǐn)⑹鰪膎個數(shù)據(jù)中選出一個最小元素作為第一項再從剩下的n-1個數(shù)據(jù)中選出一個最小元素作為第二項重復(fù)上述，直至選擇最后一項不依賴數(shù)據(jù)結(jié)構(gòu)，不考慮如何存儲數(shù)據(jù) 進(jìn)一步敘述 將數(shù)據(jù)存儲在數(shù)組an中從n個元素中選擇最小元aj，換到a0處；再從剩下的n-1個元素中選擇最小元，換到a1處； 22示例1-1 自然選擇排序算法（1）文字?jǐn)⑹鰪膎個數(shù)據(jù)中選出一個最小元素作為第一項再從剩下的n-1個數(shù)據(jù)中選出一個最小元素作為第二項重復(fù)上述，直至選擇最后一項 循環(huán)形式：步驟1）置i=0；步驟2）從aian-1選出最小元素ak；步

9、驟3）交換ai與ak；步驟4）i=i+1;步驟5）如果i等于n-1，則算法結(jié)束； 否則，轉(zhuǎn)步驟2。23示例1-1 自然選擇排序算法（2）流圖24示例1-1 自然選擇排序算法（3）偽代碼for(i=0;in-1;i+) 從ai到an-1中選出最小元素ak; 使ak與ai交換; 25示例1-1 自然選擇排序算法for(i=0;in-1;i+) k=i; for(j=i+1;jn;j+)if(ajrightleft=0; right=n-1; i=-1mid=(left+right)/2比較x與amidx=amidxamidi=mid;left=right+1開始29示例1-2 二分查找（binar

10、y search）（3）偽代碼 left0，rightn-1;while (leftamid) 沒找到x，返回-1; mid=(left +right)/2; if(x=amid) 找到x，返回x的下標(biāo)mid; if(x n0，T(n)cf(n)都成立 那么，就記作 T(n)=O(f(n) 381.2.2 算法的評價標(biāo)準(zhǔn)和評價方法 3時間復(fù)雜性T(n)=O(f(n) T(n)是f(n)的大O函數(shù)只求T(n)的最高階忽略其低階項和常系數(shù)f(n)：運(yùn)行時間 增長率的上界簡化T(n)的計算；較客觀地反映當(dāng)n很大時，算法的時間性能 391.2.2 算法的評價標(biāo)準(zhǔn)和評價方法 3時間復(fù)雜性示例設(shè)T(n)=

11、n2+4n，有f(n)=n2，則： n2 + 4n = O(n2)證明： 因為存在c=2，n0=4，使對于一切nn0，恒有 n2 +4n2 n2注意： f(n)越小，越接近T(n)401.2.2 算法的評價標(biāo)準(zhǔn)和評價方法 3時間復(fù)雜性都是n的平方階的又例：算法A的時間耗用函數(shù) T1(n)=20n2+100n 算法B的時間耗用函數(shù) T2(n)=0.5n23n+18于是 T1(n)=O(n2) T2(n)=O(n2)41常用階（由低到高）O(1) O(logn) O(n) O(n logn) O(n2) O(n3)O(nc)常數(shù)階最快對數(shù)階底數(shù)無關(guān)線性階很理想的階平方階c是常數(shù)，多項式階O(2n)

12、O(n!)指數(shù)階階乘階（無效算法）（均為有效算法）42示例某算法T(n)=2n，當(dāng)n=1000時，其工作量（執(zhí)行基本語句條數(shù)）將達(dá)到21000假定每執(zhí)行一條基本語句需要花費(fèi)1毫微秒（10-9秒）時間，那么解此問題共需要：設(shè)計算法時，應(yīng)當(dāng)選用有效算法，并且盡量設(shè)法降低它的時間耗用量，以提高算法的運(yùn)行速度 434. 最壞情況和平均情況 （1）為什么要區(qū)分兩種情況 有些算法因分支等因素，對不同的輸入數(shù)據(jù)（即使輸入數(shù)據(jù)量都是n）耗用時間會有所不同，而且往往相差很大為使評價更客觀，更有說服力，通常需要分幾種情況討論算法的時間性能在算法理論分析上，最常見的是分別計算出最壞情況下和平均情況下算法的時間復(fù)雜性

13、（也稱最壞性態(tài)和平均性態(tài)）44具有相同輸入數(shù)據(jù)量的不同輸入數(shù)據(jù)算法時間用量的最大值 用TW(n)表示（2） 最壞情況（worst-case） 說一個算法是“好”的，總是希望它在任何情況下運(yùn)行速度都快最壞情況下算法的時間性態(tài)可以表述算法的這一特征4. 最壞情況和平均情況 45對于所有相同輸入數(shù)據(jù)量的各種不同數(shù)據(jù)，算法耗用時間的“平均值”用TE(n)表示 （3）平均情況等概率：平均情況（average -case）加概率：期望情況（expected-case） 4. 最壞情況和平均情況 46（3）平均情況從實用角度看，有些算法遇到最壞情況的可能性極小極小，在大多數(shù)情況下是快的。算法的平均性態(tài)可以表

14、述算法的這一特征從最壞情況和平均情況兩個角度分析算法的時間性能，可以給算法作出更為客觀的評價 對于所有相同輸入數(shù)據(jù)量的各種不同數(shù)據(jù)，算法耗用時間的“平均值”用TE(n)表示 4. 最壞情況和平均情況 475. 算法的選用原則 當(dāng)數(shù)據(jù)量不大時，低階算法未必就快 例如，算法A1和A2的時間復(fù)雜性分別為 T1(n)=1000n 和 T2(n)=n2 雖然O(T1(n)1000時，A1好于A2 當(dāng)n1000時，A2好于A1，因為T2(n)T1(n)485. 算法的選用原則 總原則：能滿足客觀要求即可用需要考慮如下因素：1）算法實現(xiàn)的難易程度2）算法使用的次數(shù)，否實時處理 （如通信、天氣預(yù)報等）3）算法

15、運(yùn)行環(huán)境 輸入數(shù)據(jù)量的大小范圍491.2.2 算法的評價標(biāo)準(zhǔn)和評價方法 算法空間用量函數(shù)S(n)時空折中方案（space versus time trade-offs） 算法執(zhí)行時所需空間（占用內(nèi)存單元數(shù)）通常只計算輔助空間用量不計原始數(shù)據(jù)所占的空間 為了節(jié)省時間，先作“預(yù)處理”，多記一些信息（多占空間） 時空轉(zhuǎn)換501.2.3 計算時間復(fù)雜性的一般方法 1支配性語句度量法 其他語句花費(fèi)時間的總和將不超過這個語句花費(fèi)時間的常數(shù)倍用典型語句的執(zhí)行次數(shù)作為程序段花費(fèi)時間的階 起支配性作用511支配性語句度量法示例：for(i=1,c=0,s=a0;in;i+) 1. if(aia0) 2. c+;

16、3. s+=ai; 1，2，3：語句序號用于講解算法可選句1、3作為典型語句T(n) =O(n) 522分段計算法若一段耗時為O(f(n)另一段耗時為O(g(m)兩段共耗費(fèi)O(f(n)+O(g(m)=O(f(n)+g(m) 取最高階例 O(n2)+O(n)=O(n2) O(n)+O(n)=O(n) 533分層計算法分層計算，相乘，再化簡外層循環(huán)共執(zhí)行O(f(n)次內(nèi)層循環(huán)O(g(m)次兩層共執(zhí)行O(f(n)O(g(m)=O(f(n)g(m)次543分層計算法示意性程序1：for(i=0;in;i+) x=y=0; for(j=0;jai) x+=1; if(ajai) y+=1; printf

17、(%d,%dn,x,y); O(n) *O(n/2) =O(n2) 553分層計算法直接計算內(nèi)層總的執(zhí)行時間 例for(i=1;i=n;i+) for(j=1;j=i;j+) printf(%d,i*j); 564遞推式方法利用組合論知識，列出關(guān)于時間耗費(fèi)函數(shù)的遞歸方程（或遞歸不等式），通過求解遞歸方程，計算出時間復(fù)雜性示例：漢諾塔問題的時間耗費(fèi)。用T(n)表示搬動高度為n的塔所需的移動總次數(shù)575數(shù)學(xué)模型法 利用“便于”計算的數(shù)學(xué)模型，和復(fù)雜的數(shù)學(xué)演算（包括微分和積分運(yùn)算），計算T(n) 58內(nèi)容小結(jié)58第1.1節(jié)介紹了數(shù)據(jù)結(jié)構(gòu)和算法的概念、抽象數(shù)據(jù)類型其中，抽象數(shù)據(jù)類型雖然在程序設(shè)計實踐中

18、很重要，但不是本書的訓(xùn)練重點，屬于了解內(nèi)容和擴(kuò)展內(nèi)容對于數(shù)據(jù)結(jié)構(gòu)和算法的概念，也無須強(qiáng)記，理解即可59內(nèi)容小結(jié)59第1.2節(jié)，算法的存在形式分為描述形式和實現(xiàn)形式（即程序形式）描述形式簡單直觀，易于閱讀理解，又便于對算法分析評價，需要好好掌握程序形式往往過于繁雜，尤其是類的實現(xiàn)程序極為冗長，一般不需要全面掌握，當(dāng)然上機(jī)實驗是不可缺少的60內(nèi)容小結(jié)60第1.2節(jié)算法的評價標(biāo)準(zhǔn)和評價方法占有較大篇幅，既是重點，也是難點尤其是算法時間復(fù)雜性的計算方法難度較大，需要循序漸進(jìn)地學(xué)習(xí)逐步掌握61內(nèi)容小結(jié)61基本要求了解數(shù)據(jù)結(jié)構(gòu)和算法的概念、抽象數(shù)據(jù)類型的含義；掌握算法的表示形式、評價標(biāo)準(zhǔn)、最壞情況和平均情

19、況等內(nèi)容不要求全面掌握算法的時間復(fù)雜性一般計算方法，但在后續(xù)學(xué)習(xí)中能夠讀懂各章給出的計算步驟和計算結(jié)果62內(nèi)容小結(jié)62進(jìn)一步要求：了解抽象數(shù)據(jù)類型的一般實現(xiàn)方法；對于結(jié)構(gòu)簡單的算法能夠?qū)ζ溥M(jìn)行較為恰當(dāng)?shù)脑u價提高要求：掌握算法的時間復(fù)雜性一般計算方法，對于結(jié)構(gòu)簡單的算法能夠?qū)ζ溥M(jìn)行準(zhǔn)確評價應(yīng)用要求：掌握抽象數(shù)據(jù)類型的實現(xiàn)方法，對后續(xù)章節(jié)給出的數(shù)據(jù)結(jié)構(gòu)和算法能夠進(jìn)行類化處理63第1章 概述 2節(jié) 本 節(jié) 結(jié) 束數(shù)據(jù)結(jié)構(gòu)與算法64第2章 表結(jié)構(gòu) 1節(jié)第2章 表 結(jié) 構(gòu)內(nèi)容提要普通表結(jié)構(gòu)、受限的表結(jié)構(gòu)、近似表結(jié)構(gòu)、擴(kuò)展表結(jié)構(gòu)、用類實現(xiàn)表結(jié)構(gòu)的程序示例針對各結(jié)構(gòu)的特點、存儲方法、常見的運(yùn)算，給出相應(yīng)的處

20、理算法，分析其效率第2章 表 結(jié) 構(gòu)前兩節(jié)：普通線性表的順序存儲（順序表）和鏈?zhǔn)酱鎯Γㄦ湵恚?，是重點鏈表是重中之重，也是難點內(nèi)容提要第2章 表 結(jié) 構(gòu)2.3節(jié)棧和隊，只能在指定端點進(jìn)行插入刪除（受限的表結(jié)構(gòu)），常用、重要，難度不太大循環(huán)隊的進(jìn)退隊算法有難度內(nèi)容提要第2章 表 結(jié) 構(gòu)2.4節(jié) 矩陣和字符串與普通表結(jié)構(gòu)有共同處（近似表結(jié)構(gòu)）稀疏矩陣的轉(zhuǎn)置算法和相乘算法中使用的技術(shù)值得關(guān)注KMP算法則具有較大的難度BM算法和KR算法稍作了解即可內(nèi)容提要第2章 表 結(jié) 構(gòu)2.5節(jié) 散列表與普通表差距大，有點像具有非常大的實用價值，重點！散列表的性能分析難度較大，了解內(nèi)容提要第2章 表 結(jié) 構(gòu)2.6節(jié)廣

21、義表（擴(kuò)展表結(jié)構(gòu)），非重點內(nèi)容提要2.7節(jié)表結(jié)構(gòu)的類程序設(shè)計示例（3 個）引導(dǎo)大家如何進(jìn)行面向?qū)ο蟮某绦蛟O(shè)計實現(xiàn)標(biāo)準(zhǔn)數(shù)據(jù)結(jié)構(gòu)的類第2章 表 結(jié) 構(gòu)2.1 基本概念和順序表 2.1.1 基本概念 線性表（linear list）:具有n（n0）個數(shù)據(jù)結(jié)點（元素）的序列 A=(a1，a2，an)首結(jié)點和尾結(jié)點 表的長度 空表 前驅(qū)和后繼（左鄰和右鄰）有序表 1. 定義和示例示例學(xué)生成績單財務(wù)流水賬商品供貨單、庫存單2. 主要運(yùn)算 （1）查找（search）按關(guān)鍵字x查查找結(jié)果：成功，返回x的地址 不成功：返回?zé)o效地址按非關(guān)鍵字查結(jié)果：可能找出多個符合條件的結(jié)點2. 主要運(yùn)算 （2）插入（inser

22、t） 指定條件插入（比如，有序插入） 指定位置插入（插在表頭、表尾、第i個位置）無條件插入（隨便插在何處） 2. 主要運(yùn)算 （3）刪除（delete ） 刪除值為x的結(jié)點 刪除表頭結(jié)點、表尾結(jié)點、或第i個結(jié)點插入和刪除都是對表結(jié)構(gòu)的修改 查找、插入、刪除最基本、最常用 2. 主要運(yùn)算 （4）存?。╝ccess） （5）更新（update） （6）合并（merge） （7）分裂（split） （8）復(fù)制（copy） （9）排序（sorting） 3. 基本存儲方法 順序存儲（順序表）鏈?zhǔn)酱鎯Γㄦ湵恚?1）順序存儲 按結(jié)點在表中的次序依次存儲特點：結(jié)點的邏輯次序與物理次序一致 結(jié)點i的存儲地址公式

23、： c：首地址t：結(jié)點長度（占內(nèi)存單元數(shù)） 用高級語言描述順序存儲用數(shù)組存儲數(shù)組的一個元素便是一個存儲結(jié)點下標(biāo)作為結(jié)點的存儲地址（相對地址）1）順序存儲 單值結(jié)點示例 ：15以內(nèi)的素數(shù)存儲結(jié)構(gòu)圖式Prime=(2，3，5，7，11，13)1）順序存儲 單值結(jié)點示例 ：15以內(nèi)的素數(shù)存儲結(jié)構(gòu)圖式Prime=(2，3，5，7，11，13)多值結(jié)點示例 ：學(xué)生情況登記表結(jié)點結(jié)構(gòu) ：1）順序存儲 某班級的學(xué)生情況登記表2）鏈?zhǔn)酱鎯?值域（數(shù)據(jù)域） ：存儲表元素值 鏈域（指針域）：存儲后繼結(jié)點的存儲地址 單向鏈表的結(jié)點結(jié)構(gòu)表頭指針：指向鏈表的第一個結(jié)點的指針變量 最后一個結(jié)點的鏈域值為空（NULL） 一

24、個鏈表就是表頭指針和一串相繼鏈接的結(jié)點的總稱鏈表的邏輯結(jié)構(gòu)圖2）鏈?zhǔn)酱鎯?3）存儲結(jié)構(gòu)的封裝 將一個結(jié)構(gòu)的所有信息定義成一個存儲結(jié)構(gòu)增加程序的易讀性容易檢查程序錯誤易于擴(kuò)充 順序表的封裝定義list類型：typedef struct /定義表的存儲結(jié)構(gòu)類型 char list_namename_length; /表名稱 int length ; /表長度 element_type dN; /存儲表元素的數(shù)組 list /表的類型別名用list類型定義表變量team list team; 鏈表的封裝定義link_list類型：typedef struct char list_namename_l

25、ength;/表名稱域 int length;/表長度域 ptr head;/表頭指針域 link_list;/鏈表類型名4.數(shù)據(jù)結(jié)點的存儲方法 存儲一個結(jié)點時，要體現(xiàn)兩方面信息：結(jié)點的數(shù)值，結(jié)點之間的次序關(guān)系兩方面信息集中在一個存儲結(jié)點簡單明了，易于理解，便于操作適用于：結(jié)點較?。〝?shù)據(jù)域所占空間不大）表長較短（結(jié)點數(shù)目不多）表結(jié)構(gòu)變化不大（很少進(jìn)行插入刪除）4.數(shù)據(jù)結(jié)點的存儲方法 當(dāng)表長很大，結(jié)點很大，臃腫內(nèi)存中不能容納一個完整的線性表頻繁地在順序表中進(jìn)行插入刪除，大段大段的結(jié)點移動，影響速度存儲結(jié)點分成兩個：表結(jié)點：表示結(jié)點之間的次序關(guān)系數(shù)值結(jié)點：存儲結(jié)點的數(shù)據(jù)值表結(jié)點含有指向數(shù)值結(jié)點的指

26、針表結(jié)點變短，消除臃腫，只移動指向數(shù)值結(jié)點的指針。4.數(shù)據(jù)結(jié)點的存儲方法 當(dāng)表長很大，結(jié)點很大，臃腫內(nèi)存中不能容納一個完整的線性表頻繁地在順序表中進(jìn)行插入刪除，大段大段的結(jié)點移動，影響速度表結(jié)點存儲在線性表中，表結(jié)點變短，不臃腫數(shù)值結(jié)點存儲在數(shù)據(jù)區(qū)表結(jié)點含有指向數(shù)值結(jié)點的指針插入刪除表結(jié)點時，只移動指向數(shù)值結(jié)點的指針目錄存儲和索引目錄存儲 1）等長結(jié)點的目錄存儲目錄存儲結(jié)構(gòu)：目錄區(qū)、數(shù)據(jù)區(qū)目錄區(qū)：存儲表結(jié)點（目錄表，代替原線性表）數(shù)據(jù)區(qū)：存儲數(shù)值結(jié)點表結(jié)點中存儲數(shù)值結(jié)點在數(shù)據(jù)區(qū)中的存儲地址目錄表：順序表，或鏈表數(shù)據(jù)區(qū)：數(shù)值結(jié)點無序隨意存儲1）等長結(jié)點的目錄存儲目錄表是順序表的存儲方法目錄存儲結(jié)

27、構(gòu)：目錄區(qū)、數(shù)據(jù)區(qū)目錄區(qū)：存儲表結(jié)點（目錄表，代替原線性表）數(shù)據(jù)區(qū)：存儲數(shù)值結(jié)點表結(jié)點中存儲數(shù)值結(jié)點在數(shù)據(jù)區(qū)中的存儲地址存儲結(jié)構(gòu)包括：目錄表，數(shù)據(jù)區(qū)，自由隊列1）等長結(jié)點的目錄存儲目錄表是順序表的存儲方法存儲結(jié)構(gòu)定義：int am;/目錄表element_type dm;/數(shù)據(jù)區(qū)int avm,avtop; /自由隊列及其首指針m：存儲空間大小element_type：數(shù)據(jù)元素類型1）等長結(jié)點的目錄存儲目錄表是順序表的存儲方法圖示目錄表： int am;數(shù)據(jù)表 element_type dm;自由隊列及其首指針 int avm,avtop;自由隊列：輔助機(jī)構(gòu) 1）等長結(jié)點的目錄存儲自由隊列初始

28、化for(i=0;im;i+) avi=i; /所有結(jié)點都放入自由隊列（即進(jìn)棧）avtop=m;/自由隊列首指針初值2）不等長結(jié)點的目錄存儲（1）若結(jié)點長度差別不大，或短結(jié)點極少按照最長結(jié)點的大小將短結(jié)點“湊成”長結(jié)點變成等長結(jié)點（2）若結(jié)點長度參差不齊且差別較大可以采用“不等長結(jié)點的目錄存儲”方法將數(shù)據(jù)表改為數(shù)據(jù)區(qū)需要設(shè)計專門的“數(shù)據(jù)區(qū)管理程序”3）索引目錄存儲要點：目錄表中帶關(guān)鍵字變成索引目錄表 便于通過關(guān)鍵字訪問表元素 2.1.2 順序表的插入和刪除長度為n的順序表占據(jù)數(shù)組am的前n個單元：a0an-1（nm）1. 插入（插入元素x ） （1）無條件（不指定插入點）插在表尾最方便：an+

29、x;每插一個結(jié)點，只需用O(1)時間（2）指定位置插入ka5041126382i3i+197k-1m將x插在此處右移一位當(dāng)前表長n=k7ka504112638xi2i+139k-1m插入后，表長變成n=k+17ka5041126382i2i+139k-1m先移動成這樣，再插入x完成插入的程序段：for(i=n-1;x=0;i-)ai+1=ai;/邊查邊移ai=x; /插入x 共移動n-i個元素n+; /表長增1 時間復(fù)雜性O(shè)(n-i)ka20314263812131921k-1m找9的有序序位置21ka2031426389121319k-1m右移（3）有序插入（x=9)插入的時間復(fù)雜性 插在尾

30、部： T(n)=1 （最快） 插入ai處：T(n)=n-i （i=0插在表頭最慢） 插入前，必須判斷數(shù)組是否已經(jīng)占滿：if(n=m)返回空間已用完的信息; /由請求插入者進(jìn)行處理 else 執(zhí)行具體的插入操作;建議：使用動態(tài)數(shù)組避免產(chǎn)生溢出2.1.2 順序表的插入和刪除長度為n的順序表占據(jù)數(shù)組am的前n個單元：a0an-1（nm）2. 刪除（1）刪除指定結(jié)點指定元素值x，指定存儲位置i前者，則先找到x的位置（變成后者）刪除aika5041126382i3i+197k-1m刪除ai左移一位當(dāng)前表長n=k表長變?yōu)閚=k-1左移，抹去2 ，7變成多余的，最后變成：ka5041126383i9i+17

31、7k-1m2簡單刪除（指定位置） ka5041126382i3i+197k-1m刪除ai左移一位當(dāng)前表長n=k完成刪除的程序段：for(j=i; jn-1; j+) aj=aj+1; /左移，抹去ain-; /表長減1 共移動n-1-i個元素ka5041126383i9i+177k-1m表長變?yōu)閚=k-12簡單刪除（指定位置） ka5041126382i3i+197k-1m刪除ai左移一位當(dāng)前表長n=k完成刪除的程序段：for(j=i; jn-1; j+) aj=aj+1; /左移，抹去ain-; /表長減1 時間復(fù)雜性：O(n-1-i)O(n-i)ka5041126383i9i+177k-1

32、m表長變?yōu)閚=k-12.1.2 順序表的插入和刪除長度為n的順序表占據(jù)數(shù)組am的前n個單元：a0an-1（nm）2. 刪除（2）刪除非指定結(jié)點刪除任一個結(jié)點，不定刪哪個（罕見）刪除表尾結(jié)點最方便，只需要O(1)時間3插入刪除的效率分析 1）在表尾處插/刪，最好，T(n)=O(1)2）在表頭處插/刪，最壞情況，T(n)=O(n)3）平均情況，移動半數(shù)表元素 ，T(n)=O(n)4）如果表很長 ，頻繁插/刪，效率不高 5）僅適于下列情況之一：表長不大不做，或很少做插/刪 只在表的端點處插/刪6）順序存儲結(jié)構(gòu)簡單，空間利用率高2.1.3 順序表的查找 順序查找、二分查找（針對有序表） 1順序查找（s

33、equential search） 從表的一端，向另一端，逐個元素查看 從左至右 從右至左 查找起點查找終點 在a0至an-1中，查找值為x的結(jié)點的程序段 在程序前部位定義：#define NOTFOUND -1 /定義無效地址 （1）從左向右查（起點在左，終點在右）： for(i=0; i=0; i-) if (ai=x) return(i); return(NOTFOUND); 判斷兩個條件最大查找長度等于表長n，最壞情況：T(n)=O(n) 平均查找長度約等于n/2，平均情況：T(n)=O(n) 在a0至an-1中，查找值為x的結(jié)點的程序段 2使用監(jiān)督元的順序查找在查找終點預(yù)留一個空白結(jié)

34、點（監(jiān)督元）若從后向前查，a0作監(jiān)督元，a1到an 存儲表元素表頭監(jiān)督元0 1 2 i n-10 1 2 i n監(jiān)督位帶表頭監(jiān)督元的線性表順序查找算法 int SQsearch(element_type a , element_type x,int n) int i;1. i=n; /查找起點2. a0=x; /預(yù)置監(jiān)督元3. while(ai!=x) i-; /從右向左查4 return i ; 前面定義的元素類型語句編號性能分析 設(shè)查找結(jié)果，終止于ai處(0in)查找長度： 當(dāng)i=n時，查找最快（最好情況）當(dāng)i=0時（查找不成功），查找最慢最壞情況下：TW(n)=n+1 平均情況設(shè)查找第i

35、個結(jié)點的概率為pi對于所有成功的查找，平均查找長度： 若查找概率相等，pi=1/n，上式變?yōu)椋?結(jié)論： （1）當(dāng)n很大時，查找效率較低（2）常查的結(jié)點放在查找起點處（3）采用自動調(diào)頻技術(shù)3自動調(diào)頻查找若結(jié)點查找概率不等，將查找概率大的常用結(jié)點靠近查找起點，以減小平均查找長度，提高查找效率若各個結(jié)點的查找概率事先未知，可采用自動調(diào)頻技術(shù)，每查到一個結(jié)點，就將其換到查找起點，或向前移一位。經(jīng)過反復(fù)查找，經(jīng)常查找的結(jié)點就會聚集在查找起點附近4二分查找 （1）算法（略） （2）查找路線 查找結(jié)果： n種成功的 n+1種不成功的 例如，查找x=21的步驟 mid leftright 第一步：left=0

36、，right=11計算中值地址：mid=(0+11)/2=5第一次比較結(jié)果：xa5（2143）置right=mid-1=4 leftright mid 第二步：left=0，right=4計算中值地址：mid=(0+4)/2=2第一次比較結(jié)果：xa5（21a2（2112） 置left=mid+1=3 mid例如，查找x=21的步驟 leftright mid 第三步：left=3，right=4計算中值地址：mid=(3+4)/2=3第三次比較結(jié)果：x=a3查找成功，返回地址3 （下標(biāo)）left例如，查找x=21的步驟 mid leftright 第一步：left=0，right=11計算中值

37、地址：mid=(0+11)/2=5第一次比較結(jié)果：xa5（8343）置left=mid+1=6再如，查找x=83的步驟 leftright mid 第一次比較結(jié)果：xa5（21a8（8370） 置left=mid+1=9 midleftright mid 再如，查找x=83的步驟 第三步： left=9，right=11計算中值地址： mid=(9+11)/2=10第三次比較結(jié)果：xa10（8387） 置right=mid-1=9 leftright mid 再如，查找x=83的步驟 第三步： left=9，right=11計算中值地址： mid=(9+11)/2=10第三次比較結(jié)果：xa10

38、（83a9 （8381） 置left=mid+1=10 再如，查找x=83的步驟 第四步： left=9，right=9計算中值地址： mid=(9+9)/2=9第四次比較結(jié)果：xa9 （8381） 置left=mid+1=10，發(fā)現(xiàn)leftright 終止查找 leftright 再如，查找x=83的步驟算法2-1 二分查找算法int binary_search(element_type a , element_type x, int n) int left , right, mid;1. left=0; right=n-1; /定左右邊界指針2. while (left=right) /當(dāng)

39、待查段不空時 3. mid=(left+right)/2; / 計算中值地址mid 4. if(x=amid) return(mid); / 返回x的地址mid 5. if(xamid) right=mid-1; / 準(zhǔn)備查前半段6. else left=mid+1; /準(zhǔn)備查后半段 7. return(NOTFOUND); /未找到x，返回?zé)o效地址 二分查找算法分析設(shè)T(n)是在長度為n的有序表中二分查找元素x的查找長度每查找一次，查找范圍縮小一半T(n)的遞推公式：T(1)=1T(n)1) =1+log2n=O(log2n)最壞情況：TW(n)O(logn) 平均情況：TE(n)O(log

40、n) 二分查找算法的判定樹（decision tree） 查找x=1824 14 53 174376 2 104 35 0 6 1 5 3 4 2 查找x=43查找成功的平均查找長度？判定樹的用處 （1）驗證查找算法的正確性能否歷盡所有的可能情況（成功和不成功）（2）便于計算時間復(fù)雜性 最壞情況，樹的高度 平均情況，結(jié)點平均層數(shù)（3）判斷算法的最優(yōu)性 是否存在“冗余”的比較二分查找算法的條件特點：基于計算中值地址 三要素：順序、有序、等長順序：表必須是順序存儲的 有序：表必須是有序的 等長：結(jié)點必須是等長的 135第2章 表結(jié)構(gòu) 1節(jié) 本 節(jié) 結(jié) 束數(shù)據(jù)結(jié)構(gòu)與算法136第2章 表結(jié)構(gòu) 2節(jié)(續(xù)

41、)1. 存儲狀態(tài)和邏輯狀態(tài) 用定長數(shù)組存儲的鏈表 2.2.5 靜態(tài)鏈表 1. 存儲狀態(tài)和邏輯狀態(tài)示例 存儲狀態(tài)（物理結(jié)構(gòu)） 存儲狀態(tài) 1. 存儲狀態(tài)和邏輯狀態(tài)邏輯狀態(tài) 自由隊列 單向簡單鏈表 2自由隊列的建立和管理算法2-12 自由隊列的建立和管理算法由4部分組成takoff和takeback的功能相當(dāng)于庫函數(shù)malloc和free2自由隊列的建立和管理（1）有關(guān)變量的定義部分#define N 1000/存儲空間大小#define NIL -1/空鏈域值#define OVER -2/自由結(jié)點用完標(biāo)記typedef int element_type;/元素類型typedef struct/定

42、義結(jié)點類型 element_type data;/值域 int next; /鏈域 slist; /結(jié)點類型名slist aN; /存儲靜態(tài)鏈表的數(shù)組int av; /自由隊列首指針2自由隊列的建立和管理（2）自由隊列初始化函數(shù) void initial( ) /數(shù)組a和av均為整體量 int i;1. for(i=0;in-1;i+)ai.next=i+1;2. an-1.next=NIL;3. av=0; /自由隊列首指針初值 2自由隊列的建立和管理（3）分配結(jié)點函數(shù) int takeoff( ) int i;if(av=NIL)return OVER; /自由隊列已空，返回溢出標(biāo)記5.

43、i=av;/摘下首結(jié)點6. av=aav.next;/修改首指針7. return i;/返回所分配的結(jié)點下標(biāo)i 2自由隊列的建立和管理（4）回收結(jié)點函數(shù) void takeback(int p) ap.next=av;/將釋放的結(jié)點插在自由隊列首部9. av=p; /修改首指針 （1）插入p=takeoff(); if (p=OVER) exit (OVER); ap.data=x; ap.next=head; /插在表頭head=p; 3插入和刪除操作 （1）插入p=takeoff(); if (p=OVER) exit (OVER); ap.data=x; ap.next=aq.next

44、; /插在q的右側(cè)aq.next=p; 3插入和刪除操作 （2）刪除p=head; /刪除表頭head=ahead.next;takeback(p); 3插入和刪除操作 （2）刪除p=aq.next; /刪除q的后繼aq.next=ap.next;takeback(p); 3插入和刪除操作 4. 靜態(tài)鏈表的應(yīng)用 1）多表共享空間實現(xiàn)多表共享空間有順序表法和鏈表法順序存儲下的多表共享空間設(shè)m個表共同存儲在數(shù)組an中可以預(yù)先將存儲空間分成m段（子空間）每一段存儲一個表，各表分別在自己的子空間中自由增長在一個表中插入刪除，多數(shù)情況下只引起子空間元素移動當(dāng)某個表因插入超出子空間時，就引起“周圍”表的元

45、素移動從而影響處理速度4. 靜態(tài)鏈表的應(yīng)用 1）多表共享空間鏈?zhǔn)酱鎯ο碌亩啾砉蚕砜臻g將數(shù)組an定義為靜態(tài)鏈表的存儲機(jī)構(gòu)，結(jié)點帶有鏈域每個表都采用鏈?zhǔn)浇Y(jié)構(gòu)共同存儲在數(shù)組an中每個表都可以在整個空間中自由增長只要元素總數(shù)不超過n，就不會發(fā)生溢出無論在哪個表中進(jìn)行插入刪除，都不需移動元素從而提高了速度當(dāng)然，由于增加了鏈域，所以空間開銷要大些4. 靜態(tài)鏈表的應(yīng)用 1）多表共享空間鏈表組共享空間n個元素的集合S被分割成m個子集每個元素都在且只在一個子集中可能將元素從一個子集移入另一個子集或?qū)蓚€子集拼接成一個子集每個子集都是動態(tài)變化的有時n個元素全都“跑”到一個子集中4. 靜態(tài)鏈表的應(yīng)用 2）省略數(shù)據(jù)域

46、的靜態(tài)鏈表條件：元素值都是0到n-1之間的整數(shù)只用數(shù)組nextn存儲靜態(tài)鏈表數(shù)組的下標(biāo)兼作元素的值編號為0到n-1的n只猴子排成一個圓圈反復(fù)循環(huán)地順時針1至m報數(shù)凡報數(shù)為m者退到圈外，最后退出者便是猴王按退出的次序輸出這些猴子的編號求解程序 void Josephus( ) int nextn, i,j,k;1. for(i=0; in-1;i+) nexti=i+1;2. nextn-1=0;3. j=n-1;/j指向報數(shù)起點的前驅(qū)4. for(i=0;in;i+)/每循環(huán)一次，退出一個猴子5. for(k=1;km;k+)j=nextj;/報數(shù)m-1個6. printf(%4d,nextj

47、);/輸出j的后繼7. nextj=nextnextj;/刪除j的后繼 13 個猴子1至 5 報數(shù)， 輸出結(jié)果：5 10 2 8 1 9 4 13 12 3 7 11 63） 單鏈域的雙向鏈表 鏈域（Link）結(jié)點的前驅(qū)結(jié)點和后繼結(jié)點地址“按位異或”運(yùn)算的結(jié)果值 按位異或運(yùn)算符“”“”的運(yùn)算性質(zhì)滿足交換律、結(jié)合律具有自逆性，即“”與“”互逆滿足下列關(guān)系：ff=0(fs)f=s(fs)s=f3）單鏈域的雙向鏈表 鏈域和指針的關(guān)系ap2.Link=p1p3根據(jù)“”的自逆性： p1=ap2.Linkp3 p3=ap2.Linkp1只要有兩個相鄰結(jié)點的指針便可以向左右兩個方向搜索 3）單鏈域的雙向鏈表

48、插入操作將q指向的結(jié)點插在p2和p3之間的程序段為： aq.link=p2p3; ap2.link=ap2.linkp3q; ap3.link=ap3.linkp2q;刪除操作刪除p2所指向結(jié)點的程序段： ap1.link=ap1.linkp2p3; ap3.link=ap3.linkp2p1;4）存儲空間管理不等長結(jié)點的存儲空間管理方法即動態(tài)存儲分配（dynamic storage allocation）方法 經(jīng)多次分配和回收長度不等長的存儲空間整個存儲區(qū)將被分割成長短不一的若干段已占用區(qū)（reseverd）和空白區(qū)（free）4）存儲空間管理設(shè)計管理策略時，需要考慮：當(dāng)申請分配長度為n的存

49、儲區(qū)時，如何尋找空白區(qū)并從中截取一段進(jìn)行分配當(dāng)釋放存儲區(qū)時，如何將其變成空白的經(jīng)多次分配和回收長度不等長的存儲空間整個存儲區(qū)將被分割成長短不一的若干段已占用區(qū)（reseverd）和空白區(qū)（free）使用一個靜態(tài)加頭雙向循環(huán)鏈表（空白區(qū)鏈表）將所有的空白區(qū)鏈接起來 4）存儲空間管理空白區(qū)鏈表圖示：4）存儲空間管理結(jié)點結(jié)構(gòu)含義空白區(qū)結(jié)構(gòu) 已用區(qū)結(jié)構(gòu) 4）存儲空間管理分配結(jié)點當(dāng)程序a申請長度為n的存儲空間時，沿鏈表搜索選出一個長度為m（mn）的空白區(qū)進(jìn)行分配若找不到這樣的自由區(qū)，本次分配失敗等待回收大結(jié)點后重新試分配1）若m比n大得很多，則從底部截取長度為n的一段進(jìn)行分配，原區(qū)長度變?yōu)閙-n2）若m

50、n+，就將其從鏈表中刪除，將整個區(qū) 分配給a，防止把內(nèi)存切成長度的無用小碎片 是一個小常數(shù)4）存儲空間管理3）三種分配原則：最先分配、最佳分配，最大分配最先分配 沿鏈表搜索，分配最先碰到的空白區(qū)最佳分配 尋找長度大于或等于n的最小空白區(qū)最大分配 尋找長度大于或等于n的最大空白區(qū)三種分配原則各有優(yōu)缺點其中，最先分配原則最常用，也最容易實現(xiàn)4）存儲空間管理回收結(jié)點當(dāng)程序釋放地址為p的存儲區(qū)時檢查p的上下鄰區(qū)（指地址相鄰）是否空白若為空白，則合并之合并是為了避免內(nèi)存被切得過碎上下鄰都非空白：將p插在空白區(qū)鏈表中，并修改p結(jié)點的各域的值上鄰空白，下鄰非空白：將p接到上鄰的下部，將二者合并并修改上鄰結(jié)點

51、的size，address和ltag域 4）存儲空間管理上鄰非空白，下鄰空白：將p接到下鄰的上部，并修改下鄰結(jié)點的ftag，size，Llink，Rlink，address和ltag域修改該結(jié)點鏈表中的前驅(qū)、后繼結(jié)點的鏈域上下鄰都空白：將p和下鄰都接到上鄰，將三者合并修改上鄰結(jié)點的size和address域并在鏈表中刪除下鄰結(jié)點 本 節(jié) 結(jié) 束166第2章 表結(jié)構(gòu) 2節(jié)數(shù)據(jù)結(jié)構(gòu)與算法167第2章 表結(jié)構(gòu) 2節(jié)2.2 鏈表2.2.1 基本概念和鏈操作方法 鏈表（linked list）的概念是線性表的一種存儲形式每個表元素對應(yīng)鏈表的一個結(jié)點（含值域和鏈域）值域（value field）用來存儲表

52、元素值 鏈域（link field）用來存儲相鄰結(jié)點的地址 表尾結(jié)點的鏈域值為空（NULL，即常數(shù)0）用首指針（如，變量head）指向第一個結(jié)點鏈表就是表頭指針和一串相繼鏈接的結(jié)點的總稱鏈表圖示 一般形式 head張王李趙陳簡化形式 head張王李趙陳結(jié)點和指針的類型定義typedef int element_type; /值域類型typedef struct linkednode /結(jié)點類型 element_type data; /值域 struct linkednode *next; /鏈域 snode, *ptr; /結(jié)點類型名snode和指針類型名ptr ptr head,p,q; /

53、 定義指針類型變量 類型struct linkednode * 與類型ptr等價都是指向snode的指針類型1結(jié)點的申請和釋放編譯預(yù)處理命令：#include 通過調(diào)用文件malloc.h中的動態(tài)存儲分配函數(shù) malloc產(chǎn)生結(jié)點（動態(tài)結(jié)點）malloc()的典型用法 p=(ptr)malloc(sizeof(snode)；含義：產(chǎn)生一個結(jié)點動態(tài)分配的變量 將結(jié)點的地址值轉(zhuǎn)換成ptr類型賦給指針變量p若分配失敗，返回NULL NULL是值為0的指針常量，無效地址結(jié)點的引用p-表示p所指向的結(jié)點 p-就是結(jié)點名（變量名） p-data：結(jié)點的值域 等價于 (*p).datap-next：結(jié)點的鏈

54、域 等價于 (*p).nextC+的new運(yùn)算符一般格式 new 結(jié)點類型名；語句 ： p=new snode; 等價于 p=newsnode();也等價于 p=(ptr)malloc(sizeof(snode);“廢結(jié)點”的回收 調(diào)用函數(shù)free(p) 例如： free(p)；釋放后，變量p-不復(fù)存在對p-的操作將變成“無意義”C+中用delete運(yùn)算符回收例： delete p ;2結(jié)點和指針的關(guān)系 p的指向關(guān)系不確定不能引用p- ！2結(jié)點和指針的關(guān)系 可以引用p- 2結(jié)點和指針的關(guān)系 p的指向關(guān)系“失效”不要引用p- ！2結(jié)點和指針的關(guān)系 不能引用p- ，否則異常終止 2結(jié)點和指針的關(guān)系

55、 P原來指向的結(jié)點被“忘記了 ”找不回來了 ！誤操作引起的3結(jié)點的連接讓前驅(qū)結(jié)點的鏈域指向后繼結(jié)點 若p和q指向兩個結(jié)點 p-和q-用語句： q-next=p; 將結(jié)點p-連接到q-結(jié)點的后面 連接關(guān)系圖示執(zhí)行下列程序段一：p=new snode；p-data=550；p-next=NULL；q=new snode; q-data=850； q-next=NULL；p-next=q；修改程序段一：p=new snode；p-data=550；p-next=NULL；q=new snode; q-data=850； q-next=NULL；q=p；/修改處若執(zhí)行下列程序段二：p=new snod

56、e; p-data=123;p-next=new snode; p-next-data=219；q=p-next; q-next=NULL; p-data=q-data；結(jié)點的整體賦值*p=*q ，相當(dāng)于執(zhí)行： p-data=q-data； p-next=q-next；修改程序段二后：p=new snode; p-data=123;p-next=new snode; p-next-data=219；q=p-next; q-next=NULL; *p=*q; /修改處4插入結(jié)點基本操作：局部的修改結(jié)點的鏈域 （1） 插在表頭p-next=head;head=p;（2）插在中間插入語句：p-nex

57、t=q-next;q-next=p;5刪除結(jié)點基本操作：局部的修改結(jié)點的鏈域 q=head;head=head-next;free(q); （1）刪除表頭點 （2）刪除非表頭結(jié)點p=q-next;q-next=p-next; free(p); 鏈表的特點特點：（1）結(jié)點地址不連續(xù)（2）插入/刪除不移動結(jié)點，耗時為O(1)（3）用于動態(tài)管理核心：（1）使用指向結(jié)點（結(jié)構(gòu)類型）的指針（2）執(zhí)行期間，調(diào)用動態(tài)存儲管理函數(shù) 產(chǎn)生結(jié)點、回收結(jié)點 6. 鏈表的種類（1）按結(jié)點產(chǎn)生方式靜態(tài)動態(tài)（2）按結(jié)點鏈域個數(shù)單向鏈表（singly linked lists） 雙向鏈表（doubly linked lis

58、ts）雙向鏈表結(jié)點結(jié)構(gòu)分類方法6. 鏈表的種類（3）按是否帶附加結(jié)點純鏈表不帶附加結(jié)點加頭鏈表帶附加表頭結(jié)點加尾鏈表帶附加表尾結(jié)點加頭尾鏈表既帶頭又帶尾（4）按是否循環(huán)循環(huán)鏈表（circularly linked lists） 非循環(huán)鏈表附加結(jié)點往往用作監(jiān)督元結(jié)點（存儲特殊值）6. 鏈表的種類鏈表命名： 鏈表：動態(tài)/靜態(tài) 紅字表示可以省略如果強(qiáng)調(diào)，則不省略：單向/雙向 ：無/加頭/加尾/加頭尾 ：無/無序/有序：簡單/非循環(huán)/循環(huán) 無表示沒有此項簡單表示既不帶附加結(jié)點又非循環(huán)7. 常用種類示例 （1）加頭鏈表 插/刪方便7. 常用種類示例 （2）加尾鏈表 查找方便7. 常用種類示例 （3）單向

59、循環(huán)鏈表 可循視一周7. 常用種類示例 （4）單向加頭循環(huán)鏈表 兼有二者優(yōu)點7. 常用種類示例 （5）雙向簡單鏈表 可以向左右搜索7. 常用種類示例 （6）雙向循環(huán)鏈表 一種過度形式7. 常用種類示例 （7）雙向加頭循環(huán)鏈表 一種完善形式2.2.2 鏈表的構(gòu)造和遍歷 算法2-2 構(gòu)造鏈表的通用算法（文字?jǐn)⑹鲂问剑┎襟E1）構(gòu)造“空鏈表”步驟2）讀入第一個元素值步驟3）當(dāng)讀入的元素值不是“輸入結(jié)束標(biāo)記”時 循環(huán)執(zhí)行步驟47步驟4）申請一個新結(jié)點步驟5）將讀入的元素值存入新結(jié)點的值域步驟6）將新結(jié)點“插在”鏈表中步驟7）讀入“下一個”元素值，轉(zhuǎn)步驟3步驟8）構(gòu)造完畢，返回首指針1構(gòu)造鏈表的通用算法

60、構(gòu)造簡單單向鏈表2向前插入法 示例算法之一：算法2-3 算法2-3 向前插入法構(gòu)造簡單鏈表的算法ptr creatlinkedA( ) ptr head, p; element_type x ; 1. head=NULL; /將表頭指針置空2. scanf(%d, &x); /讀入第一個元素3. while (x!=End_elm) /當(dāng)讀的不是結(jié)束標(biāo)記時循環(huán)4. p=new snode; /申請一個存儲結(jié)點5. p-data=x; /置結(jié)點的值域6. p-next=head; /插在表頭處7. head=p; /表頭指針指向新結(jié)點8. scanf(%d, &x); /讀入下一個元素 9. r