課程簡(jiǎn)介
Course Introduction
“數(shù)據(jù)結(jié)構(gòu)”是計(jì)算機(jī)大類的學(xué)科基礎(chǔ)課程,，研究計(jì)算機(jī)處理數(shù)據(jù)的結(jié)構(gòu)特性,。通過(guò)對(duì)本課程的學(xué)習(xí)，能夠解決非數(shù)值計(jì)算與工程應(yīng)用問(wèn)題,，能夠針對(duì)問(wèn)題的應(yīng)用場(chǎng)景進(jìn)行分析,，選擇或設(shè)計(jì)恰當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及相應(yīng)的算法,。本課程為學(xué)生進(jìn)一步理論學(xué)習(xí)和解決實(shí)際工程應(yīng)用問(wèn)題打下堅(jiān)實(shí)的基礎(chǔ),。
教學(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í)行過(guò)程中棧狀態(tài)的變化過(guò)程。
重點(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)算來(lái)實(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ù)和二叉樹(shù)
本章知識(shí)點(diǎn):掌握二叉樹(shù)的基本概念,、性質(zhì)和存儲(chǔ)結(jié)構(gòu),； 熟練掌握二叉樹(shù)的前、中,、后序遍歷方法,； 了解線索化二叉樹(shù)的思想 ； 熟練掌握:霍夫曼樹(shù)的實(shí)現(xiàn)方法,、構(gòu)造霍夫曼編碼的方法,；. 了解:森林與二叉樹(shù)的轉(zhuǎn)換，樹(shù)的遍歷方法
重點(diǎn):二叉樹(shù)概念,，性質(zhì),，遍歷算法，最優(yōu)二叉樹(shù)
難點(diǎn):二叉樹(shù)的非遞歸算法,，最優(yōu)二叉樹(shù)
第六章 圖
圖的基本概念,；圖的存儲(chǔ)結(jié)構(gòu)；圖的遍歷及應(yīng)用:最小生成樹(shù),、最短路徑,、拓?fù)渑判颉?/span>
本章知識(shí)點(diǎn):熟悉圖的各種存儲(chǔ)結(jié)構(gòu)，了解實(shí)際問(wèn)題與采用何種存儲(chǔ)結(jié)構(gòu)和算法有密切聯(lián)系,；掌握遍歷圖的遞歸和非遞歸算法,；掌握應(yīng)用圖的遍歷算法求各種簡(jiǎn)單路徑問(wèn)題，比如,，最小生成樹(shù),、最短路徑、拓?fù)渑判虻?。?/span>
重點(diǎn):圖的相關(guān)概念,，圖的遍歷算法
難點(diǎn):最小生成樹(shù)，最短路徑,，拓?fù)渑判?/span>
第七章 查找
靜態(tài)查找表(順序表,有序表,索引順序表),； 動(dòng)態(tài)查找表(二叉排序樹(shù),平衡二叉樹(shù),B-樹(shù)和B+樹(shù))的建立和查找,；哈希表的建立,，查找及分析,；習(xí)題討論課。
本章知識(shí)點(diǎn):理解順序查找,，折半查找和索引查找的方法,，并能靈活應(yīng)用；掌握二叉排序樹(shù)的構(gòu)造方法及算法,；掌握二叉平衡樹(shù)的建立方法,；了解B-樹(shù)，B+樹(shù)的特點(diǎn)以及它們的建立過(guò)程,；掌握哈希表的構(gòu)造方法,；按定義計(jì)算各種查找方法在等概率情況下查找成功時(shí)和失敗時(shí)的平均查找長(zhǎng)度，理解哈希表在查找不成功時(shí)的平均查找長(zhǎng)度的計(jì)算方法,。
重點(diǎn):折半查找,，二叉排序樹(shù)，哈希表
難點(diǎn):二叉平衡樹(shù)的建立方法,，哈希表
第八章 內(nèi)部排序
概念,；插入排序；交換排序(起泡,排序),；選擇排序(簡(jiǎn)單選擇,堆),；歸并排序；基數(shù)排序,。
本章知識(shí)點(diǎn):理解各種排序方法的特點(diǎn)并能靈活應(yīng)用,；掌握各種方法的排序過(guò)程和各種排序方法的時(shí)間復(fù)雜度分析。重點(diǎn)掌握快速排序,、堆排序,、歸并排序和基數(shù)排序的基本思想及排序過(guò)程，難點(diǎn)是這四個(gè)排序算法的實(shí)現(xiàn),。
重點(diǎn):插入排序,，交換排序，快速排序,，堆排序
難點(diǎn):快速排序,，堆排序，歸并排序
