数据结构绪论（B站王卓老师）

- 一，相关概念

  + 1，<font color=green>**数据（DATA）**</font>：各种符号的集合

分为：①数值型数据 实数等

②非数值型数据 文字图象等

  + 2，<font color=green>**数据元素（DATA element）**</font>数据的基本单位，在计算机中通常作为一个<u>整体</u>进行考虑和处理，别名为元素，顶点，记录，结点。

  + 3，<font color=green>**数据项（DATA item）**</font>是构成数据元素的不可分割的最小单位

  + 小结：数据>数据元素>数据项

  + 4，<font color=green>**数据对象（DATA object）**</font>是性质相同的数据元素的集合，是数据的一个子集

- 二，数据结构  

  + 1，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，包括：①逻辑结构 ②存储结构 ③数据运算

  + 2,逻辑结构的种类

    + 划分方法一：

    + 划分方法二：

  + 3，存储结构的分类

    + 1，顺序存储结构：

    将数据元素存放在地址连续的存储单元中，其数据间的逻辑关系与物理关系一致。

    + 2，链接存储结构：

    将数据元素存放在任意的存储单元中，这组存储单元之间通过链接的方式建立起来。（C语言中用指针实现链式存储结构）

    + 3，索引存储结构：

    在存储数据元素的同时，还建立附加的索引表。

    + 4，散列存储结构：

    根据元素的关键字直接计算出该元素的存储地址，又称哈希存储结构。

  + 4，数据类型(DATA type)：

    + 是指一个值的集合和定义在这个值集上的一组操作的总称。

    作用:

    1，数据类型决定了数据对象取值范围

    2，数据类型决定了数据对象所能进行的操作

    + 抽象数据类型（Abstract data type,**ADT**）

    定义格式如下：

    ```c

        ADT 抽象数据类型名{

        数据对象：

        数据关系：

        基本操作：

        }ADT 抽象数据类型名

    ```

    基本操作的定义格式为：

    ```c

        操作名（参数表）

        初始条件：

        操作结果：

    ```

    + 基本操作的定义格式说明

    + ***概念小结***

三，算法效率（时间效率和空间效率）

+ 1，两种度量方法：

  + ①事后统计方法：

    通过设计好的测试程序和数据，利用计算机计时器对不同算法的运行时间进行比较。

  + ②事前分析估算法：

    在计算机程序编写前，依据算法所处理的数据规模大小和算法实现所消耗的时间资源、空间资源等，对算法进行估算。

+ 2，算法运行时间=一个操作所需时间（假设均为单位时间）×算法中该操作重复执行的次数（语句频度）

  算法执行时间约等于语句频度总和

+ 3，两个n*n矩阵相乘算法效率分析

  ```c

    for(i=1;i<=n;i++)  //n+1

        for(j=1;j<=n;j++)  //n*(n+1)

            for(k=1;k<=n;k++) //n*n*(n+1)

                c[i][j]+=a[i][k]*b[k][j];//n*n*n

    ```

    算法耗费时间等于每条语句频度之和

T(n)=（n+1）+n*(n+1)+n*n*(n+1)+n*n*n=n^3+3n^2+2n+1

+ 4,算法的渐进时间复杂度(O是数量级符号)

  简称时间复杂度(T(n)的数量级)

  + 1，忽略低次幂项和最高次幂系数

  + 2，

  + 3，对于复杂的算法，可以分为几个部分，利用加法和乘法法则计算时间复杂度

    + 加法法则

    ：T(n)=T1(n)+T2(n)  取两个函数中数量级最大的

    + 乘法法则

    ：T(n)=T1(n)*T2(n)  数量级为两个函数的乘积

  + 4，时间复杂度T(n)按数量级递增顺序为

    O(1)<O(log2n)<O(n)<O(nlog2n)<O(n^2)<O(n^3)<O(2^n)<O(n!)

+ 5，渐进空间复杂度(S(n)的数量级)

  + 1，空间复杂度S(n)分析

    + 1，算法原地工作：算法所需 Workspace 的空间为常量，O(1)

    + 2，递归算法的空间复杂度：递归深度n*每次递归调用所需空间

    + 3，循环工作算法的空间复杂度：循环中使用的变量所占空间

  + 2，空间复杂度S(n)按数量级递增顺序为

    O(1)<O(n)<O(n^2)<O(n^3)<O(2^n)<O(n!)

    例子：