数据结构绪论

• 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
• 数据：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。
• 数据元素：是组成数据的，有一定意义的基本单位，在计算机中通常作为整体处理，也被称为记录。
• 数据项：一个数据元素可以由若干个数据项组成。数据项是数据不可分割的最小单位。
• 数据对象：是性质相同的数据元素的集合，是数据的子集。

按照视点的不同，数据结构分为逻辑结构和物理结构。

逻辑结构：是指数据对象中数据元素之间的相互关系。

• 集合结构：集合结构中的数据元素除了同属于一个集合外，它们之间没有其他关系。
• 线性结构：线性结构中的数据元素之间是一对一的关系。
• 树形结构：树形结构中的数据元素之间存在一种一对多的层次关系。
• 图形结构：图形结构的数据元素是多对多的关系。

物理结构：是指数据的逻辑结构在计算机中的存储形式。

• 顺序存储结构：是吧数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。
• 链式存储结构：是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以不是连续的。

数据类型：是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。

• 抽象：是指抽取出事物具有的普遍的性质。
• 抽象数据类型：一个数学模型及定义在该模型上的一组操作。抽象数据类型体现了程序设计中问题分解、抽象和信息隐藏的特性。

算法

算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。

算法的特性

• 输入输出：算法具有零个或多个输入。算法至少有一个或多个输出。
• 有穷性：指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成
• 确定性：算法的每一步骤都具有确定的含义，不会出现二义性。
• 可行性：算法的每一步都必须是可行的，也就是说，每一步都能够通过执行有限次数完成。

算法设计的要求

• 正确性：算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性，能正确反映问题的要求，能够得到问题的正确答案。
• 可读性：算法设计的另一目的为为了便于阅读、理解和交流。
• 健壮性：当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果。
• 时间效率高和存储量低

算法效率的度量方法

• 事后统计方法：这种方法主要是通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低。（有很大缺陷，不予采纳）
• 事前分析估算方法：在计算机程序编制前，依据统计方法对算法进行估算。

int i, sum = 0, n = 100;       // 执行一次
for (i = 1; i <= n; i ++) {    // 执行了n+1次
    sum = sum + i;             // 执行n次
}
printf("%d", sum);             // 执行1次

int sum = 0, n = 100;     // 执行1次
sum = (1 + n) * n / 2;    // 执行1次
printf("%d", sum);        // 执行1次

函数的渐近增长

给定两个函数f(n)和g(n)，如果存在一个整数N，使得对于所有的n>N，f(n)总是比g(n)大，那么，我们就说f(n)的增长渐近快于g(n)。
判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，而更应该关注主项（最高阶项）的阶数。

算法时间复杂度

常见的时间复杂度及所耗费的时间从小到大依次是：

O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)

线性表

零个或多个数据元素的有限序列。

顺序存储结构：

指的是用一段地址连续的存储单元依次存储线性表的数据元素。

优缺点

• 无需为表示表中元素之间的逻辑关系而增加额外的存储空间
• 可以快速地存储表中任一位置的元素
• 插入和删除操作需要移动大量元素
• 当线性表长度变化较大时，难以确定存储空间的容量
• 造成存储空间的“碎片”

链式存储结构

头指针：

• 头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针。
• 头指针具有标志作用，所以需要用头指针冠以链表的名字。
• 无论链表是否为空，头指针均不为空。头指针是链表的必要元素。

头结点：

• 头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义（也可存放链表的长度）
• 有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其他结点的操作就统一了
• 头结点不一定是链表必需要素

结点由存放数据元素的数据域和存放后继结点地址的指针域组成。

单链表结构与顺序存储结构的优缺点

存储分配方式：

• 顺序存储结构用一段连续存储单元依次存储线性表的数据元素
• 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素

时间性能：

• 查找：
  顺序存储结构O(1)。
  单链表O(n)

• 插入和删除：
  顺序存储结构需要平均移动表长一半的元素，时间复杂度为O(n)
  单链表再找出位置的指针后，插入和删除时间复杂度仅为O(1)

空间性能 ：

• 顺序存储结构需要分配存储空间，分大了，浪费，分小了易发生上溢
• 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制

结论：

• 若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。
• 当线性表中的元素个数变化较大或者根本不知道有多大时，最好用单链表结构。

静态链表

用数组描述的链表叫做静态链表

静态链表的优缺点：

• 在插入和删除操作时只需要修改游标，不需要移动元素，从而改进了在顺序存储结构中插入和删除操作需要移动大量的元素
• 没有解决连续存储分配带来的表长难以确定的问题
• 失去了链式存储结构随机存取的特性

循环链表

将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表。

双向链表

双向链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。

栈与队列

栈

栈是限定仅在表尾进行插入和删除操作的线性表。

允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈。栈又称为后进先出的线性表，简称LIFO结构。

• 栈的插入操作，叫做进栈，也称压栈、入栈。
• 栈的删除操作，叫做出栈，有的也叫作弹栈。

栈的顺序存储结构

既然栈是线性表的特例，那么栈的顺序存储其实也是线性表顺序存储的简化，我们简称为顺序栈。

栈的链式存储结构

栈的链式存储结构，简称为链栈。

如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是用链栈，反之，如果它的变化在可控范围内，建议使用顺序栈会更好一些。

栈的引入简化了程序设计的问题，划分了不同关注层次，使得思考范围缩小，更加聚焦于我们要解决的问题核心。

栈的应用

递归

我们把一个直接调用自己或者通过一系列的调用语句间接地调用自己的函数，称做递归函数。

• 每个递归定义必须至少有一个条件，满足时递归不再进行，即不再引用自身而是返回值退出。

递归和迭代的区别：

• 迭代使用的是循环结构，递归使用的是选择结构。
• 递归能使程序的结构更清晰、更简洁、 更容易让人理解，从而减少读懂代码的时间。但是大量的递归调用会建立函数的副本，会耗费大量的时间和内存。
• 迭代则不需要反复调用函数和占用额外的内存。

斐波那契数列

#include <stdio.h>

int Fbi(int i) {
    if (i < 2) {
        return i == 0 ? 0 : 1;
    }
    return Fbi(i - 1) + Fbi(i - 2);
}

int main(int argc, const char * argv[]) {
    
    int i;
    printf("递归显示斐波那契数列：\n");
    
    for (i = 0; i < 20; i ++) {
        printf("%d ", Fbi(i));
    }
    
    return 0;
}

四则运算表达式求值

后缀（逆波兰）表示法

正常数学表达式：9 + (3 - 1) * 3 + 10 / 2

后缀表达式： 9 3 1 - 3 * + 10 2 / +

队列

队列是只允许在一端进行插入操作、而在另一端进行删除操作的线性表。

队列是一种先进先出的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为对头。

循环队列

我们把队列的这种头尾相接的顺序存储结构称为循环队列。

链式存储结构

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。

串

串是由零个或多个字符组成的有限序列，又叫字符串。

• 串的顺序存储结构
  串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列的。
• 串的链式存储结构

树

树是n(n>=0)个结点的有限集。n=0时称为空树。在任意一棵非空树中：
1.有且仅有一个特定的称为根的结点
2.当n>1时，其余结点可分为m(m>0)个互不相交的有限集T₁、T ₂、...Tₘ、，其中每一个集合本身又是一棵树，并且称为根的子树。

结点拥有的子树数称为结点的度。度为0的结点称为叶结点或终端结点；度不为0的结点称为非终端结点或分支结点。除根节点之外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。

树中结点的最大层次称为树的深度或高度。

如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。

线性表与树的结构区别

• 线性结构
  第一个数据元素：无前驱
  最后一个数据元素：无后继
  中间元素：一个前驱一个后继
• 树结构
  根节点：无双亲，唯一
  叶结点：无孩子，可以多个
  中间节点：一个双亲多个孩子

二叉树

二叉树是n(n≥0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。

二叉树的特点

• 每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点。
• 左子树和右子树是有顺序的，次序不能任意颠倒。
• 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

二叉树五种基本形态

1. 空二叉树
2. 只有一个根节点
3. 根节点只有左子树
4. 根节点只有右子树
5. 根节点既有左子树又有右子树

特殊二叉树

斜树

所有的结点都只有左子树的二叉树叫左斜树。所有结点都只有右子树的二叉树叫右斜树。这两者统称为斜树。

满二叉树

在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

满二叉树的特点：

1. 叶子只能出现在最下一层。出现在其它层就不可能达到平衡。
2. 非叶子结点的度一定是2.
3. 在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。

完全二叉树

对一棵具有n个结点的二叉树按层序编号，如果编号为i(1≤i≤n) 的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。

完全二叉树的特点：

1. 叶子结点只能出现在最下两层。
2. 最下层的叶子一定集中在左部连续位置。
3. 倒数两层，若有叶子结点，一定都在右部连续位置。
4. 如果结点度为1，则该结点只有左孩子，即不存在只有右子树的情况。
5. 同样结点数的二叉树，完全二叉树的深度最小。

满二叉树一定是一棵完全二叉树，但完全二叉树不一定是满的。

二叉树的性质

1. 在二叉树的第 i 层至多有 2ⁱ⁻¹ 个结点 (i≥1)。
2. 深度为 i 的二叉树至多有 2ⁱ-1 个结点 (i≥1)。
3. 对任何一棵二叉树 T ，如果其终端结点数为 n₀，度为 2 的结点数为 n₂，则 n₀=n₂+1。
4. 具有 n 个结点的完全二叉树的深度为 ⎣log₂n⎦+1（ ⎣x⎦ 表示不大于 x 的最大整数）。
5. 如果对一棵有 n 个结点的完全二叉树（其深度为 ⎣log₂n⎦+1）的结点按层序编号（从第一层到第 ⎣log₂n⎦+1 层，每层从左到右），对任一结点 i （1≤i≤n）有：
   5.1. 如果 i=1，则结点 i 是二叉树的根，无双亲；如果 i>1，则其双亲是结点 ⎣i/2⎦。
   5.2. 如果 2i>n，则结点 i 无左孩子（结点 i 为叶子结点）；否则其左孩子是结点 2i。
   5.3. 如果 2i+1>n，则结点 i 无右孩子；否则其右孩子是结点 2i+1。

二叉树的存储结构

• 二叉树的顺序存储结构
• 二叉链表

遍历二叉树

二叉树的遍历是指从根节点出发，按照某中次序依次访问二叉树中的所有节点，使得每个结点被访问一次且仅被访问一次。

二叉树的遍历方法

image.png

前序遍历

规则是若二叉树为空，则空操作返回，否则先访问根节点，然后前序遍历左子树，再前序遍历右子树。
遍历的顺序为ABDGHCEIF。

中序遍历

规则是若树为空，则空操作返回，否则从根节点开始（注意并不是先访问根节点），中序遍历根节点的左子树，然后是访问根节点，最后中序遍历右子树。
遍历的顺序为GDHBAEICF。

后序遍历

规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根节点。
遍历的顺序为GHDBIEFCA。

层序遍历

规则是若树为空，则空操作返回，否则从树的第一层，也就是根节点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。
遍历的顺序为ABCDEFGHI。

二叉树遍历的性质

• 已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。
• 已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。

已知前序和后序遍历，是不能确定一棵二叉树的。

线索二叉树

指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树。

对二叉树以某种次序遍历使其变为线索二叉树的过程称做是线索化。

如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构就是非常不错的选择。

图

......