Java编程

网易云课堂数据结构与算法

1.教材:

★★★★数据结构与算法分析 (豆瓣)

(经典之作,广为人知)

网易云课堂数据结构与算法

★★★数据结构 (豆瓣)

(严蔚敏的,就是国内大学常用的那本。严谨,伪代码不错。)

★★大话数据结构 (豆瓣)

(语言比较通俗。比第一本简单易懂。btw,作者程杰老师在知乎上也相当活跃)

★★算法(第4版) (豆瓣)

(图超多。比第一本简单易懂。)

2.慕课:

★★★★★浙江大学的:数据结构 – 网易云课堂

(真的很棒。借雷军的一句广告:我所有的向往。对于每个知识点的视频讲解,基本都涉及了:动画演示、写代码的思路、写代码的技巧、算法优化、算法复杂度分析等等)

★★★★★清华大学的:数据结构-学堂在线慕课(MOOC)平台

(同样地非常非常非常好。比起浙大的数据结构,难度更深,内容更多。而且听完课以后,不仅知其然,也知其所以然。)

就需要先搞清楚几个前提,

1、内存的数据存储模式,是以顺序排列的方式存储的。

也就是说,内存中的数据是起点是0,终点根据内存的大小和操作系统而定的一个顺序的序列。0被占用,后面存入的数据则依次存入。

2、程序在一个线程中,一次只能从一个地址来取数据。所以,除了图之外,所有的数据结构都有且只有唯一的取数入口。所以,必须从一个入口来进行取数。

3、内存的数据存取并不是单线的,而是很多个程序不断的进行并行操作的。所以数据的分布是不连续的,操作系统并不能保证可以一次性找到足够大的一块内存来存放一次操作所需要的所有数据。

可以用磁盘碎片整理的图示来类比一下,使用一段时间以后,内存中的数据大概就是这个样子的,此时要想一次性开出一大块数据,是不可能的,所以要想办法解决数据量无限增加时的数据分配。

三、数据结构分为三大类

1、线性表:

这个是为了解决单线存储而出现的,数组就是最简单粗暴的存储方法。就是直接拉出一大块数据存在那里。数组的快速存取其实只是一个副作用,因为所有的数据都在一起,可以直接算出来数据的地址。链表则是为了解决可以无线增长的需求的。因为找不到一大块可以连续的存入数据,甚至也不知道程序可能使用的数据总量,所以就没办法划分一块数据来使用,划小了不够用,划大了浪费(这在早年是非常大的事情)。所以必须想办法解决问题。最后采用的方法就是从入口开始,每一个数据块不仅仅有数据,还会有指向下一个数据块的线索,用来寻找下一个数据。这就是链表。所谓的双向链表,只是加了一个向前的线索的链表而已。队列,栈,都是线性表的特殊形态。进行了操作上的限制罢了。没有什么太复杂的。

2、树:

树是为了解决单一入口下的非线性关联性的数据存储或者排序这样的功能而来的。

最常见的应用是编程时候的map,就是利用了二叉树的可排序和可以快速插入并且保持序列完整的特性来构建键值数据对,来实现数据的插入增加以及快速查找的能力的。

还有做语法解析,文字处理等等很多场景也会用到树。这就不一一赘述了。当然在吃透线性表的基础上,再去理解树也并不难。因为树相对于链表,就是每个节点不止有一个后续节点但是只有一个前置节点。

3、图:

图是数据结构里最难的一部分,但是很多学校并不作为重点,因为确实大部分人不会用到。

图其实就是把线性表进一步扩展,每个节点会有不止一个前置和后缀节点,而且前置和后缀的概念也不再明晰,变成了关联节点而已。

四、学习建议

理解数据结构/算法的原理

也就是说能够在脑子里明白这个数据结构/算法是怎样工作的,知道这样做的正确性。当然,如果理解有困难可以借助其他知友们推荐的可视化工具: VisuAlgo – 数据结构和算法动态可视化 (Chinese)

用C/C++实现

这一步也是最考验一个人编程基本功的。写出简洁、优雅、具有表现力的代码能够使数据结构的学习变得很简单。反之,如果接口设计得太复杂、边界情况不注意处理或者不注意效率的话,就会出现各种bug:内存泄漏、野指针、递归栈溢出……

因此,建议学习的时候多参考优秀的教材。我用的是邓俊辉大大的数据结构C++版(这里安利一下学堂在线上的配套MOOC 数据结构(2015秋)-学堂在线慕课(MOOC)平台)和 Weiss的数据结构与算法分析。这两本书的主页上都提供了源代码下载。

分析时间和空间复杂度、优点、缺点以及适用于解决的问题学习顺序

 形象化数据结构

     直观的理解某种数据结构是什么样的,使用起来是什么样的,在抽象和实际的内存中是如何存储的。这是一件单独的并且很重要的事情,从最简单的栈和队列到很复杂的平衡树。你可以把它们画出来,直观地展现在你脑海里,无论你用什么方式,最重要的就是你要直观地去理解。

知道在自己的代码中何时,并如何去使用这些不同的数据结构和算法

这一点对于学生来说可能有点难,因为在他们的作业中不需要思考这些。没有关系,你以后会意识到如果你不参加一个实际的项目,你就永远不会理解数据结构,你也不会发现哈希算法是你解决性能问题的方法。但是,即使是学生,你也应该学习一些实用性强的内容,比如什么时候用哈希表?什么时候用树结构?什么时候最小堆是最好的解决方案?

线性表—- 树—- 图。这是一种演进路径

线性表— 堆栈、队列、串— 数组— 各种线性表;

二叉树— 各种二叉树—- B树、B+树—- 红黑树;

附件知乎网址:https://www.zhihu.com/question/21318658

Similar Posts

发表评论

邮箱地址不会被公开。 必填项已用*标注