数据结构与算法详解

目　录


第　一部分 数据结构

第0章　基础知识　2
0．1　基本概念和术语　2
0．2　数据的逻辑结构与存储结构　3
0．2．1　逻辑结构　3
0．2．2　存储结构　4
0．3　抽象数据类型及其描述　5
0．3．1　什么是抽象数据类型　5
0．3．2　抽象数据类型的描述　5
0．4　算法　5
0．4．1　数据结构与算法的关系　6
0．4．2　什么是算法　6
0．4．3　算法的五大特性　6
0．4．4　算法的描述　6
0．5　算法分析　7
0．5．1　算法设计的4个目标　7
0．5．2　算法的时间复杂度　7
0．5．3　算法的空间复杂度　9
第　1章 线性表　10
1．1　顺序表及其应用　10
1．1．1　将两个有序的线性表合并
为一个有序的线性表　13
1．1．2　将两个无序的线性表合并
为一个线性表　16
1．1．3　求两个线性表的差集　18
1．1．4　分解顺序表，使左边的
元素小于或等于0，右边的
大于0　19
1．1．5　求两个任意长度的整数
之和　21
1．1．6　求两个元素序列的
中位数　23
1．2　单链表及其应用　25
1．2．1　逆置单链表　30
1．2．2　求两个单链表的差集　34
1．2．3　合并两个单链表　37
1．2．4　找出单链表表示的两个单词
共同后缀起始地址　40
1．2．5　找出单链表中倒数第k个
位置上的节点　42
1．3　循环单链表及其应用　44
1．3．1　分解一个循环单链表为
两个循环单链表　44
1．3．2　构造3个循环单链表　47
1．3．3　约瑟夫问题　50
1．4　双向链表及其应用　53
1．4．1　双向链表的创建与插入
操作　55
1．4．2　约瑟夫问题（双向链表）　58
1．5　线性表的典型应用　60
1．5．1　将两个一元多项式相加　60
1．5．2　将两个一元多项式相乘　65
第　2章 栈　71
2．1　顺序栈及其应用　71
2．1．1　将元素分别入栈和出栈　73
2．1．2　共享栈的入栈和出栈操作　75
2．1．3　求C (n，m)的值　78
2．1．4　求Ackermann(m，n)的值　80
2．2　链栈及其应用　83
2．2．1　将十进制数转换为
八进制数　86
2．2．2　检查表达式中的括号
是否匹配　88
2．2．3　求算术表达式的值　90
2．2．4　判断字符串是否中心
对称　96
第3章　队列　98
3．1　顺序队列及其应用　98
3．1．1　将顺序循环队列中的元素
分别入队和出队　101
3．1．2　舞伴配对　104
3．1．3　模拟轮渡管理　106
3．2　链式队列及其应用　108
3．2．1　队列在杨辉三角中的
应用　111
3．2．2　判断字符串是否为回文　114
3．3　栈和队列的综合应用──停车场
管理　116
第4章　串　126
4．1　顺序串及其应用　126
4．1．1　利用串的基本运算进行
赋值、插入和删除等操作　130
4．1．2　将浮点数转换为对应的串　134
4．1．3　求*长公共子串　135
4．1．4　求等值子串　137
4．1．5　将长度为5的单词转换为
大写形式　138
4．1．6　将小写字母a左、右两边的
串互换　140
4．2　串的模式匹配　142
第5章　数组　149
5．1　一维数组及其应用　149
5．1．1　查找第k小元素　150
5．1．2　将奇数移动到偶数的
左边　151
5．2　二维数组（矩阵）及其应用　153
5．2．1　输出魔方阵　153
5．2．2　输出内螺旋矩阵　155
5．2．3　输出逆螺旋矩阵　156
5．2．4　输出外螺旋矩阵　158
5．2．5　输出蛇形方阵　159
5．2．6　输出折叠方阵　161
5．3　特殊矩阵的压缩存储及其应用　162
5．4　稀疏矩阵的压缩存储及其应用　166
第6章　广义表　172
6．1　头尾链表表示的广义表及其
应用　172
6．2　扩展线性链表表示的广义表
及其应用　178
6．3　广义表的综合应用——导师-学生
制管理　181
第7章　树　187
7．1　树的表示及创建二叉树　187
7．1．1　采用广义表创建二叉树　194
7．1．2　创建二叉树　196
7．2　二叉树的遍历　199
7．2．1　非递归先序遍历二叉树　205
7．2．2　按层次遍历二叉树　207
7．2．3　由中序和后序序列构造
二叉树　209
7．2．4　输出树的各条边　212
7．3　二叉树的应用　214
7．3．1　求树中节点的个数　214
7．3．2　交换二叉树的左右子树　216
7．3．3　判断二叉树是否为完全
二叉树　219
7．3．4　计算二叉树的高度和*大
宽度　223
7．3．5　求树中根节点到任意节点
之间的路径　226
7．4　哈夫曼树　230
第8章　图　235
8．1　图的表示及应用　235
8．1．1　利用邻接矩阵创建
有向网　238
8．1．2　利用邻接表创建有向图　241
8．1．3　把图的邻接矩阵表示
转换为邻接表表示　244
8．2　图的遍历　248
8．2．1　判断有向图中是否存在
回路　249
8．2．2　深度优先搜索遍历
无向图　251
8．2．3　图的广度优先搜索遍历　254
8．2．4　判断有向图中是否有根
顶点　258
8．2．5　求距离顶点v0的*短路径
长度为k的所有顶点　261
8．2．6　判断顶点u和顶点v之间
是否存在简单路径　265
8．2．7　判断无向图是否为一棵树　269

第二部分　算 法

第9章　查找算法　274
9．1　与查找算法相关的概念　274
9．2　基于线性表的查找　275
9．2．1　顺序查找　275
9．2．2　折半查找　276
9．2．3　分块查找　279
9．3　基于树的查找　281
9．4　哈希表的查找　285
第　10章 排序算法　290
10．1　排序的基本概念　290
10．2　插入排序　291
10．2．1　直接插入排序　291
10．2．2　折半插入排序　293
10．2．3　希尔排序　296
10．3　交换排序　298
10．3．1　冒泡排序　298
10．3．2　快速排序　302
10．4　选择排序　305
10．4．1　简单选择排序　305
10．4．2　堆排序　308
10．5　归并排序　313
10．6　基数排序　316
第　11章 递推算法　324
11．1　顺推法　324
11．1．1　斐波那契数列　324
11．1．2　角谷猜想　327
11．1．3　将十进制整数转换为
二进制整数　328
11．1．4　将十进制浮点数转换为
二进制数　329
11．1．5　母牛生小牛问题　330
11．1．6　输出杨辉三角　332
11．1．7　质因数分解　333
11．1．8　求*大公约数和*小公
倍数　333
11．2　逆推法　334
11．2．1　猴子摘桃　334
11．2．2　存钱问题　335
第　12章 递归算法　337
12．1　简单递归　337
12．1．1　求n的阶乘　337
12．1．2　斐波那契数列　340
12．1．3　求n个元素中的*大者　341
12．1．4　求n个数的和　342
12．1．5　将十进制整数转换为
二进制整数　343
12．1．6　求整数的逆序数　344
12．1．7　求*大公约数　345
12．1．8　求Ackermann函数的值　346
12．1．9　求C (n，m)的值　347
12．2　复杂递归　348
12．2．1　逆置字符串　348
12．2．2　求*大和次大元素　349
12．2．3　求无序序列中第k大的
元素　351
12．2．4　和式分解　352
12．2．5　台阶问题　354
12．2．6　汉诺塔问题　356
12．2．7　大牛生小牛问题　358
12．2．8　从自然数1～n中任选r
个数的所有组合数　359
第　13章 枚举算法　361
13．1　判断n是否能被3、5、7整除　361
13．2　百钱买百鸡　363
13．3　五猴分桃　364
13．4　输出“水仙花数”　366
13．5　Mary的借书方案　367
13．6　整币换零　368
13．7　填数游戏　369
13．8　谁在说谎　371
13．9　求*大连续子序列和　372
13．10　0/1背包问题　373
第　14章 贪心算法　376
14．1　贪心算法的基础　376
14．1．1　贪心算法的基本思想　376
14．1．2　贪心选择性质　376
14．1．3　贪心算法的求解步骤　376
14．2　找零钱问题　377
14．3　会议安排问题　378
14．4　*优装载问题　381
14．5　哈夫曼编码　383
14．6　加油点问题　387
14．7　背包问题　389
第　15章 回溯算法　392
15．1　回溯算法的基础　392
15．1．1　回溯算法的解空间　392
15．1．2　回溯算法的搜索　393
15．2　求自然数1～n中r个数的所有
组合　394
15．3　填字游戏　395
15．4　和式分解（非递归实现）　399
15．5　装箱问题　401
15．6　0/1背包问题　404
第　16章 数值算法　408
16．1　求实数的平方根　408
16．2　利用二分法求方程的根　409
16．3　利用牛顿迭代法求方程的根　411
16．4　利用高斯消元法求解线性方程组　413
16．5　利用梯形法求定积分　416
16．6　计算π的近似值　418
第　17章 实用算法　421
17．1　阿拉伯数字/中文大写金额的
转换　421
17．2　将15位身份证号转换为18位　424
17．3　计算7的34次方　426
17．4　计算某年某月某日是一年中的
第几天　427
17．5　大整数相乘　428
17．6　输出万年历　430
17．7　求两个正整数的差　434
17．8　利用二叉树结构计算算术
表达式的值　436
第　18章 常见错误与程序调试技术　439
18．1　常见错误　439
18．1．1　错误分类　439
18．1．2　常见错误举例　440
18．2　程序调试　444
18．2．1　Visual C++ 6．0开发
环境中程序的调试　444
18．2．2　程序调试应用举例　451
18．3　小结　462