🔑数据结构_第一章：绪论

2023.3.11开始

第一章、绪论

（一）什么是数据结构

数据结构三要素：

逻辑结构
- 四种常见的逻辑结构：
  - 集合（408考纲早已去除，此处不做讨论）
  - 线性结构（二、三章）——一对一
  - 树状结构（第四章）——一对多
  - 图结构/网结构（第五章）——多对多
数据的运算

针对于某种逻辑结构，结合实际需求，定义基本运算。
- 增
- 删
- 查
物理结构

数据的物理存储结构有以下四种：
- 顺序存储：逻辑顺序和物理顺序都是线性结构。
- 链式存储：逻辑上相邻的元素在物理位置上也可以不相邻。
- 索引存储
- 散列存储（第六章）
若采用顺序存储，则各个数据元素在物理空间上必须是连续的；若采用非顺序存储，则各个数据元素在物理空间上可以是离散的。
数据的存储结构会影响存储空间分配的方便程度，和系统对数据的运算速度。
运算的定义是针对逻辑结构的，指出运算的功能。
运算的实现是针对存储结构的，指出运算的具体操作步骤。

补充：

数据类型

是一个值的集合和定义在此集合上的一组操作的总称。
- 原子类型：其值不可再分的数据类型。
  
  如bool类型、int类型等。
- 结构类型：其值可以在分解成若干分量的数据类型。
  
  如结构体等。
抽象数据类型ADT（Abstract Data Type）

是抽象数据的组织和与之相关的操作。

（二）算法的基本概念

1、什么是算法

程序 = 数据结构 + 算法

数据结构：如何用数据正确的描述现实世界的问题，并存入计算机。

算法：如何高效地处理这些数据，以解决实际问题。

算法(Algorithm)是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作。

2、算法的五个特性

有穷性：

一个算法必须能在执行有穷步之后结束，且每一步都可在有穷时间内完成。

注：算法必须是有穷的，二程序可以是无穷的。
确定性：

算法中每条指令必须具有确切的含义，对于相同的输入只能得到相同的输出。
可行性：

算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
输入：

一个算法可以有零个或多个输入，这些输入取自于某个特定的对象的集合。
输出：

一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。

只要以上任何一个特性不满足，那就不能称之为一个算法！

3、“好”算法的特质

正确性：

算法应能够正确地解决求解问题。
可读性：

算法应具有良好的可读性，以帮助人们理解。
健壮性：

输入非法数据时，算法应能适当的做出反应和处理，而不会产生莫名其妙的输出和结果。
高效率与低存储量需求

即时间复杂度和空间复杂度都比较低。

（三）算法效率的度量

1、时间复杂度

定义：算法中所有语句的频度之和记为T(n)，它是该算法问题规模n的函数，时间复杂度主要分析T(n)的数量级。
基本运算：最深层循环内的语句。基本运算的频度与T(n)同数量级，因此通常采用算法中的基本运算的频度f(n)来分析算法的时间复杂度。
因此，算法的时间复杂度记为：
$$
T(n) = O(f(n))
$$
时间复杂度的计算（同样适用于空间复杂度）
- 只需关注最深层次的循环里的某一基本运算共进行了多少次即可！
- 加法规则：只需保留最高阶数的那一个即可。
  
  $$
  T(n) = T_1 + T_2 = O(f(n)) + O(g(n)) = O(max(f(n),g(n)))
  $$
- 乘法规则：
  $$
  T(n) = T_1(n) \times T_2(n) = O(f(n)) \times O(g(n)) = O(f(n) \times O(g(n))
  $$
- 常见的渐近时间复杂度为：
  $$
  O(1)<O(log_2n)<O(n)<O(nlog_2n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)
  $$
  
  巧计：常对幂指阶

例1：

//算法一：逐步递增型爱你
void loveYou(int n){	//n为问题规模
    int i = 1;			//爱你的程度
    while(i <= n){
        i++;			//每次+1
        printf("I Love You %d", i);
    }
    printf("I Love You More Than %d\n", n);
}

该算法的时间复杂度为：
$$
T(n) = 3n + 3 = O(n)
$$

例2：

//算法二：嵌套循环型爱你
void loveYou(int n){
    int i = 1;
    while(i <= n){
        i++;
        printf("I Love You %d\n", i);
        for(int j = 1; j <= n; j++){		//while嵌套for循环
            printf("I am an iron man\n");
        }
    }
    printf("I Love You More Than%d\n", n);
}

该算法的时间复杂度为：
$$
T(n) = O(n) + O(n^2) = O(n^2)
$$

例3：

//算法三：指数递增型爱你
void loveYou(int n){
    int i = 1;
    while(i <= n){
        i *= 2;
        printf("I Love You %d\n", i);
    }
    printf("I Love You More Than%d\n", n);
}

该算法的时间复杂度为：
$$
T(n) = O(log_2n)
$$

三种复杂度：
- 最坏时间复杂度：有参考价值
- 平均时间复杂度：有参考价值
- 最好时间复杂度：基本没有参考价值

2、空间复杂度

算法的空间复杂度S(n)定义为运行该算法所耗费的内存空间，它是问题规模n的函数，记为：
$$
S(n) = O(g(n))
$$
程序运行时，程序代码被放到内存中，程序运行所需的数据的空间也会被开辟出来，而它们占用空间的大小是固定的，与问题规模无关。

例1：

//算法一：逐步递增型爱你
void loveYou(int n){	//n为问题规模
    int i = 1;			//爱你的程度
    while(i <= n){
        i++;			//每次+1
        printf("I Love You %d", i);
    }
    printf("I Love You More Than %d\n", n);
}

该算法中，无论问题规模怎么变，算法运行所需的内存空间都是固定的常量，该算法的空间复杂度为常数阶，数学表达为：
$$
S(n) = O(1)
$$

如果一个算法的空间复杂度为常数阶的话，我们称这个算法可以原地工作——算法所需空间为常量，即：
$$
O(1)
$$

例2：
1
2
3
4
5
void test(int n){
int flag[n]; //声明一个长度为n的数组
int i;
//......
}
那么该算法的空间复杂度为：
$$
S(n) = O(n)
$$
我们在谈论某个算法的空间复杂度时，只需关注它是什么数量级、什么阶数就可以了。

例3：

void test(int n){
    int flag[n][n];	//二维数组
    int n;
}

那么该算法的空间复杂度为：
$$
S(n) = O(n^2)
$$

例4：

void test(int n){
    int flag[n][n];	//二维数组
    int flag[n];
    int n;
}

那么该算法的空间复杂度为：
$$
S(n) = O(n^2) + O(n) = O(n^2)
$$

例5：

//递归型爱你
void loveYou(int i){
    int flag[n];
    //...省略数组初始化代码
    if(n > 1){
        loveYou(n - 1);
    }
    printf("I Love You %d\n", n);
}

int main(){
    loveYou(5);
    return 0;
}