數據結構、算法及應用（簡體書）

《普通高等教育"十二五"重點規劃教材?計算機系列?中國科學院教材建設專家委員會"十二五"規劃教材:數據結構、算法及應用》可作為高等院校計算機專業和相近專業本科生“數據結構”課程的教材或參考書，也可供計算機應用領域的工程技術人員參考。

第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.4 數據結構的選擇和評價
習題
第2章 線—性表
2.1 線性表的概念
2.1.1 線性表的定義及特征
2.1.2 線性表的抽象數據類型
2.1.3 線性表的存儲結構
2.1.4 線性表運算分類
2.2 順序表
2.2.1 順序表的實現
2.2.2 多維數組
2.3 鏈表
2.3.1 鏈表的實現
2.3.2 線性表實現方法的比較
2.4 棧
2.4.1 順序棧
2.4.2 鏈式棧
2.4.3 棧與遞歸
2.5 隊列
2.5.1 順序隊列
2.5.2 鏈式隊列
2.6 字符串
2.6.1 基本概念
2.6.2 存儲結構和實現
2.6.3 字符串運算的算法實現
2.6.4 字符串的模式匹配
2.7 線性表的應用
2.7.1 棧：簡易計算器
2.7.2 隊列：銀行叫號系統的實現
2.7.3 字符串及鏈表：簡易文本編輯器
習題
第3章 樹
3.1 樹的基本概念
3.1.1 樹的定義和基本術語
3.1.2 樹的基本性質
3.1.3 樹的邏輯表示方式
3.2 二叉樹
3.2.1 二叉樹的定義和相關概念
3.2.2 幾種特殊的二叉樹
3.2.3 二叉樹的性質
3.2.4 二叉樹的存儲結構
3.2.5 二叉樹的抽象數據類型
3.2.6 二叉樹的遍歷
3.2.7 線索二叉樹
3.2.8 二叉搜索樹
3.2.9 平衡二叉樹
3.2.10 堆與優先隊列
3.2.11 Huffman編碼樹
3.3 樹與森林
3.3.1 二叉樹、樹、森林之間的轉換
3.3.2 樹和森林的遍歷
3.3.3 樹的存儲
3.4 樹的應用
3.4.1 二叉樹：圖像壓縮算法
3.4.2 樹：醫院設施管理
習題
第4章 圖
4.1 圖的基本概念
4.1.1 圖的定義和概念
4.1.2 圖的抽象數據類型
4.2 圖的存儲及基本操作
4.2.1 圖的鄰接矩陣表示法
4.2.2 圖的鄰接表表示法
4.2.3 十字鏈表和鄰接多重表
4.3 圖的遍歷
4.3.1 深度優先搜索（DFS）
4.3.2 廣度優先搜索（BFS）
4.4 最小生成樹
4.4.1 普里姆（Prim）算法
4.4.2 克魯斯卡爾（Kruskal）算法
4.5 最短路徑
4.5.1 單源最短路徑
4.5.2 頂點對之間的最短路徑
4.6 拓撲排序
4.7 關鍵路徑
4.8 圖的應用
4.8.1 圖的存儲和遍歷：地圖染色應用的實現
4.8.2 最小生成樹：通信線路鋪設問題
4.8.3 最短路徑：指定時間內路口攔截犯罪分子問題
4.8.4 關鍵路徑：軟件項目管理的流程控制問題
習題
第5章 查找
5.1 靜態查找
5.1.1 順序查找法
5.1.2 折半查找法
5.1.3 分塊查找
5.2 動態查找
5.2.1 B—樹
5. B+樹
5.3 散列
5.3.1 散列的概念
5.3.2 散列函數
5.3.3 沖突解決方法
5.3.4 散列算法設計與分析
5.4 查找的應用：通訊錄
習題
第6章 排序
6.1 排序的基本概念
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.6 比較排序算法的時間復雜度下界
6.7 基數排序
6.8 各種內部排序算法的比較和選擇
6.9 外部排序
6.9.1 置換選擇排序
6.9.2 多路歸并
6.10 排序的應用：書庫信息排序
習題
參考文獻

如果當前區塊是最后一個區塊的話，選定配色方案之后，就代表著染色過程終止了。如果不是最后一個區塊，則遞歸調用染色方法。如果染色失敗，那么就要進行回溯操作，將本區塊的染色方案，以及鄰居區塊的被修改的染色方案進行恢復。
地圖染色的方案不是唯一的，而且解答方法也不唯一。與地圖染色問題類似的應用問題還有八皇后問題，感興趣的同學可以自己練習。
4.8.2 最小生成樹：通信線路鋪設問題
1.需求描述
隨著網絡技術的發展，信息化網絡正在逐漸普及，各個城市都會鋪設通信線路，使得城市中的區、縣都存在通信路徑。本應用程序將設計一個鋪設費用最優的鋪設方案，至少支持以下功能：
1）獲取城市的下轄區／縣。
2）修改區／縣之間的花銷。
3）計算最佳鋪設方法。
2.問題分析
本應用的目標是給一個城市下轄的區／縣鋪設通信線路，可以利用本章中學習的圖來存儲城市中的區、縣的距離信息，這里選擇使用鄰接矩陣來存儲。首先，從文件中讀取城市下轄的區、縣信息（每個區、縣包括對應的名稱，X坐標和Y坐標），利用獲取的區、縣信息來構建一個圖。
實際生活中，由于區、縣之間的地理環境因素，區、縣之間的鋪設代價不僅與區、縣之間的距離有關，還與區、縣之間每公里所需的代價有關，兩者的乘積對應于圖中邊的權重。默認情況下區、縣之間每公里所需的代價都為l。應用程序應該提供修改每公里所需代價的接口函數。
本應用最重要的一個方面就是已知地理信息之后自動進行計算，并將結果輸出。最佳通信線路鋪設問題正好對應于本章中的最小生成樹問題，可以利用Kmskal算法或者Prim算法解決。
3.概要設計
需求描述和問題分析中主要涉及區、縣、城市、開銷等概念。開銷可以用double類型的數據來保存，因此本應用中需要有三個類：區、縣County類、城市City類和用于表示通信線路鋪設問題的CabelAllocator類。
根據上文的分析，區、縣類需要包括的成員變量包括區、縣名稱、區、縣所處位置的X坐標和Y坐標。