今天面试~问到了简单的数据结构，不知道是紧张还是啥，反正我之前是学习过也做过笔记，但还是没答全，太丢人了。

---

数据结构

基础概念

数据

• 所有能输入到计算机中去的描述客观事物的符号
  • 数值性数据
  • 非数值性数据

数据元素

• 数据的基本单位，也称结点（node）或记录（record）

数据项

• 有独立含义的数据最小单位，也称域(field)

数据对象

数据结构

• 层次
  • 逻辑结构
    • 数据元素间抽象化的相
      互关系，与数据的存储
      无关，独立于计算机
  • 存储结构（物理结构）
    • 数据元素及其关系在计算机
      存储器中的存储方式

逻辑结构

• 线性结构
  • 有且仅有一个开始和一个终端结点
    ，并 且所有结点都最多只有一个直
    接前趋和一个后继。
    例如：线性表、栈、队列、串
• 非线性结构
  • 一个结点可能有多个直接前趋和直
    接后继。
    例如：树、图

存储结构

• 顺序存储结构
  • 借助元素在存储器
    中的相对位置来表
    示数据元素间的逻
    辑关系
• 链式存储结构
  • 借助指示元素存储
    地址的指针表示数
    据元素间的逻辑关
    系

数据类型

• 数据类型是一组性质相同的值的集合, 以及定义于这个集
  合上的一组运算的总称
• 如：char,varchar,String,int

抽象数据类型

• 更高层次的数据抽象
• 由用户定义，用以表示应用问题的数据
  模型
• 由基本的数据类型组成, 并包括一组相关
  的操作

算法

• 时间复杂度
  • 算法中基本语句重复执行的次数是问题规模n的某个函数f(n),算
    法的时间量度记作：T(n)=O(f(n))
  • 随着n的增大，算法执行的时间的增长率和f(n)的增长率相同，
    称渐近时间复杂度。
• 空间复杂度
  • 空间复杂度:算法所需存储空间的度量，
    记作: S(n)=O(f(n))
    其中n为问题的规模(或大小)
  • 随着问题规模的增大，算法所需空间的快慢
• 概要: 复杂度计算
  • 时间复杂度计算（单个循环体）
    • 直接关注循环体的执行次数，设为k
  • 时间复杂度计算（多个循环体）
    • 两个运算规则：乘法规则，加法规则。

线性表

基本

• 线性表的链式存储是指通过一组任意的存储单元来存储线性表中的数据元素。
• 头结点和头指针的区别
  • 不管带不带头结点，头指针始终指向链表的第一个结点，而头结点是带头结点链表中的第一个结点，结点内通常不存储信息
• 为什么要设置头结点
  • 1.处理操作起来方便 例如：对在第一元素结点前插入结点和删除第一结点起操作与其它结点的操作就统一
  • 2.无论链表是否为空，其头指针是指向头结点的非空指针，因此空表和非空表的处理也就统一

顺序表

单链表

双链表

循环链表

静态链表

栈和队列

栈

• 基本
  • 栈（Stack）：只允许在一端进行插入或删除操作的线性表
  • 栈顶（Top）：线性表允许进行插入和删除的那一端
  • 栈底（Bottom）：固定的，不允许进行插入和删除的另一端
• 特点
  • 1.栈是受限的线性表，所以自然具有线性关系
  • 2.栈中元素后进去的必然先出来，即后进先出
• 顺序栈
  • 栈是线性表的特例，那栈的顺序存储也是线性表顺序存储的简化。栈的顺序存储结构也叫作顺序栈
  • 顺序栈的操作
    • 判空
    • 进栈
    • 出栈
    • 读取栈顶元素
• 共享栈
  • 顺序栈的存储空间大小需要事先开辟好，很多时候对每个栈各自单独开辟存储空间的利用率不如将各个栈的存储空间共享
• 链式栈
  • 栈是线性表的特例，线性表的存储结构还有链式存储结构，所以也可以用链表的方式来实现栈。栈的链式存储结构也叫作链栈

队列

• 基本
  • 队列是只允许在一端进行插入，而在另一端进行删除的线性表
  • 队头（Front）：允许删除的一端，又称为队首
  • 队尾（Rear）： 允许插入的一端
  • 先进入队列的元素必然先离开队列，即先进先出（First In First Out）简称FIFO
• 顺序队列
  • 用数组来实现队列，可以将队首放在数组下标为0的位置。
• 循环队列
  • 把数组“掰弯”，形成一个环。Rear指针到了下标为4的位置还能继续指回到下标为0的地方。这样首尾相连的顺序存储的队列就叫循环队列
• 链式队列
  • 队列的链式存储结构，其实就是线性表的单链表，只不过需要加点限制，只能表尾插入元素，表头删除元素

串 、数组和广义表

串

• 零个或多个字符组成的有限序列
• 存储结构
  • 顺序存储
    • 定长顺序存储结构
    • 堆式顺序存储结构
  • 链式存储

数组

广义表

• n (≥0 )个表元素组成的有限序列

树和二叉树

树

• 基本概念

  • 树是递归定义的结构
  • 结点
    • 根节点：树只有一个根结点
    • 结点的度：结点拥有的子树的数量
      • 度为0：叶子结点或者终端结点
      • 度不为0：分支结点或者非终端结点
        • 分支结点除去根结点也称为内部结点
  • 树的度：树中所有结点的度数的最大值

  • 结点关系

    • 祖先结点
      • 根结点到该结点的唯一路径的任意结点
    • 子孙结点

    • 双亲结点

      • 根结点到该结点的唯一路径上最接近该结点的结点
    • 孩子结点

    • 兄弟结点

      • 有相同双亲结点的结点
  • 层次，高度，深度，树的高度
    • 层次：根为第一层，它的孩子为第二层，以此类推
    • 结点的深度：根结点开始自顶向下累加
    • 结点的高度：叶节点开始自底向上累加
    • 树的高度（深度）：树中结点的最大层数
• 存储结构
  • 顺序存储结构
    • 双亲表示法：用一组连续的存储空间存储树的结点，同时在每个结点中，用一个变量存储该结点的双亲结点在数组中的位置。
  • 链式存储结构
    • 孩子表示法
      • 把每个结点的孩子结点排列起来存储成一个单链表。所以n个结点就有n个链表；
        如果是叶子结点，那这个结点的孩子单链表就是空的；
        然后n个单链表的的头指针又存储在一个顺序表（数组）中。
    • 孩子兄弟表示法
      • 顾名思义就是要存储孩子和孩子结点的兄弟，具体来说，就是设置两个指针，分别指向该结
        点的第一个孩子结点和这个孩子结点的右兄弟结点

二叉树

• 定义
  • 二叉树是n（n≥0）个结点的有限集合
  • 每个结点最多有两棵子树
  • 左右子树有顺序
• 性质
  • 非空二叉树上叶子结点数等于度为2的结点数加1
  • 非空二叉树上第K层上至多有2^k−1个结点（K≥1）
  • 高度为H的二叉树至多有2^H-1个结点（H≥1）
  • 具有N个（N>0）结点的完全二叉树的高度为 [log2(N+1)]或[log2N] +1
• 五种基本形态
  • 空树
  • 只有一个根结点
  • 根结点只有左子树
  • 根结点只有右子树
  • 根结点既有左子树又有右子树
• 特殊二叉树
  • 斜树
  • 满二叉树
  • 完全二叉树
• 存储结构
  • 顺序存储
    • 二叉树的顺序存储结构就是用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素
  • 链式存储
    • 二叉树每个结点最多两个孩子，所以设计二叉树的结点结构时考虑两个指针指向该结点的两个孩子
• 遍历
  • 先序遍历
    • 访问根结点
    • 先序遍历左子树
    • 先序遍历右子树
      • 递归
      • 非递归
  • 中序遍历
    • 中序遍历左子树
    • 访问根结点
    • 中序遍历右子树
      • 递归
      • 非递归
  • 后序遍历
    • 后序遍历左子树
    • 后序遍历右子树
    • 访问根结点
      • 递归
      • 非递归
  • 层次遍历
    • 若树为空，则什么都不做直接返回
    • 否则从树的第一层开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问

线索二叉树

• N个结点的二叉链表，每个结点都有指向左右孩子的结点指针，所以一共有2N个指针，而N个结点的二叉树一共有N-1条分支，也就是说存在2N-(N-1)=N+1个空指针。比如左图二叉树中有6个结点，那么就有7个空
• 大量的空余指针能否利用起来
  • 指向前驱和后继的指针称为线索，加上线索的二叉链表就称为线索链表，相应的二叉树就称为线索二叉树
  • 对二叉树以某种次序遍历使其变为线索二叉树的过程就叫做线索化

哈夫曼树和哈夫曼编码

• 算法的描述如下：
  1）将这N个结点分别作为N棵仅含一个结点的二叉树，构成森林F。
  2）构造一个新结点，并从F中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值
  置为左、右子树上根结点的权值之和。
  3）从F中删除刚才选出的两棵树，同时将新得到的树加入F中。
  4）重复步骤2）和3），直至F中只剩下一棵树为止。

图

基本概念

• 定义
  • 树是N（N≥0）个结点的有限集合，N=0时，称为空树，这是一种特殊情况。在任意一棵非空树中应满足：
    1）有且仅有一个特定的称为根的结点。
    2）当N>1时，其余结点可分为m（m>0）个互不相交的有限集合T1，T2，…，Tm，其中每一个集合本身又是一棵树，并且称为根结点的子树
• 分类
  • 有向图
    • 有向边（弧）的有限集合
  • 无向图
    • 无向边的有限集合
  • 简单图
    • 1.不存在顶点到自身的边
    • 2.同一条边不重复出现
  • 多重图
    • 若图G中某两个结点之间的边数多于一条，又允许顶点通过通过同一个边和自己关联
  • 完全图
    • 无向完全图
      • 如果任意两个顶点之间都存在边
    • 有向完全图
      • 如果任意两个顶点之间都存在方向相反的两条弧

遍历

• 深度优先遍历
  • 深度优先搜索(DFS:Depth-First-Search):深度优先搜索类似于树的先序遍历算法
• 广度优先遍历
  • 广度优先搜索(BFS:Breadth-First-Search):广度优先搜索类似于树的层序遍历算法

存储结构

• 邻接矩阵（顺序存储）
• 邻接表（链式存储）
  • 十字链表（有向图）
  • 邻接多重表（无向图）

排序

基本知识

• 定义
  • 排序就是将原本无序的序列重新排列成有序的序列
• 稳定性
  • 如果待排序表中有两个元素Ri、Rj，其对应的关键字keyi=keyj，且在排序前Ri在Rj前面，如果使用某一排序算法排序后，Ri仍然在Rj的前面，则称这个排序算法是稳定的，否则称排序算法是不稳定的

插入类排序

• 直接插入排序
  • 首先以一个元素为有序的序列，然后将后面的元素依次插入到有序的序列中合适的位置直到所有元素都插入有序序列
  • 时间复杂度为O(n)
  • 直接插入排序是稳定性是稳定的
• 折半插入排序
  • 折半插入排序将比较和移动这两个操作分离出来，也就是先利用折半查找找到插入的位置，然后一次性移动元素，再插入该元素
  • 折半插入排序的时间复杂度为O(n^2)
  • 稳定性：和直接插入排序稳定性相同，是稳定的
• 希尔排序
  • 希尔排序本质上还是插入排序，只不过是把待排序序列分成几个子序列，再分别对这几个子序列进行直接插入排序

交换类排序

• 冒泡排序
• 快速排序

选择类排序

• 简单选择排序
• 堆排序

归并排序

基数排序

外部排序

查找

基本概念

• 在数据集合中寻找满足某种条件的数据元素的过程称为查找

折半查找

• 算法思路
  • 首先将给定值key与表中中间位置元素的关键字比较，若相等，则查找成功，返回该元素的存储位置；若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分中。然后在缩小的范围内继续进行同样的查找，如此重复直到找到为止，或者确定表中没有所需要查找的元素，则查找不成功，返回查找失败的信息。

分块查找

• 分块查找又称为索引顺序查找
• 分块查找思想
  • 确定待查找值在哪个块（折半查找）
  • 在确定的块中查找待查找值（顺序查找）

二叉排序树

• 二叉排序树(Binary Search Tree 也叫二叉搜索树)或者是一棵空树，或者是具有以下性质的二叉树
  ①若左子树不空，则左子树上所有结点的值均小于它的根结点的值。
  ②若右子树不空，则右子树上所有结点的值均大于它的根结点的值。
  ③它的左右子树也是一棵二叉排序树。

平衡二叉树(AVL树)

• 平衡二叉树(AVL树)是特殊的二叉排序树，特殊的地方在于左右子树的高度之差绝对值不超过1，而且左右子树又是一棵平衡二叉树

B树和B+树

• 2-3树
  • 2-3树是一种多路查找树：2和3的意思就是2-3树包含两种结点
• 2-3-4树
  • 2-3-4树也是一种多路查找树：2和3和4的意思就是2-3-4树包含三种结点
• B树
  • B树也是一种平衡的多路查找树，2-3树和2-3-4树都是B树的特例，我们把树中结点最大的孩子数目称为B树的阶。通常记为m
• B+树
  • B+树是常用于数据库和操作系统的文件系统中的一种用于查找的数据结构

散列表

根据给定的关键字来计算出关键字在表中的地址的数据结构。也就是说，散列表建立了关键字和存储地址之间的一种直接映射关系