數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)與習(xí)題

數(shù)據(jù)結(jié)構(gòu)與算法復(fù)習(xí)與習(xí)題解析第一講數(shù)據(jù)結(jié)構(gòu)與算法概述了解數(shù)據(jù)結(jié)構(gòu)有關(guān)概念的含義，特別是數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)之間的關(guān)系；（重點(diǎn)）熟悉類C語言的書寫規(guī)范；了解計(jì)算算法時(shí)間復(fù)雜度的方法。（難點(diǎn)）12/04/20242數(shù)據(jù)結(jié)構(gòu)的定義按某種邏輯關(guān)系組織起來的一批數(shù)據(jù)（或稱帶結(jié)構(gòu)的數(shù)據(jù)元素的集合）應(yīng)用計(jì)算機(jī)語言并按一定的存儲(chǔ)表示方式把它們存儲(chǔ)在計(jì)算機(jī)的存儲(chǔ)器中，并在其上定義了一個(gè)運(yùn)算的集合?；靖拍詈托g(shù)語【數(shù)據(jù)】是對(duì)信息的一種符號(hào)表示。是可以輸入計(jì)算機(jī)中，

能被計(jì)算機(jī)識(shí)別處理和輸出的一切符號(hào)集合?！緮?shù)據(jù)元素】是數(shù)據(jù)的基本單位，在計(jì)算機(jī)中通常作為一個(gè)

整體進(jìn)行考慮和處理。也稱為記錄?！緮?shù)據(jù)項(xiàng)】一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成。是數(shù)據(jù)不

可分割的最小單位。【數(shù)據(jù)對(duì)象】是性質(zhì)相同的數(shù)據(jù)元素的集合。是數(shù)據(jù)的一個(gè)

子集。12/04/20244【數(shù)據(jù)結(jié)構(gòu)】相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)

元素的集合計(jì)算機(jī)如何解決問題12/04/20245問題機(jī)外表示處理要求邏輯結(jié)構(gòu)基本運(yùn)算數(shù)學(xué)模型存儲(chǔ)結(jié)構(gòu)編程實(shí)現(xiàn)實(shí)現(xiàn)建模求精研究數(shù)據(jù)結(jié)構(gòu)是為了幫計(jì)算機(jī)解決問題！數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容12/04/20246【數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面研究?jī)?nèi)容】具體來說，數(shù)據(jù)結(jié)構(gòu)包含三個(gè)方面的內(nèi)容，即數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和對(duì)數(shù)據(jù)所施加的運(yùn)算（操作）。

數(shù)據(jù)的邏輯結(jié)構(gòu)（面向人類）

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（面向計(jì)算機(jī)）

數(shù)據(jù)的運(yùn)算（操作）：檢索、排序、插入、刪除、修改等

線性結(jié)構(gòu)

非線性結(jié)構(gòu)順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)線性表?xiàng)ｊ?duì)列樹形結(jié)構(gòu)圖形結(jié)構(gòu)散列存儲(chǔ)索引存儲(chǔ)串及數(shù)組四種基本邏輯結(jié)構(gòu)12/04/20247【集合】——數(shù)據(jù)元素間除了“同屬于一個(gè)集合”外，無其他關(guān)系?！揪€性結(jié)構(gòu)】——

1對(duì)1的關(guān)系比如線性表、棧、隊(duì)列?！緲湫谓Y(jié)構(gòu)】——

1對(duì)多的關(guān)系比如樹?！緢D形結(jié)構(gòu)】——多對(duì)多的關(guān)系比如圖。數(shù)據(jù)結(jié)構(gòu)與算法算法與數(shù)據(jù)結(jié)構(gòu)關(guān)系密切選擇的數(shù)據(jù)結(jié)構(gòu)是否恰當(dāng)直接影響算法的效率；而數(shù)據(jù)結(jié)構(gòu)的優(yōu)劣由算法的執(zhí)行來體現(xiàn)?！八惴?數(shù)據(jù)結(jié)構(gòu)=程序”算法!=程序算法是供人閱讀的，程序是讓機(jī)器執(zhí)行的算法用計(jì)算機(jī)語言實(shí)現(xiàn)時(shí)就是程序程序不具有算法的有窮性算法的概念算法是解決某個(gè)特定問題的求解步驟的描述。算法在計(jì)算機(jī)中表現(xiàn)為指令的有限序列，每條指令表示一個(gè)或多個(gè)操作。計(jì)算機(jī)對(duì)數(shù)據(jù)的操作可以分為數(shù)值性和非數(shù)值性兩種類型。在數(shù)值性操作中主要進(jìn)行的是算術(shù)運(yùn)算；而在非數(shù)值性操作中主要進(jìn)行的是檢索、排序、插入、刪除等等。程序不等于算法：計(jì)算機(jī)程序是算法的具體實(shí)現(xiàn)。12/04/20249（1）有窮性：一個(gè)算法必須在執(zhí)行有窮步之后結(jié)束。（2）確定性：算法中的每一步，必須有確切的含義，在他人理解時(shí)不會(huì)產(chǎn)生二義性。（3）可行性：算法中描述的每一步操作都可以通過已有的基本操作執(zhí)行有限次實(shí)現(xiàn)。（4）輸入：一個(gè)算法應(yīng)該有零個(gè)或多個(gè)輸入。（5）輸出：一個(gè)算法應(yīng)該有一個(gè)或多個(gè)輸出。這里所說的輸出是指與輸入有某種特定關(guān)系的量。算法的性質(zhì)算法設(shè)計(jì)的要求正確性（四個(gè)境界）沒有語法錯(cuò)誤對(duì)于合法的輸入數(shù)據(jù)能夠產(chǎn)生滿足要求的輸出對(duì)于非法的輸入數(shù)據(jù)能夠得出滿足規(guī)格說明的結(jié)果對(duì)于任何測(cè)試數(shù)據(jù)都有滿足要求的輸出結(jié)果可讀性：便于閱讀、理解和交流健壯性：不合法數(shù)據(jù)也能合理處理時(shí)間效率高和存儲(chǔ)量低12/04/202411算法效率的度量方法事后統(tǒng)計(jì)方法通過設(shè)計(jì)好的測(cè)試程序和數(shù)據(jù)，利用計(jì)算機(jī)測(cè)量其運(yùn)行時(shí)間。缺陷：需要先編寫程序；和計(jì)算機(jī)軟硬件相關(guān)；和測(cè)試數(shù)據(jù)相關(guān)。事前分析估算方法（我們的選擇）依據(jù)統(tǒng)計(jì)方法對(duì)算法進(jìn)行估算。m=f(n)，m是語句總的執(zhí)行次數(shù)，n是輸入的規(guī)模。和問題輸入規(guī)模相關(guān)，獨(dú)立于程序設(shè)計(jì)語言和計(jì)算機(jī)軟硬件

12/04/202412算法時(shí)間復(fù)雜度（重點(diǎn)）12/04/202413在進(jìn)行算法分析時(shí)，語句的總執(zhí)行次數(shù)T(n)是關(guān)于問題規(guī)模n的函數(shù)，進(jìn)而分析T(n)隨n的變化情況并確定T(n)的數(shù)量級(jí)。算法的時(shí)間復(fù)雜度，也就是算法的時(shí)間量度，用“大O記法”記作：T(n)=O(f(n))。由此得到的T(n)的數(shù)量級(jí)叫“大O階”。它表示隨問題規(guī)模n的增大，算法執(zhí)行時(shí)間增長(zhǎng)率和f(n)的增長(zhǎng)率相同，稱作算法的漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。其中f(n)是問題規(guī)模n的某個(gè)函數(shù)。一般情況下，T(n)增長(zhǎng)越慢，算法越優(yōu)。大O階的數(shù)學(xué)定義

當(dāng)n→∞時(shí)，有f(n)/g(n)=常數(shù)≠0，則稱函數(shù)f(n)與g(n)同階,或者說，f(n)與g(n)同一個(gè)數(shù)量級(jí)，記作

f(n)=O(g(n))

稱上式為算法的時(shí)間復(fù)雜度,或稱該算法的時(shí)間復(fù)雜度為O(g(n))。其中,n為問題的規(guī)模(大小)的量度。若lim(f(n)/g(n))=lim((2n3+3n2+2n+1)/n3)

=2n→∞n→∞則算法的時(shí)間復(fù)雜度為O(n3)算法空間復(fù)雜度12/04/202415

算法的空間復(fù)雜度通過計(jì)算算法所需的存儲(chǔ)空間實(shí)現(xiàn)，算法空間復(fù)雜度的計(jì)算公式記作：S(n)=O(f(n))，其中，n為問題的規(guī)模，f(n)為語句關(guān)于n所占存儲(chǔ)空間的函數(shù)。

我們主要討論時(shí)間復(fù)雜度問題。例題解析【例1】數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中有幾種表示方法？各有什么特點(diǎn)？答：四種表示方法（1）順序存儲(chǔ)方式。數(shù)據(jù)元素順序存放，每個(gè)存儲(chǔ)結(jié)點(diǎn)只含一個(gè)元素。存儲(chǔ)位置反映數(shù)據(jù)元素間的邏輯關(guān)系。存儲(chǔ)密度大，但有些操作（如插入、刪除）效率較差。（2）鏈?zhǔn)酱鎯?chǔ)方式。每個(gè)存儲(chǔ)結(jié)點(diǎn)除包含數(shù)據(jù)元素信息外還包含一組（至少一個(gè)）指針。指針反映數(shù)據(jù)元素間的邏輯關(guān)系。這種方式不要求存儲(chǔ)空間連續(xù)，便于動(dòng)態(tài)操作（如插入、刪除等），但存儲(chǔ)空間開銷大（用于指針），另外不能折半查找等。（3）索引存儲(chǔ)方式。除數(shù)據(jù)元素存儲(chǔ)在一地址連續(xù)的內(nèi)存空間外，尚需建立一個(gè)索引表，索引表中索引指示存儲(chǔ)結(jié)點(diǎn)的存儲(chǔ)位置（下標(biāo)）或存儲(chǔ)區(qū)間端點(diǎn)（下標(biāo)），兼有靜態(tài)和動(dòng)態(tài)特性。（4）散列存儲(chǔ)方式。通過散列函數(shù)和解決沖突的方法，將關(guān)鍵字散列在連續(xù)的有限的地址空間內(nèi)，并將散列函數(shù)的值解釋成關(guān)鍵字所在元素的存儲(chǔ)地址，這種存儲(chǔ)方式稱為散列存儲(chǔ)。其特點(diǎn)是存取速度快，只能按關(guān)鍵字隨機(jī)存取，不能順序存取，也不能折半存取。12/04/202416例題解析【例2】有下列運(yùn)行時(shí)間函數(shù)：（1）T1(n)=1000;（2）T2(n)=n2n;（3）T3(n)=3n3+100n2+n+1;分別寫出相應(yīng)的大O表示的運(yùn)算時(shí)間答：(1)O(1)(2)O(n2)(3)O(n3)12/04/202417例題解析【例3】已知如下程序段for(i=n;i>0;i--){ {語句1}x=x+1; {語句2}for(j=n;j>=i;j--) {語句3}y=y+1; {語句4}}語句1執(zhí)行的頻度為_____________；語句2執(zhí)行的頻度為_____________；語句3執(zhí)行的頻度為_____________；語句4執(zhí)行的頻度為_____________。答：（1）n+1（2）n（3）n(n+1)/2+1（4）n(n+1)/2【例3】已知如下程序段inti=1;//①的頻度是1

while(i<=n)

i=i*3;//②求該程序的時(shí)間復(fù)雜度是多少？解：設(shè)語句②的頻度是f(n),則：3^f(n)<=n;f(n)<=log3n

取最大值f(n)=log3n,T(n)=O(log3n)第二講

線性表(順序表和鏈表及其應(yīng)用)線性結(jié)構(gòu)的定義和特點(diǎn)在數(shù)據(jù)元素的非空有限集中，有且僅有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)只有一個(gè)直接前趨和一個(gè)直接后繼。簡(jiǎn)言之，線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是

一對(duì)一。線性結(jié)構(gòu)包括線性表、堆棧、隊(duì)列、字符串、數(shù)組等等，其中，最簡(jiǎn)單、最常用的是線性表。線性表的存儲(chǔ)方法順序存儲(chǔ)：邏輯上相鄰物理上一定相鄰鏈?zhǔn)酱鎯?chǔ)：邏輯上相鄰物理上不一定相鄰順序表順序表——線性表的順序存儲(chǔ)表示順序存儲(chǔ)——用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的元素，可通過數(shù)組來實(shí)現(xiàn)。（邏輯上相鄰物理上一定相鄰）

LOC(ai

)=LOC(a1)+(i-1)

len（a1為首元素，len為單個(gè)元素占用空間長(zhǎng)度）順序存儲(chǔ)的優(yōu)點(diǎn)可以隨機(jī)存取表中任一元素O(1)；存儲(chǔ)空間使用緊湊順序存儲(chǔ)的缺點(diǎn)在插入元素時(shí)平均需要移動(dòng)n/2個(gè)元素，刪除某一元素時(shí)，平均需要移動(dòng)n-1/2個(gè)元素。算法的平均時(shí)間復(fù)雜度為O(n)預(yù)先分配空間需按最大空間分配，利用不充分;表容量難以擴(kuò)充12/04/202421學(xué)習(xí)重點(diǎn)：各種查找所基于的基本思想。順序表因引設(shè)置了監(jiān)視哨使查找效率大大提高。有序表的平均查找長(zhǎng)度不超過樹的深度，其判定樹是唯一的。索引順序查找綜合了上述二者的優(yōu)點(diǎn)，既能較快速的查找，又能適應(yīng)動(dòng)態(tài)變化的要求。各種排序所基于的基本思想。在“最好”和“最差”情況下，排序性能的分析，是否是穩(wěn)定排序的結(jié)論。對(duì)每種排序方法的學(xué)習(xí)，應(yīng)掌握其本質(zhì)（排序所基于的思想），熟練掌握手工模擬各種排序的過程。熟練掌握線性表查找和排序算法的思想和時(shí)間復(fù)雜性。查找基本概念：表/記錄/關(guān)鍵字/靜態(tài)查找表/動(dòng)態(tài)查找表/平均查找長(zhǎng)度順序表查找和“哨兵”有序查找：折半查找/插值查找/斐波那契查找線性索引：稠密索引/分塊索引/倒排索引二叉排序樹/平衡二叉樹：構(gòu)建/插入/刪除/保持平衡B-樹/B+樹：構(gòu)建/插入/刪除操作散列表：散列函數(shù)的選擇和處理沖突的方法例題解析設(shè)有序表為(a,b,c,d,e,f,g,h,i,j,k,p,q)，請(qǐng)分別畫出對(duì)給定值a,g和n進(jìn)行折半查找的過程。12/04/202424【答】例題解析構(gòu)造有1-12元素的二分查找的判定樹，并求解下列問題：（1）各元素的查找長(zhǎng)度最大是多少？（2）查找長(zhǎng)度為1、2、3、4的元素各有多少？具體是哪些元素？（3）查找第5個(gè)元素依次要比較哪些元素？【答】12個(gè)元素的判斷樹如下圖所示：12/04/202425653912241171810（1）最大查找長(zhǎng)度是樹的深度4。（2）查找長(zhǎng)度為1的元素有1個(gè)，為第6個(gè)，查找長(zhǎng)度為2的元素有2個(gè)，為第3個(gè)和第9個(gè)，查找長(zhǎng)度為3的元素有4個(gè)，為第1、4、7、11個(gè)，查找長(zhǎng)度為4的元素有5個(gè)，為第2、5、8、10、12個(gè)。（3）查找第五個(gè)元素依次比較6，3，4，5。例：設(shè)有一組關(guān)鍵字{32,75,63,48,94,25,36,18,70}，采用哈希函數(shù)：H(key)=keyMOD11并采用步長(zhǎng)為1的線性探測(cè)法解決沖突，試在0--10的散列地址空間中對(duì)該關(guān)鍵字序列構(gòu)造哈希表。【答】依題意，m=11，線性探測(cè)再散列的下一地址計(jì)算公式為：

d1=H(key)，dj+1=(dj+1)MOD11；j=1,2,...

其計(jì)算過程如下：

H(32)=32MOD11=10 H(75)=75MOD11=9H(63)=63MOD11=8 H(48)=48MOD11=4H(94)=94MOD11=6 H(25)=25MOD11=3H(36)=36MOD11=3(沖突)H(36)=(3+1)MOD11=4(仍沖突)H(36)=(4+1)MOD11=5 H(18)=18MOD11=7H(70)=70MOD11=4(沖突)H(70)=(4+1)MOD11=5(仍沖突)……H(70)=(10+1)MOD11=0012345678910702548369418637532例題解析排序簡(jiǎn)單排序方法（0（n2））插入排序（穩(wěn)定排序）選擇排序（不穩(wěn)定排序）冒泡排序（不穩(wěn)定排序）先進(jìn)排序方法（O(nlogn)）快速排序（不穩(wěn)定排序）歸并排序（穩(wěn)定排序）堆排序（不穩(wěn)定排序）一、時(shí)間性能時(shí)間復(fù)雜度為O(nlogn)：快速排序、堆排序和歸并排序，其中以快速排序?yàn)樽詈谩r(shí)間復(fù)雜度為O(n2)：直接插入排序、起泡排序和簡(jiǎn)單選擇排序，

其中以直接插入為最好，特別是對(duì)那些對(duì)關(guān)鍵字基本有序的記錄序列尤為如此。

時(shí)間復(fù)雜度為O(n*d)：基數(shù)排序。1.按平均時(shí)間性能來分，有三類排序方法：

2.當(dāng)待排序列按關(guān)鍵字順序有序時(shí)，直接插入排序和起泡排序能達(dá)到O(n)的時(shí)間復(fù)雜度，快速排序的時(shí)間性能蛻化為O(n2)。3.簡(jiǎn)單選擇排序、堆排序和歸并排序的時(shí)間性能不隨記錄序列中關(guān)鍵字的分布而改變。各種排序方法的綜合比較二、空間性能指的是排序過程中所需的輔助空間大小。所有的簡(jiǎn)單排序方法(包括：直接插入、冒泡和簡(jiǎn)單選擇)和堆排序的空間復(fù)雜度為O(1)；快速排序?yàn)镺(logn)，為遞歸程序執(zhí)行過程中，棧所需的輔助空間；3.歸并排序所需輔助空間最多，其空間復(fù)雜度為O(n)；4.鏈?zhǔn)交鶖?shù)排序需附設(shè)隊(duì)列首尾指針，則空間復(fù)雜度為O(2*rd+n)三、排序方法的穩(wěn)定性能1.當(dāng)對(duì)多關(guān)鍵字的記錄序列進(jìn)行LSD方法排序時(shí)，必須采用穩(wěn)定的排序方法。2.對(duì)于不穩(wěn)定的排序方法，只要能舉出一個(gè)實(shí)例說明即可。3.快速排序、堆排序是不穩(wěn)定的排序方法。各種排序方法的綜合比較各種內(nèi)部排序方法的比較

排序方法平均時(shí)間最壞情況最好情況輔助存儲(chǔ)穩(wěn)定性插入排序O(n2)O(n2)O(n)O(1）穩(wěn)定選擇排序O(n2)O(n2)O(n2)O(1）穩(wěn)定冒泡排序O(n2)O(n2)O(n)O(1）穩(wěn)定快速排序O(nlgn)O(n2)O(nlgn)O(lgn)不穩(wěn)定歸并排序O(nlgn)O(nlgn)O(nlgn)O(n）穩(wěn)定堆排序O(nlgn)O(nlgn)O(nlgn)O(1）不穩(wěn)定基數(shù)排序O(d×n)O(d×n)O(d×n)O(n)穩(wěn)定例題解析設(shè)待排序的排序碼序列為{12,2,16,30,28,10,16*,20,6,18},試分別寫出使用以下排序方法每趟排序后的結(jié)果。并說明做了多少次排序碼比較。

（1）直接插入排序；（2）起泡排序； 【答】（1）直接插入排序12/04/202431例題解析設(shè)待排序的排序碼序列為{12,2,16,30,28,10,16*,20,6,18},試分別寫出使用以下排序方法每趟排序后的結(jié)果。并說明做了多少次排序碼比較。

（1）直接插入排序；（2）起泡排序；【答】（2）起泡排序12/04/202432例題解析【例】填空題：1.空格串是指_____________，其長(zhǎng)度等于_____________?！敬鸢浮浚?）由空格字符（ASCII值32）所組成的字符串。（2）空格個(gè)數(shù)2．組成串的數(shù)據(jù)元素只能是_____________?！敬鸢浮孔址窘馕觥看且环N特殊的線性表，其特殊性在于串中的元素只能是字符型數(shù)據(jù)。3．兩個(gè)字符串相等的充分必要條件是_____________?！敬鸢浮?jī)纱拈L(zhǎng)度相等且兩串中對(duì)應(yīng)位置上的字符也相等。4．一個(gè)字符串中_____________稱為該串的子串?！敬鸢浮咳我鈧€(gè)連續(xù)的字符組成的子序列例題解析【例】設(shè)計(jì)一個(gè)算法，將字符串s的全部字符復(fù)制到字符串t中，不能利用strcpy函數(shù)。答：【算法分析】要實(shí)現(xiàn)兩個(gè)字符串的復(fù)制，實(shí)質(zhì)為兩個(gè)字符數(shù)組之間的復(fù)制，在復(fù)制時(shí)，一個(gè)字符一個(gè)字符的復(fù)制，直到遇到'\0'，'\0'一同復(fù)制過去，'\0'之后的字符不復(fù)制?！舅惴ㄔ创a】voidcopy(chars[],chart[]){inti;for(i=0;s[i]!='\0';i++)t[i]=s[i];t[i]=s[i];}鏈表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn)用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素利用指針實(shí)現(xiàn)了用不相鄰的存儲(chǔ)單元存放邏輯上相鄰的元素每個(gè)數(shù)據(jù)元素ai，除存儲(chǔ)本身信息外，還需存儲(chǔ)其直接后繼的信息

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)：結(jié)點(diǎn)空間可以動(dòng)態(tài)申請(qǐng)和釋放；數(shù)據(jù)元素的邏輯次序靠結(jié)點(diǎn)的指針來指示，插入和刪除時(shí)不需要移動(dòng)數(shù)據(jù)元素。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的缺點(diǎn)：每個(gè)結(jié)點(diǎn)的指針域需額外占用存儲(chǔ)空間。當(dāng)數(shù)據(jù)域所占字節(jié)不多時(shí)，指針域所占存儲(chǔ)空間的比重顯得很大。鏈表是非隨機(jī)存取結(jié)構(gòu)。對(duì)任一結(jié)點(diǎn)的操作都要從頭指針依鏈查找該結(jié)點(diǎn)，這增加了算法的復(fù)雜度O（n）不便于在表尾插入元素：需遍歷整個(gè)表才能找到位置。12/04/202435例題解析【例1】說明在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，頭指針與頭結(jié)點(diǎn)之間的根本區(qū)別。答：在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，頭指針指鏈表的指針，若鏈表有頭結(jié)點(diǎn)則是鏈表的頭結(jié)點(diǎn)的指針，頭指針具有標(biāo)識(shí)作用，故常用頭指針冠以鏈表的名字。頭結(jié)點(diǎn)是為了操作的統(tǒng)一、方便而設(shè)立的，放在第一元素結(jié)點(diǎn)之前，其數(shù)據(jù)域一般無意義（當(dāng)然有些情況下也可存放鏈表的長(zhǎng)度、用做監(jiān)視哨等等），有頭結(jié)點(diǎn)后，對(duì)在第一元素結(jié)點(diǎn)前插入結(jié)點(diǎn)和刪除第一結(jié)點(diǎn)，其操作與對(duì)其它結(jié)點(diǎn)的操作統(tǒng)一了。而且無論鏈表是否為空，頭指針均不為空。12/04/202436例題解析

【例2】設(shè)順序表va中的數(shù)據(jù)元素遞增有序。試設(shè)計(jì)一個(gè)算法，將x插入到順序表的適當(dāng)位置上，以保持該表的有序性。答：voidInsert_SqList(SqListva,intx)/*把x插入遞增有序表va中*/{inti;if(va.length>MAXSIZE)return;

for(i=va.length-1;va.elem[i]>x&&i>=0;i--)va.elem[i+1]=va.elem[i];va.elem[i+1]=x;va.length++;}/*Insert_SqList*/12/04/202437#defineMAXSIZE100typedefstruct{ ElemType*elem; intlength;}SqList；例題解析【例3】設(shè)單鏈表結(jié)點(diǎn)指針域?yàn)閚ext，試寫出刪除鏈表中指針p所指結(jié)點(diǎn)的直接后繼的C語言語句。答： q=p->next; p->next=q->next; free(q);12/04/202438例題解析【例4】設(shè)單鏈表中某指針p所指結(jié)點(diǎn)（即p結(jié)點(diǎn)）的數(shù)據(jù)域?yàn)閐ata，鏈指針域?yàn)閚ext，請(qǐng)寫出在p結(jié)點(diǎn)之前插入s結(jié)點(diǎn)的操作。答：

設(shè)單鏈表的頭結(jié)點(diǎn)的頭指針為head,且pre=head；

while(pre->next!=p)pre=pre->next;s->next=p;pre->next=s;12/04/202439例題解析【例5】試編寫在帶頭結(jié)點(diǎn)的單鏈表中刪除（一個(gè)）最小值結(jié)點(diǎn)的算法。voiddelete（Linklist&L）[分析]單鏈表中刪除最小值結(jié)點(diǎn)，為使結(jié)點(diǎn)刪除后不出現(xiàn)“斷鏈”，應(yīng)知道被刪結(jié)點(diǎn)的前驅(qū)。而“最小值結(jié)點(diǎn)”是在遍歷整個(gè)鏈表后才能知道。故應(yīng)首先遍歷鏈表，求得最小值結(jié)點(diǎn)及其前驅(qū)。遍歷結(jié)束后再執(zhí)行刪除操作。

voiddelete（LinkedList&L）{∥L是帶頭結(jié)點(diǎn)的單鏈表p=L->next；∥p為工作指針。指向待處理的結(jié)點(diǎn)。

pre=L；∥pre指向最小值結(jié)點(diǎn)的前驅(qū)。

q=p；∥q指向最小值結(jié)點(diǎn)，初始假定第一結(jié)點(diǎn)是最小值結(jié)點(diǎn)。

while（p->next!=null）{if（p->next->data<q->data）{pre=p；q=p->next；}∥查最小值結(jié)點(diǎn)

p=p->next；∥指針后移。

}pre->next=q->next；∥從鏈表上刪除最小值結(jié)點(diǎn)

free（q）；∥釋放最小值結(jié)點(diǎn)空間}∥結(jié)束算法delete。12/04/202440例題解析【例6】一元稀疏多項(xiàng)式以循環(huán)單鏈表按降冪排列，結(jié)點(diǎn)有三個(gè)域，系數(shù)域coef，指數(shù)域exp和指針域next；現(xiàn)對(duì)鏈表求一階導(dǎo)數(shù)，鏈表的頭指針為ha，頭結(jié)點(diǎn)的exp域?yàn)楱C1。

voidderivative(ha){q=ha;pa=ha->next;while((1)_______){if((2)____){((3)__);free(pa);pa=((4)_);}else{pa->coef((5)___);pa->exp((6)___);q=((7)__);}pa=((8)________);}}12/04/202441(1)pa!=ha∥或pa->exp!=-1(2)pa->exp==0∥若指數(shù)為0，即本項(xiàng)為常數(shù)項(xiàng)(3)q->next=pa->next∥刪常數(shù)項(xiàng)(4)q->next∥取下一元素(5)=pa->coef*pa->exp(6)--∥指數(shù)項(xiàng)減1(7)pa∥前驅(qū)后移,或q->next(8)pa->next∥取下一元素【例7】(1)在一個(gè)長(zhǎng)度為n的順序表的第i（1≤i≤n+1）個(gè)元素之前插入一個(gè)元素，需向后移動(dòng)

n-i+1個(gè)元素，刪除第i（1≤i≤n）個(gè)元素時(shí)，需向前移動(dòng)

n-i個(gè)元素。(2)在單循環(huán)鏈表中，由rear指向表尾，在表尾插入一個(gè)結(jié)點(diǎn)s的操作順序是:s->next=rear->next;

rear->next=s;rear=s;刪除開始結(jié)點(diǎn)的操作順序?yàn)閝=rear->next->next;

rear->next->next=q->next;deleteq;

。例題解析棧限定僅在表尾進(jìn)行插入和刪除的線性表，把這個(gè)表尾稱為棧頂。特點(diǎn)后進(jìn)先出(LIFO表)棧的存儲(chǔ)方法棧的順序存儲(chǔ)——順序棧棧的鏈?zhǔn)酱鎯?chǔ)——鏈棧12/04/202443第三講

棧和隊(duì)列(棧和隊(duì)列及其應(yīng)用)關(guān)于棧要求掌握的內(nèi)容12/04/202444

棧的基本概念：LIFO

棧的存儲(chǔ)棧的應(yīng)用（了解）順序棧（熟練掌握）鏈棧（熟練掌握）初始化取棧頂入棧出棧判斷棧空

棧初始化取棧頂入棧出棧判斷?？贞?duì)列定義12/04/202445

隊(duì)列的定義隊(duì)列：線性表(queue)特點(diǎn)：先進(jìn)先出(FIFO結(jié)構(gòu))。隊(duì)尾隊(duì)頭下圖是隊(duì)列的示意圖：

a1

a2

…

an出隊(duì)入隊(duì)隊(duì)頭隊(duì)尾當(dāng)隊(duì)列中沒有元素時(shí)稱為空隊(duì)列。表尾稱為隊(duì)尾(rear)表頭稱為隊(duì)頭(front)插入元素稱為入隊(duì)刪除元素稱為出隊(duì)限定在表的一端插入、另一端刪除。順序隊(duì)列的假溢出問題12/04/202446

在順序隊(duì)列中，當(dāng)尾指針已經(jīng)指向了隊(duì)列的最后一個(gè)位置即數(shù)組上界時(shí)，若再有元素入隊(duì)，就會(huì)發(fā)生“溢出”。

“假溢出”——隊(duì)列的存儲(chǔ)空間未滿，卻發(fā)生了溢出。rearfrontJ1

J2

J3

J4

rearfrontJ3

J4

(1)、平移元素：把元素平移到隊(duì)列的首部。效率低。

解決“假溢出”的問題有兩種可行的方法：(2)、將新元素插入到第一個(gè)位置上，構(gòu)成循環(huán)隊(duì)列，入隊(duì)和出隊(duì)仍按“先進(jìn)先出”的原則進(jìn)行。

操作效率、空間利用率高。rearfrontJ3

J4

frontrearJ3

J4

循環(huán)隊(duì)列12/04/202447隊(duì)空條件:front=rear(初始化時(shí)：front=rear)隊(duì)滿條件：front=(rear+1)%N(N=maxsize)隊(duì)列長(zhǎng)度：L=（N＋rear－front）%NJ2J3

J1

J4

J5frontrear

選用空閑單元法：即front和rear之一指向?qū)嵲?，另一指向空閑元素。

問2：在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有多少個(gè)元素？n-1個(gè)5問1：左圖中隊(duì)列長(zhǎng)度L=？例題解析【例1】一個(gè)棧的輸入序列是12345，若在入棧的過程中允許出棧，則棧的輸出序列43512可能實(shí)現(xiàn)嗎？12345的輸出呢？答： 43512不可能實(shí)現(xiàn)，主要是其中的12順序不能實(shí)現(xiàn)； 12345的輸出可以實(shí)現(xiàn)，只需壓入一個(gè)立即彈出一個(gè)即可。12/04/202448例題解析【例2】如果一個(gè)棧的輸入序列為123456，能否得到435612和135426的出棧序列？答： 435612中到了12順序不能實(shí)現(xiàn)； 135426可以實(shí)現(xiàn)。思考題：編寫算法，利用棧判斷所給字符串是否具有中心對(duì)稱關(guān)系（如xyzyx和abcdcba是中心對(duì)稱的）。12/04/202449例題解析【例3】一個(gè)棧的輸入序列為123，若在入棧的過程中允許出棧，則可能得到的出棧序列是什么？答：可以通過窮舉所有可能性來求解：①1入1出，2入2出，3入3出，即123；②1入1出，2、3入3、2出，即132；③1、2入，2出，3入3出，即231；④1、2入，2、1出，3入3出，即213；⑤1、2、3入，3、2、1出，即321；

合計(jì)有5種可能性。12/04/202450例題解析【例4】簡(jiǎn)述順序存儲(chǔ)隊(duì)列的假溢出的避免方法及隊(duì)列滿和空的條件。答：設(shè)順序存儲(chǔ)隊(duì)列用一維數(shù)組q[m]表示，其中m為隊(duì)列中元素個(gè)數(shù)，隊(duì)列中元素在向量中的下標(biāo)從0到m-1。設(shè)隊(duì)頭指針為front，隊(duì)尾指針是rear，約定front指向隊(duì)頭元素的前一位置，rear指向隊(duì)尾元素。當(dāng)front等于-1時(shí)隊(duì)空，rear等于m-1時(shí)為隊(duì)滿。由于隊(duì)列的性質(zhì)（“刪除”在隊(duì)頭而“插入”在隊(duì)尾），所以當(dāng)隊(duì)尾指針rear等于m-1時(shí)，若front不等于-1，則隊(duì)列中仍有空閑單元，所以隊(duì)列并不是真滿。這時(shí)若再有入隊(duì)操作，會(huì)造成假“溢出”。其解決辦法有二，一是將隊(duì)列元素向前“平移”（占用0至rear-front-1）；二是將隊(duì)列看成首尾相連，即循環(huán)隊(duì)列（0..m-1）。在循環(huán)隊(duì)列下，仍定義front=rear時(shí)為隊(duì)空，而判斷隊(duì)滿則用兩種辦法，一是用“犧牲一個(gè)單元”，即rear+1=front（準(zhǔn)確記是（rear+1）%m=front，m是隊(duì)列容量）時(shí)為隊(duì)滿。另一種解法是“設(shè)標(biāo)記”方法，如設(shè)標(biāo)記tag，tag等于0情況下，若刪除時(shí)導(dǎo)致front=rear為隊(duì)空；tag=1情況下，若因插入導(dǎo)致front=rear則為隊(duì)滿。12/04/202451第四講特殊矩陣、廣義表及其應(yīng)用12/04/202452二維數(shù)組每一行是一個(gè)一維數(shù)組，元素間存在序偶關(guān)系；每一列也是一個(gè)一維數(shù)組，元素間也同樣存在序偶關(guān)系。若把每一行看作是一個(gè)整體，則行與行之間是線性關(guān)系；若把每一列看作是一個(gè)整體，則列與列之間也是線性關(guān)系。內(nèi)容提要內(nèi)容提要矩陣：是由m×n個(gè)數(shù)排列成m行(橫向)、n列(縱向)所形成的矩形數(shù)表：

內(nèi)容提要矩陣與數(shù)組的關(guān)系

：對(duì)照上述數(shù)組的定義，我們不難看出，矩陣中所有數(shù)據(jù)元素組成了一個(gè)二維數(shù)組，矩陣的每一行、每一列的數(shù)據(jù)元素分別組成等長(zhǎng)的一維數(shù)組。我們也可以說，矩陣是一個(gè)線性表，其每一個(gè)數(shù)據(jù)元素(行或列)也是一個(gè)線性表。按行優(yōu)先順序存儲(chǔ)按列優(yōu)先順序存儲(chǔ)二維數(shù)組中任一元素的地址特殊矩陣對(duì)稱矩陣三角矩陣對(duì)角矩陣稀疏矩陣和三元組十字鏈表廣義表的概念廣義表的存儲(chǔ)結(jié)構(gòu)內(nèi)容提要例題解析【例】設(shè)有一個(gè)二維數(shù)組A[m][n]，假設(shè)A[0][0]存放位置在644，A[2][2]存放位置在676，每個(gè)元素占一個(gè)空間，問A[3][3]存放在什么位置？答：設(shè)數(shù)組元素A[i][j]存放在起始地址為L(zhǎng)oc（i,j）的存儲(chǔ)單元中?！週oc（2,2）=Loc（0,0）+2*n+2=644+2*n+2=676.∴n=（676-2-644）/2=15∴Loc（3,3）=Loc（0,0）+3*15+3=644+45+3=692.12/04/202456例題解析【例】設(shè)有一個(gè)n

n的對(duì)稱矩陣A，為了節(jié)約存儲(chǔ)，可以只存對(duì)角線及對(duì)角線以上的元素，或者只存對(duì)角線或?qū)蔷€以下的元素。前者稱為上三角矩陣，后者稱為下三角矩陣。我們把它們按行存放于一個(gè)一維數(shù)組B中，稱之為對(duì)稱矩陣A的壓縮存儲(chǔ)方式。試問：（1）存放對(duì)稱矩陣A上三角部分或下三角部分的一維數(shù)組B有多少元素？（2）若在一維數(shù)組B中從0號(hào)位置開始存放，則對(duì)稱矩陣中的任一元素aij在只存下三角部分的情形下應(yīng)存于一維數(shù)組的什么下標(biāo)位置？給出計(jì)算公式。答：（1）數(shù)組B共有1＋2+3+

+n=（n+1）*n/2個(gè)元素。（2）只存下三角部分時(shí)，若i

j，則數(shù)組元素A[i][j]前面有i-1行（1

i-1，第0行第0列不算），第1行有1個(gè)元素，第2行有2個(gè)元素，

，第i-1行有i-1個(gè)元素。在第i行中，第j號(hào)元素排在第j個(gè)元素位置，因此，數(shù)組元素A[i][j]在數(shù)組B中的存放位置為：1+2+

+（i-1）+j=（i-1）*i/2+j若i<j，數(shù)組元素A[i][j]在數(shù)組B中沒有存放，可以找它的對(duì)稱元素A[j][i]。在數(shù)組B的第（j-1）*j/2+i位置中找到。如果第0行第0列也計(jì)入，數(shù)組B從0號(hào)位置開始存放，則數(shù)組元素A[i][j]在數(shù)組B中的存放位置可以改為：當(dāng)i

j時(shí)，=i*（i+1）/2+j；當(dāng)i<j時(shí)，=j*（j+1）/2+i。12/04/202457廣義表

一、廣義表定義：數(shù)據(jù)元素可以是表的線性表。記為：LS＝(d1,d2,…,dn)，LS為表名，di(i＝1,2,…,n)，可以是單元素(稱為原子，用小寫字母表示)，也可以是廣義表(稱為子表，用大寫字母表示)；若廣義表LS非空，則必有n大于0（即n>0）n為表的長(zhǎng)度，當(dāng)長(zhǎng)度為0時(shí)稱為空表；稱非空表的第一個(gè)元素d1為表頭，其余元素組成的表(d2,…,dn)稱為表尾。注意：表尾可以可以是空表，而表頭可以是原子，也可以是一個(gè)表。二、廣義表的表達(dá)方式及例子1．A=()A是一個(gè)空表，其長(zhǎng)度為0。2．B=(e)列表B只有一個(gè)原子e，其長(zhǎng)度為1。3．C=(a,(b,c,d))列表C的長(zhǎng)度為2，表頭為原子，第二個(gè)元素是一個(gè)列表(b,c,d)。4.D=(A,B,C)列表D的長(zhǎng)度為3，表頭也是一個(gè)列表A，表尾是列表（A,B）,注意：這里引用了已有的列表A、B、C作為該廣義表D的元素。5．E=(a,E)。這是一個(gè)遞歸列表，其元素中有自己。例題解析這種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是：最上層的表結(jié)點(diǎn)數(shù)即為廣義表的長(zhǎng)度；層次清楚；表結(jié)點(diǎn)數(shù)目多，與廣義表中括號(hào)對(duì)的數(shù)目不匹配。

例:C=(a,(b,c,d))，用單鏈存儲(chǔ)結(jié)構(gòu)表示。111110a0b0c0d＾＾((b,c,d))(b,c,d)(c,d)(d)C例題解析同層結(jié)點(diǎn)鏈結(jié)構(gòu)的特點(diǎn)是：表結(jié)點(diǎn)的數(shù)目與廣義表的括號(hào)對(duì)數(shù)目一致；寫遞歸算法不方便。例:C=(a,(b,c,d))，用雙鏈存儲(chǔ)結(jié)構(gòu)表示。1C＾0a1＾0b0c0d＾(b,c,d)第五講二叉樹、樹和森林及其應(yīng)用12/04/202462二叉樹的定義定義：是n（n≥0）個(gè)結(jié)點(diǎn)的有限集合，由一個(gè)根結(jié)點(diǎn)以及兩棵互不相交的、分別稱為左子樹和右子樹的二叉樹組成。邏輯結(jié)構(gòu)：一對(duì)二（1：2）

基本特征:每個(gè)結(jié)點(diǎn)最多只有兩棵子樹（不存在度大于2的結(jié)點(diǎn)）；左子樹和右子樹次序不能顛倒（有序樹）。滿二叉樹完全二叉樹二叉樹的性質(zhì)（能證明嗎）12/04/202463【性質(zhì)1】在二叉樹的第i

層上至多有2i-1個(gè)結(jié)點(diǎn)(i≥1)?！拘再|(zhì)2】深度為k的二叉樹至多有2k

-1個(gè)結(jié)點(diǎn)（k≥1）?！拘再|(zhì)3】對(duì)任何一棵二叉樹T，如果其葉子數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。（葉子數(shù)＝結(jié)點(diǎn)的度為2的結(jié)點(diǎn)數(shù)＋1）【性質(zhì)4】具有n

個(gè)結(jié)點(diǎn)的完全二叉樹的深度為

log2n

+1或者

log2(n+1)

?！拘再|(zhì)5】n個(gè)結(jié)點(diǎn)的完全二叉樹，結(jié)點(diǎn)按層次編號(hào)有：

1)i的雙親是，如果i=1時(shí)為根（無雙親）；

2)i的左孩子是2i，如果2i>n，則無左孩子；

3)i的右孩子是2i+1，如果2i+1>n則無右孩子。例題解析1．深度為H的完全二叉樹至少有_____________個(gè)結(jié)點(diǎn)；至多有_____________個(gè)結(jié)點(diǎn)；H和結(jié)點(diǎn)總數(shù)N之間的關(guān)系是_____________?！敬鸢浮浚?）2H-1 （2）2H-1 （3）H=

log2N

+12．一棵有n個(gè)結(jié)點(diǎn)的滿二叉樹有_____________個(gè)度為1的結(jié)點(diǎn)，有_____________個(gè)分支（非終端）結(jié)點(diǎn)和_____________個(gè)葉子，該滿二叉樹的深度為_____________?！敬鸢浮浚?）0 （2）(n-1）/2 （3）(n+1）/2 （4）

log2n

+13．對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)它為一棵_____________時(shí)，具有最小高度，當(dāng)它為一棵_____________時(shí)，具有最大高度?！敬鸢浮浚?）完全二叉樹 （2）單支樹，樹中任一結(jié)點(diǎn)（除最后一個(gè)結(jié)點(diǎn)是葉子外），只有左子女或只有右子女。4．已知二叉樹有50個(gè)葉子結(jié)點(diǎn)，則該二叉樹的總結(jié)點(diǎn)數(shù)至少是_____________。【答案】99【解析】在二叉樹中，N0=N2+1，所以，有50個(gè)葉子結(jié)點(diǎn)的二叉樹，有49個(gè)度為2的結(jié)點(diǎn)。若要使該二叉樹的結(jié)點(diǎn)數(shù)最少，度為1的結(jié)點(diǎn)應(yīng)為0個(gè)，即總結(jié)點(diǎn)數(shù)N=N0+N1+N2=99。12/04/202464二叉樹的存儲(chǔ)（一）12/04/202465二叉樹存儲(chǔ)方法有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)二叉樹順序存儲(chǔ)結(jié)構(gòu)完全二叉樹：用一組地址連續(xù)的存儲(chǔ)單元依次自上而下、自左至右存儲(chǔ)結(jié)點(diǎn)元素，即將編號(hào)為i

的結(jié)點(diǎn)元素存儲(chǔ)在一維數(shù)組中下標(biāo)為

i

的分量中（不用下標(biāo)為0存儲(chǔ)單元）。此順序存儲(chǔ)結(jié)構(gòu)僅適用于完全二叉樹不是完全二叉樹怎么辦？一律轉(zhuǎn)為完全二叉樹！方法很簡(jiǎn)單，將各層空缺處統(tǒng)統(tǒng)補(bǔ)上“虛結(jié)點(diǎn)”，其內(nèi)容為空。缺點(diǎn)：①浪費(fèi)空間；②插入、刪除不便二叉樹的存儲(chǔ)（二）12/04/202466二叉樹鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

存儲(chǔ)方式

一般從根結(jié)點(diǎn)開始存儲(chǔ)，用二叉鏈表來表示。（相應(yīng)地，訪問樹中結(jié)點(diǎn)時(shí)也只能從根開始）

二叉樹結(jié)點(diǎn)的特點(diǎn)二叉樹是非線性結(jié)構(gòu)，適合用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)lchilddatarchild結(jié)點(diǎn)結(jié)構(gòu)datarchildlchilddata

parentlchildrchild二叉樹結(jié)點(diǎn)數(shù)據(jù)類型定義：typedefstructBiTNode{

TElemTypedata; structBiTNode*lchild,*rchild;}BiTNode,*BiTree;二叉樹遍歷12/04/202467若規(guī)定先左后右，則只有前三種情況：DLR——

前（根）序遍歷，LDR——

中（根）序遍歷，LRD——

后（根）序遍歷根據(jù)遍歷順序確定一棵二叉樹已知二叉樹的前序序列和中序序列，可以唯一確定一棵二叉樹。已知二叉樹的后序序列和中序序列，可以唯一確定一棵二叉樹。已知二叉樹的前序序列和后序序列，不能唯一確定一棵二叉樹。例題解析12/04/202468

設(shè)二叉樹bt的一種存儲(chǔ)結(jié)構(gòu)如下：00237580101jhfdbacegi000940000012345678910lchilddatarchild

其中bt為樹根結(jié)點(diǎn)指針,lchild、rchild分別為結(jié)點(diǎn)的左、右孩子指針域,在這里使用結(jié)點(diǎn)編號(hào)作為指針域值,0表示指針域?yàn)榭?data為結(jié)點(diǎn)的數(shù)據(jù)域。請(qǐng)完成下列各題：(1)畫出二叉樹的樹形表示；(2)寫出按先序、中序和后序遍歷二叉樹bt所得到的結(jié)點(diǎn)序列；例題解析（續(xù)）12/04/20246900237580101jhfdbacegi000940000012345678910lchilddatarchild(1)畫出二叉樹的樹形表示；因?yàn)榈?號(hào)結(jié)點(diǎn)不是任何結(jié)點(diǎn)的孩子結(jié)點(diǎn)，該結(jié)點(diǎn)必定是根結(jié)點(diǎn)，再根據(jù)和結(jié)點(diǎn)左、右指針域的值很容易得到該二叉樹的樹形表示為

abgfdcehij例題解析（續(xù)）12/04/20247000237580101jhfdbacegi000940000012345678910lchilddatarchildabgfdcehij(2)寫出按先序、中序和后序遍歷二叉樹bt所得到的結(jié)點(diǎn)序列；a.先序序列abcedfhgij例題解析（續(xù)）12/04/20247100237580101jhfdbacegi000940000012345678910lchilddatarchildabgfdcehij(2)寫出按先序、中序和后序遍歷二叉樹bt所得到的結(jié)點(diǎn)序列；a.先序序列abcedfhgijb.中序序列ecbhfdjiga例題解析（續(xù)）12/04/20247200237580101jhfdbacegi000940000012345678910lchilddatarchildabgfdcehij(2)寫出按先序、中序和后序遍歷二叉樹bt所得到的結(jié)點(diǎn)序列；a.先序序列abcedfhgijb.中序序列ecbhfdjigab.后序序列echfjigdba樹與森林【例題】從概念上講，樹，森林和二叉樹是三種不同的數(shù)據(jù)結(jié)構(gòu)，將樹，森林轉(zhuǎn)化為二叉樹的基本目的是什么，并指出樹和二叉樹的主要區(qū)別。答：樹的孩子兄弟鏈表表示法和二叉樹二叉鏈表表示法，本質(zhì)是一樣的，只是解釋不同，也就是說樹（樹是森林的特例，即森林中只有一棵樹的特殊情況）可用二叉樹惟一表示，并可使用二叉樹的一些算法去解決樹和森林中的問題。樹和二叉樹的區(qū)別有3：一是二叉樹的度至多為2，樹無此限制；二是二叉樹有左右子樹之分，即使在只有一個(gè)分支的情況下，也必須指出是左子樹還是右子樹，樹無此限制；三是二叉樹允許為空，樹一般不允許為空（個(gè)別書上允許為空）。12/04/202473例題解析【例題】已知一棵二叉樹的中序序列和后序序列分別為GLDHBEIACJFK和LGHDIEBJKFCA（1）給出這棵二叉樹；（2）轉(zhuǎn)換為對(duì)應(yīng)的森林。答：12/04/202474ACBHJDFGKLEIEABLDGHIJFCK例題解析【例題】假設(shè)一棵二叉樹的層次次序（按層次遞增順序排列，同一層次自左向右）為ABECFGDHI,中序序列為BCDAFEHIG。請(qǐng)畫出該二叉樹，并將其轉(zhuǎn)換為對(duì)應(yīng)的森林。答：按層次遍歷，第一個(gè)結(jié)點(diǎn)（若樹不空）為根，該結(jié)點(diǎn)在中序序列中把序列分成左右兩部分：左子樹和右子樹。若左子樹不空，層次序列中第二個(gè)結(jié)點(diǎn)為左子樹的根；若右子樹為空，則層次序列中第三個(gè)結(jié)點(diǎn)為右子樹的根。對(duì)右子樹也作類似的分析。層次序列的特點(diǎn)是，從左到右每個(gè)結(jié)點(diǎn)或是當(dāng)前情況下子樹的根或是葉子。12/04/202475IADEBFCGHECABDIGHF二叉樹的應(yīng)用：Huffman樹12/04/202476Huffman樹的應(yīng)用帶權(quán)路徑計(jì)算WPL帶權(quán)路徑長(zhǎng)度WPL最小的二叉樹稱作赫夫曼樹具有相同帶權(quán)結(jié)點(diǎn)的哈夫曼樹不惟一滿二叉樹不一定是哈夫曼樹哈夫曼樹的結(jié)點(diǎn)的度數(shù)為0或2，沒有度為1的結(jié)點(diǎn)。包含

n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹中共有2n–1個(gè)結(jié)點(diǎn)。Huffman樹的構(gòu)造過程給定權(quán)值集w={2,3,4,7,8,9},試構(gòu)造關(guān)于w的的一顆哈夫曼樹，并求其帶權(quán)路徑長(zhǎng)度WPL。12/04/2024772347894789235789235499235497815Huffman樹的構(gòu)造過程12/04/202478給定權(quán)值集w={2,3,4,7,8,9},試構(gòu)造關(guān)于w的的一顆哈夫曼樹，并求其帶權(quán)路徑長(zhǎng)度WPL。78159235491878159235491833WPL=(2+3)×4+4×3+9×2+(7+8)×2=80【例題】T={(a,2),(b,3),(c,4),(d,7),(e,9)}為帶權(quán)字符集，試構(gòu)造關(guān)于該字符集的一顆哈夫曼樹，求其加權(quán)路徑長(zhǎng)度WPL、T中每個(gè)字符的哈曼夫編碼和哈夫曼編碼的平均長(zhǎng)度。23479Huffman編碼過程T={(a,2),(b,3),(c,4),(d,7),(e,9)}為帶權(quán)字符集，試構(gòu)造關(guān)于該字符集的一顆哈夫曼樹，求其加權(quán)路徑長(zhǎng)度WPL、T中每個(gè)字符的哈曼夫編碼和哈夫曼編碼的平均長(zhǎng)度。23479235T={(a,2),(b,3),(c,4),(d,7),(e,9)}為帶權(quán)字符集，試構(gòu)造關(guān)于該字符集的一顆哈夫曼樹，求其加權(quán)路徑長(zhǎng)度WPL、T中每個(gè)字符的哈曼夫編碼和哈夫曼編碼的平均長(zhǎng)度。23479235T={(a,2),(b,3),(c,4),(d,7),(e,9)}為帶權(quán)字符集，試構(gòu)造關(guān)于該字符集的一顆哈夫曼樹，求其加權(quán)路徑長(zhǎng)度WPL、T中每個(gè)字符的哈曼夫編碼和哈夫曼編碼的平均長(zhǎng)度。2347923523549T={(a,2),(b,3),(c,4),(d,7),(e,9)}為帶權(quán)字符集，試構(gòu)造關(guān)于該字符集的一顆哈夫曼樹，求其加權(quán)路徑長(zhǎng)度WPL、T中每個(gè)字符的哈曼夫編碼和哈夫曼編碼的平均長(zhǎng)度。2347923523549T={(a,2),(b,3),(c,4),(d,7),(e,9)}為帶權(quán)字符集，試構(gòu)造關(guān)于該字符集的一顆哈夫曼樹，求其加權(quán)路徑長(zhǎng)度WPL、T中每個(gè)字符的哈曼夫編碼和哈夫曼編碼的平均長(zhǎng)度。23479235235497916T={(a,2),(b,3),(c,4),(d,7),(e,9)}為帶權(quán)字符集，試構(gòu)造關(guān)于該字符集的一顆哈夫曼樹，求其加權(quán)路徑長(zhǎng)度WPL、T中每個(gè)字符的哈曼夫編碼和哈夫曼編碼的平均長(zhǎng)度。23479235235497916T={(a,2),(b,3),(c,4),(d,7),(e,9)}為帶權(quán)字符集，試構(gòu)造關(guān)于該字符集的一顆哈夫曼樹，求其加權(quán)路徑長(zhǎng)度WPL、T中每個(gè)字符的哈曼夫編碼和哈夫曼編碼的平均長(zhǎng)度。2347923523549791623549791625T={(a,2),(b,3),(c,4),(d,7),(e,9)}為帶權(quán)字符集，試構(gòu)造關(guān)于該字符集的一顆哈夫曼樹，求其加權(quán)路徑長(zhǎng)度WPL、T中每個(gè)字符的哈曼夫編碼和哈夫曼編碼的平均長(zhǎng)度。2347923523549791623549791625T={(a,2),(b,3),(c,4),(d,7),(e,9)}為帶權(quán)字符集，試構(gòu)造關(guān)于該字符集的一顆哈夫曼樹，求其加權(quán)路徑長(zhǎng)度WPL、T中每個(gè)字符的哈曼夫編碼和哈夫曼編碼的平均長(zhǎng)度。23549791625abcdeWPL=5500001111a:010b:011c:00d:10e:11哈夫曼編碼的平均長(zhǎng)度=3×2+3×3+2×4+2×7+2×9=551、定義和性質(zhì)2、存儲(chǔ)結(jié)構(gòu)3、遍歷4、線索化：線索樹順序結(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)前序線索樹中序線索樹后序線索樹樹二叉樹森林前序遍歷后續(xù)遍歷遍歷存儲(chǔ)結(jié)構(gòu)遍歷雙親表示孩子表示孩子兄弟先根遍歷后根遍歷中序遍歷后序遍歷前序遍歷霍夫曼樹霍夫曼編碼關(guān)于樹的小結(jié)第6講圖及其應(yīng)用圖的相關(guān)定義(無向完全圖、有向完全圖、網(wǎng)、連通圖、強(qiáng)連通圖、度、入度、出度、生成樹和生成森林)圖的存儲(chǔ)方式鄰接矩陣無向圖鄰接矩陣有向圖鄰接矩陣網(wǎng)的鄰接矩陣每個(gè)結(jié)點(diǎn)的出度？入度？度？圖的邊數(shù)？鄰接表每個(gè)結(jié)點(diǎn)的出度？入度？度？圖的邊數(shù)？例已知某網(wǎng)的鄰接（出邊）表，請(qǐng)畫出該網(wǎng)絡(luò)。當(dāng)鄰接表的存儲(chǔ)結(jié)構(gòu)形成后，圖便唯一確定！例題解析圖的遍歷廣度優(yōu)先搜索從圖的某一結(jié)點(diǎn)出發(fā)，首先依次訪問該結(jié)點(diǎn)的所有鄰接頂點(diǎn)V1,V2,…,Vn

再按這些頂點(diǎn)被訪問的先后次序依次訪問與它們相鄰接的所有未被訪問的頂點(diǎn)，重復(fù)此過程，直至所有頂點(diǎn)均被訪問為止。深度優(yōu)先搜索1、訪問指定的起始頂點(diǎn)；2、若當(dāng)前訪問的頂點(diǎn)的鄰接頂點(diǎn)有未被訪問的，則任選一個(gè)訪問之；反之，退回到最近訪問過的頂點(diǎn)；直到與起始頂點(diǎn)相通的全部頂點(diǎn)都訪問完畢；3、若此時(shí)圖中尚有頂點(diǎn)未被訪問，則再選其中一個(gè)頂點(diǎn)作為起始頂點(diǎn)并訪問之，轉(zhuǎn)2；反之，遍歷結(jié)束。例題解析12/04/202493熟悉圖的存儲(chǔ)結(jié)構(gòu)，畫出右邊有向圖的鄰接矩陣、鄰接表、逆鄰接表。寫出鄰接表表示的圖從頂點(diǎn)A出發(fā)的深度優(yōu)先遍歷序列和廣度優(yōu)先遍歷序列。深度優(yōu)先遍歷序列為ABCFED，廣度優(yōu)先遍歷序列為ABDCEF鄰接矩陣如下鄰接表如下逆鄰接表如下【答】最小生成樹普里姆（Prim）算法將頂點(diǎn)進(jìn)行歸并克魯斯卡爾（Kruscal）算法將邊進(jìn)行歸并例：Prim算法最小代價(jià)生成樹的生成過程UV0V1V3V2V4V56165556342V0V1V3V2V4V515342(4)(1)(3)(2)(5)例：Kruscal算法

實(shí)例的執(zhí)行過程

圖G1、初始連通分量：{0},{1},{2},{3},{4},{5}2、反復(fù)執(zhí)行添加、放棄動(dòng)作。

條件：邊數(shù)不等于n-1時(shí)邊 動(dòng)作 連通分量

(0,2)添加 {0,2},{1},{3},{4},{5}(3,5)添加 {0,2},{3,5},{1},{4}(1,4)添加 {0,2},{3,5},{1,4}(2,5)添加 {0,2,3,5},{1,4}(0,3)放棄 因構(gòu)成回路

(2,3)放棄 因構(gòu)成回路

(1,2)添加 {0,2,3,5,1,4}最小代價(jià)生成樹V0V1V3V2V4V56165556342V0V1V3V2V4V51534255例題解析請(qǐng)分別用Prim算法和Kruskal算法構(gòu)造以下網(wǎng)絡(luò)的最小生成樹，并求出該樹的代價(jià)。12/04/202497例題解析12/04/202498【解析】Prim算法的操作步驟：首先從一個(gè)只有一個(gè)頂點(diǎn)的集合開始，通過加入與其中頂點(diǎn)相關(guān)聯(lián)的最小代價(jià)的邊來擴(kuò)充頂點(diǎn)集，直到所有頂點(diǎn)都在一個(gè)集合中。例題解析12/04/202499【解析】Kruscal算法的操作步驟：首先將n個(gè)頂點(diǎn)看成n個(gè)互不連通的分量，從邊集中找最小代價(jià)的邊，如果落在不同連通分量上，則將其加入最小生成樹，直到所有頂點(diǎn)都在同一連通分量上。單源最短路徑在帶權(quán)有向圖中A點(diǎn)（源點(diǎn)）到達(dá)B點(diǎn)（終點(diǎn)）的多條路徑中，尋找一條各邊權(quán)值之和最小的路徑，即最短路徑。迪杰斯特拉(Dijkstra)算法：

按路徑長(zhǎng)度遞增次序產(chǎn)生最短路徑1、把V分成兩組：

(1)S：已求出最短路徑的頂點(diǎn)的集合。

(2)V-S=T：尚未確定最短路徑的頂點(diǎn)集合。2、將T中頂點(diǎn)按最短路徑遞增的次序加入到S中，保證：(1)從源點(diǎn)v0

到S中各頂點(diǎn)的最短路徑長(zhǎng)度都不大于