數據結構

費如純  遼寧科技學院教授，武漢大學博士。曾任遼寧科技學院電子與信息工程學院副院長（2010—2016年），遼寧科技學院曙光大數據學院副院長（2016—2018年），遼寧科技學院信息化管理辦公室主任（2018—2022年）。目前主要研究方向為密碼學、網絡安全及大數據技術。出版教材5部、學術專著1部。在國內外學術期刊發表EI檢索論文10余篇。

 

目錄

 

 

 

 

 

第1章緒論

 

1.1數據結構有什麼用

 

1.2基本概念

 

1.2.1數據

 

1.2.2數據結構

 

1.2.3數據類型

 

1.3算法及性能分析

 

1.3.1算法

 

1.3.2算法描述

 

1.3.3性能分析

 

小結

 

習題1

 

第2章線性表

 

2.1基本概念

 

2.1.1線性表的概念

 

2.1.2抽象數據類型

 

2.2順序表

 

2.2.1基本概念

 

2.2.2插入與刪除操作

 

2.2.3數據類型及算法描述

 

2.3動態鏈表

 

2.3.1基本概念

 

2.3.2單鏈表

 

2.3.3雙向鏈表

 

2.4靜態鏈表

 

2.4.1基本概念

 

2.4.2存儲結構

 

2.4.3基本操作

 

2.5集合的線性表實現

 

2.5.1用線性表存儲集合元素

 

2.5.2位圖

 

2.5.3並查集

 

2.6應用案例

 

小結

 

習題2

 

第3章棧和隊列

 

3.1棧

 

3.1.1基本概念

 

3.1.2順序棧

 

3.1.3鏈式棧

 

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章串、數組和廣義表

 

4.1串

 

4.1.1基本概念

 

4.1.2存儲結構

 

4.1.3模式匹配

 

4.2數組

 

4.2.1基本概念和存儲結構

 

4.2.2特殊矩陣的壓縮存儲

 

4.3廣義表

 

4.3.1基本概念

 

4.3.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.3.4二元運算表達式與二叉樹的遍歷

 

5.3.5非遞歸遍歷

 

5.3.6通過遍歷對二叉樹進行處理

 

5.4線索二叉樹

 

5.4.1線索二叉樹的基本概念

 

5.4.2線索二叉樹的構建

 

5.4.3線索二叉樹的遍歷

 

5.5樹和森林

 

5.5.1樹和森林的存儲結構

 

5.5.2樹和森林與二叉樹之間的相互轉換

 

5.5.3樹和森林的遍歷

 

5.5.4通過遍歷對樹和森林進行處理

 

5.5.5基於森林的並查集

 

5.6哈夫曼樹

 

5.6.1基本概念

 

5.6.2哈夫曼樹的構建

 

5.6.3哈夫曼編碼與解碼

 

5.7應用案例

 

小結

 

習題5

 

第6章圖

 

6.1基本概念

 

6.2圖的存儲結構

 

6.2.1鄰接矩陣

 

6.2.2鄰接表

 

6.2.3十字鏈表

 

6.3圖的遍歷

 

6.3.1深度優先搜索

 

6.3.2廣度優先搜索

 

6.4圖的連通性

 

6.4.1路徑

 

6.4.2生成樹

 

6.4.3可達分量與連通分量

 

6.4.4最小生成樹

 

6.5最短路徑

 

6.5.1迪傑斯特拉算法

 

6.5.2弗洛伊德算法

 

6.6有向無環圖

 

6.6.1拓撲排序

 

6.6.2關鍵路徑

 

6.7應用案例

 

6.7.1迷宮問題

 

6.7.2華容道遊戲

 

小結

 

習題6

 

第7章查找

 

7.1基本概念

 

7.2順序查找

 

7.3折半查找

 

7.4索引順序查找

 

7.5二叉排序樹與平衡二叉樹

 

7.5.1二叉排序樹

 

7.5.2平衡二叉樹

 

7.6B樹

 

7.6.1B樹的定義

 

7.6.2B樹的操作

 

7.7哈希查找

 

7.7.1基本概念

 

7.7.2哈希函數

 

7.7.3解決沖突的方法

 

7.7.4插入、刪除與擴容

 

小結

 

習題7

 

第8章排序

 

8.1基本概念

 

8.2插入排序

 

8.2.1直接插入排序

 

8.2.2折半插入排序

 

8.2.3希爾排序

 

8.3交換排序

 

8.3.1冒泡排序

 

8.3.2快速排序

 

8.4選擇排序

 

8.4.1簡單選擇排序

 

8.4.2樹狀選擇排序

 

8.4.3堆排序

 

8.5歸並排序

 

8.6基於比較的排序方法的對比

 

8.7計數排序和基數排序

 

8.7.1計數排序

 

8.7.2基數排序

 

8.8外排序

 

小結

 

習題8

 

參考文獻