数据结构和算法导学

程序 = 数据结构 + 算法

认识数据结构

• 什么是数据结构？

  数据结构是一门研究计算机中数据存储和数据操作的学科。

• 为什么要学习数据结构？

  学习数据结构能让我们写出更加优秀的代码。当我们熟悉了常见的数据结构后，我们再编写程序，就能够选择一种更加合理的数据结构，让我们的代码更加高效、简洁，节省大量的时间、内存。

• 数据结构的组成：数据的逻辑结构+数据的存储结构+数据的运算

  • 数据的逻辑结构：指从数据的逻辑角度¹来观察数据、分析数据，本质就是数据间的关系

    主要有4种：集合、线性结构、树形结构、图形结构

    数据的逻辑结构	特点	示例
    集合结构	元素间关系松散，元素之间只存在是否同属一个集合的关系
    线性结构	元素间存在一对一的关系
    树形结构	元素间存在一对多的关系
    图形结构	元素间存在多对多的关系

    这四种以又分为两大类，即：线性结构和非线性结构。线性结构常见的有：数组、队列、链表和栈；非线性结构包括：二维数组，多维数组，广义表，树结构，图结构

  • 数据的存储结构：是数据逻辑结构再计算机中的具体实现，我们也称之为数据的物理结构，本质就是数据存储的方式

    主要有4种：顺序存储、链接存储、索引存储 和 散列存储

    数据的存储结构	描述	具体实现
    顺序存储	把数据存放在地址连续的存储单元中的存储方式，逻辑关系和物理关系一致	数组
    链接存储	用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)，借用指针或引用来来确定逻辑关系	链表
    索引存储	分别存放数据元素和元素间关系的存储方式	索引表
    散列存储	又称hash存储，是一种力图将数据元素的存储位置与关键码之间建立确定对应关系的存储方式	Hash表

  • 数据的运算：指对数据结构的操作（主要是针对存储在改数据结构中的元素），本质是对数据的操作

    常见的的数据运算有：

    1. 创建（create）: 创建一个空的数据结构
    2. 清除（clear）: 删除数据结构中的所有数据元素
    3. 插入（insert）: 在数据结构指定的位置插入一个元素
    4. 删除（remove）：将数据结构中的某个元素删除
    5. 搜索（search）：在数据结构中搜索满足特定条件的数据元素
    6. 更新（update）：修改数据结构中的某个数据元素的值
    7. 访问（visit）：访问数据结构中的某个数据元素
    8. 遍历（traverse）：按照某种次序访问数据结构中的每一数据元素，是每个数据元素恰好被访问一次
    注：每种数据结构还可包含一些特定的计算
    1. 树状结构中，找某个元素的儿子/父亲的操作
    2. 线形结构中，找某个元素的前驱或后继
    

• 数据结构中的基本概念：

  • 数据元素：是组成数据的、有一定意义的基本单位，也别称作记录、结点
  • 数据项：是组成数据元素的基本单位，是不可再分的最小数据单位了。一个数据元素可以由若干数据项组成

  

  数据元素是正真进行访问和处理的基本单位

  我对数据元素和数据项的理解：

  数据元素就类似于编程时的对象，数据项就是对象的属性，我们在编程时，一般是先确定对象，然后通过对象操作属性。

认识算法

• 什么是算法？

  官方定义：算法是对特点问题求解步骤的准确而完整的描述。

  我对理解：算法简而言之就是计算方法，是一种方法、一种策略，能够使用这种方法得到我们想要的结果，当我们遇到一个数学问题求根号2保留六位小数的近似解时，其中就可以使用二分法这种算法进行求解。

  （这个理解有失偏颇，计算方法≠计算方法，算法有时候不一定需要计算）

• 算法的特征：

  • 输入：一个算法可接受零个或多个输入参数
  • 输出：一个算法有至少一个或多个输出
  • 确定性：算法的每一步必须确定，无二义性，对于同类型输入，只能有一条执行路径，只能得到相同的结果
  • 有穷性：算法的执行步骤是有限的，每一个步骤都能在可接受的时间范围内
  • 可行性：算法可以使用代码实现，并在机器上运行并能够最终得到正确结果

一个简单的算法例子：

求解1~n之间所有整数的和。

方法一：暴力求解

Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int sum = 0;
for(int i=0;i<n;i++){
  sum += i;
}
System.out.pirntln(sum);

方法二：公式法（高斯求和算法）

Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int sum = 0;
sum = (1+n)*n/2;
System.out.pirntln(sum);

显然明显算法二要优于算法一！那么如何评判这两个算法的优劣呢？这就需要对算法进行性能分析了

• 算法的性能分析：通常以算法的 空间复杂度 和 时间复杂度 来评价一个算法的优劣（一般而言我们会更加注重算法的时间复杂度）

  • 空间复杂度：根据算法编写的程序所占计算机的内存

  • 时间复杂度：根据算法编写的程序从执行到得到正确结果，这一过程总共所花的时间

    时间复杂度分析：

    • 事后分析法：编写一个测试程序运行时间的代码，去测试算法程序的运行时间

      例如：

      long start = System.currentTimeMillis();
      /*-------------待测试的代码---------------*/
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int sum = 0;
      sum = (1+n)*n/2;
      System.out.pirntln(sum);
      /*--------------------------------------*/
      long end = System.currentTimeMillis();
      System.out.println(end-start);
      

      优点：直观，简单

      缺点：不能够准确反映算法的时间复杂度，测试会受硬件环境影响

    • 事前分析法：可以根据以下几个主要因素分析算法

      1）编译产生的机器语言代码的质量（与编译器相关，难以干预）

      2）机器执行指令的速度（与机器硬件相关，难以干预）

      3）问题的输入规模（可以人为干预）

      4）算法的策略（可以人为干预）

      根据3）和4）可以构造一个$T(n)=O(f(n))$的函数来分析算法的时间复杂度（其中n表示算法执行的次数）

总结

• 数据的逻辑结构和物理结构之间的关系：数据的逻辑结构是一种比存储结构更大的概念，它注重的数据元素之间的关系，不在乎数据元素的存储方式，是十分抽象的；而存储结构注重的是数据的存储方式，是一个具体实在的东西，依靠存储结构能够实现元素间不同的关系，所以数据的一种逻辑结构可以由多种存储结构去实现，比如：线性结构可以由顺序存储、链式存储实现。

  举个不恰当的例子：在建房子时，建筑师绘制草图用于描述房屋各部分之间的结构，这个草图就相当于是房屋的逻辑结构；而包工头选择用什么材料去具体实现它，这个过程就是房屋的存储结构。

• 算法和数据结构之间关系，在我看来数据结构就是让算法更好实现的一个工具。数据结构是一种存储数据的方式，由数据的存储结构实现；而算法是解决问题的方法，由代码实现；我们在实现算法的时候，需要选用一种合适的数据结构来让代码占用更小的内存、更少的时间。

推荐阅读：

• 图的几种存储方式
• 数据结构-二维数组-存储结构