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

數(shù)據(jù)結(jié)構(gòu)教學(xué)大綱一、本大綱適用專業(yè)本大綱適用于計算機(jī)科學(xué)與技術(shù)本科專業(yè)。二、編寫本教學(xué)大綱的說明（一）課程類別與教學(xué)任務(wù)《數(shù)據(jù)結(jié)構(gòu)》是介于數(shù)學(xué)、計算機(jī)硬件和計算機(jī)軟件之間的一門計算機(jī)科學(xué)與技術(shù)專業(yè)的核心課程，是操作系統(tǒng)、數(shù)據(jù)庫原理、編譯原理、軟件工程、人工智能等課程的基礎(chǔ)。數(shù)據(jù)結(jié)構(gòu)技術(shù)廣泛應(yīng)用于信息科學(xué)、系統(tǒng)工程、應(yīng)用數(shù)學(xué)以及各種工程技術(shù)領(lǐng)域。通過本課程的學(xué)習(xí)，使學(xué)生了解軟件分析階段、設(shè)計階段、編碼階段的若干基本問題，明確數(shù)據(jù)結(jié)構(gòu)的內(nèi)容包括抽象、實(shí)現(xiàn)和評價三個層次，即五個基本組成“要素”邏輯結(jié)構(gòu)，存儲結(jié)構(gòu)、基本運(yùn)算、算法及不同數(shù)據(jù)結(jié)構(gòu)的比較與算法分析，初步具備分析問題、解決問題的能力，養(yǎng)成良好的程序設(shè)計風(fēng)格。為學(xué)生在此領(lǐng)域中繼續(xù)學(xué)習(xí)和研究打下堅實(shí)的基礎(chǔ)。（二）本課程的基本要求1.

了解數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語、掌握算法描述、算法分析方法。2.

掌握線性表的抽象數(shù)據(jù)類型定義，線性表的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，及線性表的各種運(yùn)算的實(shí)現(xiàn)技巧。3.

掌握棧和隊(duì)列這兩種最常用數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)，初步掌握棧和隊(duì)列的運(yùn)用技巧，應(yīng)用方法。4.掌握串的基本概念、串的基本操作和存儲結(jié)構(gòu)，理解串的模式匹配算法和改進(jìn)的KMP算法。5.

掌握數(shù)組的定義、順序存儲表示與實(shí)現(xiàn)，掌握幾種特殊矩陣的存儲方法，掌握廣義表的概念及存儲的實(shí)現(xiàn)。6.

掌握樹和二叉樹的概念、存儲結(jié)構(gòu)，基本運(yùn)算及其遍歷，掌握哈夫曼樹的概念和構(gòu)造方法以及哈夫曼編碼的概念。7.

掌握圖的有關(guān)概念、存儲結(jié)構(gòu)、遍歷算法、生成樹的求法以及拓?fù)渑判虻母拍罴扒蠓ā?.

掌握靜態(tài)查找表、動態(tài)查找表及哈希表的概念、存儲結(jié)構(gòu)、及實(shí)現(xiàn)方法。9.

掌握各類排序的方法，算法的性能分析，應(yīng)用特點(diǎn)。（三）本課程的重點(diǎn)和難點(diǎn)1.

數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語，算法的時間復(fù)雜度分析；2.

線性表的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及線性表的各種運(yùn)算的實(shí)現(xiàn)技巧；3.

棧和隊(duì)列的數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)，運(yùn)用技巧，應(yīng)用方法；4.

串的基本概念、串的基本操作和存儲結(jié)構(gòu)，理解串的模式匹配算法和改進(jìn)的KMP算法。5.

數(shù)組的定義、順序存儲表示與實(shí)現(xiàn)，特殊矩陣的存儲方法，廣義表的概念及存儲的實(shí)現(xiàn)；6.

樹和二叉樹的概念、存儲結(jié)構(gòu)，基本運(yùn)算及樹的遍歷，哈夫曼樹的概念和構(gòu)造方法；7.

圖的有關(guān)概念、存儲結(jié)構(gòu)、遍歷算法、生成樹的求法以及拓?fù)渑判虻母拍罴扒蠓?，最短路徑的概念及其?shí)現(xiàn)算法；8.

各類排序的方法，算法的性能分析。（四）本課程與其他相關(guān)課程的聯(lián)系和后續(xù)課程先修課程：《高級程序設(shè)計語言》、《離散數(shù)學(xué)》（五）學(xué)時、學(xué)時分配安排本課程理論課時為54課時，18個課時的實(shí)踐課時，具體學(xué)時安排見教學(xué)內(nèi)容。（六）本課程的教學(xué)方式及其它教學(xué)環(huán)節(jié)的安排本課程采用通常的課堂教學(xué)方式，并注重理論與實(shí)踐相結(jié)合的方法，即以教師的課堂教授為主，同時輔以學(xué)生課外實(shí)踐，培養(yǎng)與提高學(xué)生對本學(xué)科的興趣和研究能力。三、教學(xué)基本內(nèi)容和學(xué)時分配第1章

緒論（3課時）1．什么是數(shù)據(jù)結(jié)構(gòu)2．基本概念和術(shù)語3．抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)4．算法和算法分析第2章

線性表（3課時）1．線性表的類型和定義2．線性表的順序表示和實(shí)現(xiàn)3．線性表的鏈?zhǔn)酱鎯蛯?shí)現(xiàn)4．一元多項(xiàng)式的表示及相加第3章

棧和隊(duì)列（6課時）1．棧的定義及實(shí)現(xiàn)2．棧的應(yīng)用3．隊(duì)列的定義及實(shí)現(xiàn)4．隊(duì)列的應(yīng)用第四章串（3課時）1.

串的基本概念、串的基本操作和存儲結(jié)構(gòu)2.

串的模式匹配算法和改進(jìn)的KMP算法第5章

數(shù)組和廣義表（3課時）1．?dāng)?shù)組的類型定義2．?dāng)?shù)組的順序表示和實(shí)現(xiàn)3．矩陣的壓縮存儲第6章

樹和二叉樹（9課時）1．樹的定義和基本術(shù)語2．二叉樹3．遍歷二叉樹和線索二叉樹4．樹和森林5．哈夫曼樹及其應(yīng)用第7章

圖（12課時）1．圖的定義和術(shù)語2.

圖的存儲結(jié)構(gòu)3．圖的遍歷4．圖的連通性問題5．有向無回圖及其應(yīng)用6．最短路徑第9章

查找（6課時）1.

靜態(tài)查找表2.

動態(tài)查找表3.

哈希表第10章

內(nèi)部排序（9課時）1．概述2．插入排序3．快速排序4.

選擇排序5.

歸并排序6.

各類內(nèi)部排序方法的比較討論上機(jī)實(shí)踐及內(nèi)容1.

線性表操作（鏈表）——插入、刪除、合并、查找（4課時）2.

樹和二叉樹的應(yīng)用

——建立二叉樹、遍歷二叉樹（4課時）3.

圖的應(yīng)用

——尋找兩頂點(diǎn)間邊數(shù)最少的一條路徑（4課時）4.

查找

——靜態(tài)、動態(tài)查找算法（2課時）5.

排序

——數(shù)組、鏈表排序算法（4課時）四、教材與教學(xué)參考書教材：《數(shù)據(jù)結(jié)構(gòu)》（C語言版）

嚴(yán)蔚敏吳偉民編著清華大學(xué)出版社教學(xué)參考書：1.

《數(shù)據(jù)結(jié)