數據結構及套用

《數據結構及套用》 是機械工業出版社出版的圖書， ISBN是9787111321552

基本介紹

• 書名：數據結構及套用
• 作者：沈華
• ISBN：9787111321552
• 出版社：機械工業出版社

基本信息

上架時間：2010-12-22

出版日期：2011 年1月

開本：16開

頁碼：275

內容簡介

本書系統地介紹各種常用的數據結構以及排序、查找的各種算法，闡述各種數據結構的邏輯關係、存儲表示及運算，涵蓋研究生入學考試大綱的所有內容。全書採用c語言作為數據結構和算法的描述語言，並對c語言描述的算法作了詳細的註解和簡要的性能分析。全書共分為六個部分：第一部分主要介紹什麼是數據結構，什麼是算法，它們之間有著怎樣的聯繫，如何進行算法分析；第二部分針對後續學習的需要幫助讀者溫習一些相關知識；第三部分和第四部分分別重點介紹幾種常見的線性結構和非線性結構；第五部分介紹在實際套用中最常遇到的兩個運算——查找(即搜尋)和排序，以及實現這兩種運算的各種算法；第六部分則簡要介紹檔案和外排序的相關內容。

為了幫助讀者直觀、正確地理解各種數據結構和算法的要旨，本書利用大量的圖表進行詮釋，並通過典型的思考題、例題和習題來加深讀者對相關知識的理解。

本書內容豐富、概念清楚、邏輯推理嚴謹、通俗易懂，可以作為計算機科學與技術及相關專業本科生的教材，也可以作為高等院校計算機專業碩士研究生入學考試的複習用書，同時還可以作為廣大工程技術人員的參考資料。

目錄

序

前言

教學建議

第一部分概論

第1章數據結構3

1.1什麼是數據3

1.2什麼是數據結構3

1.2.1數據的邏輯結構3

1.2.2數據的存儲結構4

1.2.3數據的運算5

1.3什麼是數據類型5

1.4知識點小結6

習題6

第2章算法7

2.1什麼是算法7

2.2算法的描述7

2.3算法分析8

2.3.1時間複雜度8

2.3.2漸近符號9

2.3.3空間複雜度10

.2.3.4複雜度分析舉例10

2.4知識點小結13

習題13

第二部分預備知識

第3章c語言、遞歸及存儲分配方式16

3.1c語言的相關內容16

3.1.1函式的參數傳遞與結果返回16

3.1.2結構體類型17

3.1.3指針18

3.2遞歸18

3.3存儲分配方式19

3.4知識點小結20

習題20

第三部分線性結構

第4章線性表22

4.1線性表的類型定義22

4.1.1線性表的邏輯結構22

4.1.2線性表的基本運算22

4.2線性表的順序存儲表示23

4.2.1順序表23

4.2.2順序表中基本運算的實現24

4.3線性表的鏈式存儲表示30

4.3.1單鍊表30

4.3.2單鍊表中基本運算的實現31

4.4線性表的其他鏈式存儲表示38

4.4.1靜態單鍊表38

4.4.2雙（向）鍊表41

4.4.3循環單（向）鍊表43

4.4.4循環雙（向）鍊表46

4.5線性表的套用舉例47

4.6順序表和鍊表的比較48

4.7知識點小結49

習題49

第5章棧51

5.1棧的類型定義51

5.1.1棧的邏輯結構51

5.1.2棧的基本運算52

5.2棧的順序存儲表示52

5.2.1順序棧52

5.2.2順序棧中基本運算的實現53

5.3棧的鏈式存儲表示55

5.3.1鏈棧55

5.3.2鏈棧中基本運算的實現55

5.4兩個方向生長的棧56

5.5棧的套用舉例57

5.6知識點小結61

習題61

第6章佇列63

6.1佇列的類型定義63

6.1.1佇列的邏輯結構63

6.1.2佇列的基本運算63

6.2佇列的鏈式存儲表示64

6.2.1鏈佇列64

6.2.2鏈佇列中基本運算的實現65

6.3佇列的順序存儲表示66

6.3.1順序佇列66

6.3.2循環佇列69

6.3.3循環佇列中基本運算的實現71

6.4雙端佇列74

6.5佇列的套用舉例74

6.6知識點小結75

習題76

第7章串77

7.1串的類型定義77

7.1.1串的邏輯結構77

7.1.2串的基本運算77

7.2串的順序存儲表示78

7.3串的堆分配存儲表示80

7.4串的塊鏈存儲表示81

7.5串的模式匹配82

7.6知識點小結88

習題88

第8章數組及廣義表89

8.1數組的類型定義89

8.1.1數組的定義89

8.1.2數組的性質89

8.1.3數組的基本運算89

8.2數組的順序存儲表示90

8.3特殊矩陣的壓縮存儲92

8.3.1特殊形狀矩陣的壓縮存儲93

8.3.2隨機稀疏矩陣的壓縮存儲及其運算95

8.4廣義表104

8.4.1廣義表的基本概念104

8.4.2廣義表的基本運算105

8.4.3廣義表的存儲結構106

8.5知識點小結108

習題108

第四部分非線性結構

第9章樹110

9.1概述110

9.1.1樹的定義及基本術語110

9.1.2樹的存儲結構112

9.2二叉樹123

9.2.1二叉樹的定義123

9.2.2二叉樹的性質123

9.2.3二叉樹的存儲結構128

9.3二叉樹的遍歷132

9.3.1遍歷操作132

9.3.2先序遍歷132

9.3.3中序遍歷133

9.3.4後序遍歷134

9.3.5層次遍歷135

9.3.6二叉樹遍歷的套用舉例136

9.4線索二叉樹144

9.4.1二叉樹的線索化145

9.4.2線索二叉樹上的運算149

9.5二叉樹的套用156

9.5.1哈夫曼樹及其套用156

9.5.2二叉排序樹161

9.5.3平衡二叉樹163

9.6樹、森林與二叉樹的相互轉換166

9.6.1樹與二叉樹的相互轉換166

9.6.2森林與二叉樹的相互轉換168

9.7樹、森林的遍歷169

9.7.1樹的遍歷169

9.7.2森林的遍歷169

9.8樹的套用舉例170

9.9知識點小結171

習題172

第10章圖173

10.1概述173

10.1.1圖的定義及基本術語173

10.1.2圖的存儲結構179

10.1.3圖的創建184

10.2圖的遍歷187

10.2.1深度優先搜尋遍歷187

10.2.2廣度優先搜尋遍歷191

10.2.3圖遍歷的套用舉例193

10.3生成樹194

10.3.1連通圖的生成樹194

10.3.2連通網的最小生成樹195

10.4最短路徑197

10.4.1單源最短路徑197

10.4.2每對頂點間的最短路徑201

10.5有向無環圖及其套用205

10.5.1aov網與拓撲排序205

10.5.2aoe網與關鍵路徑207

10.6知識點小結209

習題209

第五部分兩種重要運算

第11章查找212

11.1查找的基本概念212

11.2主要查找方法簡介213

11.3靜態查找213

11.3.1順序查找213

11.3.2二分查找215

11.3.3分塊查找219

11.4動態查找220

11.5散列查找227

11.5.1散列表的概念228

11.5.2散列函式的構造方法228

11.5.3處理衝突的方法229

11.5.4散列表的查找232

11.6知識點小結234

習題235

第12章內排序236

12.1排序的基本概念236

12.2插入排序237

12.2.1直接插入排序237

12.2.2希爾排序241

12.3交換排序242

12.3.1冒泡排序242

12.3.2快速排序244

12.4選擇排序247

12.4.1直接選擇排序247

12.4.2樹形選擇排序248

12.4.3堆排序249

12.5歸併排序254

12.6分配排序255

12.6.1箱排序255

12.6.2基數排序255

12.7各種內排序法的比較257

12.8知識點小結257

習題258

第六部分檔案的組織結構及排序

第13章檔案260

13.1檔案的基本概念260

13.2順序檔案260

13.3索引檔案261

13.4索引順序檔案262

13.5散列檔案267

13.6多關鍵字檔案268

13.7知識點小結268

習題268

第14章外排序269

14.1多路平衡歸併269

14.2置換選擇排序272

14.3歸併樹及最佳歸併樹274

14.4知識點小結275

習題275

參考文獻276