新編數(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ù)的存儲(chǔ)結(jié)構(gòu)

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

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

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

1．3算法及其性能分析

1．3．1算法

1．3．2算法設(shè)計(jì)的目標(biāo)

1．3．3算法的時(shí)間復(fù)雜度度量

1．3．4算法的空間復(fù)雜度度量

1．4STL概述

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

1．4．2C++標(biāo)準(zhǔn)庫和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線性表的順序存儲(chǔ)結(jié)構(gòu)

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

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

2．3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

2．3．1線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——鏈表

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

2．3．3雙鏈表

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

2．3．5STL與鏈表

2．4綜合案例

2．4．1一元多項(xiàng)式的表示及相加運(yùn)算

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

2．4．3約瑟夫問題

本章小結(jié)

第3章棧與隊(duì)列

3．1棧

3．1．1棧的概述

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

3．1．3棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

3．2棧綜合案例

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

3．2．2表達(dá)式求值

3．2．3檢驗(yàn)表達(dá)式中的括號(hào)匹配情況

3．2．4棧與遞歸問題

3．3隊(duì)列

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

3．3．2隊(duì)列的順序存儲(chǔ)

3．3．3隊(duì)列的鏈?zhǔn)酱鎯?chǔ)

3．3．4優(yōu)先級(jí)隊(duì)列

3．4STL中的棧與隊(duì)列

3．4．1STL中的棧

3．4．2STL中的隊(duì)列

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

3．5隊(duì)列綜合案例

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

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

3．5．3舞伴問題

本章小結(jié)

第4章串

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

4．1．1串的基本概念

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

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

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

4．2．2串的鏈?zhǔn)酱鎯?chǔ)結(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ù)組的順序存儲(chǔ)與尋址

5．2．1以行序?yàn)橹餍?br />
5．2．2以列序?yàn)橹餍?br />
5．3特殊矩陣及其壓縮存儲(chǔ)

5．3．1對(duì)稱矩陣

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

5．3．3對(duì)角矩陣

5．4稀疏矩陣

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

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

5．5廣義表

5．5．1廣義表的定義

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

5．5．3廣義表的運(yùn)算

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二叉樹的存儲(chǔ)結(jié)構(gòu)

6．3二叉樹的基本操作

6．3．1中序遍歷

6．3．2先序遍歷

6．3．3后序遍歷

6．3．4層次遍歷

6．3．5二叉樹遍歷的應(yīng)用

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

6．4線索二叉樹

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

6．4．2線索化二叉樹

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

6．5樹與森林

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

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

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

6．6哈夫曼樹及其應(yīng)用

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

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

6．6．3哈夫曼編碼

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

6．7．1STL中的vector

6．7．2STL中的map

6．8綜合案例——學(xué)校建模問題

本章小結(jié)

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

第7章圖

7．1圖的概念

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

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

7．2圖的存儲(chǔ)表示

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活動(dòng)網(wǎng)絡(luò)

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

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

7．7綜合案例

7．7．1道路修建問題

7．7．2回家路線問題

7．7．3棍子還原問題

本章小結(jié)

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

第8章查找

8．1查找的基本概念

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

8．2．1順序查找

8．2．2折半查找

8．2．3斐波那契查找

8．2．4分塊查找

8．3動(dòng)態(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錦標(biāo)賽排序

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全國計(jì)算機(jī)專業(yè)數(shù)據(jù)結(jié)構(gòu)考研大綱

參考文獻(xiàn)