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