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

1、.新版數(shù)據(jù)結(jié)構(gòu)課程教學(xué)大綱一、課程名稱數(shù)據(jù)結(jié)構(gòu)二、教學(xué)目的數(shù)據(jù)結(jié)構(gòu)是高等教育計算機(jī)信息管理專業(yè)中的一門專業(yè)基礎(chǔ)課，在計算機(jī)軟件的各個領(lǐng)域中均會使用到數(shù)據(jù)結(jié)構(gòu)的有關(guān)知識。本課程的目的和任務(wù)是使學(xué)生較全面地掌握各種常用的數(shù)據(jù)結(jié)構(gòu)，為學(xué)習(xí)后續(xù)軟件課程提供必要的基礎(chǔ)，提高運(yùn)用數(shù)據(jù)結(jié)構(gòu)解決實(shí)際問題的能力。三、教學(xué)要求 1. 從數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算三個方面去掌握線性表、棧、隊列、串、數(shù)組、廣義表、樹、圖等常用的數(shù)據(jù)結(jié)構(gòu)。 2. 掌握在各種常用的數(shù)據(jù)結(jié)構(gòu)上實(shí)現(xiàn)的排序和查找運(yùn)算。 3. 對算法的時間和空間復(fù)雜性有一定的分析能力。 4. 針對簡單的應(yīng)用問題.應(yīng)能選擇合適的數(shù)據(jù)結(jié)構(gòu)及設(shè)計有效的

2、算法解決之。四、教學(xué)課時數(shù)分配表章 次教學(xué)內(nèi)容課時數(shù)分配作業(yè)次數(shù)備注總課時數(shù)理論實(shí)踐習(xí)題第一章緒論22第二章線性表147(6)7(8)2第三章棧和隊列6(8)3(4)3(4)2第四章 串4221第五章 數(shù)組和廣義表4221第六章樹和二叉樹8442第七章圖8442第八章查找8441第九章內(nèi)部排序10(8)46(4)1合計64323212五、理論教學(xué)內(nèi)容第一章 緒論 （2課時）內(nèi)容提要：本章的目的是介紹數(shù)據(jù)結(jié)構(gòu)中常用的基本概念和術(shù)語以及學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義，要求了解本章介紹的各種基本概念和術(shù)語，掌握算法描述和分析的方法。教學(xué)重點(diǎn)和難點(diǎn)：本章重點(diǎn)是了解數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及數(shù)據(jù)的運(yùn)算三方面的概

3、念及相互關(guān)系，難點(diǎn)是算法復(fù)雜度的分析方法。§1.1 基本概念和術(shù)語（1課時）§1.2 算法的描述和分析（1課時）第二章 線性表 （7課時）內(nèi)容提要：本章目的是介紹線性表的邏輯結(jié)構(gòu)和各種存儲表示方法，以及定義在邏輯結(jié)構(gòu)上的各種基本運(yùn)算及其在存儲結(jié)構(gòu)上如何實(shí)現(xiàn)這些基本運(yùn)算。要求在熟悉這些內(nèi)容的基礎(chǔ)上，能夠針對具體應(yīng)用問題的要求和性質(zhì)，選擇合適的存儲結(jié)構(gòu)設(shè)計出相應(yīng)的有效算法，解決與線性表相關(guān)的實(shí)際問題。教學(xué)重點(diǎn)和難點(diǎn)：本章重點(diǎn)是熟練掌握順序表和單鏈表上實(shí)現(xiàn)的各種基本算法及相關(guān)的時間性能分析，難點(diǎn)是能夠使用本章所學(xué)到的基本知識設(shè)計有效算法解決與線性表相關(guān)的應(yīng)用問題。§2.

4、1 線性表的邏輯結(jié)構(gòu)（2課時）§2.2 線性表的順序存儲結(jié)構(gòu)（2課時）§2.3 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)（2課時）§2.4 順序表和鏈表的比較（1課時）第三章 棧和隊列 （3課時）內(nèi)容提要：本章目的是介紹棧和隊列的邏輯結(jié)構(gòu)定義及在兩種存儲結(jié)構(gòu)上如何實(shí)現(xiàn)棧和隊列的基本運(yùn)算。要求在掌握棧和隊列的特點(diǎn)的基礎(chǔ)上，懂得在什么樣的情況下能夠使用?；蜿犃小＝虒W(xué)重點(diǎn)和難點(diǎn)：本章重點(diǎn)是掌握棧和隊列在兩種存儲結(jié)構(gòu)上實(shí)現(xiàn)的基本運(yùn)算，難點(diǎn)是循環(huán)隊列中對邊界條件的處理。§3.1 棧（1課時）§3.2 隊列（1課時）§3.3 棧和隊列的應(yīng)用（1課時）第四章 串 （2

5、課時）內(nèi)容提要：本章目的是介紹串的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其中上的基本運(yùn)算，由于C語言及其它高級語言均已具備了較強(qiáng)的串處理功能。教學(xué)重點(diǎn)和難點(diǎn)：本章重點(diǎn)是掌握串上實(shí)現(xiàn)的模式匹配算法，這也是本章的難點(diǎn)。§4.1 串及其運(yùn)算（1課時）§4.2 串的存儲結(jié)構(gòu)（1課時）第五章 數(shù)組和廣義表 （2課時）內(nèi)容提要：本章目的是介紹多維數(shù)組的邏輯結(jié)構(gòu)特征及其存儲方式，特殊矩陣和稀疏矩陣的壓縮存儲方法及廣義表的概念，要求學(xué)生熟悉這些內(nèi)容。教學(xué)重點(diǎn)和難點(diǎn)：本章重點(diǎn)是熟悉多維數(shù)組的存儲方式、矩陣的壓縮存儲方式、廣義表的定義及其求表頭和表尾的運(yùn)算，難點(diǎn)是稀疏矩陣的壓縮存儲表示下實(shí)現(xiàn)的算法。§

6、5.1 多維數(shù)組（1課時）§5.2 矩陣的壓縮存儲（0.5課時）§5.3 廣義表的概念（0.5課時）第六章 樹和二叉樹 （4課時）內(nèi)容提要：本章目的是介紹二叉樹的定義、性質(zhì)、存儲結(jié)構(gòu)、遍歷、線索化，樹的定義、存儲結(jié)構(gòu)、遍歷、樹和森林與二叉樹的轉(zhuǎn)換，哈夫曼樹及哈夫曼編碼等內(nèi)容。教學(xué)重點(diǎn)和難點(diǎn)：重點(diǎn)掌握二叉樹的遍歷算法及其有關(guān)應(yīng)用，難點(diǎn)是使用本章所學(xué)到的有關(guān)知識設(shè)計出有效算法，解決與樹或二叉樹相關(guān)的應(yīng)用問題。§6.1 樹的概念（0.5課時）§6.2 二叉樹（1課時）§6.3 二叉樹的遍歷（1課時）§6.4 線索二又樹（0.5課時）

7、7;6.5 樹和森林（0.5課時）§6.6 哈夫曼樹及其應(yīng)用（0.5課時）第七章 圖 （4課時）內(nèi)容提要：圖的定義，有關(guān)術(shù)語和存貯結(jié)構(gòu)，圖的兩種遍歷算法。兩個求最小生成樹的算法，最短路徑，拓?fù)渑判蚝完P(guān)鍵路徑算法。教學(xué)重點(diǎn)和難點(diǎn)：要求學(xué)生在熟悉這些內(nèi)容的基礎(chǔ)上，重點(diǎn)掌握圖存貯結(jié)構(gòu)，圖的兩種遍歷算法。本章難點(diǎn)是求最小生成樹的算法，最短路徑，拓?fù)渑判蚝完P(guān)鍵路徑算法。§7.1 圖的基本概念和存貯結(jié)構(gòu)（1課時）§7.2 最小生成樹的算法（1課時）§7.3 最短路徑，拓?fù)渑判蚝完P(guān)鍵路徑算法（2課時）第八章 查找 （4課時）內(nèi)容提要：本章目的是介紹線性表、樹和散列表的

8、查找方法、算法實(shí)現(xiàn)以及各種查找方法的時間性能(平均查找長度)分析。教學(xué)重點(diǎn)和難點(diǎn)：要求學(xué)生在熟悉這些內(nèi)容的基礎(chǔ)上，重點(diǎn)掌握順序查找、二分查找，二叉查找樹上查找以及散列表上查找的基本思想和算法實(shí)現(xiàn)。本章難點(diǎn)是二叉查找樹的刪除算法及B樹上的插入和刪除算法。§9.1 基本概念（1 課時）§9.2 線性表的查找（1課時）§9.3 樹的查找（1課時）§9.4 散列技術(shù)（1課時）第九章 內(nèi)部排序 （4課時）內(nèi)容提要：本章目的是介紹五類內(nèi)部排序方法的基本思想、排序過程、算法實(shí)現(xiàn)、時間和空間性能的分析以及各種排序方法的比較和選擇。教學(xué)重點(diǎn)和難點(diǎn)：要求學(xué)生在熟悉這些內(nèi)容的

9、基礎(chǔ)上，重點(diǎn)掌握快速排序、堆排序、歸并排序和基數(shù)排序的基本思想及排序過程。本章難點(diǎn)是四個排序算法的實(shí)現(xiàn)。§9.1 插入排序（1課時）§9.2 交換排序（1課時）§9.3 選擇排序（0.5課時）§9.4 歸并排序（0.5課時）§9.5 分配排序（0.5課時）§9.6 各種排序方法的比較和選擇（0.5課時）八、實(shí)踐教學(xué)內(nèi)容第一章 線性表 （7課時）內(nèi)容提要：本章目的是介紹線性表的邏輯結(jié)構(gòu)和各種存儲表示方法，以及定義在邏輯結(jié)構(gòu)上的各種基本運(yùn)算及其在存儲結(jié)構(gòu)上如何實(shí)現(xiàn)這些基本運(yùn)算。要求在熟悉這些內(nèi)容的基礎(chǔ)上，能夠針對具體應(yīng)用問題的要求和性質(zhì)，

10、選擇合適的存儲結(jié)構(gòu)設(shè)計出相應(yīng)的有效算法，解決與線性表相關(guān)的實(shí)際問題。教學(xué)重點(diǎn)和難點(diǎn)：本章重點(diǎn)是熟練掌握順序表和單鏈表上實(shí)現(xiàn)的各種基本算法及相關(guān)的時間性能分析，難點(diǎn)是能夠使用本章所學(xué)到的基本知識設(shè)計有效算法解決與線性表相關(guān)的應(yīng)用問題。§1.1 線性表的邏輯結(jié)構(gòu)（1課時）§1.2 線性表的順序存儲結(jié)構(gòu)（2課時）§1.3 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)（2課時）§1.4 順序表和鏈表的比較（2課時）第二章 棧和隊列 （3課時）內(nèi)容提要：本章目的是介紹棧和隊列的邏輯結(jié)構(gòu)定義及在兩種存儲結(jié)構(gòu)上如何實(shí)現(xiàn)棧和隊列的基本運(yùn)算。要求在掌握棧和隊列的特點(diǎn)的基礎(chǔ)上，懂得在什么樣的情況下

11、能夠使用棧或隊列。教學(xué)重點(diǎn)和難點(diǎn)：本章重點(diǎn)是掌握棧和隊列在兩種存儲結(jié)構(gòu)上實(shí)現(xiàn)的基本運(yùn)算，難點(diǎn)是循環(huán)隊列中對邊界條件的處理。§2.1 棧（1課時）§2.2 隊列（1課時）§2.3 棧和隊列的應(yīng)用（1課時）第三章 串 （2課時）內(nèi)容提要：本章目的是介紹串的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其中上的基本運(yùn)算，由于C語言及其它高級語言均已具備了較強(qiáng)的串處理功能。教學(xué)重點(diǎn)和難點(diǎn)：本章重點(diǎn)是掌握串上實(shí)現(xiàn)的模式匹配算法，這也是本章的難點(diǎn)。§3.1 串及其運(yùn)算（1課時）§3.2 串的存儲結(jié)構(gòu)（1課時）第四章 數(shù)組和廣義表 （2課時）內(nèi)容提要：本章目的是介紹多維數(shù)組的邏輯結(jié)構(gòu)

12、特征及其存儲方式，特殊矩陣和稀疏矩陣的壓縮存儲方法及廣義表的概念，要求學(xué)生熟悉這些內(nèi)容。教學(xué)重點(diǎn)和難點(diǎn)：本章重點(diǎn)是熟悉多維數(shù)組的存儲方式、矩陣的壓縮存儲方式、廣義表的定義及其求表頭和表尾的運(yùn)算，難點(diǎn)是稀疏矩陣的壓縮存儲表示下實(shí)現(xiàn)的算法。§4.1 多維數(shù)組（1課時）§4.2 矩陣的壓縮存儲（1課時）第五章 樹和二叉樹 （4課時）內(nèi)容提要：本章目的是介紹二叉樹的定義、性質(zhì)、存儲結(jié)構(gòu)、遍歷、線索化，樹的定義、存儲結(jié)構(gòu)、遍歷、樹和森林與二叉樹的轉(zhuǎn)換，哈夫曼樹及哈夫曼編碼等內(nèi)容。教學(xué)重點(diǎn)和難點(diǎn)：重點(diǎn)掌握二叉樹的遍歷算法及其有關(guān)應(yīng)用，難點(diǎn)是使用本章所學(xué)到的有關(guān)知識設(shè)計出有效算法，解決與

13、樹或二叉樹相關(guān)的應(yīng)用問題。§5.1二叉樹（1課時）§5.2線索二又樹（1課時）§5.3樹和森林（1課時）§5.4哈夫曼樹及其應(yīng)用（1課時）第六章 圖 （4課時）內(nèi)容提要：圖的定義，有關(guān)術(shù)語和存貯結(jié)構(gòu)，圖的兩種遍歷算法。兩個求最小生成樹的算法，最短路徑，拓?fù)渑判蚝完P(guān)鍵路徑算法。教學(xué)重點(diǎn)和難點(diǎn)：要求學(xué)生在熟悉這些內(nèi)容的基礎(chǔ)上，重點(diǎn)掌握圖存貯結(jié)構(gòu)，圖的兩種遍歷算法。本章難點(diǎn)是求最小生成樹的算法，最短路徑，拓?fù)渑判蚝完P(guān)鍵路徑算法。§6.1 圖的基本概念和存貯結(jié)構(gòu)（1課時）§6.2 最小生成樹的算法（1課時）§6.3 最短路徑，拓?fù)渑?/p>

14、序和關(guān)鍵路徑算法（2課時）第七章 查找 （4課時）內(nèi)容提要：本章目的是介紹線性表、樹和散列表的查找方法、算法實(shí)現(xiàn)以及各種查找方法的時間性能(平均查找長度)分析。教學(xué)重點(diǎn)和難點(diǎn)：要求學(xué)生在熟悉這些內(nèi)容的基礎(chǔ)上，重點(diǎn)掌握順序查找、二分查找，二叉查找樹上查找以及散列表上查找的基本思想和算法實(shí)現(xiàn)。本章難點(diǎn)是二叉查找樹的刪除算法及B樹上的插入和刪除算法。§7.1線性表的查找（1課時）§7.2樹的查找（2課時）§7.3散列技術(shù)（1課時）第八章 內(nèi)部排序 （6課時）內(nèi)容提要：本章目的是介紹五類內(nèi)部排序方法的基本思想、排序過程、算法實(shí)現(xiàn)、時間和空間性能的分析以及各種排序方法的比較

15、和選擇。教學(xué)重點(diǎn)和難點(diǎn)：要求學(xué)生在熟悉這些內(nèi)容的基礎(chǔ)上，重點(diǎn)掌握快速排序、堆排序、歸并排序和基數(shù)排序的基本思想及排序過程。本章難點(diǎn)是四個排序算法的實(shí)現(xiàn)。§8.1 插入排序（1課時）§8.2 交換排序（1課時）§8.3 選擇排序（1課時）§8.4 歸并排序（1課時）§8.5 分配排序（1課時）§8.6 各種排序方法的比較和選擇（1課時）九、使用教材：數(shù)據(jù)結(jié)構(gòu)（C語言版）嚴(yán)蔚敏著清華大學(xué)出版社 1999.6十、參考書目：1、數(shù)據(jù)結(jié)構(gòu)（C語言版）清華大學(xué)出版社 主編：嚴(yán)蔚敏、吳偉民 2007.3 ；2、數(shù)據(jù)結(jié)構(gòu)題集（C語言版）清華大學(xué)出版社 主編：嚴(yán)蔚敏 1999.2 ；3、數(shù)據(jù)結(jié)構(gòu)清華大學(xué)出版社 主編：李筠、姜學(xué)軍 2008.8 ；4、數(shù)據(jù)結(jié)構(gòu)（第二版）清華大學(xué)出版社 主編：張世和 2007.9；5、數(shù)據(jù)結(jié)構(gòu)習(xí)題解析與實(shí)訓(xùn)(第2版)清華大學(xué)出版社 主編：張世和 2008.8 ；6、數(shù)據(jù)結(jié)構(gòu)（第二版）高等教