数据结构和算法基础（Java语言实现）读后感锦集
《数据结构和算法基础（Java语言实现）》是一本由柳伟卫著作，北京大学出版社出版的平装图书，本书定价：119，页数：582，特精心从网络上整理的一些读者的读后感，希望对大家能有帮助。
《数据结构和算法基础（Java语言实现）》读后感(一)：《数据结构和算法基础（Java语言实现）》介绍
《数据结构和算法基础（Java语言实现）》一书由北京大学出版社出版，已经于近日上市。拿到了样书，第一时间希望与读者朋友们分享下这本书里面的内容。
12月6日拿到了样书，迫不及待的对新书做了浏览。同时也做了拆书与导读，可以在B站找到：https://www.bilibili.com/video/BV1fY411s7Kr/
聊下为啥要写这本书。
其实，这本是我所编写过的书目（https://waylau.com/books/）里面，算是最为“低级”的课题了吧，毕竟谁不知道“数据结构和算法”呢？这个课题太基础了。
但是“数据结构和算法”却又是非常重要的课程。算法和数据结构是程序的灵魂，在计算机类培训课程中属于必开的课程。虽然实际工作中大多数人并不是专业的算法工程师，不以算法为深，但不可否认算法在工作中的重要性，初级工程师与高级工程师的差距也许就在对于算法的理解上。理解算法，运用合理的数据结构，可以让程序更加高效。
随着云计算、大数据、人工智能、虚拟现实等应用的兴起，企业对于开发人员的算法技术要求也越来越高。不会算法或不精通算法，也许就会错过很多就业良机。另外，在求职时，算法是面试的必考类型。
鉴于算法和数据结构在编程中的重要性，笔者迫不及待地希望将工作中常用的算法介绍给大家。因此，笔者陆续在个人开源网站https://github.com/waylau/java-data-structures-and-algorithms-in-action上发表了众多关于算法的技术博客>。2020年年底，笔者将之前算法相关的个人博客整理成册，遂有了本书。
概况起来，这本《数据结构和算法基础（Java语言实现）》主要有三大特点。B站也有相关介绍：https://www.bilibili.com/video/BV1Lg411P7LP/
那么涉及广的话可以体现在哪里呢？可以看这本书的内容简介部分。
该书分为以下几部分：
可以说，基本上你常见的一些是业务上还是技术常用的一些数据结构和算法，这本书都已经涉及了。更难能可贵的是，这本书也对当前非常火爆的诸如AI、机器学习等算法也做了讲解。
这本书是他这个图例非常丰富，从基本的IDE安装，到复杂的数据结构的演示，都有丰富的图例。那么在讲这种数据结构或者算法理论的时候，通过图例的配套讲解演示，可以方便读者理解。
第三个特点的话就是它里面的实战案例非常丰富。实战案例体现在，这本书的每一章每个知识点基本上会配套一个实战案例，代码量是非常大的。每行代码这个重点代码它都有一些注释给你写得明明白白。
这本书呢是不单只是简单的讲一些理论，它还有会手把手的教你写代码。理论联系实际。
学习本书，一起手撕算法！参考引用原本同步至：https://waylau.com/java-data-structures-and-algorithms-in-action-book-three-features/京东有售：https://item.jd.com/13014179.html
《数据结构和算法基础（Java语言实现）》读后感(二)：分析算法和数据结构的重要工具——渐近记法
本节是《Java数据结构及算法实战》系列的第5节，主要介绍分析算法和数据结构的重要工具——渐近记法。
在前一节，我们介绍了程序的性能，也介绍了评估性能的方式。那么，我们是否就能测算出算法需要运行的时间呢？
直接回答上述问题并非易事，原因在于，即使是同一算法，针对不同的输入运行的时间并不相同。以排序问题为例，输入序列的规模、组成和次序都不是确定的，这些因素都会影响到排序算法的运行时间。在所有这些因素中，输入的规模是最重要的一个。假设我们要对学生按照成绩排序，那么显然，当学生的规模很少时（比如50个）所耗费的排序时间，肯定是要比当学生的规模很大时（比如50万个）所耗费的排序时间短。
因此，在实际分析算法的时间复杂度时，通常只考虑输入规模这一主要因素。如果将某一算法为了处理规模为n的问题所需的时间记作T(n)，那么随着问题规模n的增长，运行时间T(n)我们将称之为算法的时间复杂度。
由于小规模的问题所需的处理时间相对更少，不同算法在效率方面的差异并不明显，而只有在处理大规模的问题时，这方面的差异才有质的区别。因此，在评价算法的运行时间时，我们往往可以忽略其在处理小规模问题时的性能，转而关注其在处理足够大规模问题时的性能，即所谓的渐进复杂度（Asmpototic Complexity）。
另外，通常我们也不需要知道T(n)的确切大小，而只需要对其上界作出估计。比如说，如果存在正常数a、N和一个函数f(n)，使得对于任何n > N，都有
T(n) < a × f(n)
我们就可以认为在n足够大之后，f(n)给出了T(n)的一个上界。对于这种情况，我们记之为
T(n) = O(f(n))
这里的O称作“大O记号（Big-O notation）”，是希腊字母omicron的大写形式。从上述例子可以看出，大O记号实质上是对算法执行效率的一种保守估计⎯⎯对于规模为n的任意输入，算法的运行时间都不会超过O(f(n))。换言之，大O记号是对算法执行效率最差情况的估算。
大O记号是渐进记法的一种。渐进记法一直就是人们用于分析算法和数据结构的重要工具。其核心思想是：提供一种资源表示形式，主要用于分析某项功能在应对一定规模参数时需要的资源（通常是时间，有时候也会是内存）。常用的渐进记法还包括大Θ记号、大Ω记号。
如果存在正常数a、N和一个函数g(n)，使得对于任何n>N，都有
T(n) > a × g(n)
我们就可以认为在n足够大之后，g(n)给出了T(n)的一个下界。对于这种情况，我们记之为
T(n) = Ω(g(n))
这里的Ω称作“大Ω记号（Big-Ω notation）”，是希腊字母omega的大写形式。大Ω记号与大O记号正好相反，它是对算法执行效率的一种乐观估计⎯⎯对于规模为n的任意输入，算法的运行时间都不会低于Ω(g(n))。换言之，大O记号是对算法执行效率最好情况的估算。
如果存在正常数a<b、N和一个函数h(n)，使得对于任何n > N，都有
a × h(n) < T(n) < b × h(n)
我们就可以认为在n足够大之后，h(n)给出了T(n)的一个确界。对于这种情况，我们记之为
T(n) = Θ(h(n))
这里的Θ称作“大Θ记号（Big-Θ notation）”，是希腊字母theta的大写形式。大Θ记号是对算法执行效率的一种准确估计⎯⎯对于规模为n的任意输入，算法的运行时间都与Θ(h(n))同阶。
总结而言，渐近记法的含义如下表1-2所示。
表1-2 渐近记法含义
符号含义O渐进小于或等于Ω渐进大于或等于Θ渐进等于
在上面度量算法复杂度的三种记号中，大O记号是最基本的，也是最常用到的。本书后续的算法复杂度也主要采用按照大O记号来表示。参考引用原本同步至：https://waylau.com/asymptotic-notation/本系列归档至《Java数据结构及算法实战》：https://github.com/waylau/java-data-structures-and-algorithms-in-action《数据结构和算法基础（Java语言实现）》：https://item.jd.com/13014179.html
《数据结构和算法基础（Java语言实现）》读后感(三)：聊下什么是数据结构和算法
本节是《Java数据结构及算法实战》系列的第1节，主要介绍数据结构和算法概念。
对于接触过计算机基础知识的读者而言，对于下面这个公式应该不会陌生：
提出这一公式并以此作为其一本专著书名[1]的瑞士计算机科学家Niklaus Wirth于1984年获得了图灵奖。
程序（Program）是由数据结构（Data Structure）和算法（Algorithm）组成，这意味着的程序的好快是直接由程序所采用的数据结构和算法决定的。
数据结构可以简单理解为是承载数据元素的容器，这个容器中的数据元素之间存在一种或者多种特性关系。比如在Java中，Map和List就是非常常见的数据结构，他们提供了非常方便的方法用于将数据元素添加到这类容器中，同时也提供了在容器中查找数据的方法。
举一个实际的例子，假设我们有一个“学生信息管理系统”需要管理学生的信息，在Java中，我们可以将学生的信息存储在List<Student>这个结构中，代码如下：
学生这个类型Student代码如下：
理论上，学生的所有信息，都可以有在Student类型中做映射，但实际上，在设计计算机系统，我们往往只会记录对该系统相关的信息，比如学生的年龄、姓名、电话号码、地址等。我们没有记录诸如学生的爱好、偶像等信息，因为这些信息对于“学生信息管理系统”而言毫无用处。
研究数据结构时，主要是从三个方面入手，这三个方面称为数据结构的三要素：
数据的物理结构，是指数据在计算机中的存储形式。因此，物理结构又叫存储结构。
物理结构可分为四种：顺序存储结构、链式存储结构、索引结构、散列结构。其优缺点总结如下表1-1所示。
表1-1各种物理结构的优缺点
物理结构特征优点缺点顺序存储结构一段连续的内存空间能随机访问插入删除效率低，大小固定链式存储结构不连续的内存空间大小动态扩展，插入删除效率高不能随机访问索引存储结构整体无序，但索引块之间有序，需要额外空间，存储索引表对顺序查找的一种改进，查找效率高需额外空间存储索引散列存储结构数据元素的存储位置与散列值之间建立确定对应关系查找基于数据本身即可找到，查找效率高，存取效率高存取随机，不便于顺序查找
逻辑结构分为四种类型：集合结构、线性结构、树形结构和图形结构，如下图所示1-1所示。
因此，数据的逻辑结构通常可以采用一个二元组来表示：
其中，D是数据元素的有限集，R是D上关系的有限集。
在上述数据的逻辑结构分类的基础上，还可以进一步细化，衍生出多少种常见的抽象数据类型，包括数组、链表、矩阵、栈、队列、跳表、散列、树、图等。同时，在书中也会给出上述抽象数据类型的Java实现[2]。
算法就是解决问题的步骤。比如，要将大象装进冰箱，需要分为三个步骤：
在计算机科学领域，算法这个词来描述一种有限、确定、有效的并适合用计算机程序来实现的解决问题的方法[3]。算法是计算机科学的基础，是这个领域研究的核心。那么如何来理解算法的有限性、确定性和有效性呢？
[1]该书名为Algorithms + Data Structures = Programs，在1975年由Prentice Hall出版社出版
[2]本书不会对Java语言本身做过多的介绍。如果读者想深入了解Java语言，可以参阅笔者所著的《Java核心编程》。该书在2020年由清华大学出版社出版
[3]出自Robert Sedgewick和Kevin Wayne所著的《算法》一书。该书第4版在2012年由人民邮电出版社出版参考引用原本同步至：https://waylau.com/what-are-data-structures-and-algorithms/本系列归档：https://github.com/waylau/java-data-structures-and-algorithms-in-action数据结构和算法基础（Java语言实现）：https://item.jd.com/13014179.html
《数据结构和算法基础（Java语言实现）》读后感(四)：算法的4种描述方式
本节是《Java数据结构及算法实战》系列的第2节，主要介绍描述算法的常用的4种方式。
要定义一个算法，我们可以用自然语言、流程图、伪代码的方式描述解决某个问题的过程或是编写一段程序来实现这个过程。比如，在前面所举的“学生信息管理系统”例子中，我们希望实现添加用户、删除用户、查询用户三个算法。
可以采用自然语言的方式来描述添加用户、删除用户、查询用户三个算法：
使用自然语言描述的好处是任何人都能看懂。当然相比于伪代码或者程序语言而言，使用自然语言描述有时会显得繁琐。
流程图（Flow Diagram）是一种通用的图形符号表示法是一种非正式的，可以清楚描述步骤和判断。图1-2展示的是用流程图的方式来描述添加用户、删除用户、查询用户三个算法。
相比较自然语言而言，通过流程图的描述，可以很清楚的看到操作的流向及经过的步骤。但需要注意的是，流程图应该只描述核心的操作步骤以及关键的节点判断，而不是事无巨细的把所有的操作都描述出来，否则只会让整个图看上去复杂难以理解。
伪代码（Pseudocode）是一种非正式的，类似于英语结构的，用于描述模块结构图的语言。可以采用伪代码的方式来描述添加用户、删除用户、查询用户三个算法。
添加用户的伪代码如下：
input(student) if student in studentList print "Student exsit" else add student in studentList print "Add student success"
删除用户的伪代码如下：
input(student) if student in studentList remove student from studentList print "Remove student success" else print "Student not exsit"
查询用户的伪代码如下：
if student in studentList output studentList else print "No student exsit"
伪代码结构清晰、代码简单、可读性好，并且类似自然语言。介于自然语言与编程语言之间。以编程语言的书写形式指明算法职能。使用伪代码，不用拘泥于具体实现。相比程序语言（例如Java、C++、C等等）它更类似自然语言。它虽然不是标准的语言，却可以将整个算法运行过程的结构用接近自然语言的形式（可以使用任何一种你熟悉的文字，关键是把程序的意思表达出来）描述出来。
程序语言描述算法，实际上就是用程序语言实现算法。不同的编程语言其语法不尽相同。以下是采用Java语言的方式来描述添加用户、删除用户、查询用户三个算法。
import java.util.ArrayList; import java.util.List; public class StudentInfoManageSystem { private List<Student> studentList = new ArrayList<>(); public void addStudent(Student student) { // 如果已经添加了过该用户的信息，则提示用户。 // 否则将用户信息添加到系统中，并给出提示。 if (studentList.contains(student)) { System.out.println("Student exsit"); } else { studentList.add(student); System.out.println("Add student success"); } } public void removeStudent(Student student) { // 如果用户信息不存在于系统中，则提示用户。 // 否则将用户信息从系统中删除，并给出提示。 if (studentList.contains(student)) { studentList.remove(student); System.out.println("Remove student success"); } else { System.out.println("Student not exsit"); } } public List<Student> getStudentList() { // 如果系统中不存在用户，则提示用户。 // 否则将用户信息查询出来返回，并将用户信息打印出来。 if (studentList.isEmpty()) { System.out.println("No student exsit"); } else { for (Student s : studentList) { System.out.format("Student info: name %s, age %d, phone %s, address %s%n", s.getName(), s.getAge(), s.getPhoneNumer(), s.getAddress()); } } return studentList; } }
为了演示上述算法，还需要一个应用入口。我们用StudentInfoManageSystemDemo类来表示应用主程序，代码如下：
import java.util.ArrayList; import java.util.List; public class StudentInfoManageSystemDemo { public static void main(String[] args) { // 初始化系统 StudentInfoManageSystem system = new StudentInfoManageSystem(); // 初始化学生信息 Student student = new Student(32, "Way Lau", "17088888888", "Shenzhen"); // 添加学生 system.addStudent(student); // Add student success // 再次添加学生 system.addStudent(student); // Student exsit // 第一次查询所有学生 List<Student> studentList = system.getStudentList(); // 删除学生 system.removeStudent(student); // Remove student success // 再次删除学生 system.removeStudent(student); // Student not exsit // 查询所有学生 studentList = system.getStudentList(); // No student exsit } }
运行上述程序，可以看到控制台输出内容如下：
Add student success Student exsit Student info: name Way Lau, age 32, phone 17088888888, address Shenzhen Remove student success Student not exsit No student exsit
程序语言描述算法一步到位，写出的算法可直接交予计算机处理。对于懂得这类程序语言的开发者而言，通过运行程序可以马上验证算法的正确性。当然其缺点也较为明显：
因此，在描述某个算法时，往往通过几种描述方式结合起来使用。参考引用原本同步至：https://waylau.com/deｓｃｒｉｐｔion-of-algorithms/本系列归档：https://github.com/waylau/java-data-structures-and-algorithms-in-action数据结构和算法基础（Java语言实现）：https://item.jd.com/13014179.html
