数据结构之绪论

数据结构之绪论

第一章_绪论

1.1 数据结构在学什么

• 如何用程序代码把现实世界的问题信息化
• 如何用计算机高效地处理这些信息从而创造价值

只有详细学习过这四门课的人才能够更好理解信息化，这也是计算机专业的学生和只会写代码的人的区别所在

1.2 数据结构的基本概念

本小节会对数据结构中的基本概念做简单讲解，目的在于了解和理解概念，具体的深入了解会在后面的章节中提到，本小节的思维导图如下：

1.2.1 基本概念

1.2.1.1 数据

数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合，数据是计算机程序加工的原料。

简单来看，在计算机的世界中，数据就是0和1

1.2.1.2 数据元素、数据项

数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位

其实什么是数据元素什么是数据项，得根据实际的业务需求来确定，比如以微博举例：每一个账号为一个数据元素，而账号里的每一个信息为一个数据项：

1.2.1.3 数据结构、数据对象

数据结构是相互之间存在一种或者多种特定关系的数据元素的集合，数据对象是具有相同性质的数据元素的集合。

其实简单理解就是数据对象是一堆相同性质的数据集合，而数据结构是在数据对象的基础上，还规定了数据结构的三要素–逻辑关系，存储结构，数据的运算。

1.2.1.4 数据类型、抽象数据类型

数据类型是一个值的集合和定义在此集合上的一组操作的总称。分为原子类型（其值不可再分的数据类型）和结构类型（其值可以分解成若干成分的数据类型）

抽象数据类型(Abstract Data Type,ADT) 是抽象数据组织及与之相关的操作

若从数据结构的三要素来进行讨论，数据类型和抽象数据类型都只是实现了逻辑结构和数据的运算，不涉及具体的存储结构和实现细节。

1.2.2 数据结构三要素

非常重要，我们再数据结构的学习中，任何涉及到数据结构的地方，首先想到的就应该是三要素

1.2.2.1 逻辑结构

数据的逻辑结构只分为以下的四种结构，在考研数据结构中主要是讨论后三种逻辑结构：

• 集合：各个数据元素同属一个集合，之间没有任何关系。
• 线性结构：数据元素之间是一对一的关系，除了第一个元素，所有的元素都有唯一前驱，除了最后一个元素，任何元素都有唯一后继
• 树形结构，就像树枝一样，数据元素之间是一对多的关系，比如本小节开始给的思维导图就是树形结构的关系
• 图结构：数据元素之间存在多对多的关系，像一张网一样。

1.2.2.2 存储结构（物理结构）

数据的存储结构（物理结构）是指数据在计算机内存中的存储方式，常见有以下四种：

• 顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现，要求给数据元素分配的是一片连续的内存空间，就像C语言中的数组。
• 链式存储：逻辑上相邻的元素可能在物理位置上表示不相邻，借助指示元素存储地址的指针来表示元素间的逻辑地址关系，就像C语言中的链表。
• 索引存储：在存储元素信息的同时，还建立附加的索引表。索引表中的每项称为索引项，索引项的一般形式是（关键字，地址）。就像操作系统中分页存储中的页表。
• 散列存储：根据元素的关键字通过散列函数直接计算出元素的存储地址，又称哈希(Hash)存储。具体比较复杂，后面在做讲解，这里了解就好。

1.2.2.3 数据的运算

数据的运算是施加在数据上的运算，包括运算的定义和实现。运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤。

主要就是数据结构的创销，增删改查。

数据的运算（“能对数据做什么”）
    │
    ├── 运算的定义（面向逻辑结构）
    │   ├── 插入
    │   ├── 删除
    │   ├── 查找
    │   ├── 修改
    │   └── 遍历
    │
    └── 运算的实现（面向存储结构）
        ├── 顺序存储：移动元素 / 下标访问
        ├── 链式存储：修改指针
        ├── 索引存储：先查索引再访问数据
        └── 散列存储：通过散列函数定位

1.3 算法的基本概念

算法（Algorithm）是对特定问题求解步骤的描述，是一个有穷的指令序列，其中每条指令表示一个或者多个操作。

程序=数据结构+算法，数据结构是探讨用数据正确的现实世界的问题并存入计算机，而算法是如何高效的处理这些数据以解决实际问题。此外，一个有效的算法应该具有如下五个重要特性：

• 有穷性：意思算法的步骤必须要有限，而程序是可以无限的执行下去的。
• 确定性：算法中的每条指令都要有确定的含义。
• 可行性：就是你解决现实问题的算法要能通过计算机实现。
• 输入：0个或者多个。
• 输出：至少一个。

而通常，一个“好”的算法应该力求满足以下目标：

• 正确性：能正确的解决问题，但是不能正确解决它也叫算法。
• 可读性：好读懂，别写完过几天自己都看不懂，记得加注释。
• 健壮性：处理异常和非法输入还能争两下，不是完全不知道会输出什么。
• 高效率与低存储量需求：效率是算法的执行时间，存储量需求是执行过程所需的最大存储空间，就是时间复杂度和空间复杂度都低。

1.4 算法的时间复杂度

1.4.1 时间复杂度介绍

时间复杂度是描述算法执行时间随问题规模n增大而变化的趋势，算法的执行时间通常由语句频度（某条语句的执行次数）来衡量。

先来看一个例子：

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

void love(int n) {
	int i = 1;   //步骤1:1次
	while (i <= n) {   //步骤2：3001次
		printf("love you %d \n", i);   //步骤3:3000次
		i++;   //步骤4:3000次
	}
	printf("love you more than %d", n);   //步骤5：1次
}
int main() {
	love(3000);
	return 0;
}

在上述代码里，设算法中所有语句的频度之和为T(n)，T(3000)=1+3001++3000*2+1。所以T(n)=3*n+3。但是如果有好几千行代码难道要一个个数？这样表示太复杂难以比较怎么办？于是提出一种抓大放小的方法：只记录T(n)中增长最快的项。像上述代码，我们认为时间复杂度T用大O表示法(省略常数因子） 表示为：T(n)=O(n)。

1.4.2 时间复杂度推导

总时间复杂度 = 所有语句执行次数累加，嵌套循环语句用乘法计算，单次或并列操作用加法累加，再保留最高阶项。

在引入时间复杂度的表示方法之后，分析由多个代码组成的程序时，还需了解大O表示法(省略常数因子） 的运算法则：

• 加法规则： 若两段代码顺序执行，则总时间复杂度取两者中的高阶项： O(f(n))+O(g(n))=O(max(f(n),g(n))) 例如：O(3n) + O(n²) = O(n²)
• 乘法规则：若一段代码嵌套在另一段内部，则总时间复杂度为两者之积： O(f(n)) * O(g(n)) = O(f(n)g(n)) 例如：当a{b{}}且时间复杂度分别为O(log₂n)，O(n)时，时间复杂度为O(nlog₂n) 特别注意：语句和语句之间是没有嵌套关系的，所谓嵌套关系使用乘法指语句被循环或递归包围以方便计算次数

常见的时间复杂度阶次（按增长速度升序）： O(1) < O(log₂n) < O(n) < O(nlog₂n) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)

在数据结构中了解上述时间复杂度就够用了，其实就是高数中的函数增长趋势陡峭判断，遇到没见过的也还能使用洛必达进行判断。再分享一个函数增长趋势按照升序方式排列的口诀：常对幂指阶。

关于时间复杂度的推导，我们列举一个题目：

//算法——嵌套循环型爱你
void loveYou(int n) {    //n 为问题规模
    int i=1;    //语句1：O(1)
    while(i<=n){
        i++;    //语句2：O(n)
        printf("I Love You %d\n", i); //语句3：O(n)
        for (int j=1; j<=n; j++){
            printf("I am Iron Man\n");  //语句4：O(n*n)
        }
    }
    printf("I Love You More Than %d\n", n); //语句5：O(1)
}

解释一（不准确，快速估算）： 这是一个嵌套代码，while循环执行n次，for循环再不在while循环的作用下执行n次，所以while循环和for循环将其看成两段独立的代码时间复杂度都是O(n)，由于是嵌套结构，采用乘法，O(n) * O(n) = O(n²),整个while循环的时间复杂度 = 在while的作用下for循环的时间复杂度 = O(n²)，而外层时间复杂度为O(1)，所以整个算法的时间复杂度为O(n²+1)=O(n²)。

解释二（较为准确和直观）： while循环每执行一次，其中嵌套的for循环执行n次，所以for循环内的语句的时间复杂度在while的作用下为O(n²)，而while中的printf语句时间复杂度是O(n)(与for循环是并列关系，用加法)，而while外面的时间复杂度为O(1)。所以总时间复杂度为O(n²+n+1)=O(n²)。由此我们还可以得出一个结论：若一个循环结构中仅存在嵌套关系，则整个循环结构的时间复杂度，等于最内层基本操作在所有外层循环作用下的总执行次数

1.4.3 输入数据影响时间复杂度

算法的实际运行时间不仅依赖于问题规模n，还受输入数据初始状态的影响，具有三种时间复杂度，通常以最坏时间复杂度作为算法效率的评价标准。

• 最坏时间复杂度：考虑输入数据 “最坏” 的情况
• 平均时间复杂度：考虑所有输入数据都等概率出现的情况
• 最好时间复杂度：考虑输入数据 “最好” 的情况

看个例子：

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

// 算法4— 搜索数字型爱你
void loveYou(int flag[], int n) {
    // n 为问题规模
    printf("I Am Iron Man\n");
    // 从第一个元素开始查找
    for(int i=0; i<n; i++){
        // 找到元素n
        if(flag[i]==n) {
            printf("I Love You %d\n", n);
            break; // 找到后立即跳出循环
        }
    }
}

int main(){
    // flag 数组中乱序存放了 1~n 这些数
    int flag[n]={1...n};//伪代码
    loveYou(flag, n);
}

• 最好情况：元素n在第一个位置 —— 最好时间复杂度 T(n)=O(1)
• 最坏情况：元素n在最后一个位置 —— 最坏时间复杂度 T(n)=O(n)，所以T(n)=O(x)=O(n)
• 平均情况：假设元素n在任意一个位置的概率相同为 1/n —— 平均时间复杂度 T(n)=O(n) x = (1+2+3+…+n)·1/n = (n(1+n)/2)·1/n = (1+n)/2

1.5 算法的空间复杂度

空间复杂度S(n)表示算法在运行过程中所需的额外辅助存储空间随问题规模 n 增长的趋势。

空间复杂度也用大O表示法表示，请注意，计算空间复杂度只关注算法额外的辅助空间（栈 + 堆 + 临时变量）。如：若算法创建了若干与输入规模n同阶的辅助数组，则其空间复杂度为O(n)。若算法仅使用常量级的额外空间，则称之为原地工作（不使用与输入规模 n 成正比的额外空间），空间复杂度为O(1)，示例说明如下：

• 例 1：常量级 -> 空间复杂度 O(1)

  int sum(int a[], int n) {
    int s = 0;
    for (int i = 0; i < n; i++)
        s += a[i];
    return s;
    }
  

  输入数组 a[] ：不算，变量 s, i：常量 空间复杂度：O(1)
  

• 例 2：用了辅助数组 -> O(n)

  void copy(int a[], int n) {
    int b[n];   // 新开数组在栈区
    for (int i = 0; i < n; i++)
        b[i] = a[i];
    }
  

  b[n]：大小随 n 变化 空间复杂度：O(n)
  

• 例 3：递归一 -> O(n)

  int f(int n) {
    if (n == 0) return 0;
    return n + f(n - 1);
    }
  

  递归深度：n，每层：常量空间（保存当前 n 的值，等待 f(n-1) 返回后再加上 n） 空间复杂度：O(n) 在考研题中递归求空间复杂度时，绝大多数都是这种
  

• 例 4： 递归二

  // 算法5 —— 递归型爱你
    void loveYou(int n) {     // n 为问题规模
        int flag[n];          // 声明一个数组（局部变量，随 n 变化）
        // ... 省略数组初始化代码
  
        if (n > 1) {
            loveYou(n - 1);   // 递归调用
        }
  
        printf("I Love You %d\n", n);
    }
  
    int main() {
        loveYou(5);
        return 0;
    }
  

  递归展开是这样的：

  loveYou(5)  内存里flag[5]
   └─ loveYou(4)  内存里flag[4]
       └─ loveYou(3)  内存里flag[3]
           └─ loveYou(2)  内存里flag[2]
               └─ loveYou(1)  内存里flag[1]
  

  所以空间复杂度为：S(n)=O((1+n)*n/2)=O(0.5n²+0.5n)=O(n²)（大O表示法常数因子（如1/2n中的1/2）一律忽略）