基本概念理解

  • 时间复杂度
    • 时间复杂度是指执行算法所需要的 计算工作量
    • 基本操作:一般位于循环最里层的操作
    • 时间复杂度一般只考虑对于问题规模 n 的增长率(其他因素如使用的程序语言,机器运算速度等因素不可控)
    • O(1) 称为常量阶,O(n)是线性阶,O(n^2)为平方阶
    • 在难以精确计算 基本操作 执行的次数时只需要求出其关于 n 的阶即可,如:(n-1)*(n-2)/2 关于 n 的增长率为 n^2
  • 空间复杂度
    • 是对一个算法在运行过程中临时占用 存储空间大小 的量度
  • 线性表
    • 在数据元素的非空有限集合中:存在唯一一个被称为第一个的元素
    • 存在唯一一个被称为最后一个的元素
    • 除去第一个之外,集合中的每个数据元素均只有一个前驱
    • 除去最后一个之外,集合中的每个数据元素均只有一个后置
    • 线性表的顺序是指用一组地址连续的存储单元依次存储线性表的数据元素
    • 一般情况下,在第 i(1 <= i <= n) 个元素之前插入一个元素时,需要将第 n 至 i (共n - i + 1)个元素向后移动一个位置
    • 一般情况下,删除第 i 个(1 <= i <= n)元素需要将第 i + 1 至 n 共(n - i)个元素向前移动一个位置,这种算法的时间复杂度为 O(n)
  • 线性链表(单链表)
    • 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的(a1,a2,a3,…,an) 对于ai ,除了存储其本身的信息之外,还需要存储一个指示其直接后继的信息叫做指针。最后一个元素没有指针域,用线性链表来表示线性表时,数据元素之间的逻辑关系是由节点中的指针指示的,逻辑上相邻的两个数据元素其存储的物理位置不要求紧邻
    • 在单链表中插入和删除一个元素是不需要移动元素的,只是需要改变指针
  • 循环链表
    • 最后一个节点的指针指向头节点
  • 双向链表
    • 特点:在双向链表中有两个指针域,其一指向直接后继,另一指向直接前驱
    • 有栈顶(表尾,最后一个元素),和栈底(表头,头元素)的概念。后进先出的线性表(LIFO)
  • 队列
    • 和栈相反,队列是一种先进先出(FIFO)的线性表
    • 队列只允许在一端插入元素,在另一端删除元素
    • 允许插入的一端叫做 队尾,允许删除的一端叫:队头
    • 是一种数据结构,可以用来表示层次关系,因表示的样子很像一颗 倒立的树 而得名 在数据结构中的特点,是 一对多(链表是一对一,图是多对多)
    • pic
    • n>0时,根结点唯一
    • 结点拥有的子树数称为结点的度(Degree),度为0的结点称为叶子结点
    • 树的度是树内各结点的度的最大值
    • 结点的层数是从根开始定义起,根为第1层,根的孩子是第2层,以此类推。树中结点的最大层次称为树的深度(Depth)或高度
    • 如果各子树看成从左至右不可互换的,则称为有序树,否则为无序树
    • 森林是互不相交的树的集合,某个结点的子树可以看做是森林
  • 二叉树
    • 每个结点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”
    • 二叉树不存在度大于2的结点
    • 左右子树是有顺序的,即使某结点只有一棵子树,也要区分它是左子树还是右子树
    • 根据上一条,二叉树具有五种基本形态:空二叉树、只有一个根节点、只有左子树、只有右子树、左右子树都有
    • 二叉树第i层上至多有2^(i-1)个结点(i≥1)
    • 深度为k的二叉树至多有(2^k) - 1个结点(k≥1),此时为 满二叉树
  • 二叉树的遍历
    • 只要是按照某种次序依次访问二叉树中所有结点,使得 每个结点被访问且仅被访问一次 就是二叉树的遍历
    • 习惯的方法有四种:前序遍历中序遍历后序遍历层序遍历
    • 前序遍历:先访问根结点,然后前序遍历左子树,再前序遍历右子树 => 注意到这里是一个递归的过程,后面的遍历方法采用的也是这个思想。另外,这个“序”针对的是根结点的访问时机
    • 中序遍历:先中序遍历根结点的左子树,然后访问根结点,再中序遍历右子树
    • 后序遍历:先后序遍历根结点的左子树,然后后序遍历右子树,再访问根结点
    • 层序遍历:从上到下从左到右对结点逐个访问