数据结构

这份笔记的主线是跟着《数据结构（C语言第3版）》来的，但实际上我还会有很多学习路径，所以使用的是C++和Java。并且会随着学习的进展逐渐完善这份笔记。

Chapter 1 绪论

1.1 数据结构的基本概念与术语

简单地说，数据结构是一门研究非数值计算程序设计中的操作对象，以及这些对象之间的关系和操作的学科。

1.1.1 术语

  • 数据（Data） 是信息的载体，是客观事物的符号表示，是所有能输入计算机中并被计算机程序处理的符号的总称。
  • 数据元素（Data Element） 是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。
  • 数据项（Data Item） 是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。
  • 数据对象（Data Object） 是性质相同的数据元素的集合，是数据的一个子集。

1.1.2 数据结构

数据结构（Data Structure） 是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。

  1. 逻辑结构：数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。它有两个要素，数据元素和关系。有四种基本逻辑结构类型

    • 集合结构：数据元素之间除了“属于同一集合”的关系外，别无其他关系。
    • 线性结构：数据元素之间存在一对一的关系。
    • 树结构：数据元素之间存在一对多的关系。
    • 图结构或网状结构：数据元素之间存在多对多的关系。

    线性结构包括线性表、栈和队列、字符串、数组、广义表等。

    非线性结构包括树结构（分为树和二叉树）、图结构（分为有向图和无向图）和集合结构。

  2. 存储结构：数据对象在计算机中的存储表示称为数据的存储结构，也称为物理结构。

    • 顺序存储结构：顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系的，通常借助程序设计语言的数组类型来描述。
    • 链式存储结构：顺序存储结构要求所有的元素依次存放在一片连续的存储空间中，而链式存储结构，无须占用一整块存储空间。但为了表示结点之间的关系，需要给每个结点附加指针字段，用于存放后继元素的存储地址。所以链式存储结构通常借助于程序设计语言的指针类型来描述。

1.1.3 数据类型和抽象数据类型

  1. 数据类型（Data Type）：是高级程序设计语言中的一个基本概念，是一组性质相同的值的集合和定义在此集合上的一组操作的总称，是某种程序设计语言中已实现的数据结构。前面提到过顺序存储结构可以借助程序设计语言的数组类型来描述，链式存储结构可以借助指针类型来描述，所以数据类型和数据结构的概念密切相关。

  2. 抽象数据类型（Abstract Data Type，ADT）：抽象就是抽取出实际问题的本质。在处理复杂问题时，通常可以采用抽象化的方法来简化问题及其解决过程。抽象化的核心在于屏蔽具体实现细节，通过隐藏非必要的复杂性，使我们能够聚焦于整体框架和关键概念，进而提升我们理解和解决问题的效率。

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

1.2 抽象数据类型的表示与实现

抽象数据类型的概念与面向对象方法的思想是一致的。抽象数据类型独立于具体实现，将数据和操作封装在一起，使得用户程序只能通过抽象数据类型定义的某些操作来访问其中的数据，从而实现了信息隐藏。

下面以复数为例，给出一个完整的抽象数据类型的定义、表示和实现。

定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
APT Complex {
    数据对象：D={e1,e2|e1,e2∈R,R是实数集}
    数据关系：S={<e1,e2>|e1是复数的实部，e2 是复数的虚部}
    基本操作：
    Creat(&C,x,y)
        操作结果：构造复数C，其实部和虚部分别被赋予参数x和y的值。
    getReal(C)
        初始条件：复数C已存在。
        操作结果：返回复数C的实部值。
    getImag(C)
        初始条件：复数C已存在。
        操作结果：返回复数C的虚部值。
    Add(C1,C2)
        初始条件：C1，C2是复数。
        操作结果：返回两个复数C1和C2的和。
    Sub(C1,C2)
        初始条件：C1，C2是复数。
        操作结果：返回两个复数C1和C2的差。
} ADT Complex

表示

1
2
3
4
typedef struct {        //复数类型
    double realPart;    // 实部
    double imagePart;   // 虚部
} Complex;

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void Create(&Complex C, float x, float y) {     //构造一个复数
　C.realPart=x;
　C.imagePart=y;
}
float getReal(Complex C) {                      //取复数C=x+yi的实部
　return C.realPart;
}
float getImag(Complex C) {                      //取复数C=x+yi的虚部
　return C.imagePart;
}
Complex Add(Complex C1, Complex C2) {           //求两个复数C1和C2的和sum
 　Complex sum;
 　sum.realPart=C1.realPart+C2.realPart;
 　sum.imagePart=C1.imagePart+C2.imagePart;
 　return sum;
}
Complex Sub(Complex C1, Complex C2) {           //求两个复数C1和C2的差difference
 　Complex difference;
 　difference.realPart=C1.realPart-C2.realPart;
 　difference.imagePart=C1.imagePart-C2.imagePart;
 　return difference;
}

这样定义之后，就可以在主程序中通过调用Create()函数构造一个复数，调用Add()或Sub()函数实现复数的加法或减法运算，从而使用户可以像使用整数类型那样使用复数类型了。

1.3 算法与算法分析

程序=数据结构+算法。——Niklaus Wirth

1.3.1 算法的定义及特性

算法（Algorithm） 是为了解决某类问题而规定的一个有限长的操作序列。数据结构和算法是程序的两大要素，二者相辅相成，缺一不可。程序设计的本质是为要处理的问题选择好的数据结构，同时在此结构上施加一种好的算法。如果把程序设计比作建造房子的话，数据结构可以看作建筑工程中的建筑设计图，算法可以看作施工流程图。

一个算法必须满足以下5个重要特性。

  • 输入 一个算法有0个或多个输入。对绝大多数算法来说，输入参数都是必要的，当用函数描述算法时，输入往往是通过形参表示的，在它们被调用时，从主调函数获得输入值。对于简单的算法，数据也可以直接在程序中给定，如打印“hello world”，这时不需要任何输入参数，因此算法的输入可以是0个。
  • 输出 一个算法有一个或多个输出，它们是算法进行信息加工后得到的结果，无输出的算法没有任何意义。当用函数描述算法时，输出多用返回值或引用类型的形参表示。
  • 确定性。对于每种情况下所应执行的操作，在算法中都有确切的规定，不会产生二义性，使算法的执行者或阅读者都能明确其含义及如何执行。
  • 有穷性 一个算法必须总是在执行有穷步后结束，且每一步都必须在有穷时间内完成。
  • 可行性 算法中的所有操作都可以通过已经实现的基本操作运算执行有限次来实现，即算法描述中的每条指令都是可执行的。

1.3.2 评价算法优劣的基本标准

  1. 正确性 算法应能正确地解决求解问题。算法的正确性是指算法能够按照预定的功能和性能需求，对任何合法的输入，都能产生预期的输出，并且没有歧义。
  2. 可读性 一个好的算法，首先应便于人们理解和相互交流，其次才是机器可执行性。可读性强的算法有助于人们对算法的理解，而难懂的算法容易隐藏错误，且难于调试和修改。
  3. 健壮性 当输入的数据非法时，好的算法能适当地做出正确反应或进行相应处理，而不会产生一些莫名其妙的输出结果。
  4. 高效性 高效性包括时间和空间两个方面。时间高效是指算法设计合理，执行效率高，可以用时间复杂度来度量；空间高效是指算法占用存储容量合理，可以用空间复杂度来度量。时间复杂度和空间复杂度是衡量算法的两个主要指标。

1.3.3 时间复杂度

详见时间复杂度。

1.3.4 空间复杂度

详见空间复杂度

Chapter 2 线性表

线性结构是简单且常用的数据结构，它的基本特点是除第一个数据元素无直接前驱、最后一个数据元素无直接后继之外，其他每个数据元素都有一个前驱和一个后继。线性表是最基本且最常用的一种线性结构，同时也是其他数据结构的基础。

2.1 线性表的定义和特点

在所有的数据结构中，最典型、最常用的是线性表（Linear List）。

线性表： 由n个属于同一数据对象、相邻之间存在序偶关系的的数据元素构成的有限序列。个数n为线性表的长度，n=0时称为空表。

非空的线性表或线性结构有四个特点：

  1. 顺序性（序列）： 元素具有线性顺序，除第一个数据元素无前驱、最后一个数据元素无后继之外，其他每个数据元素均有 一个前驱和一个后继；
  2. 有限性（有限）： 元素个数有限，在计算机中处理的对象都是有限的；
  3. 同构性（相同类型）： 元素属于同一数据对象，即数据元素具有相同的类型；
  4. 抽象性（元素类型不确定）： 数据元素的类型需要根据实际的具体问题而确定，在定义中是不具体的，而是抽象的。

2.2 线性表的类型定义

呃呃呃……可能是我天资愚钝，我咋看不懂这本教程呢？感觉读起来很吃力，所以我决定抛弃这本书，按我能理解的方式学和写。