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

1、算法與數(shù)據(jù)結(jié)構教學大綱一、使用說明（一）課程性質(zhì)數(shù)據(jù)結(jié)構是一門專業(yè)基礎課，在計算機軟件的各個領域中均會使用到數(shù)據(jù)結(jié)構的有關知識。本課程的先修課程為C程序設計或C+程序設計。（二）教學目的學會從問題入手，分析研究計算機加工的數(shù)據(jù)結(jié)構的特性，以便為應用所涉及的數(shù)據(jù)選擇適當?shù)倪壿嫿Y(jié)構、存儲結(jié)構及其相應的操作算法，并初步掌握時間和空間分析技術。另一方面，本課程的學習過程也是進行復雜程序設計的訓練過程，要求學生會書寫符合軟件工程規(guī)范的文件，編寫的程序代碼應結(jié)構清晰、正確易讀，能上機調(diào)試并排除錯誤。（三）教學時數(shù)課堂講授每周4學時，18周，共72學時。（四）教學方法本課程將采用課堂講授及課堂討論相結(jié)合的交

2、互式教學法，同時輔以必要的上機操作實踐。（五）面向?qū)I(yè)計算機科學與技術專業(yè)。二、教學內(nèi)容第一章 緒論（一）教學目的要求 介紹數(shù)據(jù)結(jié)構的一些基本概念，算法的時間復雜度和空間復雜度的分析方法，抽象數(shù)據(jù)類型的定義和使用以及算法的描述方法。掌握數(shù)據(jù)結(jié)構的一些基本概念，掌握算法的時間復雜度和空間復雜度的分析方法，了解抽象數(shù)據(jù)類型的定義和使用，了解算法的描述方法。（二）教學內(nèi)容主要內(nèi)容：數(shù)據(jù)結(jié)構的一些基本概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)邏輯結(jié)構、數(shù)據(jù)存儲結(jié)構、數(shù)據(jù)類型、算法等。抽象數(shù)據(jù)類型。算法時間復雜度和空間復雜度的分析。教學重點：有關數(shù)據(jù)結(jié)構的各個名詞和術語的含義，以及語句頻度和時間復雜度、空間復雜度的估算

3、。教學難點：算法時間復雜度和空間復雜度的分析。第一節(jié) 什么是數(shù)據(jù)結(jié)構一、非數(shù)值計算二、數(shù)據(jù)結(jié)構課程內(nèi)容的歷史演變?nèi)?shù)據(jù)結(jié)構研究范圍第二節(jié) 基本概念和術語一、數(shù)據(jù)二、數(shù)據(jù)結(jié)構三、數(shù)據(jù)類型四、抽象數(shù)據(jù)類型五、多型數(shù)據(jù)類型第三節(jié) 抽象數(shù)據(jù)類型的表示與實現(xiàn)一、固有數(shù)據(jù)類型二、數(shù)據(jù)抽象三、抽象數(shù)據(jù)類型的描述語言第四節(jié) 算法和算法分析一、算法二、算法設計的要求三、算法效率的度量四、算法的存儲空間需求（三）教學方法與形式課堂講授、多媒體課件。（四）教學時數(shù) 4學時。第二章 線性表（一）教學目的與要求 介紹線性表的基本概念和類型定義，對順序表和單鏈表的常用操作方法及其程序?qū)崿F(xiàn)，循環(huán)鏈表和雙向鏈表的定義和它的

4、插入、刪除等操作方法。掌握線性表的基本概念和類型定義；熟練掌握對順序表和單鏈表的常用操作方法及其程序?qū)崿F(xiàn)；掌握循環(huán)鏈表和雙向鏈表的定義和它的插入、刪除等操作方法。（二）教學內(nèi)容主要內(nèi)容：線性表的基本概念和類型定義， 線性表的順序存儲結(jié)構， 線性表的鏈接存儲結(jié)構：（1）單鏈表的查找、插入和刪除；（2）循環(huán)鏈表；（3）雙向鏈表。教學重點：在順序表和鏈表上各種基本算法的實現(xiàn)及相關的時間性能分析。教學難點：用所學的基本知識設計有效算法解決與線性表相關的應用問題。鏈表要分清鏈表中指針p和結(jié)點*p之間的對應關系，區(qū)分鏈表中的頭結(jié)點、頭指針以及循環(huán)鏈表、雙向鏈表的特點等。第一節(jié) 線性表的類型定義一、線性表的

5、定義二、線性表的基本操作第二節(jié) 線性表的順序存儲表示和實現(xiàn)一、順序表二、順序表上基本運算的實現(xiàn)三、順序表應用舉例第三節(jié) 線性表的鏈式存儲表示和實現(xiàn)一、線性鏈表二、循環(huán)鏈表三、雙向鏈表四、靜態(tài)鏈表第四節(jié) 一元多項式的表示及相加一、一元多項式的數(shù)學表示二、一元多項式的計算機表示三、抽象數(shù)據(jù)類型：一元多項式的定義四、抽象數(shù)據(jù)類型：一元多項式的存儲結(jié)構五、抽象數(shù)據(jù)類型：一元多項式的基本操作算法實現(xiàn)（三）教學方法與形式課堂講授、多媒體課件。（四）教學時數(shù) 8學時。第三章 棧和隊列（一）教學目的與要求 介紹棧和隊列的定義，順序和鏈接存儲的棧和隊列的各種運算的方法及其程序?qū)崿F(xiàn)。掌握棧和隊列的定義，熟練掌握順

6、序和鏈接存儲的棧和隊列的各種運算的方法及其程序?qū)崿F(xiàn)。（二）教學內(nèi)容主要內(nèi)容：棧的類型定義，棧的順序存儲和鏈接存儲的表示，在棧的順序存儲和鏈接存儲上進行各種棧操作的算法，棧的應用舉例，隊列的類型定義，隊列的順序存儲(循環(huán)隊)和鏈接存儲表示及各種操作的實現(xiàn)算法。教學重點：棧和隊列在兩種存儲結(jié)構上實現(xiàn)的基本運算。教學難點：遞歸的實現(xiàn)、循環(huán)隊列中對邊界條件的處理。第一節(jié) 棧一、抽象數(shù)據(jù)類型棧的定義二、棧的表示和實現(xiàn)第二節(jié) 棧的應用舉例一、數(shù)制轉(zhuǎn)換二、括號匹配的檢驗三、表達式求值第三節(jié) 棧與遞歸的實現(xiàn)一、函數(shù)調(diào)用與棧二、遞歸調(diào)用棧的變化第四節(jié) 隊列一、抽象數(shù)據(jù)類型隊列的定義二、鏈隊列-隊列的鏈式表示和實

7、現(xiàn)三、循環(huán)隊列-隊列的順序表示和實現(xiàn)第五節(jié) 優(yōu)先級隊列一、優(yōu)先級隊列的概念二、優(yōu)先級隊列的存儲表示和實現(xiàn)（三）教學方法與形式課堂講授、多媒體課件。（四）教學時數(shù) 4學時。第四章 串（一）教學目的與要求 介紹串的基本概念和操作，串的存儲結(jié)構以及基本操作的算法實現(xiàn)。掌握串的基本概念和操作，掌握串的存儲結(jié)構以及基本操作的算法實現(xiàn)。（二）教學內(nèi)容 主要內(nèi)容：串的類型定義，串的表示和實現(xiàn)，正文模式匹配，正文編輯串操作應用舉例串的類型定義。教學重點：串類型定義中各基本操作的定義以及串的實現(xiàn)方法。教學難點：利用串的基本操作來實現(xiàn)串的其它操作。第一節(jié) 串的類型定義一、串的定義二、串的基本操作第二節(jié) 串的表示和

8、實現(xiàn)一、定長順序存儲表示二、堆分配存儲表示三、串的塊鏈存儲表示四、字符串操作的實現(xiàn)第三節(jié) 字符串的模式匹配一、求子串位置的定位函數(shù)Index（S，T，pos）二、模式匹配的一種改進算法（三）教學方法與形式課堂講授、多媒體課件。（四）教學時數(shù)4學時。第五章 數(shù)組和廣義表（一）教學目的 介紹數(shù)組的基本概念和基本操作的算法實現(xiàn)；稀疏矩陣的定義和各種存儲結(jié)構，稀疏矩陣的轉(zhuǎn)置和相加的方法并了解其算法；廣義表的定義、存儲結(jié)構和求廣義表的長度及深度的算法，建立廣義表和輸出廣義表的方法并了解其算法。掌握數(shù)組的基本概念和基本操作的算法實現(xiàn)；掌握稀疏矩陣的定義和各種存儲結(jié)構，掌握稀疏矩陣的轉(zhuǎn)置和相加的方法并了解其

9、算法；掌握廣義表的定義、存儲結(jié)構和求廣義表的長度及深度的算法，掌握建立廣義表和輸出廣義表的方法并了解其算法。（二）教學內(nèi)容主要內(nèi)容：稀疏矩陣的定義、存儲和運算，廣義表的定義、存儲和運算串的類型定義。教學重點：特殊矩陣的壓縮存儲，以及稀疏矩陣的三元組順序表示。教學難點：特殊矩陣的壓縮存儲，以及稀疏矩陣的三元組順序表示。第一節(jié) 數(shù)組類型第二節(jié) 數(shù)組的順序表示和實現(xiàn)一、數(shù)組的存儲方式二、數(shù)組元素存儲位置的計算三、基本操作的實現(xiàn)第三節(jié) 矩陣的壓縮存儲一、特殊矩陣二、稀疏矩陣第四節(jié) 廣義表的定義一、廣義表的基本概念二、廣義表的三個重要結(jié)論第五節(jié) 廣義表的存儲表示一、頭尾鏈表存儲表示二、擴展線性鏈表存儲表

10、示第六節(jié) 廣義表的遞歸算法一、求廣義表的深度二、復制廣義表三、建立廣義表的存儲結(jié)構（三）教學方法與形式課堂講授、多媒體課件。（四）教學時數(shù)6學時。第六章 樹和二叉樹（一）教學目的與要求 介紹樹的定義、性質(zhì)、存儲結(jié)構及遍歷算法，握二叉樹的各種遍歷方法及其實現(xiàn)，二叉樹的其他操作方法及實現(xiàn)，樹、森林和二叉樹的轉(zhuǎn)換方法，哈夫曼樹的定義和構造哈夫曼樹的方法，哈夫曼樹編碼的方法。掌握樹的定義、性質(zhì)、存儲結(jié)構及遍歷算法，熟練掌握二叉樹的各種遍歷方法及其實現(xiàn)，掌握二叉樹的其他操作方法及實現(xiàn)，掌握樹、森林和二叉樹的轉(zhuǎn)換方法，掌握哈夫曼樹的定義和構造哈夫曼樹的方法，了解哈夫曼樹編碼的方法。（二）教學內(nèi)容主要內(nèi)容：

11、樹的定義、性質(zhì)和表示方法，二叉樹的定義、性質(zhì)和存儲結(jié)構，二叉樹的各種遍歷方法及實現(xiàn)，建立二叉樹、輸出二叉樹、求二叉樹深度等的操作方法及實現(xiàn)，樹的存儲結(jié)構，進行先根遍歷、后根遍歷和按層遍歷的方法及實現(xiàn)，進行樹與二叉樹的轉(zhuǎn)換方法，哈夫曼樹的定義、構造哈夫曼樹的方法及哈夫曼編碼的方法。教學重點：二叉樹和樹的遍歷及其應用。教學難點：實現(xiàn)二叉樹和樹的各種操作的遞歸算法。第一節(jié) 樹的定義和基本術語一、樹的定義二、森林的定義三、樹的抽象數(shù)據(jù)類型定義第二節(jié) 二叉樹一、二叉樹的定義二、二叉樹的性質(zhì)三、二叉樹的存儲結(jié)構第三節(jié) 遍歷二叉樹和線索二叉樹一、遍歷二叉樹二、線索二叉樹第四節(jié) 樹和森林一、樹的存儲結(jié)構二、森

12、林與二叉樹的轉(zhuǎn)換三、樹和森林的遍歷第五節(jié) 最優(yōu)樹和赫夫曼編碼一、最優(yōu)二叉樹（赫夫曼樹）二、赫夫曼編碼（三）教學方法與形式課堂講授、多媒體課件。（四）教學時數(shù)10學時。第七章 圖（一）教學目的與要求 介紹圖的定義和術語；圖的存儲結(jié)構及深度和廣度優(yōu)先搜索方法及其實現(xiàn)；圖的生成樹的概念，求圖的最小生成樹的普里姆算法和克魯斯卡爾算法并了解其實現(xiàn)算法；拓撲排序的方法并了解其實現(xiàn)算法；計算關鍵路徑的方法及其實現(xiàn)算法。掌握圖的定義和術語；熟練掌握圖的存儲結(jié)構及深度和廣度優(yōu)先搜索方法及其實現(xiàn)；掌握圖的生成樹的概念，掌握求圖的最小生成樹的普里姆算法和克魯斯卡爾算法并了解其實現(xiàn)算法；掌握拓撲排序的方法并了解其實現(xiàn)

13、算法；了解計算關鍵路徑的方法并了解其實現(xiàn)算法。（二）教學內(nèi)容主要內(nèi)容：圖的定義和術語，圖的鄰接矩陣、鄰接表和邊集數(shù)組表示，圖的深度和廣度優(yōu)先搜索遍歷，圖的生成樹和最小生成樹，拓撲排序。教學重點：圖在鄰接矩陣與鄰接表上實現(xiàn)的遍歷算法(DFS和BFS)。教學難點：基于遍歷算法的應用。第一節(jié) 圖的定義和術語一、圖的定義二、無向圖三、有向圖四、連通圖五、生成樹第二節(jié) 圖的存儲表示一、數(shù)組表示法二、鄰接表三、十字鏈表四、鄰接多重表第三節(jié) 圖的遍歷一、深度優(yōu)先搜索二、廣度優(yōu)先搜索三、連通分量第四節(jié) 最小生成樹一、Kruskal算法二、Prim算法第五節(jié) 有向無環(huán)圖及其應用一、拓撲排序二、關鍵路徑第六節(jié) 最

14、短路徑一、從某個源點到其余各項點的最短路徑二、每一對頂點之間的最短路徑（三）教學方法與形式課堂講授、多媒體課件。（四）教學時數(shù)12學時。第八章 查找表（一）教學目的與要求 介紹順序表查找和有序表查找的方法及實現(xiàn)；二叉排序樹和平衡二叉樹的定義、對二叉排序樹和平衡二叉樹進行插入、刪除和查找的方法和實現(xiàn)。哈希表的定義，構造哈希函數(shù)的多種方法，以及處理沖突的方法；B樹的定義，查找、插入和刪除元素的方法。熟練掌握順序表查找和有序表查找的方法及實現(xiàn)；掌握二叉排序樹和平衡二叉樹的定義、熟練掌握對二叉排序樹和平衡二叉樹進行插入、刪除和查找的方法和實現(xiàn)。掌握哈希表的定義，構造哈希函數(shù)的多種方法，以及處理沖突的方

15、法；了解B樹的定義，查找、插入和刪除元素的方法。（二）教學內(nèi)容主要內(nèi)容：順序查找和二分查找，索引查找和分塊查找，散列查找，動態(tài)查找樹表。教學重點：順序查找、二分查找、二叉排序樹上查找以及散列表上查找的基本思想和算法實現(xiàn)。教學難點：二叉排序樹的刪除算法。第一節(jié) 靜態(tài)查找表一、順序表的查找二、有序表的查找三、靜態(tài)樹表的查找四、索引順序表的查找第二節(jié) 動態(tài)查找表一、二叉排序樹二、平衡二叉樹三、動態(tài)的m路搜索樹四、B樹和B+樹基本概念第三節(jié) 哈希表一、什么是哈希表二、哈希函數(shù)的構造方法三、處理沖突的方法四、哈希表的查找及其分析（三）教學方法與形式課堂講授、多媒體課件。（四）教學時數(shù)10學時。第九章 內(nèi)

16、部排序（一）教學目的與要求 介紹插入排序、交換排序、選擇排序、快速排序、歸并排序、基數(shù)排序的方法及其實現(xiàn)，快速排序、堆排序、二路歸并排序的方法及其實現(xiàn)，各種排序方法的穩(wěn)定性、時間復雜度和空間復雜度。掌握插入排序、交換排序、選擇排序、快速排序、歸并排序、基數(shù)排序的方法及其實現(xiàn)，熟練掌握快速排序、堆排序、二路歸并排序的方法及其實現(xiàn)，掌握各種排序方法的穩(wěn)定性、時間復雜度和空間復雜度。（二）教學內(nèi)容 主要內(nèi)容：排序的概念，直接插入排序，冒泡排序和快排序，直接選擇排序和堆排序，歸并排序。教學重點：插入排序(直接插入、折半插入)、交換排序（冒泡、快速排序）、選擇排序（直接選擇、堆）、2 -路歸并排序。教學

17、難點：快速排序partition算法的應用和堆的調(diào)整。第一節(jié) 排序的定義和方法一、穩(wěn)定的排序方法二、內(nèi)部/外部排序三、內(nèi)部排序種類四、排序中的基本操作五、排序數(shù)據(jù)的存儲方式第二節(jié) 插入排序一、直接插入排序二、其他插入排序三、希爾排序第三節(jié) 交換排序法一、起泡排序算法二、快速排序算法第四節(jié) 選擇排序法一、簡單選擇排序二、樹形選擇排序三、堆排序第五節(jié) 歸并排序法第六節(jié) 基數(shù)排序一、多關鍵字的排序二、鏈式基數(shù)排序第七節(jié) 各種排序方法的綜合比較（三）教學方法與形式課堂講授、多媒體課件。（四）教學時數(shù)10學時。第十章 文件（一）教學目的與要求 介紹文件和記錄的基本概念以及基本操作。掌握文件和記錄的基本概念以及基本操作。（二）教學內(nèi)容主要內(nèi)容：基本概念，順序文件，索引文件，索引順序文件，散列文件，多關鍵碼文件。教學重點：各種文件的結(jié)構特點及其適用場合。教學難點：各種文件的結(jié)構特點及其適用場合。第一節(jié) 基本概念一、文件及其類別二、記錄的邏輯結(jié)構和物理結(jié)構三、文件的操作四、文件的物理結(jié)構第二節(jié) 順序文件一、順序文件的定義二、順序文件的優(yōu)缺點第三節(jié) 索引文件一、索引文件的定義二、索引文件的特點第四節(jié) ISAM文件和VSAM文件一、ISAM文件二、VSAM文件第五節(jié) 散列文件一、散