附表1-1 理論課程教學大綱

1、理論課程教學大綱課程名稱數(shù)據(jù)結構英文名稱DataStructures課程編號不填總學時60學分不填預修課程C語言開課學期不填大綱撰寫人黃劉生一、教學目標和基本要求?目的：目的：使學生較全面地掌握各種常用的數(shù)據(jù)結構，提高其數(shù)據(jù)抽象和程序設計能力為學習后續(xù)軟件課程提供堅實的基礎。?基本要求：基本要求：使學生能夠從邏輯結構、存儲結構和數(shù)據(jù)的運算三個方面去掌握各種數(shù)據(jù)結構的特性對算法的時、空復雜性有一定的分析能力，使之能夠針對具體的應用問題，選

2、擇合適的數(shù)據(jù)結構及設計結構清晰、正確有效的算法解決之。二、課程簡介數(shù)據(jù)結構是計算機學科一門重要的專業(yè)基礎課，該課程系統(tǒng)地討論各種常用的數(shù)據(jù)結構及其應用，以及查找和排序的各種方法及其綜合分析比較，培養(yǎng)學生數(shù)據(jù)抽象和程序設計的能力，算法時、空復雜性的分析能力。三、教學重點、難點1概論：概論：重點是了解數(shù)據(jù)結構的邏輯結構、存儲結構及數(shù)據(jù)的運算三方面的概念及其相互關系，難點是抽象數(shù)據(jù)類型和算法復雜度的分析方法。2線性表：線性表：重點是熟練掌握順

3、序表和單鏈表上實現(xiàn)的各種基本算法及相關的時間性能分析，難點是能夠使用所學到的基本知識設計有效算法解決與線性表相關的應用問題。3棧和隊列：棧和隊列：重點是掌握棧和隊列在兩種存儲結構上實現(xiàn)的基本運算，難點是循環(huán)隊列中對邊界條件的處理。4串：串：重點是掌握串上實現(xiàn)的模式匹配算法，這也是本章的難點。5樹：樹：重點掌握二叉樹的遍歷算法及其有關應用，難點是使用本章所學到的有關知識設計出有效算法解決與樹或二叉樹相關的應用問題。6圖：圖：重點掌握圖在鄰

4、接矩陣與鄰近表上實現(xiàn)的遍歷算法。難點是求圖的最小生成樹、最短路徑、拓撲排序等應用算法及其時間性能分析。7動態(tài)存儲管理動態(tài)存儲管理:重點是內存空間的分配與回收算法，以及可利用空間表的結構。本章難點是無用單元收集算法的理解與掌握。8查找：查找：重點掌握順序查找、二分查找、二叉查找樹上查找以及散列表上查找的基本思想和算法實現(xiàn)。本章難點是二叉查找樹的刪除算法及B樹上的插入和刪除算法。9文件：文件：本章重點是介紹存儲在外存上的數(shù)據(jù)結構（文件）的有

5、關概念、各種文件的特點、組織方法及查詢和更新操作。四、教材名稱及主要參考書《數(shù)據(jù)結構C語言版》嚴蔚敏、吳偉民，清華大學出版社，2000?！稊?shù)據(jù)結構第2版》黃劉生、唐策善，中國科技大學出版社，2001?！癉ataStructureswithC“WilliawFdetal.PrenticeHallInc.1996.“DataStructures&ProgramDesigninC2ndEd.“RobertKruseetal.PrenticeH

6、allInc.1997.五、課程章節(jié)主要內容及學時分配第一章第一章概論（3學時）第一節(jié)基本概念和術語第二節(jié)學習數(shù)據(jù)結構的意義第三節(jié)抽象數(shù)據(jù)類型第四節(jié)算法的描述和分析第二章第二章線性表線性表（6學時）第一節(jié)線性表的邏輯結構第二節(jié)線性表的順序存貯結構第三節(jié)線性表的鏈式存貯結構第四節(jié)順序表和鏈表的比較第三章第三章棧和隊列棧和隊列（6學時）第一節(jié)棧第二節(jié)隊列第三節(jié)棧與隊列的應用實例第四章第四章串（4學時）第一節(jié)串及其運算第二節(jié)串的存貯結構第三節(jié)

7、串的模式匹配第六章第六章樹（10學時）第一節(jié)樹的概念第二節(jié)二叉樹第三節(jié)二叉樹的遍歷第四節(jié)線索二叉樹第五節(jié)樹和森林第六節(jié)哈夫曼樹及其應用第七節(jié)樹與等價問題、樹的計數(shù)第六章第六章圖（10學時）第一節(jié)圖的概念第二節(jié)圖的存貯結構第三節(jié)圖的遍歷第四節(jié)圖的連通性問題第五節(jié)最短路徑第六節(jié)有向無環(huán)圖及其應用第七章第七章動態(tài)存儲管理動態(tài)存儲管理（5學時）第一節(jié)概述第二節(jié)可利用空間表及分配算法第三節(jié)邊界標識法第四節(jié)伙伴系統(tǒng)第五節(jié)無用單元收集第八章第八章查找