数据结构知识点复习

以下内容主要面向保研复试，只包括少部分内容，（图、树），后续会继续补充

数据结构

绪论及基本概念

• 数据结构包含三部分
  • 逻辑结构：从逻辑关系描述
    • 线性
      • 线性表
      • 数组
    • 非线性
      • 树
      • 图
      • 集合
  • 存储结构（物理结构），在计算机中的关系
    • 顺序存储
    • 链式存储
    • 索引存储
    • 散列存储
  • 运算

树

• 基本概念：度、层数、深度，二叉树，什么什么的
• 二叉树的性质：有个奇怪的 n0=n2+1，经过推导的
• 基本操作
  • 树的遍历：前序、中序（二叉树）、后序、层序（广度）
  • 树/森林和二叉树的转化
• 树的存储结构
  • 双亲表示：T data; int parent
  • 孩子表示：
  • 双亲孩子表示
  • 孩子兄弟表示
• 二叉树的存储结构
  • data，左右孩子
  • 二叉列表/三叉列表
• 二叉树的实现（基于二叉链表）
• 哈夫曼树和哈夫曼编码

图

• 图的相关概念
  • （）表示一条边，<>表示一个弧
  • 完全有向/无向 指所有顶点都连上的
  • VG 分别是顶点和边
  • 带权的图叫 网
  • 连通图，任何顶点间都存在路径，对应还有连通分量，是指无向图中的极大连通子图
  • 强连通图，对应有向图中的概念
• 图的存储结构
  • 顺序存储结构：邻接矩阵
  • 链式存储结构：邻接表
  • 十字链表
  • 边集数组
• 图的操作
  • 深度优先遍历，广度优先遍历
• 最小生成树：要走遍所有顶点的
  • 两种算法：Prim 和 Kurskal
• 最短路径：固定两个顶点
  • 两个算法：Dijkstra 和 Floyd
  • D 算法
    • 研究特定顶点到其他顶点，每个点的最短路径
    • 初始化一个数组，存储每个点到特定顶点的距离
    • 将所有顶点划分为已确定和没确定的点，已确定的 距离在数组内 定下来
    • 每次确定一个新的点，以该点相邻的点判断是否更新最短路径