21世紀高等學校本科計算機專業系列實用教材：數據結構與算法實用教程

　「數據結構與算法」是計算機科學與技術專業的一門非常重要的專業基礎課，是《中國計算機科學與技術學科教程2002》指定的核心課程之一。本書由長期擔任本課程教學任務的教授主持編寫，內容覆蓋了該教程規定的關於本門課程的全部知識點，並融入了編者的教學經驗和對課程內涵的深入思考。全書共分l0章，內容涉及數據結構的基本概念、線性表、棧和隊列、串和數組、廣義表、樹、圖、查找、排序及算法設計方法。
　　本書可作為高等院校計算機專業及相關專業的教材和參考書，也可供IT工程技術人員參考。

第1章　緒論
1.1　引言
1.1.1　解決問題的步驟
1.1.2　一個例子
1.2　數據結構
1.2.1　有關概念和術語
1.2.2　抽象數據類型
1.2.3　描述工具——類C語言
1.3　算法和算法分析
1.3.1　算法的定義及算法設計的要求
1.3.2　算法性能分析與度量
1.3.3　複雜度函數的增長率
1.3.4　複雜度分析的例子
本章小結
習題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.4　線性表實現方法的比較
2.5　循環鏈表
2.6　雙向鏈表
2.7　靜態鏈表
﹡2.8　 算法設計實例——一元多項式的表示及相加
本章小結
習題2

第3章　棧和隊列
3.1　棧
3.1.1　棧的類型定義
3.1.2　棧的表示和實現
3.1.3　順序棧和鏈棧的比較
3.2　隊列
3.2.1　隊列的類型定義
3.2.2　循環隊列
3.2.3　鏈隊——隊列的鏈式表示和實現
*3.3　遞歸
3.3.1　遞歸的定義
3.3.2　遞歸的實現
3.3.3　遞歸和迭代
3.3.4　遞歸的消除
*3.4　算法設計實例
3.4.1　數制轉換
3.4.2　表達式求值算法
本章小結
習題3

第4章　串
4.1　串的類型定義
4.1.1　串的基本概念
4.1.2　串的抽象數據類型
4.2　串的表示和實現
4.2.1　串的順序存儲結構
4.2.2　串的鏈式存儲結構
4.3　串的模式匹配
4.3.1　樸素的模式匹配算法
4.3.2　KMP算法
*4.4　串的應用舉例
本章小結
習題4

第5章　數組和廣義表
5.1　數組的概念及其基本操作
5.1.1　數組的抽象數據類型
5.1.2　二維數組
5.2　數組的順序存儲
5.3　矩陣的壓縮存儲
5.3.1　特殊矩陣
5.3.2　稀疏矩陣
*5.4　廣義表
5.4.1　廣義表的定義
5.4.2　廣義表的存儲結構
本章小結
習題5

第6章　樹與二叉樹
6.1　樹的概念和操作
6.1.1　樹的定義
6.1.2　樹的基本術語
6.1.3　樹的基本操作
6.2　二叉樹
6.2.1　二叉樹的概念及操作
6.2.2　二叉樹的性質
6.2.3　二叉樹的存儲結構
6.3　二叉樹的遍歷
6.3.1　二叉樹的遍歷
6.3.2　遍歷算法的應用
6.4　線索二叉樹
6.4.1　線索二叉樹的基本概念
6.4.2　線索二叉樹的基本操作
6.5　樹和森林
6.5.1　樹的存儲結構
6.5.2　森林、樹、二叉樹的相互轉換
6.5.3　樹和森林的遍歷
6.6　哈夫曼樹及其應用
6.6.1　最優二叉樹（哈夫曼樹）
6.6.2　哈夫曼編碼
*6.7　算法設計實例
本章小結
習題6

第7章　圖
7.1　圖的定義和術語
7.1.1　圖的基本概念
7.1.2　圖的基本操作
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.5.1　拓撲排序
*7.5.2　關鍵路徑
7.6　最短路徑
7.6.1　從某個源點到其他各頂點的最短路徑
7.6.2　每一對頂點之間的最短路徑
*7.7　網絡流問題
*7.8　算法實例
本章小結
習題7

第8章　查找
8.1　概述
8.2　線性表上的查找
8.2.1　順序表上的查找
8.2.2　有序表上的二分查找
8.3　索引表上的查找
8.4　樹表上的查找
8.4.1　二叉排序樹
8.4.2　平衡二叉樹
*8.4.3　B_樹
*8.4.4　鍵樹
8.5　哈希表
8.5.1　哈希表查找的基本概念
8.5.2　構造哈希函數的方法
8.5.3　哈希衝突的解決方法
8.5.4　哈希表的查找及分析
*8.6　算法設計實例
本章小結
習題8

第9章　排序
9.1　概述
9.1.1　排序的定義
9.1.2　排序的分類
9.1.3　排序的基本操作
9.1.4　排序算法的性能評價
9.1.5　排序算法涉及的數據類型
9.2　插入排序
9.2.1　直接插入排序
9.2.2　折半插入排序
9.2.3　希爾排序
9.2.4　其他插入排序
9.3　交換排序
9.3.1　冒泡排序
9.3.2　快速排序
9.4　選擇排序
9.4.1　簡單選擇排序
9.4.2　堆排序
9.5　歸併排序
9.5.1　歸併排序
9.5.2　二路歸併排序
9.6　分配排序
9.6.1　多關鍵字排序
9.6.2　基數排序
9.7　計數排序
9.7.1　計數排序
9.7.2　計數排序算法實現
9.8　內部排序比較與選擇
9.8.1　內部排序算法性能比較
9.8.2　內部排序算法的選擇
*9.9　外部排序簡介
9.9.1　磁盤文件管理
9.9.2　多路歸併排序
9.9.3　二路歸併排序算法
9.9.4　磁盤文件排序的例子
9.9.5　提高外部排序算法效率的途徑
本章小結
習題9

第10章　算法設計初步
10.1　迭代法與窮舉法
10.1.1　迭代法
10.1.2　窮舉法
10.2　遞歸技術與分治法
10.2.1　遞歸技術
10.2.2　分治法
10.3　回溯法
10.3.1　回溯法的基本思想
10.3.2　0-1背包問題
10.3.3　旅行商問題
10.3.4　求解迷宮問題
10.4　倒推法
10.4.1　倒推法的基本思想
10.4.2　倒推法應用實例
10.5　貪心法
10.5.1　貪心法的基本思想
10.5.2　使用貪心法的前提
10.5.3　貪心法應用實例
10.6　分枝限界法
10.6.1　分枝限界法的基本思想
10.6.2　分枝限界法的應用實例
10.7　動態規劃法
10.7.1　動態規劃法的基本思想
10.7.2　動態規劃法的基本要素
10.7.3　動態規劃法的變形——備忘錄方法
10.8　隨機算法
10.8.1　隨機數的產生
10.8.2　用隨機算法計算p的值
10.8.3　蒙特卡羅積分
本章小結
習題10
參考文獻