課程簡介
Course Introduction
數(shù)據(jù)結(jié)構(gòu)是計算機(jī)專業(yè)一門重要的專業(yè)基礎(chǔ)課程,，是開展計算機(jī)業(yè)務(wù)的技術(shù)基礎(chǔ),。它是由某一數(shù)據(jù)元素的集合和該集合中數(shù)據(jù)元素的關(guān)系組成。本課程用面向?qū)ο蟮挠^點(diǎn)討論數(shù)據(jù)結(jié)構(gòu),，主要介紹了數(shù)據(jù)結(jié)構(gòu)的基本概念,，線性表,，棧和隊列，數(shù)組,、串和廣義表,，樹，集合,，搜索結(jié)構(gòu),，排序和文件10章的內(nèi)容，分析它們的特點(diǎn),，以及在計算機(jī)中的存儲方法,，和常規(guī)操作的實(shí)現(xiàn)。 課程以C++語言作為算法的描述工具,，強(qiáng)化數(shù)據(jù)結(jié)構(gòu)基本知識和面向?qū)ο蟪绦蛟O(shè)計基本能力的訓(xùn)練,，目的是使學(xué)生學(xué)會分析研究計算機(jī)加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu),、存儲結(jié)構(gòu)及相應(yīng)的算法,，并初步了解對算法的時間分析和空間分析技術(shù)。另一方面,，通過對本課程算法設(shè)計的實(shí)踐與訓(xùn)練,，培養(yǎng)學(xué)生的數(shù)據(jù)抽象能力和程序設(shè)計的能力，為以后的專業(yè)課程學(xué)習(xí)打下堅實(shí)的基礎(chǔ),。
教學(xué)大綱
Teaching Syllabus
單元一:數(shù)據(jù)結(jié)構(gòu)和算法的相關(guān)概念
1. 數(shù)據(jù)結(jié)構(gòu)的一些基本概念:數(shù)據(jù),、數(shù)據(jù)元素、數(shù)據(jù)邏輯結(jié)構(gòu),、數(shù)據(jù)存儲結(jié)構(gòu),、數(shù)據(jù)類型,、算法等。
2. 抽象數(shù)據(jù)類型,。
3. 描述算法所用的C++語言中的一些有關(guān)問題,。
4. 算法時間復(fù)雜度和空間復(fù)雜度的分析。
單元二:線性表
1. 線性表的基本概念和類型定義
2. 線性表的順序存儲結(jié)構(gòu)
3. 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)
(1) 單鏈表的查找,、插入和刪除
(2) 循環(huán)鏈表的查找,、插入和刪除
(3) 雙向鏈表的查找、插入和刪除
單元三:棧和隊列
1. 棧的類型定義
2. 棧的順序存儲和鏈接存儲的表示
3. 在棧的順序存儲和鏈接存儲上進(jìn)行各種棧操作的算法
4. 棧的應(yīng)用分析
(1)表達(dá)式求值問題的分析及算法設(shè)計
(2)迷宮問題的求解分析及算法設(shè)計
5. 隊列的類型定義
6. 隊列的順序存儲(循環(huán)隊)和鏈接存儲表示及各種操作的實(shí)現(xiàn)算法
單元四:數(shù)組,、串與廣義表
1．特殊矩陣的定義,、存儲和運(yùn)算
2．串的概念(包括 串, 空串 ,子串, 串的長度).
3．串的存儲結(jié)構(gòu)(靜態(tài)存儲和動態(tài)存儲的方法)
4．掌握C/C++中有關(guān)串的常用函數(shù)并能運(yùn)用到實(shí)際的問題解決中。
5．廣義表的定義,、存儲和運(yùn)算
單元五: 樹
1. 樹的定義,、性質(zhì)和表示方法
2. 二叉樹的定義、性質(zhì)和存儲結(jié)構(gòu)
3. 二叉樹的各種遍歷方法及算法的實(shí)現(xiàn)
4. 建立二叉樹,、輸出二叉樹,、求二叉樹深度等的操作方法及算法的實(shí)現(xiàn)
5. 樹的存儲結(jié)構(gòu)，進(jìn)行前序遍歷,、中序遍歷,、后序遍歷和按層遍歷的方法及算法的實(shí)現(xiàn)
6. 進(jìn)行樹與二叉樹的轉(zhuǎn)換方法
7. 哈夫曼樹的定義、構(gòu)造哈夫曼樹,、哈夫曼編碼的方法以及算法的實(shí)現(xiàn)
單元六:集合與字典
1.集合及其表示
2.并查集與等價類的基本概念及算法設(shè)計思路
3.散列查找的基本概念及算法設(shè)計思路的分析與實(shí)現(xiàn)
單元七:搜索結(jié)構(gòu)
1. 順序查找和二分查找的處理策略及算法實(shí)現(xiàn)過程
2．索引查找和分塊查找的處理策略及算法實(shí)現(xiàn)過程
3．二叉樹查找樹及平衡樹的概念及處理策略
單元八:圖
1. 圖的定義和術(shù)語
2. 圖的鄰接矩陣,、鄰接表和邊集數(shù)組表示
3. 圖的深度和廣度優(yōu)先搜索遍歷的思想及算法實(shí)現(xiàn)
4. 圖的生成樹和最小生成樹的思路及算法實(shí)現(xiàn)
5. 拓?fù)渑判虻乃枷爰八惴▽?shí)現(xiàn)
6．最短路徑的思想及算法實(shí)現(xiàn)
單元九:排序
1.排序的概念
2.直接插入排序的處理思想及算法設(shè)計思路
3.冒泡排序和快排序的處理思想及算法設(shè)計思路
4.直接選擇排序和堆排序的處理思想及算法設(shè)計思路
5．二路歸并排序的處理思想及算法設(shè)計思路
6．分配排序的處理思想及算法設(shè)計思路
單元十:文件、外部排序與搜索
1．文件的基本概念
2．順序文件,，索引文件和散列文件的組織方法和操作方法,。
3．外排序的方法
4. B樹的概念及操作
