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