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