數據結構與算法

“數據結構與算法”是計算機及其相關專業的重要課程,是計算機軟件開發及應用人員的專業基礎。本書首先介紹數據結構與算法的基礎知識,然後系統地論述線性表、棧、隊列、串、數組、樹和二叉樹、圖等基本數據結構,並討論了常用的查找和排序技術。在用例選擇方面,充分考慮了電子信息類專業的特點,尤其突出了信息與通信工程相關專業的特色。本書在部分章節加入了相應的標準模板庫(STL),旨在使讀者瞭解STL與數據結構的關係並且掌握各類STL的應用,提高其實際應用能力和程序設計的效率。 ^[1] 

第1章 緒論

1．1 數據結構與算法的重要性

1．2 數據結構的基本概念

1．3 算法和算法分析

1．3．1 算法描述

1．3．2 算法分析

1．3．3 NP問題

1．4 STL與數據結構

1．4．1 STL簡介

1．4．2 STL與數據結構的關係

1．5 工程實踐和思考

習題1

第2章 線性表

2．1 線性表概述

2．1．1 線性表的定義

2．1．2 線性表的運算

2．1．3 各種常用存儲結構

2．2 順序表的實現

2．2．1 順序表的存儲結構

2．2．2 順序表的基本運算

2．2．3 順序表的應用——通信錄

2．2．4 STL中的順序表——vector

2．3 單鏈表的實現

2．3．1 單鏈表的存儲結構

2．3．2 單鏈表的基本運算

2．3．3 單鏈表的應用——通信錄

2．4 循環鏈表的實現

2．5 雙鏈表的實現

2．5．1 雙鏈表的基本結構

2．5．2 雙鏈表的基本運算

2．5．3 STL中的雙鏈表——list

2．6 順序表與鏈表的比較

2．6．1 時間性能比較

2．6．2 空間性能比較

2．7 工程實踐和思考

問題1：不支持指針的高級語言，如何實現鏈表？

問題2：如何實現一元多項式的求和？

問題3：操作系統的內存如何管理？

問題4：荷蘭國旗問題

習題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 STL中的棧——stack

3．3 隊列的實現

3．3．1 循環隊列

3．3．2 鏈隊列

3．3．3 STL中的隊列

3．4 串的實現

3．4．1 串的存儲結構

3．4．2 串的模式匹配

3．4．3 KMP算法

3．4．4 STL中的串——string

3．5 多維數組

3．5．1 多維數組的存儲

3．5．2 稀疏矩陣

3．6 基於棧的經典算法

3．6．1 遞歸——斐波那契數列

3．6．2 分治法——漢諾塔遊戲

3．6．3 回溯法——迷宮問題

3．6．4 動態規劃——揹包問題

3．7 工程實踐和思考

問題1：優先級隊列的調度

問題2：圖像識別領域的基本問題——手寫數字識別

問題3：貪心算法和動態規劃的區別

問題4：窮舉法和動態規劃的區別

習題3

第4章 樹

4．1 基本概念

4．1．1 樹

4．1．2 二叉樹

4．1．3 森林

4．2 基本操作

4．2．1 樹的遍歷

4．2．2 二叉樹的遍歷

4．2．3 森林的遍歷

4．2．4 樹、森林與二叉樹的轉換

4．3 存儲結構

4．3．1 樹的存儲結構

4．3．2 二叉樹的存儲結構

4．4 二叉樹的實現

4．4．1 二叉樹的聲明

4．4．2 二叉樹的關鍵算法

4．4．3 遞歸算法的規律

4．5 哈夫曼樹的應用

4．5．1 哈夫曼樹的定義與存儲結構

4．5．2 哈夫曼樹的構造

4．5．3 哈夫曼編碼表的構建

4．5．4 哈夫曼編、解碼的實現

4．6 工程實踐和思考

問題1：構建算術表達式二叉樹

問題2：通信系統中如何使用哈夫曼樹壓縮信息？

習題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．4 最小生成樹

5．4．1 普里姆算法

5．4．2 克魯斯卡爾算法

5．5 最短路徑

5．5．1 Dijkstra算法

5．5．2 Floyd算法

5．6 工程實踐與思考

問題1：圖着色問題

問題2：地鐵換乘線路查找問題

問題3：教學計劃安排問題

問題4：關鍵路徑問題

習題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．3．3 B-樹

6．3．4 STL中的樹表——set和map

6．4 散列查找

6．4．1 散列技術

6．4．2 散列函數設計

6．4．3 衝突處理

6．4．4 常用的散列函數

6．5 工程實踐和思考

問題1：自然語言處理的基本問題——中文分詞

問題2：數據庫索引結構

習題6

第7章 排序

7．1 基本概念

7．1．1 相關概念

7．1．2 排序性能評估

7．1．3 排序方法分析

7．2 簡單排序

7．2．1 起泡排序

7．2．2 直接插入排序

7．2．3 簡單選擇排序

7．3 複雜排序

7．3．1 希爾排序

7．3．2 快速排序

7．3．3 堆排序

7．3．4 歸併排序

7．3．5 STL中常用的排序算法

7．4 非比較的排序算法

7．4．1 計數排序

7．4．2 桶排序

7．4．3 基數排序

7．5 工程實踐和思考

問題1：電話號碼排序

問題2：大數據下的排序問題

習題7

參考文獻

附錄

附錄1 異常處理

附錄2 模板 ^[2]