第1章 编程准备知识 … 1

  1.1 指针  2

   1.1.1 C语言的变量和指针 … 2

   1.1.2 指针和数组 … 6

   1.1.3 指针和字符串  8

   1.1.4 二维指针  9

  1.2 结构体  10

   1.2.1 定义结构体  10

   1.2.2 用typedef定义新数据类型 10

   1.2.3 结构体变量的定义和访问数据成员  11

  1.3 软考试题 … 13

  本章小结  13

  实验题1  13

  习题1 … 14

第2章 算法与数据结构 … 16

  2.1 数据结构的基本概念和术语 … 17

   2.1.1 数据、数据元素、数据项和数据对象 … 17

   2.1.2 数据结构 … 17

  2.2 抽象数据类型的表示与实现 … 20

   2.2.1 数据类型 … 20

   2.2.2 抽象数据类型 … 20

  2.3 算法与程序的关系 … 21

  2.4 算法复杂度分析  22

   2.4.1 时间复杂度的组成 … 23

   2.4.2 空间复杂度的组成 … 27

  2.5 软考试题 … 28

  本章小结  28

  实验题2  29

  习题2 … 29

第3章 线性表 32

  3.1 线性表的基本概念 … 32

   3.1.1 线性表定义  32

   3.1.2 抽象数据类型定义 … 33

  3.2 线性表的顺序存储 … 35

   3.2.1 线性顺序表的逻辑状态 … 35

   3.2.2 定长数组存储 … 35

   3.2.3 变长数组存储 … 36

   3.2.4 顺序表的操作算法 … 36

   3.2.5 顺序表的算法分析 … 41

  3.3 线性表链式描述  41

   3.3.1 单链表  41

   3.3.2 单链表的操作算法 … 44

   3.3.3 单链表的操作算法复杂度分析  50

   3.3.4 循环单链表  51

   3.3.5 双向循环链表 … 52

  3.4 软考试题 … 54

  本章小结  55

  实验题3  55

  习题3 … 56

第4章 栈  59

  4.1 栈的基本概念 … 59

   4.1.1 栈的定义 … 60

   4.1.2 栈的抽象数据类型定义 … 60

  4.2 栈的顺序存储 … 61

   4.2.1 利用静态数组实现 … 61

   4.2.2 利用动态数组实现 … 64

   4.2.3 算法时间复杂度分析  65

  4.3 栈的链式存储 … 66

  4.4 栈的应用 … 69

   4.4.1 十进制数转换为其他进制  69

   4.4.2 括号匹配的检验  70

   4.4.3 递归 … 71

  4.5 软考试题 … 75

本章小结  75

  实验题4  75

  习题4 … 76

第5章 队列 … 78

  5.1 队列的基本概念  79

   5.1.1 队列的定义  79

   5.1.2 队列的抽象数据类型定义  79

  5.2 循环队列—队列的顺序表示和实现  80

  5.3 链队列—队列的链式表示和实现 … 85

  5.4 软考试题 … 88

  本章小结  89

  实验题5  89

  习题5 … 90第6章 树  91

  6.1 树的基本概念 … 91

   6.1.1 树的定义 … 91

   6.1.2 树结构中常用术语 … 92

  6.2 二叉树  94

   6.2.1 二叉树的定义 … 94

   6.2.2 二叉树的性质 … 95

   6.2.3 二叉树的抽象数据类型定义 … 97

  6.3 二叉树的顺序存储结构 … 99

  6.4 二叉树的链式存储结构 … 100

   6.4.1 二叉树的二叉链表的表示及创建二叉链表 … 100

   6.4.2 二叉树的遍历 … 101

   6.4.3 二叉树表达式 … 102

   6.4.4 二叉链表的遍历算法实现  102

  6.5 线索二叉树  105

  6.6 树和森林 … 110

   6.6.1 树的存储结构 … 110

   6.6.2 树和二叉树的转换 … 111

   6.6.3 树和森林的遍历  114

  6.7 树的应用 … 114

   6.7.1 最优二叉树 (Huffman树) … 114

            6.7.2 构建 Huffman树 (最优二叉树)  117

   6.7.3 Huffman编码 … 118

  6.8 软考试题 … 119

  本章小结 … 121

  实验题6 … 121

  习题6  122

第7章 图 … 125

  7.1 图的定义和术语  126

   7.1.1 图的基本概念 … 126

   7.1.2 图的抽象数据类型定义 … 129

  7.2 图的存储结构 … 131

   7.2.1 邻接矩阵 (顺序存储结构) … 131

   7.2.2 邻接表 (链式存储结构)  135

   7.2.3 十字链表 (链式存储) … 140

  7.3 图的遍历 … 145

   7.3.1 图的深度优先搜索遍历 … 145

   7.3.2 图的广度优先搜索遍历 … 147

  7.4 图的应用 … 148

   7.4.1 生成树与最小生成树  148

   7.4.2 拓扑排序和关键路径  155

   7.4.3 最短路径 … 159

  7.5 软考试题 … 165

  本章小结 … 166

  实验题7 … 166

  习题7  167

第8章 查找  169

  8.1 静态查找 … 170

   8.1.1 顺序表的查找 … 170

   8.1.2 折半查找 … 171

   8.1.3 索引顺序表的查找 … 173

  8.2 动态查找 … 175

   8.2.1 二叉排序树  175

   8.2.2 平衡二叉树 (∗) … 178

  8.3 哈希表查找  184

         8.3.1 哈希表  184

   8.3.2 哈希函数的构造方法  185

   8.3.3 处理冲突的方法  187

   8.3.4 哈希表的查找及其分析 … 189

  8.4 软考试题 … 192

  本章小结 … 193

  实验题8 … 193

  习题8  194

第9章 排序  196

  9.1 插入排序 … 197

   9.1.1 直接插入排序 … 197

   9.1.2 折半插入排序 … 199

   9.1.3 希尔排序 … 201

  9.2 交换排序 … 203

   9.2.1 冒泡排序 … 203

   9.2.2 快速排序 … 204

  9.3 选择排序 … 207

   9.3.1 简单选择排序 … 207

   9.3.2 树形选择排序 … 209

   9.3.3 堆排序  210

  9.4 归并排序 … 213

  9.5 基数排序 (∗)  216

  9.6 软考试题 … 219

  本章小结 … 220

  实验题9 … 220

  习题9  221

参考答案… 223

参考文献… 238