数据结构 1000个问题与解答（C语言版）PDF电子书下载

第1章 数组 1

1.0 引言 1

1.1　如何初始化数组 1

1.1.1　初始化：在声明数组时 1

1.1.2　初始化：使用循环 1

1.1.3　初始化：使用另一个数组的值 2

1.1.4　初始化：使用特殊值 2

1.2　如何使用下标遍历一维数组 2

1.2.1　如何使用指针遍历一维数组 3

1.2.2　如何使用下标遍历二维数组 3

1.2.3　如何使用指针遍历二维数组 3

1.3　如何操作数组元素 3

1.4　如何把指定范围内的数据元素加起来 5

1.5　如何把数组中偶数位置和奇数位置的元素加起来 5

1.6　如何执行包含外部变量的运算 6

1.6.1　如何乘以数组元素 7

1.6.2　如何仅仅把数组中的偶数元素加起来 7

1.6.3　如何仅仅把数组中的奇数元素加起来 7

1.6.4　如何把一个元素加到数组每一个元素上 7

1.6.5　如何从数组的每一个元素中减去某个元素 8

1.6.6　如何将一个元素乘以数组的每一个元素 8

1.6.7　如何让数组的每一个元素除以某个元素 8

1.6.8　如何平方数组的每一个元素 9

1.7　如何找出函数值 9

1.8　如何求解人口统计学应用——一个人口统计的问题 9

1.9　在什么地方使用三维数组 10

1.10　如何删除数组中的某个特定数据项 11

1.11 如何删除特定位置的数据项 12

1.12　如何得到数组中的最大值 14

1.13　如何得到数组中的最小值 15

1.14　如何按字母顺序排序数组 15

1.15　如何检查字符串是否是回文字符串 16

1.16　如何搜索数组元素 17

1.17　如何让数组元素唯一 18

1.18　如何计算数组元素的平均值 19

1.19　如何计算一组整数的加权平均值 20

1.20　如何计算已排序数组元素的中值 20

1.21　如何找出数组元素的众数 21

1.22　如何得到数组元素的值域 22

1.23　如何得到数组的标准差 22

1.24　如何得到数组元素的方差 24

1.25　如何使用牛顿前向差分内插法得到内插值 24

1.26　如何使用拉格朗日内插公式插值 25

1.27　如何得到X或Y的回归线 27

1.28　如何得到简单聚合指数 28

1.29　如何得到价格相关指数的简单平均值 30

1.30　如何得到拉斯贝尔（Laspeyre）指数 30

1.31 如何得到派许（Paasche）指数 31

1.32　如何得到鲍莱（Bowley）指数 31

1.33　如何得到费雪（Fisher）指数 31

1.34　如何得到马歇尔-爱德华（Marshall-Edward）指数 32

1.35　如何使用二维数组表示矩阵 32

1.36　如何把两个3×3矩阵加起来 33

1.37　如何做两个3×3矩阵的减法 34

1.38　如何做两个矩阵的乘法 34

1.39　如何使用矩阵乘法计算收入 35

1.40　使用斯特拉森算法计算2×2矩阵的乘法，它仅需7次乘法和18次加法即可完成 36

1.41 如何得到两个矩阵的Hadamard积 37

1.42　如何得到两个矩阵的Kronecker积 38

1.43　如何得到矩阵的转置矩阵 39

1.44　如何得到方阵的逆矩阵 40

1.45　如何得到矩阵的上三角矩阵 42

1.46　如何得到严格上三角矩阵 43

1.47　如何得到矩阵的下三角矩阵 43

1.48　如何得到严格下三角矩阵 44

1.49　如何用给定的行和列构造Toeplitz矩阵 45

1.50　如何判断矩阵是否是对称矩阵 45

1.51　将稀疏矩阵表示为数组 46

1.51.1 如何把两个稀疏矩阵相加 47

1.52　三维数组应用 49

1.53　如何从函数中返回多个值 50

1.54　如何克隆Java的字符串分词类 51

1.55　二进制到十进制转换 52

1.56　如何为股票交易设计一张图表 53

1.57　如何得到HHI指数 55

1.58　如何得到城市的基尼系数 56

1.59　如何判断三个给定数字是否构成等差数列、等比数列或调和数列 57

1.60　不同信号格式的动画 58

1.61 一个著名的密码技术——密写术 64

1.62　上述加密法的解密程序 65

1.63　如何得到256级灰度图像的直方图 66

1.64　如何把灰度图像转换为黑白图像／负片图像 67

概念复习 68

练习题 69

编程题 70

第2章　结构 73

2.0 引言 73

2.1 使用typedef 73

2.2　访问结构元素 74

2.3 Turbo C（DOS下）中一些内置的有用结构 75

2.4　如何定义一个表示三维空间中点的结构 76

2.5　如何使用点结构得到多边形的图心 76

2.6　如何得到三维空间中两个点之间的距离 77

2.7　如何得到任何正多边形的面积 77

2.8　如何测试三个点的共线性 78

2.9　如何检查三角形是否是等边三角形 78

2.10　如何检查三角形是否是等腰三角形 79

2.11　如何使用Point结构建立三角形模型 79

2.12　如何检查三角形是否是直角三角形 80

2.13 如何得到三角形是否是等边三角形 80

2.14　如何使用三角形构建四面体模型 81

2.15　如何使用Struct和Enum建立矩形模型 82

2.16　如何使用Point建立梯形模型 82

2.17　如何检查梯形是否是等腰梯形 83

2.18　如何检查点是否位于三角形内部 83

2.19　如何检查点是否位于矩形内部 84

2.20　如何检查点是否位于圆内部 85

2.21　如何检查两个圆是否相交 85

2.22　如何检查两个圆是否相切 86

2.23　如何以斜率方式建立直线模型 86

2.24　如何以XY截距格式建立直线模型 87

2.25　如何把XY截距形式的直线转换为斜率格式的直线 87

2.26　如何把斜率格式的直线转换为XY截距形式的直线 87

2.27　如何检查两条直线是否平行 87

2.28　如何得到两条直线的交点 88

2.29　如何得到圆上任一点的切线 88

2.30　如何使用直线和点建立抛物线模型 88

2.31 如何得到抛物线上任一点的切线 89

2.32　如何得到抛物线上任一点的法线 89

2.33　如何建立椭圆模型 89

2.34　如何计算椭圆的面积 90

2.35　如何得到椭圆上任何一点的切线 90

2.36　如何得到椭圆上任何一点的法线 90

2.37　如何用结构建立棱柱建模 91

2.38　如何建立圆柱的模型 91

2.39　如何得到圆柱的表面积 92

2.40　如何建立圆锥的模型 92

2.41 如何得到圆锥的面积 92

2.42　如何得到由圆和点定义的圆柱的体积 93

2.43　如何得到棱柱的面积 93

2.44　如何检查点是否位于椭圆的内部 94

2.45　如何检查点是否位于双曲线内部，假定给出了长轴或短轴 94

2.46　如何建立菱形的模型 95

2.47　如何得到菱形的面积 95

2.48　如何以结构方式建立向量的模型 95

2.49　如何编写向量加法的函数 95

2.50　如何得到向量的加权和 96

2.51 如何检查向量的加权和是否是仿射和 97

2.52　如何编写一个得到两个向量积的函数 97

2.53 如何编写一个得到两个向量向量积的函数 98

2.54　如何编写一个向量标量乘法的函数 98

2.55　如何得到三个向量的点积 99

2.56　如何检测三个向量是否共面 99

2.57　如何得到三个向量的向量积 99

2.58　如何得到四个向量的标量积 100

2.59　如何得到四个向量的向量积 100

2.60　如何用结构建立复数模型 100

2.61 如何在极坐标和直角坐标之间转换 101

2.62　如何把复数加起来 102

2.63　如何用一个复数减去另一个复数 102

2.64　如何乘两个复数 103

2.65　使用极坐标复数结构验证棣莫弗定理 103

2.66　如何使用结构编写一个电话本模拟程序 103

2.67　如何以结构组合方式建立银行账户模型 107

2.68　如何使用结构编写一个POS（销售点）模拟程序 109

概念复习 123

练习题 123

编程题 124

第3章　链表 126

3.0　引言 126

3.1 单向链表 126

3.2　双向链表 128

3.3　循环链表 129

3.4　你如何处理链表数组 129

3.5　在C和预测器重的链表 130

3.6　本章的链表函数理念 130

3.7　如何在单向链表的末尾插入一个结点 131

3.8　如何在单向链表首部插入结点 132

3.9　如何得到单向链表的第一个元素 133

3.10　如何得到单向链表的最后一个元素 134

3.11　如何遍历单向链表 134

3.12　如何计数单向链表中结点的个数 134

3.13　如何得到单向链表中数据项的频率 135

3.14　如何搜索单向链表中特定数据项 135

3.15　如何得到单向链表中特定结点的地址 136

3.16　如何在单向链表的特定位置插入结点 136

3.17　如何在单向链表特定元素之前插入一个结点 137

3.18　如何显示单向链表的所有内容 138

3.19　如何得到单向链表的最大元素 138

3.20　如何得到单向链表的最小值 139

3.21 如何使用给定值编辑特定结点的内容 139

3.22　如何编写一个合并两个链表的函数 140

3.23　如何编写一个将一个链表插入到另一个链表中的函数 141

3.24　如何交换单向链表的首尾结点（即第一个结点和最后一个结点） 142

3.25　如何对换除首尾结点之外的任何其他两个结点 143

3.26　如何删除由下标数字给定的特定结点 143

3.27　如何从链表中删除一个范围的元素 144

3.28　如何从链表中隔一个元素删除一个元素 145

3.29　如何让链表数据项唯一 145

3.30　如何删除链表的第一个元素 146

3.31　如何删除链表的最后一个元素 146

3.32　链表和判定函数 147

3.33　作为一个数据结构的多项式的属性和方法是什么 148

3.34　如何使用单向链表表示多项式 148

3.35　多项式工具箱 149

3.36　如何在多项式上增加一个新的数据项 150

3.37　如何把两个多项式相加并返回它们的和 151

3.38　如何将两个多项式相乘 151

3.39　如何得到多项式的微分 151

3.40　如何计算多项式的积分 152

3.41 如何计算给定值处多项式的值 152

3.42　如何得到函数的定积分值 152

3.43　如何显示多项式 152

3.44　如何得到复合函数的值 153

3.45　如何在多项式中添加一个新的数据项 154

3.46　如何把两个三变量多项式相加 155

3.47　如何把两个三变量多项式相乘 155

3.48　如何计算多项式对x的微分 155

3.49　如何计算多项式对y的微分 156

3.50　如何计算多项式对z的微分 156

3.51 如何计算多项式对x的积分，假定其他两个变量为常量 156

3.52　如何计算多项式对y的积分，假定其他两个变量为常量 157

3.53　如何计算多项式对z的积分，假定其他两个变量为常量 157

3.54　当所有三个变量都变化时如何积分多项式 157

3.55　如何对给定的x、y、z值计算多项式的值 157

3.56　如何在给定区间内积分多项式 158

3.57　多项式工具箱的一些应用 158

3.58　如何得到三变量函数的卷积 159

3.59　大数：链表的应用 160

3.60　如何在链表中存储两个大数，之后把这两个大数相加并显示和 161

3.61　数字信号处理 162

3.61.1　如何使用链表建立数字信号的模型 162

3.62　如何得到信号长度 163

3.63　如何得到信号中给定振幅的位置 163

3.64　如何在信号末尾添加一个新值 164

3.65　如何在信号前部添加新值 165

3.66　如何返回第一个信号结点指针 165

3.67　如何返回最后一个信号结点指针 166

3.68　如何在信号的特定位置插入结点 166

3.69　如何显示数字信号 166

3.70　如何得到第一个信号结点的振幅 167

3.71 如何得到最后一个信号结点的振幅 167

3.72　如何得到给定信号特定振幅的频率 167

3.73　如何得到给定索引信号结点的地址 168

3.74　如何得到特定点信号的振幅 168

3.75　如何检查数字信号是否是偶信号 168

3.76　如何检查数字信号是否是因果信号 169

3.77　如何检查数字信号是否是反因果信号 170

3.78　如何检查信号是否是非因果信号 171

3.79　如何在单向循环链表末尾添加结点 171

3.80　双向链表 172

3.80.1 如何编写一个建立整型双向链表的模型 172

3.81　如何在双向链表末尾添加一个数值 172

3.82　如何在双向链表前部添加一个数值 173

3.83　如何前进到双向链表的下一个结点 173

3.84　如何前进到双向链表的前一个结点 174

3.85　如何以前向方式显示双向链表 174

3.86　如何以后向方式显示双向链表 174

3.87　如何在链表的某个位置插入一个值 174

3.88　如何在循环双向链表末尾添加一个值 175

3.89　链表在生物化学上的应用 176

3.89.1　使用链表表示DNA链 176

3.90　如何被两个单DNA链混合到另一个DNA上 178

3.91 如何把一个DNA溶合到一对链中 179

3.92　如何模拟一个DNA链到另一个DNA链的链接 180

3.93　如何使用锯齿数组表示稀疏矩阵 181

3.94　如何在稀疏矩阵中添加一个数据项 182

3.95　如何把一个锯齿行添加到稀疏矩阵的锯齿表示中 182

3.96　如何从用户处接收稀疏矩阵的元素并创建链表的锯齿数组以空间高效方式表达该矩阵 183

3.97　使用锯齿数组表示手写签名 184

3.98　如何使用链表建立简单内容管理系统的模型 185

3.99　如何使用链表建立工作流引擎系统的模型 189

3.100　数组和链表的对比 190

概念复习 191

练习题 192

编程题 193

第4章　字符串 194

4.0 引言 194

4.1 C中有关字符串的一些关键事实 194

4.2　C-风格字符串 195

4.2.1　字符串初始化 195

4.3　如何在声明时初始化 195

4.4　如何使用用户定义值初始化字符串 195

4.5　如何使用一个字符串初始化另一个字符串 196

4.6　如何使用字符值初始化字符串 196

4.7　如何使用ASCII值初始化字符串 197

4.8 一些内置Turbo C字符串库函数简介 197

4.8.1　得到字符串长度 198

4.8.2　连接两个C-风格字符串 198

4.8.3 比较两个字符串 199

4.8.4　将字符串复制到另一个字符串 200

4.8.5　将字符串改变为小写或大写 202

4.9　设计使用这两个函数的实用工具 202

4.9.1 纠正C/C＋＋程序中错误的大小写（使用strlwr（） 202

4.10　用于更改文件中几个所选缩略语大小写的工具（使用strupr（）） 204

4.11　如何颠倒字符串 205

4.12　如何使用一个字符设置字符串中的字符 206

4.13　如何找到子串字符在另一个字符串中的第一次出现 207

4.14　如何得到两个字符串开始不同的位置 208

4.15　如何以内存高效方式创建字符串的副本 209

4.16　如何将字符串拆分为符号 210

4.17　你知道什么是字符串前缀吗 211

4.18　你知道什么是字符串后缀吗 212

4.19　你知道什么是字符串的子序列吗 213

4.19.1 如何检查单词是否有某个前缀 215

4.19.2　如何检查单词是否有给定的后缀 215

4.19.3　如何接收一个使用空格分隔的单词字符串并以char＊类型返回这些单词的链表 217

4.19.4　如何计算句子中单词的总数 218

4.19.5　如何在短语中用一个单词替换另一个单词 218

4.19.6　如何从句子中删除给定单词的所有出现 219

4.19.7　如何以换行方式显示文本 220

4.19.8　如何演示文本的随机密码学加密 221

4.19.9　如何解密使用上述函数加密的文本 222

4.19.10　如何以字符链表形式表示字符串 223

4.19.11 如何使用字符串的上述链表表示创建新的字符串 223

4.19.12　如何显示链表表示的字符串 224

4.19.13　如何从字符串中提取从一个下标开始、另一个下标结束的子串 224

4.19.14　如何从给定字符串左部截掉指定个数的字符 225

4.19.15　如何从给定字符串右部截掉指定个数的字符 225

4.19.16　如何在字符串左部填充n个指定字符 225

4.19.17　如何在字符串右部填充n个指定字符 226

4.19.18　如何去除单词两边的空白 226

4.19.19　如何使用指定字符和对齐方式填充字符串 227

4.19.20　如何移除短语中的所有空格 228

4.19.21　如何对给定的k提取字符串的所有k-gram 228

4.19.22　如何检查字符串是否是有效的UPC代码 229

4.20　如何检查字符串是否是有效的ISBN 230

4.21　如何检查社会保险号（SIN）的有效性 231

4.22　如何检查给定的信用卡号码是否有效 232

4.23　如何将句子的大小写修改为正确的句子大小写 238

4.24　如何切换句子中字母的大小写 238

4.24.1　如何计算句子中给定单词的频率 239

4.24.2　如何显示给定句子的单词直方图 240

4.24.3 如何找到句子／短语／字符串中最常使用的单词 241

4.24.4　如何检查一个单词／短语是否是另一个单词／短语的变位词 241

4.25　如何得到给定单词的同音码 244

4.25.1 如何使用单词的语音码检查两个单词是否发音相同 246

练习题 246

编程题 247

第5章 递归 248

5.0　引言 248

5.1　递归的不同类型 248

5.2　递归的陷阱 248

5.3　斐波纳契数和黄金分割 249

5.4　使用递归的随机数生成器 252

5.5　如何使用von Numann中间平方法生成伪随机数（PRN） 254

5.6 如何生成Ackermann函数 257

5.7 什么是逆Ackermann函数 257

5.8　如何对给定变量生成TAK函数 257

5.9　使用递归求解非线性方程 262

5.10　使用递归的模式生成 271

5.11　如何编写一个递归函数生成帕斯卡三角形的数 274

5.12　帕斯卡三角形和斐波纳契数之间的关系是什么 275

5.13　如何编写一个递归函数得到Bell三角形的数。要接收两个数字，一个用于行，另一个用于列 276

5.14　Bell数的应用 277

5.15　如何编写一个递归函数生成Bernoulli三角形的数 277

5.16　如何编写一个递归函数生成Catalan三角形的数 278

5.17　生成Catalan数的递归关系是什么 279

5.18　使用Catalan数求解欧拉多边形剖分问题 280

5.19　DYCK路径和Catalan数 280

5.20　投票问题和Catalan数 281

5.21 如何编写一个递归函数生成Losanitsch三角形数 281

5.22　如何编写递归函数生成Leibnitz Harmonic三角形数 282

5.23　L-系统、递归以及更多分形 287

5.24　使用递归的分形生成 289

5.25　Koch曲线 289

5.26　Koch雪花 290

5.27 自然场景生成中的递归 290

概念复习 291

练习题 292

编程题 292

第6章　栈 294

6.0　引言 294

6.1 使用结构建立栈的模型 294

6.2　如何初始化上述模型建立的栈 294

6.3　如何从上述栈中弹出MRA元素 296

6.4　如何显示栈顶元素 296

6.5　如何交换栈顶的两个元素 297

6.6　使用数组的方法大汇总 297

6.7　使用链表建立栈的模型 299

6.8　入栈一个元素 299

6.9　如何从栈中出栈一个元素 300

6.10　如何窥视栈顶 301

6.11　如何交换栈顶两个元素 301

6.12　如何使用栈编写一个括号匹配器 306

6.13　开关箱布线问题 306

6.14　仙人掌栈 314

6.14.1　如何把数据项压入仙人掌栈 315

6.14.2　如何从仙人掌栈中弹出数据项 316

6.15　如何编写一个使用仙人掌栈检查错误输入URL的算法 316

6.16　什么是MTFL 321

6.17　如何使用两个栈建立MTFL模型，而这两个栈本身由链表建立 322

6.18　如何使用MTFL找出商店中最常被搜索的商品 326

6.19　什么是回溯法 327

6.20　如何使用栈开发一个找到迷宫中路径的回溯算法 328

概念复习 333

练习题 333

编程题 334

第7章 队列 336

7.0　引言 336

7.1　如何使用数组建立线性队列的模型 336

7.2　如何初始化上面定义的线性队列 336

7.3　如何在队列中添加一个元素 337

7.4　如何从队列中删除元素 338

7.5　如何在队列中搜索元素 340

7.6　如何显示队列中的元素 341

7.7　使用链表建立队列模型 341

7.8　如何在链表队列中添加一个数据项 342

7.8.1　如何得到队列中元素的个数 343

7.9　如何删除队列的队首数据项 344

7.10　如何搜索队列中的元素 344

7.11　如何显示队列元素 345

7.11.1 如何找到队列的队首元素 345

7.11.2　如何找到队列的队尾元素 345

7.12　使用两个栈建立线性队列的模型 347

7.13　如何使用两个队列建立栈的模型 349

7.14　使用结构建立循环队列的模型 350

7.14.1　如何初始化循环队列 351

7.14.2　如何把字符串添加到上面定义的循环队列中 351

7.14.3　如何删除循环队列的第一个字符串 351

7.14.4　如何在循环队列中搜索特定数据项 352

7.14.5　如何显示循环队列 352

7.15　使用数组建立优先队列模型 352

7.16　使用单向链表建立优先队列的模型 358

7.17　优先队列的一个应用 366

7.18　如何使用链表建立Deque（双端队列）的模型 374

7.19　如何使用队列建立移动到线性表首部（MTFL）的模型 374

7.20　如何模拟收银台前的队列 375

概念复习 380

练习题 381

编程题 381

第8章　树 383

8.0　引言 383

8.1　表示树的不同方法是什么 385

8.2　什么是严格二叉树 385

8.3　什么是准完全二叉树 385

8.4　什么是完全二叉树（又称完美二叉树） 385

8.5　什么是弱二叉树 386

8.6　什么是强二叉树 387

8.7　如何使用数组建立二叉树的模型 388

8.7.1　如何添加根的值 388

8.7.2　如何给结点添加一个左孩子 388

8.7.3　如何给结点添加一个右孩子 388

8.7.4　如何从左孩子找到父结点位置 388

8.7.5　如何从右孩子找到父结点位置 388

8.7.6　如何得到子结点是否是单独的结点 389

8.7.7　如何找到姐妹／兄弟的位置 389

8.7.8　如何得到结点在二叉树中的层次 389

8.7.9　如何得到二叉树的度数 390

8.7.10　如何在树中找到某个值的位置 390

8.7.11 如何计算树中结点的个数 390

8.7.12　如何得到结点孩子的个数 391

8.7.13　如何计算树中叶子的个数 391

8.7.14　如何得到有单个孩子的父结点的个数 391

8.7.15　如何得到结点左孩子的值 392

8.7.16　如何得到结点右孩子的值 392

8.7.17　如何检测结点是否有左孩子 392

8.7.18　如何判断结点是否是其父母的左孩子 392

8.8　如何判断结点是否是其父母的右孩子 393

8.8.1　如何判断结点是否有右结点 394

8.8.2　如何走到左孩子的位置 394

8.8.3　如何走到右孩子的位置 394

8.8.4　如何使用链表建立二叉树的模型 394

8.8.5　如何给任意结点添加左孩子 395

8.8.6　如何给任意结点添加右孩子 395

8.9　如何得到结点的兄弟结点的地址 395

8.10　如何得到结点叔叔的地址 396

8.11　如何以中序方式遍历树 396

8.11.1　如何以前序方式遍历树 396

8.11.2　如何以后序方式遍历树 396

8.11.3　如何计算二叉树中结点的个数 397

8.11.4　如何计算父结点拥有的孩子的个数 397

8.11.5　如何计算二叉树中内部结点的个数 397

8.11.6　如何计算二叉树中叶子的个数 398

8.11.7　如何检查两个二叉树是否相同 398

8.12　什么是二叉搜索树 398

8.12.1　如何向二叉搜索树添加元素 399

8.12.2　如何检查二叉树是否是二叉搜索树 400

8.13　如何在二叉搜索树中搜索值 400

8.13.1　如何从二叉搜索树中删除一个结点 401

8.14　什么是二叉搜索树的右旋转 402

8.14.1 如何绕着一个结点右旋转树一次 402

8.14.2　什么是二叉搜索树的左旋转 403

8.14.3　如何向左旋转树一次 403

8.15　二叉搜索树的一些应用领域 403

8.16　什么是表达式树 404

8.16.1　如何用二叉树表示表达式树 404

8.17　什么是决策树 409

8.18　二叉搜索树和对策 411

8.19　如何在这样的适应性测试中处理多个科目 414

8.20　如何把多叉树转换为二叉树 415

8.21　什么是二叉搜索树的平衡因子 416

8.21.1 如何得到二叉搜索树的平衡因子 417

8.21.2　如何检测二叉搜索树是否平衡 417

8.22　如何平衡二叉搜索树 418

8.22.1 自平衡二叉搜索树 418

8.22.2 自组织二叉搜索树： 418

8.23　什么是伸展树 418

8.23.1 如何在二叉搜索树上执行Zig操作 420

8.23.2　如何在二叉搜索树上执行Zag操作 420

8.24　什么是堆 421

8.25　创建堆的不同方法是什么 421

8.25.1 自项向下方法 421

8.25.2 自底向上方法 422

8.26　如何用数组实现二叉堆 422

8.27　什么是AVL树 422

8.28　如何在AVL树中插入元素 422

8.29　什么是BSP树 423

8.30　四元树 424

8.30.1　如何使用C结构建立四元树的模型 424

8.30.2　如何在这个四元树中添加一个东北方向的孩子 425

8.30.3 如何在这个四元树中添加一个西北方向的孩子 425

8.30.4　如何在这个四元树中添加一个东南方向的孩子 425

8.30.5　如何在这个四元树中添加一个西南方向的孩子 426

8.30.6　如何检测一个结点是否是另一个结点东北方向的孩子 426

8.30.7　如何检测一个结点是否是另一个结点西北方向的孩子 426

8.30.8　如何检测一个结点是否是另一个结点东南方向的孩子 426

8.30.9　如何检测一个结点是否是另一个结点西南方向的孩子 426

8.31 如何得到四元树结点的东北方向的叔叔 427

8.3 1.1 如何得到四元树结点的西北方向的叔叔 427

8.31.2　如何得到四元树结点的东南方向的叔叔 428

8.31.3　如何得到四元树结点的西南方向的叔叔 428

8.32　如何使用四元树表示图像 429

8.33　如何把四元树转换为二叉树 429

8.34　叠加使用二叉树表示的多个二值图像 430

8.35　使用四元树的手写体识别 432

8.36　如何使用四元树压缩图像 433

8.37　什么是八叉树 435

8.37.1 如何使用C结构建立八叉树的模型 435

8.37.2　如何给八叉树结点添加一个上邻居 436

8.37.3　如何给八叉树结点添加一个下邻居 436

8.37.4　如何给八叉树结点添加一个左邻居 436

8.38　什么是字典树 437

8.39　如何使用链表建立字典树的模型 437

8.40　如何向字典树中添加一个键 438

8.41　如何在字典树中搜索键 439

8.42　如何知道字典树中的键能否被删除 442

8.43　如何使用字典树进行拼法检查 443

概念复习 444

编程题 445

第9章 图 446

9.0　引言 446

9.1 表示图的不同方法是什么 446

9.2　如何在使用邻接矩阵建立模型的图中添加边 446

9.3　如何在使用邻接矩阵建立模型的图中删除边 447

9.4　什么是路径矩阵 447

9.4.1 如何检测两个结点之间是否存在一条路径 447

9.5　如何检测图是否是一棵树 448

9.6　什么是图的最小生成树 448

9.7　Prim算法 448

9.8　得到最小生成树的Kruskal算法 450

9.9　得到最小生成树的反向删除算法 451

9.9.1 如何使用Warshall算法得到最短路径 452

9.10　什么是有向无环图（DAG） 452

9.11　DAG的拓扑排序是什么 453

9.11.1　如何得到使用矩阵表示的两个图的并 454

9.11.2　如何得到使用矩阵表示的两个图的交 454

9.11.3　如何使用邻接表建立无向图的模型 454

9.11.4　如何在图中添加一个新结点 455

9.11.5　如何向图中添加一条新边 456

9.11.6　如何从图中软删除边 457

9.11.7　如何显示图的边 457

9.11.8　如何从图中软删除顶点 458

9.11.9　如何检测顶点是否出现在图中 458

9.11.10　如何检测边是否出现在图中 458

9.11.11　如何得到拥有绕其自循环的结点列表 459

9.11.12　如何得到图中结点的度数 459

9.11.13　如何检测结点是否孤立 460

9.11.14　什么是吊坠顶点，如何检测顶点是否是吊坠顶点 460

9.11.15　如何显示图 460

9.11.16　如何检测一个图的顶点是否是另一个图的顶点的子集 461

9.11.17　如何检测一个图的边是否是另一个图的边的子集 461

9.11.18　如何检测一个图是否是另一个图的子集 462

9.11.19　如何检测图是否是欧拉图 462

9.11.20　如何检测图是否是完全图 463

9.12　如何检测图是否是平面图 463

9.12.1 如何使用结构建立有向加权图的模型 463

9.12.2　如何向加权有向图上添加一条边 464

9.12.3　如何得到有向图结点的入度 465

9.12.4　如何得到有向图结点的出度 465

9.12.5　如何得到一对儿结点的并行边的条数 465

9.12.6　如何输出拥有并行路径的所有边 466

9.12.7　如何检测有向图是否平衡 466

9.12.8　如何检测有向图中边是否存在 466

9.12.9　如何检测有向图是否对称 467

9.12.10　如何检测边是否自循环 467

9.12.11 如何得到有向图中自循环的个数 467

9.12.12　如何检测有向图是否正则 467

9.13　宽度优先搜索 468

9.14　深度优先搜索 470

概念复习 470

练习题 471

编程题 471

第10章　排序 473

10.0　引言 473

10.1　本章中的函数 473

10.2　排序算法分类 473

10.3　交换排序算法 474

10.3.1　解释冒泡排序算法 474

10.4 冒泡排序的时间复杂度是什么 476

10.5　什么是奇偶移项排序 477

10.6　双向冒泡排序的时间复杂度是什么 480

10.7　组合排序的时间复杂度是什么 482

10.8　插入排序算法 483

10.9　插入排序的时间复杂度是什么 484

10.10　与理想（O（n2））曲线的比较 485

10.11　二叉插入排序的时间复杂度是什么 486

10.12　插入排序中存在的问题：移位 487

10.13　解释图书馆排序算法（又称间隙插入排序） 488

10.14　Shell排序的时间复杂度是什么 489

10.15　选择排序算法 490

10.16　选择排序的时间复杂度是什么 491

10.17　什么是Bingo排序 492

10.18　混合排序算法 492

10.19　什么是J-Sort排序 493

10.20　N分而治之算法 493

10.21 如何编写一个演示快速排序的函数 493

10.22　快速排序的时间复杂度是什么 494

10.23　快速排序中如何选择基准 494

10.24　合并排序的时间复杂度是什么 496

10.25　Stooge排序的时间复杂度是什么 497

10.26　分布排序算法 497

10.27　桶排序 497

10.28　具有O（n2）时间复杂度的排序算法的性能比较 498

10.29　具有O（n log n）时间复杂度的排序算法的性能比较 499

10.30　Bogo排序及其他 500

10.31　树排序 500

10.32　词典排序 501

10.33　基数排序 501

10.34　使用散列的地址计算排序 502

10.35　排序的应用 504

10.36　什么是聚类 504

10.37　商业集群 504

10.38　找出最短路径 504

10.39　找到城市中最热销的DVD 505

10.40　找出联机台球比赛中的最大联机得分 505

10.41　给定维度后找到最大形状 505

概念复习 505

练习题 506

编程题 507

第11章　散列 508

11.0　引言 508

11.1　冲突的概念及其解析 508

11.2　有关散列的一些关键事实和术语 510

11.2.1　如何演示整数的线性探查技巧 511

11.2.2　如何演示二次探查法 512

11.3　如何对散列表中散列元素演示分离链接方法 513

11.4　什么是混合散列 515

11.4.1　如何演示混合散列（链表散列） 516

11.4.2　如何从混合散列表中搜索数据项 519

11.5　混合散列（链表散列）的变体是什么 520

11.6　什么是散列链以及什么是它的OTP利用 520

11.6.1　如何演示散列链和OTP生成 520

11.7　如何使用散列树检查从P2P网络下载的媒体的完整性 522

练习题 523

编程题 523

第12章　ADT 524

12.1　黑箱的概念 524

12.2　ADT概述 524

12.3 C中ADT设计 525

12.4　设计你自己的ADT 525

练习题 527

编程题 527

第13章 日期 529

13.0　引言 529

13.0.1　如何检查年份是否是闰年 529

13.0.2　如何得到任意日期明天的日期 530

13.0.3　如何得到任意日期昨天的日期 532

13.0.4　如何计算同一年度两个日期之间的天数 534

13.1　如何得到星期几 534

13.2　如何从给定日期得到后第N个星期日的日期 538

13.3 如何从给定日期得到前第N个星期日的日期 539

13.4　包装函数：提高代码的可读性 540

13.4.1　如何得到前年特定日期是星期几 541

13.4.2　如何得到明年特定日期是星期几 541

13.4.3 如何得到下个月最后X天的日期 543

13.4.4　如何得到下个月前X天的日期 544

13.4.5　如何得到给定范围内所有闰年2月29日是星期几 544

13.4.6　如何得到一个日期相比于另一个日期是否是过去 545

13.4.7　如何检查两个日期是否相同 545

13.4.8　如何检查一个日期是否是另一个日期的将来 545

13.4.9　如何得到特定日期之后或之前一定天数的日期 546

13.4.10　如何得到特定日期之后或之前数月的日期 547

13.4.11　如何得到特定日期数年后或数年前的日期 547

13.5　与系统内置的Date结构交互 547

13.6　与现实世界交互 548

练习题 551

编程题 552

第14章　映射 554

14.0　引言 554

14.1　如何表示映射 554

14.1.1　如何在Buddy链表末尾添加一个Buddy 555

14.1.2　如何在Buddy链表首部添加一个Buddy 555

14.1.3　如何删除链表中的最后一个Buddy 555

14.1.4　如何删除链表中的第一个Buddy 556

14.1.5　如何在特定下标处删除Buddy／映射数据项 556

14.1.6　如何删除一个范围内的Buddy／映射数据项 557

14.1.7　如何隔一项删除一项Buddy／映射数据项 557

14.1.8　如何在Buddy链表／映射中得到第一个朋友／数据项 558

14.1.9　如何在Buddy链表／映射中得到最后一个朋友／数据项 558

14.1.10　如何计算链表中伙伴的个数 558

14.1.11　如何替换映射中特定数据项 559

14.1.12 如何对换映射中两个不同位置上元素的内容 559

14.1.13　如何对换映射的首部和尾部 559

14.2　如何在映射上定义谓词并从客户端使用它 560

14.3　如何从Buddy链表中知道谁是谁的朋友 560

14.4　如何使用映射设计一个随机加密编码器 561

14.5　映射之映射的应用 562

14.6　多语言单词映射 563

14.7　键互联映射（KIM） 564

练习题 564

编程题 565

第15章　货币 566

15.0　引言 566

15.0.1 如何使用结构建立USD货币 566

15.0.2　如何加两个USD金额 566

15.0.3　如何把字符串转换为相应的USD金额 567

15.0.4　如何检查两个USD金额是否相等 569

15.0.5　如何检查一个USD是否大于另一个USD 569

15.0.6　如何检查一个USD是否小于另一个USD 570

15.0.7　如何用结构建立GBP货币模型 570

15.0.8　如何用结构建立欧元货币模型 570

15.0.9　如何从提供的一系列金额中得到最大USD金额 571

15.0.10　如何从提供的一系列金额中得到最小USD金额 571

15.1 实际应用：得到最低投标金额 572

15.2　如何把USD转换为GBP，或进行相反转换 573

15.3　如何按日将USD转换为GBP，或进行相反的转换 574

练习题 575

编程题 575

第16章　文件处理 576

16.0　引言 576

16.1　什么是文件 576

16.2　函数rewind（）干什么 580

16.2.1 如何编写函数wcl（）计算文件的行数 580

16.2.2　如何编写函数wcw（）计算文件的单词个数 581

16.2.3　如何编写函数wcc（）计算文件的字符个数 581

16.2.4　如何编写一个使用这三个函数的客户端代码函数 582

16.2.5　如何模拟UNIX head命令 582

16.2.6　如何模拟UNIX tail命令 583

16.3　如何模拟UNIX cat命令 585

16.4　如何模拟精确匹配的UNIX grep命令 586

16.5 如何模拟UNIX Grep命令的-V开关 587

16.5.1 如何输出文本文件中包含以给定前缀开始的单词的那些文本行 588

16.5.2　如何输出文本文件中包含以给定后缀结束的单词的那些文本行 589

16.5.3　如何输出文本文件中不包含以给定前缀开始的单词的那些文本行 590

16.5.4　如何输出文本文件中不包含以给定后缀结束的单词的那些文本行 591

16.5.5　如何输出文本中的这些行，它包含了匹配使用星号通配符表示的特定模式的单词或短语 591

16.6　如何输出文件中的那些行，它包含了发音类似于给定单词的单词 593

16.7　如何使用一个字符取代文件中的另一个字符 593

16.8　如何使用一个单词替换文件中的另一个单词 595

16.9　如何逐行比较两个文本文件 596

16.10　如何输出两个文件的相同行 597

16.11　如何把文件从源复制到目标 598

16.12　控制台游戏中的文件处理 621

16.13　函数定义 632

练习题 637

编程题 638

附录A　项目概念 640

概念＃1：确定一个集合 640

概念＃2：ATM 640

概念＃3：行编辑器 640

概念＃4：POS机完全定制化 641

概念＃5：使用少量的SQL支持定制地址本 641

概念＃6：创建幻方 641

概念＃7：剽窃探测 642

概念＃8：动态自适应测验系统（DAQS） 643

概念＃9：简单英语到C代码生成器（SETCOGEN） 643

概念＃10：检测作者的性别（DAG） 643

附录B　参考文献 645