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

第1章 绪论 1

1．1什么是数据结构 1

1．2基本概念和常用术语 2

1．3数据抽象和抽象数据类型 6

1．3．1数据抽象 6

1．3．2抽象数据类型 7

1．3．3抽象数据类型描述和实现 8

1．4算法和算法分析 10

1．4．1算法及其性能标准 10

1．4．2算法时间复杂度和渐近时间复杂度 11

1．4．3算法的空间复杂度 13

小结 13

习题 14

第2章 线性表 15

2．1线性表概念 15

2．2线性表的顺序表示和实现 17

2．2．1线性表的顺序存储结构 17

2．2．2线性表在顺序存储结构下的运算 17

2．3线性表的链式表示和实现 21

2．3．1线性链表 21

2．3．2循环链表 28

2．3．3双向循环链表 29

2．3．4顺序表和链表的比较 32

2．4一元多项式的表示及相加 33

小结 36

习题 36

第3章 栈和队列 39

3．1栈 39

3．1．1栈的定义及其运算 39

3．1．2顺序栈 40

3．1．3多栈共享邻接空间 42

3．1．4链栈 44

3．1．5栈的应用举例 46

3．1．6栈与递归的实现 51

3．2队列 54

3．2．1队列的定义 54

3．2．2顺序队列 56

3．2．3链队列 59

3．2．4队列应用举例 60

小结 63

习题 64

第4章 串 67

4．1串的类型定义 67

4．2串的定长顺序存储 70

4．3串的堆存储结构 73

4．3．1串名存储映像 73

4．3．2堆存储结构 75

4．3．3基于堆结构的基本运算 75

4．4串的块链存储结构 78

4．5模式匹配 79

4．6串的应用举例——正文编辑 84

小结 85

习题 86

第5章 数组和广义表 88

5．1数组类型的定义 88

5．2数组顺序存储和实现 90

5．3矩阵压缩存储 92

5．3．1对称矩阵 92

5．3．2三角矩阵 93

5．3．3带状矩阵 94

5．4稀疏矩阵 95

5．4．1稀疏矩阵三元组表存储 95

5．4．2稀疏矩阵十字链表存储 103

5．5广义表 107

5．5．1广义表的定义和基本运算 107

5．5．2广义表的存储 108

5．5．3广义表基本操作的实现 110

小结 113

习题 113

第6章 树 115

6．1树的基本概念 115

6．1．1树的定义 115

6．1．2树的逻辑表示方法 116

6．1．3树的基本术语 117

6．1．4树的抽象数据类型定义 118

6．1．5树的存储结构 119

6．2二叉树的概念和性质 122

6．2．1二叉树的概念 122

6．2．2二叉树的性质 123

6．2．3二叉树与树、森林之间的转换 125

6．3二叉树的存储结构 127

6．3．1二叉树的顺序存储结构 127

6．3．2二叉树的链式存储结构 128

6．4二叉树的遍历 129

6．4．1二叉树遍历的概念 129

6．4．2二叉树遍历递归算法 130

6．4．3二叉树遍历非递归算法 131

6．5二叉树的基本运算及其实现 134

6．5．1二叉树的基本运算 134

6．5．2二叉树的基本运算算法实现 135

6．6二叉树的构造 137

6．7线索二叉树 138

6．7．1线索二叉树的概念 138

6．7．2线索化二叉树 139

6．7．3遍历线索化二叉树 140

6．8哈夫曼树 141

6．8．1哈夫曼树的概述 141

6．8．2哈夫曼树的构造算法 142

6．8．3哈夫曼编码 143

小结 146

习题 146

第7章 图 149

7．1图的基本概念 149

7．1．1图的定义 149

7．1．2图的基本术语 151

7．2图的存储结构 152

7．2．1邻接矩阵存储方法 152

7．2．2邻接表存储方法 155

7．2．3十字邻接表存储方法 157

7．2．4邻接多重表存储方法 159

7．3图的遍历 160

7．3．1图的遍历的概念 160

7．3．2深度优先搜索遍历 161

7．3．3广度优先搜索遍历 162

7．3．4非连通图的遍历 164

7．4生成树和最小生成树 165

7．4．1生成树的概念 165

7．4．2最小生成树的定义 165

7．4．3无向图的连通分量和生成树 166

7．4．4有向图的强连通分量 166

7．4．5普里姆算法 167

7．4．6克鲁斯卡尔算法 168

7．5最短路径 171

7．5．1路径的概念 171

7．5．2从一个顶点到其余各顶点的最短路径 171

7．5．3每对顶点之间的最短路径 174

7．6拓扑排序 176

7．7 AOE网与关键路径 179

小结 184

习题 184

第8章 查找 186

8．1查找的基本概念 186

8．2线性表的查找 188

8．2．1顺序查找 188

8．2．2二分查找 189

8．2．3分块查找 192

8．3树表的查找 194

8．3．1二叉排序树 194

8．3．2平衡二叉树 201

8．3．3 B-树 210

8．3．4 B＋树 214

8．4哈希表查找 215

8．4．1哈希表的基本概念 215

8．4．2哈希函数构造方法 216

8．4．3哈希冲突解决方法 218

8．4．4哈希表上的运算 221

小结 224

习题 224

第9章 内排序 226

9．1排序的基本概念 226

9．2插入排序 227

9．2．1直接插入排序 228

9．2．2希尔排序 229

9．3交换排序 231

9．3．1冒泡排序 231

9．3．2快速排序 233

9．4选择排序 236

9．4．1直接选择排序 237

9．4．2堆排序 238

9．5归并排序 242

9．6基数排序 245

9．7各种内排序方法的比较和选择 248

小结 250

习题 250

第10章 文件 252

10．1文件的基本概念 252

102顺序文件 254

10．3索引文件 255

10．4索引顺序文件 257

10．4．1 ISAM文件 257

10．4．2 VSAM文件 259

10．5散列文件 261

10．6多关键字文件 262

10．6．1多重表文件 262

10．6．2倒排文件 263

小结 264

习题 264

第11章 上机实验题 266

11．1实验一线性表的顺序存储结构 266

11．2实验二单向链表 267

11．3实验三双向链表 267

11．4实验四栈、队列 268

11．5实验五二叉树 269

11．6实验六图 270

11．7实验七查找 271

11．8实验八排序 272

参考文献 274