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

1、數(shù)據(jù)結(jié)構(gòu)一、課程說明課程編號： 390106X10課程名稱（中/英文）：數(shù)據(jù)結(jié)構(gòu)/Data Structures課程類別：學(xué)科基礎(chǔ)課學(xué)時/學(xué)分：48/3先修課程：離散數(shù)學(xué)、C語言程序設(shè)計(jì)、計(jì)算機(jī)基礎(chǔ)適用專業(yè)：軟件工程 教材、教學(xué)參考書：1數(shù)據(jù)結(jié)構(gòu)(C語言版).嚴(yán)蔚敏，吳偉民 北京：清華大學(xué)出版社，20112數(shù)據(jù)結(jié)構(gòu)(Java語言描述). 劉小晶,杜選，北京：清華大學(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ǔ)課，是一門綜合性、理論性和實(shí)踐性較強(qiáng)的課程。本課程是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間的一門核心課程，是設(shè)計(jì)和實(shí)現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其它系統(tǒng)程序和大型應(yīng)用程序的重要基礎(chǔ)。本課程從客觀世界的計(jì)算機(jī)描述入手，講述數(shù)據(jù)對象在計(jì)算機(jī)中的形式表達(dá)、邏輯關(guān)系以及相關(guān)基本操作，要求學(xué)生初步掌握數(shù)據(jù)表達(dá)、數(shù)據(jù)存儲以及數(shù)據(jù)操作的基本理論與方法，

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

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

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

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

7、業(yè)素質(zhì)、敬業(yè)精神和職業(yè)道德；對應(yīng)培養(yǎng)方案“培養(yǎng)要求”3-。四、教學(xué)內(nèi)容、重點(diǎn)難點(diǎn)及教學(xué)設(shè)計(jì)章節(jié)教學(xué)內(nèi)容總學(xué)時學(xué)時分配教學(xué)重點(diǎn)教學(xué)難點(diǎn)教學(xué)方案設(shè)計(jì)（含教學(xué)方法、教學(xué)手段）講課(含研討)實(shí)踐第1章緒論440數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及數(shù)據(jù)運(yùn)算、算法時間和空間復(fù)雜度分析算法時間復(fù)雜度分析教學(xué)思路：通過對經(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é)思路：通過對現(xiàn)實(shí)實(shí)例的講述，然后引出線性表的研究內(nèi)容，并課堂討論

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

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

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

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