數(shù)據(jù)結(jié)構(gòu)-Python語言描述教案

教案

講授章節(jié)第1章緒論

授課時(shí)數(shù)2

教學(xué)目的：

1.介紹數(shù)據(jù)結(jié)構(gòu)的基本概念（P2）

2.算法的描述(P8)和算法時(shí)間復(fù)雜度(P10)空間復(fù)雜度(P10)

3.要求了解本章介紹的各種基本概念和術(shù)語，是全書的基礎(chǔ)。

教學(xué)內(nèi)容（課程導(dǎo)入）

一數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)基本概念：指的是相互之間存在著一種或者多種關(guān)系的數(shù)據(jù)元素的集合，也叫

數(shù)據(jù)元素類，是數(shù)據(jù)的一個(gè)自己，數(shù)據(jù)元素是數(shù)據(jù)對(duì)象的一個(gè)實(shí)例。

數(shù)據(jù)的邏輯結(jié)構(gòu)可分為四類：1）集合2）線性結(jié)構(gòu)3）樹形結(jié)構(gòu)4）圖形結(jié)構(gòu)P3【圖

1.2】

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可分為四類：1）順序存儲(chǔ)結(jié)構(gòu)2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)3）索引存儲(chǔ)結(jié)構(gòu)4）

散列存儲(chǔ)結(jié)構(gòu)

數(shù)據(jù)操作：1）創(chuàng)建操作2）插入創(chuàng)造3）刪除創(chuàng)造4）查找創(chuàng)造5）修改操作6）遍

歷操作7）銷毀操作

數(shù)據(jù)類型：是一組性質(zhì)相同的值的集合和定義在此集合上的一組操作的總稱。

數(shù)據(jù)抽象：數(shù)據(jù)抽象指“定義和實(shí)現(xiàn)相分離”，即將一個(gè)類型的數(shù)據(jù)及其上的操作的邏

輯含義和具體實(shí)現(xiàn)相分離，只考慮執(zhí)行什么操作，而不考慮怎樣實(shí)現(xiàn)這些操作。

抽象數(shù)據(jù)類型：抽象數(shù)據(jù)類型是從問題的數(shù)學(xué)模型中抽象出來的邏輯結(jié)構(gòu)定義在邏輯結(jié)

構(gòu)上的一組操作，進(jìn)描述了數(shù)據(jù)的特性和數(shù)據(jù)操作的語法規(guī)則，隱藏了數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和操

作的實(shí)現(xiàn)細(xì)節(jié)。P6【例1.2】

二算法：

算法的定義：算法是有窮規(guī)則的集合，其規(guī)則確定一個(gè)解決某一特定類型問題的指令序

列，其中每一條指令表示計(jì)算機(jī)的一個(gè)或者多個(gè)操作。

算法必須滿足五個(gè)特性：1）有窮性2）確定性3）可行性4）有輸入5）有輸出

算法建立在數(shù)據(jù)結(jié)構(gòu)上，對(duì)數(shù)據(jù)結(jié)構(gòu)的操作需要使用算法來描述。算法設(shè)計(jì)依賴于數(shù)據(jù)

的邏輯結(jié)構(gòu)，算法實(shí)現(xiàn)依賴于數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。

算法描述：算法可以采用1）自然語言2）程序設(shè)計(jì)語言3）偽代碼多種語言來描述

P9【例1.3】

三算法分析

算法分析是主要是通過某種方法討論算法的復(fù)雜度，評(píng)價(jià)算法的效率，以便在解決實(shí)際

問題時(shí)根據(jù)實(shí)際情況和算法的優(yōu)缺點(diǎn)對(duì)算法進(jìn)行取舍。

四算法的時(shí)間復(fù)雜度

是指算法的執(zhí)行時(shí)間雖問題規(guī)模的變化而變化的趨勢(shì)，反映算法執(zhí)行時(shí)間的長(zhǎng)短。執(zhí)行時(shí)

間是用算法編寫的程序在計(jì)算機(jī)上運(yùn)行的時(shí)間，他是算法中涉及的所有的基本運(yùn)算的執(zhí)行時(shí)

間之和。

·通常采用算法的漸進(jìn)分析中的大O表示作為算法時(shí)間復(fù)雜度的漸進(jìn)度量值，稱為算法

的漸進(jìn)時(shí)間復(fù)雜度。

·循環(huán)語句的時(shí)間代價(jià)一般可用一下3條原則進(jìn)行分析：

1）一個(gè)循環(huán)的時(shí)間代價(jià)=循環(huán)次數(shù)每次執(zhí)行的基本指令數(shù)目。

2）多個(gè)并列的循環(huán)的時(shí)間代價(jià)=每個(gè)循環(huán)的時(shí)間代價(jià)之和。

3）多層嵌套循環(huán)的時(shí)間代價(jià)=每層循環(huán)的時(shí)間代價(jià)值積。

五算法的時(shí)間/空間復(fù)雜度

·.算法分析舉例書本P11【例1.4】

本章節(jié)的教學(xué)重點(diǎn)、難點(diǎn)：

1.重點(diǎn)是數(shù)據(jù)結(jié)構(gòu)的基本概念

2.難點(diǎn)是時(shí)間復(fù)雜度分析

教學(xué)方法、教學(xué)手段：

1.介紹到算法概念

2.算法分析和舉例

使用教具：計(jì)算機(jī)和投影儀

作業(yè)、討論題、思考題：

P12

講授章節(jié)第二章線性表

授課時(shí)數(shù)7

教學(xué)目的：

1.介紹線性表的基本概念（P15）和各種存儲(chǔ)表示方法(P16-18)

2.定義在邏輯結(jié)構(gòu)上的各種基本運(yùn)算及在存儲(chǔ)結(jié)構(gòu)上如何實(shí)現(xiàn)這些基本運(yùn)算

(P18-22)。

3.要求在這些內(nèi)容的基礎(chǔ)上，能夠針對(duì)具體應(yīng)用問題的要求和性質(zhì)，選擇合適的存儲(chǔ)

結(jié)構(gòu)設(shè)計(jì)出相應(yīng)的有效算法，解決與線性表相關(guān)的實(shí)際問題。

教學(xué)內(nèi)容（講授提綱）

一線性表

線性表的Python抽象類的實(shí)現(xiàn)方法主要有以下兩種

1）基于順序存儲(chǔ)的實(shí)現(xiàn)2）基于鏈?zhǔn)酱鎯?chǔ)的實(shí)現(xiàn)。

二線性表的順序存儲(chǔ)

定義：是把線性表中的所有元素按照其邏輯順序依次存儲(chǔ)到計(jì)算機(jī)的內(nèi)存單元中指定存

儲(chǔ)位置開始的一塊連續(xù)的存儲(chǔ)空間中，成為順序表。P17圖2.2

特點(diǎn)：

1)在線性表中邏輯上相鄰的元素在物理存儲(chǔ)位置上也同樣相鄰。

2)可按照數(shù)據(jù)元素的位序號(hào)進(jìn)行隨機(jī)存取。

3)進(jìn)行插入，殺出操作需要移動(dòng)大量的數(shù)據(jù)元素。

4)需要進(jìn)行存儲(chǔ)空間的預(yù)先分配，可能會(huì)造成空間浪費(fèi)，但存儲(chǔ)密度較高

描述：P17

插入操作：

P19圖2.3主要步驟為：

判斷順序表的存儲(chǔ)空間是否已滿，若已滿則拋出異常。

1）判斷參數(shù)i的值是否滿足0<=i<=curLen，若不滿足則拋出異常。

2）將插入位置及其之后的所有數(shù)據(jù)元素后移一個(gè)存儲(chǔ)位置。

3）在位置i出插入新的數(shù)據(jù)元素x。

4）在插入位置及其新的數(shù)據(jù)元素。

5）表長(zhǎng)加1.P19【算法2.1】

刪除操作

P20圖2.4主要步驟為：

1）判斷參數(shù)i是否滿足i<=i<=curLen-1,若不滿足則拋出異常。

2）將第i個(gè)數(shù)據(jù)元素之后的數(shù)據(jù)元素都向前移動(dòng)一個(gè)存儲(chǔ)單元。

3）表長(zhǎng)減1.P20【算法2.2】

查找操作

主要步驟為將x與順序表中的每一個(gè)數(shù)據(jù)元素的值進(jìn)行比較，若相等，則返回該數(shù)據(jù)元

素的位置；若比較結(jié)束未找到等值的數(shù)據(jù)元素，返回-1.

P21【算法2.3】【例2.3】P22【例2.4】

三線性表的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn)

采用鏈?zhǔn)酱鎯?chǔ)方式存儲(chǔ)的線性表稱為鏈表，鏈表是用若干地址分散的存儲(chǔ)單元存儲(chǔ)數(shù)據(jù)

元素。邏輯上相鄰的數(shù)據(jù)元素在屋里位置上不一定相鄰，必須采用附加欣喜表示數(shù)據(jù)元素之

間的邏輯關(guān)系，因此鏈表的每一個(gè)結(jié)點(diǎn)不僅包含元素本身的信息-數(shù)據(jù)域，而且包含元素之

間的邏輯關(guān)系的信息，即邏輯上相鄰結(jié)點(diǎn)地址的指針域。

單鏈表

單鏈表指結(jié)點(diǎn)中只包含一個(gè)指針域的鏈表，指針域中儲(chǔ)存著指向后繼結(jié)點(diǎn)的指針。P22

圖2.5、2.6

查找操作

其主要步驟為將x與單鏈表中的每一個(gè)數(shù)據(jù)元素的數(shù)據(jù)域進(jìn)行比較，若想等，則返回該

數(shù)據(jù)元素在單鏈表中的位置；若比較結(jié)束未找到等值的數(shù)據(jù)元素，返回-1.

P24【算法2.4】【算法2.5】

插入操作

主要步驟如下：

1）查找到插入位置的前驅(qū)結(jié)點(diǎn)，即第i-1個(gè)結(jié)點(diǎn)。

2）創(chuàng)建數(shù)據(jù)域值為x的新節(jié)點(diǎn)。

3）修改前去結(jié)點(diǎn)的指針域?yàn)橹赶蛐鹿?jié)點(diǎn)的指針，新結(jié)點(diǎn)的指針域位指向原第i個(gè)結(jié)點(diǎn)

的指針。

P25【算法2.6】【算法2.7】

刪除操作

主要步驟如下

1）判斷單鏈表是否為空。

2）查找待刪除結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。

3）修改前驅(qū)結(jié)點(diǎn)的指針域?yàn)榇齽h除結(jié)點(diǎn)的指針域。P26【算法2.8】

單鏈表的建立操作

1)頭插法P26【算法2.9】

2)尾插法P27【算法2.10】

本章節(jié)的教學(xué)重點(diǎn)、難點(diǎn)

本章重點(diǎn)是熟練掌握順序表(P17-21)和單鏈表(P22-27)上實(shí)現(xiàn)的各種基本算法及相關(guān)

的時(shí)間性能分析，難點(diǎn)是能夠使用本章學(xué)到的基本知識(shí)設(shè)計(jì)有效算法與線性表相關(guān)的應(yīng)用問

題。

教學(xué)方法、教學(xué)手段：

1.開始到順序表中各種操作實(shí)現(xiàn)

2.順序表算法鐘）

使用教具：計(jì)算機(jī)和投影儀

作業(yè)、討論題、思考題：

P28-30

講授章節(jié)第三章棧

授課時(shí)數(shù)6

教學(xué)目的：

1.介紹棧（P31）和隊(duì)列(P37)的邏輯結(jié)構(gòu)定義

2.兩種順序結(jié)構(gòu)上如何實(shí)現(xiàn)棧(P32-36)和隊(duì)列(P38-46)的基本運(yùn)算。

3.要求在掌握棧和隊(duì)列的特點(diǎn)的基礎(chǔ)上，懂得在什么樣的情況下能夠使用?；蜿?duì)列。

教學(xué)內(nèi)容（講授提綱）

一棧

棧的概念：棧是一種特殊的線性表，其插入，刪除操作只能在表的尾部進(jìn)行。在棧中允

許進(jìn)行插入，刪除操作的一端稱為棧頂，另一端稱為棧底。

在棧{a0，a1，a2，……，an-1}中a0成為占地元素，an-1成為棧頂元素。通常，棧的

插入叫做入棧，站的刪除操作交出棧。

棧的抽象數(shù)據(jù)Python接口包含了棧的主要基本操作，如果要使用這個(gè)接口還需要具體的

類來實(shí)現(xiàn)。棧的Python接口的實(shí)現(xiàn)方法主要有以下兩種：

1）基于順序存儲(chǔ)的實(shí)現(xiàn)，為順序棧；

2）基于鏈?zhǔn)酱鎯?chǔ)的實(shí)現(xiàn)，為鏈棧。

順序棧

順序棧基本操作的實(shí)現(xiàn)入棧操作(P33圖3.1)

1）判斷順序棧是否為滿，若滿則拋出異常。

2）將x存入top所指的存儲(chǔ)單元位置。

3）Top加1.P33【算法3.1】P33【算法3.2】P34【例3.1】

鏈棧

鏈棧的存儲(chǔ)結(jié)構(gòu)：P34圖3.3

鏈?；静僮鞯膶?shí)現(xiàn)

1）入棧操作，主要步驟如下

1)改造購書值域?yàn)閤的新結(jié)點(diǎn)。

2)改變新結(jié)點(diǎn)和首結(jié)點(diǎn)指針域，是新結(jié)點(diǎn)成為新的棧頂頂點(diǎn)。

鏈棧進(jìn)行入棧操作后的狀態(tài)棉花如圖P363.4所示

P36【算法3.3】

2）出棧操作，主要步驟如下

1）判斷鏈棧是否為空，若空則返回null。

2）修改top指針域的值，返回被刪結(jié)點(diǎn)的數(shù)據(jù)域值。

鏈棧進(jìn)行出棧操作后的狀態(tài)變化如圖3.5所示P40

P36[【算法3.4】【例3.2】]P37[【例3.3】【例3.4】]

二隊(duì)列

隊(duì)列的基本概念

隊(duì)列是一種特殊的線性表，其插入操作只能在表的尾部進(jìn)行，刪除操作只能在表頭進(jìn)行。

通常，隊(duì)列的插入操作交入隊(duì)，隊(duì)列的刪除操作叫出隊(duì)。沒有數(shù)據(jù)元素的隊(duì)列稱為空隊(duì)

列。

隊(duì)列的抽象數(shù)據(jù)Python接口包含了隊(duì)列的主要的基本操作，如果要使用這個(gè)接口，還

需要具體的類來實(shí)現(xiàn)。隊(duì)列的Python抽象類的實(shí)現(xiàn)方法主要有以下兩種：

1）基于順序存儲(chǔ)的實(shí)現(xiàn)，為順序隊(duì)列。

2）基于鏈?zhǔn)酱鎯?chǔ)的實(shí)現(xiàn)，為鏈隊(duì)列。

順序隊(duì)列

順序隊(duì)列的存儲(chǔ)結(jié)構(gòu)與順序棧類似，可用數(shù)組實(shí)現(xiàn)，因?yàn)槿腙?duì)和出隊(duì)操作分別在對(duì)為和

對(duì)手進(jìn)行，所以增加變量front來只是隊(duì)首元素的位置，rear指示隊(duì)尾元素的下一個(gè)存儲(chǔ)

單元的位置。順序隊(duì)列進(jìn)行入隊(duì)操作的狀態(tài)變化如P39圖3.7進(jìn)行出對(duì)操作后的狀態(tài)變化

P37圖3.8

順序隊(duì)列之所以會(huì)出現(xiàn)“假溢出”（P40圖3.9）現(xiàn)象是因?yàn)轫樞蜿?duì)列的存儲(chǔ)單元沒有重

復(fù)使用機(jī)制，為了解決順序隊(duì)列因數(shù)組下標(biāo)越界而應(yīng)起的“溢出”問題，課將順序序列的首

位項(xiàng)鏈，形成循環(huán)順序隊(duì)列。

循環(huán)順序隊(duì)列進(jìn)行入隊(duì)和出對(duì)操作后狀態(tài)變化如P40圖3.10P41【例3.5】【例3.6】

鏈隊(duì)列是單鏈表實(shí)現(xiàn)，由于入隊(duì)和出對(duì)分別在隊(duì)尾和隊(duì)首進(jìn)行，不存在在隊(duì)列的任意位

置進(jìn)行插入和刪除的情況，所以不需要設(shè)置頭結(jié)點(diǎn)，只需要將指針front和rear分別指向

對(duì)手節(jié)點(diǎn)和對(duì)為節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的指針域指向其后繼結(jié)點(diǎn)即可。

P42圖3.12所示為鏈隊(duì)列進(jìn)行入隊(duì)操作的狀態(tài)變化。

本章節(jié)的教學(xué)重點(diǎn)、難點(diǎn)：

本章重點(diǎn)是掌握棧(P31-36)和隊(duì)列(P37-44)在兩種存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)的基本運(yùn)算.

教學(xué)方法、教學(xué)手段：

1．棧的基本概念和順序棧

2．鏈棧、中綴表達(dá)式求值

使用教具：計(jì)算機(jī)和投影儀

作業(yè)、討論題、思考題：

P47、48、49

講授章節(jié)第四章串和數(shù)組

授課時(shí)數(shù)5

教學(xué)目的：

1.本章主要是介紹串的基本概念（P50）

2.數(shù)據(jù)類型定義(P50)

3.串的存儲(chǔ)結(jié)構(gòu)，基本操作實(shí)現(xiàn)和應(yīng)用等(P51)。

4.介紹多維數(shù)組的邏輯結(jié)構(gòu)特征及存儲(chǔ)方式（P60-61），特殊矩陣和稀疏矩陣的壓

縮存儲(chǔ)方法(P61-64)。

教學(xué)內(nèi)容（講授提綱）

一串

串的概念：字符串也叫串，是有字符組成的有限序列，是一種常用的非數(shù)值數(shù)據(jù)。串的

邏輯結(jié)構(gòu)是線性表，串是一種特殊的線性表，其每個(gè)數(shù)據(jù)元素都是一個(gè)字符。穿的操作特點(diǎn)

與線性表不同，，主要是對(duì)字串進(jìn)行操作，通過采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)。

串的比較規(guī)則和字符的比較規(guī)則有關(guān)，字符的比較規(guī)則由所屬的字符集的編碼決定。

字符串的抽象數(shù)據(jù)類型Python抽象類包含了串的主要基本操作，如果要使用這個(gè)接口，

還需要具體的類來實(shí)現(xiàn)。串的Python抽象類的實(shí)現(xiàn)方法主要有以下兩點(diǎn)：

1）基于順序存儲(chǔ)的實(shí)現(xiàn)，為順序串；

2）基于鏈?zhǔn)酱鎯?chǔ)的實(shí)現(xiàn)，為鏈串。

順序串

順序串與順序表的邏輯結(jié)構(gòu)相同，存儲(chǔ)結(jié)構(gòu)類似，均可用數(shù)組來存儲(chǔ)數(shù)據(jù)元素。但串具

有獨(dú)特的不同雨線性表的操作，屬于特殊類型的線性表。如P51圖4.1

順序串基本操作的實(shí)現(xiàn)

1）求子串操作；P53【算法4.1】

2）插入操作主要步驟如下：

1）判斷參數(shù)i是否0<=i<=n，若不滿足，則拋出異常。

2）重新分配存儲(chǔ)空間為n+m，m為插入的字符串str的長(zhǎng)度。

3）將第i個(gè)及之后的數(shù)據(jù)元素向后移動(dòng)m個(gè)存儲(chǔ)單元。

4）將str插入到字符串從i開始的位置。

3）刪除操作P54[【算法4.2】【算法4.3】]

4)連接操作

5）比較操作主要步驟如下：

1）確定需要比較的字符的個(gè)數(shù)n為兩個(gè)字符串長(zhǎng)度的較小值。

2）從下標(biāo)0至n-1依次進(jìn)行比較P54-55[【算法4.4】【例4.1】]

鏈串的兩種存儲(chǔ)結(jié)構(gòu)P55圖4.2

串的匹配模式

串的模式匹配也叫查找定位，指的是在當(dāng)前串中的尋找模式串的過程，主要的模式匹配

算法有Brute-Force算法和KMP算法。

Brute-Force算法

是從主串的第一個(gè)字符開始和模式串的第一個(gè)字符進(jìn)行比較，若想等，則繼續(xù)比較后

續(xù)字符；否則從主串的第二個(gè)字符開始重新和模式串進(jìn)行比較。以此類推，知道模式串的每

個(gè)字符一次與朱傳的字符相等，匹配成功。P56【算法4.5】

KMP算法

Kmp算法的主要思想是當(dāng)某次匹配失敗時(shí)主串的開始標(biāo)位置不會(huì)推推，而是利用部分字

符匹配的結(jié)果將模式串向右移動(dòng)較遠(yuǎn)的距離后再繼續(xù)進(jìn)行比較。

Kmp模式匹配算法分析

K值的計(jì)算P57【算法4.6】

Kmp算法步驟

1）計(jì)算模式穿的next[]函數(shù)值

2）I為主串的比較字符位序號(hào)，j為模式串的比較字符位序號(hào)。當(dāng)字符相等時(shí)，i，

j分別加1后繼續(xù)比較；否則i的值不變，j=next[j],繼續(xù)比較。

3）重復(fù)步驟2），直到j(luò)等于模式串的長(zhǎng)度是匹配成功，否則匹配失敗。

P58[【算法4.7】【例4.2】【例4.3】]

二數(shù)組

數(shù)組是n個(gè)具有相同數(shù)據(jù)類型的數(shù)據(jù)元素構(gòu)成的集合，數(shù)組元素按某種次序存儲(chǔ)在地質(zhì)

連續(xù)的存儲(chǔ)單元中，是順序存儲(chǔ)的隨機(jī)存儲(chǔ)結(jié)構(gòu)。

數(shù)組元素在數(shù)組中的位置成為數(shù)組元素的下標(biāo)，用戶通過下標(biāo)可以訪問相應(yīng)的數(shù)組元素。

數(shù)組的下標(biāo)的個(gè)數(shù)是數(shù)組的維數(shù)，具有一個(gè)下標(biāo)的數(shù)組叫一維數(shù)組，具有兩個(gè)下標(biāo)的數(shù)

組叫二維數(shù)組。

一維數(shù)組的邏輯結(jié)構(gòu)是線性表，多維數(shù)組是線性表的擴(kuò)展。

數(shù)組的特性

數(shù)組元素被存放在一組地址連續(xù)的存儲(chǔ)單元里，并且每個(gè)數(shù)據(jù)元素的大小相同，故只要

已知首地址和每個(gè)數(shù)據(jù)元素占用的內(nèi)存單元大小即可求出數(shù)組中任意數(shù)據(jù)元素的存儲(chǔ)地址。

數(shù)組的遍歷

對(duì)二維數(shù)組進(jìn)行遍歷操作有兩種次序，即行主序和列主序。P61【例4.4】

三特殊矩陣的壓縮存儲(chǔ)

在科學(xué)技術(shù)和工程計(jì)算的許多領(lǐng)域，矩陣是數(shù)值分析問題研究的對(duì)象。

本章將以特殊矩陣為例介紹矩陣的壓縮存儲(chǔ)。

矩陣采用二維數(shù)組進(jìn)行存儲(chǔ)，至少占用mxn個(gè)存儲(chǔ)單元。

三角矩陣的壓縮存儲(chǔ)

線性壓縮存儲(chǔ)

使用三角形的二維數(shù)組壓縮存儲(chǔ)

對(duì)稱矩陣的壓縮存儲(chǔ)

對(duì)角矩陣的壓縮存儲(chǔ)

稀疏矩陣的壓縮存儲(chǔ)

1.稀疏矩陣的非零元素三元組P64【算法4.8】

矩陣元素的行號(hào)，列號(hào)和元素值稱為鈣元素的三元組。

2.稀疏矩陣的十字鏈表存儲(chǔ)P64【例4.5】

本章節(jié)的教學(xué)重點(diǎn)、難點(diǎn)：

1．中綴表達(dá)式轉(zhuǎn)成前綴、后綴表達(dá)式，并對(duì)兩種表達(dá)式求值。

2．用遞歸解決的問題：?jiǎn)栴}的定義是遞歸的，數(shù)據(jù)結(jié)構(gòu)是遞歸的，以及問題的解法是

遞歸的，掌握典型問題的算法。將遞歸算法轉(zhuǎn)為非遞歸算法，特別是尾遞歸的消除。

教學(xué)方法、教學(xué)手段：

使用教具：計(jì)算機(jī)和投影儀

作業(yè)、討論題、思考題：

P65、P66，P67

講授章節(jié)第五章樹形結(jié)構(gòu)

授課時(shí)數(shù)7

教學(xué)目的：

1.介紹樹的定義（P68）

2.二叉樹的定義和性質(zhì)(69)

3.存儲(chǔ)結(jié)構(gòu)(P71)

4.遍歷及算法和應(yīng)用（P72-79）

5.哈夫曼樹及哈夫曼編碼(P79-83)等內(nèi)容。

教學(xué)內(nèi)容（講授提綱）

一樹

樹的概念

樹是數(shù)據(jù)元素之間具有層次關(guān)系的非線性結(jié)構(gòu)，是由n個(gè)結(jié)點(diǎn)構(gòu)成的有限集合，結(jié)點(diǎn)數(shù)

為0的樹叫空樹。

樹必須滿足：

1）有且僅有一個(gè)被稱為根的結(jié)點(diǎn)。

2）其余結(jié)點(diǎn)可分為m個(gè)互不相交的有限集合，每個(gè)集合又構(gòu)成一棵樹，叫根結(jié)點(diǎn)的子

樹。

樹的表示方法有很多種，如樹形表示法，文氏圖表示法，凹入圖表示法和廣義表表示法。

見68[圖5.1圖5.2]

樹的術(shù)語P69需熟悉

二叉樹

二叉樹的基本概念

1）普通二叉樹

2）滿二叉樹

3）完全二叉樹

二叉樹的性質(zhì)

有五個(gè)性質(zhì)P705.2.2、P70-71[【例5.1】【例5.2】]

二叉樹的存儲(chǔ)結(jié)構(gòu)

二叉樹的順序存儲(chǔ)結(jié)構(gòu)：是指將二叉樹的各個(gè)結(jié)點(diǎn)存放在一組地址連續(xù)的存儲(chǔ)單元中，

所有結(jié)點(diǎn)按結(jié)點(diǎn)序號(hào)進(jìn)行順序存儲(chǔ)?？梢岳?.2.2節(jié)總的性質(zhì)5將二叉樹的結(jié)點(diǎn)排成線性

序列，將節(jié)點(diǎn)存放在下標(biāo)為對(duì)應(yīng)編號(hào)的數(shù)組元素中。示意圖P71圖5.5

二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：是指將二叉樹的各個(gè)結(jié)點(diǎn)隨機(jī)存放在存儲(chǔ)空間中，二叉樹的各

結(jié)點(diǎn)間的邏輯關(guān)系由指針確定。

二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)又分為P72[【圖5.6】]

1）二叉鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

2）三叉鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

二叉樹鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的結(jié)點(diǎn)類的描述

二叉樹類的描述

二叉樹的遍歷

二叉樹的遍歷方法

二叉樹通常可劃分為三個(gè)部分，即根結(jié)點(diǎn)，左子樹和右子樹。根據(jù)3個(gè)部分的訪問順

序不同，可將二叉樹的遍歷方法分為：P73[【圖5.7】]

1）層次遍歷

2）P73先序遍歷【算法5.1】

3）P73中序遍歷【算法5.2】

4）P73后序遍歷【算法5.3】

二叉樹遍歷操作實(shí)現(xiàn)的遞歸算法

二叉樹遍歷操作實(shí)現(xiàn)的非遞歸算法

將遞歸算法轉(zhuǎn)換成非遞歸算法

·使用臨時(shí)便利保存中間結(jié)果，用循環(huán)結(jié)構(gòu)代替遞歸過程

·利用棧保存中間結(jié)果

1）P74先序遍歷【算法5.4】

2）P74中序遍歷【算法5.5】

3）P75后序遍歷【算法5.6】

4）P75層次遍歷【算法5.7】

二叉樹遍歷算法的應(yīng)用

二叉樹上的查找算法P76【算法5.8】

統(tǒng)計(jì)二叉樹的結(jié)點(diǎn)個(gè)數(shù)的算法P77【算法5.9】

二叉樹的深度P77【算法5.10】

二叉樹的建立P79[【例5.3】【圖5.9】]

1）由中序和先序遍歷序列建立二叉樹P78[【圖5.8】【算法5.11】]

2）由標(biāo)明空子樹的先序遍歷序列創(chuàng)建二叉樹P79[【算法5.12】]

二哈夫曼樹及哈夫曼編碼

哈夫曼樹的基本概念

1結(jié)點(diǎn)間的路徑

2節(jié)點(diǎn)的路徑長(zhǎng)度

3結(jié)點(diǎn)的權(quán)

4節(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度

5樹的帶權(quán)路徑長(zhǎng)度

6最優(yōu)二叉樹

哈夫曼樹的構(gòu)造

P81【圖5.10】P80【例5.4】

構(gòu)造哈夫曼樹和哈夫曼編碼的類的描述

構(gòu)造哈夫曼樹需要從子結(jié)點(diǎn)到父結(jié)點(diǎn)的操作，譯碼是需要從父結(jié)點(diǎn)到子結(jié)點(diǎn)的操作，所

以為了提高算法的效率將哈夫曼樹的結(jié)點(diǎn)設(shè)計(jì)為三叉鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

構(gòu)造哈夫曼樹P82【算法5.13】

求哈夫曼編碼P82【算法5.14】P83【例5.5】

三樹和森林

樹的存儲(chǔ)結(jié)構(gòu)

1樹的父母孩子鏈表

2樹的父母孩子兄弟鏈表

樹的遍歷規(guī)則

樹的孩子有限遍歷規(guī)則有兩種

1）樹的先序遍歷

2）樹的后序遍歷

樹的遍歷規(guī)則也是遞歸的

本章節(jié)的教學(xué)重點(diǎn)、難點(diǎn)：

重點(diǎn)掌握二叉樹的遍歷算法及其與有關(guān)應(yīng)用（P76-79）

難點(diǎn)是使用本章所學(xué)到的有關(guān)知識(shí)設(shè)計(jì)出有效算法

解決與樹或二叉樹相關(guān)的應(yīng)用問題。

教學(xué)方法、教學(xué)手段：

使用教具：計(jì)算機(jī)和投影儀

作業(yè)、討論題、思考題：

P84、P85、P86

講授章節(jié)第六章圖

授課時(shí)數(shù)7

教學(xué)目的：

1.主要介紹圖的基本概念（P87）

2.抽象數(shù)據(jù)類型定義和存儲(chǔ)結(jié)構(gòu)(P89-96),遍歷方法（P97-P101）

3.介紹最小生成樹的基本概念和算法(P102-104)

4.最短路徑的相關(guān)算法(P104-107)，拓?fù)渑判虻母拍詈蛯?shí)現(xiàn)方法(P107-110)。

教學(xué)內(nèi)容（講授提綱）

一圖概述

圖的概念

無向邊

有向邊

零圖

無向圖

有向圖

完全圖P88【圖6.16.26.3】

稠密圖

子圖

生成子圖

鄰接點(diǎn)

頂點(diǎn)的度

路徑

回路

連通圖

連通分量

強(qiáng)連通圖

強(qiáng)連通分量

生成樹和生成森林

網(wǎng)

圖的抽象數(shù)據(jù)類型描述

二圖的存儲(chǔ)結(jié)構(gòu)

鄰接矩陣

1.圖的鄰接矩陣的存儲(chǔ)結(jié)構(gòu)

2.圖的鄰接矩陣類的基本操作的實(shí)現(xiàn)

1）圖的創(chuàng)建【P90算法6.1P91[6.26.3]P916.4】（創(chuàng)建無/有向圖，創(chuàng)建

無/有向網(wǎng)）

2）頂點(diǎn)的定位P92【算法6.5】

3）查找第一個(gè)鄰接點(diǎn)P92【算法6.6】

4）查找下一個(gè)鄰接點(diǎn)P92【算法6.7】

3.鄰接矩陣表示圖的性能分析P93【例6.1】

鄰接表

1.圖的鄰接表存儲(chǔ)結(jié)構(gòu)

2.圖的鄰接表的基本操作的實(shí)現(xiàn)

1）圖的創(chuàng)建【算法P95[6.86.9]P96[6.106.11]】（創(chuàng)建無/有向圖，創(chuàng)建無/

有向網(wǎng)）

2）在圖中插入邊節(jié)點(diǎn)P96【算法6.12】

3）查找第一個(gè)鄰接點(diǎn)P96【算法6.13】

4）查找下一個(gè)鄰接點(diǎn)

三圖的遍歷

圖的遍歷概念

圖的遍歷方式分為

1.廣度優(yōu)先搜索

圖的廣度優(yōu)先搜索遵循“先被訪問的頂點(diǎn)，其鄰接點(diǎn)先被訪問”的規(guī)則P98【算法

6.14】

2.深度優(yōu)先搜索

P99[【算法6.15】【例6.2】]P100【例6.3】

P100-101[【例6.4】【例6.5】]

四最小生成樹

在一個(gè)網(wǎng)的所有生成樹中權(quán)值總和最少的生成樹稱為最小代價(jià)生成樹，簡(jiǎn)稱為最小生成

樹，最小生成樹不一定唯一，需要滿足以下三條準(zhǔn)則

1）只能使用圖中的邊構(gòu)造最小生成樹

2）具有n個(gè)頂點(diǎn)和n-1條邊

3）不能使用產(chǎn)生回路的邊。

產(chǎn)生最小生成樹的算法主要有兩種

Krusakl算法

Prim算法

P104【例6.6】

五最短路徑

最短路徑的求解問題主要分為兩類

1.求某個(gè)頂點(diǎn)到其余頂點(diǎn)的最短路徑

2.求任意兩個(gè)頂點(diǎn)間的最短路徑

六拓?fù)渑判蚝完P(guān)鍵路徑

拓?fù)渑判?/p>

主要步驟

1).在AOV網(wǎng)中選擇一個(gè)沒有前去的頂點(diǎn)并輸出

2).在AOV網(wǎng)中刪除該頂點(diǎn)以及從它出發(fā)的弧

3).重復(fù)1.2直到AOV網(wǎng)為空，或者剩余子圖中不存在沒有前驅(qū)的頂點(diǎn)，此時(shí)說明AOV

網(wǎng)中存在環(huán)。

P108【算法6.166.17】

關(guān)鍵路徑

由于AOE網(wǎng)中某些活動(dòng)可以并行進(jìn)行，故完成整個(gè)工程的最短時(shí)間即從源點(diǎn)到匯點(diǎn)的最

長(zhǎng)路徑的長(zhǎng)度，這條路徑被稱為關(guān)鍵路徑，構(gòu)成關(guān)鍵路徑的弧即為關(guān)鍵活動(dòng)

P109-110【算法6.186.19】

本章節(jié)的教學(xué)重點(diǎn)、難點(diǎn)：

要求學(xué)生在熟悉這些內(nèi)容的基礎(chǔ)上

重點(diǎn)掌握?qǐng)D的存儲(chǔ)結(jié)構(gòu)和圖的兩種遍歷算法(P89-101))

本章難點(diǎn)是求最小生成樹的算法(P102-104)

最短路徑(P104-106)

拓?fù)渑判蚝完P(guān)鍵路徑算法(P107-110)。

教學(xué)方法、教學(xué)手段：

使用教具：計(jì)算機(jī)和投影儀

作業(yè)、討論題、思考題：

P111、P112

講授章節(jié)第七章排序

授課時(shí)數(shù)7

教學(xué)目的：

1.本章目的是介紹五類內(nèi)部排序方法的基本思想

2.排序過程

3.算法實(shí)現(xiàn)

4.時(shí)間和空間性能的分析以及各種排序方法的比較和選擇。

教學(xué)內(nèi)容（講授提綱）

一排序概述

排序的基本概念

是指將一組數(shù)據(jù)按照關(guān)鍵字值的大?。ㄟf增或遞減）次序進(jìn)行排列。

排序是線性表，二叉樹等數(shù)據(jù)結(jié)構(gòu)的一種基本操作。

排序算法的性能評(píng)價(jià)

通常從時(shí)間復(fù)雜度和空間復(fù)雜度兩個(gè)方面評(píng)價(jià)排序算法的性能

待排序的記錄和順序表的類描述

二插入排序

直接插入排序

1．直接插入算法的實(shí)現(xiàn)P114[【圖7.1】【算法7.1】]

2．算法性能分析

1.時(shí)間復(fù)雜度

2.空間復(fù)雜度

3.算法穩(wěn)定性

希爾排序

1.希爾排序算法的實(shí)現(xiàn)P115[【圖7.2】【算法7.2】]

2.算法性能分析

1.時(shí)間復(fù)雜度

2.空間復(fù)雜度

3.算法穩(wěn)定性

三交換排序

冒泡排序

1.冒泡算法的實(shí)現(xiàn)P116[【圖7.3】【算法7.3】

2.算法性能分析

1.時(shí)間復(fù)雜度

2.空間復(fù)雜度

3.算法穩(wěn)定性

快速排序

1.快速排序算法的實(shí)現(xiàn)P118【圖7.47.5】P119【算法7.4】

2.算法性能分析P120【例7.1】

1.時(shí)間復(fù)雜度

2.空間復(fù)雜度

3.算法穩(wěn)定性

四選擇排序

直接選擇排序

1.直接選擇排序算法的實(shí)現(xiàn)P121[【圖7.6】【算法7.5】]

2.算法性能分析

1.時(shí)間復(fù)雜度

2.空間復(fù)雜度

3.算法穩(wěn)定性

堆排序

1.堆的定義

是利用完全二叉樹特性的一種選擇排序

2.用篩選法調(diào)整堆

在進(jìn)行堆排序的過程中，當(dāng)堆頂元素和堆中的最后一個(gè)元素交換位置后根結(jié)點(diǎn)和其

子結(jié)點(diǎn)的關(guān)鍵字值不再滿足堆的含義，需要進(jìn)行調(diào)整。

3.堆排序P123【算法7.7】

4.算法性能分析P123【例7.2】

1.時(shí)間復(fù)雜度

2.空間復(fù)雜度

3.算法穩(wěn)定性

五歸并程序

1.兩個(gè)相鄰有序序列歸并P124【算法7.8】

2.一趟歸并排序P125[【算法7.9】]

3.二路歸并排序P125【算法7.10】

算法性能分析P125【例7.3】

1.時(shí)間復(fù)雜度

2.空間復(fù)雜度

3.算法穩(wěn)定性

本章節(jié)的教學(xué)重點(diǎn)、難點(diǎn)：

要求學(xué)生在熟悉這些內(nèi)容的基礎(chǔ)上