數據結構與算法：C語言版

《數據結構與算法:C語言版》一書共10章，一方面，涵蓋數據結構的基本概念，定義了線性表、棧、佇列、串、數組、廣義表、樹和二叉樹、圖、查找、排序等各種結構的抽象數據類型，並給出了相應操作的實現算法；另一方面，採用C語言描述算法，並給出了各種算法的效率分析，以及這些結構在計算機科學及其他領域的套用。此外，每章後均配有典型例題、上機實驗和習題。《數據結構與算法:C語言版》中的所有算法均在VC++環境下調試通過。

基本介紹

• 書名：數據結構與算法：C語言版
• 原版名稱：計算機套用技術規劃教材
• ISBN：9787111321224
• 頁數：238頁
• 出版社： 機械工業出版社
• 出版時間：第1版 (2010年10月1日)
• 裝幀：平裝
• 開本：16
• 正文語種：簡體中文

內容簡介

《數據結構與算法:C語言版》在內容安排上，突出由淺入深、循序漸進、通俗易懂的特點，算法分析透徹，講解清晰，便於學生自學。為了激發學生的學習興趣，培養學生解決實際問題的能力，書中融入了一些典型的套用實例，如命題公式真值表的求解算法、出棧序列的求解算法等。《數據結構與算法:C語言版》可作為高等院校計算機及相關專業本科生的“數據結構”課程教材，也可供相關科技人員學習參考。

目錄

前言

教學建議

第1章 緒論1

1.1 數據結構的研究對象1

1.2 數據結構的發展概況4

1.3 基本概念與術語4

1.4 數據類型與抽象數據類型6

1.4.1 數據類型6

1.4.2 抽象數據類型6

1.4.3 抽象數據類型的表示與實現7

1.5 算法與算法分析9

1.5.1 算法9

1.5.2 算法設計的原則10

1.5.3 算法效率的衡量方法和準則10

1.5.4 算法的存儲空間需求12

1.6 典型例題12

1.7 上機實驗13

習題13

第2章 線性表16

2.1 線性表的定義16

2.1.1 線性表的概念16

2.1.2 線性表的抽象數據類型定義16

2.2 線性表的順序表示與實現17

2.2.1 線性表的順序表示17

2.2.2 線性表的順序實現18

2.2.3 順序表的套用舉例21

2.3 線性表的鏈式表示與實現22

2.3.1 單鍊表22

2.3.2 雙向鍊表26

2.3.3 循環鍊表29

2.3.4 靜態鍊表31

2.3.5 鍊表的套用舉例33

2.4 典型例題35

2.5 上機實驗37

習題39

第3章 棧與佇列41

3.1 棧41

3.1.1 棧的抽象數據類型定義41

3.1.2 棧的表示與實現42

3.2 棧的套用舉例44

3.2.1 數制轉換44

3.2.2 括弧匹配的檢驗45

3.2.3 表達式求值46

3.2.4 求命題公式的真值50

3.3 棧與遞歸實現53

3.3.1 遞歸的定義53

3.3.2 遞歸與棧的關係53

3.3.3 遞歸的實現54

3.3.4 用遞歸求所有出棧序列56

3.3.5 遞歸的消除57

3.4 佇列59

3.4.1 佇列的抽象數據類型定義59

3.4.2 佇列的鏈式表示與實現60

3.4.3 佇列的順序表示與實現——循環佇列61

3.4.4 佇列的套用舉例63

3.5 典型例題64

3.6 上機實驗66

習題68

第4章 串70

4.1 串的定義70

4.2 串的表示與實現72

4.2.1 串的順序存儲表示72

4.2.2 串的鏈式存儲表示75

4.3 串的模式匹配75

4.3.1 簡單匹配算法75

4.3.2 首尾匹配算法77

4.3.3 kmp算法78

4.4 典型例題80

4.5 上機實驗82

習題83

第5章 數組與廣義表85

5.1 數組的定義85

5.2 數組的順序存儲86

5.3 矩陣的壓縮存儲88

5.3.1 特殊矩陣89

5.3.2 稀疏矩陣90

5.4 廣義表94

5.4.1 廣義表的定義94

5.4.2 廣義表的存儲結構96

5.5 典型例題98

5.6 上機實驗99

習題100

第6章 樹與二叉樹101

6.1 樹的定義101

6.1.1 樹的概念與術語101

6.1.2 樹的邏輯表示方法102

6.1.3 樹的抽象數據類型定義102

6.2 二叉樹的定義103

6.2.1 二叉樹的概念103

6.2.2 二叉樹的重要性質105

6.3 二叉樹的存儲結構106

6.3.1 二叉樹的順序存儲表示106

6.3.2 二叉樹的鏈式存儲表示106

6.4 二叉樹的遍歷108

6.4.1 二叉樹遍歷的概念108

6.4.2 二叉樹遍歷的遞歸算法108

6.4.3 二叉樹遍歷的非遞歸算法109

6.4.4 層次遍歷算法111

6.4.5 遍歷算法的套用舉例112

6.5 二叉樹的構造115

6.6 線索二叉樹116

6.6.1 線索二叉樹的定義116

6.6.2 線索鍊表的建立117

6.6.3 線索鍊表的遍歷算法118

6.7 樹和森林的表示方法119

6.7.1 雙親表示法119

6.7.2 孩子鍊表表示法120

6.7.3 孩子-兄弟鍊表表示法121

6.7.4 樹、森林和二叉樹的對應關係121

6.8 樹和森林的遍歷122

6.8.1 樹的遍歷122

6.8.2 森林的遍歷123

6.8.3 樹遍歷算法的套用124

6.9 赫夫曼樹與赫夫曼編碼124

6.9.1 赫夫曼樹的定義125

6.9.2 赫夫曼樹的構造125

6.9.3 赫夫曼編碼127

6.1 0典型例題128

6.1 1上機實驗130

習題130

第7章 圖133

7.1 圖的定義與術語133

7.1.1 圖的相關術語133

7.1.2 圖的抽象數據類型定義135

7.2 圖的存儲表示136

7.2.1 圖的鄰接矩陣存儲表示136

7.2.2 圖的鄰接表存儲表示137

7.2.3 有向圖的十字鍊表存儲表示138

7.2.4 無向圖的鄰接多重表存儲表示140

7.3 圖的遍歷141

7.3.1 深度優先搜尋遍歷圖141

7.3.2 廣度優先搜尋遍歷圖142

7.3.3 圖遍歷的套用舉例143

7.4 最小生成樹145

7.4.1 普里姆算法145

7.4.2 克魯斯卡爾算法147

7.5 兩點之間的最短路徑問題148

7.5.1 從某個源點到其餘各點的最短路徑148

7.5.2 每一對頂點之間的最短路徑150

7.6 拓撲排序151

7.7 關鍵路徑153

7.8 典型例題156

7.9 上機實驗158

習題160

第8章 查找162

8.1 基本概念162

8.2 靜態查找表163

8.2.1 順序查找163

8.2.2 有序表查找164

8.2.3 索引查找167

8.3 動態查找樹表168

8.3.1 二叉排序樹169

8.3.2 平衡二叉樹173

8.3.3 b-樹179

8.3.4 b+樹183

8.3.5 鍵樹184

8.4 哈希表185

8.4.1 哈希表的概念185

8.4.2 哈希函式的構造方法185

8.4.3 處理衝突的方法187

8.4.4 哈希表的查找189

8.4.5 哈希表的插入操作190

8.4.6 哈希表的刪除操作191

8.5 典型例題191

8.6 上機實驗193

習題194

第9章 排序196

9.1 概述196

9.1.1 什麼是排序196

9.1.2 內部排序和外部排序196

9.1.3 內部排序的方法197

9.2 插入排序198

9.2.1 直接插入排序198

9.2.2 折半插入排序199

9.2.3 二路插入排序200

9.2.4 表插入排序202

9.2.5 希爾排序204

9.3 交換排序205

9.3.1 起泡排序205

9.3.2 快速排序206

9.4 選擇排序209

9.4.1 簡單選擇排序209

9.4.2 堆排序209

9.5 歸併排序212

9.6 基數排序213

9.6.1 多關鍵字排序213

9.6.2 鏈式基數排序214

9.7 各種排序方法的綜合比較216

9.8 外排序簡介217

9.8.1 外存信息的存取218

9.8.2 外排序的基本方法218

9.9 典型例題219

9.1 0上機實驗221

習題222

第10章 檔案224

10.1 檔案的基本概念224

10.1.1 什麼是檔案224

10.1.2 檔案的邏輯結構及操作224

10.1.3 檔案的存儲結構225

10.2 順序檔案225

10.3 索引檔案226

10.3.1 isam檔案227

10.3.2 vsam檔案229

10.4 哈希檔案231

10.5 多關鍵字檔案232

10.5.1 多重表檔案232

10.5.2 倒排檔案232

10.5.3 倒排檔案的套用234

10.6 典型例題235

10.7 上機實驗237

習題237

參考文獻239