第1章緒論

1.1引言

1.1.1學習目的

1.1.2課程內容

1.2基本概念

1.2.1數據與數據結構

1.2.2數據類型與抽象數據類型

1.3算法

1.3.1算法的概念

1.3.2算法描述

1.3.3算法分析

小結

習題1

第2章線性表

2.1線性表及其基本操作

2.1.1線性表的基本概念

2.1.2抽象數據類型描述

2.1.3線性表的存儲和實現

2.2線性表的順序存儲

2.2.1順序表

2.2.2順序表的基本操作實現

2.3線性表的鏈式存儲和實現

2.3.1單鏈表

2.3.2單鏈表的基本操作實現

2.3.3其他鏈表

2.4順序表與鏈表的比較

2.5實驗

2.5.1數字加1

2.5.2只出現一次的數字

2.5.3合并有序鏈表

小結

習題2

第3章棧和隊列

3.1棧

3.1.1棧的基本概念

3.1.2棧的抽象數據類型描述

3.1.3順序棧

3.1.4鏈棧

3.2隊列

3.2.1隊列的基本概念

3.2.2隊列的抽象數據類型描述

3.2.3順序隊列

3.2.4鏈隊列

3.2.5優(yōu)先級隊列

3.3棧和隊列的比較

3.4實驗

3.4.1用隊列實現棧

3.4.2用棧實現隊列

3.4.3棧的最小值

小結

習題3

第4章串和數組

4.1串

4.1.1串的基本概念

4.1.2串的抽象數據類型描述

4.1.3順序串

4.1.4鏈串

4.2串的模式匹配

4.2.1Brute Force算法

4.2.2KMP算法

4.3數組

4.3.1數組的基本概念

4.3.2數組的特性

4.3.3數組的遍歷

4.4特殊矩陣的壓縮存儲

4.4.1三角矩陣的壓縮存儲

4.4.2對稱矩陣的壓縮存儲

4.4.3對角矩陣的壓縮存儲

4.4.4稀疏矩陣的壓縮存儲

4.5實驗

4.5.1驗證回文串

4.5.2轉置矩陣

4.5.3左旋轉字符串

小結

習題4

第5章樹結構

5.1樹

5.1.1樹的基本概念

5.1.2樹的術語

5.2二叉樹

5.2.1二叉樹的基本概念

5.2.2二叉樹的性質

5.2.3二叉樹的存儲結構

5.2.4二叉樹的遍歷

5.2.5二叉樹遍歷算法的應用

5.2.6二叉樹的建立

5.3哈夫曼樹及哈夫曼編碼

5.3.1哈夫曼樹的基本概念

5.3.2哈夫曼樹的構造

5.3.3哈夫曼編碼

5.3.4構造哈夫曼樹和哈夫曼編碼的類的描述

5.4樹和森林

5.4.1樹的存儲結構

5.4.2樹的遍歷規(guī)則

5.5實驗

5.5.1二叉樹剪枝

5.5.2相同的樹

5.5.3翻轉二叉樹

小結

習題5

第6章圖

6.1圖概述

6.1.1圖的基本概念

6.1.2圖的抽象數據類型描述

6.2圖的存儲結構

6.2.1鄰接矩陣

6.2.2鄰接表

6.3圖的遍歷

6.4最小生成樹

6.4.1最小生成樹的基本概念

6.4.2Kruskal算法

6.4.3Prim算法

6.5最短路徑

6.5.1單源最短路徑

6.5.2求任意兩個頂點間的最短路徑

6.6拓撲排序和關鍵路徑

6.6.1拓撲排序

6.6.2關鍵路徑

6.7實驗

6.7.1尋找圖中是否存在路徑

6.7.2最小花費

小結

習題6

第7章排序

7.1排序概述

7.1.1排序的基本概念

7.1.2排序算法的性能評價

7.1.3待排序的記錄和順序表的類描述

7.2插入排序

7.2.1直接插入排序

7.2.2希爾排序

7.3交換排序

7.3.1冒泡排序

7.3.2快速排序

7.4選擇排序

7.4.1直接選擇排序

7.4.2堆排序

7.5歸并排序

7.6實驗

7.6.1投票排序

7.6.2查找缺失的數字

7.6.3檢查高度

小結

習題7

第8章查找

8.1查找的基本概念

8.1.1什么是查找

8.1.2查找表

8.1.3平均查找長度

8.2靜態(tài)表查找

8.2.1順序查找

8.2.2二分查找

8.2.3分塊查找

8.3動態(tài)表查找

8.3.1二叉排序樹查找

8.3.2平衡二叉樹

8.3.3B-樹和B 樹

8.4哈希表查找

8.4.1哈希表的概念

8.4.2哈希函數

8.4.3解決沖突的方法

8.4.4哈希表查找性能分析

8.5實驗

8.5.1二叉搜索樹的最小絕對差

8.5.2查找插入位置

8.5.3排序矩陣查找

小結

習題8

附錄A實踐題

第2章線性表

第3章棧和隊列

第4章串和數組

第5章樹結構

第6章圖

第7章排序

第8章查找

參考文獻