算法与数据结构：C语言版

本书主要内容包括绪论、线性表、栈和队列、串、数组、树形结构、图、内部排序、查找。教材中对各类数据结构的分析按照“逻辑结构—存储结构—基本运算的实现—时空性分析—实例”的顺序进行讲述，结构规范，条理清晰。
书中给出的程序和算法都是经过仔细筛选的经典内容，便于读者理解和掌握，程序采用C语言描述并容易调试通过；每章有重点介绍和总结，总结对重要的知识点进行穿线，每章后针对本章重要知识点配有大量习题。
本书可作为高等院校计算机有关专业本科生、专科生教材，也可作为自考成人教育的教材。

目录
第1章数据结构与算法1

1.1学习数据结构1

1.1.1为什么学习数据结构1

1.1.2如何学习数据结构2

1.2基本概念和术语3

1.2.1基本概念3

1.2.2逻辑结构和存储结构4

1.3算法7

1.3.1算法的定义7

1.3.2算法的特性8

1.3.3算法效率度量方法8

1.3.4算法的时间复杂度9

本章小结13

练习题13

第2章线性表16

2.1线性表及其逻辑结构16

2.1.1线性表的定义16

2.1.2线性表的基本运算17

2.2线性表的顺序存储结构18

2.2.1线性表的顺序存储结构——顺序表18

2.2.2顺序表基本运算的实现19

2.3线性表的链式存储结构23

2.3.1线性表的链式存储结构——链表23

2.3.2单链表25

2.3.3循环链表32

2.3.4双链表33

2.4线性表的应用35

2.5顺序表和单链表的比较41

本章小结42

练习题42

第3章栈和队列45

3.1栈45

3.1.1栈的定义及基本运算45

3.1.2栈的顺序存储结构及其基本运算实现46

3.1.3栈的链式存储结构及其基本运算的实现50

3.2栈的应用实例51

3.2.1数制转换问题51

3.2.2迷宫的求解53

3.2.3表达式求值56

3.2.4栈与递归59

3.3队列61

3.3.1队列的定义及基本运算61

3.3.2队列的顺序存储结构及其基本运算的实现61

3.3.3队列的链式存储结构及其基本运算的实现65

本章小结67

练习题67

第4章串69

4.1串的基本概念69

4.1.1串的基本概念69

4.1.2串的抽象数据类型70

4.1.3C语言的串函数71

4.2串的存储结构73

4.2.1串的顺序存储结构——顺序串73

4.2.2串的链式存储结构——链串74

4.3串的模式匹配75

4.3.1BruteForce算法75

4.3.2KMP算法77

本章小结82

练习题83

第5章数组85

5.1数组85

5.1.1数组的基本概念85

5.1.2数组的顺序表示和实现85

5.2特殊矩阵的压缩存储86

5.2.1特殊矩阵87

5.2.2稀疏矩阵89

本章小结94

练习题94

第6章树和二叉树96

6.1树的定义和基本术语96

6.2二叉树100

6.2.1二叉树的概念100

6.2.2二叉树的性质102

6.2.3二叉树的存储103

6.2.4二叉树的基本操作及实现105

6.3二叉树的遍历108

6.3.1二叉树的遍历方法及递归实现108

6.3.2二叉树遍历的非递归实现110

6.3.3由遍历序列恢复二叉树114

6.3.4不用栈的二叉树遍历的非递归方法115

6.4线索二叉树116

6.4.1线索二叉树的定义及结构116

6.4.2线索二叉树的基本操作实现118

6.4.3树、森林与二叉树的转换123

6.5哈夫曼树及其应用125

6.5.1二叉树遍历的应用125

6.5.2二叉树——哈夫曼树128

本章小结134

练习题134

第7章图139

7.1图的定义与基本术语139

7.1.1图的定义139

7.1.2基本术语140

7.2图的存储结构143

7.2.1邻接矩阵表示法143

7.2.2邻接表146

7.2.3十字链表148

7.3图的遍历149

7.3.1深度优先遍历149

7.3.2广度优先遍历151

7.4小生成树153

7.4.1普利姆算法153

7.4.2克鲁斯卡尔算法155

7.5拓扑排序155

7.5.1拓扑排序156

7.5.2拓扑排序算法156

7.6关键路径158

7.6.1关键路径的概念和原理158

7.6.2关键路径算法159

7.7短路径163

7.7.1求某一顶点到其他各顶点的短路径164

7.7.2求任意一对顶点间的短路径166

本章小结168

练习题168

第8章内部排序172

8.1基本概念172

8.2插入排序175

8.2.1直接插入排序175

8.2.2希尔排序177

8.3交换排序179

8.3.1冒泡排序179

8.3.2快速排序183

8.4选择排序188

8.4.1简单选择排序188

8.4.2堆排序190

8.5归并排序194

8.5.12路归并排序194

8.5.22路归并排序的时间复杂度196

8.6内部排序方法的比较和选择196

本章小结197

练习题197

第9章查找200

9.1查找基本概念200

9.2静态查找201

9.2.1顺序查找202

9.2.2二分查找203

9.2.3索引查找205

9.3动态查找206

9.3.1二叉排序树206

9.3.2平衡二叉树211

9.4散列表查找214

9.4.1散列表214

9.4.2散列函数构造方法214

9.4.3处理冲突的方法215

9.4.4散列表的查找和分析216

本章小结216

练习题217

参考文献219