【数据结构】绪论

梦里梦外; 2024-04-07 15:12 68阅读 0赞

## 文章目录 ##

1. 绪论

1.1 概述

1.2 数据与数据结构

1.2.1 术语

1.2.2 逻辑结构

1.2.3 存储结构：

1.2.4 数据操作：

1.3 算法

1.3.1 算法特性

1.3.2 算法目标

1.3.3 算法分析：概述

1.3.4 算法分析：时间复杂度（大O）

1.3.5 算法分析：最好、最坏、平均

1.4 回顾：西格玛Σ 求和

## 1. 绪论 ##

### 1.1 概述 ###

*  算法 + 数据结构 = 程序
    
     *  程序：计算机指令的组合
     *  算法：程序的逻辑抽象
     *  数据结构：数据及其关系的反映，从逻辑结构和存储(物理)结构。
 *  数据结构解决具体问题：
    
    1.  数据的逻辑结构（数学模型）
    2.  数据的存储结构
    3.  数据操作与运算

### 1.2 数据与数据结构 ###

#### 1.2.1 术语 ####

*  数据（Data）：数据是信息的载体，是对客观事物的符号表示。
 *  数据元素（Data Element）：是数据的基本单位，是一个个体。相当于表的一行。
 *  数据项（Data Item）：是数据元素的组成部分。相当于表的列。
 *  数据对象（Data Object）：性质相同的数据元素的集合。相当于表。
 *  数据结构（Data Structure）：特定关系的数据元素的集合。

#### 1.2.2 逻辑结构 ####

*  逻辑结构：数据元素之间的逻辑关系，与数据存储无关，独立与计算机之外。
 *  数据元素按照特性：
    
    1.  集合：元素之间没有关系，比较松散
    2.  线性结构：元素之间存在==一对一==关系。除了开始和终端结点，其他结点由有一个前驱和一个后继。
    3.  树形结构：元素之间存在==一对多==关系。
    4.  图形结构：元素之间存在==多对多==关系。
 *  数据的逻辑结构需要2部分：数据元素（data）、数据元素的关系（relationship）
    
    ![23f2c4724700432d9fadd953d79413a1.png][]

#### 1.2.3 存储结构： ####

*  存储结构：数据的存储结构，也称为物理结构，是数据的逻辑结构在计算机的实现。
    
     *  数据元素的值存储表示和逻辑关系。
 *  存储结构的4种方式：
    
    1.  顺序存储：在一片连续的存储空间中进行存储，元素的逻辑位置和物理位置保持一致。例如：数组
        
        ![73dd1fd528ef4819996f4a0ff8d86180.png][]
    2.  链式存储：可以存储在任意的物理物质上，需要额外的部分存放逻辑关系的指针。例如：链表
        
        ![55b1940e0cb446c1923a3dfeee2da48d.png][]
    3.  索引存储：存储数据的同时，额外的存储一个索引表。在查询时可以提高效率。
    4.  散列存储：一般情况物理上可以是连续的存储空间，需要通过`散列函数hash`来确定存储位置。在查询时可以提高效率。
        
        ![a25f6978782446d3a50cd70b6d8a5b65.png][]

#### 1.2.4 数据操作： ####

*  初始化：创建、销毁：
 *  数据操作：插入/添加、删除、修改
 *  数据使用：查找、遍历

### 1.3 算法 ###

*  算法：对特定问题求解步骤的一种描述。是指令的有限序列。

#### 1.3.1 算法特性 ####

1.  有穷性：有限
2.  确定性：需求确定、指令确定
3.  有效性：指令都是由意义
4.  输入：
5.  输出：

![5e320d58a77c42c5933525107e7a5e58.png][]

#### 1.3.2 算法目标 ####

1.  正确性：基本要求，需求和实现对应。
2.  可读性：使程序员能够读懂，编写代码时可以辅助注释。
3.  健壮性：临界值的处理、无效数据的校验等。
4.  高效性：使用较少的资源（资源分2种：时间资源、空间资源）。一个好的算法要做到执行时所需时间尽量短，所需的最大存储空间尽量少。

#### 1.3.3 算法分析：概述 ####

*  算法的复杂度是衡量算法优劣的重要依据。
 *  算法的复杂度分类：时间复杂度、空间复杂度。
    
     *  时间复杂度：执行时间的长短。
     *  空间复杂度：执行时空间需求量，也就是计算机资源的使用量。

#### 1.3.4 算法分析：时间复杂度（大O） ####

*  主要考虑因素：
    
    1.  算法本身
    2.  问题规模
    3.  程序语言选择
    4.  编译程序（JDK优劣）
    5.  硬件速度
    6.  运行软件
 *  时间复杂度通过`大O表示法`进行表示的
    
     *  大O表示法，用于估算一个算法的执行时间。
     *  算法执行时间：Σ(指令的执行次数 \* 指令的执行时间)。
     *  `指令的执行时间`是固定的，可以不考虑。只需要考虑`指令的执行次数`即可。
     *  大O表达法，通过统计`指令的执行次数`，就可以估算出一个算法的优劣。
     *  `指令的执行次数`：每行代码执行的次数，将所有的`次数累加`在一起即可。
     *  例如1.7：2n^3 + 3n^2+2n+1 总次数表达式 --> 只考虑最高次幂 --> O(n^3)
     *  大O表达式只需要考虑最高次幂的项。
 *  大O表达式常见的形式
    
     *  常量阶：O(1) ，执行的次数与输入无关。
     *  线性阶：O(n) ，执行的次数与输入成正比关系。例如：一层循环。
     *  平方阶：O(n^2) ， 执行的次数与输入成平方关系。例如：二层循环
     *  立方阶：O(n^3) ，执行的次数与输入成立方关系。例如：三层循环
     *  对数阶：O(log2n) ， 执行的次数与输入成开方关系。例如：求对数 log28 = 3
     *  线性对数阶：O(nlog2n)

![972884adb88549e3aeca513a113dd2ec.png][]

*  O(log2n) 指数计算：R表示次数
    
    ![0a7a9cdf556b465297d25f1eeabd1721.png][]
 *  O (n) ：一层循环
 *  O(n^2)：二层循环（99乘法表）
    
        int n = 9;
        for(int i = 0 ; i < n ; i ++) {
            for(int j = 0 ; j < n : j ++) {
                // 次数 n*n
            }
        }
 *  O(n^3)：三层循环
    
        int n = 9;
        for(int i = 0 ; i < n ; i ++) {             //时针
            for(int j = 0 ; j < n : j ++) {         //分针
                for(int m = 0 ; m < n ; m++) {      //秒针
                    // 次数 n * n * n
                }
            }
        }

#### 1.3.5 算法分析：最好、最坏、平均 ####

*  实例：从数组中获得内容 a\[1...n\]
 *  最好时间复杂度：获得最好的情况，例如：数组中的第一个数据。O(1)表示此情况。
 *  最坏时间复杂度：获得最坏的情况，例如：数据中最后一位。O(n)表示此情况。
 *  平均时间复杂度：
    
     *  1+...+n和 ： (n+1) \* n/2
     *  平均，和/n ：(n+1) \* n/2 / n ---> (n + 1) / 2 --> O(n)表示
 *  结论：在一般情况下，取`最坏时间复杂度`或`等概率下的平均时间复杂度`作为算法的时间复杂度。

### 1.4 回顾：西格玛Σ 求和 ###

![b60cbfc7be8940a6b5b076366dc1fdc2.png][]

*  需求：1+2+3+4+....+n
    
    ![d967131ed18846b1ae3eb32f00835216.png][]
    
    $$  
    \\sum\_\{i=1\}^\{n\}\\dfrac\{(n+1)\*n\}\{2\} \\tag\{西格玛Σ求和\}  
    $$

[23f2c4724700432d9fadd953d79413a1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/00da4101669343ddb6327e420ec9e11f.png
[73dd1fd528ef4819996f4a0ff8d86180.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/e0135346d4e64b8e8a6564fb0bb0157e.png
[55b1940e0cb446c1923a3dfeee2da48d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/7d0375a9990546d49e20ddddb056dd96.png
[a25f6978782446d3a50cd70b6d8a5b65.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/626681c4f78d4195b30d5f08f1acbafb.png
[5e320d58a77c42c5933525107e7a5e58.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/2ebad69474df4258a7532e1d2a40aaf2.png
[972884adb88549e3aeca513a113dd2ec.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/50d02b36f4ed493d871141a1315da9c1.png
[0a7a9cdf556b465297d25f1eeabd1721.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/d626d82697944f84a5879dafd151913f.png
[b60cbfc7be8940a6b5b076366dc1fdc2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/2cad0ec943ae499c9eed5904ac5cbec4.png
[d967131ed18846b1ae3eb32f00835216.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/bfd826db04e647379d35ca3eed335e96.png