数据结构 使用C语言PDF电子书下载

第一章 绪论 1

1.1 数据结构课程的形成和发展 1

1.2 数据结构与算法 3

1.2.1 什么是数据结构 3

1.2.2 算法的概念和特性 4

1.2.3 数据结构与算法的关系 5

1.3 抽象数据类型 5

1.3.1 抽象——程序设计最基本的思想方法 5

1.3.2 抽象数据类型 6

1.4 算法的描述和分析 7

习题一 8

第二章 线性表 10

2.1 线性表及其抽象数据类型 10

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

2.2.1 顺序分配 12

2.2.2 顺序表的插入和删除 13

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

2.3.1 链式分配 17

2.3.2 线性链表的插入和删除 18

2.4 栈和队列 22

2.4.1 栈的概念 23

2.4.2 栈的存储结构 23

2.4.3 栈的应用 27

2.4.4 队列的概念 33

2.4.5 队列的存储结构 35

2.4.6 队列的应用 40

2.5 循环线性链表和双向链表 41

2.5.1 循环线性链表 41

2.5.2 双向链表和循双向链表 43

2.6 一元多项式的存储和相加 46

习题二 51

3.1 串的基本概念和存储结构 53

3.1.1 串的基本概念 53

第三章 串 53

3.1.2 串的存储结构 54

3.1.3 串变量的存储 56

3.2 串的基本运算 57

3.2.1 串的联接 58

3.2.2 求子串 59

3.2.3 子串的插入和删除 60

3.2.4 串的置换 62

*3.3 模式匹配 64

3.4 汉字串 70

习题三 73

第四章 数组和广义表 74

4.1 数组的顺序存储结构 74

4.1.1 数组元素的地址公式 74

4.1.2 稀疏矩形的三元组表表示法 77

4.2 数组的链接存储结构 82

4.2.1 稀疏矩阵的十字链表表示及矩阵相加 83

4.2.2 三维图形信息的压缩存储 87

4.3 迷宫问题 90

*4.4 广义表 92

习题四 94

第五章 树 96

5.1 树的基本概念和术语 96

5.2 树的存储结构 98

5.3 树的应用 100

5.4.1 二叉树的定义和性质 102

5.4 二叉树 102

5.4.2 二叉树的存储结构 104

5.4.3 二叉树与树、森林之间的转换 106

5.5 二叉树的遍历 109

5.5.1 二叉树链表结构的建立 110

5.5.2 前序遍历 112

5.5.3 中序遍历 113

5.5.4 后序遍历 115

5.6 线索树 117

5.6.1 建立线索树 118

5.6.2 线索树结点的检索 121

5.6.3 在线索树上插入结点 124

5.7 二叉树的应用 126

5.7.1 二叉排序树 126

5.7.2 哈夫曼树 130

习题五 135

第六章 图 137

6.1 基本概念 137

6.2 图的存储结构 139

6.2.1 邻接矩阵 139

6.2.2 邻接表 140

6.3 图的遍历 141

6.3.1 深度优先搜索法 141

6.3.2 广度优先搜索法 143

6.4.1 生成树的概念 145

6.4.2 最小生成树 145

6.4 生成树 145

6.5 最短路径 151

6.5.1 从某个源点到其余各顶点的最短路径 152

6.5.2 每一对顶点间的最短路径 156

6.6 拓扑排序 158

6.6.1 AOV网 158

6.6.2 拓扑排序 159

*6.7 关键路径 164

习题六 169

第七章 查找 171

7.1 线性表的查找 171

7.1.1 顺序查找 171

7.1.2 折半查找 173

7.1.3 分块查找 176

7.2 树表查找 177

7.2.1 二叉查找树 178

7.2.2 平衡二叉树 181

*7.2.3 B树 184

7.3 哈希表及其查找 186

7.3.1 哈希法 186

7.3.2 哈希函数的构造方法 187

7.3.3 解决哈希法冲突的基本方法 189

习题七 194

第八章 排序 196

8.1 插入排序 196

8.1.1 直接插入排序 196

8.1.2 希尔排序 198

8.2 交换排序 201

8.2.1 冒泡排序 201

8.2.2 快速排序 202

8.3 选择排序 206

8.3.1 直接选择排序 206

8.3.2 堆排序 207

8.4 归并排序 212

*8.5 基数排序 215

8.6 外排序 221

8.6.1 外存设备 221

8.6.2 文件及其组织 222

8.6.3 外排序的基本方法 223

习题八 227

第九章 数据结构应用示例 229

9.1 存储管理 229

9.1.1 存储管理基本概念 229

9.1.2 动态存储分配和回收 230

9.1.3 不用单元收集和紧凑存储 235

9.2 学生成绩管理 235

9.2.1 学生成绩管理软件的数据结构 236

9.2.2 各函数的功能和实现 237

习题九 250

附录一 数据结构上机实习 252

附录二 若干程序 254

参考书目 265