logo头像
ICQL

110_数据结构与算法

相关源码

https://gitee.com/icql/icql-java/tree/master/datastructure
https://github.com/icql/icql-java/tree/master/datastructure
https://gitee.com/icql/icql-java/tree/master/algorithm
https://github.com/icql/icql-java/tree/master/algorithm

什么是数据结构和算法

  • 概念
    • 数据结构:指一组数据的存储结构
    • 算法:操作数据的一组方法
  • 逻辑结构:数据对象中的数据元素之间的相互关系
    • 集合结构:各个数据元素是平等的
    • 线性结构:1对1
    • 树形结构:1对多
    • 图形结构:多对多
  • 物理结构:数据的逻辑结构在计算机中的存储形式
    • 顺序存储结构:把数据元素存放在地址连续的存储单元里
    • 链式存储结构:把数据元素存放在任意的存储单元里,这些存储单元可以是连续的,也可以是不连续的

总览图

复杂度分析(时间/空间)

1)大O复杂度表示法

  • 渐进表示法(随入参增大的趋势分析)
  • 分析原则
    • 只关注循环执行次数最多的一段代码
    • 加法法则:总复杂度等于量级最大的那段代码的复杂度
    • 乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
  • 单参数:
    • O(1)常数阶 < O(logn)对数阶 > < O(n)线性阶 < O(nlogn)线性对数阶 < O(n^2)平方阶 < O(n^3)立方阶 < O(2^n)指数阶
  • 多参数:
    • O(m+n) < O(m*n)

2)时间复杂度分析

  • 时间耗费与输入n的关系(用大O法表示渐进时间复杂度)
    • 最好情况时间复杂度
    • 最坏情况时间复杂度
    • 平均情况时间复杂度
    • 均摊时间复杂度

3)空间复杂度分析

  • 内存占用与输入n的关系(用大O法表示渐进空间复杂度)

线性表

  • 定义:0个或多个数据元素的有限序列
  • 存储:顺序存储(数组),链式存储(链表)

1)数组

  • 用一组连续的内存空间,来存储一组具有相同类型的数据
  • 特点
    • 随机访问(用索引访问)
    • 新增/删除需要移动大量元素(优化措施:将多次删除集中到1次删除,jvm的标记清除垃圾回收算法)
    • 数组/容器选择:性能要求较高优先数组
    • 数组索引从0开始而非1的原因,cpu少了一次减法操作
      • 若1开始,a[k] = a[1]_addr + (k-1)*type_size
      • 若0开始,a[k] = a[0]_addr + k*type_size

2)链表

  • 不需要连续的内存空间,使用零散的内存块存储数据
  • 单链表:头结点(data,next) -> Node(data,next) -> … -> 尾结点(data,next(null))
  • 循环链表:头结点(data,next) -> Node(data,next) -> … -> 尾结点(data,next(头结点))
  • 双向链表:头结点(data,prev(null),next) -> Node(data,prev,next) -> … -> 尾结点(data,prev,next(null))
  • 哨兵简化边界处理,带头链表,不带头链表
    1
    2
    3
    4
    5
    单链表反转
    链表中环的检测
    两个有序的链表合并
    删除链表倒数第 n 个结点
    求链表的中间结点

3)栈

  • 定义:限定仅在一端进行插入和删除的线性表,FILO(first in last out)
  • 主要功能:入栈push,出栈pop
  • 递归

4)队列

  • 定义:只允许在一端(队尾)进行插入操作,在另一端(队头)进行删除操作的线性表,FIFO(first in first out)
  • 主要功能:入队,出队
  • 阻塞队列:队列为空,阻塞出队直到有数据,队列满了,阻塞入队直到队列有空闲
  • 并发队列:线程安全
  • 各种资源池

散列表

  • 1、定义:树是n个结点的有限集
  • 2、基本概念:
    • 1)结点的度:结点的子项个数
    • 2)树的度:结点度中的最大值
    • 3)祖先
    • 4)双亲(父结点)
    • 5)孩子
    • 6)树的深度:树的最大层次
    • 7)森林:m个互不相交的树的集合
  • 3、特点:
    • 1)根结点:无双亲,唯一
    • 2)叶结点:无孩子
    • 3)中间结点:一个双亲,多个孩子
  • 4、树的存储结构
    • 1)双亲表示法:数据项(data | parent)
      • (1)求结点的双亲:直接可以找到
      • (2)求结点的孩子:遍历整个结构
    • 2)孩子表示法:n个结点的树用1个顺序数组和n个单链表来存储。顺序数组存储所有结点,数据结构(结点数据data | firstchild指针),n个单链表数据项结构(结点数据data | next结点指针)
      • 1)求结点的双亲:遍历整个结构
      • 2)求结点的孩子:直接可以得到
    • 3)双亲孩子表示法:结合双亲表示法和孩子表示法。在孩子表示法的基础上,在数组的数据结构增加 parent指针
      • 案例:数据库表设计,菜单(id,parentid,childernid)
    • 4)孩子兄弟表示法:任意一颗树,它的结点的第一个孩子如果存在就是的,它的右兄弟如果存在也是唯一的。因此,我们设置两个指针,分别指向该结点的第一个孩子和此结点的右兄弟

1)二叉树

  • 1、定义:每个结点最多有两棵子树,所以二叉树中不存在度大于2的结点;左右子树是有顺序的,即使只有一棵子树
  • 2、特殊二叉树:
    • 1)满二叉树:除了叶子之外所有子树都有左右孩子,且叶子均在同一层次上
    • 2)完全二叉树:一棵二叉树,除了最后一层之外都是完全填充的,并且最后一层的叶子结点要么都有要么只有左边
  • 3、二叉树的性质:
    • 1)第i层上最多有 2^(i-1)个结点
    • 2)深度为k的二叉树最多有(2^k - 1)个结点
    • 3)终端结点数为n0,度数为2的结点数n2,则 n0 = n2 + 1
    • 4)具有n个节点的完全二叉树深度为 log2 n +1
    • 5)具有n个节点的完全二叉树深度为 log2 n +1,1 <= i <= n
      • (1)i=1,结点i是二叉树的根,无双亲
      • (2)i>1,其双亲是结点 i/2
      • (3)i>n/2,则结点i无左孩子,否则左孩子是结点 2i
      • (4)2i+1>n,则结点i无右孩子,否则其右孩子是结点 2i+1
  • 4、二叉树的存储结构:
    • 1)顺序存储:从根开始,按照每层从左到右依次存储,普通的二叉树若结点不是2个孩子,则以null代替,但这样比较浪费空间,所以一般只有完全二叉树使用顺序存储(数组)
    • 2)二叉链表:结点数据结构(data数据项 | lchild | rchild)
      • 线索二叉树:利用二叉链表中的空指针域,存放指向结点在某种遍历次序下的前驱和后继结点的指针(这种附加的指针称为”线索”)
        • 数据结构(data数据项 | lchild | ltag | rchild | rtag)
        • ltag为0表示左孩子,为1表示前驱;rtag为0表示右孩子,为1表示后继
    • 3)三叉链表:结点数据结构(data数据项 | parent | lchild | rchild)
  • 5、遍历二叉树
    • 1)前序遍历:从根结点开始,先一直从左孩子向下遍历,再右孩子向上遍历,再左孩子向下遍历,依次进行,类似斜着遍历
    • 2)中序遍历:从最后一层开始,先左孩子,再双亲结点,再右孩子,依次遍历
    • 3)后序遍历:从最后一层开始,先左孩子,再右孩子,再双亲结点,依次遍历
    • 4)层序遍历:从根节点开始,每层从左到右依次遍历

  • 1、定义:实现多对多的有限顶点之间关系的结构

递归

微信打赏

赞赏是不耍流氓的鼓励