# dataStructure

**Repository Path**: FangWW/dataStructure

## Basic Information

- **Project Name**: dataStructure
- **Description**: review
- **Primary Language**: Java
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2018-01-28
- **Last Updated**: 2020-12-19

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# dataStructure
personal review


``` 
穷举法、分治法、贪心法、动态规划法、回溯法、分枝限界法
1.数据存储的目的是便于数据访问。这个关系就是数据结构
2.算法是计算机解题的模型：输入，输出，顺序执行，跳转，循环，分支，有限步骤。
3.人大脑组织数据的方式 有线，树，图三种逻辑结构，而计算机存储采用顺序，链式和两者混合的方式。前者是概念性的东西，后者是物理实现。
4.线形结构：算法是迭代算法，你只要注意规模最小的情况下不出错，则算法一般不出错
   树形结构：算法是递归算法，你只要运用递归组合的方法，将简单情形组合出复杂情形
                     简单情形不出错，则算法一般不会出错。
   图形结构：DFS：将图按照树形结构来处理，运用递归算法
                     BFS：将图按章线形结构来处理，运用迭代算法
必须会下面几个几个算法：
（线形两个）   
  1.将两个有序表合并为一个表，这个算法的变种很多，可以是链表，顺序表。涉及集合运算，
      归并排序，字符串处理。
  2.将一个顺序表的元素重新划分，左边的较小，右边较大。涉及快速排序，求字符串的逆串。
 （树形若干个）注意：有些可以实现，有些实现不了，可以拿来思考。
  3.前序线索化，递归实现，栈模拟递归，非栈式迭代实现。
  4.中序线索化，递归实现，栈模拟递归，非栈式迭代实现。
  5.后序线索化，递归实现，栈模拟递归，非栈式迭代实现。
  （图形）注意：会画表格，写出算法的逐个步骤即可。
  6.MST:prim,kruskal
  7.short path:Dijkstra ,Floyd
  8.AOV:拓扑排序的DFS，BFS实现
  9.AOE：关键路径

kmp 字符匹配 利用之前已知的数据最大限度跳过绝对不可能匹配上的数据  需要维护一个next数值
　　－　"ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；
　　－　"ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1；
　　－　"ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2

(1)完全二叉树——只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树；
(2)满二叉树——除了叶结点外每一个结点都有左右子叶且叶结点都处在最底层的二叉树,。

各类Tree总结： (二分查找)     
       B树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于走右结点；
       B-树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；
       B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；
       B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3；

树的操作核心在于递归
f(node){
f(node.leftnext)
f(node.rightnext)
}
前中后 遍历 在于打日志的位置

二叉树中的插入，主要分两步：查找、插入 (插入到最后)

AVL树 红黑树???
平衡二叉树，又称AVL树。它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差之差的绝对值不超过1.。
常用算法有：红黑树、AVL树、Treap等。

线索二叉树 中序排列后 将空节点指向前后节点

hash表 通过%取余数 分类 数组下标 相同下标放于链表后面

图成树就是：生成树是将图中所有顶点以最少的边连通的子图。 最少边数量=顶点数-1


BFS，其英文全称是Breadth First Search。 BFS并不使用经验法则算法。从算法的观点，所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中。一般的实验里，其邻居节点尚未被检验过的节点会被放置在一个被称为 open 的容器中（例如队列或是链表），而被检验过的节点则被放置在被称为 closed 的容器中。（open-closed表）


最小生成树
假如有10个点，你可以用9条线把这10个点连起来，不漏掉任何一个点，
然后这9条边的权值最小，就是最小生成树了
就是用小于顶点个数-1的边，连接所有点，权值最小。

HashTable 核心数据 数组 数组元素是linkedlist

自定义 线程池 当没有run可以执行就wait add run后就notifyall 

run(){
if(runlets.size==0){
wait;
}

addRun(run){
runlist.add(run);
notifyall();
}
}

  Collections.synchronizedList(new ArrayList<Object>());
返回新的list 对原list代理包装一层 代理的方法里面全部有synchronized(){调用原list的方法}


再举个例子：当有多个线程读写文件时，读操作和写操作会发生冲突现象，写操作和写操作会发生冲突现象，但是读操作和读操作不会发生冲突现象。

　　但是采用synchronized关键字来实现同步的话，就会导致一个问题：

　　如果多个线程都只是进行读操作，所以当一个线程在进行读操作时，其他线程只能等待无法进行读操作。

　　因此就需要一种机制来使得多个线程都只是进行读操作时，线程之间不会发生冲突，通过Lock就可以办到。

　　另外，通过Lock可以知道线程有没有成功获取到锁。这个是synchronized无法办到的。

　　总结一下，也就是说Lock提供了比synchronized更多的功能。但是要注意以下几点：

　　1）Lock不是Java语言内置的，synchronized是Java语言的关键字，因此是内置特性。Lock是一个类，通过这个类可以实现同步访问；

　　2）Lock和synchronized有一点非常大的不同，采用synchronized不需要用户去手动释放锁，当synchronized方法或者synchronized代码块执行完之后，系统会自动让线程释放对锁的占用；而Lock则必须要用户去手动释放锁，如果没有主动释放锁，就有可能导致出现死锁现象。


&两个操作数中位都为1，结果才为1，否则结果为0
|两个位只要有一个为1，那么结果就是1，否则就为0
~如果位为0，结果是1，如果位为1，结果是0
^两个操作数的位中，相同则结果为0，不同则结果为1
权限a,001 b,010 c,100
给ab a|b 011
是否有a权限 a&ab==a   001&011=001
&检查权限 |给予权限
用一个32位整形参数在保持接口参数数量不变的情况下预留了31个可能的扩展开关位置。

>>除 <<乘 操作数为2的倍数
a*8=a<<3=a*2*2*2
a*9=a*(8+1)=a<<3+a=a*2*2*2+a




概率论和数理统计
线性代数
　　离散的意思就是不连续。一般学的数学的数据范围都是连续的，比如初高中那些函数，通常都说在某某区间内。而离散数学就是不连续的数，比如：1和2，中间的如1.1，1.11，1.1111等数都没有连续。
　　离散数学以研究离散量的结构和相互间的关系为主要目标，其研究对象一般地是有限个或可数无穷个元素；因此它充分描述了计算机科学离散性的特点。