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

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

一、課程基本概況

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

課程名稱（英文）： Data Structures

課程編號：B09042

課程總學(xué)時：60（其中，講課48，實驗12）

課程學(xué)分：3

課程分類：專業(yè)選修課

開設(shè)學(xué)期：4

適用專業(yè)：計算機網(wǎng)絡(luò)工程本科

先修課程：集合論，圖論，高級語言（結(jié)構(gòu)或記錄，指針）

后續(xù)課程：數(shù)據(jù)庫，編譯原理，操作系統(tǒng)等

二、課程的性質(zhì)、目的和任務(wù)

數(shù)據(jù)結(jié)構(gòu)是計算機專業(yè)的一門核心專業(yè)課程，是軟件課程中非常重要的一門課程，在整個專業(yè)教學(xué)中占有十分重要的地位，是一門理論性非常強的課程。通過課堂教學(xué)、課外練習(xí)和上機實習(xí)，使學(xué)生了解數(shù)據(jù)對象的特性，數(shù)據(jù)組織的基本方法，并初步具備分析和解決現(xiàn)實世界問題在計算機中如何表示和處理的能力以及培養(yǎng)良好的程序設(shè)計技能，為后續(xù)課程的學(xué)習(xí)和科研工作的參與打下良好的基礎(chǔ)。

三、主要內(nèi)容、重點及深度

本門課程共60學(xué)時，其中理論教學(xué)48學(xué)時，實驗教學(xué)12學(xué)時。其中，理論教學(xué)部分：

第一章

緒論

（一）目的要求

了解數(shù)據(jù)結(jié)構(gòu)的意義與發(fā)展過程、數(shù)據(jù)結(jié)構(gòu)在計算機科學(xué)中的作用、學(xué)習(xí)本課程的目的、任務(wù)及要求。理解數(shù)據(jù)結(jié)構(gòu)的基本概念；算法設(shè)計；掌握算法的時間和空間復(fù)雜度。

（二）教學(xué)內(nèi)容 本章知識點：

1.相關(guān)的基本概念(掌握)；

2.算法五大要素(掌握)；

3.計算語句頻度和估算算法時間復(fù)雜度的方法（掌握）。

（三）重點與難點

重點：數(shù)據(jù)結(jié)構(gòu)的定義；算法的描述方法。

難點：數(shù)據(jù)結(jié)構(gòu)的定義；算法與程序的區(qū)別；時間復(fù)雜度及其計算。

第二章

線性表

（一）目的要求

掌握線性表的邏輯結(jié)構(gòu)；線性表的存儲結(jié)構(gòu)及操作的實現(xiàn)；理解一元多項式的表示；

（二）教學(xué)內(nèi)容 本章知識點：

1.線性表的邏輯結(jié)構(gòu)(掌握)；2.線性表的存儲結(jié)構(gòu)(掌握)；

3.線性表在順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)上實現(xiàn)基本操作的方法(掌握)；

4.從時間和空間復(fù)雜度的角度比較線性表兩種存儲結(jié)構(gòu)的不同特點及其適用場合(掌握)。

（三）重點與難點

重點：線性表的概念；線性表的順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)及其常用算法。難點：鏈?zhǔn)酱鎯Y(jié)構(gòu)及其常用算法；雙向循環(huán)鏈表。

第三章 棧和隊列

（一）目的要求

掌握棧的定義，表示及實現(xiàn)；表達(dá)式求值；棧與遞歸過程；隊列的定義、表示及實現(xiàn)。

（二）教學(xué)內(nèi)容 本章知識點： 1.棧和隊列的特點(掌握)；

2.在兩種存儲結(jié)構(gòu)上棧的基本操作的實現(xiàn)(掌握)； 3.循環(huán)隊列和鏈隊列的基本運算(熟練掌握)； 4.遞歸算法執(zhí)行過程中棧狀態(tài)的變化過程(掌握)。

（三）重點與難點

重點：堆棧和隊列的概念；遞歸的定義；循環(huán)隊列和鏈隊列的基本運算。難點：遞歸的編程實現(xiàn)；循環(huán)隊列和鏈隊列的基本運算。

第四章 串

（一）目的要求

了解串的邏輯結(jié)構(gòu)，存儲結(jié)構(gòu)；掌握串操作的實現(xiàn)(重點難點BF和KMP算法)串的應(yīng)用。

（二）教學(xué)內(nèi)容 本章知識點：

1.串的七種基本運算的定義（了解）；

2.利用這些基本運算來實現(xiàn)串的其它各種運算的方法(掌握)； 3.在順序存儲結(jié)構(gòu)上實現(xiàn)串的各種操作的方法(掌握)；

4.KMP算法，熟悉NEXT函數(shù)和改進(jìn)NEXT函數(shù)的定義和計算(掌握)； 5.串名的存儲映象和在堆存儲結(jié)構(gòu)實現(xiàn)串操作的方法(理解)。

（三）重點與難點 重點：串定義和存儲方法；串的操作 難點：串操作實現(xiàn)方法

第五章 數(shù)組和廣義表

（一）目的要求

掌握數(shù)組的存儲結(jié)構(gòu)；稀疏矩陣的表示及操作的實現(xiàn)；廣義表的定義和存儲結(jié)構(gòu)；廣義表的遞歸算法。

（二）教學(xué)內(nèi)容 本章知識點：1.數(shù)組在以行為主的存儲結(jié)構(gòu)中的地址計算方法(掌握)； 2.矩陣實現(xiàn)壓縮存儲時的下標(biāo)變換(掌握)；

3.理解稀疏矩陣的兩種存儲方式的特點和適用范圍，領(lǐng)會以三元組表示稀疏矩陣時進(jìn)行運算采用的處理方法(掌握)；

4.廣義表的定義及其存儲結(jié)構(gòu)，學(xué)會廣義表的表頭，表尾分析方法(掌握)； 5.學(xué)習(xí)編制廣義表的遞歸算法(掌握)。

（三）重點與難點

重點：多維數(shù)組元素存儲地址的計算；稀疏矩陣的三元組表示；廣義表的存儲定義、操作。難點：稀疏矩陣的三元組表示；廣義表的存儲定義、操作。

第六章 樹和二叉樹

（一）目的要求

了解樹的基本概念；理解二叉樹的性質(zhì)和存儲結(jié)構(gòu)；遍歷二叉樹和線索二叉樹；理解樹的存儲結(jié)構(gòu)和遍歷；集合的一種表示方法；掌握哈夫曼樹及其應(yīng)用；

（二）教學(xué)內(nèi)容 本章知識點： 1.二叉樹的結(jié)構(gòu)特點(理解)；

2.二叉樹的各種存儲結(jié)構(gòu)的特點及適用范圍(掌握)； 3.按各種次序遍歷二叉樹的遞歸和非遞歸算法(掌握)；

4.二叉樹的線索化，在中序線索樹上找給定結(jié)點的前驅(qū)和后繼的方法(掌握)； 5.樹的各種存儲結(jié)構(gòu)及其特點(掌握)； 6.編寫樹的各種運算的算法(掌握)；

7.建立最優(yōu)二叉樹和哈夫曼編碼的方法(掌握)。

（三）重點與難點 重點：二叉樹的概念、性質(zhì)；二叉樹的遍歷方式；構(gòu)造二叉排序樹。難點：二叉樹的遍歷方式；二叉排序樹的構(gòu)造方法；二叉樹的線索化。

第七章 圖

（一）目的要求

理解圖的基本概念；圖的存儲結(jié)構(gòu)；掌握圖的遍歷及應(yīng)用{最小生成樹，最短路徑等}；拓?fù)渑判蚝完P(guān)鍵路徑。

（二）教學(xué)內(nèi)容 本章知識點： 1.熟悉圖的各種存儲結(jié)構(gòu)；

2.了解實際問題與采用何種存儲結(jié)構(gòu)和算法有密切聯(lián)系(掌握)； 3.遍歷圖的遞歸和非遞歸算法(掌握)；

4.應(yīng)用圖的遍歷算法求各種簡單路徑問題（比如，最小生成樹、最短路徑、拓?fù)渑判?、關(guān)鍵路徑等）(掌握)。

（三）重點與難點

重點：圖的存儲結(jié)構(gòu)；圖的遍歷 難點：圖遍歷的算法；

第八章

動態(tài)存儲管理

（一）目的要求

了解邊界標(biāo)識法和伙伴系統(tǒng)；無用單元收集和緊縮；

（二）教學(xué)內(nèi)容 本章知識點：

1.存儲器分配策略和算法（了解）；

2.無用單元收集時的標(biāo)志算法（了解）。

（三）重點與難點

存儲器分配策略和算法、無用單元收集時的標(biāo)志算法

第九章

查找

（一）目的要求

了解靜態(tài)查找表(順序表，有序表，索引順序表)；動態(tài)查找表(二叉排序樹，平衡二叉樹，B-樹和B+樹)的建立和查找；掌握哈希表的建立，查找及分析；

（二）教學(xué)內(nèi)容 本章知識點：

1.順序查找、折半查找和索引查找的方法、應(yīng)用(掌握)；

2.二叉排序樹的構(gòu)造方法(掌握)；

3.二叉平衡樹的建立方法(掌握)；

4.B-樹，B+樹和鍵樹的特點以及它們的建立過程（理解）；

5.哈希表的構(gòu)造方法(掌握)；

6.按定義計算各種查找方法在等概率情況下查找成功時和失敗時的平均查找長度；

7.哈希表在查找不成功時的平均查找長度的計算方法(掌握)。

（三）重點與難點

重點：二叉排序樹的構(gòu)造方法、二叉平衡樹的建立方法；哈希表的構(gòu)造、應(yīng)用；

難點：二叉排序樹的構(gòu)造及應(yīng)用；哈希表的構(gòu)造方法；查找的平均長度。

第十章

內(nèi)部排序

（一）目的要求

掌握插入排序、交換排序(起泡排序，快速排序)、選擇排序(簡單選擇，樹形選擇，堆)、歸并排序、基數(shù)排序等算法。

（二）教學(xué)內(nèi)容 本章知識點：

1.各種排序方法的特點并能靈活應(yīng)用(掌握)； 2.各種方法的排序過程(掌握)；

3.各種排序方法的時間復(fù)雜度分析(掌握)。

（三）重點與難點

重點：各種排序方法的特點及其應(yīng)用；實現(xiàn)排序的各種算法。難點：各種排序算法的時間復(fù)雜度分析。

十一章

外部排序

（一）目的要求

理解外部排序的基本方法；掌握敗者樹和多路平衡歸并的實現(xiàn)；置換--選擇排序；最佳歸并樹。

（二）教學(xué)內(nèi)容 本章知識點：

1.外部排序的兩個過程(理解)；

2.外排過程中所需進(jìn)行外存讀/寫次數(shù)的計算方法(掌握)；

3.敗者樹的建立過程(掌握)；

4.實現(xiàn)多路歸并的算法(掌握)；

5.置換-選擇排序的過程(掌握)；

6.最佳歸并樹的構(gòu)造方法（熟悉）；

7.按最佳歸并樹的歸并方案進(jìn)行平衡歸并時，外存讀/寫次數(shù)的計算方法(掌握)。

（三）重點與難點

重點：外部排序過程和實現(xiàn)方法；多路并歸算法及其實現(xiàn)； 難點：最佳并歸樹的構(gòu)造方法及其應(yīng)用。

實踐教學(xué)部分：上機實驗分4個專題，每個專題可提供2~4個難度不等的題目供選。

實驗一

停車場管理系統(tǒng)

（一）實驗內(nèi)容 以棧模擬車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬管理。棧以順序結(jié)構(gòu)實現(xiàn)，隊列以鏈表結(jié)構(gòu)實現(xiàn)。

（二）實驗過程 編程實現(xiàn)實驗內(nèi)容。

（三）實驗教學(xué)基本要求

通過實例，使學(xué)生掌握棧和隊列兩種特殊的線性結(jié)構(gòu)，掌握棧和隊列的特點。實驗后學(xué)生提交實驗報告。

（四）實驗設(shè)備和材料 計算機。

（五）實驗學(xué)時 4學(xué)時

實驗二

教學(xué)計劃編制問題

（一）實驗內(nèi)容

假設(shè)任何專業(yè)都有固定的學(xué)習(xí)年限，每學(xué)年含兩學(xué)期，每學(xué)期的時間長度和學(xué)分上限值均相等。每個專業(yè)開設(shè)的課程都是確定的，而且課程在開設(shè)時間的安排必須滿足先修關(guān)系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課恰好占一個學(xué)期。編制一個教學(xué)計劃程序。

（二）實驗過程編程實現(xiàn)實驗內(nèi)容。

（三）實驗教學(xué)基本要求

通過實例，使學(xué)生熟悉圖的各種存儲結(jié)構(gòu)的特性，掌握如何應(yīng)用圖結(jié)構(gòu)解決具體問題。實驗后學(xué)生提交實驗報告。

（四）實驗設(shè)備和材料 計算機。

（五）實驗學(xué)時 2學(xué)時

實驗三

最小生成樹問題

（一）實驗內(nèi)容

利用克魯斯卡爾算法求最小生成樹。以文本形式輸出樹中各條邊以及他們的權(quán)值。

（二）實驗過程 編程實現(xiàn)實驗內(nèi)容

（三）實驗教學(xué)基本要求

通過實例，使學(xué)生熟悉圖的各種存儲結(jié)構(gòu)的特性，掌握如何應(yīng)用圖結(jié)構(gòu)解決具體問題。實驗后學(xué)生提交實驗報告。

（四）實驗設(shè)備和材料 計算機。

（五）實驗學(xué)時 2學(xué)時

實驗四

哈希表設(shè)計

（一）實驗內(nèi)容

假設(shè)人名為中國人的漢語拼音形式。待填入哈希表的人名共有30個，取平均查找長度的上限為2。哈希函數(shù)用除留余數(shù)法構(gòu)造，用偽隨機探測再散列法處理沖突。

（二）實驗過程 編程實現(xiàn)實驗內(nèi)容

（三）實驗教學(xué)基本要求 掌握索引技術(shù)的使用。

（四）實驗設(shè)備和材料 計算機

（五）實驗學(xué)時 4學(xué)時

五、課程教學(xué)的基本要求和主要環(huán)節(jié)

本課程可采用課堂講授、課堂討論、習(xí)題課等進(jìn)行課堂教學(xué);條件允許可采用CAI、電子教案、幻燈片、參觀等進(jìn)行輔助教學(xué);每章布置3~6道習(xí)題以鞏固教學(xué);在課程后半程，安排3~4個上機實驗，讓學(xué)生應(yīng)用數(shù)據(jù)結(jié)構(gòu)的理論、方法，分組設(shè)計幾個較大的軟件，使理論與實際相結(jié)合。

考試采用閉卷方式?？偝煽冇善綍r成績和考試成績組成。平時成績占30%，考試成績占70%。

六、本課程與其它課程的聯(lián)系與分工

先修課包括：集合論，圖論，高級語言（結(jié)構(gòu)或記錄，指針）；

后續(xù)課包括：數(shù)據(jù)庫，編譯原理，操作系統(tǒng)等。

七、建議教材與參考教材

《數(shù)據(jù)結(jié)構(gòu)》（C語言版）

嚴(yán)蔚敏等

清華大學(xué)出版社

1997 《數(shù)據(jù)結(jié)構(gòu)題集》

嚴(yán)蔚敏等

清華大學(xué)出版社

1999

《數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析》

李春葆

清華大學(xué)出版社

2004

八、負(fù)責(zé)人

撰稿人：劉景匯、李玉香

審稿人：

系（院）領(lǐng)導(dǎo)：

第二篇：《數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)大綱

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

Data Structure 執(zhí)筆人：

編寫日期：

一、課程基本信息

1.課程編號：

2.課程性質(zhì)/類別： 必修課 / 專業(yè)主干課

3.學(xué)時/學(xué)分： 48 學(xué)時（另實驗16學(xué)時）/ 4 學(xué)分

4.適用專業(yè)：計算機科學(xué)與技術(shù)、軟件工程、網(wǎng)絡(luò)工程、信息管理與信息系統(tǒng)等專業(yè)

二、課程教學(xué)目標(biāo)及學(xué)生應(yīng)達(dá)到的能力

數(shù)據(jù)結(jié)構(gòu)課程是計算機相關(guān)專業(yè)的專業(yè)基礎(chǔ)課、必修課程，主要介紹用計算機解決一系列問題特別是非數(shù)值信息處理問題時所用的各種組織數(shù)據(jù)的方法、存儲數(shù)據(jù)結(jié)構(gòu)的方法以及在各種結(jié)構(gòu)上執(zhí)行操作的算法。通過本課程的學(xué)習(xí)，要求學(xué)生掌握各種數(shù)據(jù)結(jié)構(gòu)的特點、存儲表示、運算方法以及在計算機科學(xué)中最基本的應(yīng)用，培養(yǎng)、訓(xùn)練學(xué)生選用合適的數(shù)據(jù)結(jié)構(gòu)和編寫質(zhì)量高、風(fēng)格好的應(yīng)用程序的能力，培養(yǎng)學(xué)生分析問題、解決問題的能力，并為后續(xù)課程的學(xué)習(xí)打下良好的理論基礎(chǔ)和實踐基礎(chǔ)。

三、課程教學(xué)內(nèi)容與基本要求

（一）緒論（3 學(xué)時）1．主要內(nèi)容：

（1）介紹什么是數(shù)據(jù)結(jié)構(gòu)；

（2）基本概念和術(shù)語: 數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象，以及數(shù)據(jù)結(jié)構(gòu)的定義、邏輯結(jié)構(gòu)、物理結(jié)構(gòu)（理解）數(shù)據(jù)類型、抽象數(shù)據(jù)類型；

（3）抽象數(shù)據(jù)類型的表示與實現(xiàn)；

（4）算法和算法分析: 算法的概念、算法設(shè)計的要求以及算法效率的度量。2．基本要求

（1）了解學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的重要性；

（2）掌握數(shù)據(jù)結(jié)構(gòu)的定義及相關(guān)概念和術(shù)語；（3）了解抽象數(shù)據(jù)類型的定義、表示與實現(xiàn)方法；（4）理解算法的概念、特點并掌握度量其效率的基本方法。3．自學(xué)內(nèi)容：

類C語言的書寫規(guī)范。

（二）線性表（6 學(xué)時）1．主要內(nèi)容：

（1）線性表的抽象數(shù)據(jù)類型定義和相關(guān)概念：數(shù)據(jù)項、記錄、文件等；（2）線性表順序存儲表示和基本操作的實現(xiàn)；（3）線性表的鏈?zhǔn)酱鎯Ρ硎竞突静僮鞯膶崿F(xiàn)；

（4）稀疏多項式的抽象數(shù)據(jù)類型定義、表示和加法的實現(xiàn)。2．基本要求

（1）掌握線性表的定義和特點；

（2）熟練掌握線性表的順序存儲表示和插入、刪除、查找等實現(xiàn)算法；

（3）熟練掌握單鏈表、循環(huán)鏈表、雙向鏈表三種鏈表的表示，以及單鏈表的查找、插入、刪除、創(chuàng)建等實現(xiàn)算法。

3．自學(xué)內(nèi)容：

靜態(tài)鏈表。

（三）棧和隊列（5 學(xué)時）1．主要內(nèi)容：

（1）棧和隊列的結(jié)構(gòu)特性和抽象數(shù)據(jù)類型定義；（2）棧和隊列的順序存儲表示和實現(xiàn)；（3）棧和隊列的鏈?zhǔn)酱鎯Ρ硎竞蛯崿F(xiàn)；（4）棧和隊列在程序設(shè)計中的應(yīng)用。2．基本要求

（1）掌握棧和隊列兩種抽象數(shù)據(jù)類型的特點；

（2）掌握棧的兩種存儲表示和實現(xiàn)，特別注意棧滿?？盏臈l件；（3）掌握隊列的兩種存儲表示和實現(xiàn)，特別注意隊滿隊空的條件；（4）了解遞歸算法與棧的關(guān)系。3．自學(xué)內(nèi)容：

鏈棧，離散事件模擬

（四）串（3 學(xué)時）1．主要內(nèi)容：

（1）串的抽象數(shù)據(jù)類型定義；

（2）串的表示和實現(xiàn): 定長順序存儲結(jié)構(gòu)和堆分配存儲結(jié)構(gòu)；（3）串的各種基本操作的實現(xiàn)及其應(yīng)用；（4）串的模式匹配操作。2．基本要求

（1）熟悉串的一些基本操作的定義，并能利用基本操作實現(xiàn)串的其它操作；（2）掌握串的定長順序存儲結(jié)構(gòu)以及基本操作的實現(xiàn)；（3）掌握串的堆分配存儲結(jié)構(gòu)以及基本操作的實現(xiàn)；（4）掌握串的簡單模式匹配算法，理解KMP算法。3．自學(xué)內(nèi)容：

串操作的應(yīng)用實例。

（五）數(shù)組和廣義表（4 學(xué)時）1．主要內(nèi)容：

（1）數(shù)組的抽象數(shù)據(jù)類型定義及其順序表示和實現(xiàn)；（2）特殊矩陣和稀疏矩陣的壓縮存儲；（3）廣義表的抽象數(shù)據(jù)類型定義和存儲結(jié)構(gòu)。2．基本要求

（1）了解數(shù)組的兩種存儲表示方法，并掌握數(shù)組在以行為主的存儲結(jié)構(gòu)中的地址計算方法；（2）掌握對特殊矩陣進(jìn)行壓縮存儲時的下標(biāo)變換公式；

（3）熟悉稀疏矩陣的三元組順序表存儲結(jié)構(gòu)下的一般轉(zhuǎn)置和快速轉(zhuǎn)置算法；了解十字鏈表等存儲結(jié)構(gòu)；

（4）掌握廣義表的結(jié)構(gòu)特點、取表頭表尾操作，及其存儲表示方法。3．自學(xué)內(nèi)容：

采用十字鏈表存儲結(jié)構(gòu)創(chuàng)建稀疏矩陣。

（六）樹和二叉樹（10 學(xué)時）1．主要內(nèi)容：

（1）樹的抽象數(shù)據(jù)類型定義和基本術(shù)語；

（2）二叉樹的抽象數(shù)據(jù)類型定義、性質(zhì)和存儲結(jié)構(gòu)；（3）二叉樹的遍歷；

（4）線索二叉樹的定義、遍歷及線索化二叉樹；

（5）樹的存儲結(jié)構(gòu)、樹和森林的遍歷以及與二叉樹的轉(zhuǎn)換；（6）Huffman樹及其應(yīng)用。2．基本要求

（1）掌握樹型結(jié)構(gòu)的特點和基本術(shù)語；

（2）熟練掌握二叉樹的性質(zhì)，了解相應(yīng)的證明方法；

（3）了解二叉樹的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，熟練掌握二叉鏈表存儲結(jié)構(gòu)；（4）熟練掌握二叉樹三種遍歷的遞歸算法和中序遍歷非遞歸算法，能靈活運用遍歷算法實現(xiàn)二叉樹的其他操作；

（5）熟練掌握二叉樹的線索化過程，以及在中序線索二叉樹上找結(jié)點的前驅(qū)與后繼的方法；

（6）熟悉樹的各種存儲結(jié)構(gòu)及其特點，掌握樹和森林與二叉樹的轉(zhuǎn)換方法；（7）了解Huffman樹的特性，掌握建立Huffman樹和Huffman編碼的方法。3．自學(xué)內(nèi)容：

先序、后序遍歷二叉樹非遞歸算法，層次遍歷二叉樹算法。

（七）圖（9 學(xué)時）1．主要內(nèi)容：（1）圖的定義和術(shù)語；

（2）圖的四種存儲結(jié)構(gòu)：數(shù)組表示法（鄰接矩陣）、鄰接表、十字鏈表和鄰接多重表；（3）圖的兩種遍歷策略：深度優(yōu)先遍歷和廣度優(yōu)先遍歷；（4）圖的連通性和最小生成樹；

（5）有向無環(huán)圖及其應(yīng)用：拓?fù)渑判蚝完P(guān)鍵路徑；（6）最短路徑問題。2．基本要求

（1）熟悉圖的定義和術(shù)語；

（2）了解圖的存儲結(jié)構(gòu)，熟練掌握數(shù)組表示法（鄰接矩陣）和鄰接表存儲表示；（3）熟練掌握圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷算法；（4）掌握無向連通帶權(quán)圖的最小生成樹求解算法；

（5）了解有向無環(huán)圖、AOV網(wǎng)、AOE網(wǎng)及其在實際中的應(yīng)用，熟悉拓?fù)渑判蛩惴ê完P(guān)鍵路徑算法；

（6）熟悉兩種最短路徑問題求解算法。3．自學(xué)內(nèi)容：

樹的先根遍歷算法與圖的深度優(yōu)先遍歷算法比較；

樹的層次遍歷算法與圖的廣度優(yōu)先遍歷算法比較。

（八）查找（4 學(xué)時）1．主要內(nèi)容：

（1）查找的基本概念和相關(guān)術(shù)語；

（2）靜態(tài)查找表：順序查找、折半查找和索引順序表查找；（3）動態(tài)查找表：二叉排序樹的查找、插入和刪除；（4）哈希表。2．基本要求

（1）了解查找的作用，熟悉相關(guān)術(shù)語；

（2）熟練掌握順序查找、折半查找和索引順序表查找；（3）熟練掌握二叉排序樹的特性、構(gòu)造和查找方法；

（4）熟練掌握哈希表的構(gòu)造方法，特別是哈希函數(shù)和處理沖突方法的選取；（5）通過分析等概率下的平均查找長度來衡量各種查找方法的效率。3．自學(xué)內(nèi)容：

平衡二叉樹。

（九）內(nèi)部排序（4 學(xué)時）1．主要內(nèi)容：

（1）排序的基本概念和相關(guān)術(shù)語；

（2）插入排序：直接插入排序、折半插入排序和希爾排序；（3）交換排序：起泡排序和快速排序；（4）選擇排序：簡單選擇排序和堆排序；（5）歸并排序：二路歸并排序；（6）基數(shù)排序：鏈?zhǔn)交鶖?shù)排序；（7）各種內(nèi)部排序方法的比較討論。2．基本要求

（1）了解排序作用，熟悉相關(guān)術(shù)語；

（2）掌握多種排序的基本思想、算法特點和排序過程，分析它們的時間復(fù)雜度、空間復(fù)雜度和穩(wěn)定性。

3．自學(xué)內(nèi)容：

二路插入排序、表插入排序和樹形選擇排序。

四、教學(xué)安排建議

1.作業(yè)練習(xí) 完成每章的教學(xué)后進(jìn)行布置習(xí)題，使用教材配套的《數(shù)據(jù)結(jié)構(gòu)題集（C語言版）》。盡量選擇基礎(chǔ)的并且加注了標(biāo)記的題，應(yīng)注重于精，而不要求多。要求積極獨立完成所布置的習(xí)題，建議安排至少六次。

2.案例分析

可參考選擇以下一些案例：（1）學(xué)生通訊錄管理系統(tǒng)，（2）表達(dá)式求值問題（3）交通咨詢系統(tǒng)，等。3.專題研討

可參考選擇以下一些：（1）最小生成樹問題（2）航班信息查詢與檢索系統(tǒng)，（3）內(nèi)部排序算法比較，等。

4.實驗安排

為了達(dá)到理論與實際應(yīng)用的結(jié)合，讓學(xué)生能將所學(xué)知識應(yīng)用于實際問題的求解中，培養(yǎng)學(xué)生的實際動手能力，從而加深對概念及所學(xué)知識的理解，靈活、牢固掌握教材內(nèi)容，提高程序設(shè)計及解決實際問題的能力，實驗環(huán)節(jié)的安排非常重要。

建議實驗安排為八次，共16學(xué)時，分別如下：

實驗1 線性表的順序存儲結(jié)構(gòu)的實現(xiàn)(2學(xué)時)

實驗2 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)的實現(xiàn)(2學(xué)時)

實驗3 棧的算法實現(xiàn)(2學(xué)時)

實驗4 隊列的算法實現(xiàn)(2學(xué)時)

實驗5 串類型及操作(2學(xué)時)

實驗6 二叉樹的建立與遍歷(2學(xué)時)

實驗7 圖的建立與遍歷(2學(xué)時)

實驗8 查找與排序(2學(xué)時)注：教師可根據(jù)教學(xué)實際情況（如：學(xué)生情況及學(xué)時情況等），適當(dāng)調(diào)整實踐教學(xué)內(nèi)容及學(xué)時分配。

五、課程考核

1.考核形式及成績評定辦法

本課程考核形式為：平時成績占40%，期末考試成績占60%。其中平時成績的結(jié)構(gòu)分包括：課堂表現(xiàn)10%、平時作業(yè)10%和實驗20%，期末考試為閉卷筆試考試：120分鐘，卷面分滿分100分。期末考試成績低于50分者，本課程成績按不及格論處。

2.本課程考核的基本要求

課堂表現(xiàn)10%：包括課堂考勤和課堂提問，如果缺課課時達(dá)到本課程教學(xué)時數(shù)的1/3，則取消考試資格。

平時作業(yè)10%：根據(jù)上交次數(shù)及完成情況進(jìn)行評定。

實驗20%：根據(jù)各次實驗完成情況及實驗報告成績進(jìn)行評定。

期末考試60%：本課程的期末考試考核內(nèi)容主要包括線性表、棧與隊列、串、數(shù)組與廣義表、樹與二叉樹、圖、查找和內(nèi)部排序。其中，線性表、二叉樹、圖、查找和內(nèi)部排序內(nèi)容為考核的重點。

六、本課程與其它課程的先行后續(xù)關(guān)系

先行課程：《高級程序設(shè)計語言》、《離散數(shù)學(xué)》

后續(xù)課程：《操作系統(tǒng)》、《編譯原理》、《數(shù)據(jù)庫理論》、《算法分析與設(shè)計》等

七、建議教材及教學(xué)參考書

1.教材：

嚴(yán)蔚敏，吳偉民編著，《數(shù)據(jù)結(jié)構(gòu)（C語言版）》，清華大學(xué)出版，2012.5 嚴(yán)蔚敏，吳偉民編著，《數(shù)據(jù)結(jié)構(gòu)題集（C語言版）》，清華大學(xué)出版，2012.5 2.參考書：

[1] 許卓群，張乃孝，楊冬青，唐世渭，《數(shù)據(jù)結(jié)構(gòu)》，高等教育出版社，2004.[2] 徐孝凱，《數(shù)據(jù)結(jié)構(gòu)簡明教程》，清華大學(xué)出版社，1995 [3] 陳文博，朱青，《數(shù)據(jù)結(jié)構(gòu)與算法》，機械工業(yè)出版社，1996 [4] 李云清，楊慶紅，揭安全編著，《數(shù)據(jù)結(jié)構(gòu)》（C語言版），人民郵電出版社，2007.[5] 楊秀金主編，《數(shù)據(jù)結(jié)構(gòu)》，西安電子科技大學(xué)出版社，2002.[6] 李廉治，姜文清，郭福順，《數(shù)據(jù)結(jié)構(gòu)》，大連理工大學(xué)出版社，1989

[7] Aho A V, Hopcroft J E, Ullman J D.Data Structures and Algorithms.Addison-Wesley Publishing Company,Inc.,1983

[8] Baron R J, Shapiro L G.Data Structures and their Implementation.Van Nostrand Reinhold Company, 1980

[9] Esakov J, Weiss T.Data Structures: An Advanced Approach Using C.Prentice-Hall, Inc.,1989

[10] [美]S巴斯《計算機算法：設(shè)計和分析引論》朱洪等譯，復(fù)旦大學(xué)出版社，1985

第三篇：《數(shù)據(jù)結(jié)構(gòu) A》課程教學(xué)大綱

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

Data Structure A

課程代碼：

適用專業(yè)：信息計算、信息安全 總學(xué)時數(shù)：72

編寫年月：2003年7月

執(zhí)

筆：高學(xué)軍、劉科峰、李小英



一、課程的性質(zhì)和目的

數(shù)據(jù)結(jié)構(gòu)是信息與計算科學(xué)專業(yè)的一門重要專業(yè)基礎(chǔ)課程。當(dāng)用計算機來解決實際問題時，就要涉及到數(shù)據(jù)的表示及數(shù)據(jù)的處理，而數(shù)據(jù)表示及數(shù)據(jù)處理正是數(shù)據(jù)結(jié)構(gòu)課程的主要研究對象，通過這兩方面內(nèi)容的學(xué)習(xí)，為后續(xù)課程，特別是軟件方面的課程打下了厚實的知識基礎(chǔ)，同時也提供了必要的技能訓(xùn)練。因此，數(shù)據(jù)結(jié)構(gòu)課程在信息與計算科學(xué)專業(yè)中具有舉足輕重的作用。

課程性質(zhì)：專業(yè)基礎(chǔ)理論課/必修 開課學(xué)期：5 總學(xué)分?jǐn)?shù)：4.5 修訂年月：2007年7月

二、課程教學(xué)內(nèi)容及學(xué)時分配

第1章 緒論（4學(xué)時）

理解數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項的概念及其相互間的關(guān)系。理解數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)的聯(lián)系與區(qū)別，以及在數(shù)據(jù)結(jié)構(gòu)上施加的運算及其實現(xiàn)。掌握簡單的算法分析方法。

本章知識點為：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)類型等概念術(shù)語的確定含義；抽象數(shù)據(jù)類型的定義、表示和實現(xiàn)方法；描述算法的類C語言；算法設(shè)計的基本要求以及從時間和空間角度分析算法的方法。

第2章 線性表（10學(xué)時，2個學(xué)時實驗上機）

理解線性表的定義及其運算。理解順序表和鏈表的定義、組織形式、結(jié)構(gòu)特征和類型說明，掌握在這兩種表上實現(xiàn)的插入、刪除和按值查找的算法。了解循環(huán)鏈表、雙向(循環(huán))鏈表的結(jié)構(gòu)特點和在其上施加的插入、刪除等操作。掌握稀疏多項式在線性表的兩種存儲結(jié)構(gòu)上的實現(xiàn)方法。

本章知識點為：線性表的邏輯結(jié)構(gòu)定義、抽象數(shù)據(jù)類型定義和各種存儲結(jié)構(gòu)的描述方法；在線性表的兩類存儲結(jié)構(gòu)(順序的和鏈?zhǔn)降?上實現(xiàn)基本操作；稀疏多項式的抽象數(shù)據(jù)類型定義、表示和加法的實現(xiàn)。

第3章 棧和隊列（6學(xué)時，2個學(xué)時實驗上機）

理解棧和隊列的定義、特征及在其上所定義的基本運算。掌握在兩種存儲結(jié)構(gòu)上對棧和隊列所施加的基本運算的實現(xiàn)。熟練掌握循環(huán)隊列和鏈隊列的基本操作實現(xiàn)算法，尤其是隊滿和隊空的描述方法。

本章知識點為：抽象數(shù)據(jù)類型棧的定義；棧的表示和實現(xiàn)；棧的應(yīng)用；抽象數(shù)據(jù)類型隊列的定義；鏈隊列；循環(huán)隊列。第4章 串（4學(xué)時，2個學(xué)時實驗上機）

熟悉串的七種基本操作的定義，并能利用這些基本操作來實現(xiàn)串的其它各種操作的方法。熟練掌握在串的定長順序存儲結(jié)構(gòu)上實現(xiàn)串的各種操作的方法。掌握串的堆存儲結(jié)構(gòu)以及在其上實現(xiàn)串操作的基本方法。

本章知識點為：串的數(shù)據(jù)類型定義；串的三種存儲表示：定長順序存儲結(jié)構(gòu)、塊鏈存儲結(jié)構(gòu)和堆分配存儲結(jié)構(gòu)；串的各種基本操作的實現(xiàn)及其應(yīng)用；

第5章 數(shù)組和廣義表（6學(xué)時，2個學(xué)時實驗上機）

了解數(shù)組的兩種存儲表示方法，并掌握數(shù)組在以行為主的存儲結(jié)構(gòu)中的地址計算方法。掌握對特殊矩陣進(jìn)行壓縮存儲時的下標(biāo)變換公式。了解稀疏矩陣的兩種壓縮存儲方法的特點和適用范圍，領(lǐng)會以三元組表示稀疏矩陣時進(jìn)行矩陣運算采用的處理方法。掌握廣義表的結(jié)構(gòu)特點及其存儲表示方法。

本章知識點為：數(shù)組的類型定義和表示方式；特殊矩陣和稀疏矩陣的壓縮存儲方法及運算的實現(xiàn)；廣義表的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)和廣義表的操作。

第6章 樹和二叉樹（12學(xué)時，2個學(xué)時實驗上機）

深刻理解樹的定義、性質(zhì)及其存儲方法，熟練掌握二叉樹的二叉鏈表存儲方式、結(jié)點結(jié)構(gòu)和類型定義，并能畫出給定二叉樹的二叉鏈表的結(jié)構(gòu)示意圖；理解并掌握二叉樹的三種遍歷方法，并能寫出該三種遍歷的算法；會完成樹、森林與二叉樹間的相互轉(zhuǎn)換；理解哈夫曼樹的構(gòu)造方法，并能對給定的數(shù)據(jù)集合構(gòu)造出哈夫曼樹。

本章知識點為：二叉樹的定義、性質(zhì)和存儲結(jié)構(gòu)；二叉樹的遍歷和線索化以及遍歷算法的各種描述形式；樹和森林的定義、存儲結(jié)構(gòu)、與二叉樹的轉(zhuǎn)換、遍歷；樹的多種應(yīng)用。

第7章 圖（12學(xué)時，2個學(xué)時實驗上機）

理解圖的基本概念及術(shù)語，掌握圖的兩種存儲結(jié)構(gòu)(鄰接矩陣和鄰接表)的表示方法；熟練掌握圖的兩種遍歷(深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷)的算法思想、步驟，并能列出在兩種存儲結(jié)構(gòu)上按上述兩種遍歷算法得到的序列；理解最小生成樹的概念，能按Prim算法構(gòu)造最小生成樹；了解并掌握拓?fù)渑判?、關(guān)鍵路徑、最短路徑的算法思想。

本章知識點為：圖的定義和術(shù)語；圖的四種存儲結(jié)構(gòu)：數(shù)組表示法、鄰接表、十字鏈表和鄰接多重表；圖的兩種遍歷策略：深度優(yōu)先搜索和廣度優(yōu)先搜索；圖的連通性：連通分量和最小生成樹；拓?fù)渑判蚝完P(guān)鍵路徑；兩類求最短路徑問題的解法。

第8章 查找（10學(xué)時，2個學(xué)時實驗上機）

了解查找的基本思想及查找成功和不成功的概念，掌握在順序表、有序表、索引表、散列表等上的查找方法和算法，并能求出相應(yīng)的平均查找長度。

本章知識點為：討論查找表(包括靜態(tài)查找表和動態(tài)查找表)的各種實現(xiàn)方法：順序表、有序表、樹表和哈希表；平均查找長度的討論。

第9章 內(nèi)部排序（8學(xué)時，2個學(xué)時實驗上機）了解排序的基本思想和基本概念，理解和掌握插入排序、冒泡排序、快速排序、直接選擇排序、堆排序、歸并排序和基數(shù)排序的基本思想、步驟及算法。

本章知識點為：討論比較各種內(nèi)部排序方法，插入排序、交換排序、選擇排序、歸并排序和基數(shù)排序的基本思想、算法特點、排序過程以及它們的時間復(fù)雜度分析。在每類排序方法中，又從簡單方法入手，重點討論性能先進(jìn)的高效方法。

三、課程教學(xué)的基本要求

本課程是信息與計算科學(xué)專業(yè)的重要專業(yè)基礎(chǔ)課，計算機科學(xué)各領(lǐng)域及有關(guān)的系統(tǒng)和應(yīng)用軟件都要用到各種數(shù)據(jù)結(jié)構(gòu)。在教學(xué)方法上采用課堂講授，課后自學(xué)，課堂討論等教學(xué)形式。

(一)課堂講授

本課程屬于基礎(chǔ)理論課程。在傳授知識原理的前提下，配合實際應(yīng)用例子，由淺入深善于誘導(dǎo)，使學(xué)生從被動吸收知識的狀態(tài)下，轉(zhuǎn)化到主動索取知識的狀態(tài)中來，并采用多媒體輔助教學(xué)，加大課堂授課的知識含量。注重培養(yǎng)學(xué)生的學(xué)習(xí)興趣，提高學(xué)生的基本素質(zhì)。

（二）課后自學(xué)

為了培養(yǎng)學(xué)生整理歸納，綜合分析和處理問題的能力，每章都安排一部分內(nèi)容，課上教師只給出自學(xué)提綱，不作詳細(xì)講解，課后學(xué)生自學(xué)。

（三）課堂討論

課堂討論的目的是活躍學(xué)習(xí)氣氛，開拓思路。教師應(yīng)認(rèn)真組織，安排重點發(fā)言，充分調(diào)動每一名同學(xué)的學(xué)習(xí)積極性，做好總結(jié)。

（四）課外作業(yè)

為了讓學(xué)生鞏固所學(xué)的知識，每章都布置一定數(shù)量課外作業(yè)。

（五）實驗

用C語言或C++語言完成一些算法設(shè)計題。培養(yǎng)學(xué)生的算法設(shè)計能力和程序設(shè)計能力?？傇u成績：平時作業(yè)占30%，閉卷考試占70%。

四、本課程與其它課程的聯(lián)系與分工

先修課程：離散數(shù)學(xué)，C++面向?qū)ο蟪绦蛟O(shè)計等。后續(xù)課程：操作系統(tǒng)，數(shù)據(jù)庫原理等。

五、建議教材與教學(xué)參考書

[1] 嚴(yán)蔚敏 吳偉民編著，數(shù)據(jù)結(jié)構(gòu)(C語言版)，北京:清華大學(xué)出版社, 2004 [2] 嚴(yán)蔚敏 吳偉民編著，數(shù)據(jù)結(jié)構(gòu)題集(C語言版)，北京:清華大學(xué)出社，2004 [3] Willan Ford,Willian Topp.Data Structures with C++.New Jersey:Prentice Hall Inc, Adivision Simon & Schuster Company，1996(數(shù)據(jù)結(jié)構(gòu)——C++語言描述.北京:清華大學(xué)出版社，1997)

[4] 徐孝凱，數(shù)據(jù)結(jié)構(gòu)實用教程（C/C++描述），北京:清華大學(xué)出版社，1999 [5] 陳慧南.數(shù)據(jù)結(jié)構(gòu)（使用C++語言描述），南京:東南大學(xué)出版社，2001 [6] 殷人昆,陶永雷,謝若陽等.數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC++描述），北京:清華大學(xué)出版社，1999

第四篇：數(shù)據(jù)結(jié)構(gòu)與算法課程教學(xué)大綱

教學(xué)大綱

數(shù)據(jù)結(jié)構(gòu)與算法（Data Structures）

計算機技術(shù)已成為現(xiàn)代化發(fā)展的重要支柱和標(biāo)志，并逐步滲透到人類生活的各個領(lǐng)域。隨著計算機硬件的發(fā)展，對計算機軟件的發(fā)展也提出了越來越高的要求。由于軟件的核心是算法，而算法實際上是對加工數(shù)據(jù)過程的描述，所以研究數(shù)據(jù)結(jié)構(gòu)對提高編程能力和設(shè)計高性能的算法是至關(guān)重要的。

非數(shù)值計算問題的數(shù)學(xué)模型不再是傳統(tǒng)的數(shù)學(xué)方程問題，而是諸如表、樹、圖之類的數(shù)據(jù)結(jié)構(gòu)。因此，簡單地說，數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題的學(xué)科，主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和算法。

一、教學(xué)目的與要求---了解數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)；

教學(xué)要求在每章教學(xué)內(nèi)容給出，大體上為三個層次：了解、掌握和熟練掌握。他們的含義大致為：了解是正確理解概念，掌握是學(xué)會所學(xué)知識，熟練掌握就是運用所學(xué)知識解決實際問題。

教學(xué)目的為：了解算法對于程序設(shè)計的重要性 ； 學(xué)習(xí)掌握基本數(shù)據(jù)結(jié)構(gòu)的描述與實現(xiàn)方法，熟練掌握典型數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用算法的設(shè)計。了解算法分析方法。

二、教學(xué)重點與難點--數(shù)據(jù)結(jié)構(gòu)中基本概念和術(shù)語，算法描述和分析方法。

1、鏈表插入、刪除運算的算法。算法時間復(fù)雜度

2、后綴表達(dá)式的算法，數(shù)制的換算

利用本章的基本知識設(shè)計相關(guān)的應(yīng)用問題

3、循環(huán)隊列的特點及判斷溢出的條件

利用隊列的特點設(shè)計相關(guān)的應(yīng)用問題

4、串的模式匹配運算算法

5、二叉樹遍歷算法的設(shè)計

利用二叉樹遍歷算法，解決簡單應(yīng)用問題 哈夫曼樹的算法

6、圖的遍歷

最小生成樹

最短路徑

7、二叉排序樹查找

平衡樹二叉樹

8、堆排序

快速排序 歸并排序

三、教學(xué)方法與手段-充分利用多媒體教學(xué)工具，配合黑板上的教學(xué)內(nèi)容較難部分的算法實現(xiàn)過程演義

四、教學(xué)內(nèi)容、目標(biāo)與學(xué)時分配

教學(xué)內(nèi)容 教學(xué)目標(biāo) 課時分配

1、緒論

數(shù)據(jù)結(jié)構(gòu)的內(nèi)容

邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)

算法和算法分析

2、線性表

線性表的定義與運算

線性表的順序存儲

線性表的鏈?zhǔn)酱鎯?/p>

3、棧

棧的定義與運算

棧存儲和實現(xiàn)

棧的應(yīng)用舉例

4、隊列

隊列的定義與基本運算

隊列的存儲與實現(xiàn)

隊列的應(yīng)用舉例

5、串

串的定義與基本運算

串的表示與實現(xiàn)

串的基本運算

6、樹和二叉樹

樹的定義和術(shù)語

二叉樹樹的基本概念和術(shù)語 遍歷二叉數(shù)和線索二叉樹

二叉樹的轉(zhuǎn)換

二叉樹的應(yīng)用

哈夫曼樹及其應(yīng)用

7、圖

圖的定義和術(shù)語

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

圖的遍歷算法

圖的連通性

8、查找

查找的基本概念與靜態(tài)查找 動態(tài)查找

哈希表

了解

了解

掌握

熟練掌握順序表存儲地址的計算

掌握單鏈表的結(jié)構(gòu)特點和基本運算

掌握雙鏈表的結(jié)構(gòu)特點和基本運算

掌握棧的定義與運算

掌握棧的存儲與實現(xiàn)

熟練掌握棧的各種實際應(yīng)用

掌握隊列的定義與基本運算

熟練掌握隊列的存儲與實現(xiàn)

掌握循環(huán)隊列的特征和基本運算

了解串的邏輯結(jié)構(gòu)

掌握串的存儲結(jié)構(gòu)

熟練掌握串的基本運算

了解

了解二叉樹

熟練掌握二叉樹定義和存儲結(jié)構(gòu)

了解二叉樹的遍歷算法

掌握

掌握哈夫曼的建立及編碼

了解

了解

熟練掌握

熟練掌握

了解

熟練掌握

了解哈希表與哈希方法

4學(xué)時

1學(xué)時

1學(xué)時

2學(xué)時

8學(xué)時

2學(xué)時

2學(xué)時

4學(xué)時

8學(xué)時

2學(xué)時

2學(xué)時

4學(xué)時

6學(xué)時

2學(xué)時

2學(xué)時

2學(xué)時

6學(xué)時

2學(xué)時

2學(xué)時

2學(xué)時

12學(xué)時

2學(xué)時

2學(xué)時

2學(xué)時

2學(xué)時

2學(xué)時

2學(xué)時

8學(xué)時

2學(xué)時

2學(xué)時

2學(xué)時

2學(xué)時

8學(xué)時

4學(xué)時

2學(xué)時

2學(xué)時

9、排序

12學(xué)時 插入排序

熟練掌握基本思想

3學(xué)時 快速排序

了解各種內(nèi)部排序方法和特點

3學(xué)時 選擇排序

掌握

2學(xué)時 各種排序方法比較

掌握

2學(xué)時

實驗內(nèi)容 實驗?zāi)繕?biāo) 課時分配 算法編程實驗：

1、用指針方式編寫程序 復(fù)習(xí)C（C++）語言指針、結(jié)構(gòu)體等的用法

2、對單鏈表進(jìn)行遍歷

鏈表的描述與操作實現(xiàn)

3、棧及其操作

描述方法及操作

4、編寫串子系統(tǒng)1 串的特點及順序定長存儲、操作、查找

5、編寫串子系統(tǒng) 2 串的特點及順序定長存儲、操作、查找

6、編寫樹子系統(tǒng)1 二叉樹的特點及存儲方式、創(chuàng)建、顯示、遍歷等

7、編寫樹子系統(tǒng)2 二叉樹的特點及存儲方式、創(chuàng)建、顯示、遍歷等

8、圖子系統(tǒng)

圖的鄰接矩陣的存儲、遍歷、廣度/深度優(yōu)先搜索

9、查找子系統(tǒng)

理解查找基本算法、平均查找長度、靜態(tài)、動態(tài)查找等

五、考試范圍與題型

1、考試范圍與分?jǐn)?shù)比例

1)緒論

12% 2)線性表

17% 3)棧

7% 4)隊列

6% 5)串

4% 6)樹和二叉樹

14% 7)圖

15% 8)查找

4% 9)排序

21%

2、考試題型與分?jǐn)?shù)比例

1)名詞解釋

18% 2)判斷對錯

16% 3)填空

16% 4)單項選擇

18% 5)應(yīng)用

32%

六、教材與參考資料

1、教材： 實用數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)（譚浩強）中國鐵道出版社

2、參考資料： 數(shù)據(jù)結(jié)構(gòu)（嚴(yán)蔚敏）清華大學(xué)出版社

數(shù)據(jù)結(jié)構(gòu)實用教程（徐孝凱）清華大學(xué)出版社

（撰寫人：

，審核人： 2學(xué)時 2學(xué)時 2學(xué)時 2學(xué)時 2學(xué)時 2學(xué)時 2學(xué)時 2學(xué)時 2學(xué)時）

第五篇：數(shù)據(jù)結(jié)構(gòu)教學(xué)大綱(參考)

數(shù)據(jù)結(jié)構(gòu) Data Structure 課程代碼：

學(xué) 時 數(shù)：64（講課50 實驗14 研討0 實習(xí)實踐1周）

學(xué) 分 數(shù)：

3、4 課程類別：學(xué)科基礎(chǔ)課

開課學(xué)期：4 主講教師：

編寫日期： 2011年7月1日

一、課程性質(zhì)和目的課程性質(zhì)：數(shù)據(jù)結(jié)構(gòu)A是計算機科學(xué)與技術(shù)、數(shù)字媒體藝術(shù)、信息管理與信息系統(tǒng)專業(yè)的一門重要學(xué)科基礎(chǔ)課，是必修課。

教學(xué)目的：通過本課程的學(xué)習(xí)，一方面，使學(xué)生學(xué)會分析研究計算機加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)及相應(yīng)的算法，并初步了解對算法的時間分析和空間分析技術(shù)。另一方面，通過對本課程算法設(shè)計和上機實踐的訓(xùn)練，還應(yīng)培養(yǎng)學(xué)生的數(shù)據(jù)抽象能力和程序設(shè)計的能力。

二、課程教學(xué)內(nèi)容、學(xué)時分配和課程教學(xué)基本要求

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

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

(1)數(shù)據(jù)結(jié)構(gòu)的一些基本概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)等。(2)抽象數(shù)據(jù)類型的表示和實現(xiàn)。(3)算法的概念和特性。

(4)算法時間復(fù)雜度和空間復(fù)雜度的分析?；疽螅?/p>

掌握數(shù)據(jù)結(jié)構(gòu)的基本概念，了解抽象數(shù)據(jù)類型，掌握算法時間復(fù)雜度和空間復(fù)雜度的分析方法。

2.線性表（理論8學(xué)時，實驗4學(xué)時）

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

(1)線性表的類型定義。(2)線性表的順序表示和實現(xiàn)。(3)線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)。

(4)線性表的應(yīng)用，包括無序表和有序表的合并、多項式的加法運算等。基本要求：

理解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著線性關(guān)系，在計算機中表示這種關(guān)系的兩類不同的存儲結(jié)構(gòu)是順序存儲結(jié)構(gòu)（順序表）和鏈?zhǔn)酱鎯Y(jié)構(gòu)（鏈表）。熟練掌握這兩類存儲結(jié)構(gòu)的描述方法，掌握鏈表中的頭結(jié)點、頭指針和首元結(jié)點的區(qū)別及循環(huán)鏈表、雙向鏈表的特點等。掌握順序表的查找、插入和刪除算法，掌握鏈表的查找、插入和刪除算法。能夠從時間和空間復(fù)雜度的角度比較兩種存儲結(jié)構(gòu)的不同特點及其適用場合。掌握無序表和有序表的合并算法，了解多項式的加法運算。

實驗：

實驗內(nèi)容：單鏈表的基本操作。實驗要求：以單鏈表形式創(chuàng)建一個學(xué)生表或圖書表，并能實現(xiàn)相關(guān)的查找、插入和刪除等算法。3.棧和隊列（理論6學(xué)時，實驗4學(xué)時）

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

(1)棧的類型定義，棧的順序存儲和鏈接存儲的表示和實現(xiàn)。(2)棧的應(yīng)用舉例，如迷宮求解和表達(dá)式求值。

(3)棧與遞歸的實現(xiàn)，遞歸程序轉(zhuǎn)換為非遞歸程序的方法。

(4)隊列的類型，隊列的順序存儲(循環(huán)隊)和鏈接存儲的表示和實現(xiàn)。(5)隊列的應(yīng)用舉例，如打印楊暉三角形，模擬汽車加油站等問題。基本要求：

掌握棧和隊列的特點，并能在相應(yīng)的應(yīng)用問題中正確選用。熟練掌握棧的順序棧和鏈棧的進(jìn)棧出棧算法，特別應(yīng)注意棧滿和?？盏臈l件。掌握利用棧實現(xiàn)表達(dá)式求值的算法，了解迷宮求解算法。理解遞歸算法執(zhí)行過程中棧的狀態(tài)變化過程，了解將遞歸程序轉(zhuǎn)換為非遞歸程序的方法。熟練掌握循環(huán)隊列和鏈隊列的進(jìn)隊出隊算法，特別是循環(huán)隊列中隊頭與隊尾指針的變化情況。了解隊列的應(yīng)用。

實驗：

實驗內(nèi)容：棧的應(yīng)用。實驗要求：借助棧來解決某些實際應(yīng)用問題，如表達(dá)式求值、迷宮問題等。

4.串、數(shù)組和廣義表（理論2學(xué)時）

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

(1)串的表示和實現(xiàn)，包括順序存儲和鏈?zhǔn)酱鎯Ρ硎?。古典的模式匹配算法?2)數(shù)組的存儲方法。

(3)特殊矩陣和稀疏矩陣的壓縮存儲，稀疏矩陣的轉(zhuǎn)置運算。(4)廣義表的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。基本要求：

了解串的順序存儲結(jié)構(gòu)和堆存儲結(jié)構(gòu)。掌握串的古典的模式匹配算法。掌握數(shù)組的地址計算方法。了解稀疏矩陣的兩種壓縮存儲方法的特點和適用范圍。了解廣義表的結(jié)構(gòu)特點及其存儲方法。5.樹和二叉樹（理論8學(xué)時，實驗2學(xué)時）

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

(1)二叉樹的定義和術(shù)語，二叉樹的性質(zhì)，特殊的二叉樹。(2)二叉樹的存儲結(jié)構(gòu)，順序存儲和二叉鏈表。

(3)二叉樹的的前序、中序、后序、層次遍歷方法。線索化二叉樹。(4)樹和森林的定義，樹的存儲，樹、森林與二叉樹的轉(zhuǎn)換。(5)樹的應(yīng)用，哈夫曼樹及哈夫曼編碼?；疽螅?/p>

了解樹和森林的概念，包括樹的定義、樹的術(shù)語。掌握二叉樹的概念、性質(zhì)及二叉樹的表示。熟練掌握二叉樹的遍歷算法，并且能靈活運用遍歷算法實現(xiàn)二叉樹的其他操作。掌握線索化二叉樹的特性及尋找某結(jié)點的前驅(qū)和后繼的方法。了解樹的存儲、樹和森林與二叉樹的轉(zhuǎn)換方法。掌握哈夫曼樹的實現(xiàn)方法、構(gòu)造哈夫曼編碼的方法及帶權(quán)路徑長度的計算。

實驗：

實驗內(nèi)容：二叉樹的基本算法。實驗要求：利用二叉鏈表方法建立二叉樹，實現(xiàn)二叉樹的前、中、后序三種遍歷算法，并運用遍歷算法實現(xiàn)二叉樹的其他操作，如計算二叉樹結(jié)點個數(shù)、葉子結(jié)點個數(shù)、二叉樹的高度等。6.圖（理論8學(xué)時，實驗2學(xué)時）

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

(1)圖的定義和術(shù)語。

(2)圖的存儲結(jié)構(gòu)兩種存儲結(jié)構(gòu)：鄰接矩陣和鄰接表表示法。(3)圖的兩種遍歷策略：深度優(yōu)先搜索和廣度優(yōu)先搜索。(4)構(gòu)造最小生成樹的兩種算法：普里姆算法和克魯斯卡爾算法。(5)拓?fù)渑判蚝完P(guān)鍵路徑。

(6)兩類求最短路徑問題的算法，迪杰斯特拉算法和弗洛伊德算法。基本要求：

掌握圖的基本概念及相關(guān)術(shù)語和性質(zhì)，掌握圖的鄰接矩陣和鄰接表表示法，了解實際問題的求解效率與采用何種存儲結(jié)構(gòu)和算法有密切聯(lián)系。熟練掌握圖的兩種搜索路徑的遍歷：深度優(yōu)先搜索和廣度優(yōu)先搜索的算法。掌握構(gòu)造最小生成樹的兩種算法及拓?fù)渑判蛩惴ǖ乃枷?，掌握迪杰斯特拉算法。了解關(guān)鍵路徑的概念和求解方法，了解弗洛伊德算法。

實驗：

實驗內(nèi)容：圖的建立和搜索。實驗要求：使用鄰接矩陣或鄰接表表示法存儲一個圖，實現(xiàn)圖的深度優(yōu)先搜索和廣度優(yōu)先搜索的算法。7.查找（理論6學(xué)時）

教學(xué)內(nèi)容：(1)查找的基本概念，平均查找長度。(2)基于線性表的查找：順序查找、折半查找。

(3)基于樹表的查找：二叉排序樹、平衡二叉樹、B-樹和B+樹。

(4)散列表：散列表的基本概念，散列函數(shù)的構(gòu)造方法、處理沖突的方法、散列表的查找與分析。

基本要求：

熟練掌握順序表和有序表的查找方法及其實現(xiàn)，掌握二叉排序樹的插入和查找算法及其實現(xiàn)，了解平衡二叉樹、B-樹和B+樹的各種操作。熟練掌握散列表的構(gòu)造方法、處理沖突的方法，深刻理散列表與其他結(jié)構(gòu)的表的實質(zhì)性的差別，了解各種散列函數(shù)的特點。掌握描述折半查找過程的判定樹的構(gòu)造方法，以及按定義計算各種查找方法在等概率情況下查找成功時的平均查找長度。

8.排序（理論8學(xué)時，實驗2學(xué)時）

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

(1)排序的基本概念，包括正序，逆序，穩(wěn)定性，排序方法的分類。(2)插入排序：直接插入排序、折半插入排序和希爾排序。(3)交換排序：冒泡排序和快速排序。(4)選擇排序：簡單選擇排序和堆排序。(5)歸并排序：2-路歸并排序。

(6)基數(shù)排序：多關(guān)鍵字的排序和鏈數(shù)基數(shù)排序。

(7)排序算法分析：各種排序算法的比較和移動次數(shù)，時間復(fù)雜度和空間復(fù)雜度的分析?；疽螅?/p>

明確排序的基本概念，排序方法的分類。深刻理解排序算法的過程、特點及其依據(jù)的原則，并能加以靈活應(yīng)用。掌握各種排序方法的時間和空間復(fù)雜度的分析方法。能從關(guān)鍵字間的比較次數(shù)和移動次數(shù)分析算法的平均情況和最壞情況的時間性能。理解排序方法“穩(wěn)定”或“不穩(wěn)定”的含義，弄清楚在什么情況下要求應(yīng)用的排序方法必須是穩(wěn)定的。快速排序、堆排序和歸并排序等高效排序方法是本章的學(xué)習(xí)重點和難點。

實驗：

實驗內(nèi)容：綜合性實驗。實驗要求：選取一個合適的數(shù)據(jù)結(jié)構(gòu)存儲數(shù)據(jù)，能對數(shù)據(jù)進(jìn)行插入、刪除，用不同查找算法進(jìn)行查找、用不同的排序算法進(jìn)行排序等。9.實習(xí)（1周）

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

(1)設(shè)計準(zhǔn)備：理解實習(xí)任務(wù)，明確相關(guān)算法，搜集可用資源，熟悉實習(xí)環(huán)境。(2)方案設(shè)計：完成設(shè)計目標(biāo)、設(shè)計路線的確定，并進(jìn)行模塊設(shè)計和任務(wù)分工。(3)代碼編寫：各模塊代碼編寫，模塊測試。(4)代碼測試：模塊組裝，整體測試。(5)設(shè)計報告：完成設(shè)計文檔，制作設(shè)計報告?；疽螅?/p>

能將數(shù)據(jù)結(jié)構(gòu)課程中所學(xué)的基本知識融會貫通，綜合運用所學(xué)的知識解決相關(guān)的實際問題，能夠把所學(xué)知識（包括算法和結(jié)構(gòu)）在計算機上用編程語言加以實現(xiàn)，并且能夠根據(jù)實際需求創(chuàng)建自己的數(shù)據(jù)結(jié)構(gòu)和實現(xiàn)自己的算法。

本課程的教學(xué)環(huán)節(jié)包括：課堂講授、實驗、實習(xí)、作業(yè)、答疑、小測驗等。其中，課堂講授以教師講授為主，授課時將電子教案和板書相結(jié)合，充分發(fā)揮各自的優(yōu)點。采用啟發(fā)式教學(xué)，鼓勵學(xué)生自學(xué)，培養(yǎng)學(xué)生的自學(xué)能力，以“少而精”為原則，精選教學(xué)內(nèi)容，調(diào)動學(xué)生學(xué)習(xí)的主觀能動性。實驗針對相應(yīng)單元所學(xué)的內(nèi)容，能夠采取合適的數(shù)據(jù)結(jié)構(gòu)和算法解決有關(guān)問題。實驗重點培養(yǎng)學(xué)生的動手能力。實習(xí)針對較為復(fù)雜的應(yīng)用問題，能夠綜合運用所學(xué)的各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行算法設(shè)計和實現(xiàn)，注重學(xué)生數(shù)據(jù)抽象能力和算法設(shè)計能力的培養(yǎng)。

三、本課程與其它課程的聯(lián)系和分工

本課程的先修課為程序設(shè)計基礎(chǔ)和離散數(shù)學(xué)，本課程可以C/C++或Java語言作為算法描述和上機實踐的工具。同時，本課程又是軟件開發(fā)與設(shè)計等方面課程的基礎(chǔ)，如數(shù)據(jù)庫、操作系統(tǒng)、編譯原理、軟件工程等課程。

四、本課程的考核方式

期末考試采用筆試形式，考試題型為：選擇、填空、判斷、應(yīng)用題和算法設(shè)計題。總評成績由平時成績和期末成績組成，其中平時成績占30%--40%，期末考試占70%--60%。

課程實習(xí)的成績由平時成績和實習(xí)作業(yè)兩部分組成，其中平時成績占30%，實習(xí)作業(yè)占70%。

五、建議教材與教學(xué)參考書

建議教材：

1.嚴(yán)蔚敏，李冬梅，吳偉民．?dāng)?shù)據(jù)結(jié)構(gòu)（C語言版）．北京：人民郵電出版社． 2.嚴(yán)蔚敏主編．?dāng)?shù)據(jù)結(jié)構(gòu)（C語言版）．北京：清華大學(xué)出版社．

3.殷人昆主編．?dāng)?shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC++描述）．北京：清華大學(xué)出版社． 建議教學(xué)參考書：

1.[美]Bruno R.Preiss著，胡廣斌，王崧等譯．?dāng)?shù)據(jù)結(jié)構(gòu)與算法－面向?qū)ο蟮腃++設(shè)計模式．北京：電子工業(yè)出版社．

2.殷人昆主編．?dāng)?shù)據(jù)結(jié)構(gòu)與習(xí)題解析（用面向?qū)ο蠓椒ㄅcC++描述）．北京：清華大學(xué)出版社．

六、課程簡介

數(shù)據(jù)結(jié)構(gòu)是一門專業(yè)基礎(chǔ)課，是學(xué)習(xí)其他軟件開發(fā)與設(shè)計等方面課程的基礎(chǔ)。主要內(nèi)容包括：線性表、棧和隊列、串、數(shù)組和廣義表、樹、圖、查找算法和排序算法。數(shù)據(jù)結(jié)構(gòu)研究數(shù)據(jù)的組織方式，內(nèi)容豐富、學(xué)習(xí)量大，隱含在各部分內(nèi)容中的方法和技術(shù)多，旨在讓學(xué)生掌握計算機軟件系統(tǒng)所必需的數(shù)據(jù)結(jié)構(gòu)的算法。要求學(xué)生掌握貫穿全課程的動態(tài)鏈表存儲結(jié)構(gòu)，掌握算法設(shè)計的動態(tài)性和抽象性。要求學(xué)生學(xué)會分析研究計算機加工的數(shù)據(jù)對象的特征，以便在實際應(yīng)用中選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)、存儲結(jié)構(gòu)和相應(yīng)算法，初步掌握算法的時間與空間性能分析技巧，并培養(yǎng)復(fù)雜程序設(shè)計的技能。

執(zhí)筆人：

審核人：

教學(xué)院長：

院學(xué)術(shù)委員會：

院長：