數(shù)據(jù)結構教學大綱

《數(shù)據(jù)結構》教學大綱

課程代碼：********。

課程負責人：********。

課程中文名稱：數(shù)據(jù)結構。

課程英文名稱：DataStructures。

課程類別：專業(yè)基礎課必修.

課程學分數(shù)：3。

課程學時數(shù)：講課32/48學時，上機32學時。

授課對象：計算機科學與技術專業(yè)。

本課程的前導課程：高級語言程序設計。

本課程的后續(xù)課程：操作系統(tǒng)、數(shù)據(jù)庫應用技術等?

一'教學目的

《數(shù)據(jù)結構》是計算機專業(yè)一門重要的專業(yè)基礎課。通過本課程的學習，使得學生從數(shù)

據(jù)邏輯結構、存儲結構和基本運算算法設計三個層面掌握基本的數(shù)據(jù)組織和數(shù)據(jù)處理方法，

能夠從問題出發(fā)設計面向數(shù)據(jù)結構的求解算法，并能夠對算法進行時間復雜度與空間復雜度

分析。為后續(xù)課程如操作系統(tǒng)等課程學習打下基礎。

二、教學要求

通過講授和上機實驗，使學生了解《數(shù)據(jù)結構》的原理和特點。掌握線性表、棧和隊列、

串、數(shù)組和稀疏矩陣、樹和二叉樹、圖、查找和排序等基本數(shù)據(jù)結構及其相關算法的設計。

具備一定的利用數(shù)據(jù)結構方法求解實際問題的能力。

三、課程知識點

知識單元知識點名稱知識點內容知識點類型備注

數(shù)據(jù)結構的基認識數(shù)據(jù)結構的定義、包括數(shù)據(jù)邏輯結

一般知識點

本概念構、存儲結構和運算的3個層次。

算法的基本概

認識算法的定義和5個基本特性。重要知識點

念

數(shù)據(jù)結構算法描述認識用高級語言如C/C++描述算法的自我

一般知識點

概述基本方法。學習

算法分析掌握算法的時間復雜度和空間復雜度

重要知識點

分析方法。

數(shù)據(jù)結構+算認識從數(shù)據(jù)結構角度求解問題的基本

重要知識點

法=程序步驟。

線性表及其邏認識線性表的定義和線性表的基本運

一般知識點

輯結構算。

線性表的順序

掌握順序表的存儲結構特點和順序表

存儲結構一順重要知識點

基本運算的實現(xiàn)。

序表

線性表的鏈式掌握單鏈表的存儲結構特點、單鏈表的

存儲結構一單插入和刪除節(jié)點操作、單鏈表的建表方重要知識點

鏈表法、以及單鏈表基本運算的實現(xiàn)。

線性表線性表的鏈式掌握雙鏈表的存儲結構特點、雙鏈表的

存儲結構一雙插入和刪除節(jié)點操作、雙鏈表的建表方重要知識點

鏈表法、以及雙鏈表基本運算的實現(xiàn)。

掌握循環(huán)鏈表的存儲結構特點、循環(huán)鏈

線性表的鏈式

表的插入和刪除節(jié)點操作、循環(huán)鏈表的

存儲結構一循重要知識點

建表方法、以及循環(huán)鏈表基本運算的實

環(huán)鏈表

現(xiàn)。

掌握從求解問題描述、數(shù)據(jù)組織到運算

線性表的應用難度知識點

算法設計完整過程。

了解棧的定義、棧的邏輯結構特性和棧

棧的基本概念一般知識點

的基本運算。

棧的順序存儲掌握順序棧的存儲結構特點和順序棧

重要知識點

棧結構-順序?；具\算的實現(xiàn)。

棧的鏈式存儲掌握鏈棧的存儲結構特點和鏈?；?/p>

重要知識點

結構-鏈棧運算的實現(xiàn)。

棧的應用了解棧在表達式求值中的應用。難度知識點

隊列的基本概了解隊列的定義、隊列的邏輯結構特性

一般知識點

念和隊列的基本運算。

隊列的順序存掌握順序隊的存儲結構特點和順序隊

重要知識點

隊列儲結構-順序隊基本運算的實現(xiàn)。

隊列的鏈式存掌握鏈隊的存儲結構特點和鏈隊基本

重要知識點

儲結構-鏈隊運算的實現(xiàn)。

隊列的應用了解隊列在病人看病問題中的應用。難度知識點

了解串的定義、串的邏輯結構特性和串

串的基本概念一般知識點

的基本運算。

串的順序存儲掌握順序串的存儲結構特點和順序串

串一般知識點

結構一順序串基本運算的實現(xiàn)。

串的鏈式存儲掌握鏈串的存儲結構特點和鏈串基本

一般知識點

結構-鏈串運算的實現(xiàn)。

數(shù)組的基本概

了解數(shù)組的定義和數(shù)組的存儲結構。一般知識點

念

數(shù)組和稀特殊矩陣的壓了解對稱矩陣、上下三角矩陣和對角矩

重要知識點

疏矩陣縮存儲陣的壓縮存儲。

了解稀疏矩陣的特點、稀疏矩陣的三元

稀疏矩陣一般知識點

組表示和十字鏈表表示。

樹樹的基本概念了解樹的定義、樹的邏輯表示方法和樹一般知識點

的基本術語。

樹的性質了解樹的4個性質及其應用。一般知識點

掌握樹的先根遍歷、后根遍歷和層次遍

樹的基本運算一般知識點

歷過程。

掌握樹的雙親存儲結構、孩子鏈存儲結

樹的存儲結構一般知識點

構和孩子兄弟鏈存儲結構以及特點。

了解二叉樹、滿二叉樹和完全二叉樹的

二叉樹的基本

定義、二叉樹的邏輯表示方法和二叉樹一般知識點

概念

的基本術語。

二叉樹樹的性

了解二叉樹樹的5個性質及其應用。重要知識點

質

二叉樹與樹、

了解森林、樹轉換為二叉樹以及二叉樹

森林之間的轉一般知識點

還原為森林、樹的過程。

換

二叉樹存儲結掌握二叉樹的順序存儲結構和二叉樹

重要知識點

構的鏈式存儲結構。

二叉樹的基本

掌握二叉樹的基本運算及其實現(xiàn)過程。重要知識點

運算及其實現(xiàn)

二叉樹掌握二叉樹的先序遍歷、中序遍歷、后

序遍歷和層次遍歷算法設計，了解先序

二叉樹的遍歷重要知識點

遍歷、中序遍歷和后序遍歷非遞歸算法

設計。

二叉樹遍歷應掌握二叉樹的4種遍歷在二叉樹算法

難度知識點

用設計中的應用。

掌握由先序遍歷、中序遍歷序列構造二

二叉樹的構造叉樹和由后序遍歷、中序遍歷序列構造一般知識點

二叉樹的過程.

了解線索二叉樹的概念、線索二叉樹的

線索二叉樹一般知識點

構造和遍歷過程。

掌握哈夫曼樹的概念、構造哈夫曼樹和

哈夫曼樹一般知識點

產生哈夫曼編碼的過程。

圖的基本概念了解圖的定義和圖的基本術語。一般知識點

掌握圖的鄰接矩陣存儲方法和鄰接表

圖的存儲結構重要知識點

表存儲方法。

掌握圖深度優(yōu)先搜索遍歷和廣度優(yōu)先

圖的遍歷重要知識點

搜索遍歷算法。

圖遍歷算法的掌握圖的兩種遍歷算法在圖算法設計

難度知識點

圖應用中的應用。

了解生成樹和最小生成樹的概念，掌握

生成樹和最小

構造最小生成樹的普里姆算法和克魯重要知識點

生成樹

斯卡爾算法。

了解最短路徑的概念,掌握構造最短路

最短路徑重要知識點

徑的狄克斯特拉算法和弗洛伊德算法。

拓撲排序了解拓撲排序的概念和拓撲排序過程。一般知識點

AOE網與關鍵了解AOE網與關鍵路徑的概念、求解

一般知識點

路徑關鍵路徑的過程。

查找的基本概

查找表和平均查找長度ASL的定義。一般知識點

念

掌握順序查找、折半查找和分塊查找算

線性表的查找重要知識點

法設計和算法分析。

掌握二叉排序樹的算法設計。重要知識點

查找

樹表的查找了解平衡二叉樹、B和B+樹的組織和

一般知識點

查找過程。

掌握哈希表的基本概念、哈希函數(shù)構造

哈希表查找方法、哈希沖突解決方法和哈希查找過重要知識點

程。

排序的基本概了解排序算法的穩(wěn)定性、排序算法的分

一般知識點

念類。

掌握直接插入排序算法的思路、排序算

法和算法分析，折半插入排序算法的思

插入排序重要知識點

路、排序算法和算法分析，希爾排序算

法的思路、排序算法和算法分析。

掌握冒泡排序算法的思路、排序算法和

交換排序算法分析，快速排序算法的思路、排序重要知識點

算法和算法分析。

掌握直接選擇排序算法的思路、排序算

選擇排序法和算法分析，堆排序算法的思路、排重要知識點

排序序算法和算法分析。

掌握歸并排序算法的思路，二路歸并算

歸并排序重要知識點

法和算法分析。

掌握基數(shù)排序算法的思路、排序算法和

基數(shù)排序重要知識點

算法分析。

各種內排序方

掌握各種內排序方法時間和空間因素

法的比較和選難度知識點

的比較和分析。

擇

外排序的基本

了解外排序概念和外排序的一般過程。一般知識點

概念

掌握磁盤排序中生成初始歸并段、多路

磁盤排序重要知識點

平衡歸并和構造最佳歸并樹的過程。

四'課程能力點

能力單元能力點名稱能力點要求能力點類型備注

掌握從數(shù)據(jù)邏輯結構到存儲結構的

映射關系，算法的時間復雜度和空

面向數(shù)據(jù)結構數(shù)據(jù)結構算法

間復雜度分析，使學生能夠從數(shù)據(jù)思維能力點

的算法設計設計流程

結構角度出發(fā)，掌握從邏輯結構一

存儲結構f基本運算算法設計的流

程，并通過設計合理的存儲結構來

設計出好算法的過程。

掌握線性表的順序存儲結構和鏈式

線性表算法設

存儲結構中線性表基本運算算法設設計能力點

計

計方法。

線性表

掌握線性表的邏輯結構f存儲結構

線性表應用一運算算法設計的主線，利用線性設計能力點

表求解實際應用問題。

掌握棧的順序存儲結構和鏈式存儲

棧算法設計設計能力點

結構中棧基本運算算法設計方法。

掌握隊列的順序存儲結構和鏈式存

隊列算法設計儲結構中隊列基本運算算法設計方設計能力點

棧和隊列法。

掌握棧在實際求解問題中的應用方

棧的應用設計能力點

法。

掌握隊列在實際求解問題中的應用

隊列的應用設計能力點

方法。

掌握二叉樹、滿二叉樹和完全二叉

二叉樹結構思維能力點

樹的性質和結點計算。

二叉樹遍歷算掌握二叉樹4種遍歷算法設計

二叉樹設計能力點

法設計

二叉樹遍歷算掌握基于二叉樹遍歷的二叉樹遞歸

設計能力點

法的應用算法設計

圖遍歷算法設

掌握基于兩種圖遍歷的圖算法設計設計能力點

il-

圖掌握求最小生成樹的Prim和

圖的應用Kruskal算法和求最短路徑的設計能力點

Dijkstra和Flody算法。

掌握順序查找、折半查找、二叉排

查找算法設計思維能力點

序樹和哈希表查找算法。

查找

基于不同的數(shù)據(jù)結構選擇合適的查

查找的應用設計能力點

找算法求解問題。

掌握直接插入排序、折半插入排序、

內排序算法設希爾排序、冒泡排序、快速排序、

思維能力點

計簡單選擇排序、堆排序、二路歸并

排序

排序和基數(shù)排序算法。

基于不同的要求選擇合適的內排序

內排序的應用設計能力點

算法求解問題。

五、授課課時安排（32/48課時）

授課

知識單元涵蓋知識點情況授課目標重難點要求備注

課時

目標：①數(shù)據(jù)結構的基本概念，②數(shù)

據(jù)邏輯結構和存儲結構的映射關系，

③數(shù)據(jù)類型和數(shù)據(jù)結構的區(qū)別和聯(lián)

系，④利用抽象數(shù)據(jù)類型表述求解問

題的方法，⑤算法的特性和采用

數(shù)據(jù)結構的基本概念；

C/C++語言描述算法的方法，⑥算法

算法的基本概念；算法

1、緒論2/2設計目標和分析方法，包括時間復雜

描述；算法分析；數(shù)據(jù)

度和空間復雜度分析，⑦從數(shù)據(jù)結構

結構+算法=程序

的角度設計好算法的過程。

重點和難點：①算法的時間和空間復

雜度分析，特別是遞歸算法的時間和

空間復雜度分析，②如何設計好的算

法。

線性表及其邏輯結構；目標：①線性表的邏輯結構特點和線

線性表的順序存儲結性表抽象數(shù)據(jù)類型的描述方法，②線

構一順序表；線性表的性表的兩類存儲結構設計方法以及

鏈式存儲結構一單鏈各自的優(yōu)缺點，③順序表算法設計方

2、線性表6/8表：線性表的鏈式存儲法，④單鏈表、雙鏈表和循環(huán)鏈表算

結構一雙鏈表；線性表法設計方法。

的鏈式存儲結構一循重點：順序表、單鏈表、雙鏈表和循

環(huán)鏈表；線性表的應環(huán)鏈表算法設計方法。

用；有序表。難點：利用線性表求解復雜問題。

目標：①棧的邏輯結構特性和棧抽象

數(shù)據(jù)類型的描述方法，②棧的先進后

出特點，③棧基本運算在兩類存儲結

棧的基本概念；棧的順構下的實現(xiàn)算法，④棧在實際求解問

序存儲結構-順序棧；題中的應用方法，⑤隊列的邏輯結構

棧的鏈式存儲結構-鏈特性和隊列抽象數(shù)據(jù)類型的描述方

3、棧和隊棧；棧的應用；隊列的法，⑥隊列的先進后出特點，⑦隊列

4/6

列基本概念；隊列的順序基本運算在兩類存儲結構下的實現(xiàn)

存儲結構-順序隊；隊算法，⑧隊列在實際求解問題中的應

列的鏈式存儲結構-鏈用方法。

隊；隊列的應用。重點：①棧算法設計，②隊列算法設

計。

難點：棧和隊列在求解復雜問題中的

應用。

目標：①串的邏輯結構特性和串抽象

數(shù)據(jù)類型的描述方法，②串的兩類存

串的基本概念；串的順

儲結構設計方法以及各自的優(yōu)缺點，

序存儲結構-順序串；

4、串2/2③順序串算法設計方法，④鏈串算法

串的鏈式存儲結構-鏈

設計方法。

串。

重點：①順序串運算算法設計，②鏈

串運算算法設計、

5、數(shù)組和2/2數(shù)組的基本概念；特殊目標：①數(shù)組的邏輯結構特性和數(shù)組

稀疏矩陣矩陣的壓縮存儲；稀疏抽象數(shù)據(jù)類型的描述方法，②數(shù)組的

矩陣。順序存儲結構及其特點，③對稱矩

陣、上三角矩陣、下三角矩陣和三對

角矩陣的壓縮存儲，④稀疏矩陣的兩

種壓縮存儲方法。

重點：各種特殊矩陣的壓縮存儲方

法。

目標：①樹的定義及其邏輯結構特

性，②樹的邏輯結構表示方法和樹的

樹的基本概念；樹的性性質，③樹的遍歷方法和樹的存儲結

質；樹的基本運算；樹構，④二叉樹的定義及其性質，⑤二

的存儲結構；二叉樹的叉樹與樹、森林之間的轉換，⑥二叉

基本概念；二叉樹樹的樹的兩種存儲結構和二叉樹的基本

性質；二叉樹與樹、森運算算法設計。⑦二叉樹的遍歷過

6、樹和二林之間的轉換；二叉樹程、算法設計及其應用。⑧二叉樹的

6/8

叉樹存儲結構；二叉樹的基構造過程，⑨線索二叉樹的特點及其

本運算及其實現(xiàn)；二叉構造過程，⑩哈夫曼樹和哈夫曼編碼

樹的遍歷；二叉樹遍歷的構造過程。

應用；二叉樹的構造；重點：①二叉樹性質和二叉樹結點計

線索二叉樹；哈夫曼算，②二叉樹的遍歷過程、算法設

樹。計及其應用。

難點：靈活利用二叉樹的遍歷思路進

行較復雜二叉樹算法設計。

目標：①圖的定義及其邏輯結構特

性，圖抽象數(shù)據(jù)類型的描述方法，②

圖的基本術語及其含義，③圖的鄰接

矩陣和鄰接表兩種主要的存儲結構

及其特點，④圖的深度優(yōu)先和廣度優(yōu)

先遍歷算法，⑤圖遍歷算法的應用，

圖的基本概念；圖的存⑥生成樹和最小生成樹的定義和求

儲結構；圖的遍歷；圖最小生成樹的Prim和Kruskal算法，

遍歷算法的應用；生成⑦最短路徑的概念和求最短路徑的

7、圖4/8

樹和最小生成樹；最短Dijkstra和Flody算法,⑧拓撲排序過

路徑；拓撲排序；AOE程，⑨關鍵路徑的定義及其構造過

網與關鍵路徑。程。

重點：①圖的鄰接矩陣和鄰接表兩種

主要的存儲結構及其特點，②圖的深

度優(yōu)先和廣度優(yōu)先遍歷算法，③Prim

和Kruskal算法，④Dijkstra和Flody

算法。

難點：圖遍歷算法的應用。

查找的基本概念；線性目標：①掌握查找的概念，②線性表

8、查找3/6表的查找；樹表的查的順序查找和折半查找算法，索引存

找；哈希表查找。儲結構和分塊查找方法，③二叉排序

樹的定義、查找和插入算法、刪除過

程，④平衡二叉樹的特點及其調整方

法，⑤B-樹的定義和基本操作過程，

B+的定義，⑥哈希表的定義及其特

點，⑦哈希函數(shù)構造方法和解決沖突

的方法，⑧各種查找方法的性能分

析。

重點：各種查找算法的實現(xiàn)。

難點：各種查找方法的性能分析。

目標：①排序的定義和相關概念，②

插入排序算法，包括直接插入排序、

折半插入排序和希爾排序，③交換排

序算法，包括冒泡排序和快速排序，

排序的基本概念；插入④選擇排序算法，包括簡單選擇排序

排序；交換排序；選擇和堆排序，⑤歸并排序算法，包括二

9、排序3/6排序；歸并排序；基數(shù)路歸并排序，⑥基數(shù)排序算法，包括

排序；各種內排序方法最低位優(yōu)先和最高位優(yōu)先排序，⑦各

的比較和選擇。種內排序方法的性能分析和比較。⑧

外排序的基本過程。

重點：各種排序算法的實現(xiàn)。

難點：各種內排序方法的性能分析和

比較。

六、上機課時安排（32課時）

課時課

內容對應能力點要求備注

類型時

設計順序表各種基本運

上機實驗項目1一線性表線性表算法

算的算法，設計單鏈表2

基本運算算法設計。設計

各種基本運算的算法。

設計順序棧各種基本運

上機實驗項目2—?；?/p>

棧算法設計算的算法，設計鏈棧各2

運算算法設計。

種基本運算的算法。

設計順序隊各種基本運

上機實驗項目3一隊列基隊列算法設

上機算的算法，設計鏈隊各2

本運算算法設計。計

實驗種基本運算的算法。

題上機實驗項目4一求解〃遞歸算法設掌握遞歸算法設計方

2

皇后問題。計法。

上機實驗項目5一二叉樹二叉樹遍歷掌握二叉樹4種遍歷算

2

4種遍歷算法設計算法設計法的特點和實現(xiàn)過程。

上機實驗項目6—圖遍歷圖遍歷算法掌握圖的DFS和BFS遍

2

算法設計設計歷算法設計。

上機實驗項目7—圖中帶圖遍歷算法掌握圖的DFS遍歷算法

2

條件的路徑查找設計設計。

上機實驗項目8—線性表查找算法設掌握順序查找和折半查

2

的查找算法設計計找算法設計。

上機實驗項目9—樹表的查找算法設掌握二叉排序樹算法設

2

查找算法設計計，il'o

上機實驗項目10―哈希表查找算法設掌握哈希表查找算法設

2

的查找算法設計計il'o

掌握直接插入排序、折

上機實驗項目11一插入排內排序算法

半插入排序、希爾排序1

序算法設計設計

算法設計。

上機實驗項目12一交換排內排序算法掌握冒泡排序、快速排

1

序算法設計設計序算法設計。

上機實驗項目13一選擇排內排序算法掌握簡單選擇排序和堆