數據結構與算法——C語言和Java語言描述

《數據結構與算法——C語言和Java語言描述》是2017年清華大學出版社出版的圖書，作者是唐懿芳、鐘達夫、林萍、陶南、鐘麗萍、崔曉坤。

基本介紹

• 書名：數據結構與算法——C語言和Java語言描述
• 作者：唐懿芳、鐘達夫、林萍、陶南、鐘麗萍、崔曉坤
• 出版時間：2017.06.01

出版信息

數據結構與算法——C語言和Java語言描述

作者：唐懿芳、鐘達夫、林萍、陶南、鐘麗萍、崔曉坤

定價：36元
印次：1-1
ISBN：9787302472650
出版日期：2017.06.01
印刷日期：2017.06.16

內容簡介

本書系統全面地講解了數據結構與算法的主要內容，包括線性表、棧和佇列、字元串、數組與矩陣、樹、圖、查找以及排序。對於每一種類型的數據結構，都詳細闡述了基本概念、各種不同的存儲結構和不同存儲結構上一些主要操作的算法，並給出完整的C語言代碼和Java代碼，有助於不同語言學習者的理解。C語言的指針概念雖較好地闡述了鍊表的結構，但目前軟體設計的主流方法是面向對象思想，所以本書在附錄中提供了各個算法對應的Java代碼。

目錄

第1章緒論1

1.1學習數據結構的意義1

1.1.1引言1

1.1.2數據結構研究什麼2

1.2數據結構的基本概念3

1.3算法及其描述4

1.3.1算法的概念和特性4

1.3.2算法設計的要求5

1.3.3算法的分析5

1.4小結7

1.5習題7

第2章線性表9

2.1線性表的定義及運算9

2.1.1線性表的定義9

2.1.2線性表的基本運算10

2.2順序線性表11

2.2.1順序存儲的定義11

2.2.2順序線性表的基本運算12

2.3線性表的鏈式存儲結構14

2.3.1線性表鏈式存儲結構的定義14

2.3.2單鍊表的定義15

2.3.3線性表鏈式存儲結構代碼描述15

2.3.4單鍊表的基本運算16

2.3.5單鍊表的創建20

2.4循環鍊表和雙向鍊表22

2.4.1循環鍊表22

2.4.2雙向鍊表23

2.5實訓24

實訓1隨機生成5個數放入順序表中,實現插入

和刪除操作24實訓2創建5個節點的單鍊表,隨機生成5個數並放入單鍊表中,

實現插入和刪除操作27

2.6小結33

2.7習題33

第3章棧和佇列34

3.1棧的定義和基本運算34

3.1.1棧的定義34

3.1.2棧的基本運算35

3.2順序棧35

3.2.1順序棧存儲的定義35

3.2.2順序棧的基本運算36

3.3鏈棧39

3.3.1鏈棧的定義39

3.3.2鏈棧的基本運算39

3.4佇列的定義和基本運算42

3.4.1佇列的定義42

3.4.2佇列的基本運算42

3.5順序佇列42

3.5.1順序佇列的存儲結構42

3.5.2順序佇列的基本運算45

3.6鏈式佇列49

3.6.1鏈式佇列的存儲結構49

3.6.2鏈式佇列的基本運算50

3.7實訓52

實訓1順序共享棧的簡單實現52

實訓2鏈式佇列分隊的簡單實現54

3.8小結57

3.9習題57

第4章字元串59

4.1字元串的定義和基本運算59

4.1.1字元串的定義59

4.1.2字元串的基本運算60

4.2串的線性存儲結構和基本運算的實現60

4.2.1串的賦值運算61

4.2.2求串的長度61

4.2.3判斷兩個串是否相等61

4.2.4求子串61

4.2.5串值的連線62

4.2.6插入子串62

4.2.7刪除子串63

4.3串的模式匹配算法63

4.3.1BruteForce算法的設計思路63

4.3.2BruteForce算法的實現過程66

4.3.3BruteForce算法的時間複雜度66

4.4實訓練習和掌握BruteForce算法66

4.5小結69

4.6習題69

第5章數組與矩陣71

5.1數組的基本概念71

5.1.1數組的定義71

5.1.2一維數組72

5.1.3二維數組72

5.1.4多維數組73

5.1.5數組的順序存儲結構73

5.2特殊矩陣的壓縮存儲74

5.2.1對稱矩陣74

5.2.2三角矩陣75

5.2.3對角矩陣76

5.3稀疏矩陣76

5.3.1三元組順序存儲表77

5.3.2稀疏矩陣的賦值運算77

5.3.3稀疏矩陣的轉置運算78

5.3.4稀疏矩陣的加法運算79

5.4實訓二維數組的相加81

5.5小結84

5.6習題85

第6章樹87

6.1樹的相關知識87

6.1.1樹的基本概念87

6.1.2樹的表示方法88

6.1.3樹的常用術語89

6.2樹的基本操作90

6.3樹的存儲結構90

6.3.1雙親表示法90

6.3.2孩子表示法91

6.3.3孩子兄弟表示法93

6.4二叉樹的定義和基本操作94

6.4.1二叉樹的定義94

6.4.2二叉樹的基本操作94

6.4.3二叉樹的性質95

6.4.4二叉樹的順序存儲結構96

6.4.5二叉樹的鍊表存儲結構98

6.5二叉樹的遍歷98

6.5.1二叉樹的先根遍歷方法99

6.5.2二叉樹的中根遍歷方法101

6.5.3二叉樹的後根遍歷方法102

6.5.4遍歷序列與二叉樹的結構103

6.6創建二叉樹105

6.6.1用順序存儲方式創建二叉樹105

6.6.2用鍊表方式創建二叉樹106

6.7樹、森林與二叉樹的轉換108

6.7.1一般樹轉換為二叉樹108

6.7.2二叉樹還原為一般樹109

6.7.3森林轉換為二叉樹110

6.7.4二叉樹還原為森林110

6.7.5樹與森林的遍歷111

6.8二叉樹的套用——哈夫曼樹111

6.8.1哈夫曼樹的定義112

6.8.2哈夫曼樹的構造113

6.8.3哈夫曼算法的實現114

6.8.4哈夫曼樹的套用116

6.9實訓創建二叉樹並遍歷117

6.10小結121

6.11習題121

第7章圖123

7.1圖的基本概念123

7.1.1圖的定義123

7.1.2圖的基本術語124

7.2圖的存儲結構126

7.2.1鄰接矩陣的概念126

7.2.2建立圖的鄰接矩陣127

7.2.3鄰接表128

7.3圖的遍歷131

7.3.1連通圖的深度優先搜尋132

7.3.2連通圖的廣度優先搜尋133

7.3.3非連通圖的遍歷135

7.4最小生成樹135

7.4.1生成樹及最小生成樹135

7.4.2普里姆算法136

7.4.3克魯斯卡爾算法139

7.5最短路徑140

7.5.1迪傑斯特拉算法141

7.5.2弗洛伊德(Floyd)算法147

7.6拓撲排序152

7.7實訓鄰接矩陣與遍歷算法153

7.8小結162

7.9習題162

第8章查找164

8.1查找的相關定義164

8.2順序查找算法164

8.2.1順序查找描述165

8.2.2數據結構定義165

8.2.3典型算法與分析165

8.3折半查找算法166

8.3.1折半查找描述166

8.3.2折半查找分析166

8.3.3數據結構定義167

8.3.4典型算法與分析167

8.4分塊查找168

8.4.1分塊查找描述168

8.4.2分塊查找分析169

8.4.3數據結構定義169

8.4.4典型算法與分析169

8.5二叉排序樹查找169

8.5.1二叉排序樹描述169

8.5.2二叉排序樹分析170

8.5.3數據結構定義173

8.5.4典型算法與分析173

8.6哈希表查找173

8.6.1哈希表查找描述173

8.6.2哈希表查找分析174

8.6.3數據結構定義177

8.6.4典型算法與分析177

8.7實訓套用各種查找算法178

8.8小結181

8.9習題181

第9章排序184

9.1插入排序184

9.1.1直接插入排序184

9.1.2希爾排序187

9.2交換排序188

9.2.1冒泡排序188

9.2.2快速排序189

9.3選擇排序191

9.3.1直接選擇排序191

9.3.2堆排序192

9.3.3歸併排序198

9.4基數排序200

9.4.1多關鍵字排序200

9.4.2基數排序方法200

9.5實訓實現不同的排序算法202

9.6小結210

9.7習題211

附錄對應章節的Java代碼215

習題答案258

參考文獻271