参考链接

数据结构之数组和链表的区别

算法的时间与空间复杂度

 

1、前言

数据结构与算法是计算机专业必修的一门课

在工作中，免不了要面对一些复杂的业务逻辑，可能有多种方法实现，每种方式的运行效率也可能都不一样，好的数据结构与算法能提升效率，具体体现在时间和空间上

比如，现在有一万个人，要找出姓名叫张三的人，最简单的方式是从头到尾遍历，如果张三是最后一位，则要遍历10000次

如果按字母首字母去查找的话，则首先在10000个人当中找到首字母为Z的人，假如是100个人，那最快的情况也只用遍历100次

这个就是数据结构与算法最简单的例子

 

为什么要学数据结构与算法？

锻炼思维和问题处理能力提高代码效率大厂面试必备

 

学习路线图：

 

 

2、数据和链表的区别

数据特点：

用一块连续的内存存储：空间利用率低，内存要求比较高查询简单，增加和删除困难：从头部插入（后面所有元素向后搬移）和删除（后面所有元素向前搬移）效率低按索引随机访问效率高，为O(1)，从数组首地址向后偏移即可数组的大小是固定的，不能进行动态扩展

 

链表特点：

由一系列结点组成，结点可以动态生成结点包括两部分：数据和指向下一个结点的指针查询慢，插入删除快占用不连续空间（不能随机访问，只能从头到尾遍历），空间利用率高

 

 

3、栈

栈其实是一种受限的线性数据结构，遵循先进后出

术语：

栈顶栈底入栈出栈

 

栈结构的方法：

方法含义push()入栈操作pop()出栈操作getTopElement()返回栈顶的元素，但不会移除栈顶的元素isEmpty()查看栈是否为空size()返回栈内元素的个数toString()以字符串的形式展示栈内的所有元素

 

典型的栈的应用场景：

public class Test { private static Stack<Integer> stack = new Stack<Integer>(); /** * 将十进制n数转化为m进制数 */ public static void fun(int n,int m){ int a = n/m; int b = n%m; stack.push(b); if(a!=0){ fun(a,m); }else{ String s = ""; int l = stack.size(); for (int i = 0; i < l; i++) { s+=String.valueOf(stack.pop()); } System.out.println(s); } } public static void main(String[] args) { fun(17,2); } }

 

4、队列

队列也是一种受限的线性数据结构，遵循先进先出的原则

优先级队列：不遵循先进先出，优先级高的元素，在插入队列的时候可能会排在前面

 

5、链表

单向链表

双向链表

 

6、哈希表

哈希表的由来：

对于数组，如果已知下标i,那么查询一个元素就很快。但是如果不知道下标i,只知道元素的值，那么需要从头开始遍历数组，直到找到这个元素位置

为了解决数组的不足，引入了哈希表，哈希表在很多编程语言中都有实现

将一个值经过哈希函数计算后，再取模，会得到一个下标，好的哈希函数会使哈希冲突的几率很小

 

哈希冲突的解决方法：

拉链法（链地址法）开放地址法（可以理解为，当冲突时，寻找一个空白位置进行插入）线性探测法：从前往后查找，但是如果发生聚集现象（即从前往后查找时，连续好几个位置都不是空白的），则查找下一个空白位置就很慢二次探测：为了解决线性探测的聚集现象，主要做法是：依次移动index+1^2,index+2^2,index+3^2,...个位置，直到找到空白位置再哈希法

    

7、树结构

树结构是平日里我们常见的一种数据结构，例如家族族谱、公司管理层级结构图等，这样的数据结构的存在一定有一定的道理

树是一种非线性数据结构

7.1、树结构的优点：

空间利用率比较高可以非常快速地查找到最大值和最小值

 

7.2、树结构术语

术语名含义结点树中的数据元素结点的度结点拥有的子树个数叶子结点度为0的结点分支结点度大于0的结点父节点衍生出其它结点的结点为这些结点的父结点子结点被某个结点衍生出来的结点为该结点的子结点兄弟结点具有同一个父节点的所有结点为兄弟结点结点的层次设定根结点所在层次为1，其它结点层次为其父节点层次+1树的深度树的所有结点中的最大层次为该树的深度路径从某个结点沿着树的层级关系到达另一个结点之间的路线路径长度路径上的结点个数 -1

 

7.3、二叉树

二叉树的定义： 树结构中每个结点最多只有两个子结点，即任何一个结点的度都小于等于 2

 

7.3.1、完美二叉树（满二叉树）

 

7.3.2、完全二叉树

完全二叉树要满足以下两个条件：

除了最后一层外，其它各层的结点个数都达到最大个数最后一层的结点集中在左侧，且结点连续，只有右侧部分可以缺失结点

 

7.3.3、二叉树特性

第i层结点个数最大为2^(i-1)个，i>=1

深度为k的二叉树总结点个数最大为2^k-1，k>=1