【正文】 第一篇：《算法與數(shù)據(jù)結(jié)構(gòu)》教學(xué)大綱《算法與數(shù)據(jù)結(jié)構(gòu)》教學(xué)大綱一、使用說明（一）課程性質(zhì)《數(shù)據(jù)結(jié)構(gòu)》是一門專業(yè)基礎(chǔ)課，在計算機軟件的各個領(lǐng)域中均會使用到數(shù)據(jù)結(jié)構(gòu)的有關(guān)知識。本課程的先修課程為C程序設(shè)計或C++程序設(shè)計。（二）教學(xué)目的學(xué)會從問題入手，分析研究計算機加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用所涉及的數(shù)據(jù)選擇適當?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)及其相應(yīng)的操作算法，并初步掌握時間和空間分析技術(shù)。另一方面，本課程的學(xué)習(xí)過程也是進行復(fù)雜程序設(shè)計的訓(xùn)練過程，要求學(xué)生會書寫符合軟件工程規(guī)范的文件，編寫的程序代碼應(yīng)結(jié)構(gòu)清晰、正確易讀，能上機調(diào)試并排除錯誤。（三）教學(xué)時數(shù)課堂講授每周4學(xué)時，18周，共72學(xué)時。（四）教學(xué)方法本課程將采用課堂講授及課堂討論相結(jié)合的交互式教學(xué)法，同時輔以必要的上機操作實踐。（五）面向?qū)I(yè)計算機科學(xué)與技術(shù)專業(yè)。二、教學(xué)內(nèi)容第一章 緒論（一）教學(xué)目的要求介紹數(shù)據(jù)結(jié)構(gòu)的一些基本概念，算法的時間復(fù)雜度和空間復(fù)雜度的分析方法，抽象數(shù)據(jù)類型的定義和使用以及算法的描述方法。掌握數(shù)據(jù)結(jié)構(gòu)的一些基本概念，掌握算法的時間復(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ù)類型。算法時間復(fù)雜度和空間復(fù)雜度的分析。教學(xué)重點：有關(guān)數(shù)據(jù)結(jié)構(gòu)的各個名詞和術(shù)語的含義，以及語句頻度和時間復(fù)雜度、空間復(fù)雜度的估算。教學(xué)難點：算法時間復(fù)雜度和空間復(fù)雜度的分析。第一節(jié)一、非數(shù)值計算二、數(shù)據(jù)結(jié)構(gòu)課程內(nèi)容的歷史演變?nèi)?、?shù)據(jù)結(jié)構(gòu)研究范圍第二節(jié)一、數(shù)據(jù)二、數(shù)據(jù)結(jié)構(gòu)三、數(shù)據(jù)類型四、抽象數(shù)據(jù)類型五、多型數(shù)據(jù)類型第三節(jié)一、固有數(shù)據(jù)類型抽象數(shù)據(jù)類型的表示與實現(xiàn)基本概念和術(shù)語 什么是數(shù)據(jù)結(jié)構(gòu)二、數(shù)據(jù)抽象三、抽象數(shù)據(jù)類型的描述語言第四節(jié)一、算法二、算法設(shè)計的要求三、算法效率的度量四、算法的存儲空間需求（三）教學(xué)方法與形式課堂講授、多媒體課件。（四）教學(xué)時數(shù)4學(xué)時。第二章 線性表（一）教學(xué)目的與要求介紹線性表的基本概念和類型定義，對順序表和單鏈表的常用操作方法及其程序?qū)崿F(xiàn)，循環(huán)鏈表和雙向鏈表的定義和它的插入、刪除等操作方法。掌握線性表的基本概念和類型定義；熟練掌握對順序表和單鏈表的常用操作方法及其程序?qū)崿F(xiàn)；掌握循環(huán)鏈表和雙向鏈表的定義和它的插入、刪除等操作方法。（二）教學(xué)內(nèi)容主要內(nèi)容：線性表的基本概念和類型定義，線性表的順序存儲結(jié)構(gòu)，線性表的鏈接存儲結(jié)構(gòu)：（1）單鏈表的查找、插入和刪除；（2）循環(huán)鏈表；（3）雙向鏈表。教學(xué)重點：在順序表和鏈表上各種基本算法的實現(xiàn)及相關(guān)的時間性能分析。教學(xué)難點：用所學(xué)的基本知識設(shè)計有效算法解決與線性表相關(guān)的應(yīng)用問題。鏈表要分清鏈表中指針p和結(jié)點*p之間的對應(yīng)關(guān)系，區(qū)分鏈表中的頭結(jié)點、頭指針以及循環(huán)鏈表、雙向鏈表的特點等。第一節(jié)一、線性表的定義二、線性表的基本操作第二節(jié)一、順序表二、順序表上基本運算的實現(xiàn)三、順序表應(yīng)用舉例第三節(jié)一、線性鏈表二、循環(huán)鏈表三、雙向鏈表四、靜態(tài)鏈表第四節(jié) 一、一元多項式的數(shù)學(xué)表示 二、一元多項式的計算機表示三、抽象數(shù)據(jù)類型：一元多項式的定義四、抽象數(shù)據(jù)類型：一元多項式的存儲結(jié)構(gòu)五、抽象數(shù)據(jù)類型：一元多項式的基本操作算法實現(xiàn)（三）教學(xué)方法與形式一元多項式的表示及相加 線性表的鏈式存儲表示和實現(xiàn) 線性表的順序存儲表示和實現(xiàn)線性表的類型定義 算法和算法分析 課堂講授、多媒體課件。（四）教學(xué)時數(shù)8學(xué)時。第三章 棧和隊列（一）教學(xué)目的與要求介紹棧和隊列的定義，順序和鏈接存儲的棧和隊列的各種運算的方法及其程序?qū)崿F(xiàn)。掌握棧和隊列的定義，熟練掌握順序和鏈接存儲的棧和隊列的各種運算的方法及其程序?qū)崿F(xiàn)。（二）教學(xué)內(nèi)容主要內(nèi)容：棧的類型定義，棧的順序存儲和鏈接存儲的表示，在棧的順序存儲和鏈接存儲上進行各種棧操作的算法，棧的應(yīng)用舉例，隊列的類型定義，隊列的順序存儲(循環(huán)隊)和鏈接存儲表示及各種操作的實現(xiàn)算法。教學(xué)重點：棧和隊列在兩種存儲結(jié)構(gòu)上實現(xiàn)的基本運算。教學(xué)難點：遞歸的實現(xiàn)、循環(huán)隊列中對邊界條件的處理。第一節(jié)一、抽象數(shù)據(jù)類型棧的定義二、棧的表示和實現(xiàn)第二節(jié)一、數(shù)制轉(zhuǎn)換二、括號匹配的檢驗三、表達式求值第三節(jié)一、函數(shù)調(diào)用與棧二、遞歸調(diào)用棧的變化第四節(jié)一、抽象數(shù)據(jù)類型隊列的定義二、鏈隊列隊列的鏈式表示和實現(xiàn)三、循環(huán)隊列隊列的順序表示和實現(xiàn)第五節(jié)一、優(yōu)先級隊列的概念二、優(yōu)先級隊列的存儲表示和實現(xiàn)（三）教學(xué)方法與形式課堂講授、多媒體課件。（四）教學(xué)時數(shù)4學(xué)時。第四章 串（一）教學(xué)目的與要求介紹串的基本概念和操作，串的存儲結(jié)構(gòu)以及基本操作的算法實現(xiàn)。掌握串的基本概念和操作，掌握串的存儲結(jié)構(gòu)以及基本操作的算法實現(xiàn)。（二）教學(xué)內(nèi)容主要內(nèi)容：串的類型定義，串的表示和實現(xiàn)，正文模式匹配，正文編輯——串操作應(yīng)用舉例串的類型定義。教學(xué)重點：串類型定義中各基本操作的定義以及串的實現(xiàn)方法。教學(xué)難點：利用串的基本操作來實現(xiàn)串的其它操作。優(yōu)先級隊列 隊列 棧與遞歸的實現(xiàn) 棧的應(yīng)用舉例棧第一節(jié)一、串的定義二、串的基本操作第二節(jié)一、定長順序存儲表示二、堆分配存儲表示三、串的塊鏈存儲表示四、字符串操作的實現(xiàn)第三節(jié)二、模式匹配的一種改進算法（三）教學(xué)方法與形式課堂講授、多媒體課件。（四）教學(xué)時數(shù)4學(xué)時。串的類型定義串的表示和實現(xiàn)字符串的模式匹配一、求子串位置的定位函數(shù)Index（S，T，pos）第五章 數(shù)組和廣義表（一）教學(xué)目的介紹數(shù)組的基本概念和基本操作的算法實現(xiàn)；稀疏矩陣的定義和各種存儲結(jié)構(gòu)，稀疏矩陣的轉(zhuǎn)置和相加的方法并了解其算法；廣義表的定義、存儲結(jié)構(gòu)和求廣義表的長度及深度的算法，建立廣義表和輸出廣義表的方法并了解其算法。掌握數(shù)組的基本概念和基本操作的算法實現(xiàn)；掌握稀疏矩陣的定義和各種存儲結(jié)構(gòu)，掌握稀疏矩陣的轉(zhuǎn)置和相加的方法并了解其算法；掌握廣義表的定義、存儲結(jié)構(gòu)和求廣義表的長度及深度的算法，掌握建立廣義表和輸出廣義表的方法并了解其算法。（二）教學(xué)內(nèi)容主要內(nèi)容：稀疏矩陣的定義、存儲和運算，廣義表的定義、存儲和運算串的類型定義。教學(xué)重點：特殊矩陣的壓縮存儲，以及稀疏矩陣的三元組順序表示。教學(xué)難點：特殊矩陣的壓縮存儲，以及稀疏矩陣的三元組順序表示。第一節(jié) 第二節(jié)一、數(shù)組的存儲方式二、數(shù)組元素存儲位置的計算三、基本操作的實現(xiàn)第三節(jié)一、特殊矩陣二、稀疏矩陣第四節(jié)一、廣義表的基本概念二、廣義表的三個重要結(jié)論第五節(jié)一、頭尾鏈表存儲表示二、擴展線性鏈表存儲表示第六節(jié)廣義表的遞歸算法 廣義表的存儲表示 廣義表的定義 矩陣的壓縮存儲 數(shù)組類型 數(shù)組的順序表示和實現(xiàn)一、求廣義表的深度二、復(fù)制廣義表三、建立廣義表的存儲結(jié)構(gòu)（三）教學(xué)方法與形式課堂講授、多媒體課件。（四）教學(xué)時數(shù)6學(xué)時。第六章 樹和二叉樹（一）教學(xué)目的與要求介紹樹的定義、性質(zhì)、存儲結(jié)構(gòu)及遍歷算法，握二叉樹的各種遍歷方法及其實現(xiàn)，二叉樹的其他操作方法及實現(xiàn)，樹、森林和二叉樹的轉(zhuǎn)換方法，哈夫曼樹的定義和構(gòu)造哈夫曼樹的方法，哈夫曼樹編碼的方法。掌握樹的定義、性質(zhì)、存儲結(jié)構(gòu)及遍歷算法，熟練掌握二叉樹的各種遍歷方法及其實現(xiàn)，掌握二叉樹的其他操作方法及實現(xiàn)，掌握樹、森林和二叉樹的轉(zhuǎn)換方法，掌握哈夫曼樹的定義和構(gòu)造哈夫曼樹的方法，了解哈夫曼樹編碼的方法。（二）教學(xué)內(nèi)容主要內(nèi)容：樹的定義、性質(zhì)和表示方法，二叉樹的定義、性質(zhì)和存儲結(jié)構(gòu)，二叉樹的各種遍歷方法及實現(xiàn)，建立二叉樹、輸出二叉樹、求二叉樹深度等的操作方法及實現(xiàn)，樹的存儲結(jié)構(gòu)，進行先根遍歷、后根遍歷和按層遍歷的方法及實現(xiàn)，進行樹與二叉樹的轉(zhuǎn)換方法，哈夫曼樹的定義、構(gòu)造哈夫曼