算法大视界/魏振钢

― 目 录 ―

第1章 绪论 / 1
1．1 何为算法 / 1
1．2 算法的特性 / 3
1．3 “敲7”游戏 / 4
1．3．1 数据元素 / 4
1．3．2 数据的逻辑结构 / 5
1．3．3 数据的存储结构 / 6
1．3．4 线性表的删除 / 7
1．3．5 “敲7”游戏的算法
设计 / 9
1．4 计算机求解问题的基本
步骤 / 10
1．5 总结与思考 / 11
第2章 《三体》在哪里 / 12
2．1 怎样找到《三体》
这本书 / 12
2．2 线性表的定义及表示 / 14
2．2．1 类型定义 / 14
2．2．2 线性表的顺序表示和实现 / 17
2．2．3 线性链表 / 20
2．2．4 循环链表 / 27
2．3 查找的定义 / 28
2．3．1 概念与术语 / 28
2．3．2 顺序表的查找 / 29
2．3．3 有序表的查找 / 33
2．4 如何查找《三体》
这本书 / 37
2．4．1 问题分析 / 37
2．4．2 算法设计 / 37
2．5 如何找到“小明” / 38
2．5．1 问题描述 / 38
2．5．2 问题分析 / 39
2．6 总结与思考 / 39
第3章 奖学金争先 / 41
3．1 谁能拿到奖学金 / 41
3．2 常用排序方法介绍 / 42
3．2．1 概述 / 42
3．2．2 直接插入排序 / 43
3．2．3 起泡排序 / 46
3．2．4 快速排序 / 49
3．2．5 简单选择排序 / 51
3．3 奖学金竞争问题的
求解 / 53
3．3．1 问题分析 / 53
3．3．2 算法分析 / 53
3．3．3 算法设计 / 54
3．4 应用 / 55
3．4．1 荷兰国旗问题 / 55
3．4．2 货箱移动问题 / 57
3．5 总结与思考 / 58
第4章 网上冲浪 / 59
4．1 “Web导航”问题 / 59
4．1．1 问题描述 / 59
4．1．2 问题分析 / 61
4．2 什么是“栈” / 62
4．2．1 栈的定义 / 62
4．2．2 栈的顺序表示和
实现 / 64
4．2．3 栈的应用举例 / 64
4．2．4 生活中的栈 / 67
4．3 如何实现“Web导航” / 69
4．3．1 问题分析 / 69
4．3．2 算法设计 / 71
4．4 列车调度问题 / 73
4．4．1 问题描述 / 73
4．4．2 问题分析 / 73
4．4．3 算法设计 / 74
4．5 总结与思考 / 75
第5章 “汉诺塔”的智慧 / 77
5．1 “汉诺塔”问题 / 77
5．1．1 问题描述 / 77
5．1．2 问题分析 / 78
5．2 递归的基本概念与
应用 / 81
5．2．1 递归 / 81
5．2．2 递归函数 / 82
5．3 “汉诺塔”问题求解 / 83
5．3．1 问题分析 / 83
5．3．2 算法设计 / 84
5．4 应用 / 85
5．4．1 八皇后问题 / 85
5．4．2 快速排序 / 88
5．4．3 分苹果问题 / 88
5．5 总结与思考 / 89
第6章 舞伴的选择 / 91
6．1 舞伴组合 / 91
6．1．1 问题描述 / 91
6．1．2 问题分析 / 91
6．2 队列 / 92
6．2．1 队列的抽象数据类型定义 / 92
6．2．2 队列的基本
操作 / 93
6．2．3 生活中的队列 / 94
6．3 舞伴组合问题求解 / 95
6．3．1 算法分析 / 95
6．3．2 算法设计 / 95
6．3．3 算法设计 / 97
6．4 消息的加密和解密 / 98
6．4．1 问题描述 / 98
6．4．2 问题分析 / 98
6．4．3 算法设计 / 99
6．5 总结与思考 / 99
第7章 爱的密码 / 101
7．1 如何传输“I LOVE
YOU” / 101
7．1．1 问题描述 / 101
7．1．2 问题分析 / 101
7．2 树及二叉树 / 102
7．2．1 树的定义 / 102
7．2．2 二叉树 / 104
7．3 哈夫曼树及其哈夫曼
编码 / 110
7．3．1 哈夫曼树 / 110
7．3．2 哈夫曼编码 / 113
7．3．3 传输“I LOVE YOU”的解决方案 / 114
7．4 农夫锯木板问题 / 117
7．4．1 问题描述 / 117
7．4．2 算法分析 / 117
7．4．3 算法设计 / 117
7．5 总结与思考 / 118
第8章 众里寻他千百度 / 120
8．1 微信通讯录 / 120
8．2 动态查找表 / 121
8．2．1 二叉排序树 / 121
8．2．2 平衡二叉树 / 127
8．2．3 B-树和B+树 / 129
8．3 哈希表 / 132
8．3．1 哈希表的定义 / 132
8．3．2 哈希表的查找 / 134
8．3．3 哈希表的应用 / 134
8．4 电话通讯录的实现 / 134
8．4．1 问题描述 / 134
8．4．2 问题分析 / 135
8．5 总结与思考 / 139
第9章 城市互连 / 140
9．1 城市公路连接问题 / 140
9．1．1 问题描述 / 140
9．1．2 问题分析 / 141
9．2 图的基本知识 / 141
9．2．1 图的定义和
术语 / 141
9．2．2 图的存储结构 / 144
9．3 *小生成树的求解 / 148
9．3．1 普里姆算法 / 148
9．3．2 克鲁斯卡尔
算法 / 152
9．4 城市公路连接问题的
求解 / 153
9．5 应城市之间的通信线路网建设问题 / 154
9．5．1 问题描述 / 154
9．5．2 问题分析 / 154
9．6 总结与思考 / 154
第10章 地图导航 / 155
10．1 如何去罗马 / 156
10．1．1 问题描述 / 156
10．1．2 问题分析 / 156
10．2 如何求解*短路径 / 157
10．2．1 从某个源点到
其余各顶点的*
短路径 / 157
10．2．2 每对顶点之间的
*短路径 / 160
10．3 如何实现去罗马 / 163
10．4 校园导航 / 163
10．4．1 问题描述 / 163
10．4．2 问题分析 / 164
10．4．3 算法设计 / 164
10．5 总结与思考 / 167
参考文献 / 169