数据结构学习分享讲述.ppt

一些看法 学了数据结构的同学，不是被数据结构伤的百孔千疮，就是产生了心理阴影，太难太绕了。辛辛苦苦的学的差不多了吧，做程序的时候，好像根本用不上数据机构一样。此乃神物，花费那么大的力气学，到时候用不上岂不是太亏了。 很多很多的文章很多很多的过来人，都告诉你，数据结构很重要。老师上来就跟你说，这个很重要很重要。其实没有几个老师能跟你讲清楚数据结构到底是什么，以至于你学完了都不知所云。都不知道学完后怎么用，如何用，有没有用。虽然他们都说有用，非常有用，那怎么个有用法，很少提及。甚至，在工作中怎么体现的也不曾提及。 似乎数据结构就是什么栈、链表、二叉树、图之类的。 其实这些东西不是数据结构。 作为一个特别爱思考的人，没有一个清晰的方向，学起来也是痛苦的，也是盲目的，虽然知道有用，但是还是如此。或者换一种说法，清楚了自己学的东西，不仅学起来目标明确，心情也爽快，同时效率还会很高。 数据结构+算法=程序 其实，算法和数据结构并非一个东西，数据结构也不是链表之类的。这些都是错误的信号。 数据结构是一门抽象的学科。这个确实如此。而且非常抽象。然而我们的学习，最好是从具体的开始东西开始，这样学习效果更好。很少有人一开始抽象思维就很好的，抽象思维是通过大量的培养才得到的。实际上在潜意识里，抽象思维好的人总会无意识的将一个抽象模型关联到他熟知的一个东西或者现象中。 而这些联系在讲授或学习知识的时候，又忽略了。才导致抽象的东西，越来越抽象，或者说，我们没有能够将抽象的东西足够的具体化成一个实例。所以，你在学习的时候，尽量联系实际中的案例来理解。 数据结构和算法，都是一种抽象的东西。 其实就是人的思想。学好数据结构和算法，就是去掌握那些别人已经想出来的思想而已。并不是让你去记住这些东西如何实现，怎么写代码怎么考试。而我们学到的各种数据结构，是为了算法思路好完成逻辑而构建的一些固定的模型，这些模型只是人为的一个规定而已。或者说，我们只是将这些比较不错的想法思路取一个名字，然后大家交流的时候，说起这个名字就知道了这个数据结构等。 例如我们学习链表结构之类的，就是人家建立的一个固定的模型，或者叫做一个约定的操作方式。那么既然这些别人实现的都是一个典型的操作方式，那么必然有他的优点，我们才需要学习的。然而你既然知道了天机，那么自然就可以去藐视天机，可以去创造，而不是一味的接受。既然是一种思想，你完全可以通过你自己的智慧去改善他的思想，这个就是思想更迭的过程。并不是后来人比前面的人聪明，而是因为他站在巨人的肩膀上起飞的。 国内的教育都是应试教育，没有挖掘这种创造力，然而，要想把这门课学好，就需要充分发挥创造力。你完全可以在掌握一种数据结构模型后，改造它。可以创造出更好的数据结构模型，在今后的多少年，可能教材里的结构就出现了你的结构模型了。 以上是如何学习思想的看法。 算法则是一套思维的流程，以何种逻辑或者说是运算的先后顺序将一个目标实现。比如说，冒泡排序，最终的目标是将一组数据拍好顺序，至于如何实现，其实可以有多种，并不是唯一的。冒泡代表一种思想。你只需要弄懂这个思想的关键，如何一步步运作到实现目标的这个流程，就可以了。基于这个流程，你可以使用另外的实现方式来做到需要的目标，而不必拘泥于课本上的实现过程。否则，你永远都学不会算法。 通常，算法都要用到数据结构的各种模型，这些模型的建立，就是为了方便完成算法的逻辑流程的。正是这些数据结构的存在，让效率大大提升，或者让操作过程更加简便。如果你能理解我说的这些，说明你有所领悟，而彻底明白，只是时间的问题了，前提是要继续思考。 当你领悟到数据结构和算法不再是书上那些东西，你就成功了一大半了。当你的思维高于书上的东西，你学起来，那就简单多了。至少你不会再迷茫，而只是熟悉那些套路而已了。你改进一个算法才成为可能，从此就不是死读书的模式学习数据结构了。 第五讲 图 逻辑结构：网络结构 物理存储结构： 数组存储 相邻矩阵 链表 邻接表（数组+链表） 入边表 出边表 运算： 遍历 深度优先 广度优先：层次遍历 查找、插入、删除 相关应用 拓扑排序：深度优先，基于队列 最短路径 单源最短路径：dijkstra算法 每对结点间最短路径：Floyd算法 最小生成树 Prim算法 Kruskal算法 11.1 图的基本概念 有向图、无向图 图的度、路径 完全图 生成树 一个连通图的生成树是它的极小连通子图，在n个顶点的情形下，有n-1条边。 在生成树中添加一条边，必定形成回路或者环。 但有向图则可能得到它的由若干有向树组成的生成森林。 图的存储：邻接矩阵、邻接表 邻接矩阵 邻接表 图的遍历 深度优先 广度优先 11.4 最短路径 单源最短路径：Dijkstra算法 每对结点间最短路径：Floyd算法 Dijkstra算法 最小支撑树 P