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

1、數(shù)據(jù)結(jié)構(gòu)一、課程說(shuō)明課程編號(hào)： 390106X10課程名稱（中/英文）：數(shù)據(jù)結(jié)構(gòu)/Data Structures課程類別：學(xué)科基礎(chǔ)課學(xué)時(shí)/學(xué)分：48/3先修課程：離散數(shù)學(xué)、C語(yǔ)言程序設(shè)計(jì)、計(jì)算機(jī)基礎(chǔ)適用專業(yè)：軟件工程 教材、教學(xué)參考書(shū)：1數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版).嚴(yán)蔚敏，吳偉民 北京：清華大學(xué)出版社，20112數(shù)據(jù)結(jié)構(gòu)(Java語(yǔ)言描述). 劉小晶,杜選，北京：清華大學(xué)出版社，20113Data Structures and Algorithms. Adam Drozdek, 20044Data Structures & Algorithm Analysis in C+. Mark A.

2、Weiss, 20135Data Structures and Algorithm Analysis in C+ 3rd Edition, Clifford A.Shaffer,2013二、課程設(shè)置的目的意義數(shù)據(jù)結(jié)構(gòu)是軟件工程本科專業(yè)的綜合性的專業(yè)基礎(chǔ)課，是一門(mén)綜合性、理論性和實(shí)踐性較強(qiáng)的課程。本課程是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間的一門(mén)核心課程，是設(shè)計(jì)和實(shí)現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫(kù)系統(tǒng)及其它系統(tǒng)程序和大型應(yīng)用程序的重要基礎(chǔ)。本課程從客觀世界的計(jì)算機(jī)描述入手，講述數(shù)據(jù)對(duì)象在計(jì)算機(jī)中的形式表達(dá)、邏輯關(guān)系以及相關(guān)基本操作，要求學(xué)生初步掌握數(shù)據(jù)表達(dá)、數(shù)據(jù)存儲(chǔ)以及數(shù)據(jù)操作的基本理論與方法，

3、了解軟件開(kāi)發(fā)的基本原理，通過(guò)本課程的學(xué)習(xí)，使學(xué)生初步建立的邏輯分析、抽象思維和程序設(shè)計(jì)的能力，培養(yǎng)學(xué)生具有優(yōu)良的程序設(shè)計(jì)風(fēng)格，為更深入地學(xué)習(xí)和今后從事軟件工程實(shí)踐打下良好的基礎(chǔ)。三、課程的基本要求通過(guò)本課程的學(xué)習(xí)，要求學(xué)生能夠掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)以及其他結(jié)構(gòu)定義的各種運(yùn)算及應(yīng)用。對(duì)同一種邏輯結(jié)構(gòu)的數(shù)據(jù)，討論其不同的物理結(jié)構(gòu)和相應(yīng)的有關(guān)算法；要求學(xué)生學(xué)會(huì)分析、研究計(jì)算機(jī)加工的數(shù)據(jù)對(duì)象特性，以便選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)以及相應(yīng)的算法，并初步掌握算法的時(shí)間分析和空間分析方法。此外，學(xué)習(xí)本課程的過(guò)程也是進(jìn)行程序設(shè)計(jì)的訓(xùn)練過(guò)程，所以要求學(xué)生書(shū)寫(xiě)的算法結(jié)構(gòu)清楚，正確易讀。具體要求如下：（一）知識(shí)學(xué)習(xí)要求

4、1. 理解掌握數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語(yǔ)，算法的描述和算法分析基本方法；對(duì)應(yīng)培養(yǎng)方案“培養(yǎng)要求”1-和1-；2. 熟練掌握線性表的邏輯結(jié)構(gòu)，線性表的順序存儲(chǔ)結(jié)構(gòu)，線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，一元多項(xiàng)式的表示及相加；對(duì)應(yīng)培養(yǎng)方案“培養(yǎng)要求”1-；3. 熟練掌握棧和隊(duì)列的基本概念、存儲(chǔ)方式，運(yùn)用棧結(jié)構(gòu)實(shí)現(xiàn)表達(dá)式求值，熟悉棧與遞歸過(guò)程的關(guān)系，以及隊(duì)列與離散事件模擬；對(duì)應(yīng)培養(yǎng)方案“培養(yǎng)要求”1-；4. 熟練掌握樹(shù)和二叉樹(shù)：樹(shù)的結(jié)構(gòu)定義和基本操作，二叉樹(shù)，遍歷二叉樹(shù)和線索二叉樹(shù)，樹(shù)和森林，哈夫曼樹(shù)及其應(yīng)用；對(duì)應(yīng)培養(yǎng)方案“培養(yǎng)要求”1-；5. 掌握?qǐng)D的定義及術(shù)語(yǔ)，圖的存儲(chǔ)結(jié)構(gòu)，圖的遍歷操作；理解圖的連通性問(wèn)題，有

5、向無(wú)環(huán)圖及其應(yīng)用，最短路徑等相關(guān)應(yīng)用；對(duì)應(yīng)培養(yǎng)方案“培養(yǎng)要求”1-B；6. 掌握查找與排序的基本概念、基本方法，熟悉理解經(jīng)典的查找算法、內(nèi)排序算法，理解不同排序算法的優(yōu)缺點(diǎn)，以及選擇應(yīng)用的標(biāo)準(zhǔn)。對(duì)應(yīng)培養(yǎng)方案“培養(yǎng)要求”1-和1-；（二）能力培養(yǎng)要求1. 掌握程序設(shè)計(jì)的基本方法、算法設(shè)計(jì)與分析的基本方法，算法時(shí)間、空間復(fù)雜度的分析能力；對(duì)應(yīng)培養(yǎng)方案“培養(yǎng)要求”2-A；2. 應(yīng)用線性表解決復(fù)雜軟件工程問(wèn)題，設(shè)計(jì)使用堆棧和隊(duì)列相關(guān)算法的設(shè)計(jì)的能力，掌握程序設(shè)計(jì)的基本方法、軟件建模方法；對(duì)應(yīng)培養(yǎng)方案“培養(yǎng)要求”2-和2-；3. 具備基于樹(shù)結(jié)構(gòu)設(shè)計(jì)算法的能力，應(yīng)用樹(shù)結(jié)構(gòu)解決復(fù)雜工程問(wèn)題的能力；對(duì)應(yīng)培養(yǎng)方

6、案“培養(yǎng)要求”2-和2-；4. 具備基于圖結(jié)構(gòu)設(shè)計(jì)算法的能力，應(yīng)用圖結(jié)構(gòu)解決復(fù)雜工程問(wèn)題的能力。對(duì)應(yīng)培養(yǎng)方案“培養(yǎng)要求”2-和2-；5. 具備排序相關(guān)算法的設(shè)計(jì)能力，掌握各排序算法的特點(diǎn)，能在不同場(chǎng)合選擇最合適的排序算法解決問(wèn)題的能力；對(duì)應(yīng)培養(yǎng)方案“培養(yǎng)要求”2-和2-；6. 具備查找算法的設(shè)計(jì)能力，掌握各查找算法的特點(diǎn)，根據(jù)工程問(wèn)題的性質(zhì)選擇最佳查找算法并解決問(wèn)題的能力；對(duì)應(yīng)培養(yǎng)方案“培養(yǎng)要求”2-和2-。（三）素質(zhì)培養(yǎng)要求1. 能夠針對(duì)具體的數(shù)據(jù)要求，使用批判性思維方法，不斷完善和豐富數(shù)據(jù)結(jié)構(gòu)；對(duì)應(yīng)培養(yǎng)方案“培養(yǎng)要求”3-；2. 能夠從描述現(xiàn)實(shí)數(shù)據(jù)的多個(gè)角度思考開(kāi)發(fā)的軟件程序，培養(yǎng)基本的職

7、業(yè)素質(zhì)、敬業(yè)精神和職業(yè)道德；對(duì)應(yīng)培養(yǎng)方案“培養(yǎng)要求”3-。四、教學(xué)內(nèi)容、重點(diǎn)難點(diǎn)及教學(xué)設(shè)計(jì)章節(jié)教學(xué)內(nèi)容總學(xué)時(shí)學(xué)時(shí)分配教學(xué)重點(diǎn)教學(xué)難點(diǎn)教學(xué)方案設(shè)計(jì)（含教學(xué)方法、教學(xué)手段）講課(含研討)實(shí)踐第1章緒論440數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及數(shù)據(jù)運(yùn)算、算法時(shí)間和空間復(fù)雜度分析算法時(shí)間復(fù)雜度分析教學(xué)思路：通過(guò)對(duì)經(jīng)典軟件程序、算的實(shí)例講述軟件、數(shù)據(jù)結(jié)構(gòu)、算法之間的關(guān)系，然后引出數(shù)據(jù)結(jié)構(gòu)的有關(guān)概念，再概述算法分析的主要內(nèi)容，并課堂討論數(shù)據(jù)結(jié)構(gòu)的難點(diǎn)。教學(xué)方法：調(diào)查分析、講授、課堂討論第2章線性表1082線性表的基本概念、以及線性表的實(shí)現(xiàn)方式單鏈表教學(xué)思路：通過(guò)對(duì)現(xiàn)實(shí)實(shí)例的講述，然后引出線性表的研究?jī)?nèi)容，并課堂討論

8、線性表的性質(zhì)特點(diǎn)和難點(diǎn)，并要求學(xué)生通過(guò)實(shí)踐理解線性表的設(shè)計(jì)和使用。教學(xué)方法：講授、案例分析教學(xué)手段：PPT、軟件設(shè)計(jì)工具第3章棧和隊(duì)列12102堆棧和隊(duì)列的定義及其應(yīng)用棧的應(yīng)用教學(xué)思路：通過(guò)對(duì)現(xiàn)實(shí)實(shí)例的講述，然后引出棧和隊(duì)列的研究?jī)?nèi)容，并課堂討論棧和隊(duì)列的性質(zhì)特點(diǎn)和難點(diǎn)，并要求學(xué)生通過(guò)實(shí)踐理解棧和隊(duì)列的設(shè)計(jì)和使用。教學(xué)方法：講授、案例分析教學(xué)手段：PPT、軟件設(shè)計(jì)工具第4章樹(shù)和二叉樹(shù)12102二叉樹(shù)定義和主要性質(zhì)；二叉樹(shù)鏈接存儲(chǔ)及操作；樹(shù)與森林的遍歷；哈夫曼樹(shù)二叉樹(shù)遍歷教學(xué)思路：通過(guò)對(duì)現(xiàn)實(shí)實(shí)例的講述，然后引出樹(shù)和二叉樹(shù)的研究?jī)?nèi)容，并課堂討論樹(shù)和二叉樹(shù)性質(zhì)特點(diǎn)和難點(diǎn)，并要求學(xué)生通過(guò)實(shí)踐理解二叉樹(shù)

9、的設(shè)計(jì)和使用。教學(xué)方法：講授、案例分析教學(xué)手段：PPT、軟件設(shè)計(jì)工具第5章圖44圖的鄰接矩陣和鄰接表存儲(chǔ)；圖的深度優(yōu)先和廣度優(yōu)先遍歷；最短路徑問(wèn)題圖的遍歷教學(xué)思路：通過(guò)對(duì)現(xiàn)實(shí)實(shí)例的講述，然后引出圖的研究?jī)?nèi)容，并課堂討論圖結(jié)構(gòu)性質(zhì)特點(diǎn)和難點(diǎn)，并要求學(xué)生通過(guò)實(shí)踐理解圖的相關(guān)算法的設(shè)計(jì)和使用。教學(xué)方法：講授、案例分析教學(xué)手段：PPT、軟件設(shè)計(jì)工具第6章查找與排序642Shell排序；快速排序；堆排序；合并排序；有序表順序查找；對(duì)半查找；散列函數(shù)及沖突調(diào)解快速排序、哈希查找教學(xué)思路：通過(guò)對(duì)案例講解講述，分別介紹相關(guān)排序算法的設(shè)計(jì)思想，并課堂討論算法的相關(guān)性能指標(biāo)，并要求學(xué)生通過(guò)實(shí)踐理解每個(gè)算法的實(shí)現(xiàn)。

10、教學(xué)方法：講授、案例分析教學(xué)手段：PPT、軟件設(shè)計(jì)工具注：實(shí)踐包括實(shí)驗(yàn)、上機(jī)等五、實(shí)踐教學(xué)內(nèi)容和基本要求要求學(xué)生針對(duì)具體實(shí)驗(yàn)中的數(shù)據(jù)實(shí)現(xiàn)其邏輯、物理等結(jié)構(gòu)，且能根據(jù)不同數(shù)據(jù)對(duì)象，選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)及相應(yīng)的算法。同時(shí)要求學(xué)生書(shū)寫(xiě)的算法結(jié)構(gòu)清楚，可讀性強(qiáng)。著重訓(xùn)練學(xué)生掌握本單元講授的數(shù)據(jù)結(jié)構(gòu)和算法的應(yīng)用。課內(nèi)實(shí)驗(yàn)內(nèi)容如下表所示。實(shí)驗(yàn)名稱實(shí)驗(yàn)內(nèi)容學(xué)時(shí)基本要求線性表的操作線性表基本操作的實(shí)現(xiàn)，分別采用數(shù)組和鏈表結(jié)構(gòu)實(shí)現(xiàn)線性表，實(shí)現(xiàn)線性表的基本操作。2編寫(xiě)、上機(jī)運(yùn)行程序、保存和打印出程序的運(yùn)行結(jié)果，并結(jié)合程序進(jìn)行分析。棧的基本操作利用棧的基本操作，設(shè)計(jì)一個(gè)程序，實(shí)現(xiàn)用算符優(yōu)先法對(duì)算術(shù)表達(dá)式求值的過(guò)程。2

11、認(rèn)真閱讀和掌握本實(shí)驗(yàn)的算法、上機(jī)將本算法實(shí)現(xiàn)、保存和打印出程序的運(yùn)行結(jié)果，并結(jié)合程序進(jìn)行分析。在程序的編寫(xiě)中，力求設(shè)計(jì)代碼以及注釋等規(guī)范。二叉樹(shù)的基本操作以二叉鏈表作存儲(chǔ)結(jié)構(gòu)，采用遞歸和非遞歸的編程方法編寫(xiě)程序，實(shí)現(xiàn)二叉樹(shù)的基本功能。2認(rèn)真閱讀和掌握本實(shí)驗(yàn)的算法、上機(jī)將本算法實(shí)現(xiàn)、保存和打印出程序的運(yùn)行結(jié)果，并結(jié)合程序進(jìn)行分析。在程序的編寫(xiě)中，力求設(shè)計(jì)代碼以及注釋等規(guī)范。快速排序?qū)崿F(xiàn)排序的各算法、用多組數(shù)據(jù)對(duì)編寫(xiě)的排序算法進(jìn)行測(cè)試，記錄運(yùn)算時(shí)間，分析算法效率。2認(rèn)真閱讀和掌握本實(shí)驗(yàn)的算法、上機(jī)將本算法實(shí)現(xiàn)、保存和打印出程序的運(yùn)行結(jié)果，并結(jié)合程序進(jìn)行分析。在程序的編寫(xiě)中，力求設(shè)計(jì)代碼以及注釋等規(guī)范。要求在課外，學(xué)生能針對(duì)一個(gè)具體實(shí)際的案例，通過(guò)團(tuán)隊(duì)協(xié)作，采用結(jié)構(gòu)化軟件開(kāi)發(fā)方法和面向?qū)ο筌浖_(kāi)發(fā)方法完成案例項(xiàng)目的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)、軟件系統(tǒng)基本功能的開(kāi)發(fā)，提交規(guī)范、清晰的軟件文檔，并