課程簡介
Course Introduction
數(shù)據(jù)結(jié)構是一門專業(yè)基礎課，是學習其他軟件開發(fā)與設計等方面課程的基礎,。主要內(nèi)容包括:線性表,、棧和隊列、串,、數(shù)組和廣義表,、樹、圖,、查找算法和排序算法,。數(shù)據(jù)結(jié)構研究數(shù)據(jù)的組織方式，內(nèi)容豐富,、學習量大,，隱含在各部分內(nèi)容中的方法和技術多，旨在讓學生掌握計算機軟件系統(tǒng)所必需的數(shù)據(jù)結(jié)構的算法,。要求學生掌握貫穿全課程的動態(tài)鏈表存儲結(jié)構,，掌握算法設計的動態(tài)性和抽象性,。要求學生學會分析研究計算機加工的數(shù)據(jù)對象的特征，以便在實際應用中選擇適當?shù)臄?shù)據(jù)結(jié)構,、存儲結(jié)構和相應算法,，初步掌握算法的時間與空間性能分析技巧，并培養(yǎng)復雜程序設計的技能,。
教學大綱
Teaching Syllabus
第一章 緒論
本章知識點:理解相關的基本概念；掌握算法五大要素,；掌握計算語句頻度和估算算法時間復雜度的方法,。
重點:數(shù)據(jù)結(jié)構基本概念, 算法的時間和空間復雜度
難點:算法的時間和空間復雜度
第二章 線性表
本章知識點:掌握線性表的邏輯結(jié)構、線性表的存儲結(jié)構,、線性表在順序結(jié)構和鏈式結(jié)構上實現(xiàn)定義,、查找、插入和刪除等基本操作的方法,；理解從時間和空間復雜度的角度比較線性表兩種存儲結(jié)構的不同特點及其適用場合,。
重點:線性表的概念
難點:線性表的表示及實現(xiàn)
第三章 棧和隊列
本章知識點:了解棧和隊列的定義及特點；掌握在兩種存儲結(jié)構上棧的基本操作的實現(xiàn),；掌握循環(huán)隊列和鏈隊列的基本運算,；掌握遞歸算法執(zhí)行過程中棧狀態(tài)的變化過程。
重點:棧和隊列的表示和實現(xiàn)
難點:循環(huán)隊列
第四章 串,、數(shù)組和廣義表
串的邏輯結(jié)構,，存儲結(jié)構；串的應用,；
本部分知識點:理解串的基本運算的定義,，掌握利用這些基本運算來實現(xiàn)串的其它各種運算的方法；掌握在順序存儲結(jié)構上實現(xiàn)串的各種操作的方法,；重點掌握串上實現(xiàn)的模式匹配算法,。
重點:串的各種運算方法
難點:串的模式匹配算法
數(shù)組的存儲結(jié)構；稀疏矩陣的表示及操作的實現(xiàn),；廣義表的定義和存儲結(jié)構,；廣義表的遞歸算法；(該部分根據(jù)學時選講)
本部分知識點:掌握數(shù)組在以行為主的存儲結(jié)構中的地址計算方法,；掌握矩陣實現(xiàn)壓縮存儲時的下標變換,；理解稀疏矩陣的兩種存儲方式的特點和適用范圍，領會以三元組表示稀疏矩陣時進行運算采用的處理方法,；掌握廣義表的定義及其存儲結(jié)構,，學會廣義表的表頭，表尾分析方法,。
重點:稀疏矩陣存儲,，矩陣元素地址的計算，廣義表的表頭、表尾分析
難點:矩陣的三元組存儲時算法
第五章 樹和二叉樹
本章知識點:掌握二叉樹的基本概念,、性質(zhì)和存儲結(jié)構,； 熟練掌握二叉樹的前、中,、后序遍歷方法,； 了解線索化二叉樹的思想 ； 熟練掌握:霍夫曼樹的實現(xiàn)方法,、構造霍夫曼編碼的方法,；. 了解:森林與二叉樹的轉(zhuǎn)換，樹的遍歷方法
重點:二叉樹概念,，性質(zhì),，遍歷算法，最優(yōu)二叉樹
難點:二叉樹的非遞歸算法,，最優(yōu)二叉樹
第六章 圖
圖的基本概念,；圖的存儲結(jié)構；圖的遍歷及應用:最小生成樹,、最短路徑,、拓撲排序。
本章知識點:熟悉圖的各種存儲結(jié)構,，了解實際問題與采用何種存儲結(jié)構和算法有密切聯(lián)系,；掌握遍歷圖的遞歸和非遞歸算法；掌握應用圖的遍歷算法求各種簡單路徑問題,，比如,，最小生成樹、最短路徑,、拓撲排序等,。
重點:圖的相關概念，圖的遍歷算法
難點:最小生成樹,，最短路徑,，拓撲排序
第七章 查找
靜態(tài)查找表(順序表,有序表,索引順序表)； 動態(tài)查找表(二叉排序樹,平衡二叉樹,B-樹和B+樹)的建立和查找,；哈希表的建立,，查找及分析；習題討論課,。
本章知識點:理解順序查找,，折半查找和索引查找的方法，并能靈活應用,；掌握二叉排序樹的構造方法及算法,；掌握二叉平衡樹的建立方法,；了解B-樹，B+樹的特點以及它們的建立過程,；掌握哈希表的構造方法,；按定義計算各種查找方法在等概率情況下查找成功時和失敗時的平均查找長度，理解哈希表在查找不成功時的平均查找長度的計算方法,。
重點:折半查找,，二叉排序樹，哈希表
難點:二叉平衡樹的建立方法,，哈希表
第八章 內(nèi)部排序
概念,；插入排序；交換排序(起泡,排序),；選擇排序(簡單選擇,堆),；歸并排序,；基數(shù)排序,。
本章知識點:理解各種排序方法的特點并能靈活應用；掌握各種方法的排序過程和各種排序方法的時間復雜度分析,。重點掌握快速排序,、堆排序、歸并排序和基數(shù)排序的基本思想及排序過程,，難點是這四個排序算法的實現(xiàn),。
重點:插入排序，交換排序,，快速排序,，堆排序
難點:快速排序，堆排序,，歸并排序
