第一章 绪论

基本概念

数据结构（这门学科）： 是一门研究数据的组织， 存储， 和运算的一般方法。

数据： 是客观事物的符号表示， 是所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素： 是数据的基本单位， 在计算机中通常作为一个整体进行考虑和处理。数据元素用于完整地描述一个对象。

数据项： 组成数据元素的、 有独立含义的、 不可分割的最小单位。例如 ：学生的姓名学号等。

数据对象： 是性质相同的数据元素的集合， 是数据的一个子集。只要集合内的性质均相同， 都可称之为一个数据对象。

数据结构： 是相互之间存在一种或多种特定关系的数据元素的集合。

数据结构

  • 逻辑结构
    • 集合结构（离散结构， 因为太简单， 所以不考虑）
    • 线性结构
    • 非线性结构
      • 树结构
      • 图结构或网状结构
  • 存储结构
    • 顺序存储结构
    • 链式存储结构

逻辑结构
二元组 （D， R）

  • D是数据关系的集合
  • R是D关系上的集合
    （） 代表无序 <> 代表有序

抽象数据类型

抽象数据类型 ： 一般指由用户定义的、 表示应用问题的数学模型， 以及定义在这个模型上的一组操作的总称。
具体包括三部分： 数据对象， 数据对象上关系的集合 以及 对数据对象的基本操作的集合。
定义格式：

1
2
3
4
5
ADT 抽象数据类型名{
    数据对象:<数据对象的定义>
    数据关系:<数据关系的定义>
    基本操作:<基本操作的定义>
} ADT 抽象数据类型名

算法

算法 ：是为了解决某类问题而规定的一个有限长的操作序列。
重要特性

  • 有穷性
  • 确定性
  • 可行性
  • 输入
  • 输出

评价算法优劣的基本标准

  • 正确性 能在有限的运行时间内得到正确的结果。
  • 可读性
  • 健壮性
  • 高效性 时间空间

语句频度： 一条语句重复执行的次数

算法的时间复杂度： （一般指的是最坏时间复杂度）

  • 常量阶实例 
    1
    2
    3
    for (int i = 1; i <= 100000000; i++){
        puts("我爱你啊亲！");
    }
    此算法时间复杂度 T(n) = O(1)。

算法的空间复杂度

  • 常量阶
    1
    2
    3
    4
    5
    for (int i = 0; i <= n / 2; i++){
        t = a[i];
        a[i] = a[n - i + 1];
        a[n - i - 1] = t;
    }
  • 线性阶
    1
    2
    3
    4
    for (int i = 0; i < n; i++)
        b[i] = a[n - i + 1];
    for (int i = 0; i < n; i++)
        a[i] = b[i];
    此算法需要借助大小为n的辅助数组， 所以其空间复杂度为O(n)。

第二章 线性表

线性表： 由n（n >= 0）个数据特性相同的元素构成的有限序列。
空表： n = 0的线性表。

非空的线性表或线性结构的特点：
（1） 存在唯一的一个被称作“第一个”的数据元素；
（2） 存在唯一的一个被称作“最后一个”的数据元素；
（3） 除第一个元素外， 结构中的每个数据元素均只有一个前驱；
（4） 除最后一个元素外， 结构中的每个数据元素均只有一个后继。

顺序表

线性表的顺序存储结构是一种随机存取的存储结构。

平均查找长度： 在查找时， 为确定元素在顺序表中的位置， 需和给定的值进行比较的数据元素个数的期望值称为查找算法在查找成功时的平均查找长度（Average Search Length ASL）

  • 假设pi 是查找第i个元素的概率， Ci 为找到其中关键字与给定值相等的第i个记录时， 和给定值已进行过比较的关键字个数， 则在长度为n的线性表中， 查找成功时的平均查找长度为ASL = piCi （i : 1 - n 之和）

链表

链表这东西没什么好说的， 会一些基本的操作就行。

待解决的问题

把链表的基本操作写一下。

第三章 栈和队列

栈 （后进先出的数据结构（Last In First Out, LIFO））

栈顶， 栈底。

  • 顺序栈
  • 链栈
  • 递归*：
  1. 定义是递归的 比如： 阶乘，二阶Fibonacci数列
    • 分治法：
    • 能将一个问题变成一个新问题， 而新问题与原问题的解法相同或类同， 不同的仅是处理的对象， 并且这些处理对象更小且变化有规律。
    • 可以通过上述转化而使问题简化。
    • 必须有一个明确的递归出口， 或称递归的边界。
  2. 数据结构是递归的 比如： 链表
  3. 问题的解法是递归的 比如： Hanoi塔问题， 八皇后问题， 迷宫问题

递归的算法效率分析：通过迭代法求解递归方程来计算时间复杂度。

队列 （先进先出的数据结构（First In First Out, FIFO））

队头， 队尾

  • 顺序队列（循环队列）
    少用一个元素空间；
    队空的条件： Q.front == Q.rear
    队满的条件： (Q.rear + 1) % MAXQSIZE == Q.front

  • 链队

遗留的问题

链栈， 顺序队， 链队的代码

第四章 串、数组和广义表

串（或字符串）

串的模式匹配算法

  1. BF算法（Brute-Force）
    就是暴力、这个 太简单就不写代码了。
  2. KMP算法
    最主要的是如何构造next数组和nextval数组
    • next数组（模式串）：
    1. 0 j = 1
    2. max k(1 < k < j) ‘p1 p2 … p(k - 1)’ == ‘p(j - k + 1) … p(j - 2) p(j - 1)’
      通俗的来说 就是看 j 前面的 k - 1（1 < k < j）字符 和 从 1 到k - 1的字符是不是一样
    3. 1 一个字符都不匹配
    • nextval数组
    1. 求出next数组
    2. 根据next数组判断 s[j] ?= s[next[j]]
      如果相等 nextval[j] = next[next[j]]
      如果不想等(不相等) nextval[j] = next[j]

数组

数组很简单就不说了

广义表

就把一些基本的定义弄熟就行了
广义表一般记作LS = (a1, a2, a2, ..., an) 其中LS是这个广义表的名称， n为其长度。
ai 可以是单个元素， 也可以是广义表 分别称为 广义表LS的原子和字表。
习惯上， 用大写字母表示广义表的名称， 用小写字母表示原子。
显然， 广义表的定义是一个递归的定义， 因为在描述广义表时又用到了广义表的概念。
例子

  1. A = () —— A是一个空表， 其长度为0。
  2. B = (e) —— B只有一个原子e，其长度为1。
  3. C = (a, (b, c, d)) —— C的长度为2， 两个元素分别为原子a和字表(b, c, d)。
  4. D = (A, B, C) —— D的长度为3， 三个字表都是广义表。
  5. E = (a, E) —— 这是一个递归表， 长度为2。E 相当于一个无限的广义表 E = (a, (a, (a, …)))。

概念

  • 表头（是一个元素）： 为非空广义表的以一个元素， 它可以是一个原子也可以是一个子表。
  • 表尾（是一个广义表）：除表头之外， 由其余元素构成的表。（若只有一个元素， 那么其为空表）。

遗留的问题

  1. KMP算法的实现

第五章 树和二叉树

树

树： 是n（n >= 0）个结点的有限集， 它或为空树；或为非空树， 对于非空树T：

  1. 有且仅有一个称之为根的结点。
  2. 除根结点以外的其余结点可分为m(m > 0) 个互不相交的有限集T1, T2, …, TM, 其中每一个集合本身又是一棵树， 并且称之为根的子树（SubTree）。

树的基本术语

  1. 结点：树中的一个独立单元。包含一个数据元素及若干指向其子树的分支 。
  2. 结点的度： 结点拥有的子树数。（这个结点后继的个数）。
  3. 树的度： 树内各结点度的最大值。
  4. 叶子： 度为0的结点称为叶子结点或者终端结点。
  5. 非终端结点： 度不为0的结点称为非终端结点或者分支结点。 除根结点以外， 非终端结点也称为内部结点。
  6. 双亲和孩子： 结点的子树的根称为该结点的孩子， 相应地， 该结点称为孩子的双亲。
  7. 兄弟： 同一个双亲的孩子之间互称兄弟。
  8. 祖先： 从根到该结点所经分支上的所有结点。
  9. 子孙： 以某结点为根的子树中的任一结点都称为该结点的子孙。
  10. 层次： 结点的层次从根开始定义起， 根为第一层， 根的孩子为第二层。 树中任一结点的层次等于其双亲结点的层次加一。
  11. 堂兄弟： 双亲在同一层的结点互为堂兄弟。
  12. 树的深度： 树中结点的最大层次称为树的深度或高度。
  13. 有序树和无序树： 如果将树中结点的各子树看成从左到右是有次序的， 则称该树为有序树， 否则称为无序树。
  14. 森林： 是m(m >= 0) 课互不相交的树的集合。

二叉树

二叉树：是n (n >= 0) 个结点所构成的集合。对于非空树T：

  1. 有且仅有一个称之为根的结点。
  2. 除根结点外的其余结点分为两个互不相交的子集T1 和T2， 分别称为T的左子树和右子树。
  • 二叉树与树的区别
    1. 二叉树每个结点至多只有两棵子树。
    2. 二叉树是有序树。
  • 二叉树的性质
    1. 在二叉树的第i层上至多有2 ^ (i - 1) 个结点（i >= 1）。
    2. 深度为k的二叉树至多有2 ^ k - 1个结点。
    3. 对任何一棵二叉树T， 如果其终端结点数为n0， 度为2的结点数为n2， 则n0 = n2 + 1。
  • 证明*：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    设B为总分支数
    二叉树结点总数
    n = n0 + n1 + n2
    除了根结点外， 每一个结点都有一个分支进入则
    n = B + 1
    由于这些分支是由度为1 和度为2 的结点射出的，所以
    B = n1 + 2 * n2
    于是得
    n = n1 + 2* n2 + 1
    所以
    n0 = n2 + 1

对于任意一棵树：

1
2
3
4
5
6
7
8
9
10
树的总结点个数为
n = n1 + n2 + ... + nk
除了根结点外， 每一个结点都有一个分支进入则
n = B + 1
由于这些分支是由度为1 ， 度为2， ...， 度为k的结点射出的， 所以
B = n1 + 2 * n2 + 3 * n3 + ... + k * nk
于是得
n = n1 + 2 * n2 + 3 * n3 + ... + k * nk + 1
所以
n0 = 1 + n2 + 2 * n3 + ... + (k - 1) * nk
  • 满二叉树： 深度为k且含有2 ^ k - 1个结点的二叉树。
  • 完全二叉树： 深度为k的， 有n个结点的二叉树， 当且仅当其每一个结点都与深度为k的满二叉树中编号从1 - n 一一对应时， 称为完全二叉树。
    • 特点
    1. 叶子节点只可能在层次最大的两层上出现（第k层和第k - 1层）；
    2. 对任一结点， 若其右分支下的子孙的最大层次为l， 则其左分支下的子孙的最大层次必为l 或 l + 1 。
  1. 具有n个结点的完全二叉树的深度为 (向下取整)[log2 n] + 1。

遍历二叉树和线索二叉树

遍历二叉树

  • 前序（先序）遍历
    1. 访问根结点
    2. 先序遍历左子树
    3. 先序遍历右子树
  • 中序遍历
    1. 中序遍历左子树
    2. 访问根结点
    3. 中序遍历右子树
  • 后序遍历
    1. 后序遍历左子树
    2. 后序遍历右子树
    3. 访问根结点

表达式的前缀表示：波兰式。
表达式的后缀表示：逆波兰式。
表达式的中缀表示：中缀式。

如何根据中缀式写出波兰表达式和逆波兰表达式？
相关博客链接

线索二叉树

构造中序线索二叉树
在二叉树的线索链表上添加一个头结点，令其lchild 指向二叉树的根结点， rchild指向中序遍历时的最后一个节点；同时令二叉树中序遍历序列第一个节点的lchild和最后一个节点的rchild指向头结点。
以结点p为根的子树中序线索化

  1. 若p非空， 左子树递归线索化
  2. 若p的左孩子为空， 则给p加上左线索， 将其LTag置为1， 让p的左孩子指针指向pre（前驱）；否则将LTag置为0。
  3. 若pre的右孩子为空，则给pre加上右线索， 将其LTag置为1， 让pre的右孩子指针指向p（后继）；否则将pre的LTag置为0；
  4. 将pre指向刚访问过的结点p， 即pre = p。
  5. 右子树递归线索化。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    void InThreading(BiThrTree p){
        //pre为全局变量， 初始化时其右孩子指针为空， 便于在树的最左点开始建线索。
        if (p){
            InThreading(p -> lchild);
            if (!p->lchild){ 
                p->LTag = 1;
                p->lchild = pre;
            }
            else
                p->LTag = 0;
            if (!pre->rchild){
                pre->RTag = 1;
                pre->rchild = p;
            }
            else
                pre->RTag = 1;
            pre = p;
            InThreading(p->rchild);
        }
    }

带头结点的二叉树中序线索化 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void InOrderThreading(BiThrTree &Thrt, BithrTree T){
    //中序遍历二叉树T， 并将其中序线索化。 Thrt指向头结点
    Thrt = new BiThrNode;
    Thrt->LTag = 0;
    Thrt->RTag = 1;
    Thrt->rchild = Thrt;
    if (!T)
        Thrt->lchild = Thrt;
    else{
        Thrt->lchild=T;
        pre = Thrt;
        InThreading(T);
        pre->rchild = Thrt;
        pre->RTag = 1;
        Thrt->rchild = pre;
    }
}

遍历线索二叉树

  1. 在中序线索二叉树中查找
    • 若p->LTag=1 ，则p的左链指向其前驱；
    • 若p->LTag=0 ，则说明p有左子树， 结点的前驱是遍历其左子树时最后访问的一个结点。
    • 若p->RTag=1， 则p的右链指向其后继；
    • 若p->RTag=0， 则说明p有右子树， 结点的后继是遍历其右子树时访问的第一个结点。
  2. 在先序线索二叉树中查找
    • 若p->LTag=1， 则p的左链指向其前驱；
    • 若p->LTag=0， 则说明p有左子树， 此时p的前驱有两种情况：若*p是其双亲的左孩子， 则其双亲结点为其前驱；否则应该是其双亲的左子树上先序遍历的最后一个结点。
    • 若p->RTag=1， 则p的右链指向其后继；
    • 若p->RTag=0， 则说明p有右子树， *p的后继必为其左子树数（若存在）或右子树根。
  3. 在后序线索二叉树中查找
    • 若p->LTag=1， 则p的左链指向其前驱；
    • 若p->LTag=0， 当p->RTag=0时， 则p的右链指示其前驱；若p->RTag=1时， 则p的左链指向其前驱；
    • 若p->RTag=1， 则p的右链指向其后继；
    • 查找其后继比较复杂，若*p是二叉树的根， 则其后继为空；若*p是其双亲的右孩子， 则其后继为双亲结点；若*p是其双亲上午左孩子， 且*p没有右兄弟，则其后继为双亲结点；若*p是其双亲的左孩子， 且*p有右兄弟，， 则其后继为双亲的右子树上按后序遍历列出的第一个结点。

树和森林

树的存储结构

  1. 双亲表示法
data parent

  1. 孩子表示法

  2. 孩子兄弟法
    又称二叉树表示法， 或二叉链表表示法， 即以二叉链表做树的存储结构。链表中结点的两个链域分别指向该节点的第一个孩子结点和下一个兄弟结点。

firstchild data nextsibling

树与二叉树的转换

遵循左儿子右兄弟的原则。

树和森林的遍历

树的遍历

  • 先根遍历树：先访问数的根结点， 然后依次先根遍历根的每棵子树。
  • 后根遍历树：先依次后根遍历每棵子树， 然后访问根结点。