数据结构 C语言描述PDF电子书下载

序 1

前言 1

第1章　学习数据结构课程的意义 1

本章学习目标 1

1.1 实例：高校选修课程管理 1

1.1.1 问题描述 1

目录 1

1.1.2　问题的分析 2

1.1.3　学习本课程的意义 3

1.2　数据结构的主要内容 3

1.2.1　基本概念和术语 3

1.2.2　数据结构定义 4

2.1.3　实现算法 1 5

1.2.3　逻辑结构的表示方法 5

1.3　算法和算法分析 7

1.3.1　算法定义 7

1.3.2　算法分析 8

本章小结 10

习题 10

第2章　线性表 14

本章学习目标 14

2.1 实例：学生信息的存储 14

2.1.1 问题描述 14

2.1.2　问题的分析 14

2.2　线性表的逻辑结构 16

2.2.1　线性表的逻辑结构 16

2.3.1　顺序存储方式 17

2.3　线性表的顺序存储 17

2.2.2　线性表的基本操作 17

2.3.2　各种操作的实现 18

2.4　线性表的链式存储 23

2.4.1　链式存储方式 23

2.4.2　各种操作的实现 25

2.4.3　循环单链表 28

2.4.4　双向链表 28

2.5　动态存储管理 30

2.5.1　存储管理的任务 30

2.5.2　内存的动态分配和回收 31

2.6　应用举例：线性表的建立与合并 34

2.6.1　线性表的建立 34

2.6.2　线性表的合并 36

2.6.3　线性表的逆置 37

2.6.4　线性表各种操作的综合实践 39

本章小结 44

习题 45

第3章　栈和队列 47

本章学习目标 47

3.1 实例：药店药品柜的管理 47

3.1.1 问题描述 47

3.1.2 问题分析 47

3.2　逻辑结构及特征 47

3.2.1　栈的基本概念 48

3.2.2　队列的基本概念 49

3.3　栈的存储结构 50

3.3.1　栈的顺序存储 50

3.3.2　栈的链式存储 52

3.4.1 队列的顺序存储 55

3.4　队列的存储结构 55

3.4.2　队列的链式存储 58

3.5　应用举例 61

3.5.1 表达式中的括号匹配的检验 61

3.5.2　递归 61

3.5.3　栈和队列的各种操作的综合实践 63

本章小结 67

习题 68

第4章　串 70

本章学习目标 70

4.1 串类型的定义 70

4.2　串的存储结构 70

4.2.1　串的顺序存储 71

4.2.3　串的索引存储 72

4.2.2　串的链式存储 72

4.3 串的操作 73

4.3.1 串常用操作的实现 74

4.3.2　模式匹配操作 82

本章小结 87

习题 87

第5章　数组 89

本章学习目标 89

5.1 数组 89

5.1.1 一维数组 89

5.1.2　多维数组 89

5.2　数学中的应用 91

5.2.1　稀疏矩阵 91

5.2.2　特殊矩阵 97

5.3.1　基本概念 99

5.3　广义表 99

5.3.2　广义表的存储结构 100

5.3.3　广义表的运算 102

本章小结 107

习题 107

第6章　树 110

本章学习目标 110

6.1　实例1：文件目录管理 110

6.1.1　问题描述 110

6.1.2　问题分析 110

6.1.3　实现算法 111

6.2　树的逻辑结构和存储结构 112

6.2.1　树的逻辑结构 112

6.3　树的遍历 113

6.2.2　树的相关术语 113

6.3.1　先根遍历 114

6.3.2　后根遍历 114

6.3.3　按层遍历 114

6.4　实例2：通信中电文编码 115

6.4.1　问题描述 115

6.4.2　问题分析 115

6.4.3　 实现算法 116

6.5　二叉树的定义和存储结构 117

6.5.1　二叉树的定义 117

6.5.2　二叉树的性质 118

6.5.3　二叉树的存储结构 119

6.6　二叉树遍历 121

6.6.1　先根遍历 121

6.6.2　中根遍历 123

6.6.3　后根遍历 124

6.6.4　按层遍历 125

6.6.5　二叉树遍历的应用 126

6.7　树与二叉树的转换 127

6.7.1　树的存储结构 127

6.7.2　树与二叉树的转换 129

6.7.3　森林与二叉树的转换 131

6.8　应用举例 132

6.8.1 线索二叉树 132

6.8.2　二叉排序树 134

6.8.3　哈夫曼树 136

6.8.4　二叉树的综合实例 137

本章小结 141

习题 142

7.1.1　问题描述 146

7.1.2　问题分析 146

第7章　图 146

7.1　实例：求城市间最短路径 146

本章学习目标 146

7.2 图的逻辑结构和特征 148

7.2.1 图的逻辑结构 148

7.2.2　图的特征 149

7.3　图的存储结构 151

7.3.1　邻接矩阵 151

7.3.2　邻接表 153

7.3.3 十字链表 155

7.3.4　边集数组 156

7.3.5　邻接多重表 157

7.4.1　深度优先搜索 158

7.4　图的遍历 158

7.4.2　广度优先搜索 159

7.5　最小生成树 160

7.5.1　克鲁斯卡尔算法 161

7.5.2　普里姆算法 163

7.6　应用举例 166

7.6.1　求源点到其余各顶点间的最短路径 166

7.6.2　拓扑排序 168

本章小结 172

习题 173

8.1　实例：学生分配座位 176

8.1.1 问题描述 176

8.1.2　问题分析 176

本章学习目标 176

第8章　典型查找算法 176

8.1.3　实现算法 177

8.1.4　基本概念 178

8.2　静态查找 178

8.2.1 顺序查找 179

8.2.2　折半查找 179

8.2.3　分块查找 182

8.3　动态查找 183

8.3.1　二叉排序树查找 183

8.3.2　二叉平衡树 185

8.4　散列查找 186

8.4.1 散列存储和散列函数的构造方法 186

8.4.2　解决冲突的方法 188

8.4.3 散列查找实现算法和性能分析 190

本章小结 192

习题 193

本章学习目标 195

9.1 实例：统计学生成绩表 195

9.1.1 问题描述 195

第9章　典型排序算法 195

9.1.2 问题分析 196

9.1.3　实现算法 196

9.1.4　排序定义及相关概念 197

9.2　插入排序 198

9.2.1　直接插入排序 198

9.2.2　折半插入排序 199

9.2.3　希尔排序 199

9.3　选择排序 201

9.3.1　直接选择排序 201

9.3.2　堆排序 202

9.4.1 冒泡排序 205

9.4　交换排序 205

9.4.2　快速排序 206

9.5　归并排序和基数排序 208

9.5.1 归并排序 208

9.5.2　基数排序 211

9.6　比较各种内排序方法 214

9.6.1　各种内排序方法的比较 214

9.6.2　各种内排序方法的选择 215

9.7　外排序 216

9.7.1　外排序的基本过程 216

9.7.2　多路归并排序 217

本章小结 218

习题 219

10.1.2　问题分析 222

10.1.1　问题描述 222

第10章　案例分析 222

10.1　约瑟夫问题 222

本章学习目标 222

10.1.3 函数设计 223

10.1.4　上机调试 224

10.2　迷宫求解 225

10.2.1　问题描述 225

10.2.2　问题分析 225

10.2.3　函数设计 226

10.2.4　上机调试 229

10.3　排队问题 230

10.3.1　问题描述 230

10.3.2　问题分析 231

10.3.3　 函数设计 231

10.3.4　上机调试 234

10.4　教学计划中的课程编排 236

10.4.1　问题描述 236

10.4.2　问题分析 237

10.4.3　函数设计 237

10.4.4　上机调试 240

10.5　简单的学籍管理系统 241

10.5.1 问题描述 241

10.5.2　问题分析 242

10.5.3　函数设计 242

10.5.4　上机调试 246

本章小结 248

习题 249

参考文献 250