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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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