《java数据结构和算法》读书笔记

大学时并不是读计算机专业的, 之前并没有看过数据结构和算法,这是我第一次看。

        从数据结构方面来说:
               数组:最简单,遍历、查找很快;但是大小固定,不利于扩展,同时插入、删除比较麻烦。
               链表:插入、删除很容易实现,没有限定大小,容易扩展;遍历、查找比较麻烦。
               哈希表:它可以提供快速的插入操作和查找操作。哈希表也有一些缺点它是基于数组的,数组创建后难于扩展某些哈希表被基本填满时,性能下降得非常严重。这个问题是哈希表不可避免的,即冲突现象:对不同的关键字可能得到同一哈希地址。
               栈: 是只能在某一端插入和删除的特殊线性表。它按照后进先出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据。
               队列 : 一种特殊的线性表,它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。
               树:它是由n(n>=1)个有限节点组成一个具有层次关系的集合。每个节点有零个或多个子节点;没有父节点的节点称为根节点;每一个非根节点有且只有一个父节点;除了根节点外,每个子节点可以分为多个不相交的子树。二叉树最容易理解,每个节点最多只有两个子节点。树分为平衡树和非平衡树。一般用红黑树来实现平衡树。红黑树有以下几个性质:性质1. 节点是红色或黑色;性质2. 根是黑色;性质3. 所有叶子都是黑色(叶子是NIL节点);性质4. 如果一个节点是红的,则它的两个儿子都是黑的;性质5. 从任一节点到其叶子的所有简单路径都包含相同数目的黑色节点。
               堆:是一种特殊的二叉树。
               图:图是由顶点的有穷非空集合和顶点之间边的集合组成,通过表示为G(V,E),其中,G标示一个图,V是图G中顶点的集合,E是图G中边的集合。树是一种特殊的图。
 
       从算法方面说:
               冒泡法:逻辑简单,但是效率低下。
               选择排序法:与冒泡法相比,减少了交换次数,但是比较次数还是比较多。
               插入排序法:一般情况下,比冒泡法快一倍,比选择排序法要快一点。是基础排序算法中最好的一种。
               希尔排序法:基于插入排序法。如果数据原先排列为从大到小,要用出入排序法从小到大排序的话,效率很低,于是出现了希尔排序法。其余插入排序法的区别是:插入排序法的间隔为1;而希尔排序法是先用较大的间隔进行排序,最后以间隔为1进行排序,成功的避免了上述情况。
               快速排序法:快速排序是最流行的排序算法,因为在大多数情况下,快速算法都是最快的。我比较喜欢的做法是,用三数据项取中划分法将数组分成两份,左边比枢纽小,右边比枢纽大,用递归的方法处理左右两个数组,直至数组的数据项小于等于3,用正常的排序算法进行排序。
               基数排序法:看的头疼,放弃。。。
 
       要做一个好的码农,这本书还是值得看的~
上一篇:A python script to check NE syncfail and get log from CIPS


下一篇:[Python] Execute a Python Script