新編數(shù)據(jù)結(jié)構(gòu)案例教程：微課版（C/C++語言）

目錄
第1篇緒論篇

第1章緒論

1．1什么是數(shù)據(jù)結(jié)構(gòu)

1．1．1數(shù)據(jù)結(jié)構(gòu)的產(chǎn)生與發(fā)展

1．1．2數(shù)據(jù)結(jié)構(gòu)的基本概念

1．1．3邏輯結(jié)構(gòu)的種類

1．1．4數(shù)據(jù)的存儲結(jié)構(gòu)

1．2抽象數(shù)據(jù)

1．2．1數(shù)據(jù)類型

1．2．2抽象數(shù)據(jù)類型的表示與實現(xiàn)

1．3算法及其性能分析

1．3．1算法

1．3．2算法設(shè)計的目標

1．3．3算法的時間復雜度度量

1．3．4算法的空間復雜度度量

1．4STL概述

1．4．1STL的發(fā)展和特點

1．4．2C++標準庫和STL

1．4．3數(shù)據(jù)結(jié)構(gòu)和STL的關(guān)系

1．5綜合案例

1．5．1哥德巴赫猜想問題

1．5．2連續(xù)整數(shù)問題

本章小結(jié)

第2篇線性結(jié)構(gòu)篇

第2章線性表

2．1線性表的抽象數(shù)據(jù)類型

2．1．1線性表的定義

2．1．2線性表的抽象數(shù)據(jù)類型描述

2．2線性表的順序存儲結(jié)構(gòu)

2．2．1線性表的順序存儲結(jié)構(gòu)——順序表

2．2．2順序表基本運算的實現(xiàn)

2．3線性表的鏈式存儲結(jié)構(gòu)

2．3．1線性表的鏈式存儲結(jié)構(gòu)——鏈表

2．3．2單鏈表基本運算的實現(xiàn)

2．3．3雙鏈表

2．3．4循環(huán)鏈表

2．3．5STL與鏈表

2．4綜合案例

2．4．1一元多項式的表示及相加運算

2．4．2魔法師發(fā)牌問題

2．4．3約瑟夫問題

本章小結(jié)

第3章棧與隊列

3．1棧

3．1．1棧的概述

3．1．2棧的順序存儲結(jié)構(gòu)

3．1．3棧的鏈式存儲結(jié)構(gòu)

3．2棧綜合案例

3．2．1進制轉(zhuǎn)換

3．2．2表達式求值

3．2．3檢驗表達式中的括號匹配情況

3．2．4棧與遞歸問題

3．3隊列

3．3．1隊列的定義和抽象數(shù)據(jù)類型

3．3．2隊列的順序存儲

3．3．3隊列的鏈式存儲

3．3．4優(yōu)先級隊列

3．4STL中的棧與隊列

3．4．1STL中的棧

3．4．2STL中的隊列

3．4．3STL中的優(yōu)先隊列的使用方法

3．5隊列綜合案例

3．5．1打印楊輝三角形

3．5．2報數(shù)問題

3．5．3舞伴問題

本章小結(jié)

第4章串

4．1串的基本概念和抽象數(shù)據(jù)類型

4．1．1串的基本概念

4．1．2串的抽象數(shù)據(jù)類型

4．2串的存儲結(jié)構(gòu)

4．2．1串的順序存儲結(jié)構(gòu)——順序串

4．2．2串的鏈式存儲結(jié)構(gòu)——鏈串

4．3串的模式匹配

4．3．1串的古典匹配算法

4．3．2串的KMP算法

4．4綜合案例

4．4．1文本編輯

4．4．2建立詞索引表

本章小結(jié)

第5章數(shù)組和廣義表

5．1數(shù)組的定義及抽象數(shù)據(jù)類型

5．1．1數(shù)組的定義

5．1．2數(shù)組的抽象數(shù)據(jù)類型

5．2數(shù)組的順序存儲與尋址

5．2．1以行序為主序

5．2．2以列序為主序

5．3特殊矩陣及其壓縮存儲

5．3．1對稱矩陣

5．3．2下(上)三角矩陣

5．3．3對角矩陣

5．4稀疏矩陣

5．4．1稀疏矩陣的三元組表示

5．4．2稀疏矩陣的十字鏈表表示

5．5廣義表

5．5．1廣義表的定義

5．5．2廣義表的存儲結(jié)構(gòu)

5．5．3廣義表的運算

5．6綜合案例

5．6．1大整數(shù)相乘

5．6．2荷蘭國旗問題

本章小結(jié)

第3篇樹形結(jié)構(gòu)篇

第6章樹和二叉樹

6．1樹

6．1．1樹的定義

6．1．2樹的術(shù)語

6．1．3樹的基本性質(zhì)

6．1．4樹的抽象數(shù)據(jù)類型

6．2二叉樹

6．2．1二叉樹的定義

6．2．2二叉樹的性質(zhì)

6．2．3二叉樹的抽象數(shù)據(jù)類型

6．2．4二叉樹的存儲結(jié)構(gòu)

6．3二叉樹的基本操作

6．3．1中序遍歷

6．3．2先序遍歷

6．3．3后序遍歷

6．3．4層次遍歷

6．3．5二叉樹遍歷的應用

6．3．6二叉樹遍歷的非遞歸實現(xiàn)

6．4線索二叉樹

6．4．1線索二叉樹的概念

6．4．2線索化二叉樹

6．4．3遍歷線索二叉樹

6．5樹與森林

6．5．1樹的存儲結(jié)構(gòu)

6．5．2森林與二叉樹的轉(zhuǎn)換

6．5．3樹的遍歷與森林的遍歷

6．6哈夫曼樹及其應用

6．6．1哈夫曼樹的基本概念

6．6．2哈夫曼樹構(gòu)造算法

6．6．3哈夫曼編碼

6．7STL中實現(xiàn)樹結(jié)構(gòu)

6．7．1STL中的vector

6．7．2STL中的map

6．8綜合案例——學校建模問題

本章小結(jié)

第4篇圖形結(jié)構(gòu)篇

第7章圖

7．1圖的概念

7．1．1圖的定義和術(shù)語

7．1．2圖的抽象數(shù)據(jù)類型

7．2圖的存儲表示

7．2．1鄰接矩陣

7．2．2鄰接表

7．2．3十字鏈表

7．3圖的遍歷與連通性

7．3．1深度優(yōu)先遍歷

7．3．2廣度優(yōu)先遍歷

7．3．3連通分量

7．4最小生成樹

7．4．1普里姆算法

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

7．5最短路徑

7．5．1單源最短路徑

7．5．2全源最短路徑

7．6活動網(wǎng)絡(luò)

7．6．1用頂點表示活動的AOV網(wǎng)絡(luò)

7．6．2AOE圖與關(guān)鍵路徑

7．7綜合案例

7．7．1道路修建問題

7．7．2回家路線問題

7．7．3棍子還原問題

本章小結(jié)

第5篇數(shù)據(jù)運算篇

第8章查找

8．1查找的基本概念

8．2靜態(tài)表的查找

8．2．1順序查找

8．2．2折半查找

8．2．3斐波那契查找

8．2．4分塊查找

8．3動態(tài)查找表

8．3．1二叉排序樹

8．3．2平衡二叉樹

8．3．3B-樹

8．3．4B+樹

8．4哈希表查找

8．4．1哈希表的基本概念

8．4．2哈希函數(shù)構(gòu)造方法

8．4．3哈希沖突解決方法

8．4．4哈希表上的查找分析

8．5STL中的查找

8．6綜合案例——拼寫檢查問題

本章小結(jié)

第9章排序

9.1排序的基本概念

9.2插入排序

9.2.1直接插入排序

9.2.2希爾排序

9.3交換排序

9.3.1冒泡排序

9.3.2快速排序

9.4選擇排序

9.4.1簡單選擇排序

9.4.2錦標賽排序

9.4.3堆排序

9.5二路歸并排序

9.6基數(shù)排序

9.7內(nèi)部排序方法的比較

9.8STL中的排序

9.9綜合案例——比賽排名問題

本章小結(jié)

第10章ACM經(jīng)典案例

10.1遞歸算法

10.1.1三柱漢諾塔問題

10.1.2傳染病問題

10.1.3N皇后問題

10.2DFS與BFS問題

10.2.1DFS之迷宮難題

10.2.2BFS之管道和指針游戲

本章小結(jié)

附錄A全國計算機專業(yè)數(shù)據(jù)結(jié)構(gòu)考研大綱

參考文獻