數(shù)據(jù)結(jié)構(gòu)（Python版）教學(xué)大綱 及 教案

數(shù)據(jù)結(jié)構(gòu)課程教學(xué)大綱

課程代碼：

課程名稱：數(shù)據(jù)結(jié)構(gòu)

開課學(xué)期：2

學(xué)分/學(xué)時：4/48+32

課程類型：必修

適用專業(yè)/開課對象：就計算機相關(guān)/大一、大二

先修課程：計算機導(dǎo)論、程序設(shè)計語言（Python）

開課單位：

團隊負責人：責任教授：

執(zhí)筆人：核準院長：

一、課程的性質(zhì)、目的與任務(wù)

隨著近年來計算概念的快速發(fā)展，計算學(xué)科已經(jīng)發(fā)展成為一個內(nèi)涵繁雜的綜合性學(xué)科,

至少可以劃分為計算機工程（CE）、計算機科學(xué)（CS）、信息系統(tǒng)（IS）、信息技術(shù)（IT）

和軟件工程（SE）等五個領(lǐng)域，而且不同領(lǐng)域的人才所應(yīng)具備的知識結(jié)構(gòu)與能力側(cè)重也不

盡相同。盡管如此，從目前已經(jīng)完成的部分來看，數(shù)據(jù)結(jié)構(gòu)在各領(lǐng)域的知識體系中仍然占據(jù)

著重要的位置。數(shù)據(jù)結(jié)構(gòu)是普通高等院校計算機和信息管理等專業(yè)的一門必修課程，主要討

論數(shù)據(jù)的邏輯結(jié)構(gòu)，在計算機中的存儲結(jié)構(gòu)以及對其進行的各種處理運算的方法和算法。

二、教學(xué)內(nèi)容及教學(xué)基本要求

1.緒論（2學(xué)時）

了解數(shù)據(jù)結(jié)構(gòu)的基本概念，掌握算法的描述和算法時間復(fù)雜度、空間復(fù)雜度等內(nèi)容。

2.線性表（7學(xué)時）

了解線性表的基本概念和抽象數(shù)據(jù)類型定義,掌握線性表順序和鏈式兩種存儲方式的表

示，基本操作的實現(xiàn)和相應(yīng)的應(yīng)用。

3.棧和隊列（6學(xué)時）

掌握棧和隊列的基本概念和抽象數(shù)據(jù)類型定義，棧和隊列在順序存儲和鏈式存儲結(jié)構(gòu)下

的基本操作和應(yīng)用。

4.串和數(shù)組（5學(xué)時）

了解串的基本概念和數(shù)據(jù)類型定義，串的存儲結(jié)構(gòu)，基本操作實現(xiàn)和應(yīng)用等內(nèi)容；掌握

數(shù)組的概念。

5.樹形結(jié)構(gòu)（7學(xué)時）

掌握樹和二叉樹的基本概念，二叉樹的性質(zhì)和存儲結(jié)構(gòu)，遍歷方法、實現(xiàn)及應(yīng)用，哈夫

曼樹的概念和構(gòu)造方法.

6.圖（7學(xué)時）

了解圖的基本概念、抽象數(shù)據(jù)類型定義、存儲結(jié)構(gòu)和遍歷方法，掌握最小生成樹的基本

概念和算法、最短路徑相關(guān)算法、拓撲排序的概念和實現(xiàn)方法。

7.排序（7學(xué)時）

掌握排序的基本概念，插入排序、交換排序、選擇排序、歸并排序等多種排序的原理、

實現(xiàn)方法及性能分析。

8.查找（7學(xué)時）

掌握查找的基本概念，順序查找、二分查找等查找的原理、實現(xiàn)方法和性能分析，平衡

二叉樹、哈希表的概念、結(jié)構(gòu)定義和實現(xiàn)方法。

三、教學(xué)方法

本課程教學(xué)方法以教師為主導(dǎo)的啟發(fā)式講授教學(xué)法為主，討論（提問）式教學(xué)為輔，結(jié)

合課外學(xué)習的教學(xué)方法。

1.本課程概念較多，因此教學(xué)形式以講授方式為主。本課程擬采用多媒體PPT的教學(xué)方法，

增加課堂信息，淺顯通俗地對概念、定義和原理進行解釋，增加教學(xué)的直觀性，教學(xué)過程中

注意各個知識點的關(guān)聯(lián)性，以使學(xué)生更好地理解課程內(nèi)容。

2.對課程中關(guān)鍵性概念、設(shè)計思想方面的問題可輔以課堂討論的形式。

3.為加強和落實動手能力的培養(yǎng)，每章課后應(yīng)安排作業(yè)，幫助學(xué)生學(xué)習和應(yīng)用。

四、課內(nèi)外教學(xué)環(huán)節(jié)及基本要求

本課程共48+32個學(xué)時，理論48個學(xué)時，講授16周（每周3學(xué)時）；實驗32個學(xué)時。

課外學(xué)習要求：

1.做好課前預(yù)習，預(yù)習時以教材為主，了解相關(guān)的概念、定義、原理。預(yù)習中認真思考，

以便帶著問題主動地聽課。

2.課后要復(fù)習，有余力的學(xué)生復(fù)習時還應(yīng)閱讀參考資料，認真整理課堂聽課筆記。

3.要求學(xué)生課外自主學(xué)習，學(xué)生課外閱讀的參考資料以本大綱所列參考資料為主。

4.認真完成所布置的大作業(yè)。

五、考核內(nèi)容及方式

本課程成績由平時成績和期末考核成績組合而成，課程成績以百分制計算，分配比例如

下：

1.平時成績占30%,主要考查作業(yè)的完成程度，理論課的出勤率，其中作業(yè)占25%,出

勤率占5%。

2.期末成績占70%,采用考試的考核方式。考試采用閉卷形式，題型為選擇題、正確/

錯誤題、填空題、簡答題，以及應(yīng)用題。

六、持續(xù)改進

本課程根據(jù)學(xué)生作業(yè)、課堂討論、平時考核情況和學(xué)生、教學(xué)督導(dǎo)等反饋，及時對教學(xué)

中不足之處進行改進，并在下一輪課程教學(xué)中改進。

七、建議教材及參考資料

建議教材：

[1]呂云翔，郭穎美，孟爻等.數(shù)據(jù)結(jié)構(gòu)（Python版）[M].北京：機械工業(yè)出版社，2020

參考資料：

[1]KennethA.Lambert.數(shù)據(jù)結(jié)構(gòu)Python語言描述[M].李軍，譯.北京：人民郵電出版

社,2017.

[2]裘宗燕.數(shù)據(jù)結(jié)構(gòu)與算法:Python語言描述[M].北京:機械工業(yè)出版社,2016.

教案

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

授課時數(shù)2

教學(xué)目的：

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

2.算法的描述(P8)和算法時間復(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ù)的一個自己，數(shù)據(jù)元素是數(shù)據(jù)對象的一個實例。

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

1.2]

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

散列存儲結(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ù)抽象指''定義和實現(xiàn)相分離”，即將一個類型的數(shù)據(jù)及其上的操作的邏

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

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

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

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

二算法：

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

列，其中每一條指令表示計算機的一個或者多個操作。

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

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

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

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

P9【例1.3]

三算法分析

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

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

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

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

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

間之和。

?通常采用算法的漸進分析中的大0表示作為算法時間復(fù)雜度的漸進度量值，稱為算法

的漸進時間復(fù)雜度。

?循環(huán)語句的時間代價一般可用一下3條原則進行分析：

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

2）多個并列的循環(huán)的時間代價=每個循環(huán)的時間代價之和。

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

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

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

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

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

2.難點是時間復(fù)雜度分析

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

1.介紹到算法概念

2.算法分析和舉例

使用教具：計算機和投影儀

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

P12

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

授課時數(shù)7

教學(xué)目的：

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

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

(P18-22)。

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

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

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

-線性表

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

1）基于順序存儲的實現(xiàn)2）基于鏈式存儲的實現(xiàn)。

二線性表的順序存儲

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

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

特點：

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

2）可按照數(shù)據(jù)元素的位序號進行隨機存取。

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

4）需要進行存儲空間的預(yù)先分配，可能會造成空間浪費，但存儲密度較高

描述：P17

插入操作：

P19圖2.3主要步驟為：

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

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

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

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

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

5）表長加1.P19【算法2.11

刪除操作

P20圖2.4主要步驟為：

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

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

3）表長減1.P20【算法2.2】

查找操作

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

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

P21[算法2.3][例2.3]P22【例2.4]

三線性表的鏈式存儲和實現(xiàn)

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

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

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

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

單鏈表

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

圖2.5、2.6

查找操作

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

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

P241算法2.4】【算法2.5]

插入操作

主要步驟如下：

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

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

3）修改前去結(jié)點的指針域為指向新節(jié)點的指針，新結(jié)點的指針域位指向原第i個結(jié)點

的指針。

P25【算法2.6]【算法2.7]

刪除操作

主要步驟如下

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

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

3）修改前驅(qū)結(jié)點的指針域為待刪除結(jié)點的指針域。P26【算法2.8】

單鏈表的建立操作

1）頭插法P26【算法2.91

2）尾插法P27【算法2.10】

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

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

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

題。

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

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

2.順序表算法鐘）

使用教具：計算機和投影儀

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

P28-30

講授章節(jié)第A-/r-二------,n早*r,棧LI1

授課時數(shù)6

教學(xué)目的：

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

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

3.要求在掌握棧和隊列的特點的基礎(chǔ)上，懂得在什么樣的情況下能夠使用棧或隊列。

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

一棧

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

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

在棧｛aO,al,a2,...,anT｝中aO成為占地元素，anT成為棧頂元素。通常，棧的

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

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

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

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

2）基于鏈式存儲的實現(xiàn)，為鏈棧。

順序棧

順序?；静僮鞯膶崿F(xiàn)入棧操作（P33圖3.1）

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

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

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

鏈棧

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

鏈?；静僮鞯膶崿F(xiàn)

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

1）改造購書值域為x的新結(jié)點。

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

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

P36【算法3.31

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

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

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

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

P36［【算法3.4】【例3.2］北37［【例3.3】【例3.4】］

二隊列

隊列的基本概念

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

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

列。

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

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

1）基于順序存儲的實現(xiàn)，為順序隊列。

2）基于鏈式存儲的實現(xiàn)，為鏈隊列。

順序隊列

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

對手進行，所以增加變量front來只是隊首元素的位置，rear指示隊尾元素的下一個存儲

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

P37圖3.8

順序隊列之所以會出現(xiàn)“假溢出”（P40圖3.9）現(xiàn)象是因為順序隊列的存儲單元沒有重

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

位項鏈，形成循環(huán)順序隊列。

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

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

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

對手節(jié)點和對為節(jié)點，每個節(jié)點的指針域指向其后繼結(jié)點即可。

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

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

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

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

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

2.鏈棧、中綴表達式求值

使用教具：計算機和投影儀

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

P47、48、49

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

授課時數(shù)5

教學(xué)目的:

1.本章主要是介紹串的基本概念(P50)

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

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

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

縮存儲方法（P61-64）。

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

-串

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

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

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

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

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

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

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

2）基于鏈式存儲的實現(xiàn)，為鏈串。

順序串

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

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

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

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

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

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

2）重新分配存儲空間為n+m,m為插入的字符串str的長度。

3）將第i個及之后的數(shù)據(jù)元素向后移動m個存儲單元。

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

3）刪除操作P54［【算法4.2］【算法4.3】］

4）連接操作

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

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

2）從下標0至n-1依次進行比較P54-55［【算法4.4］【例4.1】］

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

串的匹配模式

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

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

Brute-Force算法

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

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

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

KMP算法

Kmp算法的主要思想是當某次匹配失敗時主串的開始標位置不會推推，而是利用部分字

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

Kmp模式匹配算法分析

K值的計算「57【算法4.6】

Kmp算法步驟

1）計算模式穿的next□函數(shù)值

2）I為主串的比較字符位序號，j為模式串的比較字符位序號。當字符相等時，i,

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

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

P58［【算法4.7】【例4.2】【例4.3】］

二數(shù)組

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

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

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

數(shù)組的下標的個數(shù)是數(shù)組的維數(shù)，具有一個下標的數(shù)組叫一維數(shù)組，具有兩個下標的數(shù)

組叫二維數(shù)組。

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

數(shù)組的特性

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

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

數(shù)組的遍歷

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

三特殊矩陣的壓縮存儲

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

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

矩陣采用二維數(shù)組進行存儲，至少占用mxn個存儲單元。

三角矩陣的壓縮存儲

線性壓縮存儲

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

對稱矩陣的壓縮存儲

對角矩陣的壓縮存儲

稀疏矩陣的壓縮存儲

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

矩陣元素的行號，列號和元素值稱為鈣元素的三元組。

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

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

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

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

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

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

使用教具：計算機和投影儀

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

P65、P66,P67

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

授課時數(shù)7

教學(xué)目的：

1.介紹樹的定義(P68)

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

3.存儲結(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個結(jié)點構(gòu)成的有限集合，結(jié)點數(shù)

為0的樹叫空樹。

樹必須滿足：

1)有且僅有一個被稱為根的結(jié)點。

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

樹。

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

見68[圖5.1圖5.2]

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

二叉樹

二叉樹的基本概念

1）普通二叉樹

2）滿二叉樹

3）完全二叉樹

二叉樹的性質(zhì)

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

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

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

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

序列，將節(jié)點存放在下標為對應(yīng)編號的數(shù)組元素中。示意圖P71圖5.5

二叉樹的鏈式存儲結(jié)構(gòu)：是指將二叉樹的各個結(jié)點隨機存放在存儲空間中，二叉樹的各

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

二叉樹的鏈式存儲結(jié)構(gòu)又分為P72[【圖5.6]]

1）二叉鏈式存儲結(jié)構(gòu)

2）三叉鏈式存儲結(jié)構(gòu)

二叉樹鏈式存儲結(jié)構(gòu)的結(jié)點類的描述

二叉樹類的描述

二叉樹的遍歷

二叉樹的遍歷方法

二叉樹通?？蓜澐譃槿齻€部分，即根結(jié)點，左子樹和右子樹。根據(jù)3個部分的訪問順

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

1）層次遍歷

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

3)P73中序遍歷【算法5.2]

4)P73后序遍歷【算法5.3]

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

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

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

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

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

1)P74先序遍歷【算法5.4]

2)P74中序遍歷【算法5.51

3)P75后序遍歷【算法5.61

4)P75層次遍歷【算法5.7]

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

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

統(tǒng)計二叉樹的結(jié)點個數(shù)的算法P77【算法5.91

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

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

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

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

二哈夫曼樹及哈夫曼編碼

哈夫曼樹的基本概念

1結(jié)點間的路徑

2節(jié)點的路徑長度

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

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

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

6最優(yōu)二叉樹

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

P81【圖5.10]P80【例5.4]

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

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

以為了提高算法的效率將哈夫曼樹的結(jié)點設(shè)計為三叉鏈式存儲結(jié)構(gòu)。

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

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

三樹和森林

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

1樹的父母孩子鏈表

2樹的父母孩子兄弟鏈表

樹的遍歷規(guī)則

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

1）樹的先序遍歷

2）樹的后序遍歷

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

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

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

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

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

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

使用教具：計算機和投影儀

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

P84、P85、P86

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

授課時數(shù)7

教學(xué)目的：

1.主要介紹圖的基本概念(P87)

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

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

4.最短路徑的相關(guān)算法(P104T07),拓撲排序的概念和實現(xiàn)方法(P107T10)。

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

一圖概述

圖的概念

?無向邊

?有向邊

?零圖

?無向圖

?有向圖

?完全圖P88【圖6.16.26.3]

?稠密圖

?子圖

?生成子圖

?鄰接點

?頂點的度

?路徑

?回路

?連通圖

?連通分量

?強連通圖

?強連通分量

?生成樹和生成森林

?網(wǎng)

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

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

鄰接矩陣

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

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

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

無/有向網(wǎng)）

2）頂點的定位P921算法6.5]

3）查找第一個鄰接點P92【算法6.6]

4）查找下一個鄰接點P92【算法6.7]

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

鄰接表

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

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

1）圖的創(chuàng)建【算法P95E6.86.9]P96[6.106.11]]（創(chuàng)建無/有向圖,創(chuàng)建無/

有向網(wǎng)）

2）在圖中插入邊節(jié)點P96【算法6.12]

3）查找第一個鄰接點P96【算法6.13]

4）查找下一個鄰接點

三圖的遍歷

圖的遍歷概念

圖的遍歷方式分為

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

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

6.14]

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

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

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

四最小生成樹

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

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

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

2)具有n個頂點和n-1條邊

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

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

Krusakl算法

Prim算法

P1041例6.6]

五最短路徑

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

1.求某個頂點到其余頂點的最短路徑

2.求任意兩個頂點間的最短路徑

六拓撲排序和關(guān)鍵路徑

拓撲排序

主要步驟

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

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

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

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

P108【算法6.166.17]

關(guān)鍵路徑

由于AOE網(wǎng)中某些活動可以并行進行，故完成整個工程的最短時間即從源點到匯點的最

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

P109-110【算法6.186.19]

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

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

重點掌握圖的存儲結(jié)構(gòu)和圖的兩種遍歷算法(P89-101))

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

最短路徑(P104-106)

拓撲排序和關(guān)鍵路徑算法(P107-110)。

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

使用教具：計算機和投影儀

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

P11KP112

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

授課時數(shù)7

教學(xué)目的:

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

2.排序過程

3.算法實現(xiàn)

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

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

一排序概述

排序的基本概念

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

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

排序算法的性能評價

通常從時間復(fù)雜度和空間復(fù)雜度兩個方面評價排序算法的性能

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

二插入排序

直接插入排序

1.直接插入算法的實現(xiàn)P114［【圖7.1］【算法7.1］］

2.算法性能分析

1.時間復(fù)雜度

2.空間復(fù)雜度

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

希爾排序

1.希爾排序算法的實現(xiàn)P115［【圖7.2】【算法7.2】］

2.算法性能分析

1.時間復(fù)雜度

2.空間復(fù)雜度

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

三交換排序

冒泡排序

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

2.算法性能分析

1.時間復(fù)雜度

2.空間復(fù)雜度

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

快速排序

1.快速排序算法的實現(xiàn)P1181圖7.47.51P119【算法7.4】

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

1.時間復(fù)雜度

2.空間復(fù)雜度

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

四選擇排序

直接選擇排序

1.直接選擇排序算法的實現(xiàn)P121E【圖7.6】【算法7.5】］

2.算法性能分析

1.時間復(fù)雜度

2.空間復(fù)雜度

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

堆排序

1.堆的定義

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

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

在進行堆排序的過程中，當堆頂元素和堆中的最后一個元素交換位置后根結(jié)點和其

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

3.堆排序P123【算法7.7】

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

1.時間復(fù)雜度

2.空間復(fù)雜度

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

五歸并程序

1.兩個相鄰有序序列歸并P124【算法7.8]

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

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

算法性能分析P1