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

教學(xué)單元：數(shù)據(jù)結(jié)構(gòu)（本科）課程概述（2學(xué)時(shí)）

授課班級(jí)：

教學(xué)內(nèi)容提要：

1課程簡介：地位（考研、軟件開發(fā)崗位必考），在專業(yè)知識(shí)體系中的位置，就

業(yè)崗位等；

2課程主要內(nèi)容及學(xué)時(shí)分配；

3課程考核方式；

4課程學(xué)習(xí)方法；

5算法的基本概念和術(shù)語；

6Java語言編程回顧。

教學(xué)目的：

1了解該課程所研究的內(nèi)容、作用和發(fā)展?fàn)顩r，就業(yè)崗位，可以考取的證書等；

2了解算法基本概念和術(shù)語；

3在Eclipse環(huán)境下編輯一個(gè)簡單的求最大公約數(shù)的程序。

教學(xué)重點(diǎn)、難點(diǎn)：

1數(shù)據(jù)結(jié)構(gòu)、算法、算法復(fù)雜度的基本概念；

2如何把現(xiàn)實(shí)的問題抽象出來，建立模型，設(shè)計(jì)算法，再分析算法的復(fù)雜度，并

選取合適的語言編碼實(shí)現(xiàn)。

教學(xué)方法：

通過動(dòng)畫演示，提問，采用講授、啟發(fā)引導(dǎo)、學(xué)生自己動(dòng)手做相結(jié)合。

教學(xué)過程設(shè)計(jì)：

1、利用CC網(wǎng)，介紹課程的資源：老師搭建的hustoj在線評(píng)測網(wǎng)站、幾本教材的

PPT、Java軟件等供他們下載，自學(xué)，要求他們主動(dòng)學(xué)習(xí)，提供參考資料給他們；

2、介紹學(xué)習(xí)方法，課堂及作業(yè)要求、紀(jì)律要求、考核方式等；

3、了解學(xué)生：有多少人數(shù)準(zhǔn)備繼續(xù)深造（出國，考研等），多少人準(zhǔn)備從事軟件

開發(fā)，自己創(chuàng)業(yè)等；

4、介紹課程的作用，在專業(yè)課程中的地位，對(duì)個(gè)人提升的重要性等，特別強(qiáng)調(diào)所

有的相關(guān)計(jì)算機(jī)專業(yè)的考研以及高級(jí)程序員、系統(tǒng)分析師的考試、另外招聘程序

員的面試筆試等都會(huì)考相關(guān)的算法等；

5、介紹課程的主要內(nèi)容和學(xué)時(shí)分配；

6、鼓勵(lì)他們考取高級(jí)證書，提前到招聘會(huì)或者招聘網(wǎng)站上了解最新的崗位需求,

提前學(xué)些前沿的技術(shù)，為就業(yè)作準(zhǔn)備，介紹一些學(xué)生就業(yè)情況

7、通過最大公約數(shù)、一列數(shù)中第k大數(shù)等例子，介紹計(jì)算機(jī)算法可以解決的實(shí)際

問題，引出算法、算法評(píng)價(jià)指標(biāo)和算法復(fù)雜度等基本概念，并要同學(xué)舉例說明：

現(xiàn)實(shí)世界中的有哪些運(yùn)用計(jì)算機(jī)算法的地方？

課堂提問：

1、最小公倍數(shù)怎么計(jì)算？

2、n個(gè)數(shù)中第k大數(shù)，當(dāng)數(shù)字的個(gè)數(shù)n非常巨大，而k比較小時(shí)，采用什么樣的算法,

當(dāng)k的階和數(shù)字個(gè)數(shù)n相當(dāng)時(shí)，又該如何計(jì)算？

小結(jié)：

1）初步認(rèn)識(shí)算法基本概念和術(shù)語，一定要分清程序和算法是完全不同的兩個(gè)概

念；

2）了解課程章節(jié)的安排規(guī)律；

3）基本熟悉Java環(huán)境的使用，知道如何在Java中進(jìn)行算法編程。

作業(yè)：習(xí)題1（簡答「3,7,8）

預(yù)習(xí)：算法復(fù)雜度分析

復(fù)習(xí)：Java與算法相關(guān)的類庫和這些類的使用

教學(xué)單元：數(shù)據(jù)結(jié)構(gòu)A——線性表基礎(chǔ)(3學(xué)時(shí))

授課班級(jí)：

教學(xué)內(nèi)容提要：

2線性表的定義、分類和實(shí)現(xiàn)

2.1線性表的順序表示和實(shí)現(xiàn)

1)線性表的順序表示：指的是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)

元素。用物理位置來表示邏輯結(jié)構(gòu)。

LOC(ai+i)=LOC(ai)+/

LOC(ai)=LOC(ai)+(i-l)*/

2)順序表的特點(diǎn)：隨機(jī)存取

3)順序表的運(yùn)算

順序表容易實(shí)現(xiàn)訪問操作，可隨機(jī)存取元素。但是插入、刪除操作是需要移動(dòng)

大量的元素。

2.2線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)

2.2.1單鏈表：

1)單鏈表概念

2)單鏈表的存儲(chǔ)結(jié)構(gòu)定義

3)單鏈表的操作：

算法思想：單鏈表是非隨機(jī)存取結(jié)構(gòu)。每個(gè)元素的位置信息都包含在前驅(qū)結(jié)

點(diǎn)的信息中，所以取得第i個(gè)元素必須從頭指針出發(fā)尋找。設(shè)置一個(gè)指針變量指向

第一個(gè)結(jié)點(diǎn)，然后，讓該指針變量逐一向后指向，直到第i個(gè)元素。

插入操作：要在數(shù)據(jù)元素a和b之間插入元素x。

3.2.2掌握循環(huán)鏈表、雙鏈表及靜態(tài)鏈表存儲(chǔ)結(jié)構(gòu)及其運(yùn)算實(shí)現(xiàn)

教學(xué)目的：

1了解線性表和鏈表、單鏈表、雙向鏈表的定義；

2了解單鏈表的存儲(chǔ)和操作；

3掌握循環(huán)鏈表、雙鏈表及靜態(tài)鏈表存儲(chǔ)結(jié)構(gòu)及其運(yùn)算實(shí)現(xiàn)。

教學(xué)重點(diǎn)、難點(diǎn)：

1線性表的基本概念；

2單鏈表的實(shí)現(xiàn)，插入、刪除和查詢操作。

教學(xué)方法：

通過動(dòng)畫演示，提問，采用講授、啟發(fā)引導(dǎo)、學(xué)生自己動(dòng)手做相結(jié)合。

教學(xué)過程設(shè)計(jì)：

1、介紹線性表的基本概念；

2、介紹線性表的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

對(duì)比順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的內(nèi)存組織方式，讓學(xué)生了解要根據(jù)實(shí)際場景選擇

合適的存儲(chǔ)結(jié)構(gòu)；

介紹單鏈表、雙向鏈表的邏輯結(jié)構(gòu)，并畫出示意圖（黑板）；

3、提問單鏈表的插入、刪除和查詢操作如何實(shí)現(xiàn)；

4、讓學(xué)生完成一個(gè)簡單的鏈表插入節(jié)點(diǎn)和刪除節(jié)點(diǎn)的程序；

提示學(xué)生一定要注意要判斷引用不為空。否則引發(fā)空指針異常。

5、介紹雙向鏈表的節(jié)點(diǎn)定義以及插入、刪除和查詢操作

課堂提問：

1、能開整數(shù)數(shù)組大小最大多少？為什么可用內(nèi)存還有很多？

2、數(shù)組（順序存儲(chǔ)結(jié)構(gòu)）插入、刪除和查找節(jié)點(diǎn)的時(shí)間復(fù)雜度

3、單鏈表（鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)）插入、刪除和查找節(jié)點(diǎn)如何實(shí)現(xiàn)？這些操作的時(shí)間復(fù)

雜度是多少？

小結(jié)：

3）初步認(rèn)識(shí)線性表基本概念和術(shù)語，一定要分清線性表的線性存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)

是完全不同的邏輯結(jié)構(gòu)；

4）介紹多種鏈表的邏輯結(jié)構(gòu)；

3）教會(huì)如何實(shí)現(xiàn)單鏈表和雙向鏈表。

作業(yè)：預(yù)習(xí)：有序線性表

復(fù)習(xí)：常見數(shù)據(jù)結(jié)構(gòu)

教學(xué)單元：《數(shù)據(jù)結(jié)構(gòu)（本科）》有序線性表廣義（6學(xué)時(shí)）

授課班級(jí)：

教學(xué)內(nèi)容提要：

3.4有序線性表

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

4）有序線性表的順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)

相關(guān)概念：順序存儲(chǔ)、數(shù)組、二分查找

5）順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)：

二分查找查找非常高效

6）順序存儲(chǔ)結(jié)構(gòu)的缺點(diǎn)：

增加和刪除操作，需要移動(dòng)大量元素，效率低。

3.4.2有序線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)：

4）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)定義（鏈表節(jié)點(diǎn)）

5）有序鏈表的操作：

算法思想：單鏈表是非隨機(jī)存取結(jié)構(gòu)，所以從頭節(jié)點(diǎn)出發(fā)尋找合適的位置插

入節(jié)點(diǎn)。找到第一個(gè)比待插入節(jié)點(diǎn)值大的節(jié)點(diǎn)（假設(shè)為節(jié)點(diǎn)N）,待插入節(jié)點(diǎn)就放

在節(jié)點(diǎn)N前面即可。

6）有序鏈表的作業(yè)1——多項(xiàng)式相加

7）有序鏈表的作業(yè)2——多項(xiàng)式相乘

3.5廣義表

3.5.1廣義表的定義

3.5.2廣義表的創(chuàng)建的遞歸算法

教學(xué)目的：

1了解有序線性表的定義和分類；

2掌握有序數(shù)組的存儲(chǔ)和二分查找操作；

3掌握有序鏈表的存儲(chǔ)結(jié)構(gòu)及其操作實(shí)現(xiàn)：插入、更新和刪除；

4掌握廣義表的存儲(chǔ)結(jié)構(gòu)及其操作實(shí)現(xiàn)：插入、更新和刪除；

教學(xué)重點(diǎn)、難點(diǎn)：

1有序數(shù)組的二分查找；

2有序鏈表的實(shí)現(xiàn)，插入、刪除和查詢操作；

3廣義表創(chuàng)建的遞歸算法

教學(xué)方法：

通過動(dòng)畫演示，提問，采用講授、啟發(fā)引導(dǎo)、學(xué)生自己動(dòng)手做相結(jié)合。

教學(xué)過程設(shè)計(jì)：

1、介紹有序線性表的基本概念；

2、介紹順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的邏輯結(jié)構(gòu)，并畫出示意圖（黑板）；

3、復(fù)習(xí)書上沒有的有序鏈表的插入、刪除和更新操作；

4、提問如何保證插入節(jié)點(diǎn)后鏈表還是有序的；

5、用課件中微軟面試題，拓展學(xué)生視野，并引發(fā)學(xué)生的討論；

微軟面試題：一共三道，難度為遞進(jìn)關(guān)系。而且環(huán)環(huán)相扣，對(duì)學(xué)生掌握鏈表的

設(shè)計(jì)和操作，有很大幫助

課堂提問：

提問1：為什么是第一個(gè)比待插入節(jié)點(diǎn)值大的節(jié)點(diǎn)

提問2：如果節(jié)點(diǎn)N為鏈表第一個(gè)節(jié)點(diǎn)，還要注意什么？

提問3：節(jié)點(diǎn)N是否會(huì)找不到，找不到怎么辦？

提問4：廣義表的創(chuàng)建為什么使用遞歸算法？可不可以不用？

小結(jié)：

5）介紹有序線性表基本概念和術(shù)語，一定要分清線性表的線性存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)

是完全不同的邏輯結(jié)構(gòu)；

6）介紹有序線性表的操作，并分析相關(guān)的復(fù)雜度；

7）教會(huì)如何實(shí)現(xiàn)二分查找和有序鏈表；

8）廣義表的創(chuàng)建和基本操作

作業(yè)：

預(yù)習(xí)：棧

復(fù)習(xí)：線性表的插入節(jié)點(diǎn)（代碼）

教學(xué)單元：《數(shù)據(jù)結(jié)構(gòu)A》棧和隊(duì)列（棧4學(xué)時(shí)）

授課班級(jí)：

教學(xué)內(nèi)容提要：

1.什么是堆棧？

2.堆棧的存儲(chǔ)方式

3.堆棧的操作

4.堆棧的應(yīng)用

5.實(shí)踐項(xiàng)目：進(jìn)制的轉(zhuǎn)換、括號(hào)匹配、后綴表達(dá)式的計(jì)算

教學(xué)目的：

1理解堆棧的工作原理

2掌握堆棧的設(shè)計(jì)與實(shí)現(xiàn)

3會(huì)使用堆棧進(jìn)行編程

教學(xué)重點(diǎn)、難點(diǎn)：

1堆棧的工作原理

2使用堆棧進(jìn)行編程

3中綴表達(dá)式變后綴表達(dá)式以及后綴表達(dá)式的計(jì)算

教學(xué)方法：

通過動(dòng)畫演示，提問，采用講授、啟發(fā)引導(dǎo)、學(xué)生自己動(dòng)手做相結(jié)合。

教學(xué)過程設(shè)計(jì)：

1、介紹棧的基本概念；

2、介紹棧的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)，并畫出示意圖(黑板)；

3、利用提問棧的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)，棧頂位于哪一端，讓學(xué)生掌握自己創(chuàng)建棧;

4、介紹括號(hào)匹配問題，并給出用棧的解決方法；

5、講解棧和遞歸的關(guān)系，并讓學(xué)生測試機(jī)房的機(jī)器遞歸最大深度；

6、講解作業(yè)題“迷宮”，突出里面的遞歸思想；

7、講解練習(xí)題“全排列”和“組合”，進(jìn)一步消化遞歸思想；

課堂提問：

提問1：棧的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)，棧頂位于哪一端？

提問2：機(jī)房的機(jī)器，遞歸最大深度是多少，怎能知道？

提問3：迷宮問題，走回頭路怎么辦？

提問4：全排列問題的分解，是否能理解？

提問5：組合問題的分解，是否能理解？

小結(jié)：

9)介紹?；靖拍詈托g(shù)語，一定要分清棧的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)是完全不同的

邏輯結(jié)構(gòu)；

10)介紹棧的操作，并分析相關(guān)的復(fù)雜度；

11)教會(huì)如何用棧解決括號(hào)匹配問題；

12)理解棧和遞歸的關(guān)系；

13)掌握常見遞歸問題的解法

作業(yè)：

預(yù)習(xí)：棧

復(fù)習(xí)：有序鏈表

教學(xué)單元：《數(shù)據(jù)結(jié)構(gòu)》樹和二叉樹（6學(xué)時(shí)）

授課班級(jí)：

教學(xué)內(nèi)容提要：

5樹

5.1樹的定義和基本術(shù)語

結(jié)點(diǎn)的度、樹的度、兒子結(jié)點(diǎn)、父親結(jié)點(diǎn)、兄弟結(jié)點(diǎn)

5.2樹的表示形式

5.3樹形結(jié)構(gòu)的邏輯結(jié)構(gòu)

樹形結(jié)構(gòu)的邏輯特征可用樹中結(jié)點(diǎn)之間的父子關(guān)系來描述

樹形結(jié)構(gòu)是非線性結(jié)構(gòu)

5.4二叉樹

5.4.1二叉樹的定義

二叉樹的五種基本形態(tài)：

5.4.2二叉樹的重要性質(zhì)

性質(zhì)1、在二叉樹中的第i層上最多有的結(jié)點(diǎn)數(shù)為2i-l個(gè)結(jié)點(diǎn)。（i2l）

性質(zhì)2、深度為k的二叉樹至多有2k-l個(gè)結(jié)點(diǎn)（i'l）

性質(zhì)3、在任意二叉樹中，若葉子結(jié)點(diǎn)（即度為零的結(jié)點(diǎn)）的個(gè)數(shù)為nO,度

為1的結(jié)點(diǎn)個(gè)數(shù)為nl，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2,則有nO=n2+l

性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹樹深為log2n+1

性質(zhì)5、對(duì)于完全二叉樹，對(duì)其結(jié)點(diǎn)采用“按層編號(hào)”比較方便，即從根結(jié)

點(diǎn)開始由上而下逐層給結(jié)點(diǎn)編號(hào)，同一層的結(jié)點(diǎn)由左向右編號(hào)。

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

順序存儲(chǔ)、二叉鏈表存儲(chǔ)和三叉鏈表存儲(chǔ)

5.4.4二叉樹的遍歷

1）遍歷二叉樹

三種遍歷次序以遞歸的形式定義：

中序（Inorder）遍歷

先序（Preorder）遍歷

后序（Proorder）遍歷

2）遍歷算法的實(shí)現(xiàn)

3）遍歷算法的應(yīng)用

4）二叉樹的層次遍歷

層次遍歷的定義、層次遍歷的算法實(shí)現(xiàn)和層次遍歷的應(yīng)用

教學(xué)目的：

1了解樹和二叉樹的定義；

2了解二叉樹的性質(zhì)和存儲(chǔ)結(jié)構(gòu)；

3掌握二叉樹的幾種遍歷；

4掌握利用前序和中序遍歷構(gòu)建二叉樹的遞歸算法

教學(xué)重點(diǎn)、難點(diǎn)：

1二叉樹二叉鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)

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

3利用前序和中序遍歷構(gòu)建二叉樹

教學(xué)方法：

通過動(dòng)畫演示，提問，采用講授、啟發(fā)引導(dǎo)、學(xué)生自己動(dòng)手做相結(jié)合。

教學(xué)過程設(shè)計(jì)：

1、介紹樹和二叉樹的基本概念；

2、介紹樹和二叉樹的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的實(shí)現(xiàn)，并畫出示意圖（黑板）；

3、講解完全二叉樹的存儲(chǔ)原理和實(shí)現(xiàn)細(xì)節(jié)（為后面堆的知識(shí)做鋪墊）；

4、介紹二叉樹常用的三種遍歷

討論二叉樹的遍歷能否確定一棵二叉樹？

舉出前序和后序遍歷不能確定二叉樹的反例

給出利用前序和中序遍歷構(gòu)建二叉樹的遞歸算法，作業(yè)題9

5、講解二叉樹的層次遍歷；

討論二叉樹的層次遍歷，要怎么存儲(chǔ)層次和父子信息

課堂提問：

提問1:如何判定完全二叉樹？

提問2：能不能給出前序和后序遍歷不能確定二叉樹的反例？

提問3：老師給出的利用前序和中序遍歷構(gòu)建二叉樹的算法，為什么要用遞

歸？使用遞歸有什么優(yōu)點(diǎn)？

小結(jié)：

14)介紹二叉樹基本概念和術(shù)語；

15)介紹二叉樹常用的三種遍歷和層次遍歷;

3)掌握利用前序和中序遍歷構(gòu)建二叉樹的算法。

作業(yè)：

預(yù)習(xí)：常用二叉樹

復(fù)習(xí)：隊(duì)列

教學(xué)單元：《數(shù)據(jù)結(jié)構(gòu)》哈夫曼樹（2時(shí)）

授課班級(jí)：

教學(xué)內(nèi)容提要：

5哈夫曼樹

5.1哈夫曼樹構(gòu)造方法

5.1.1最優(yōu)二叉樹概念

1.路徑和路徑長度

2.結(jié)點(diǎn)的權(quán)和帶權(quán)路徑長度

3.樹的帶權(quán)路徑長度

WPL=^Wix\i

i=l

哈夫曼樹構(gòu)造的步驟如下：

（1）用給定的n個(gè)權(quán)值{wl,w2,…，wn}對(duì)應(yīng)的n個(gè)結(jié)點(diǎn)構(gòu)成n棵二叉樹的森

林F={T1,T2,…，Tn},其中每一棵二叉樹Ti（1WiWn）都只有一個(gè)權(quán)值為wi的

根結(jié)點(diǎn)，其左、右子樹為空。

（2）在森林F中選擇兩棵根結(jié)點(diǎn)權(quán)值最小的二叉樹，作為一棵新二叉樹的左、

右子樹，標(biāo)記新二叉樹的根結(jié)點(diǎn)權(quán)值為其左右子樹的根結(jié)點(diǎn)權(quán)值之和。（3）

從F中刪除被選中的那兩棵二叉樹，同時(shí)把新構(gòu)成的二叉樹加入到森林F中。

（4）重復(fù)（2）、（3）操作，直到森林中只含有一棵二叉樹為止，此時(shí)得

到的這棵二叉樹就是赫夫曼樹。

5.2哈夫曼編碼

前綴編碼：任一個(gè)字符的編碼都不是另一個(gè)字符編碼的前綴，可利用二叉樹

設(shè)計(jì)前綴編碼。

5.3哈夫曼編碼的編碼方法

二叉樹指向左孩子的邊編碼為1,指向右孩子的邊編碼為0。每個(gè)葉子節(jié)點(diǎn)代

表字符（單詞）的編碼，為從根節(jié)點(diǎn)到該節(jié)點(diǎn)所經(jīng)邊的編碼串。

教學(xué)目的:

1了解哈夫曼樹和哈夫曼編碼的定義；

2了解哈夫曼樹的性質(zhì)和構(gòu)造方法；

3掌握哈夫曼樹的編碼方法；

教學(xué)重點(diǎn)、難點(diǎn)：

1哈夫曼樹存儲(chǔ)實(shí)現(xiàn)

2哈夫曼樹構(gòu)造方法的編碼實(shí)現(xiàn)

3哈夫曼樹編碼的編碼實(shí)現(xiàn)

教學(xué)方法：

通過動(dòng)畫演示，提問，采用講授、啟發(fā)引導(dǎo)、學(xué)生自己動(dòng)手做相結(jié)合。

教學(xué)過程設(shè)計(jì)：

1、介紹哈夫曼樹和哈夫曼編碼的基本概念；

2、介紹哈夫曼樹構(gòu)造方法，并畫出示意圖(黑板)；

3、講解哈夫曼樹構(gòu)造方法的代碼實(shí)現(xiàn)(為后面哈夫曼編碼做鋪墊)；

4、講解哈夫曼編碼的代碼實(shí)現(xiàn)；

討論：采用鏈?zhǔn)酱鎯?chǔ)好還是順序存儲(chǔ)好？

課堂提問:

有一電文共使用五種字符a,b,c,d,e,其出現(xiàn)頻率依次為4,7,5,2,9。

(1)試畫出對(duì)應(yīng)的編碼赫夫曼樹(要求左子樹根結(jié)點(diǎn)的權(quán)小于等于右子樹根結(jié)

點(diǎn)的權(quán))。

(2)求出每個(gè)字符的赫夫曼編碼。

小結(jié)：

16)介紹哈夫曼樹和哈夫曼編碼的基本概念；

17)掌握哈夫曼樹構(gòu)造方法和哈夫曼編碼方法

作業(yè)：

預(yù)習(xí)：堆

復(fù)習(xí)：二叉樹

教學(xué)單元：《數(shù)據(jù)結(jié)構(gòu)》堆和堆排序（4時(shí)）

授課班級(jí)：

教學(xué)內(nèi)容提要：

5哈夫曼樹

5.1哈夫曼樹構(gòu)造方法

5.1.1最優(yōu)二叉樹概念

1.路徑和路徑長度

2.結(jié)點(diǎn)的權(quán)和帶權(quán)路徑長度

3.樹的帶權(quán)路徑長度

WPL=^Wix\i

i=l

哈夫曼樹構(gòu)造的步驟如下：

（1）用給定的n個(gè)權(quán)值{wl,w2,…，wn}對(duì)應(yīng)的n個(gè)結(jié)點(diǎn)構(gòu)成n棵二叉樹的森

林F={T1,T2,…，Tn},其中每一棵二叉樹Ti（1WiWn）都只有一個(gè)權(quán)值為wi的

根結(jié)點(diǎn)，其左、右子樹為空。

（2）在森林F中選擇兩棵根結(jié)點(diǎn)權(quán)值最小的二叉樹，作為一棵新二叉樹的左、

右子樹，標(biāo)記新二叉樹的根結(jié)點(diǎn)權(quán)值為其左右子樹的根結(jié)點(diǎn)權(quán)值之和。（3）

從F中刪除被選中的那兩棵二叉樹，同時(shí)把新構(gòu)成的二叉樹加入到森林F中。

（4）重復(fù)（2）、（3）操作，直到森林中只含有一棵二叉樹為止，此時(shí)得

到的這棵二叉樹就是赫夫曼樹。

5.2哈夫曼編碼

前綴編碼：任一個(gè)字符的編碼都不是另一個(gè)字符編碼的前綴，可利用二叉樹

設(shè)計(jì)前綴編碼。

5.3哈夫曼編碼的編碼方法

二叉樹指向左孩子的邊編碼為1,指向右孩子的邊編碼為0。每個(gè)葉子節(jié)點(diǎn)代

表字符（單詞）的編碼，為從根節(jié)點(diǎn)到該節(jié)點(diǎn)所經(jīng)邊的編碼串。

教學(xué)目的:

1了解哈夫曼樹和哈夫曼編碼的定義；

2了解哈夫曼樹的性質(zhì)和構(gòu)造方法；

3掌握哈夫曼樹的編碼方法；

教學(xué)重點(diǎn)、難點(diǎn)：

1哈夫曼樹存儲(chǔ)實(shí)現(xiàn)

2哈夫曼樹構(gòu)造方法的編碼實(shí)現(xiàn)

3哈夫曼樹編碼的編碼實(shí)現(xiàn)

教學(xué)方法：

通過動(dòng)畫演示，提問，采用講授、啟發(fā)引導(dǎo)、學(xué)生自己動(dòng)手做相結(jié)合。

教學(xué)過程設(shè)計(jì)：

1、介紹哈夫曼樹和哈夫曼編碼的基本概念；

2、介紹哈夫曼樹構(gòu)造方法，并畫出示意圖(黑板)；

3、講解哈夫曼樹構(gòu)造方法的代碼實(shí)現(xiàn)(為后面哈夫曼編碼做鋪墊)；

4、講解哈夫曼編碼的代碼實(shí)現(xiàn)；

討論：采用鏈?zhǔn)酱鎯?chǔ)好還是順序存儲(chǔ)好？

課堂提問:

有一電文共使用五種字符a,b,c,d,e,其出現(xiàn)頻率依次為4,7,5,2,9。

(1)試畫出對(duì)應(yīng)的編碼赫夫曼樹(要求左子樹根結(jié)點(diǎn)的權(quán)小于等于右子樹根結(jié)

點(diǎn)的權(quán))。

(2)求出每個(gè)字符的赫夫曼編碼。

小結(jié)：

18)介紹哈夫曼樹和哈夫曼編碼的基本概念；

19)掌握哈夫曼樹構(gòu)造方法和哈夫曼編碼方法

作業(yè)：

預(yù)習(xí)：堆

復(fù)習(xí)：二叉樹

教學(xué)單元：《數(shù)據(jù)結(jié)構(gòu)》圖的基本概念和存儲(chǔ)(2學(xué)時(shí))

授課班級(jí)：

教學(xué)內(nèi)容提要：

1.圖的概念

首先介紹“七橋問題”，說明數(shù)學(xué)模型的重要性

圖的概念：有向圖、無向圖、完全圖、度、出度、入度、鄰接、鄰接點(diǎn)、連通分

量、強(qiáng)連通分量、生成樹、第一鄰接點(diǎn)、下一鄰接點(diǎn)

抽象數(shù)據(jù)類型定義

圖的操作中最重要的4個(gè)操作：

GraphLocateVertex(G,v)；

GraphGetVertex(G,v)；

GraphFirstAdj(G,v)；

GraphNextAdj(G,v,w)；

2.圖的順序存儲(chǔ)結(jié)構(gòu)一一鄰接矩陣表示法

圖的鄰接矩陣表示法的特點(diǎn)：對(duì)于無向圖，鄰接矩陣一定是一個(gè)對(duì)稱矩陣

行(列)非零元素個(gè)數(shù)，表示度。對(duì)于有向圖，矩陣不一定是一個(gè)對(duì)稱矩陣

行非零元素個(gè)數(shù)，表示出度列非零元素個(gè)數(shù)，表示入度鄰接矩陣的存儲(chǔ)空間只和

頂點(diǎn)個(gè)數(shù)有關(guān)，和邊數(shù)無關(guān)。

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

圖的鄰接矩陣表示法(AdjacencyMatrix)也稱作數(shù)組表示法。它采用兩個(gè)

數(shù)組來表示圖：一個(gè)是用于存儲(chǔ)頂點(diǎn)信息的一維數(shù)組；另一個(gè)是用于存儲(chǔ)圖中頂

點(diǎn)之間關(guān)聯(lián)關(guān)系的二維數(shù)組，這個(gè)關(guān)聯(lián)關(guān)系數(shù)組被稱為鄰接矩陣。

4.圖的存儲(chǔ)結(jié)構(gòu)間的相互轉(zhuǎn)換（鄰接矩陣轉(zhuǎn)為鄰接表的算法、鄰接表轉(zhuǎn)為鄰接矩

陣的算法）

教學(xué)目的：

1.掌握?qǐng)D的基本概念

2.掌握?qǐng)D的存儲(chǔ)結(jié)構(gòu)，重點(diǎn)是鄰接矩陣和鄰接表

3.掌握?qǐng)D的算法，特別是圖的生成算法

4.掌握鄰接矩陣和鄰接表存儲(chǔ)結(jié)構(gòu)間的相互轉(zhuǎn)換

教學(xué)重點(diǎn)、難點(diǎn)：

1.重點(diǎn)是圖的基本概念，存儲(chǔ)結(jié)構(gòu)

2.難點(diǎn)是圖的存儲(chǔ)結(jié)構(gòu)間相互轉(zhuǎn)換的算法

教學(xué)方法：

通過動(dòng)畫演示，提問，采用講授、啟發(fā)引導(dǎo)、學(xué)生自己動(dòng)手做相結(jié)合。

教學(xué)過程設(shè)計(jì)：

1、介紹圖的基本概念；

2、介紹圖的兩種存儲(chǔ)方法，并畫出示意圖（黑板）；

3、講解圖的基本操作；

4、講解兩種存儲(chǔ)方法的轉(zhuǎn)換

課堂提問:

1、一個(gè)n個(gè)頂點(diǎn)的連通無向圖，其邊的個(gè)數(shù)至少為多少？

2、n個(gè)頂點(diǎn)的無向圖的鄰接矩陣至少有多少非零元素？

3、n個(gè)頂點(diǎn)的完全有向圖含有弧的數(shù)目是多少？

4、要連通具有n個(gè)頂點(diǎn)的有向圖，至少需要多少條??？

小結(jié)：

20）介紹圖的基本概念和存儲(chǔ)；

21）掌握兩種存儲(chǔ)方法的轉(zhuǎn)換方法

作業(yè)：課本課后練習(xí)題

預(yù)習(xí)：圖的連通性

教學(xué)單元：《數(shù)據(jù)結(jié)構(gòu)》圖的遍歷、連通性和最小生成樹

（10時(shí)）

授課班級(jí)：

教學(xué)內(nèi)容提要：

1.圖的遍歷

圖的遍歷（TravellingGraph）:從圖中某一個(gè)頂點(diǎn)出發(fā)，訪問圖中的其余頂

點(diǎn)，使每個(gè)頂點(diǎn)被訪問一次且僅被訪問一次。

方法：

深度優(yōu)先遍歷

廣度優(yōu)先遍歷

（1）深度優(yōu)先遍歷

1）從任一個(gè)頂點(diǎn)v出發(fā)，訪問該頂點(diǎn)；

2）然后依次從v的未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和

v有路徑相通的頂點(diǎn)都被訪問到；

3）此時(shí)若圖中尚有頂點(diǎn)未被訪問，則另選中下一個(gè)未被訪問的頂點(diǎn)作起始

點(diǎn)，訪問該頂點(diǎn)，繼續(xù)過程2）,直到所有頂點(diǎn)都被訪問完。

（2）廣度優(yōu)先遍歷

1）從圖中某頂點(diǎn)v出發(fā)，訪問v,之后：

2）依次訪問v的各個(gè)未曾被訪問過的鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)依

次訪問它們的未被訪問的鄰接點(diǎn)，并使“先被訪問的頂點(diǎn)的鄰接點(diǎn)'先于'

后被訪問的頂點(diǎn)的鄰接點(diǎn)”被訪問，直至圖中所有已經(jīng)被訪問的頂點(diǎn)的鄰接

點(diǎn)都被訪問到；

3）若圖中尚有頂點(diǎn)未曾被訪問，則另選圖中一個(gè)未曾被訪問的頂點(diǎn)作起點(diǎn),

訪問該頂點(diǎn)，繼續(xù)過程2）,直至所有頂點(diǎn)被訪問完畢。

2.圖的連通分量

進(jìn)入DFS或BFS一次可以求得一個(gè)連通分量

3.深度優(yōu)先生成樹和廣度優(yōu)先生成樹

采用DFS遍歷圖所得到的生成樹稱為深度優(yōu)先生成樹，采用BFS遍歷圖所得到

的生成樹稱為廣度優(yōu)先生成樹

4.最小生成樹

n個(gè)頂點(diǎn)網(wǎng)絡(luò)的生成樹有n個(gè)結(jié)點(diǎn)，nT條分枝。假設(shè)網(wǎng)絡(luò)中有m條邊(m2n-l),

用MST表示許多可能的生成樹的集合，每棵樹中n-1條分枝上的權(quán)之和用WG⑴表

示，則使得

WG(Tmin)=Min{WG(T)|TGMST}

的生成樹Tmin便是網(wǎng)絡(luò)的最小生成樹。

MST性質(zhì)

假設(shè)N=(V,{E})是一個(gè)連通無向網(wǎng)，U是頂點(diǎn)集V的一個(gè)非空子集。若(u,v)

是一條具有最小權(quán)值的邊，其中uGU,veV-U,則必存在一棵包含邊(u,v)的

最小生成樹。

5.Prim算法

算法思想：假設(shè)N=(V,|E|)是連通圖，TE是N上最小生成樹中邊的集合。算

法從U={uO}(uOeV),TE={}開始，重復(fù)執(zhí)行下述操作：在所有ueU,veV—U的邊

(u,v)中找一條代價(jià)最小的邊(uO,vO)并入集合TE,同時(shí)vO并入U(xiǎn),直至U=V為止。

此時(shí)，TE中必有nT條邊，則T=(V,{TE})為N的最小生成樹。

教學(xué)目的：

1.掌握?qǐng)D的遍歷算法：深度優(yōu)先遍歷，寬度優(yōu)先遍歷。

2.了解圖的連通性，掌握連通分量的求法

3.掌握生成樹的構(gòu)造方法

4.理解構(gòu)造生成樹的算法

教學(xué)重點(diǎn)、難點(diǎn)：

1.重點(diǎn)：圖的遍歷算法和生成樹

2.難點(diǎn)：圖的遍歷算法的應(yīng)用

教學(xué)方法：

通過動(dòng)畫演示，提問，采用講授、啟發(fā)引導(dǎo)、學(xué)生自己動(dòng)手做相結(jié)合。

教學(xué)過程設(shè)計(jì)：

1、介紹圖的遍歷、連通性和最小生成樹的基本概念；

2、介紹圖的兩種遍歷方法，并畫出示意圖（黑板）；

3、講解求圖的連通性和最小生成樹方法（黑板）；

4、求圖的遍歷、連通性和最小生成樹的代碼實(shí)現(xiàn)；

課堂提問：

圖的BFS生成樹的樹高要小于等于同圖DFS生成樹的樹高，對(duì)嗎？

如果圖有多個(gè)連通分量，深度優(yōu)先遍歷如何找出？

Prim算法的時(shí)間復(fù)雜度是多少？

小結(jié):

22)介紹圖的遍歷、連通性和最小生成樹;

23)掌握?qǐng)D的兩種遍歷方法；

24)掌握求圖的連通性和最小生成樹方法

作業(yè)：課本課后練習(xí)題

一帶權(quán)無向圖的鄰接矩陣如下圖，試畫出它的一棵最小生成樹。

011000

101200

110030

020011

003101

000110

如圖所示是一帶權(quán)有向圖的鄰接表法存儲(chǔ)表示。其中出邊表中的每個(gè)結(jié)點(diǎn)均含有

三個(gè)字段，依次為邊的另一個(gè)頂點(diǎn)在頂點(diǎn)表中的序號(hào)、邊上的權(quán)值和指向下一個(gè)

邊結(jié)點(diǎn)的指針。試求：

（1）該帶權(quán)有向圖的圖形；

（2）從頂點(diǎn)VI為起點(diǎn)的廣度優(yōu)先遍歷的頂點(diǎn)序列及對(duì)應(yīng)的生成樹；

（3）以頂點(diǎn)VI為起點(diǎn)的深度優(yōu)先遍歷生成樹;

預(yù)習(xí)：堆

復(fù)習(xí)：二叉樹

教學(xué)單元：《數(shù)據(jù)結(jié)構(gòu)》圖的最短路徑(6時(shí))

授課班級(jí)：

教學(xué)內(nèi)容提要：

1.從某源點(diǎn)到其它各頂點(diǎn)的最短路徑。

(1)Dijkstra算法

按路徑長度遞增的次序來產(chǎn)生最短路徑算法

(2)方法：把V分成兩組

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

V-S：尚未確定最短路徑的頂點(diǎn)集合,將V-S中頂點(diǎn)按最短路徑遞增的次序加入到S

(3)步驟：

(1)鄰接矩陣arcs來表示帶權(quán)的有向圖，arcs[i][J]表示〈vi,vj＞上的權(quán)值。若＜vi,

vj＞eE,則置arcs[i][j]=8。S為已找到從v出發(fā)的最短路徑的終點(diǎn)集合，初態(tài)為空。

(2)選擇vj,使D[j]=min{D[i]|viGV-S}vj就是當(dāng)前求得的一條從v出發(fā)的最短

路徑，并令S-SU{j}

(3)從v出發(fā)到集合V-S上任一頂點(diǎn)vk可達(dá)的最短路徑，有

D[k]=min{D[k],D[j]+arcs[i][k]}

(4)重復(fù)(2)、(3)直到S=V。

2.每一對(duì)頂點(diǎn)之間的最短路徑

方法一：每次以一個(gè)頂點(diǎn)為源點(diǎn)，重復(fù)執(zhí)行Dijkstra算法n次一T(n)=O(n3)

方法二：弗洛伊德(Floyd)算法

(1)Floyd算法思想

逐個(gè)頂點(diǎn)試探法

求最短路徑步驟

初始時(shí)設(shè)置一個(gè)n階方陣，令其對(duì)角線元素為0,若存在弧則對(duì)應(yīng)元

素為權(quán)值；否則為8

逐步試著在原直接路徑中增加中間頂點(diǎn)，若加入中間點(diǎn)后路徑變短，則修改之;

否則，維持原值

所有頂點(diǎn)試探完畢，算法結(jié)束

(2)Floyd算法

voidShortestPath_Floyed(GraphG,PathMatrixP[],DistanceMatrixD)

{〃用Floyed算法求有向圖G中各對(duì)頂點(diǎn)v和w之間最短路徑P[v][w],及其帶權(quán)路

//徑長度D[v][w]。若P[v][w][u]為真，則u是從v到當(dāng)前求得最短路徑上的頂點(diǎn)

for(v=0；v<G.vexnum；v++)

for(w=0；w<G.vexnum；w++)

{D[v][w]=G.arcs[v][w]；

for(u=0；u<G.vexnum；u++)p[v][w][u]=0；

if(D[v][w]<INTMAX)//從v到w有直接通路

{P[v][w][v]=1；P[v][w][w]=l；

}//if

}//for

for(u=0；u<G.vexnum；u++)

for(v=0；v<G.vexnum；v++)

for(w=0；w<G.vexnum；w++)

if(D[v][u]+D[u][w]<D[v][w])//從v經(jīng)u到w一條路徑更短

{D[v][w]=D[v][u]+D[u][w]；

for(i=0；i<G.vexnum：i++)

P[v][w][i]=P[v][u][i]||P[u][w][i]；

}//if

}//ShortestPath_Floyed

(3)舉例

教學(xué)目的：

1.掌握單源點(diǎn)到其它各頂點(diǎn)的最短路徑。

2.掌握任意兩頂點(diǎn)間的最短路徑。

教學(xué)重點(diǎn)、難點(diǎn)：

1.重點(diǎn)是單源點(diǎn)和任意兩頂點(diǎn)間的最短路徑

2.難點(diǎn)是算法的理解和應(yīng)用

教學(xué)方法：

通過動(dòng)畫演示，提問，采用講授、啟發(fā)引導(dǎo)、學(xué)生自己動(dòng)手做相結(jié)合。

教學(xué)過程設(shè)計(jì)：

1、介紹單源最短路徑和多點(diǎn)間最短路徑的基本概念;

2、介紹Dijkstra方法，并畫出示意圖（黑板）；

3、講解Dijkstra方法的代碼實(shí)現(xiàn)；

4、介紹Floyd方法，并畫出示意圖（黑板）；

5、講解Floyd方法的代碼實(shí)現(xiàn)；

課堂提問：

比較Dijkstra方法和Prim算法的異同。

Dijkstra方法中尋找最小的D[v][w]有什么好算法？

小結(jié)：

25）介紹單源最短路徑和多點(diǎn)間最短路徑的基本概念；

26）掌握求解單源最短路徑和多點(diǎn)間最短路徑的基本概念方法