数据结构——从概念到C实现

图书标准信息

• 作者 王红梅；皮德常
• 出版社 清华大学出版社
• 出版时间 2017-02
• 版次 1
• ISBN 9787302451495
• 定价 39.00元
• 装帧 其他
• 开本 32开
• 纸张 胶版纸
• 页数 286页
• 字数 426千字

【内容简介】

数据结构是计算机及相关专业的核心课程，也是计算机及相关专业硕士研究生入学考试的必考科目，而且是理工专业的热门公选课程。本书介绍了数据结构、算法以及抽象数据类型的概念；介绍了线性表、栈和队列、字符串和多维数组、树和二叉树、图等常用数据结构；讨论了基本的查找和排序技术。本书合理规划教学内容，梳理知识单元及其拓扑结构，兼顾概念层和实现层，既强调了数据结构的基本概念和原理方法，又注重了数据结构的程序实现和实际运用，在提炼基础知识的同时，进行了适当的扩展和提高。本书内容丰富，层次清晰，深入浅出，结合实例，可作为计算机及相关专业数据结构课程的教材，也可供从事计算机软件开发和应用的工程技术人员参考和阅读。

【目录】

目录

第1章绪论1

1.1问题求解与程序设计2

1.1.1程序设计的一般过程2

1.1.2数据结构在程序设计中的作用4

1.1.3算法在程序设计中的作用6

1.1.4本书讨论的主要内容7

1.2数据结构的基本概念8

1.2.1数据结构8

1.2.2抽象数据类型11

1.3算法的基本概念12

1.3.1算法及算法的特性12

1.3.2算法的描述方法14

1.4算法分析15

1.4.1算法的时间复杂度16

1.4.2算法的空间复杂度17

1.4.3算法分析举例18

1.5扩展与提高20

1.5.1从数据到大数据20

1.5.2算法分析的其他渐进符号22

习题123

 

第2章线性表25

2.1引言26

2.2线性表的逻辑结构27

2.2.1线性表的定义27

2.2.2线性表的抽象数据类型定义27数据结构——从概念到C实现目录2.3线性表的顺序存储结构及实现29

2.3.1顺序表的存储结构定义29

2.3.2顺序表的实现30

2.3.3顺序表的使用34

2.4线性表的链接存储结构及实现35

2.4.1单链表的存储结构定义35

2.4.2单链表的实现37

2.4.3单链表的使用44

2.4.4双链表45

2.4.5循环链表47

2.5顺序表和链表的比较48

2.6扩展与提高48

2.6.1线性表的静态链表存储48

2.6.2顺序表的动态分配方式51

2.7应用实例52

2.7.1约瑟夫环问题52

2.7.2一元多项式求和55

习题259

 

第3章栈和队列63

3.1引言64

3.2栈65

3.2.1栈的逻辑结构65

3.2.2栈的顺序存储结构及实现66

3.2.3栈的链接存储结构及实现68

3.2.4顺序栈和链栈的比较71

3.3队列72

3.3.1队列的逻辑结构72

3.3.2队列的顺序存储结构及实现73

3.3.3队列的链接存储结构及实现77

3.3.4循环队列和链队列的比较80

3.4扩展与提高81

3.4.1两栈共享空间81

3.4.2双端队列82

3.5应用举例83

3.5.1括号匹配问题83

3.5.2表达式求值85

习题388第4章字符串和多维数组91

4.1引言92

4.2字符串92

4.2.1字符串的逻辑结构92

4.2.2字符串的存储结构94

4.2.3模式匹配94

4.3多维数组98

4.3.1数组的逻辑结构98

4.3.2数组的存储结构与寻址99

4.4矩阵的压缩存储100

4.4.1特殊矩阵的压缩存储100

4.4.2稀疏矩阵的压缩存储102

4.5扩展与提高105

4.5.1稀疏矩阵的转置运算105

4.5.2广义表107

4.6应用实例111

4.6.1发纸牌111

4.6.2八皇后问题112

习题4115

 

第5章树和二叉树119

5.1引言120

5.2树的逻辑结构121

5.2.1树的定义和基本术语121

5.2.2树的抽象数据类型定义123

5.2.3树的遍历操作123

5.3树的存储结构124

5.3.1双亲表示法124

5.3.2孩子表示法125

5.3.3孩子兄弟表示法126

5.4二叉树的逻辑结构127

5.4.1二叉树的定义127

5.4.2二叉树的基本性质129

5.4.3二叉树的抽象数据类型定义130

5.4.4二叉树的遍历操作131

5.5二叉树的存储结构133

5.5.1顺序存储结构133

5.5.2二叉链表134

5.5.3三叉链表138

5.6森林138

5.6.1森林的逻辑结构138

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

5.7最优二叉树141

5.7.1哈夫曼算法141

5.7.2哈夫曼编码143

5.8扩展与提高145

5.8.1二叉树遍历的非递归算法145

5.8.2线索二叉树148

5.9应用实例151

5.9.1堆与优先队列151

5.9.2并查集154

习题5155

 

第6章图159

6.1引言160

6.2图的逻辑结构161

6.2.1图的定义和基本术语161

6.2.2图的抽象数据类型定义163

6.2.3图的遍历操作164

6.3图的存储结构及实现167

6.3.1邻接矩阵167

6.3.2邻接表170

6.3.3邻接矩阵和邻接表的比较174

6.4最小生成树175

6.4.1Prim算法176

6.4.2Kruskal算法178

6.5最短路径182

6.5.1Dijkstra算法183

6.5.2Floyd算法185

6.6有向无环图及其应用187

6.6.1AOV网与拓扑排序187

6.6.2AOE网与关键路径190

6.7扩展与提高193

6.7.1图的其他存储方法193

6.7.2图的连通性194

6.8应用实例196

6.8.1七巧板涂色问题196

6.8.2医院选址问题198

习题6200

 

第7章查找技术205

7.1概述206

7.1.1查找的基本概念206

7.1.2查找算法的性能207

7.2线性表的查找技术207

7.2.1顺序查找207

7.2.2折半查找208

7.3树表的查找技术211

7.3.1二叉排序树211

7.3.2平衡二叉树217

7.3.3B树220

7.4散列表的查找技术225

7.4.1散列查找的基本思想225

7.4.2散列函数的设计226

7.4.3处理冲突的方法227

7.4.4散列查找的性能分析231

7.4.5开散列表与闭散列表的比较232

7.5各种查找方法的比较232

7.6扩展与提高233

7.6.1顺序查找的改进——分块查找233

7.6.2折半查找的改进——插值查找234

7.6.3B树的改进——B 树235

习题7236

 

第8章排序技术239

8.1概述240

8.1.1排序的基本概念240

8.1.2排序算法的性能241

8.2插入排序241

8.2.1直接插入排序241

8.2.2希尔排序243

8.3交换排序245

8.3.1起泡排序245

8.3.2快速排序247

8.4选择排序250

8.4.1简单选择排序250

8.4.2堆排序252

8.5归并排序256

8.5.1二路归并排序的递归实现256

8.5.2二路归并排序的非递归实现257

8.6各种排序方法的比较259

8.7扩展与提高261

8.7.1排序问题的时间下界261

8.7.2基数排序262

习题8264

 

附录A预备知识269

A.1数学术语269

A.2级数求和269

A.3集合270

A.4关系271

 

附录BC语言基本语法273

B.1程序结构273

B.2数据的基本表现形式——常量和变量274

B.3数据类型275

B.4控制语句277

B.5函数278

B.6动态存储分配281

 

附录C词汇索引283

 

参考文献287