图书简介:
— 目 录 —
第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
展开
前 言 —
时隔两年多的时间,《算法大视界》一书终于和大家见面了。本书是作者本人在中国海洋大学面向全校非计算机类专业所开设的通识课程“算法大视界”的配套教材。为什么要开设这样一门课程?它的目标是什么?
1.开课背景
本人在中国海洋大学长期从事“数据结构”课程的教学工作,该课程先后被评为山东省省级精品课、教育部?英特尔精品课。其慕课课程在“智慧树”平台运行多年,先后有一百多所高校将其作为学分课程选用,累计选课学生过万,深受选课学校欢迎,入选“智慧树”双一流高校专业课TOP100。“智慧树”平台相关负责老师一直希望本人在平台上开设一门与“数据结构”相关的通识课程,让更多的学校和学生受益。中国海洋大学于2017年启动了“通识教育再启航”的教学创新,其中的“科学与技术”板块希望有更多的理工类通识课程出现,教务处领导也希望并鼓励本人能够为海大学生开设一门以“数据结构”知识为背景的通识课程。另外,随着信息技术的飞速发展,以人工智能、大数据、云计算等为代表的计算机技术迎面扑来,众多非计算机类专业的学生也希望对这些知识和技术有所了解。在此背景下,本课程及配套教材应运而生。
2.课程及教材的目标及内容体系
在构思课程及教材的目标和内容体系时,主要考虑了以下几个方面的因素。
(1)IT技术飞速发展,移动智能终端的普及,“互联网+”背景下的各种应用,其所蕴含的软件技术基础是什么?
(2)“计算思维”的内涵及本质是什么?伴随着互联网成长的当代大学生应该具有什么样的“IT”职业素养和知识能力?
(3)目前国家对中小学生的信息技术教育也在从简单的操作层面向算法及程序设计层面转型,希望在“计算思维”的培养方面有所体现。本教材也可以作为中小学生的信息技术类的课外读物。
基于以上几点,我们从“数据结构”课程知识中提取精华,结合大家现在经常用到的移动智能设备当中的一些基本的功能,演化出本课程及教材的目标和内容体系。目标可以总结为以下两点:
(1)“问题驱动”为导向。通过对日常学习、生活中遇到的典型问题和案例的分析、讨论,引导学生了解“数据结构”的相关知识,培养学生对算法设计和分析的兴趣。例如,手机导航、微信通讯录、浏览器浏览等基本原理。
(2)通过学习,培养和提升学生的计算思维能力,提高学生解决实际问题的能力。
本书共10章。除第1章绪论外,其余9章均以一个具体问题为题,展开相关知识的介绍。例如,第3章奖学金争先,通过学生奖学金的计算及发放问题,对排序相关知识进行介绍;第4章网上冲浪,通过浏览器的浏览操作原理,对堆栈及相关知识进行介绍。这些案例及问题,都是学生身边所发生的或经常接触和操作的事情,容易激发学生的兴趣和提高注意力,使学习不再枯燥。
“算法大视界”由中国海洋大学计算机专业在校学生命名,寓意是“对数据结构有一定了解会为我们将来找工作提供更多的帮助,是个人视野、想法的体现,采用世界的谐音,其意味深远”。
“算法大视界”课程的开课以及相应教材的出版,是多位朋友、同事及合作伙伴共同努力的结果。在这里首先要感谢“智慧树”在线教学平台的董事长葛新女士和中国海洋大学教务处处长方奇志教授,是她们的引导、启发和鼓励,才有了这门课程和相应教材;其次要感谢我的同事高云博士、智慧树中国海洋大学崇本课栈的乔旭和张静,是她们和我共同策划了课程的主要内容及章节结构;然后还要感谢中国海洋大学计算机专业2016级学生李晓宇、王会金、魏家琪、廖舒淇、马小兰、李旭梅,由他们共同为本课程命名;最后要感谢智慧树中国海洋大学崇本课栈的陈秀英、国拯,以及我的研究生康婷婷、李飞帆、刘畅和姬晓飞,在授课视频录制、资料和初稿的整理等方面,做了大量的工作;还要感谢电子工业出版社的孟宇编辑,她对本书的编写等事宜,提出了很多指导建议。由于作者水平有限,书中不完善之处甚至错误在所难免,恳请读者批评指正。
魏振钢
2020年10月
展开