数据结构书java

2019-03-16 18:49:31 salmon_zhang 阅读数 11066

学习数据结构与算法,还是很有必要看几本相关的书籍,但根据不同基础的人,合适看的书也不一样,因此,针对不同层次、不同语言的人,推荐几本市面上口碑不错的书。

1. 入门级

针对刚入门的同学,建议不要急着去看那些经典书,像《算法导论》、《算法》这些比较经典、权威的书。虽然书很好,但看起来很费劲,如果看不完,效果会很不好。所以建议先看两本入门级的趣味书:

  1. 《大话数据结构》
  2. 《算法图解》

大话数据结构

将理论讲的很有趣,不枯燥。作者结合生活中的例子去对每个数据结构和算法进行讲解,让人通俗易懂。

算法图解

这是一本像小说一样有趣的算法入门书,书中有大量的图解,通俗易懂。

看完上面一本或两本入门级的书,你就会对数据结构和算法有个大概认识和学习。但这些入门级的书缺少细节、不够系统。所以想要深入的学习数据结构和算法,光看这两本书肯定是不够的。

2. 不同语言的教科书

国内外很多大学都是将《数据结构和算法分析》作为教科书。这本书非常系统、严谨、全面,难度适中,很适合对数据结构和算法有些了解,并且已经掌握了至少一门语言的同学学习。针对不同的语言,分别有:

  1. 《数据结构与算法分析:C语言描述》

  2. 《数据结构与算法分析:C++描述》

  3. 《数据结构与算法分析:java语言描述》

如果你不会C、C++、java,会Python或者JavaScript,可以看:

  1. 《数据结构与算法JavaScript描述》

  2. 《数据结构与算法:Python语言描述》

3. 面试书籍

现在很多大厂的面试都会考算法题,这里推荐几本面试算法书籍:

  1. 《剑指offer》

  2. 《编程珠玑》

  3. 《编程之美》

剑指offer

为面试算法量身定做的一本书。几乎包含了所有常见的、经典的面试题,如果能搞懂书里面的内容,一般公司的算法面试都应该没问题。

编程珠玑

这本书豆瓣评分有9分,评分很高。这本书最大的特色是讲了很多海量数据的处理技巧。其他算法书籍很少涉及海量数据。

编程之美

有些作者是微软工程师,算法题目较难,比较适合要面试Google、Facebook这样的公司的人去看。

4. 经典书籍

现在数据结构与算法最经典的书籍就是:

  1. 《算法导论》

  2. 《算法》

  3. 《计算机程序设计艺术》

这三本书非常经典,但都很厚,看起来比较费劲,估计很少有人能全部看完。但如果想更深入地学一遍数据结构和算法,还是建议去看看。

算法导论

章节安排不是循序渐进,里面有各种算法正确性、复杂度的证明、推导,对数学功底有一定要求,看起来有些费劲。

算法

偏重讲算法。内容不够全面,对数据结构方面的知识讲的不多,动态规划这么重要的知识点却没有讲。

计算机程序设计艺术

这本书包括很多卷,相比于其他书籍有更好的深度、广度、系统性和全面性。但如果你对数据结构和算法不是特别感兴趣,没有很好的数学、算法、计算机基础,很难把这本书读完、读懂。

5. 课外阅读

有些算法书籍也比较适合在平时悠闲的时候翻翻看看:

  1. 《算法帝国》

  2. 《数学之美》

  3. 《算法之美》

这些书都列举了大量的列子来解释说明,非常通俗易懂。

下面给出一张上面推荐的数据结构与算法书籍的思维导图:
在这里插入图片描述

2016-11-06 21:06:37 Leonidas_Li 阅读数 8819

自己已经学过数据结构与算法了,但是感觉学校的课本讲得太少,而且不全面,并且老师也是一带而过,但是在后面自学的过程中越来越觉得数据结构与算法越来越重要,因为我是从 C -> c++ -> java 这样入门的,当我学到Java的时候前面C和C++的语法除了一些基本的语法以外都很模糊了,但是数据结构的思想基本没怎么改变,而且对我后面学习java起到了很大的帮助,提升了我学习java的速度,因而觉得数据结构与算法真的很重要,然后想自己去买本好书来自学,但又不知道买java的还是C/C++的,当看了这位大神的回答之后就有了答案,还是买c/c++的吧,因为搞编程都是从顶层一步一步往底层做的,越到底层水平越高,当然工资也越高啦,对数据结构的依赖就越大,但是java的数据结构都给你封装好了,对于我来说,还是希望往底层做。不过我认为不是偏向技术(产品运营或者搞UI的)的同学的话可以选择java 的数据结构与算法。

接下来看看大神的解答吧。

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

作者:涛吴

链接:https://www.zhihu.com/question/20012022/answer/13688683
来源:知乎
著作权归作者所有,转载请联系作者获得授权。

如果说 Java 是自动档轿车,C 就是手动档吉普。数据结构呢?是变速箱的工作原理。你完全可以不知道变速箱怎样工作,就把自动档的车子从 A 开到 B,而且未必就比懂得的人慢。写程序这件事,和开车一样,经验可以起到很大作用,但如果你不知道底层是怎么工作的,就永远只能开车,既不会修车,也不能造车。如果你对这两件事都不感兴趣也就罢了,数据结构懂得用就好。但若你此生在编程领域还有点更高的追求,数据结构是绕不开的课题。

Java 替你做了太多事情,那么多动不动还支持范型的容器类,加上垃圾收集,会让你觉得编程很容易。但你有没有想过,那些容器类是怎么来的,以及它存在的意义是什么?最粗浅的,比如 ArrayList 这个类,你想过它的存在是多么大的福利吗——一个可以随机访问、自动增加容量的数组,这种东西 C 是没有的,要自己实现。但是,具体怎么实现呢?如果你对这种问题感兴趣,那数据结构是一定要看的。甚至,面向对象编程范式本身,就是个数据结构问题:怎么才能把数据和操作数据的方法封装到一起,来造出 class / prototype 这种东西?

此外,很重要的一点是,数据结构也是通向各种实用算法的基石,所以学习数据结构都是提升内力的事情。

书我推荐《Data Structures and Algorithms in Java》,如果你只会 Java,目前也只对 Java 感兴趣的话。
2018-04-29 11:53:50 qq_37101453 阅读数 4043

第一部分:Java数据结构

要理解Java数据结构,必须能清楚何为数据结构?

数据结构:

  1. Data_Structure,它是储存数据的一种结构体,在此结构中储存一些数据,而这些数据之间有一定的关系。
  2. 而各数据元素之间的相互关系,又包括三个组成成分,数据的逻辑结构,数据的存储结构和数据运算结构。
  3. 而一个数据结构的设计过程分成抽象层、数据结构层和实现层。

数据结构在Java的语言体系中按逻辑结构可以分为两大类:线性数据结构和非线性数据结构。

一、Java数据结构之:线性数据结构

线性数据结构:常见的有一维数组,线性表,栈,队列,双队列,串。

1:一维数组

在Java里面常用的util有:String [],int [],ArrayList,Vector,CopyOnWriteArrayList等。及可以同过一维数组[]自己实现不同逻辑结构的Util类。而ArrayList封装了一些[]的基本操作方法。ArrayList和Vector的区别是:Vector是线程安全的,方法同步。CopyOnWriteArrayList也是线程安全的但效率要比Vector高很多。(PS:如果不懂出门右拐看另一篇chat)。

数组这种数据结构典型的操作方法,是根据下标进行操作的,所以insert的的时候可以根据下标插入到具体的某个位置,但是这个时候它后面的元素都得往后面移动一位。所以插入效率比较低,更新,删除效率也比较低,而查询效率非常高,查询效率时间复杂度是1。

2: 线性表

线性表是有序的储存结构、链式的储存结构。链表的物理储存空间是不连续的,链表的每一个节点都知道上一个节点、或者下一个节点是谁,通常用Node表示。常见的有顺序链表(LinkedList、Linked***),单项链表(里面只有Node类),双向链表(两个Node类),循环链表(多个Node类)等。

操作方法:插入效率比较高,插入的时候只需要改变节点的前后节点的连接即可。而查询效率就比较低了,如果实现的不好,需要整个链路找下去才能找到应该找的元素。所以常见的方法有:add(index,element),addFirst(element),addLast(element)。getFirst(),getLast(),get(element)等。

常见的Uitil有:LinkedList,LinkedMap等,而这两个JDK底层也做了N多优化,可以有效避免查询效率低的问题。当自己实现的时候需要注意。其实树形结构可以说是非线性的链式储存结构。

3: 栈Stack

栈,最主要的是要实现先进后出,后进先出的逻辑结构。来实现一些场景对逻辑顺序的要求。所以常用的方法有push(element)压栈,pop()出栈。

java.util.Stack。就实现了这用逻辑。而Java的Jvm里面也用的到了此种数据结构,就是线程栈,来保证当前线程的执行顺序。

4:队列

队列,队列是一种特殊的线性数据结构,队列只能允许在队头,队尾进行添加和查询等相关操作。队列又有单项有序队列,双向队列,阻塞队列等。

Queue这种数据结构注定了基本操作方法有:add(E e)加入队列,remove(),poll()等方法。

队列在Java语言环境中是使用频率相当高的数据结构,所有其实现的类也很多来满足不同场景。


使用场景也非常多,如线程池,mq,连接池等。

5:串

串:也称字符串,是由N个字符组成的优先序列。在Java里面就是指String,而String里面是由chat[]来进行储存。

KMP算法: 这个算法一定要牢记,Java数据结构这本书里面针对字符串的查找匹配算法也只介绍了一种。关键点就是:在字符串比对的时候,主串的比较位置不需要回退的问题。

二、Java数据结构之:非线性数据结构

非线性数据结构:常见的有:多维数组,集合,树,图,散列表(hash).

1:多维数组

一维数组前面咱也提到了,多维数组无非就是String [][],int[][]等。Java里面很少提供这样的工具类,而java里面tree和图底层的native方法用了多维数组来储存。

2:集合

由一个或多个确定的元素所构成的整体叫做集合。在Java里面可以去广义的去理解为实现了Collection接口的类都叫集合。

Collection

3:树

树形结构,作者觉得它是一种特殊的链形数据结构。最少有一个根节点组成,可以有多个子节点。树,显然是由递归算法组成。

树的特点:

  1. 在一个树结构中,有且仅有一个结点没有直接父节点,它就是根节点。
  2. 除了根节点,其他结点有且只有一个直接父节点
  3. 每个结点可以有任意多个直接子节点。

树的数据结构又分如下几种:

  • 1) 自由树/普通树:对子节点没有任何约束。

    自由树

  • 2) 二叉树:每个节点最多含有两个子节点的树称为二叉树。

    2.1) 一般二叉树:每个子节点的父亲节点不一定有两个子节点的二叉树成为一般二叉树。

    2.2) 完全二叉树:对于一颗二叉树,假设其深度为d(d>1)。除了第d层外,其它各层的节点数目均已达最大值,且第d层所有节点从左向右连续地紧密排列,这样的二叉树被称为完全二叉树;

    2.3) 满二叉树:所有的节点都是二叉的二叉树成为满二叉树。

    二叉树

  • 3) 二叉搜索树/BST:binary search tree,又称二叉排序树、二叉查找树。是有序的。要点:如果不为空,那么其左子树节点的值都小于根节点的值;右子树节点的值都大于根节点的值。

    二叉搜索树

    3.1) 二叉平衡树:二叉搜索树,是有序的排序树,但左右两边包括子节点不一定平衡,而二叉平衡树是排序树的一种,并且加点条件,就是任意一个节点的两个叉的深度差不多(比如差值的绝对值小于某个常数,或者一个不能比另一个深出去一倍之类的)。这样的树可以保证二分搜索任意元素都是O(log n)的,一般还附带带有插入或者删除某个元素也是O(log n)的的性质。

    为了实现,二叉平衡树又延伸出来了一些算法,业界常见的有AVL、和红黑算法,所以又有以下两种树:

    3.1.1) AVL树:最早的平衡二叉树之一。应用相对其他数据结构比较少。windows对进程地址空间的管理用到了AVL树。

    3.1.2) 红黑树:通过制定了一些红黑标记和左右旋转规则来保证二叉树平衡。

    红黑树的5条性质:

    1. 每个结点要么是红的,要么是黑的。
    2. 根结点是黑的。
    3. 每个叶结点(叶结点即指树尾端NIL指针或NULL结点)是黑的。
    4. 如果一个结点是红的,那么它的俩个儿子都是黑的。
    5. 对于任一结点而言,其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。

    红黑树

  • 4) B-tree:又称B树、B-树。又叫平衡(balance)多路查找树。树中每个结点最多含有m个孩子(m>=2)。它类似普通的平衡二叉树,不同的一点是B-树允许每个节点有更多的子节点。

    B-tree

  • 4) B+tree:又称B+。是B-树的变体,也是一种多路搜索树。

    B+tree

树总结:
树在Java里面应用的也比较多。非排序树,主要用来做数据储存和展示。而排序树,主要用来做算法和运算,HashMap里面的TreeNode就用到了红黑树算法。而B+树在数据库的索引原理里面有典型的应用。

4:Hash

Hash概念:

  • Hash,一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入(又叫做预映射, pre-image),变换成固定长度的输出,该输出就是散列值。一般通过Hash算法实现。

  • 所谓的Hash算法都是散列算法,把任意长度的输入,变换成固定长度的输出,该输出就是散列值.(如:MD5,SHA1,加解密算法等)

  • 简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

Java中的hashCode:

  • 我们都知道所有的class都是Object的子类,既所有的class都会有默认Object.java里面的hashCode的方法,如果自己没有重写,默认情况就是native方法通过对象的内存的+对象的值然后通过hash散列算法计算出来个int的数字。

  • 最大的特性是:不同的对象,不同的值有可能计算出来的hashCode可能是一样的。

Hash表:

  • Java中数据存储方式最底层的两种结构,一种是数组,另一种就是链表。而Hash表就是综合了这两种数据结构。

  • 如:HashTable,HashMap。这个时候就得提一下HashMap的原理了,默认16个数组储存,通过Hash值取模放到不同的桶里面去。(注意:JDK1.8此处算法又做了改进,数组里面的值会演变成树形结构。)

  • 哈希表具有较快(常量级)的查询速度,及相对较快的增删速度,所以很适合在海量数据的环境中使用。一般实现哈希表的方法采用“拉链法”,我们可以理解为“链表的数组”。

    哈希表

一致性Hash:

  • 我们查看一下HashMap的原理,其实发现Hash很好的解决了单体应用情况下的数据查找和插入的速度问题。但是毕竟单体应用的储存空间是有限的,所有在分布式环境下,应运而生了一致性Hash算法。

  • 用意和hashCode的用意一样,只不过它是取模放在不同的IP机器上而已。具体算法可以找一下相关资料。

  • 而一致性Hash需要注意的就是默认分配的桶比较多些,而当其中一台机器挂了,影响的面比较小一些。

  • 需要注意的是,相同的内容算出来的hash一定是一样的。既:幂等性。

  • 一致性Hash

第二部分:Java基本算法

理解了Java数据结构,还必须要掌握一些常见的基本算法。 理解算法之前必须要先理解的几个算法的概念:

空间复杂度:一句来理解就是,此算法在规模为n的情况下额外消耗的储存空间。

时间复杂度:一句来理解就是,此算法在规模为n的情况下,一个算法中的语句执行次数称为语句频度或时间频度。

稳定性:主要是来描述算法,每次执行完,得到的结果都是一样的,但是可以不同的顺序输入,可能消耗的时间复杂度和空间复杂度不一样。

一、二分查找算法

二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好,占用系统内存较少;其缺点是要求待查表为有序表,且插入删除困难。这个是基础,最简单的查找算法了。

    public static void main(String[] args) {
        int srcArray[] = {3,5,11,17,21,23,28,30,32,50,64,78,81,95,101};
        System.out.println(binSearch(srcArray, 28));
    }
    /**
     * 二分查找普通循环实现
     *
     * @param srcArray 有序数组
     * @param key 查找元素
     * @return
     */
    public static int binSearch(int srcArray[], int key) {
        int mid = srcArray.length / 2;
//        System.out.println("=:"+mid);
        if (key == srcArray[mid]) {
            return mid;
        }

//二分核心逻辑
        int start = 0;
        int end = srcArray.length - 1;
        while (start <= end) {
//            System.out.println(start+"="+end);
            mid = (end - start) / 2 + start;
            if (key < srcArray[mid]) {
                end = mid - 1;
            } else if (key > srcArray[mid]) {
                start = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

二分查找算法如果没有用到递归方法的话,只会影响CPU。对内存模型来说影响不大。时间复杂度log2n,2的开方。空间复杂度是2。一定要牢记这个算法。应用的地方也是非常广泛,平衡树里面大量采用。

二、递归算法

递归简单理解就是方法自身调用自身。

    public static void main(String[] args) {
        int srcArray[] = {3,5,11,17,21,23,28,30,32,50,64,78,81,95,101};
        System.out.println(binSearch(srcArray, 0,15,28));
    }
    /**
     * 二分查找递归实现
     *
     * @param srcArray  有序数组
     * @param start 数组低地址下标
     * @param end   数组高地址下标
     * @param key  查找元素
     * @return 查找元素不存在返回-1
     */
    public static int binSearch(int srcArray[], int start, int end, int key) {
        int mid = (end - start) / 2 + start;
        if (srcArray[mid] == key) {
            return mid;
        }
        if (start >= end) {
            return -1;
        } else if (key > srcArray[mid]) {
            return binSearch(srcArray, mid + 1, end, key);
        } else if (key < srcArray[mid]) {
            return binSearch(srcArray, start, mid - 1, key);
        }
        return -1;
    }

递归几乎会经常用到,需要注意的一点是:递归不光影响的CPU。JVM里面的线程栈空间也会变大。所以当递归的调用链长的时候需要-Xss设置线程栈的大小。

三、八大排序算法

  • 一、直接插入排序(Insertion Sort)
  • 二、希尔排序(Shell Sort)
  • 三、选择排序(Selection Sort)
  • 四、堆排序(Heap Sort)
  • 五、冒泡排序(Bubble Sort)
  • 六、快速排序(Quick Sort)
  • 七、归并排序(Merging Sort)
  • 八、基数排序(Radix Sort)

八大算法,网上的资料就比较多了。

吐血推荐参考资料:git hub 八大排序算法详解。此大神比作者讲解的还详细,作者就不在这里,描述重复的东西了,作者带领大家把重点的两个强调一下,此两个是必须要掌握的。

1:冒泡排序

基本思想:

冒泡排序(Bubble Sort)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

冒泡排序

以下是冒泡排序算法复杂度:

平均时间复杂度最好情况最坏情况空间复杂度
O(n²)O(n)O(n²)O(1)

冒泡排序是最容易实现的排序, 最坏的情况是每次都需要交换, 共需遍历并交换将近n²/2次, 时间复杂度为O(n²). 最佳的情况是内循环遍历一次后发现排序是对的, 因此退出循环, 时间复杂度为O(n). 平均来讲, 时间复杂度为O(n²). 由于冒泡排序中只有缓存的temp变量需要内存空间, 因此空间复杂度为常量O(1).

Tips: 由于冒泡排序只在相邻元素大小不符合要求时才调换他们的位置, 它并不改变相同元素之间的相对顺序, 因此它是稳定的排序算法.

/**
 * 冒泡排序
 *
 * ①. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
 * ②. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
 * ③. 针对所有的元素重复以上的步骤,除了最后一个。
 * ④. 持续每次对越来越少的元素重复上面的步骤①~③,直到没有任何一对数字需要比较。
 * @param arr  待排序数组
 */
public static void bubbleSort(int[] arr){
    for (int i = arr.length; i > 0; i--) {      //外层循环移动游标
        for(int j = 0; j < i && (j+1) < i; j++){    //内层循环遍历游标及之后(或之前)的元素
            if(arr[j] > arr[j+1]){
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                System.out.println("Sorting: " + Arrays.toString(arr));
            }
        }
    }
}

2:快速排序

快速排序

快速排序使用分治策略来把一个序列(list)分为两个子序列(sub-lists)。步骤为:

①. 从数列中挑出一个元素,称为”基准”(pivot)。

②. 重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。

③. 递归地(recursively)把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归到最底部时,数列的大小是零或一,也就是已经排序好了。这个算法一定会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

代码实现:

用伪代码描述如下:

①. i = L; j = R; 将基准数挖出形成第一个坑a[i]。

②.j--,由后向前找比它小的数,找到后挖出此数填前一个坑a[i]中。

③.i++,由前向后找比它大的数,找到后也挖出此数填到前一个坑a[j]中。

④.再重复执行②,③二步,直到i==j,将基准数填入a[i]中。

快速排序采用“分而治之、各个击破”的观念,此为原地(In-place)分区版本。

快速排序 In-place

/**
 * 快速排序(递归)
 *
 * ①. 从数列中挑出一个元素,称为"基准"(pivot)。
 * ②. 重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
 * ③. 递归地(recursively)把小于基准值元素的子数列和大于基准值元素的子数列排序。
 * @param arr   待排序数组
 * @param low   左边界
 * @param high  右边界
 */
public static void quickSort(int[] arr, int low, int high){
    if(arr.length <= 0) return;
    if(low >= high) return;
    int left = low;
    int right = high;
    int temp = arr[left];   //挖坑1:保存基准的值
    while (left < right){
        while(left < right && arr[right] >= temp){  //坑2:从后向前找到比基准小的元素,插入到基准位置坑1中
            right--;
        }
        arr[left] = arr[right];
        while(left < right && arr[left] <= temp){   //坑3:从前往后找到比基准大的元素,放到刚才挖的坑2中
            left++;
        }
        arr[right] = arr[left];
    }
    arr[left] = temp;   //基准值填补到坑3中,准备分治递归快排
    System.out.println("Sorting: " + Arrays.toString(arr));
    quickSort(arr, low, left-1);
    quickSort(arr, left+1, high);
}

以下是快速排序算法复杂度:

平均时间复杂度最好情况最坏情况空间复杂度
O(nlog₂n)O(nlog₂n)O(n²)O(1)(原地分区递归版)

快速排序排序效率非常高。 虽然它运行最糟糕时将达到O(n²)的时间复杂度, 但通常平均来看, 它的时间复杂为O(nlogn), 比同样为O(nlogn)时间复杂度的归并排序还要快. 快速排序似乎更偏爱乱序的数列, 越是乱序的数列, 它相比其他排序而言, 相对效率更高.


最后,作者希望让大家对《Java数据结构》整体有个全面的了解,知道什么是数据结构,离我们工作中有多远,而不是一个深不可测的神秘物件。里面的细节,篇幅有限可能不能描述完,但是只要同学们的方向没有搞错,那只要针对每个点再详细的看看即可。

面试和工作,这些都是离不开的,当同学们有个完整的认识之后,一定要在工作中留心,留意每个用到的地方。

更多精彩教程,请关注公众号:Java开发教程视频      


2017-12-13 15:46:00 weixin_33697898 阅读数 772

Data Structures and Algorithms in Java (2nd Edition)

没错,这本书的代码都是用Java写的。

现在市面上关于数据结构和算法的书的描述语言一般是C、C++和Java,我只见过一本是C#的:《Data Structures and Algorithms with Object-Oriented Design Patterns in C# 》,不过从名字也能看得出来,里面涉及了部分OO的内容,我觉得在学习数据结构和算法的时候还是独立开比较好,否则程序很难独立运行。所以只好找其它的书,对于C、C++来说,它们的基本语法我们确实可以很快学会,但是学会语法跟学会使用不是一回事。因为语言本身的设计理念不同,要真的掌握一门语言不容易,而且我们也没那么多时间,Java自然就是最好的选择了。那不是又得需要学习Java?我觉得基本上不需要,Java和C#本来就是近亲,这种关系要比C#和C/C++之间近得多。

《Java数据结构与算法》是电力出版社出版的“国外经典计算机科学教材”系列的一本,作者很为初学者考虑,举了大量直观、简单的例子,使得理解这些知识变得轻松、有趣。对于计算机科班出身的人来说,这本书或许可以不看,但对于像我这样野路子出来的人来说,这本书不失为一本很好的入门书。


本文转自一个程序员的自省博客园博客,原文链接:http://www.cnblogs.com/anderslly/archive/2008/10/04/data-structures-and-algorithms-in-java.html,如需转载请自行联系原作者。

2014-09-15 07:03:40 iaiti 阅读数 122373

这篇文章里面不讲技术,抽空讲讲技术和通俗之间有一种奇特的关系,还有驱动力学习的东西。看的是——《Java数据结构和算法》一书,作者Robert Lafore。

目录

1)数据结构算法有什么用?

2)技术与通俗

3)驱动力学习


1)数据结构算法有什么用?

当你用着java里面的容器类很爽的时候,你有没有想过,怎么ArrayList就像一个无限扩充的数组,也好像链表之类的。好用吗?好用,这就是数据结构的用处,只不过你在不知不觉中使用了。

 

校招会发现大公司考的就是这类的题目,刚开始不会考你java的线程,容器,多态什么的特性,考的就是你的基础,你的这些基础扎实,学其他不是问题。

 

正如作者所说,用于现实世界的存储,我们使用的工具和建模。每种数据结构有自己的优点和缺点,想想如果Google的数据用的是数组的存储,我们还能方便地查询到所需要的数据吗。

而算法,在这么多的数据中如何做到最快的插入,查找,删除,也是在追求更快。

 

第一章也把数据库,面向对象,软件工程(原来整个软件工程项目的生命周期包括分析、设计、验证编码、测试、生产和维护几个阶段)讲了个大概

 

 

 

2)技术与通俗

大学里面那本严蔚敏的数据结构不厚,内容丰富,但是复杂问题的讲解方面篇幅这样就少了,比较难理解,c也不是很擅长,但是基本的思路还是有的。

简单的链表,数组,堆栈,队列,图,几个排序算法。

 

后面看到知乎涛吴的回答,当时很震撼,这里引用一下他的回答:

 

如果说 Java 是自动档轿车,C 就是手动档吉普。数据结构呢?是变速箱的工作原理。你完全可以不知道变速箱怎样工作,就把自动档的车子从 A 开到 B,而且未必就比懂得的人慢。写程序这件事,和开车一样,经验可以起到很大作用,但如果你不知道底层是怎么工作的,就永远只能开车,既不会修车,也不能造车。如果你对这两件事都不感兴趣也就罢了,数据结构懂得用就好。但若你此生在编程领域还有点更高的追求,数据结构是绕不开的课题。

Java 替你做了太多事情,那么多动不动还支持范型的容器类,加上垃圾收集,会让你觉得编程很容易。但你有没有想过,那些容器类是怎么来的,以及它存在的意义是什么?最粗浅的,比如 ArrayList 这个类,你想过它的存在是多么大的福利吗——一个可以随机访问、自动增加容量的数组,这种东西 C 是没有的,要自己实现。但是,具体怎么实现呢?如果你对这种问题感兴趣,那数据结构是一定要看的。甚至,面向对象编程范式本身,就是个数据结构问题:怎么才能把数据和操作数据的方法封装到一起,来造出 class / prototype 这种东西?

此外,很重要的一点是,数据结构也是通向各种实用算法的基石,所以学习数据结构都是提升内力的事情。

 

反正我有醍醐灌顶的感觉,好比说,我有在编程上更厉害的追求,怎么能死在数据结构上的感觉。

 

其实要将一门难懂的技术通俗地讲给不懂的人听,需要很大的功力,包括之前我写的那篇《C与指针》刚开始的时候,那个C语言有什么用回答也是他写的,我很佩服这样的人。

 

所以当你能把一件东西清楚的讲解给别人听,类似前几篇文章提到的橡皮鸭调试法一样,你搞懂了,摸清楚了。跟一个技术人士用技术的语言讲解,非专业人士通俗语言讲解。

 

当然了,前提需要积累。具体可以参见一下CSDN里面关于罗升阳的访谈——

专访罗升阳:老罗的Android之旅

当时吓了我一跳,之前以为和那个老罗同个级别的年龄,后面发现好年轻的小伙子,积累,慢慢积累。

 

 

3)驱动力学习

当你看到你自己玩过的马里奥可以自己写出来的时候是不是心动了?顿时学习的驱动力是不是有了——我要做一个这样的东西出来,然后开始学,直到自己动手完成。

 

当时我在大学里就在推算,按照我这个学习速度,10年之后那也可以牛逼哄哄啊。有些人为什么技术没有提升,几年之后还是那样,因为驱动力的东西,有段时间我曾经停下来过,Java的差不多都学完了,干什么?

 

因为从J2SE到EE的东西,大体的看完做过,然后就有一段迷茫期了,驱动力也没有了。后面意识到自己太肤浅了,还有其他一些热门的框架没用,最好的单例你写出来了吗,虚拟机你深入了吗,Java还有很多经典书籍没看呢?

以学习新知识为驱动力也是可以的,期间不停地学到新知识是很有成就感和很兴奋的东西——原来是这样xx。

 

还有一种——目标驱动,当时要做一个网络相关的东西——想到了爬虫,然后以做出这东西为目的,收集资料,看别人的代码,这样的驱动力学习也是可以的。工作的时候,如果目标只放在工作的项目,每次的项目都有新的东西在里面,那是可以学到东西的,一成不变的话,只能自己去发掘了。

不然哪有那个学习到半夜的——专访雷果国:从1.5K到18K 一个程序员的5年成长之路。

 

我要学Python,学了之后会发现,原来真的很牛逼,可以尝试用Python写个爬虫,GoAgent之类的。这便是进步。

 

 

扯了那么多,就是不希望自己只懂的用Java做xx系统,只懂得用容器而永远不知道里面是怎样的。这些作为根基的懂了,其他也好学。

 

说回数据结构这个,为什么很多学生听课听得想睡,xx链表,双向链表,我排序都有N种,学生的想法是这不知道有什么用,你讲链表给我,我把它实现一次,完事。

 

但当你生活中的编程问题需要解决的时候,你会发现到处都是数据结构的使用,像基金买入买出不是队列吗,先进先出;像简单的一个班级学生的数据保存,用个数组不就可以解决了吗;再复杂的游戏路线问题,这不是图的问题吗;Java里面有Tree这字的,其实不也是用到树的原理吗?

 

种种下来,你会发现,原来现实问题和语言里面的封装,都是和这些有联系的,每当你学会一种,就会恍然大悟,这不就是当年西湖河畔的夏雨荷,就是这种感觉。而学生在没有想过这些问题和没真正去使用这些语言的封装类之前,是不会考虑到上面所说的东西的。

 

所以,一大群学生趴在那里睡觉玩手机是正常的。

 

后面自己意识到之后,马上去买了《Java数据结构和算法》,补回之前没学和没弄懂的。

 

不想学好基础的程序员不是好的程序员。