數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教學(xué)課件

課程簡介
?《數(shù)據(jù)結(jié)構(gòu)》作為一門獨(dú)立的課程最早是美國的一些大學(xué)開設(shè)的，1968年美國唐·歐·克努特教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的《計(jì)算機(jī)程序設(shè)計(jì)技巧》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其操作的著作。從60年代末到70年代初，出現(xiàn)了大型程序，軟件也相對獨(dú)立，結(jié)構(gòu)程序設(shè)計(jì)成為程序設(shè)計(jì)方法學(xué)的主要內(nèi)容，人們就越來越重視數(shù)據(jù)結(jié)構(gòu)，認(rèn)為程序設(shè)計(jì)的實(shí)質(zhì)是對確定的問題選擇一種好的結(jié)構(gòu)，加上設(shè)計(jì)一種好的算法。

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)程序設(shè)計(jì)的重要理論技術(shù)基礎(chǔ)，它對理論和實(shí)踐的要求都相當(dāng)高，具有相當(dāng)?shù)碾y度，且內(nèi)容較多。本課程旨在討論現(xiàn)實(shí)世界中數(shù)據(jù)（即事物的抽象描述）的各種邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲結(jié)構(gòu)，以及進(jìn)行多種非數(shù)值基本運(yùn)算的方法，讓學(xué)生學(xué)習(xí)、分析和研究計(jì)算機(jī)加工數(shù)據(jù)對象的特性，掌握數(shù)據(jù)的組織方法，以便選擇合適的數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，設(shè)計(jì)相應(yīng)的操作運(yùn)算，把現(xiàn)實(shí)中的問題轉(zhuǎn)化為在計(jì)算機(jī)內(nèi)部的表示和處理。在計(jì)算機(jī)應(yīng)用領(lǐng)域中，尤其是在系統(tǒng)軟件和應(yīng)用軟件的設(shè)計(jì)和應(yīng)用中都要用到各種數(shù)據(jù)結(jié)構(gòu)，這對提高程序編制和軟件設(shè)計(jì)水平都有很大的幫助。

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的核心課程之一，屬于專業(yè)基礎(chǔ)課，是一門理論與實(shí)踐相結(jié)合的課程。隨著信息技術(shù)的發(fā)展，數(shù)據(jù)結(jié)構(gòu)課程不僅是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)必修的核心課，同時也是電子工程、信息工程等專業(yè)的重要選修課程。本課程是針對我校非計(jì)算機(jī)專業(yè)本科生不同基礎(chǔ)、不同能力和學(xué)習(xí)目標(biāo)等情況而開設(shè)的。適合我校廣大非計(jì)算機(jī)專業(yè)，包括理科、文科在內(nèi)，本科生學(xué)習(xí)計(jì)算機(jī)程序設(shè)計(jì)的技術(shù)基礎(chǔ)知識。
?
教學(xué)目標(biāo)
?針對全校來自不同學(xué)科，包括：理科、文科在內(nèi)的，非計(jì)算機(jī)專業(yè)本科生（具有不同基礎(chǔ)、能力和學(xué)習(xí)目標(biāo)），學(xué)習(xí)掌握數(shù)據(jù)結(jié)構(gòu)，這一計(jì)算機(jī)軟件設(shè)計(jì)基礎(chǔ)知識，我們編寫了《數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法》、《數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法習(xí)題集》和《數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法實(shí)驗(yàn)教程》等系列教材，并為全校1300多選修本課程的本科生開設(shè)了《數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法》課程，希望通過本課程講授，使得具有不同基礎(chǔ)、能力和目標(biāo)的同學(xué)們能夠掌握利用計(jì)算機(jī)求解問題時，相關(guān)對象的表示方法和相應(yīng)的基本操作算法，為今后從事計(jì)算機(jī)程序設(shè)計(jì)相關(guān)工作奠定基礎(chǔ)。
?
1.1《數(shù)據(jù)結(jié)構(gòu)》討論范疇
1.2《數(shù)據(jù)結(jié)構(gòu)》相關(guān)概念
?1.2.1基本概念和術(shù)語
?1.2.2數(shù)據(jù)結(jié)構(gòu)??? ??
?1.2.3數(shù)據(jù)類型和抽象數(shù)據(jù)類型
1.3算法及其描述和算法分析
2.1 線性表的類型定義
2.2 順序存儲的線性表
2.3 鏈?zhǔn)酱鎯Φ木€性表
2.4 有序表
2.5 順序表和鏈表的綜合比較
3.1排序的基本概念
3.2簡單排序方法（復(fù)雜度 O(n2)）
3.3先進(jìn)排序方法（復(fù)雜度 O(nLogn)）
3.4基數(shù)排序（復(fù)雜度 O(d×n)）
3.5各種排序的綜合比較
4.1棧
4.2棧的應(yīng)用
4.3隊(duì)列
4.3隊(duì)列應(yīng)用
5.1 串的定義和操作
5.2 串的表示和實(shí)現(xiàn)
5.3 正文匹配模式
5.4 正文編輯
5.5 數(shù)組
5.6 數(shù)組的壓縮
6.1二叉樹
6.2二叉樹遍歷
6.3樹和森林
6.4樹的應(yīng)用
7.1圖的定義和術(shù)語
7.2圖的存儲結(jié)構(gòu)
7.3圖的遍歷
7.4連通網(wǎng)的最小生成樹
7.5單源最短路徑
7.6 *拓?fù)渑判?BR>7.7 *關(guān)鍵路徑
7.8 *廣義表
8.1靜態(tài)查找表
8.2動態(tài)查找表
8.3哈希表及其查找