數據結構（簡體書）

《國家級教學成果獎配套教材：數據結構》的主要任務是介紹并探討有關數據組織、算法設計、時間和空間效率的概念和通用分析方法，幫助讀者理解數據的組織方法和現實世界問題在計算機內部的表示方法，針對問題的具體應用背景進行分析，進而選擇合適的數據結構，從而培養高級程序設計技能。
本書第1章介紹了數據結構與算法的基本概念；第2章基本上是對C語言關鍵內容的復習，為後續章節理解數據結構的實現作準備；第3章至第7章分別介紹了線性表、樹、散列表、圖、排序算法等經典數據結構與算法；最後在第8章通過對兩個實際生活中提煉出的問題的解答，幫助讀者更深刻體會數據結構的應用。
本書可作為高等學校計算機類專業的專業基礎課“數據結構”的教材。

陳越，浙江大學計算機科學與技術學院教授、副院長，教育部高等學校軟件工程專業教學指導分委員會委員。
主要研究方向為醫學圖像處理、語義網等。先後主持過國家自然科學基金青年基金和面上基金項目、教育部優秀青年教師基金項目、與國內外企業合作項目等，發表學術論文20余篇，并著有教材和譯著10部。
近年來主要授課課程為“數據結構基礎”、“高級數據結構與算法分析”、“軟件工程”、“數值分析”。承擔國家級教學改革項目6項，為國家精品課程“軟件工程”、國家雙語示范課程“數據結構與算法”、國家級教學團隊“程序設計系列課程教學團隊”的負責人，并主持教育部“基礎拔尖人才培養計劃（計算機專業）”、“卓越工程師計劃（軟件工程專業）”、特色專業“軟件工程（金融信息學方向）”等教改項目。曾獲國家優秀教學成果二等獎（2009）、浙江省優秀教學成果一等獎2項（2005、2009）、寶鋼優秀教師獎（2006）等。

《國家級教學成果獎配套教材：數據結構》的主要任務是介紹并探討有關數據組織、算法設計、時間和空間效率的概念及通用分析方法，幫助讀者學會數據的組織方法和現實世界問題在計算機內部的表示方法，針對問題的應用背景分析，選擇合適的數據結構，從而培養高級程序設計技能。
本書的特點是從實際應用問題出發，導出各種經典數據結構的定義、實現（存儲）方法以及操作實現，并以更豐富的綜合應用案例幫助讀者增強對理論的感性認識，從而明白這些數據結構為什么存在，以及在什么情況下可以最好地解決什么樣的問題。
本書提供了豐富的學習資源，包括源代碼及配套電子課件、浙江大學提供的在線系統PAT、《數據結構學習與實驗指導》等。讀者可以通過使用這些學習資源隨時檢測自己的學習效果與編程能力。

第1章 概論
1.1 引子
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.2 數據存儲基礎
2.2.1 數組
2.2.2 指針
2.2.3 結構
2.2.4 鏈表
2.2.5 類型定義typedef
2.3 流程控制基礎
2.3.1 分支控制
2.3.2 循環控制
2.3.3 函數與遞歸
本章小結
習題

第3章 線性結構
3.1 引子
3.2 線性表的定義與實現
3.2.1 線性表的定義
3.2.2 線性表的順序存儲實現
3.2.3 線性表的鏈式存儲實現
3.2.4 廣義表與多重鏈表
3.3 堆棧
3.3.1 堆棧的定義
3.3.2 堆棧的實現
3.3.3 堆棧應用：表達式求值
3.4 隊列
3.4.1 隊列的定義
3.4.2 隊列的實現
3.5 應用實例
3.5.1 多項式加法運算
3.5.2 迷宮問題
本章小結
習題

第4章 樹
4.1 引子
4.1.1 問題的提出
4.1.2 查找
4.2 樹的定義、表示和術語
4.3 二叉樹
4.3.1 二叉樹的定義及其邏輯表示
4.3.2 二叉樹的性質
4.3.3 二叉樹的存儲結構
4.3.4 二叉樹的操作
4.4 二叉搜索樹
4.4.1 二叉搜索樹的定義
4.4.2 二叉搜索樹的動態查找
4.4.3 二叉搜索樹的插入
4.4.4 二叉搜索樹的刪除
4.5 平衡二叉樹
4.5.1 平衡二叉樹的定義
4.5.2 平衡二叉樹的調整
4.6 樹的應用
4.6.1 堆及其操作
4.6.2 哈夫曼樹
4.6.3 集合及其運算
本章小結
習題

第5章 散列查找
5.1 引子
5.2 基本概念
5.3 散列函數的構造方法
5.3.1 數字關鍵字的散列函數構造
5.3.2 字符串關鍵字的散列函數構造
5.4 處理沖突的方法
5.4.1 開放定址法
5.4.2 分離鏈接法
5.5 散列表的性能分析
5.6 應用實例
本章小結
習題

第6章 圖
6.1 引子
6.2 圖的基本概念
6.2.1 圖的定義和術語
6.2.2 圖的抽象數據類型
6.3 圖的存儲結構
6.3.1 鄰接矩陣
6.3.2 鄰接表
6.4 圖的遍歷
6.4.1 迷宮探索
6.4.2 深度優先搜索
6.4.3 廣度優先搜索
6.5 最小生成樹
6.5.1 生成樹的構建與最小生成樹的概念
6.5.2 構造最小生成樹的Prim算法
6.5.3 構造最小生成樹的Kruskal算法
6.6 最短路徑
6.6.1 單源最短路徑
6.6.2 每一對頂點之間的最短路徑
6.7 拓撲排序
6.8 關鍵路徑計算
6.9 應用實例
6.9.1 六度空間理論
6.9.2 六度空間理論的驗證
本章小結
習題

第7章 排序
7.1 引子
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.7 外部排序
7.8 排序的比較和應用
7.8.1 排序算法的比較
7.8.2 排序算法應用案例
本章小結
習題

第8章 綜合應用案例分析
8.1 銀行排隊問題
8.1.1 單隊列多窗口服務
8.1.2 單隊列多窗口+VIP服務
8.2 暢通工程問題
8.2.1 建設道路數量問題
8.2.2 最低成本建設問題
本章小結
習題
參考文獻