# Structurealgorithm

**Repository Path**: cyhgyq/structurealgorithm

## Basic Information

- **Project Name**: Structurealgorithm
- **Description**: 数据结构和算法学习
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 1
- **Created**: 2022-04-14
- **Last Updated**: 2023-04-10

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 一、稀疏数组sparsearray  
    使用场景，五子棋黑子和白子存盘退出和续上盘的功能。 压缩数据量  
        当一个数组中大部分元素为0，或者为同一个值得数组时，可以使用稀疏数组来保存  
     使用方法：第一行记录数组一共有几行几列，数组中有几个值要记录  
             把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模  
             得到的数组时列数为3，行数为第一行第三列的值+1  

     算法分析：二维数组转稀疏数组的思路：  
             遍历原始的二维数组，得到有效数据的个数sum  
             根据sum就可以创建稀疏数组sparseArr int[sum+1][3]  
             将二维数组的有效数据存入到稀疏数组  
 
             稀疏数组转原始的二维数组的思路  
             先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组，比如上面的chessArr2=int[11][11]  
             再读取稀疏数组后几行的数据，并赋值给原始的二维数组即可。  


 # 二、队列是一个有序列表，可以用数组或链表实现。   
          先入先出原则  
          实现思路：数组方式： 两个变量记录队头front和队尾rear. 最大容量maxSize. 使用的是环形数组，用取模来实现。  
                 front表示指向队列的第一个元素。arr[front%maxSize]就是队列的第一个元素  
                 rear表示最后一个元素的后一个位置  
                 队列满时的条件：（rear+1)%maxSize = front  
                 队列空的条件：rear == front  
                 front的初始值为0,  
                 rear的初始值为0，  
                 最后一个空间预留出来不放数据，也就是最多放maxSize-1个数据。 如果不预留算法就得变更  
                 当我们这样分析，队列中有效的数据个数（rear + maxSize - front） % maxSize  

#  三、单链表   
     链表反转： 从头到尾两个之间相互反转，并且用一个temp_node记录一下后面一个的下一个节点， head_node也要改变一下位置。  
     逆序打印： 使用栈的先进后出的特点，将所有节点入栈，然后再出栈。  

#  四、双向链表    
     删除：不需要辅助节点，直接用node.prev.next = node.next; node.next.prev = node.prev;  

#  五、单向环形链表    
     应用场景：Josephu(约瑟夫问题），有1...n个小孩围成一圈，数到2的某个小孩出列，从而得到一个出队序号。 （也可以数组取模的方式实现）  

#  六、栈  
     栈的应用场景  
        子程序的调用、处理递归调用、表达式的转换、二叉树的遍历、图形的深度优先搜索法  
     用栈来实现计算器有：前缀、中缀、后缀表达式  

 # 七、递归  
     用于解决什么样的问题  
        数学问题：8皇后问题、汉诺塔问题、阶乘问题、迷宫问题、球和篮子的问题  
        算法问题：快排、归并排序、二分查找、分治算法  
        用栈解决的问题也可以用递归解决  

    球和篮子的问题：如果2个球放到2个篮子里，可以采用3中方式，即（0,2）， （1， 1）， （2， 0）  
    八皇后的问题：8x8的格子，任意两个皇后都不能处于同一行、同一列、同一斜线上，问有多少种摆法  
           思路分析：例子Queue8.java  
            1）第一个皇后先放第一行第一列  
            2）第二个皇后放在第二行第一列，然后判断是否ok，如果不ok,继续放在第二例、第三列、依次把所有的列都放完，找到一个合适的  
            3）继续第三个皇后，还是第一列、第二列...直到第8个皇后也能放到一个不冲突的位置，算是找到了一个正确的解。  
            4）当得到一个正确的解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一列的所有正确解全部得到  
            5）然后回头继续第一个皇后放到第二列，后面继续循环执行1、2、3、4的步骤  

#   八、排序算法  
     常见的排序算法：  
         插入排序：直接插入排序、希尔排序  
         选择排序：简单选择排序、堆排序  
         交换排序： 冒泡排序、快速排序  
         归并排序：  
         基数排序：  
     算法的时间复杂度从小到大依次为：o(1) < o(log 2 n) < o(n) < o(nLog 2 n) < o(n2) < o(n3) < o(nK) < o(2N)  
     各种算法的时间复杂度对比  
        排序法   平均时间     最差情形    稳定性    额外空间    备注  
        冒泡     o(n 2)     o(n 2)     稳定      o(1)      n小时比较好  
        交换     o(n 2)     o(n 2)     不稳定      o(1)      n小时比较好  
        选择     o(n 2)     o(n 2)     不稳定      o(1)      n小时比较好  
        插入     o(n 2)     o(n 2)     稳定      o(1)      大部分已排序是较好  
        基数     o(nlogRB)  o(nlogRB)  稳定      o(n)        内存耗太多，只支持正整数，不推荐  
        shell   o(nlogn)   o(ns) 1<s<2  不稳定    o(1)      s为所选分组  
        快速     o(nlogn)    o(n 2)     不稳定    o(logn)    n大时较好  
        归并     o(nlogn)   o(nlogn)     稳定    o(n)         n大时较好  
        堆       o(nlogn)   o(nlogn)    不稳定    o(1)         n大时较好  

#  十、冒泡排序 BubbleSort.java  
     思想分析：寻找n-1次，第一次找最大的放最上面，以此类推，寻找时相互交换。  
#  十一、选择排序：SelectSort.java  
      思想分析：先找出最小的，放到第一个位置，以此类推，但是它不会去交换。  
#  十二、插入排序：InsertSort.java  
      思想分析：认为前面的几个数已经排好序了，找下一个数与前面数比较，然后相邻两个数交换位置。  
#  十三、shell排序：ShellSort.java   --也是插入排序  
      简单排序有一个缺点，如果最后一个数最小，需要交换很多次才能将最后一个数排到最前面。  
      思想分析：如果有10个数字，10/2分成5组，步长为5，第0个和第5个为一组，第1个和第6个为一组，以此类推，每组内部排序；  
              5/2分成2组，步长为2，第0个和第2个为一组，以此类推，每组内部再排序；  
              以此类推，当2/2分成1组时，步长为1，就是对整个1组进行排序。  
#  十四、快速排序：QuickSort.java  --对冒泡排序的优化,  比shell排序快  
      思想分析：找到数组中间的数，将比中间小的数放到中间数的左边，大的数放到右边，左边和右边再用同样的方法操作。  
              左边和右边各一个指针，找到符合条件的数，然后交换。  
#  十五、归并排序：MergeSort.java  
      思想分析：使用的是分治算法，将一个数组拆分成单个的值，两两顺序合并，合并后的值在顺序合并。  
               全部合并完后，在新建一个临时数组，左右两边都是顺序的，左右各拿出一个数字比较，小的插入零时数组  
               每次合并都是用上面的方式合并排序的，两两合并都是上面方法排序。  
               归并排序需要额外的空间  
#   十六、基数排序： RadixSort.java ---也叫桶排序， 需要10倍的额外空间,耗内存太多，不推荐，并且只支持正整数，负数会报错  
       思想分析：添加10个桶（数组）， 将个位数取出，将整个数字放到对应的桶。  
               然后依次取出桶中的数据放到原来数组中。  
               在改变的原数组中，然后以此类推比较十位百位。  

#   十七、查找算法：常用的查找算法：顺序（线性）查找，二分查找、插值查找、斐波那契查找  
          线性查找：从头到尾一个一个查找，查到再返回。  
          二分查找：有序数组中查找，一半一半的查找中间值，递归的方法： BinarySearch.java  
          插值查找：有序数组中查找，解决二分查找如果查找两头的数据时，需要查找很多次的问题。即二分之一这个值要改成一个公式。不一定比二分查找快。  
          斐波那契查找: 有序数组中查找，使用黄金分割点0.618来代替二分查找。将二分之一改成黄金分割点公式。可能需要扩容，再分割。  

 #  十八、哈希表 略  

 #  十九、树结构
      如果不是顺序二叉树，左边的子节点不一定比右边的子节点小，值可以随意放的。  
      数组的优点：通过下标访问速度快、有序数组二分查找速度快  
           缺点：检索具体的值，或插入值速度慢。  

     链表的优点：插入和删除书店快  
          缺点：通过下标检索速度慢  

      树结构：存储和读取速度快，插入、删除、修改速度也快。  

      树的常用术语：  
         节点：  
         根节点：  
         父节点：  
         子节点：  
         叶子节点：没有子节点的节点  
         节点的权：节点的值   
         路径：从根节点找到该节点的路线  
         层：  
         子树：  
         树的高度：最大的层数  
         森林：多棵子树构成森林  

     满二叉树：二叉树的所有叶子节点都在最后一层，并且最后一层排满了  
     完全二叉树：二叉树的所有叶子节点在最后一层或者倒数第二层，最后一层左边是连续的，倒数第二层右边是连续的。  
     前序遍历： 先输出父节点，再变量左子树和右子树  
     中序遍历： 先遍历左子树，再输出父节点，再变量右子树  
     后序遍历: 先遍历左子树，再遍历右子树，最后输出父节点  
     小结：看输出父节点的顺序，就确定是前序中序还是后序遍历  
     树的查找也分为前序中序后序三种查找方法。    
     删除操作：如果是叶子节点就直接删除，如果是非叶子节点则直接删除子树，或者将左子树提升到要删除的位置。  
             判断当前节点的左子树不为空，并且左子节点的值是要删除的值，那么就通过当前节点删除左子树，以此类推。  
     顺序存储二叉树：树可以转换成数组，数组也可以转换成树。一般用完全二叉树来实现。也都可以用前序中序后序三种方式实现。  

#  二十、堆排序：使用树型结构来做的排序。  
       大顶堆：是完全二叉树，每个节点都大于或等于左右子节点的值  
       小顶堆：是完全二叉树，每个节点都小于或等于左右子节点的值。  
           注意：左右节点的值的大小没有要求。  
           一般升序使用大顶堆，降序使用小顶堆排序。  
       思想分析：将待排序序列构造成一个大顶堆  
               此时，整个序列的最大值就是堆顶的根节点。  
               将其与末尾元素进行交换，此时末尾就为最大值  
               然后将剩余n-1个元素重新构造成一个堆，这样就得到n个元素的次小值。如此反复执行，就能得到一个有序序列。  
          即：先构成一个无序的完全二叉树，先找左边最后一个非叶子节点，跟他的两个叶子节点比较，大的值变成非叶子节点，小的值变成叶子节点，  
             所有的左子树和右子树从底层往高处依次这样处理，就能在最上层得到最大值了，然后将根子节点跟最下层的最右边的叶子节点交换，  
             然后将这个叶子节点提起出来，放到数组的最后一位，以此类推，就排好序了。  

#  二十一、赫夫曼树：  
        给定n个权值作为n个叶子节点，构造一颗二叉树，如该树的带权路径长度（wpl）达到最小，某个叶子节点带权路径长度为即叶子节点的值乘以路径长度，根节点的路径长度为0，其它各层往下加1，也称最优二叉树。即权值越大，越靠前根节点。  
        树的带权路径长度（WPL):所有叶子节点带权路径长度之和。  
        构建的步骤：  
           1） 从小到大进行排序，将每个数据，每个数据都是一个节点，每个节点都可以看成是一颗最简单的二叉树。  
           2）取出根节点权值最小的二叉树。  
           3）组成一颗新的二叉树，该新的二叉树的根节点的权值是前面两颗二叉树根节点权值之和。  
           4）再将这颗新的二叉树，以根节点的权值大小进行再次排序（即跟剩余的数据排序），不断重复1-2-3-4的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树。  
        赫夫曼编码广泛用于数据文件的压缩，压缩率通常在20%-90%之间，是可变字长编码。  

#  二十二、二叉排序树  
        也称：BST: 对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。如果相等，左右都可以放。  
        删除节点时要注意删除根节点的情况。  
#  二十三、平衡二叉树 （AVL树）  
        是一种特殊的二叉排序树，为了解决二叉排序树可能变成一个类似链表的结构的问题。  
        特点：它是一颗空树或它的左右两个子树的高度差绝对值不超过1，并且左右两个子树都是一颗平衡二叉树。  
        常用的实现方法有：红黑树、AVL、替罪羊树、Treap、伸展树等。  
        构建平衡二叉树：左旋转：6是4的右子节点，5是6的左子节点，7是6的右子节点。 复制一份6,复制的6左子节点指到5，右子节点指到7,4节点的右子节点指到5， 原始的6节点没有谁指到，会被回收掉。  
                     右旋转跟左旋转类似。画图更好理解。  

#  二十四、多叉树：  
     二叉树的缺点：当海量数据时，io次数太多，高度太多，导致速度变慢。  
     B树：一个节点多个数据，B指Balanced,平衡树的意思。  
     2-3树：最简单的B树  
       特点：1）2-3树的所有叶子节点都在同一层（只要是B树都满足这个条件）  
            2）有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点  
            3）有三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点  
            4）2-3树是由二节点和三节点构成的树。  
     2-3-4树：  
     B+树： 所有的数据都在叶子节点，其他子节点的是索引，常用于数据库和文件系统。  
     B*树： 在B+树的基础上，兄弟节点之间有指针  

#  二十五、图  
     图：多对多之间的关系。  
     概念：顶点、边、路径、无向图、有向图、带权图  
     图的表示有两种：二维数组表示（邻接矩阵，1表示可以直连，0表示不能直连），链表表示（邻接表）-数组加链表构成（1表示可以直连，0表示不能直连）  
     图的深度优先遍历：a所有连接找出，b的所有连接找出并排除连接a的线。  
     图的广度优先遍历。  
 
#  二十六、二分查找算法（非递归） BinarySearchNoRecur.java  
      条件：有序数组。  

#  二十七、分治算法：将复杂的问题分成多个相同或相似的子问题 Hanoitower.java  
        解决一下经典的问题  
           二分搜索  
           大整数乘法  
           棋盘覆盖  
           归并排序  
           快速排序  
           线性时间选择  
           最接近点对问题  
           循环赛日程表  
           汉罗塔：三根柱子，64根圆盘，从a柱移动到c柱，要求大盘必须在小盘的上面。思想：将除最下面以上的盘移到b柱，再将最下面的移到c柱，剩下的以此类推。  

#  二十八、动态规划算法：背包问题  
        有一个背包，容量为4磅，现有如下物品  
           物品        重量       价格  
           吉他         1         1500  
           音响         4         3000  
           电脑         3         2000  
         要求达到的目标为装入的背包的总价值最大，并且重量不超出  
         要求装入的物品不能重复  

         思想：将大问题分成小问题解决，从而获得最优解，使用填表的方式解决（行：吉他、音响、电脑。竖：0、1、2、3、4，算出每个格子不超过磅数的最大价值）。  
         跟分治算法的区别：动态规划算法分成的子问题之间往往不是相互独立的。  

#  二十九、KMP算法：字符串查找算法 KMPAlgorithm.java  
     使用场景：字符串匹配问题：一个字符串是否可以在另外一个字符串中找到匹配的位置。  
 
#  三十、贪心算法： GreedyAlgorithm.java   
       使用场景：集合覆盖问题： 不一定是最优结果，但是都是相对接近最优的结果  
       选择最少的广播台，覆盖所有的地区  
       广播台         覆盖的地区  
       k1            北京、上海、天津  
       k2            广州、北京、深圳  
       k3            成都、上海、杭州  
       k4            上海、天津  
       k5            杭州、大连  
       步骤：  
         1）遍历找最多未覆盖的地区的电台。  
         2）将该电台加入集合中，下一次比较是去掉该电台覆盖的地区  
         3）重复前面的步骤，直到覆盖全部地区。  

#  三十一、普里姆算法：修路问题。 PrimAlgorithm.java  ---- 最小生成树  
       场景：各个村庄修路，村村直接路的长度不一样，怎样修最短。  
       思路：尽可能线路最少，路的长度最小。  
            1）找出A村庄跟相邻村庄那条最小如B。  
            2）找到A和B两个村庄相邻的最小路径（除去A-B），如C  
            3)以此类推。  

#  三十二、克鲁斯卡尔算法：公交站问题     KruskalCase.java    -------最小生成树  
       场景：7个站点：ABCDEFG, 修路连通，需要各个站点都能连通，不产生回路，里程最短。  
       思路：按顺序找出最短的边，但如果这条边的两个顶点都用过，则忽略找下一个最小边。  

#  三十三、迪杰斯特拉算法： --- 最短路径问题   
        场景：邮差去各个村庄的最短距离。  

#  三十四、弗洛伊德算法 --- 最短路径问题  

#  三十五、马踏棋盘算法