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

1、 數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)大綱前言數(shù)據(jù)結(jié)構(gòu)與算法課程是計算機相關(guān)專業(yè)高等教育的專業(yè)基礎(chǔ)課程。是計算機程序設(shè)計的重要理論技術(shù)基礎(chǔ)，它對理論和實踐的要求都相當(dāng)高，且內(nèi)容較多。作為數(shù)學(xué)與計算科學(xué)學(xué)院信息與計算專業(yè)的必修課，基本內(nèi)容以計算機系的專業(yè)技術(shù)基礎(chǔ)課-數(shù)據(jù)結(jié)構(gòu)的內(nèi)容為主，根據(jù)信息專業(yè)的特點，在內(nèi)容和難度上有所取舍。學(xué)習(xí)本課程所討論的知識內(nèi)容和提倡的技術(shù)方法和思路，無論對進一步學(xué)習(xí)計算機領(lǐng)域的其他課程，還是對從事軟件工程的開發(fā)，都有著不可替代的作用。本課程設(shè)置的目的是：要培養(yǎng)學(xué)生的數(shù)據(jù)抽象能力，學(xué)會分析研究計算機加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為信息的加工和處理選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)及實現(xiàn)應(yīng)用的適當(dāng)算

2、法，并掌握分析算法的時間和空間復(fù)雜度的技術(shù)。學(xué)習(xí)本課程的要求是：通過本課程的學(xué)習(xí)，要求學(xué)生了解數(shù)據(jù)結(jié)構(gòu)及其分類、數(shù)據(jù)結(jié)構(gòu)與算法的密切關(guān)系；熟悉各種基本數(shù)據(jù)結(jié)構(gòu)及其操作，學(xué)會根據(jù)實際問題要求來選擇數(shù)據(jù)結(jié)構(gòu)；掌握設(shè)計算法的基本步驟和算法分析方法；掌握數(shù)據(jù)結(jié)構(gòu)在排序和查找等常用算法中的應(yīng)用。先修課程要求：計算機基礎(chǔ)、C語言、離散數(shù)學(xué)本課程計劃總學(xué)時90學(xué)時，4學(xué)分，其中理論54學(xué)時，實驗課36學(xué)時。選用教材：1嚴(yán)蔚敏、吳偉民編著，數(shù)據(jù)結(jié)構(gòu)（C語言版），清華大學(xué)出版社，1999年2嚴(yán)蔚敏、吳偉民編著，數(shù)據(jù)結(jié)構(gòu)題集，清華大學(xué)出版社教學(xué)手段：多媒體教學(xué)考核方法：考試教學(xué)進程安排表周次周學(xué)時教學(xué)主要內(nèi)容教學(xué)

3、環(huán)節(jié)備注13第一章緒論2.1線性表的類型定義講課232.2線性表的順序存儲結(jié)構(gòu)講課332.3線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)講課433.1棧3.2棧的應(yīng)用舉例講課533.4隊列習(xí)題講課習(xí)題課63第四章串5.1數(shù)組的定義5.2數(shù)組的順序表示和實現(xiàn)講課735.3矩陣的壓縮存儲5.4廣義表的定義6.1樹的定義和基本術(shù)語6.2二叉樹講課836.3遍歷二叉樹和線索二叉樹講課936.4樹和森林6.6哈夫曼樹及其應(yīng)用講課1037.1圖的定義和術(shù)語7.2圖的存儲結(jié)構(gòu)講課1137.3圖的遍歷7.4圖的連通性問題講課1237.5有向圖五環(huán)圖及其應(yīng)用習(xí)題講課習(xí)題課1339.1靜態(tài)查找表9.2動態(tài)查找表講課1439.3哈希表講

4、課15310.1概述10.2插入排序10.3快速排序講課16310.4選擇排序10.5歸并排序10.7各種排序方法綜合比較講課173習(xí)題習(xí)題課183復(fù)習(xí)討論第一章緒論一、學(xué)習(xí)目的本章主要介紹了數(shù)據(jù)結(jié)構(gòu)的一些基本概念和算法分析的一般方法。具體包括數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)、算法等和類C語言的書寫規(guī)范。通過本章的學(xué)習(xí)，使學(xué)生領(lǐng)會數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)的概念及氣相互關(guān)系，掌握數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)的聯(lián)系與區(qū)別，了解算法時間復(fù)雜度和空間復(fù)雜度的分析。掌握類C語言的書寫要求。本章計劃理論2學(xué)時。二、課程內(nèi)容1.1-1.2數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語數(shù)據(jù)、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)的物理結(jié)構(gòu)、數(shù)據(jù)的邏輯

5、結(jié)構(gòu)、數(shù)據(jù)類型、抽象數(shù)據(jù)類型1.3抽象數(shù)據(jù)類型的表示與實現(xiàn)類C語言的書寫規(guī)范與應(yīng)用1.4算法描述和算法分析算法算法設(shè)計的要求算法效率的度量時間復(fù)雜度分析、語句頻度算法的存儲空間的要求三、重點、難點提示和教學(xué)手段重點難點：數(shù)據(jù)結(jié)構(gòu)相關(guān)的基本概念尤其是數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和算法之間的關(guān)系；抽象數(shù)據(jù)類型的定義、表示和實現(xiàn)；計算語句頻度和估算算法時間復(fù)雜度。教學(xué)手段講授四、思考與練習(xí)習(xí)題集1.1，1.2，1.3，1.8，1.9，1.10第二章 線性表一、學(xué)習(xí)目的通過本章的學(xué)習(xí)，要求學(xué)生掌握線性表的邏輯結(jié)構(gòu)特性及這種關(guān)系在計算機中的不同表示形式。熟練掌握順序存儲的線性表和單鏈表的算法設(shè)計及其程序?qū)崿F(xiàn)

6、結(jié)構(gòu)上實現(xiàn)的基本操作，熟練掌握線性表在鏈?zhǔn)酱鎯Y(jié)構(gòu)上基本操作的實現(xiàn)。掌握循環(huán)鏈表和雙向循環(huán)鏈表的基本操作。能夠從時間和空間的角度結(jié)合比較線性表兩種存儲結(jié)構(gòu)的不同特點及在不同的應(yīng)用中選擇合適存儲形式。計劃理論7學(xué)時。二、課程內(nèi)容2.1線性表的類型定義2.2線性表的順序存儲結(jié)構(gòu)順序表順序表上的基本運算2.3線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)線性鏈表循環(huán)鏈表雙向鏈表三、重點、難點提示和教學(xué)手段重點難點提示：線性表這種抽象數(shù)據(jù)結(jié)構(gòu)的定義及其邏輯上的特點；順序表上插入、刪除和定位運算的實現(xiàn)；單鏈表的結(jié)構(gòu)特點及其類型說明；頭指針和頭結(jié)點的作用；定位、刪除、插入運算在單鏈表上的實現(xiàn)；循環(huán)鏈表和雙鏈表的結(jié)構(gòu)特點，尤其是鏈

7、表定義及其操作。順序表和鏈表的比較和在不同應(yīng)用環(huán)境下的選擇是教學(xué)難點。講課輔以算法演示，另加實驗。四、思考與練習(xí)2.2，2.3，2.4，2.5，2.6，2.7，2.8，2.9，2.10，2.13，2.13，2.17，2.19，2.20，2.21，2.24，2.25，2.26，2.31第三章 棧和隊列一、學(xué)習(xí)目的本章主要介紹了兩種常用的操作受限的線性表，內(nèi)容包括這兩種線性表的定義和在兩種存儲結(jié)構(gòu)上操作的實現(xiàn)。通過本章學(xué)習(xí)要求理解棧和隊列的定義，掌握棧和隊列在兩種存儲結(jié)構(gòu)中的基本操作的實現(xiàn)。能夠在簡單的應(yīng)用中，為數(shù)據(jù)選擇合適的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，并實現(xiàn)要求的操作。計劃理論6學(xué)時。二、課程內(nèi)容3.1

8、棧抽象數(shù)據(jù)類型棧的定義和基本操作棧的順序存儲結(jié)構(gòu)棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)3.2棧的應(yīng)用舉例數(shù)制轉(zhuǎn)換括號匹配迷宮求解表達式求值3.3棧與遞歸（選講）3.4隊列抽象數(shù)據(jù)類型隊列的定義鏈隊列隊列的鏈?zhǔn)奖硎竞蛯崿F(xiàn)循環(huán)隊列隊列的順序表示和實現(xiàn)三、重點、難點提示和教學(xué)手段重點難點：棧上的基本運算；棧的順序存儲結(jié)構(gòu)及運算實現(xiàn)；棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)；入棧、出棧等運算在鏈棧上的實現(xiàn)；隊列上的基本運算；隊列的順序存儲結(jié)構(gòu)及其上的運算實現(xiàn)；隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)；入隊、出隊等運算在鏈?zhǔn)疥犃猩系膶崿F(xiàn)是本章教學(xué)的重點。順序棧的溢出判斷條件，循環(huán)隊列的隊空、隊滿判斷條件；循環(huán)隊列上的插入和刪除操作，為實際的應(yīng)用選擇合適的數(shù)據(jù)結(jié)構(gòu)是本章的

9、難點。講課加實驗。四、思考與練習(xí)題集3.1，3.3，3.4，3.7，3.19，3.28，3.29第四章 串一、學(xué)習(xí)目的通過本章學(xué)習(xí)，要求學(xué)生掌握串類型的抽象數(shù)據(jù)類型定義和有關(guān)基本概念，理解串的模式匹配思想，了解串的表示和實現(xiàn)和串的模式匹配算法。計劃理論2學(xué)時。二、課程內(nèi)容4.1串的定義4.2串的表示和實現(xiàn)定長順序存儲堆分配存儲表示串的塊鏈存儲表示4.4串的應(yīng)用舉例三、重點、難點提示和教學(xué)手段重點和難點：串的表示和實現(xiàn)，熟練掌握串的定長順序表示和實現(xiàn)串的基本操作。串的堆存儲是本章的難點。講授。四、思考與練習(xí)題集4.3，4.4，4.9第五章 數(shù)組和廣義表一、學(xué)習(xí)目的通過本章學(xué)習(xí)了解數(shù)組的定義和表示

10、方式，掌握特殊矩陣和壓縮矩陣的壓縮存儲方法；理解廣義表的邏輯結(jié)構(gòu)。本章計劃2學(xué)時二、課程內(nèi)容5.1數(shù)組的定義5.2數(shù)組的順序表示和實現(xiàn)5.3矩陣的壓縮存儲5.3.1特殊矩陣5.3.2稀疏矩陣5.4廣義表的定義三、重點、難點提示和教學(xué)手段重點和難點：數(shù)組在以行為主的存儲結(jié)構(gòu)中的地址計算方法，廣義表的邏輯結(jié)構(gòu)。特殊矩陣的壓縮存儲時的下標(biāo)變換公式是其難點。講課輔以算法演示。四、思考與練習(xí)題集5.1，5.6，5.7，5.8，5.10，5.13，5.21第六章 樹和二叉樹一、學(xué)習(xí)目的通過本章的學(xué)習(xí)要求，要求學(xué)生掌握以下內(nèi)容：樹的定義、性質(zhì)、存儲結(jié)構(gòu)；熟練掌握二叉樹的遍歷，哈夫曼樹的構(gòu)造和編碼方法；了解二

11、叉樹的線索化，樹與森林的轉(zhuǎn)化和樹的應(yīng)用。能夠運用二叉樹的遍歷解決相關(guān)的應(yīng)用問題。計劃理論學(xué)時8學(xué)時。二、課程內(nèi)容6.1樹的定義和基本術(shù)語樹的定義基本操作6.2二叉樹二叉樹的定義和基本操作二叉樹的性質(zhì)普通二叉樹、完全二叉樹、滿二叉樹二叉樹的存儲結(jié)構(gòu)6.3遍歷二叉樹和線索二叉樹遍歷二叉樹先序遍歷二叉樹、中序遍歷二叉樹、后序遍歷二叉樹線索二叉樹中序線索化二叉樹6.4樹和森林樹的存儲結(jié)構(gòu)森林與二叉樹的轉(zhuǎn)換樹和森林的遍歷6.6哈夫曼樹及其應(yīng)用最優(yōu)二叉樹的定義哈夫曼樹的構(gòu)造和哈夫曼編碼二、重點、難點提示和教學(xué)手段重點和難點：本章是本課程的教學(xué)重點。其中二叉樹的定義、邏輯特點及其五種基本形態(tài)；二叉樹的五個性

12、質(zhì)；二叉樹上的基本運算；二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)及其類型說明；二叉樹的順序存儲結(jié)構(gòu)及其類型說明；二叉樹的三種遍歷方法及在此基礎(chǔ)上的應(yīng)用；哈夫曼樹和哈夫曼編碼是本章的教學(xué)重點。二叉樹的遞歸定義；二叉樹鏈?zhǔn)酱鎯Y(jié)構(gòu)和組織形式；三種遍歷的主要區(qū)別是教學(xué)難點。講課輔以算法演示，另加實驗。四、思考與練習(xí)6.1，6.4，6.14，6.19，6.21，6.22，6.23，6.26，6.27，6.33，6.43，6.63第七章圖一、學(xué)習(xí)目的通過學(xué)習(xí)本章要求學(xué)生掌握以下內(nèi)容：理解圖的基本概念和術(shù)語；掌握圖的兩種存儲結(jié)構(gòu)方法；掌握圖的兩種遍歷的算法思想、步驟，并能列出在兩種存儲結(jié)構(gòu)上按上述兩種遍歷算法得到的序列；理解

13、最小生成樹的概念，能夠運用普里姆或庫魯索方法生成圖的最小生成樹；領(lǐng)會拓?fù)渑判?、最短路徑的思想，能夠列出一個圖的拓?fù)渑判蛐蛄?。本章是本課程的又一個教學(xué)的重點和難點章節(jié)。計劃理論學(xué)時9學(xué)時。二、課程內(nèi)容7.1圖的定義和術(shù)語7.2圖的存儲結(jié)構(gòu)數(shù)組表示鄰接表7.3圖的遍歷深度優(yōu)先遍歷廣度優(yōu)先遍歷7.4圖的連通性問題無向圖的連通分量和生成樹最小生成樹7.5有向圖五環(huán)圖及其應(yīng)用拓?fù)渑判蜃疃搪窂饺?、重點、難點提示和教學(xué)手段重點和難點：理解圖的定義、術(shù)語與含義；掌握各種圖的鄰接矩陣表示法及其類型說明；理解并掌握圖的兩種遍歷方法；領(lǐng)會生成樹和最小生成樹的概念，并能夠選用一種方法得到圖的最小生成樹；強化拓?fù)溆行虻?/p>

14、概念，可以根據(jù)相應(yīng)的算法和步驟得到圖的拓?fù)渑判蛐蛄?；了解關(guān)鍵路徑的思想和最短路徑的思想。圖的術(shù)語的理解和區(qū)分；圖的兩種存儲結(jié)構(gòu)的不同點及其應(yīng)用場合是教學(xué)的難點。講課輔以算法演示，另加實驗。三、思考與練習(xí)習(xí)題集：7.1，7.7，7.6，7.11第九章 查找一、學(xué)習(xí)目的通過本章的學(xué)習(xí)，要求掌握靜態(tài)查找表的查找算法和實現(xiàn)，掌握二叉排序樹的查找、插入算法及其實現(xiàn)；掌握哈希表的構(gòu)造方法；深刻理解哈希表與其他結(jié)構(gòu)表的實質(zhì)性的差別。了解三類函數(shù)和處理沖突的方法，能夠?qū)Ω鞣N查找方法，根據(jù)定義在等概率下的平均查找長度。本章是本課程的重點。計劃理論8學(xué)時.二、課程內(nèi)容9.1靜態(tài)查找表順序表查找有序表的查找靜態(tài)樹表

15、的查找索引順序表的查找9.2動態(tài)查找表二叉排序樹的查找、插入、刪除平衡二叉樹、B樹、B樹的思想9.3哈希表哈希表的概念哈希表的構(gòu)造方法處理沖突的方法哈希表的查找及其分析三、重點、難點提示和教學(xué)手段重點和難點：查找表的基本概念及查找原理，查找運算在靜態(tài)表有序表上的實現(xiàn)，動態(tài)查找表的概念，二叉排序樹的定義和二叉排序樹的查找算法和基本思想；哈希表的概念和散列的思想；簡單的構(gòu)造哈希表的方法和解決沖突的方式；平均查找長度的概念和計算是本章的教學(xué)重點。二叉排序樹上的插入和刪除；構(gòu)造散列表中的沖突的處理方式是本章的教學(xué)難點。講課輔以算法演示，另加實驗。四、思考與練習(xí)題集：9.9，9.19，9.21，9.25

16、，9.26，9.31第十章 內(nèi)部排序一、學(xué)習(xí)目的本章主要是介紹常用的內(nèi)部排序方法的基本思想、排序過程、算法實現(xiàn)、時間和空間性能的分析以及各種排序方法的比較和選擇。通過本章的學(xué)習(xí)要求理解各種內(nèi)部排序方法，插入排序、交換排序、選擇排序、歸并排序和基數(shù)排序的基本思想、算法特點、排序過程以及它們的時間復(fù)雜度分析。在每種排序方法中，重點掌握先進的高效方法。本章是本課程的重點和難點章節(jié)。計劃理論8學(xué)時。二、課程內(nèi)容10.1概述10.2插入排序直接插入排序希爾排序10.3快速排序10.4選擇排序簡單選擇排序樹刑選擇排序堆排序10.5歸并排序10.7各種排序方法綜合比較三、重點、難點提示和教學(xué)手段重點和難點：排序基本概念及穩(wěn)定排序和非穩(wěn)定排序的區(qū)別；各種排序方法的基本