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

《數據結構：C語言描述（第2版）》是2017年3月機械工業出版社出版的圖書，作者是殷人昆。

基本介紹

• 書名：數據結構：C語言描述（第2版）
• 作者：殷人昆
• ISBN：9787111559825
• 定價：55元
• 出版社：機械工業出版社
• 出版時間：2017年3月
• 開本：16開

內容簡介

本書以專業基礎能力培養為目標，承續電腦程式設計基礎課程，完全遵照教育部計算機科學與技術教學指導委員會關於《高等學校計算機專業人才專業能力構成與培養》的要求編寫而成，旨在培養學生的基本計算思維能力，提高學生的算法設計和程式實現能力，並為學生提高系統開發能力打下良好的基礎。全書共分10章，主要介紹了數據結構基本概念與基本知識、線性表及其基本操作、棧和佇列、字元串、數組和廣義表、樹與二叉樹的概念和套用、圖、查找和排序。

本書可以作為計算機科學與技術及相關專業本科生的教材，也可以作為計算機專業考研(碩士、工程碩士、博士)的複習教材，還可以供使用計算機進行系統開發的人員學習使用。

圖書目錄

目錄

前言

教學建議

第1章　緒論1

1.1　數據結構的概念及分類1

1.1.1　為什麼要學習數據結構1

1.1.2　與數據結構相關的基本術語2

1.1.3　數據結構的分類4

1.1.4　數據結構的存儲結構6

1.1.5　定義在數據結構上的操作7

1.2　使用C語言描述數據結構7

1.2.1　數據類型7

1.2.2　算法的控制結構8

1.2.3　算法的函式結構9

1.2.4　動態存儲分配12

1.2.5　邏輯和關係運算的約定12

1.2.6　輸入與輸出13

1.3　算法和算法設計13

1.3.1　算法的定義和特性13

1.3.2　算法的設計步驟14

1.3.3　算法設計的基本方法15

1.4　算法分析與度量19

1.4.1　算法的評價標準19

1.4.2　算法的時間和空間複雜度度量20

1.4.3　算法的漸近分析23

小結25

習題25

第2章　線性表27

2.1　概述27

2.1.1　線性表的定義和特點27

2.1.2　線性表的主要操作28

2.2　順序表29

2.2.1　順序表的定義和特點29

2.2.2　順序表的結構定義30

2.2.3　順序表主要操作的實現31

2.2.4　順序表主要操作的性能分析32

2.2.5　順序表的套用舉例33

2.3　單鍊表34

2.3.1　單鍊表的定義和特點34

2.3.2　單鍊表的結構定義35

2.3.3　單鍊表中的插入與刪除36

2.3.4　帶頭結點的單鍊表38

2.3.5　單鍊表的順序訪問與尾遞歸40

2.3.6　單鍊表的套用舉例42

2.3.7　循環單鍊表44

2.3.8　雙向鍊表47

2.3.9　靜態鍊表51

2.4　順序表與單鍊表的比較52

2.5　單鍊表的套用：一元多項式及其運算53

2.5.1　一元多項式的表示53

2.5.2　多項式的結構定義54

2.5.3　多項式的加法56

2.5.4　多項式的乘法57

小結59

習題59

第3章　棧和佇列62

3.1　棧62

3.1.1　棧的概念62

3.1.2　順序棧63

3.1.3　鏈式棧67

3.1.4　棧的混洗69

3.2　佇列70

3.2.1　佇列的概念71

3.2.2　循環佇列72

3.2.3　鏈式佇列75

3.3　棧的套用77

3.3.1　數制轉換77

3.3.2　括弧匹配78

3.3.3　表達式的計算與優先權處理79

3.3.4　棧與遞歸的實現84

3.4　佇列的套用87

3.4.1　列印楊輝三角形與逐行處理87

3.4.2　電路布線與兩點間的最短路徑89

3.5　在算法設計中使用遞歸91

3.5.1　漢諾塔問題與分治法91

3.5.2　迷宮問題與回溯法94

3.6　雙端佇列96

3.6.1　雙端佇列的概念97

3.6.2　輸入受限的雙端佇列97

3.6.3　輸出受限的雙端佇列98

3.6.4　雙端佇列的存儲表示98

3.7　優先佇列100

3.7.1　優先佇列的概念100

3.7.2　優先佇列的實現100

小結101

習題102

第4章　字元串105

4.1　字元串的概念105

4.1.1　字元串的基本概念105

4.1.2　字元串的初始化和賦值106

4.1.3　C語言中有關字元串的庫函式107

4.1.4　字元串的自定義操作108

4.2　字元串的實現109

4.2.1　定長順序存儲表示109

4.2.2　堆分配存儲表示110

4.2.3　塊鏈存儲表示112

4.3　字元串的模式匹配113

4.3.1　BF模式匹配算法113

4.3.2　無回溯的KMP模式匹配算法114

4.3.3　BM模式匹配算法119

小結121

習題121

第5章　多維數組和廣義表123

5.1　數組123

5.1.1　一維數組123

5.1.2　多維數組125

5.2　特殊矩陣126

5.2.1　對稱矩陣的壓縮存儲127

5.2.2　三對角矩陣的壓縮存儲128

5.2.3　w對角矩陣的壓縮存儲129

5.3　稀疏矩陣130

5.3.1　稀疏矩陣的概念130

5.3.2　稀疏矩陣的順序存儲表示130

5.3.3　稀疏矩陣的連結存儲表示137

5.4　廣義表140

5.4.1　廣義表的概念140

5.4.2　廣義表的性質141

5.4.3　廣義表的頭尾表示法142

5.4.4　廣義表的擴展線性鍊表表示145

5.4.5　廣義表的層次表示法146

5.4.6　廣義表的套用舉例：三元多項式的表示148

小結150

習題151

第6章　樹與二叉樹153

6.1　樹的基本概念153

6.1.1　樹的定義和術語153

6.1.2　樹的基本操作155

6.2　二叉樹及其存儲表示 156

6.2.1　二叉樹的概念156

6.2.2　二叉樹的性質157

6.2.3　二叉樹的主要操作159

6.2.4　二叉樹的順序存儲表示160

6.2.5　二叉樹的連結存儲表示161

6.3　二叉樹的遍歷163

6.3.1　二叉樹遍歷的遞歸算法163

6.3.2　遞歸遍歷算法的套用舉例164

6.3.3　二叉樹遍歷的非遞歸算法167

6.3.4　利用佇列實現二叉樹的層次序遍歷170

6.3.5　二叉樹的計數171

6.4　線索二叉樹173

6.4.1　線索二叉樹的概念173

6.4.2　線索二叉樹的種類174

6.4.3　中序線索二叉樹的建立和遍歷174

6.4.4　先序與後序線索二叉樹176

6.5　樹與森林178

6.5.1