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

1、數(shù)據(jù)結(jié)構(gòu)與算法課程教學(xué)大綱DataStructureAndAlgorithm課程編碼：XJB08006課程類別：學(xué)科基礎(chǔ)課程先修課程：程序設(shè)計(jì)基礎(chǔ)、高等數(shù)學(xué)、線性代數(shù)后修課程：操作系統(tǒng)、算法分析與設(shè)計(jì)、面向?qū)ο蟪绦蛟O(shè)計(jì)總學(xué)分：4總學(xué)時(shí)：64周學(xué)時(shí)：4適用專業(yè)：軟件工程、計(jì)算機(jī)科學(xué)與技術(shù)開(kāi)課單位：信息科學(xué)技術(shù)學(xué)院授課教師：常靜一、教學(xué)目標(biāo)及教學(xué)要求數(shù)據(jù)結(jié)構(gòu)與算法是計(jì)算機(jī)科學(xué)與技術(shù)、數(shù)字媒體技術(shù)、軟件工程專業(yè)的一門重要學(xué)科基礎(chǔ)課，是必修課。主要內(nèi)容包括：線性表、棧和隊(duì)列、用、數(shù)組和廣義表、樹(shù)、圖、查找算法和排序算法。數(shù)據(jù)結(jié)構(gòu)研究數(shù)據(jù)的組織方式，內(nèi)容豐富、學(xué)習(xí)量大，隱含在各部分內(nèi)容中的方法和技術(shù)多，

2、旨在讓學(xué)生掌握計(jì)算機(jī)軟件系統(tǒng)所必需的數(shù)據(jù)結(jié)構(gòu)的算法。要求學(xué)生掌握貫穿全課程的動(dòng)態(tài)鏈表存儲(chǔ)結(jié)構(gòu)，掌握算法設(shè)計(jì)的動(dòng)態(tài)性和抽象性。要求學(xué)生學(xué)會(huì)分析研究計(jì)算機(jī)加工的數(shù)據(jù)對(duì)象的特征，以便在實(shí)際應(yīng)用中選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和相應(yīng)算法，初步掌握算法的時(shí)間與空間性能分析技巧，并培養(yǎng)復(fù)雜程序設(shè)計(jì)的技能。二、本課程的重點(diǎn)和難點(diǎn)（一）課程的重點(diǎn)：數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)以及基本操作的概念及相互關(guān)系。線性表順序存儲(chǔ)實(shí)現(xiàn)中的創(chuàng)建、查找、插入和刪除等基本操作及相關(guān)算法。棧、隊(duì)列的定義、特點(diǎn)、性質(zhì)。數(shù)組的存儲(chǔ)表示方法，稀疏矩陣的壓縮存儲(chǔ)方法，廣義表的定義。二叉樹(shù)的定義、結(jié)構(gòu)特點(diǎn)和性質(zhì)，先序、中序、后序遍歷的遞歸和

3、非遞歸算法，二叉樹(shù)的線索化過(guò)程和算法，最優(yōu)二叉樹(shù)的特性及建立最優(yōu)二叉樹(shù)的算法，哈夫曼編碼的算法。圖的定義、術(shù)語(yǔ)、結(jié)構(gòu)特點(diǎn)和性質(zhì)，圖的鄰接矩陣、鄰接表的存儲(chǔ)結(jié)構(gòu)及其構(gòu)造方法，圖的深度優(yōu)先搜索和廣度優(yōu)先搜索算法，連通圖的最小生成樹(shù)算法，有向無(wú)環(huán)圖的拓?fù)渑判蛩惴?、關(guān)鍵路徑的算法，最短路徑求解中的Dijkstra算法和Floyed算法。簡(jiǎn)單插入排序、希爾排序、冒泡排序、快速排序、選擇排序、堆排序、歸并排序、基數(shù)排序算法。（二）課程的難點(diǎn)：抽象數(shù)據(jù)類型（ATD）的概念和實(shí)現(xiàn)方法，算法的時(shí)間復(fù)雜性和空間復(fù)雜性分析。線性表ADT鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)中的某些操作。棧和隊(duì)列在解決實(shí)際問(wèn)題中的應(yīng)用。二叉樹(shù)的先序、中序、后

4、序遍歷的非遞歸算法，二叉樹(shù)的線索化算法。有向無(wú)環(huán)圖的關(guān)鍵路徑算法，最短路徑求解中Floyed算法。二叉排序樹(shù)結(jié)點(diǎn)的刪除算法，二叉平衡樹(shù)的構(gòu)造算法。堆排序、歸并排序算法以及它們的時(shí)間復(fù)雜性和空間復(fù)雜性分析。三、主要實(shí)踐性教學(xué)環(huán)節(jié)及要求本課程主要依托教材所提供的課堂案例進(jìn)行實(shí)踐教學(xué)，通過(guò)每章節(jié)的學(xué)習(xí)，使用學(xué)生掌握所學(xué)章節(jié)知識(shí)在案例中的應(yīng)用。四、采用的教學(xué)手段和方法教學(xué)手段采用傳統(tǒng)教學(xué)手段和多媒體教學(xué)手段相結(jié)合的方式。課程教學(xué)在方法上，采用課堂講授，課后自學(xué)，課堂討論等多種教學(xué)形式。五、教材與主要參考文獻(xiàn)教材：數(shù)據(jù)結(jié)構(gòu)與算法（c+誠(chéng)）.唐寧九等編著.清華大學(xué)出版社主要參考文獻(xiàn)：數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）.

5、嚴(yán)蔚敏，吳偉民.清華大學(xué)出版社數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）.嚴(yán)蔚敏，李冬梅，吳偉民.人民郵電出版社六、考核形式與成績(jī)計(jì)算期末考試采用筆試形式，閉卷考試。總評(píng)成績(jī)由平時(shí)成績(jī)和期末成績(jī)組成，其中平時(shí)成績(jī)占30%期末考試占70%七、教學(xué)內(nèi)容和學(xué)時(shí)分配（一）第一章緒論2學(xué)時(shí)（課堂講授2學(xué)時(shí)）主要內(nèi)容：（1）數(shù)據(jù)結(jié)構(gòu)的一些基本概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)等。（2）抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)。（3）算法的概念和特性。（4）算法時(shí)間復(fù)雜度和空間復(fù)雜度的分析。教學(xué)要求：掌握數(shù)據(jù)結(jié)構(gòu)的基本概念，了解抽象數(shù)據(jù)類型，掌握算法時(shí)間復(fù)雜度和空間復(fù)雜度的分析方法。教學(xué)方法與手段：講授法重點(diǎn)、難點(diǎn)：算法的時(shí)間復(fù)雜度

6、和空間復(fù)雜度（二）第二章線性表2學(xué)時(shí)（課堂講授2學(xué)時(shí)）主要內(nèi)容：（1）線性表的類型定義。（2）線性表的順序表示和實(shí)現(xiàn)。（3）線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)。（4）線性表的應(yīng)用，包括無(wú)序表和有序表的合并、多項(xiàng)式的加法運(yùn)算等。教學(xué)要求：理解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著線性關(guān)系，在計(jì)算機(jī)中表示這種關(guān)系的兩類不同的存儲(chǔ)結(jié)構(gòu)是順序存儲(chǔ)結(jié)構(gòu)（順序表）和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（鏈表）。教學(xué)方法與手段：講授法、實(shí)驗(yàn)法重點(diǎn)、難點(diǎn)：兩類存儲(chǔ)結(jié)構(gòu)的描述方法，鏈表中的頭結(jié)點(diǎn)、頭指針和首元結(jié)點(diǎn)的區(qū)別及循環(huán)鏈表、雙向鏈表的特點(diǎn)等。順序表的查找、插入和刪除算法，鏈表的查找、插入和刪除算法。其它教學(xué)環(huán)節(jié)：實(shí)驗(yàn)內(nèi)容：?jiǎn)捂湵淼幕静僮?/p>

7、。實(shí)驗(yàn)要求：實(shí)現(xiàn)帶頭結(jié)點(diǎn)的單鏈表的查找、插入和刪除等算法。（三）第三章棧和隊(duì)列8學(xué)時(shí)（課堂講授6學(xué)時(shí)+課程實(shí)驗(yàn)2學(xué)時(shí)）主要內(nèi)容：（1）棧的類型定義，棧的順序存儲(chǔ)和鏈接存儲(chǔ)的表示和實(shí)現(xiàn)。（2）棧與遞歸的實(shí)現(xiàn)，遞歸程序轉(zhuǎn)換為非遞歸程序的方法。（3）隊(duì)列的類型，隊(duì)列的順序存儲(chǔ)（循環(huán)隊(duì)）和鏈接存儲(chǔ)的表示和實(shí)現(xiàn)。教學(xué)要求：掌握棧和隊(duì)列的特點(diǎn)，并能在相應(yīng)的應(yīng)用問(wèn)題中正確選用。教學(xué)方法與手段：講授法、實(shí)驗(yàn)法重點(diǎn)、難點(diǎn)：棧的順序棧和鏈棧的進(jìn)棧出棧算法，特別應(yīng)注意棧滿和棧空的條件。循環(huán)隊(duì)列和鏈隊(duì)列的進(jìn)隊(duì)出隊(duì)算法，特別是循環(huán)隊(duì)列中隊(duì)頭與隊(duì)尾指針的變化情況。其它教學(xué)環(huán)節(jié)：實(shí)驗(yàn)內(nèi)容：棧的應(yīng)用。實(shí)驗(yàn)要求：借助棧來(lái)解決某

8、些實(shí)際應(yīng)用問(wèn)題,如表達(dá)式求值、迷宮問(wèn)題等。（四）第四章用4學(xué)時(shí)（課堂講授4學(xué)時(shí)）主要內(nèi)容：（1）用類型的定義。（2）用的表示和實(shí)現(xiàn)，包括順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)表示。（3）數(shù)組的存儲(chǔ)方法。教學(xué)要求：了解用的順序存儲(chǔ)結(jié)構(gòu)和堆存儲(chǔ)結(jié)構(gòu)。教學(xué)方法與手段：講授法、討論法重點(diǎn)、難點(diǎn)：用的設(shè)計(jì)、實(shí)現(xiàn)方法和基本操作。（五）第五章數(shù)組和廣義表6學(xué)時(shí)（課堂講授6學(xué)時(shí)）主要內(nèi)容：（1）數(shù)組的定義（2）矩陣及特殊矩陣（3）廣義表的概念教學(xué)要求：掌握數(shù)組和廣義表的概念，掌握特殊矩陣的存儲(chǔ)方法，掌握廣義表的概念及存儲(chǔ)結(jié)構(gòu)。教學(xué)方法與手段：講授法、討論法重點(diǎn)、難點(diǎn)：數(shù)組的順序存儲(chǔ)方式，特殊矩陣，廣義表的存儲(chǔ)結(jié)構(gòu)(六)第六章樹(shù)和

9、二叉樹(shù)10學(xué)時(shí)(課堂講授8學(xué)時(shí)+課程實(shí)驗(yàn)2學(xué)時(shí))主要內(nèi)容：(1)二叉樹(shù)的定義和術(shù)語(yǔ)，二叉樹(shù)的性質(zhì)，特殊的二叉樹(shù)。(2)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，順序存儲(chǔ)和二叉鏈表。(3)二叉樹(shù)的的前序、中序、后序、層次遍歷方法。線索化二叉樹(shù)。(4)樹(shù)和森林的定義，樹(shù)的存儲(chǔ)，樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換。(5)樹(shù)的應(yīng)用，哈夫曼樹(shù)及哈夫曼編碼。教學(xué)要求：了解樹(shù)和森林的概念，包括樹(shù)的定義、樹(shù)的術(shù)語(yǔ)。掌握二叉樹(shù)的概念、性質(zhì)及二叉樹(shù)的表示。掌握線索化二叉樹(shù)的特性及尋找某結(jié)點(diǎn)的前驅(qū)和后繼的方法。了解樹(shù)的存儲(chǔ)、樹(shù)和森林與二叉樹(shù)的轉(zhuǎn)換方法。教學(xué)方法與手段：講授法、實(shí)驗(yàn)法重點(diǎn)、難點(diǎn)：二叉樹(shù)的遍歷算法，哈夫曼樹(shù)的實(shí)現(xiàn)方法、構(gòu)造哈夫曼編碼的方法

10、及帶權(quán)路徑長(zhǎng)度的計(jì)算。其它教學(xué)環(huán)節(jié)：實(shí)驗(yàn)內(nèi)容：二叉樹(shù)的基本算法。實(shí)驗(yàn)要求：利用二叉鏈表方法建立二叉樹(shù)，實(shí)現(xiàn)二叉樹(shù)的前、中、后序三種遍歷算法，并運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹(shù)的其他操作，如計(jì)算二叉樹(shù)結(jié)點(diǎn)個(gè)數(shù)、葉子結(jié)點(diǎn)個(gè)數(shù)、二叉樹(shù)的高度等。(七)第七章圖10學(xué)時(shí)(課堂講授8學(xué)時(shí)+課程實(shí)驗(yàn)2學(xué)時(shí))主要內(nèi)容：(1)圖的定義和術(shù)語(yǔ)。(2)圖的存儲(chǔ)結(jié)構(gòu)兩種存儲(chǔ)結(jié)構(gòu)：鄰接矩陣和鄰接表表示法。(3)圖的兩種遍歷策略：深度優(yōu)先搜索和廣度優(yōu)先搜索。(4)構(gòu)造最小生成樹(shù)的兩種算法：普里姆算法和克魯斯卡爾算法。(5)拓?fù)渑判蚝完P(guān)鍵路徑。(6)兩類求最短路徑問(wèn)題的算法，迪杰斯特拉算法和弗洛伊德算法。教學(xué)要求：掌握?qǐng)D的基本概念及

11、相關(guān)術(shù)語(yǔ)和性質(zhì)，掌握?qǐng)D的鄰接矩陣和鄰接表表示法，了解實(shí)際問(wèn)題的求解效率與采用何種存儲(chǔ)結(jié)構(gòu)和算法有密切聯(lián)系。了解關(guān)鍵路徑的概念和求解方法，了解弗洛伊德算法。教學(xué)方法與手段：講授法、實(shí)驗(yàn)法重點(diǎn)、難點(diǎn)：圖的兩種搜索路徑的遍歷：深度優(yōu)先搜索和廣度優(yōu)先搜索的算法構(gòu)造最小生成樹(shù)的兩種算法及拓?fù)渑判蛩惴ǖ乃枷?，迪杰斯特拉算法。其它教學(xué)環(huán)節(jié)：實(shí)驗(yàn)內(nèi)容：圖的建立和搜索。實(shí)驗(yàn)要求：使用鄰接矩陣或鄰接表表示法存儲(chǔ)一個(gè)圖，實(shí)現(xiàn)圖的深度優(yōu)先搜索和廣度優(yōu)先搜索的算法。(八)第八章查找6學(xué)時(shí)(課堂講授6學(xué)時(shí))主要內(nèi)容：(1)查找的基本概念，平均查找長(zhǎng)度。(2)基于線性表的查找：順序查找、折半查找。(3)基于樹(shù)表的查找：二叉

12、排序樹(shù)、平衡二叉樹(shù)、B-樹(shù)和B+W。(4)散列表：散列表的基本概念，散列函數(shù)的構(gòu)造方法、處理沖突的方法、散列表的查找與分析。教學(xué)要求：熟練掌握順序表和有序表的查找方法及其實(shí)現(xiàn)，掌握二叉排序樹(shù)的插入和查找算法及其實(shí)現(xiàn)，了解平衡二叉樹(shù)、B-樹(shù)和B+W的各種操作。教學(xué)方法與手段：講授法、討論法重點(diǎn)、難點(diǎn)：散列表的構(gòu)造方法、處理沖突的方法。折半查找過(guò)程的判定樹(shù)的構(gòu)造方法，以及按定義計(jì)算各種查找方法在等概率情況下查找成功時(shí)的平均查找長(zhǎng)度。(九)第九章排序6學(xué)時(shí)(課堂講授6學(xué)時(shí))主要內(nèi)容：(1)排序的基本概念，包括正序，逆序，穩(wěn)定性，排序方法的分類。(2)插入排序：直接插入排序、折半插入排序和希爾排序。(3)交換排序：冒泡排序和快速排序。(4)選擇排序：簡(jiǎn)單選擇排序和堆排序。(5)歸并排序：2-路歸并排序。(6)基數(shù)排序：多關(guān)鍵字的排序和鏈數(shù)基數(shù)排序。(7)排序算法分析：各種排序算法的比較和移動(dòng)次數(shù)，時(shí)間復(fù)雜度和空間復(fù)雜度的分析。教學(xué)要求：