玩转数据结构 java描述 一 概况

慕课网 笔记 第一章 介绍，数据结构是计算机专业的同学必学的课程数据结构研究的是数据如何在计算机进行组织和存储，使得我们可以高效的获取数据或者修改数据。 数据结构可以分为三种结构：线性结构：数组；栈；队列；链表；哈希表 树结构：二叉树，二分搜索树，AVL，红黑树，Treap，Splay，堆，Trie，线段树，K-D树，并查集，哈夫曼树 图结构邻接矩阵，邻接表 我们需要根据应用的不同，灵活选择最合适的数据结构， 例子：1，数据库，它已经封装好了，使用SQL语言就可以使用数据库，SELECT * FROM 慕课网WHERE interest = "数据结构" 里面最重要的是使用树结构：AVL，红黑树，Treap，伸展树，B树，还有很重要的哈希表 2，操作系统涉及非常多的数据结构，1个例子，多任务切换，涉及：系统栈，递归调用就需要系统栈优先队列：堆。 有了优先队列，操作系统才可以快速在多个任务之间比较他们的优先级，实现任务的切换 3，文件压缩不只是RAR，计算机中的PNG，MP3，PDF都是对不同的文件进行了一定的压缩处理，最基础的压缩算法使用的是哈夫曼树，哈夫曼树很简单，现在软件已经不用了 4，通讯录，当时使用的链表，但是联系人非常多时，查找特别慢，最后这个问题被实习生解决，方法很简单，Trie，前缀树。这样，在通讯录查找任何人都是ms级别，不管你有多少联系人 大量的算法，以数据结构为基石如，游戏中的寻路算法，是图论算法，DFS深度优先遍历：使用栈，BFS广度优先遍历：使用队列 数据结构+算法 = 程序 课程设置不需要任何数据结构基础，但是需要java语言的基础，选择java是因为java的推广度高，大多数同学都会，java是完全面向对象的，非常适合进行底层数据结构的研究，链表，队列，栈，哈希表，都是一个名词，然后对名词赋予不同的操作，这非常符合面向对象的原则。 所以不仅可以掌握数据结构，还可以对面向对象的设计有更深入的理解，C++ PHP swift Python，都支持面向对象，都可以自己去写 课程包含：数组，栈，队列，链表，二分搜索树，堆，线段树，Trie并查集，AVL，红黑树，哈希表， 不包含图结构，因为存储图非常简单，线性表就可以，但是图论领域非常庞大，以算法为主， 基础的结构，也不能忽视，如：递归，如何调试，复杂度分析， 手把手的学习底层的实现，完成后可以向更加复杂的数据结构进军，并不是实现了就结束了，对于每个数据结构背后的思考，为什么有他们，如何优化，比较， 三个层次：1，面向面试：数组，栈，队列，链表，二分搜索树，堆，最简单，是面试笔试的常客，要达到手写代码的程序，2，面向竞赛：线段树，Trie，并查集，这是竞赛的常客 讲一些LeetCode典型， 最后，AVL，红黑树，哈希表，AVL和红黑树本身都是平衡二叉树的实现，哈希表是非常常用的数据存储结构放在最后是因为他们比较复杂，代码量大一些面试时不要求实现他们，都是概念和性能分析上的问题，如红黑树书平衡的但是不是完全平衡的，所以有很多和性能分析相关的问题，哈希表和冲突检测相关就有很多性能分析问题本课程会从基层开始写， 一般很难这样讲  ===================1-2 ，学习数据结构有没有用？ 为什么在工作中用不到数据结构和算法？工作中用不到数据结构和算法，所以他们没用？ 考硕士博士一定要数据结构和算法，所以他们只是为了应付面试和考试？ 没用：现代软件开发过程越来越简单，如IOS开发者，使用IOS，使用Swift语言，使用Xcode开发工具，IOS开发者对他们的细节一无所知，使用接口就可以了，不需要任何数据结构算法知识，就能开发一个很好的APP，所以开发APP的门槛越来越低，苹果也希望这样，所以如果只是使用工具构建出属于我们自己的网站或者APP，是越来越简单的，在技术上，可能以后，这部分工作都不需要计算机专业的同学来做， 计算机专业的同学，关注的是上面的加粗，里面包含更多的智力劳动，底层操作系统，数据库，语言，开发环境，各种框架，开发他们会使用大量的框架， 这些都是大公司做的，所以越大的公司，越需要同学有扎实的数据结构和算法功底 随着产品庞大，功能变多，开发者不仅要解决功能需求问题，还要解决计算机科学的问题，这是数据结构和算法就发挥巨大作用学好数据结构，会大大提高技术上限，可以走的更远， 如果你想在计算机技术走的更远，就必须学习数据结构， =====================1-3这门玩转数据结构，与那个166的有什么区别？区别很大，这门课程，是以数据结构为主线的，这节课将的数据结构和那个课几乎是不重叠的，而且重复的点，讲解也有所不同， 166的课涉及各种排序，快速排序，堆排序，图算法， 166的课用C++讲解，虽然也提供了完整的java代码，但是我意识到很多同学都用的是java，所以用完全面向对象的java更好， 关于脚本语言：JS，Python，这种非编译型的语言，依靠解析器在运行时进行解释的语言脚本语言可以用来学习数据结构的原理，但不适合 考察数据结构和算法的性能，性能不仅仅和逻辑相关，还非常依赖于其解析器对不同写法的解析的不同，如，对于python，写出pythonic的写法可能比逻辑本身更重要，如：//类java的写法：arr = []for i in range(10):    arr.append(i)python中   可以用生成表达式：arr = [i for i in range(10)]但是两种写法不仅是代码数量的区别，下面的写法性能远远优于上面的写法 所以对于脚本语言，不仅关注逻辑，还关注语法， 所以对于学习，不希望两者都关注，像C++ java是更好的学习数据结构的语言，java运行在JVM上，可能也涉及一些这个问题，但可以忽略 leetcode题库分门别类解析课程，就有这个问题，python跑就超时了，java/c++是通过的， 课程官方github：https://github.com/liuyubobobo/Play-with-Data-Structures 会逐渐添加多语言支持，和习题 关于答疑，我非常注重问答，回答非常详细， 问答时不要直接贴代码，然后问为什么不对。我会回答，你要仔细debug，  好的问题，有你的思考在里面，详细说明，哪个地方出了问题，你的思考是什么？认为应该有怎么的结果，实际却得到了怎么样的输出？ 数据结构只是面试的一部分，甚至只是算法面试的一部分，如排序算法，二分搜索算法，回溯算法，贪心算法，这个可以看玩转算法面试，但是那些课不会涉及底层实现，如哈希表就拿来直接用， 算法竞赛非常广泛，深度也高，图论，计算几何，组合数学，概率论，等进行考察 ========1-4java 8，是最稳定版本现在已经退出了java 10，由于java 8是普遍使用的，所以建议用它，课程代码本身对java语言版本没有太多要求，用不上太多java的新特性，java 6以后都没问题， JDK用java 8IDE用IJ，非常好用，在jetbrains， tools->IDES->IntelliJ IDEA在慕课网有课程：IntelliJ IDEA神器使用技巧--------------------- 作者：894508923 ！