王曉東編著的《數據結構（C++語言版）》以ACM和IEEE/CS Computing Curricula 2005課程體系，以及教育部計算機科學與技術教學指導委員會發布的“高等學校計算機科學與技術本科專業規範”中制定的關於數據結構和算法設計與分析的知識結構和體系為依據，以基本數據結構和抽象數據類型為知識單元編寫而成。全書共分12章，涵蓋cc2005課程體系中有關算法與數據結構的知識結構和體系的重要內容，包括數據結構與算法概論，線性表，棧，佇列，集合，排序與選擇，樹，二叉搜尋樹，堆與優先佇列，散列，並查集，圖與相關算法。全書採用面向對象的C++語言作為描述語言，內容豐富，敘述簡明，理論與實踐並重，每章設計有套用舉例和數據結構與算法實驗題，並為任課教師免費提供電子課件和課程實驗用數據。《數據結構（C++語言版）》可作為高等學校計算機、電子信息、信息與計算科學、信息管理與信息系統等專業數據結構課程教材，也適合工程技術人員和自學者學習參考。點擊連結進入舊版： 數據結構(C++語言版)
基本介紹
- 書名：國家級精品課程主幹教材:數據結構
- 作者：王曉東
- 出版日期：2008年12月1日
- 語種：簡體中文
- ISBN：9787030230072
- 外文名：Data Structures
- 出版社：科學出版社
- 頁數：278頁
- 開本：16
- 品牌：科學出版社
內容簡介,圖書目錄,
內容簡介
《國家級精品課程主幹教材:數據結構(C++語言版)》可作為高等學校計算機、電子信息、信息與計算科學、信息管理與信息系統等專業數據結構課程教材，也適合工程技術人員和自學者學習參考。
圖書目錄
前言
第1章數據結構與算法概論
1.1算法及其複雜性的概念
1.1.1算法與程式
1.1.2算法複雜性的概念
1.1.3算法複雜性的漸近性態
1.2數據結構與抽象數據類型
1.3用C++描述數據結構與算法
1.3.1指針和引用
1.3.2函式與參數傳遞
1.3.3C++的類
1.3.4類的對象
1.3.5模板
1.3.6動態存儲分配
1.4遞歸
1.5套用舉例
習題1
實驗1
實驗題1.1實係數復變多項式問題
實驗題1.2平面幾何問題
實驗題1.3m進制數問題
第2章線性表
2.1表的基本概念
2.2用數組實現表
2.3用指針實現表
2.4用間接定址方法實現表
2.5用游標實現表
2.6循環鍊表
2.7雙鍊表
2.8表的搜尋游標
2.9套用舉例
習題2
實驗2
實驗題2.1實係數一元多項式問題
實驗題2.2Josephus排列問題1
實驗題2.3向量分類問題
實驗題2.4條形圖輪廓問題
實驗題2.5Josephus排列問題2
第3章棧
3.1棧的基本概念
3.2用數組實現棧
3.3用指針實現棧
3.4套用舉例
習題3
實驗3
實驗題3.1車皮編序問題
實驗題3.2單柱Hanoi塔問題
實驗題3.3多棧模擬問題
實驗題3.4親兄弟問題
第4章佇列
4.1佇列的基本概念
4.2用指針實現佇列
4.3用循環數組實現佇列
4.4套用舉例
習題4
實驗4
實驗題4.1組佇列問題
實驗題4.2雙棧佇列問題
實驗題4.3猴子分桃問題
實驗題4.4逆序表問題
第5章集合
5.1集合的基本概念
5.2抽象數據類型集合
5.3用位向量實現集合
5.4用鍊表實現集合
5.5套用舉例
習題5
實驗5
實驗題5.1半數集問題
第6章排序與選擇
6.1簡單排序算法
6.1.1冒泡排序算法
6.1.2插入排序算法
6.1.3選擇排序算法
6.1.4簡單排序算法的計算複雜性
6.2快速排序算法
6.2.1算法基本思想及實現
6.2.2算法性能分析
6.2.3隨機快速排序算法
6.3合併排序算法
6.3.1算法基本思想及實現
6.3.2消除遞歸
6.3.3自然合併排序算法
6.4線性時間排序算法
6.4.1計數排序算法
6.4.2桶排序算法
6.5中位數與第k小元素
6.5.1平均情況下的線性時間選擇算法
6.5.2最壞情況下的線性時間選擇算法
6.6套用舉例
習題6
實驗6
實驗題6.1交換排序問題
實驗題6.2DNA排序問題
實驗題6.3輸油管道問題
實驗題6.4最優服務次序問題
第7章樹
7.1樹的定義
7.2樹的遍歷
7.3樹的表示法
7.3.1父結點數組表示法
7.3.2兒子鍊表表示法
7.3.3左兒子右兄弟表示法
7.4二叉樹的基本概念
7.5二叉樹的運算
7.6二叉樹的實現
7.6.1二叉樹的順序存儲結構
7.6.2二叉樹的結點度表示法
7.6.3用指針實現二叉樹
7.7線索二叉樹
7.8套用舉例
習題7
實驗7
實驗題7.1層序列表問題
實驗題7.2最近公共祖先問題
實驗題7.3子樹問題—
實驗題7.4同構二叉樹問題
實驗題7.5後序中序遍歷問題
第8章二叉搜尋樹
8.1有序集與二叉搜尋樹
8.1.1抽象數據類型字典
8.1.2用數組實現字典
8.1.3二叉搜尋樹的基本概念
8.2實現二叉搜尋樹
8.3平衡的二叉搜尋樹AVL樹
8.3.1AVL樹的定義和性質
8.3.2旋轉變換
8.3.3AVL樹的插入與重平衡運算
8.3.4AVL樹的刪除與重平衡運算
8.4套用舉例
習題8
實驗8
實驗題8.1裝箱問題
實驗題8.2電路板連線問題
實驗題8.3辭典問題
第9章堆與優先佇列
9.1優先佇列的基本概念
9.2用字典實現優先佇列
9.3優先權樹和堆
9.4用數組實現堆
9.5可並優先佇列
9.5.1左偏樹的定義
9.5.2用左偏樹實現可並優先佇列
9.6套用舉例
習題9
實驗9
實驗題9.1區間相交問題
實驗題9.2整數字典問題
實驗題9.3最小權語言問題
實驗題9.4二叉搜尋堆問題
實驗題9.5區間覆蓋問題
第10章散列
10.1抽象數據類型符號表
10.2開散列
10.3閉散列
10.4散列函式的效率
10.5重新散列
10.6套用舉例
習題10
實驗10
實驗題10.1偽隨機排列問題
實驗題10.2字元串散列問題
實驗題10.3英文文本分析問題
實驗題10.4最長模式串問題
第11章並查集
11.1並查集的基本概念
11.2用父結點數組實現並查集
11.3套用舉例
習題11
實驗11
實驗題11.1二進制方程問題
實驗題11.2網路連通問題
實驗題11.3朋友問題
實驗題11.4等價類劃分問題
第12章圖
12.1圖的基本概念
12.2抽象數據類型圖
12.3圖的表示法
12.3.1鄰接矩陣表示法
12.3.2鄰接表表示法
12.3.3緊縮鄰接表
12.4用鄰接矩陣實現圖
12.4.1用鄰接矩陣實現賦權有向圖
12.4.2用鄰接矩陣實現賦權無向圖
12.4.3用鄰接矩陣實現有向圖
12.4.4用鄰接矩陣實現無向圖
12.5用鄰接表實現圖
12.5.1鄰接表基類
12.5.2用鄰接表實現有向圖
12.5.3用鄰接表實現無向圖
12.5.4用鄰接表實現賦權有向圖
12.5.5用鄰接表實現賦權無向圖
12.6圖的遍歷
12.6.1圖的搜尋游標
12.6.2廣度優先搜尋
12.6.3深度優先搜尋
12.7最短路徑算法
12.7.1單源最短路徑算法
12.7.2Bellman—Ford最短路徑算法
12.7.3所有頂點對之間的最短路徑算法
12.8最小支撐樹
12.8.1最小支撐樹性質
12.8.2最小支撐樹的Prim算法
12.8.3最小支撐樹的Kruskal算法
12.9圖匹配算法
12.10套用舉例
習題12
實驗12
實驗題12.1圖的二著色問題
實驗題12.2賦權有向圖中心問題
實驗題12.3最長簡單路徑問題
實驗題12.4計算機網路問題
實驗題12.5差分約束問題
實驗題12.6有截止時間的工作排序問題
實驗題12.7無向圖的連通分支問題
參考文獻
第1章數據結構與算法概論
1.1算法及其複雜性的概念
1.1.1算法與程式
1.1.2算法複雜性的概念
1.1.3算法複雜性的漸近性態
1.2數據結構與抽象數據類型
1.3用C++描述數據結構與算法
1.3.1指針和引用
1.3.2函式與參數傳遞
1.3.3C++的類
1.3.4類的對象
1.3.5模板
1.3.6動態存儲分配
1.4遞歸
1.5套用舉例
習題1
實驗1
實驗題1.1實係數復變多項式問題
實驗題1.2平面幾何問題
實驗題1.3m進制數問題
第2章線性表
2.1表的基本概念
2.2用數組實現表
2.3用指針實現表
2.4用間接定址方法實現表
2.5用游標實現表
2.6循環鍊表
2.7雙鍊表
2.8表的搜尋游標
2.9套用舉例
習題2
實驗2
實驗題2.1實係數一元多項式問題
實驗題2.2Josephus排列問題1
實驗題2.3向量分類問題
實驗題2.4條形圖輪廓問題
實驗題2.5Josephus排列問題2
第3章棧
3.1棧的基本概念
3.2用數組實現棧
3.3用指針實現棧
3.4套用舉例
習題3
實驗3
實驗題3.1車皮編序問題
實驗題3.2單柱Hanoi塔問題
實驗題3.3多棧模擬問題
實驗題3.4親兄弟問題
第4章佇列
4.1佇列的基本概念
4.2用指針實現佇列
4.3用循環數組實現佇列
4.4套用舉例
習題4
實驗4
實驗題4.1組佇列問題
實驗題4.2雙棧佇列問題
實驗題4.3猴子分桃問題
實驗題4.4逆序表問題
第5章集合
5.1集合的基本概念
5.2抽象數據類型集合
5.3用位向量實現集合
5.4用鍊表實現集合
5.5套用舉例
習題5
實驗5
實驗題5.1半數集問題
第6章排序與選擇
6.1簡單排序算法
6.1.1冒泡排序算法
6.1.2插入排序算法
6.1.3選擇排序算法
6.1.4簡單排序算法的計算複雜性
6.2快速排序算法
6.2.1算法基本思想及實現
6.2.2算法性能分析
6.2.3隨機快速排序算法
6.3合併排序算法
6.3.1算法基本思想及實現
6.3.2消除遞歸
6.3.3自然合併排序算法
6.4線性時間排序算法
6.4.1計數排序算法
6.4.2桶排序算法
6.5中位數與第k小元素
6.5.1平均情況下的線性時間選擇算法
6.5.2最壞情況下的線性時間選擇算法
6.6套用舉例
習題6
實驗6
實驗題6.1交換排序問題
實驗題6.2DNA排序問題
實驗題6.3輸油管道問題
實驗題6.4最優服務次序問題
第7章樹
7.1樹的定義
7.2樹的遍歷
7.3樹的表示法
7.3.1父結點數組表示法
7.3.2兒子鍊表表示法
7.3.3左兒子右兄弟表示法
7.4二叉樹的基本概念
7.5二叉樹的運算
7.6二叉樹的實現
7.6.1二叉樹的順序存儲結構
7.6.2二叉樹的結點度表示法
7.6.3用指針實現二叉樹
7.7線索二叉樹
7.8套用舉例
習題7
實驗7
實驗題7.1層序列表問題
實驗題7.2最近公共祖先問題
實驗題7.3子樹問題—
實驗題7.4同構二叉樹問題
實驗題7.5後序中序遍歷問題
第8章二叉搜尋樹
8.1有序集與二叉搜尋樹
8.1.1抽象數據類型字典
8.1.2用數組實現字典
8.1.3二叉搜尋樹的基本概念
8.2實現二叉搜尋樹
8.3平衡的二叉搜尋樹AVL樹
8.3.1AVL樹的定義和性質
8.3.2旋轉變換
8.3.3AVL樹的插入與重平衡運算
8.3.4AVL樹的刪除與重平衡運算
8.4套用舉例
習題8
實驗8
實驗題8.1裝箱問題
實驗題8.2電路板連線問題
實驗題8.3辭典問題
第9章堆與優先佇列
9.1優先佇列的基本概念
9.2用字典實現優先佇列
9.3優先權樹和堆
9.4用數組實現堆
9.5可並優先佇列
9.5.1左偏樹的定義
9.5.2用左偏樹實現可並優先佇列
9.6套用舉例
習題9
實驗9
實驗題9.1區間相交問題
實驗題9.2整數字典問題
實驗題9.3最小權語言問題
實驗題9.4二叉搜尋堆問題
實驗題9.5區間覆蓋問題
第10章散列
10.1抽象數據類型符號表
10.2開散列
10.3閉散列
10.4散列函式的效率
10.5重新散列
10.6套用舉例
習題10
實驗10
實驗題10.1偽隨機排列問題
實驗題10.2字元串散列問題
實驗題10.3英文文本分析問題
實驗題10.4最長模式串問題
第11章並查集
11.1並查集的基本概念
11.2用父結點數組實現並查集
11.3套用舉例
習題11
實驗11
實驗題11.1二進制方程問題
實驗題11.2網路連通問題
實驗題11.3朋友問題
實驗題11.4等價類劃分問題
第12章圖
12.1圖的基本概念
12.2抽象數據類型圖
12.3圖的表示法
12.3.1鄰接矩陣表示法
12.3.2鄰接表表示法
12.3.3緊縮鄰接表
12.4用鄰接矩陣實現圖
12.4.1用鄰接矩陣實現賦權有向圖
12.4.2用鄰接矩陣實現賦權無向圖
12.4.3用鄰接矩陣實現有向圖
12.4.4用鄰接矩陣實現無向圖
12.5用鄰接表實現圖
12.5.1鄰接表基類
12.5.2用鄰接表實現有向圖
12.5.3用鄰接表實現無向圖
12.5.4用鄰接表實現賦權有向圖
12.5.5用鄰接表實現賦權無向圖
12.6圖的遍歷
12.6.1圖的搜尋游標
12.6.2廣度優先搜尋
12.6.3深度優先搜尋
12.7最短路徑算法
12.7.1單源最短路徑算法
12.7.2Bellman—Ford最短路徑算法
12.7.3所有頂點對之間的最短路徑算法
12.8最小支撐樹
12.8.1最小支撐樹性質
12.8.2最小支撐樹的Prim算法
12.8.3最小支撐樹的Kruskal算法
12.9圖匹配算法
12.10套用舉例
習題12
實驗12
實驗題12.1圖的二著色問題
實驗題12.2賦權有向圖中心問題
實驗題12.3最長簡單路徑問題
實驗題12.4計算機網路問題
實驗題12.5差分約束問題
實驗題12.6有截止時間的工作排序問題
實驗題12.7無向圖的連通分支問題
參考文獻
