數據結構

本書在選材與編排上，貼近當前普通高等院校“數據結構”課程的現狀和發展趨勢，符合研究生考試大綱，內容難度適中，突出實用性和應用性。全書共9章，內容包括緒論、線性表、棧和隊列、串、數組和廣義表、樹和二叉樹、圖、查找、排序。

本書可作為普通高等院校計算機和信息技術相關專業“數據結構”課程的教材，也可供從事計算機工程與應用工作的科技工作者參考。

本書封面貼有清華大學出版社防偽標籤，無標籤者不得銷售。

朱智林，男，博士，教授，山東工商學院信號與信息處理學科帶頭人，山東省精品課程《單片機原理及應用》負責人。研究方向為，嵌入式系統綜合設計，軟/硬件協同設計。完成國家自然基金、國防預研項目、省自然基金項目等多項，發表學術論文40餘篇，獲得山東省科技進步二等獎1項，山東省高等教育省級教學成果二等獎2項，三等獎1項。

第1章緒論

1．1數據結構的概念

1．2數據結構的組成與分類

1．2．1數據的邏輯結構

1．2．2數據的物理結構

1．2．3數據的運算(集合)

1．3數據類型與抽象數據類型

1．3．1數據類型

1．3．2抽象數據類型

1.4算法和算法分析

1.4.1算法描述

1.4.2算法分析

習題

第2章線性表

2．1線性表的邏輯結構

2．1．1線性表的定義

2．1．2線性表的抽象數據類型

2．2線性表的順序存儲結構及實現

2．2．1順序表的定義

2．2．2順序表抽象數據類型定義

2．2．3順序表基本操作

2．2．4順序表應用舉例

2．3線性表的鏈式存儲

2．3．1單鏈表

2．3．2單鏈表的應用

2．3．3循環鏈表

2．3．4雙鏈表

2．4應用實例

2．4．1一元多項式的表示與加法實現

2．4．2集合運算

習題

第3章棧和隊列

3.1棧

3.1.1棧的定義和操作

3.1.2棧的順序存儲

3.1.3棧的鏈表存儲

3．2應用舉例

3.3隊列

3.3.1隊列的定義

3．3．2隊列的表示與實現

3．4隊列的應用舉例

習題

第4章串

4.1串和抽象數據類型

4.1.1串定義

4.1.2抽象數據類型定義

4．2串的存儲結構

4．2．1順序存儲

4．2．2鏈接存儲

4．2．3串的操作

4．3串的模式匹配算法

4．3．1BruteForce算法

4．3．2KMP算法

習題

第5章數組和廣義表

5.1數組

5.1.1數組定義

5.1.2數組的存儲結構

5.1.3特殊矩陣的壓縮存儲

5．2廣義表

5．2．1廣義表抽象數據類型

5．2．2廣義表的存儲結構

習題

第6章樹和二叉樹

6.1樹

6.1.1樹的定義

6.1.2基本術語

6．2二叉樹

6．2．1二叉樹的定義

6．2．2二叉樹的性質

6．2．3二叉樹的遍歷規則

6．2．4二叉樹抽象數據類型

6．2．5二叉樹的存儲結構

6．3遍歷二叉樹

6．3．1遍歷二叉樹的非遞歸算法

6．3．2遍歷二叉樹的遞歸算法

6．3．3二叉樹遍歷的應用舉例

6．4線索二叉樹

6．4．1線索二叉樹的定義

6．4．2二叉樹的線索化

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

6.5哈夫曼樹及其應用

6.5.1基本概念

6.5.2哈夫曼算法

6.5.3哈夫曼編碼

習題

第7章圖

7．1圖及其抽象數據類型

7．1．1圖的基本概念

7．1．2圖抽象數據類型

7．2圖的存儲結構

7．2．1鄰接矩陣

7．2．2鄰接表

7．2．3有向圖的十字接表

7．2．4無向圖的鄰接多重表

7．3圖的遍歷

7．3．1深度優先遍歷

7．3．2廣度優先遍歷

7．4最小生成樹

7．4．1普里姆算法

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

7．5最短路徑

7．5．1單源最短路徑

7．5．2所有頂點對之間的最短路徑

習題

第8章查找

8.1查找的基本概念

8.1.1查找

8.1.2查找表

8.1.3平均查找長度ASL

8．2線性表的查找

8．2．1順序查找

8．2．2折半查找

8．2．3分塊查找

8．3散列表的查找

8．3．1散列表的基本概念

8．3．2散列函數

8．3．3衝突的解決

8．3．4散列表查找及其分析

習題

第9章排序

9.1基本概念

9.1.1排序的概念

9.1.2排序算法的穩定性

9.1.3內排序與外排序

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．5基數排序

9．6外排序

9．6．1路平衡歸併

9．6．2k路平衡歸併與敗者樹

9．6．3最佳歸併樹

9．7內部排序方法比較

習題

參考文獻