数据结构：C++语言描述

书号： 44926

ISBN： 978-7-111-44926-3

作者： 苏仕华 刘燕君 刘振安

印次： 1-1

开本： 16开

字数： 300千字

定价： 35.0

所属丛书： 高等院校计算机教材系列

出版日期： 2014-01-22

本书使用模板描述算法，实现参数化类型，使得对算法的描述更接近自然语言和更容易理解。另外，书中还精选了典型例题、实验和习题，并有配套的课程设计，帮助学生进一步加深对算法的理解。同时，为了方便读者考研，本书还专门单列一章考研指导，并给出了一些複习方法、考试技巧以及真题练习和参考答案，指导读者複习并深入掌握相关知识。本书取材新颖、结构合理、概念清楚、语言简洁、通俗易懂、实用性强，重在培养学生对各种基本算法的理解和套用技能，特别适合作为高等院校相关专业的教材，也可以作为培训班教材、自学教材及工程技术人员的参考书

前言

第1章　数据结构概论1

1.1　引言1

1.2　基本概念和常用术语2

1.3　算法的描述和分析5

1.3.1　算法描述5

1.3.2　算法分析6

实验1　求解鸡兔同笼问题9

习题19

第2章　类和类模板基础11

2.1　使用类和对象11

2.1.1　使用对象和指针11

2.1.2　new和delete运算符13

2.2　类模板14

2.3　友元函式和友元类15

2.4　使用组合18

2.5　套用实例21

2.5.1　使用类求解一元二次方程21

2.5.2　使用类模板和头档案求解一元二次方程25

2.6　使用模板描述算法的优点和注意事项27

实验2　多档案编程28

习题228

第3章　线性表30

3.1　线性表的类型定义30

3.1.1　线性表的逻辑定义30

3.1.2　线性表的抽象数据类型30

3.2　线性表的顺序存储及基本运算31

3.2.1　线性表的顺序存储31

3.2.2　顺序表上基本运算的实现32

3.2.3　顺序表运算套用实例36

3.2.4　线性顺序表元素为结构的实例37

3.3　线性表的链式存储结构39

3.3.1　线性鍊表39

3.3.2　单鍊表上的基本运算40

3.3.3　单鍊表上的其他典型运算46

3.3.4　双向鍊表49

3.4　顺序表和鍊表的比较53

实验3　实现一元多项式的加法运算54

习题354

第4章　栈和伫列57

4.1　栈57

4.1.1　栈的定义及抽象数据类型57

4.1.2　栈的存储表示和实现58

4.2　栈套用实例63

4.2.1　圆括弧匹配的检验63

4.2.2　字元串回文的判断63

4.2.3　数制转换64

4.2.4　栈与递归65

4.3　伫列67

4.3.1　抽象数据类型68

4.3.2　顺序循环伫列68

4.3.3　链伫列73

4.4　栈和伫列套用实例——表达式求值77

4.4.1　中缀表达式到后缀表达式的转换78

4.4.2　后缀表达式的计算80

实验4　八皇后问题82

习题482

第5章　字元串86

5.1　串定义及其运算86

5.1.1　串的基本概念86

5.1.2　串的抽象数据类型86

5.1.3　串的存储结构87

5.2　串的顺序存储结构87

5.2.1　顺序串的类型定义和常用算法87

5.2.2　串基本运算的实现88

5.2.3　串定位（模式匹配）运算89

5.2.4　取子串运算（求子串）90

5.2.5　连线字元串运算90

5.2.6　演示字元串操作的实例91

5.3　串的链式存储91

5.4　串运算套用实例92

实验5　串模式匹配算法94

习题594

第6章　多维数组和广义表96

6.1　多维数组和运算96

6.1.1　数组的抽象数据类型96

6.1.2　数组的顺序存储97

6.1.3　矩阵类的定义和运算97

6.2　矩阵的压缩存储102

6.2.1　特殊矩阵103

6.2.2　稀疏矩阵107

6.3　广义表110

6.3.1　广义表的定义111

6.3.2　广义表的运算111

6.4　运算符重载112

6.4.1　重载对象的赋值运算符112

6.4.2　运算符重载的实质115

实验6　稀疏矩阵的加法运算116

习题6116

第7章　树和二叉树118

7.1　树的基本概念和术语118

7.2　二叉树119

7.2.1　二叉树的定义和性质119

7.2.2　二叉树的抽象数据类型121

7.2.3　二叉树的存储结构121

7.3　二叉树的运算123

7.3.1　二叉树的生成123

7.3.2　二叉树的递归遍历及其算法124

7.3.3　二叉树递归遍历套用实例127

7.3.4　非递归的按层遍历二叉鍊表130

7.3.5　二叉树的非递归遍历算法131

7.4　线索二叉树133

7.4.1　二叉树的线索化134

7.4.2　线索二叉鍊表上的运算135

7.5　树和森林137

7.5.1　树的存储结构137

7.5.2　树、森林与二叉树的转换139

7.5.3　树和森林的遍历140

7.6　哈夫曼树及其套用141

7.6.1　最优二叉树(哈夫曼树)141

7.6.2　哈夫曼算法143

7.6.3　哈夫曼算法的实现143

7.6.4　哈夫曼编码146

实验7　二叉树的遍历与查找算法148

习题7149

第8章　图151

8.1　图的定义和基本术语151

8.2　图的存储结构153

8.2.1　邻接矩阵表示法153

8.2.2　邻接表表示法156

8.3　图的遍历160

8.3.1　深度优先搜寻160

8.3.2　广度优先搜寻162

8.4　图的生成树和最小生成树165

8.4.1　图的生成树165

8.4.2　最小生成树166

8.5　最短路径172

8.6　拓扑排序177

实验8　实现无向网路的最小生成树的普里姆算法182

习题8182

第9章　排序184

9.1　基本概念184

9.2　插入排序185

9.2.1　直接插入排序185

9.2.2　希尔排序186

9.3　交换排序187

9.3.1　冒泡排序188

9.3.2　快速排序189

9.4　选择排序192

9.4.1　使用顺序表结构实现直接选择排序193

9.4.2　使用链式存储结构实现直接选择排序194

9.4.3　堆排序196

9.5　归併排序199

9.6　分配排序：基数排序201

9.7　内部排序方法的分析比较203

实验9　堆排序204

习题9204

第10章　查找207

10.1　基本概念207

10.2　顺序表的查找207

10.2.1　顺序查找208

10.2.2　二分查找209

10.2.3　分块查找212

10.2.4　三种查找方法的比较213

10.3　树表的查找213

10.3.1　二叉排序树213

10.3.2　B树217

10.3.3　B+树221

10.4　散列表的查找222

10.4.1　散列表的概念222

10.4.2　散列函式的构造方法223

10.4.3　处理冲突的方法224

10.4.4　散列表查找226

实验10　二叉排序树231

习题10231

第11章　档案234

11.1　基本概念234

11.2　顺序档案235

11.3　索引档案235

11.4　索引顺序档案236

11.4.1　ISAM档案236

11.4.2　VSAM档案237

11.4.3　散列档案237

11.5　多关键字档案237

11.5.1　多重表档案237

11.5.2　倒排档案238

实验11　使用档案239

习题11240

附录A　考研指导242

A.1　考纲要求242

A.1.1　绪论242

A.1.2　线性表242

A.1.3　栈、伫列和数组243

A.1.4　树和二叉树243

A.1.5　图244

A.1.6　查找244

A.1.7　排序245

A.2　知识点、重难点解析246

A.3　複习方法247

A.4　考试技巧248

A.4.1　单项选择题248

A.4.2　算法设计题249

A.5　实战真题练习250

A.5.1　真题练习1250

A.5.2　真题练习2252

A.5.3　真题练习3255

A.5.4　真题练习4257

A.5.5　真题练习5259

A.6　真题练习参考答案261

A.6.1　真题1参考答案261

A.6.2　真题2参考答案263

A.6.3　真题3参考答案264

A.6.4　真题4参考答案267

A.6.5　真题5参考答案269

附录B　七位ASCII代码表271

参考文献272