1. 概念
   1. 数据
      1. 用于描述客观事物的数值、字符，以及一切可以输入到计算机中的并由计算机程序加以处理的符号的集合
   2. 数据元素
      1. 数据的基本单位，通常作为一个整体进行考虑和处理
   3. 数据项
      1. 是数据的不可分割的最小单位，一个数据元素可由若干个数据项组成
   4. 数据对象
      1. 性质相同的元素的集合叫做数据对象
   5. 数据结构指的是数据元素之间的相互关系，这种关系是抽象的，即并不涉及数据元素的具体内容。是数据元素及其相互间的关系的数学描述
2. 逻辑结构
   1. 线性结构
      1. 集合
      2. 线性
   2. 非线性
      1. 树
         1. 树
            1. 定义
            2. （n≥0）个有限数据元素的集合
            3. 结点的度数
            4. 结点的非空子树（即后缀）个数叫作结点的度数
            5. 树叶、分支结点
            6. 左（右）子树均为空二叉树的结点称作树叶否则称作分支结点
            7. 结点的层数
            8. 规定根的层数是0，其余结点的层数等于其父结点的层数加1
            9. 树的度数
            10. 树中度数最大的结点度数叫作树的度数
            11. 树林
            12. 是由零个或多个不相交的树所组成的集合
         2. 二叉树
            1. 二叉树的第i层上至有2^i-1个结点
            2. 深度为k的二叉树至多有2^k-1个结点
            3. 满二叉树：深度为k，有2^k-1个结点
            4. 完全二叉树：给满二叉树的结点编号，从上至下，从左至右，n个结点的完全二叉树中结点在对应满二叉树中的编号正好是从1到n
            5. 存储结构
            6. 顺序存储
            7. 二叉链表
            8. 含有n个结点的二叉链表有n+1个空链域
            9. 三叉链表
            10. 二叉树的遍历
            11. 先序
            12. 中序
            13. 后序
            14. 线索二叉树
            15. n个结点的二叉链表中有n+1个空指针，可以利用其指向前驱或后继结点，叫线索，同时需附加一个标志，区分是子树还是线索。
         3. 性质
            1. 叶子结点n0，度为2的结点为n2，则n0 = n2+1
            2. n个结点的完全二叉树深度为[logn]+1
            3. n个结点的完全二叉树，结点按层次编号 有i的双亲是向下取整【2/n】如果i = 1时为根（无双亲）
         4. 存储结构
            1. 双亲表示
            2. 双亲表示法容易求得双亲，但不容易求得孩子
            3. 孩子表示
            4. 孩子表示法容易求得孩子，但求双亲麻烦
            5. 孩子兄弟
            6. 容易求得孩子和兄弟，求双亲麻烦，也可以增加指向双亲的指针来解决
         5. 树转二叉树：根对根，第一个孩子对二叉树左孩子。下一个兄弟对又孩子
         6. 树的遍历
            1. 先根
            2. 后根
            3. 森林的遍历
            4. 先序
            5. 中序
            6. 遍历树、森林、二叉树的关系
            7. 树（先根）-森林（先序）-二叉树（先序） 树（后根）-森林（中序）-二叉树（中序）
         7. 哈夫曼树
            1. 叶子结点带有权值的最小带权路径长度的最优二叉树
            2. 赫夫曼编码(前缀码) 向左分支为0，向右分支为1，从根到叶子的路径构成叶子的前缀编码
      2. 图
         1. 无向图
            1. 完全图
            2. 有1\2 n(n-1)条变得无向图
         2. 有向图
            1. 有向完全图
            2. 具有n（n-1）条弧的有向图
         3. 权
            1. 与图的边或弧相关的数
         4. 顶点的度
            1. 和v相关联的边的数目
         5. 入度
            1. 以顶点v为头的弧的数目
         6. 出度
            1. 以顶点v为尾的弧的数目
         7. 回路或环
            1. 第一个顶点和最后一个顶点相同的路径
         8. 简单回路
            1. 序列中顶点不重复出现的路径
         9. 图的存储
            1. 邻接矩阵
            2. 邻接表
            3. 边(弧)多则需要存储空间多
            4. 十字链表
            5. 十字链表是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来的一种链表。在十字链表中，对应于有向图中每一条弧有一个结点，对应于每个顶点有一个结点
            6. 邻接多重表
         10. 图的遍历
             1. 深度优先
             2. 若从某点出发所有邻接点都已访问过，退回前一个点继续上述过程，若退回开始点，结束
             3. 广度优先
             4. BFS依次从这些邻接点出发，访问它们的所有未被访问的邻接点; 依此类推，直到图中所有访问过的顶点的邻接点都被访问
         11. 生成树和最小生成树
             1. 最小生成树
             2. Kruskal算法
             3. 不构成环的情况下，每次选取最小边
             4. O(n^2)只与顶点个数n有关 与边的数目e无关 适用于稠密图
             5. 普里姆算法
             6. 记V是连通网的顶点集，U是求得生成树的顶点集，TE是求得生成树的边集。普里姆算法： (a)开始时U={v0}，TE=Φ； (b) 计算U到其余顶点V-U的最小代价，将该顶点纳入U，边纳入TE； (c) 重复(b)直到U=V
             7. 只与边的数目e有关 与顶点个数n无关 适用于稀疏图
         12. AOV网
             1. 用顶点表示活动，边表示活动的优先关系的有向图称为AOV网
             2. 拓扑排序：对AOV网络中顶点构造拓扑有序序列的过程
             3. 拓扑排序的方法 (1)在有向图中选一个没有前驱的顶点且输出之 (2)从图中删除该顶点和所有以它为尾的弧
         13. 关键路径AOE网带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间。在工程上常用来表示工程进度计划
             1. 关键路径：从源点到汇点的最长的一条路径，或者全部由关键活动构成的路径
         14. 最短路径
             1. 迪杰斯特拉算法
             2. 求一个顶点到其他各顶点的最短路径
             3. 1、初始化：用起点v到该顶点w的直接边(弧)初始化最短路径，否则设为∞
             4. 2、从未求得最短路径的终点中选择路径长度最小的终点u：即求得v到u的最短路径；
             5. 3、修改最短路径：计算u的邻接点的最短路径，若(v,…,u)+(u,w)<(v,…,w)，则以(v,…,u,w)代替
             6. 4、重复(b)-(c)，直到求得v到其余所有顶点的最短路径
             7. 特点：总是按照从小到大的顺序求得最短路径
             8. 弗洛伊德算法
             9. 求每对顶点之间的最短路径
   3. 概念
      1. 数据结构中描述的是数据元素之间的抽象关系(逻辑关系)，称为逻辑结构
3. 物理结构
   1. 顺序
      1. 线性表
         1. 逻辑上相邻的元素物理上也相邻
         2. 随机访问
         3. 表长为n时，线性表进行插入和删除操作的时间复杂为O(n) 插入一个元素时大约移动表中的一半元素。 删除一个元素时大约移动表的(n-1)/2
         4. 优点，存储密度大，可随机存储，缺点：大小固定；不利于增减节点，存储空间不能充分利用难扩充
   2. 链式
      1. 简言之数据加指针
      2. 顺序表以地址相邻表示关系，链表用指针表示关系
      3. 顺序表，取元素O(1),链表顺序访问取元素O(n)
      4. 顺序表插入删除移动O(n)，链表插入删除O(n)（用于查找定位）
      5. 优点：易于插入删除；可动态申请空间；表容量仅受内存空间限 制 缺点：增加了存储空间的开销；不可以随机存储元素
   3. 栈
      1. 概念
         1. 限定仅在表尾进行插入或删除操作的线性表
      2. 特点
         1. 栈顶：表尾；栈底，表头。特点先进后出，插入入栈，删除出栈
      3. 链栈
         1. 用不带头结点的单链表实现
      4. 顺序栈
         1. 插入和删除操作固定于表尾
   4. 队列
      1. 概念
         1. 先进先出的线性表
      2. 特点
         1. 队尾插入队头删除，先进先出
   5. 数据结构在计算机中的表示（映象）称为存储结构/物理结构
4. 数据运算
   1. 插入
   2. 修改
   3. 删除
   4. 查找
      1. 静态查找
         1. 对查找表只作查找操作的查找表
      2. 动态查找
         1. 查找过程中同时插入表中不含的元素，或者删除查找表中已有的元素的操作的查找表
      3. 顺序查找
         1. 顺序查找又称线性查找，是最基本的查找方法之一。顺序查找既 适用于顺序表，也适用于链表
      4. 二分法（折半）查找
         1. 是一种效率较高的查找方法，但前提是表中元素必须 按关键字有序（按关键字递增或递减）排列
      5. 分块查找
         1. 块内无序、块间有序、如何分块 效率最高
      6. 动态查找表
         1. 二叉排序树查找
            1. 二叉排序树的生成
            2. 二叉排序树(二叉查找树)：或者是一颗空树。或者如下1若它的左子树不空，则左子树上所有的结点的值均小于他的根结点的值。2若右子树不空，则右子树所有结点的值均大于她得根结点的值。3 左右子树也分别为二叉排序树
      7. 哈希表
         1. 哈希函数构造：直接定址法、除留余数法、平方取中法，随机数法，数字分析法
            1. 冲突解决方法：开放定址法、拉链法、公共溢出区法
   5. 排序
      1. 直接插入排序
         1. 每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止
      2. 折半插入排序
      3. 希尔排序
         1. 基本思想：先将整个待排序记录序列分成为若干个子序列分别进行直接插入排序，待整个序列中的记录 基本有序 时在对全体序列进行一次直接插入排序，子序列的构成不是简单的逐段分割，而是将像个某个增量的记录组成一个子序列
      4. 起泡排序
         1. 也称冒泡法，每相邻两个记录关键字比大小,大的记录往下沉（也可以小的往上浮）。每一遍把最后一个下沉的位置记下，下一遍只需检查比较到此为止；到所有记录都不发生下沉时，整个过程结束（每交换一次，记录减少一个反序数
      5. 快速排序
         1. 在当前无序区R[1..H]中任取一个数据元素作为比较的"基准"(不妨记为X)，用此基准将当前无序区划分为左右两个较小的无序区：R[1..I-1]和R[I+1..H]，且左边的无序子区中数据元素均小于等于基准元素，右边的无序子区中数据元素均大于等于基准元素，而基准X则位于最终排序的位置上，即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)，当R[1..I-1]和R[I+1..H]均非空时，分别对它们进行上述的划分过程，直至所有无序子区中的数据元素均已排序为止
      6. 简单选择排序
         1. 每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完
      7. 堆排序
         1. 堆排序是一树形选择排序，在排序过程中，将R[1..N]看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素
      8. 二路归并排序
      9. 基数排序
         1. 主要特点不需要进行关键字间的比较
5. 算法
   1. 概念
      1. 是对特定问题求解步骤的一种描述，它是指令（规则）的有限序列，其中每一条指令表示一个或多个操作
   2. 特征
      1. 有穷
      2. 确定
      3. 可行
      4. 输入
      5. 输出
   3. 描述
      1. 自然语言
      2. 程序语言
      3. 流程图
      4. 伪代码
   4. 算法分析
      1. 问题规模
         1. 时间和空间进行估算
      2. 基本语句
      3. 时间发杂度