数据结构 C语言版

第一章 绪论 1

第一节 引言 1

第二节 数据结构的基本概念 1

第三节 算法的概念、算法描述和算法分析 3

一、算法的概念 3

二、算法描述 4

三、算法分析 5

习题 6

第二章 线性表和数组 7

第一节 线性表及其存储表示 7

一、线性表 7

二、线性表的存储表示 8

第二节 线性表的查找、插入和删除 9

一、线性表的查找 10

二、线性表的插入和删除 12

第三节 栈和队列 14

一、栈的结构及运算 14

二、计算表达式——栈的应用举例 17

三、队列的结构及运算 19

第四节 数组的顺序分配 24

第五节 稀疏矩阵 27

第六节 线性表的应用举例 30

习题 37

第三章 链表 39

第一节 线性链表的存储表示 39

第二节 线性链表的建立、查找、插入和删除 40

一、线性链表的建立和查找 40

二、线性链表的插入和删除 45

第三节 链栈和链队列 49

一、链栈的结构及运算 49

二、链队列的结构及运算 50

第四节 循环链表 52

一、循环链表的结构 52

二、循环链表的查找、插入和删除 52

第五节 双向链表 62

一、双向链表的结构 62

二、双向链表的查找、插入和删除 63

第六节 链表的应用 68

一、多项式相加问题 68

二、约瑟夫环问题 74

习题 77

第四章 串 78

第一节 串的基本概念 78

第二节 串的基本运算 79

第三节 串的存储结构 81

一、串的静态存储结构 81

二、串的动态存储结构 82

第四节 串基本操作的实现 84

一、求子串定位函数index(s，t) 84

二、求替换运算replace(a，b，c) 85

第五节 串操作应用——文本编辑 86

习题 88

第五章 树 89

第一节 一般树的概念 89

一、一般树的定义 89

二、基本术语 89

三、树的存储结构 90

第二节 二叉树 92

一、二叉树的基本概念 92

二、二叉树的性质 94

三、二叉树的存储 95

第三节 二叉树的遍历 97

一、二叉树的遍历方式 97

二、遍历算法 97

三、由数据序列恢复二叉树 99

第四节 线索二叉树 103

一、线索二叉树的结构 103

二、线索二叉树的检索 104

第五节 二叉树的应用——表达式树 106

一、表达式树的概念 106

二、构造表达式树的方法 106

三、构造表达式树的算法 107

第六节 二叉排序树 109

一、二叉排序树的结构 109

二、建立二叉排序树的算法 109

三、在二叉排序树中删除结点 111

四、二叉查找树 113

第七节 哈夫曼树 113

一、树的路径长度和带权路径长度 113

二、哈夫曼树和哈夫曼算法 115

第八节 二叉树与树、森林之间的转换 117

一、二叉树与树之间的转换 117

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

习题 120

第六章 图 122

第一节 基本术语 122

第二节 图的存储结构 124

一、邻接矩阵 124

二、邻接链表 125

三、多重邻接表 127

第三节 遍历图 128

一、深度优先搜索法 128

二、广度优先搜索法 129

第四节 最短路径 131

一、从某个源点到其他各顶点的最短路径 131

二、求每一对顶点之间的最短路径 135

第五节 拓扑排序 138

一、AOV网 138

二、拓扑排序的方法 139

第六节 关键路径 141

习题 142

第七章 查找 144

第一节 顺序查找 145

第二节 折半查找 146

第三节 分块查找 150

第四节 哈希法 151

一、哈希法查找的概念 151

二、哈希函数的构造 152

三、解决冲突的方法 155

第五节 各种查找方法的比较及应用 160

一、各种查找方法的比较 160

二、应用举例 161

习题 165

第八章 排序 166

第一节 插入排序 167

一、直接插入排序 167

二、希尔排序 169

第二节 选择排序 171

一、直接选择排序 171

二、堆排序 172

第三节 交换排序 177

一、冒泡排序 177

二、快速排序 178

第四节 归并排序 181

第五节 各种排序方法的比较及应用 184

一、各种排序方法的比较 184

二、应用举例 185

习题 189

第九章 文件 191

第一节 文件的基本知识 191

一、文件的概念 191

二、文件的存储介质 191

三、文件的种类 193

四、文件的操作 193

第二节 文件的结构 194

一、顺序文件 194

二、索引文件 195

三、索引顺序文件ISAM 196

习题 199

实验 200

实验一 线性表的查找、插入、删除 200

实验二 线性链表的查找、插入、删除 200

实验三 循环链表的操作 204

实验四 串操作运算 209

实验五 线索二叉树的检索 213

实验六 二叉排序树的建立及中序遍历 215

实验七 最短路径的实现 216

实验八 查找练习 217

实验九 学生成绩管理 218

参考文献 220