算法大视界

本书以"问题驱动”为导向，结合数据结构课程知识的精华内容，通过学生对日常学习、生活中遇到的典型问题和案例的分析、讨论，引导学生了解数据结构的相关知识，培养学生对算法设计和分析的兴趣，帮助学生了解"计算思维”的内涵及本质，提高学生"IT”职业素养和分析能力。 本书共10章，内容涉及线性表、堆栈、队列、查找、排序、二叉树、图等数据结构的基础知识。在内容组织上，打破传统数据结构教材的编排顺序，将需要解决的问题作为主线。除第1章绪论外，其余9章均以一个具体问题为引导，然后针对该问题展开，对相关知识进行介绍。例如，第3章奖学金争先，通过学生奖学金的计算及发放问题，对排序的相关知识进行介绍；第4章网上冲浪，根据浏览器的浏览操作原理，对堆栈及相关知识进行介绍。这样容易吸引学生的兴趣和注意力，使学习不再枯燥。 本书可作为高校相关通识课程的参考教材，也可以作为中小学生信息技术类的课外读物。

本书以"问题驱动”为导向，结合数据结构课程知识的精华内容，通过学生对日常学习、生活中遇到的典型问题和案例的分析、讨论，引导学生了解数据结构的相关知识，培养学生对算法设计和分析的兴趣，帮助学生了解"计算思维”的内涵及本质，提高学生"IT”职业素养和分析能力。 本书共10章，内容涉及线性表、堆栈、队列、查找、排序、二叉树、图等数据结构的基础知识。在内容组织上，打破传统数据结构教材的编排顺序，将需要解决的问题作为主线。除第1章绪论外，其余9章均以一个具体问题为引导，然后针对该问题展开，对相关知识进行介绍。例如，第3章奖学金争先，通过学生奖学金的计算及发放问题，对排序的相关知识进行介绍；第4章网上冲浪，根据浏览器的浏览操作原理，对堆栈及相关知识进行介绍。这样容易吸引学生的兴趣和注意力，使学习不再枯燥。 本书可作为高校相关通识课程的参考教材，也可以作为中小学生信息技术类的课外读物。

魏振钢，男，教授，1984年6月毕业于山东大学计算机专业，1980.7—1986.6，山东大学讲师，1986.6—至今，中国海洋大学教授，兼任信息化教学中心主任。任全国高校计算机教育研究会理事，中国体育学会信息分会常务理事，青岛计算机学会常务理事。曾获得中国海洋大学教学名师，青岛市教学名师，*-英特尔精品课程、山东精品课程《数据结构》负责人，*-IBM精品课程《软件工程》负责人。先后主持国家自然科学基金1项，省级自然科学基金1项，主编教材1部，出版教材名称：《数据结构》，出版社：高等教育出版社，出版时间：2011年2月。

— 目 录 — 

第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

本书以"问题驱动”为导向，结合数据结构课程知识的精华内容，通过学生对日常学习、生活中遇到的典型问题和案例的分析、讨论，引导学生了解数据结构的相关知识，培养学生对算法设计和分析的兴趣，帮助学生了解"计算思维”的内涵及本质，提高学生"IT”职业素养和分析能力。 本书共10章，内容涉及线性表、堆栈、队列、查找、排序、二叉树、图等数据结构的基础知识。在内容组织上，打破传统数据结构教材的编排顺序，将需要解决的问题作为主线。除第1章绪论外，其余9章均以一个具体问题为引导，然后针对该问题展开，对相关知识进行介绍。例如，第3章奖学金争先，通过学生奖学金的计算及发放问题，对排序的相关知识进行介绍；第4章网上冲浪，根据浏览器的浏览操作原理，对堆栈及相关知识进行介绍。这样容易吸引学生的兴趣和注意力，使学习不再枯燥。 本书可作为高校相关通识课程的参考教材，也可以作为中小学生信息技术类的课外读物。

魏振钢，男，教授，1984年6月毕业于山东大学计算机专业，1980.7—1986.6，山东大学讲师，1986.6—至今，中国海洋大学教授，兼任信息化教学中心主任。任全国高校计算机教育研究会理事，中国体育学会信息分会常务理事，青岛计算机学会常务理事。曾获得中国海洋大学教学名师，青岛市教学名师，*-英特尔精品课程、山东精品课程《数据结构》负责人，*-IBM精品课程《软件工程》负责人。先后主持国家自然科学基金1项，省级自然科学基金1项，主编教材1部，出版教材名称：《数据结构》，出版社：高等教育出版社，出版时间：2011年2月。