數據結構：Java語言描述（第2版）

本書是浙江省“十一五”規劃重點建設教材，內容涵蓋了教育部計算機科學與技術教指委關於“高等學校計算機科學與技術本科專業規範”中制定的課程體系中的核心知識，並在緊扣考研大綱的前提下剔除了一些難度較大的內容。本書採用Java語言作為描述算法的語言，共9章，可分成兩大部分。第一部分主要介紹線性表、棧、佇列、串、數組、樹和圖等基本數據結構的特點、存儲方式、運算原理、實現方法以及它們在現實中的典型套用； 第二部分主要討論查找與排序這兩種最常用操作的實現原理、方法及性能分析。全書條理清楚、語言精練、重點突出，敘述循序漸進、深入淺出； 表達通俗易懂，特別注重理論與實踐相結合； 強調算法實現方法的分析，並通過豐富、典型的實例來強化知識的實際套用。

基本介紹

• 書名：數據結構：Java語言描述（第2版）
• 作者：劉小晶、杜選、朱蓉、杜衛鋒
• ISBN：9787302389446
• 定價：49元
• 出版社：清華大學出版社
• 出版時間：2015.04.01

書籍信息

作者：劉小晶、杜選、朱蓉、杜衛鋒
定價：49元
印次：2-3
ISBN：9787302389446
出版日期：2015.04.01
印刷日期：2015.12.24

目錄

第1章緒論

1.1數據結構課程討論的內容

1.1.1求解問題舉例

1.1.2本課程討論的內容

1.2基本概念與術語

1.2.1數據與數據結構

1.2.2數據類型

1.2.3抽象數據類型

1.3算法和算法分析

1.3.1算法的基本概念

1.3.2算法的描述

1.3.3算法分析

1.3.4算法設計舉例

1.4Java提供的泛型方法

小結

習題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.3.4其他鍊表

2.4順序表與鍊表的比較

2.5線性表的套用舉例

小結

習題2

第3章棧與佇列

3.1棧

3.1.1棧的概念

3.1.2棧的抽象數據類型描述

3.1.3順序棧及其基本操作的實現

3.1.4鏈棧及其基本操作的實現

3.1.5棧的套用

3.2佇列

3.2.1佇列的概念

3.2.2佇列的抽象數據類型描述

3.2.3順序佇列及其基本操作的實現

3.2.4鏈佇列及其基本操作的實現

3.2.5佇列的套用

3.2.6優先權佇列

3.3棧與佇列的比較

3.4棧與佇列的綜合套用舉例

小結

習題3

第4章串與數組

4.1串概述

4.1.1串的基本概念

4.1.2串的抽象數據類型描述

4.2串的存儲結構

4.2.1串的順序存儲結構

4.2.2串的鏈式存儲結構

4.3順序串的實現

4.3.1順序串的類定義

4.3.2串的基本操作實現

4.4串的模式匹配操作

4.4.1BruteForce模式匹配算法

4.4.2KMP模式匹配算法

4.5串的套用舉例

4.6數組的概念及順序存儲結構

4.6.1數組的基本概念

4.6.2數組的抽象數據類型描述

4.6.3數組的順序存儲結構

4.7特殊矩陣的壓縮存儲

4.7.1對稱矩陣的壓縮存儲

4.7.2三角矩陣的壓縮存儲

4.7.3對角矩陣的壓縮存儲

4.8稀疏矩陣的壓縮存儲

4.8.1稀疏矩陣的三元組表存儲

4.8.2稀疏矩陣的十字鍊表存儲

4.9數組的套用舉例

小結

習題4

第5章樹與二叉樹

5.1樹的基本概念

5.2二叉樹概述

5.2.1二叉樹的基本概念

5.2.2二叉樹的性質

5.2.3二叉樹的存儲結構

5.3二叉樹的遍歷

5.3.1二叉樹的遍歷方法及其實現

5.3.2二叉樹遍歷算法的套用舉例

5.3.3建立二叉樹

5.4哈夫曼樹及哈夫曼編碼

5.4.1哈夫曼樹的基本概念

5.4.2哈夫曼樹和哈夫曼編碼的構造方法

5.4.3構造哈夫曼樹和哈夫曼編碼類的描述

5.5樹與森林

5.5.1樹、森林與二叉樹之間的轉換

5.5.2樹的存儲結構

5.5.3樹和森林的遍歷

小結

習題5

第6章圖

6.1圖概述

6.1.1圖的基本概念

6.1.2圖的抽象數據類型描述

6.2圖的存儲結構

6.2.1鄰接矩陣

6.2.2鄰接表

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.6拓撲排序

6.6.1拓撲排序的基本概念

6.6.2拓撲排序的實現

6.7關鍵路徑

小結

第7章內排序

7.1排序的基本概念

7.2插入排序

7.2.1直接插入排序

7.2.2希爾排序

7.3交換排序

7.3.1冒泡排序

7.3.2快速排序

7.4選擇排序

7.4.1直接選擇排序

7.4.2樹形選擇排序

7.4.3堆排序

7.5歸併排序

7.6基數排序

7.6.1多關鍵字排序

7.6.2鏈式基數排序

小結

習題7

第8章外排序

8.1外排序概述

8.2磁碟排序

8.2.1磁碟信息的存取

8.2.2多路平衡歸併

8.2.3置換—選擇排序

8.2.4最優歸併樹

小結

習題8

第9章查找

9.1查找的基本概念

9.2靜態表查找

9.2.1順序查找

9.2.2二分查找

9.2.3分塊查找

9.3動態表查找

9.3.1二叉排序樹

9.3.2平衡二叉樹

9.3.3B-樹和B+樹

9.3.4紅黑樹簡介

9.4哈希表查找

9.4.1哈希表的定義

9.4.2常用的哈希函式

9.4.3處理衝突的方法

9.4.4哈希表的查找和性能分析

小結

習題9

附錄A習題參考答案

參考文獻