数据结构和算法概述

一、数据结构

1.1、什么是数据结构？

简单理解：数据结构就是把数据元素按照一定的关系组织起来的集合，用来组织和存储元素

1.2、数据结构分类？

传统意义上，我们可以把数组结构分为：

1、逻辑结构

2、物理结构

两大类。

1.2.1、逻辑结构

逻辑结构是从具体问题中抽象出来的模型，是抽象意义上的结构，按照对象中数据元素之间的相互关系分类，也是我们后面课题中需要关注和讨论的问题

逻辑结构主要分为 4 类：

1、集合结构

2、线性结构

3、树形结构

4、图形结构

1.2.1.1、集合结构

1）、集合结构中数据元素除了属于同一个集合外，他们之间没有任何其他的关系，如图 1-1：

1.2.1.2、线性结构

1）、线性结构中的数据元素之间存在一对一的关系，如图 1-2：

1.2.1.3、树形结构

1）、树形结构中的数据元素之间存在一对多的层次关系，如图 1-3：

1.2.1.4、图形结构

1）、图形结构的数据元素是多对多的关系，如图 1-4：

1.2.2、物理结构

逻辑结构在计算机中真正的表示方式称为物理结构，常用的物理结构有：

1、顺序存储结构

2、链式存储结构

1.2.2.1、顺序存储结构

如图 1-5：

1）、把数据元素放到连续的存储单元里面，其数据间的逻辑关系和物理关系是一致的，比如我们常用的数组就是顺序存储结构。

2）、顺序存储结构存在一定的弊端，就像生活中排队时也会有人插队，也有可能有人突然离开，这个时候整个结构都处于变化中，此时就需要链式存储结构。

1.2.2.2、链式存储结构

如图 1-6：

1）、把数据元素放在任意的存储单元里面，这组存储单元可以是连续的，也可以是不连续的。此时，数据元素之间并不能反映元素间的逻辑关系。

2）、因此在链式存储结构中引进了一个指针存放数据元素的地址，这样通过地址就可以找到相关联数据元素的位置

二、算法

1.1、什么是算法？

简单理解：根据一定的条件，对一些数据进行计算，得到需要的结果

1.2、算法初体验

一个优秀的算法追求两个目标：

1、花最少的时间完成需求（时间复杂度最小）

2、花最小的内存空间完成需求（空间复杂度最小）

1.2.1、计算 1 到 100 的和

解法一：

public class Sum{
  public static void main(String[] args){
    int sum = 0;
    int n = 100;
    for(int i = 1; i <= n; i++){
      sum += i;
    }
    System.out.println(sum);
  }
}
//打印结果
100

上述代码：

1、定义了两个整型变量

2、for 循环 100 次加法运算

3、打印结果到控制台

解法二：

public class Sum{
  public static void main(String[] args){
    int sum = 0;
    int n = 100;
    sum = (n + 1)*n / 2;
    System.out.println(sum);
  }
}
//打印结果
100

上述代码：

1、定义了两个整型变量

2、执行一次加法运算，一次乘法运算，一次除法运算，总共 3 次运算

3、打印结果到控制台

解法一和解法二对比：很明显解法二花费的时间更少

1.2.2、计算 10 的阶乘

解法一：

public class Factorial{
  public static void main(String[] args){
    long result = func1(10);
    System.out.println(result);
  }
  
  public static long func1(long n){
    if(n == 1){
      return 1;
    }
    return n*func1(n-1);
  }
}

//打印结果
3628800

上述代码：

使用递归完成需求，func1 方法会执行 10 次，并且第一次未执行完毕，又会调用第二次，第二次未执行完毕，又会调用第三次…最终最多的时候，需要在同时开辟 10 块内存分别去执行 10 个 func1 方法

解法二：

public class Factorial{
  public static void main(String[] args){
    long result = func2(10);
    System.out.println(result);
  }
  
  public static long func2(long n){
    int result = 1;
    for(int i = 1; i <= n; i++){
      result *= i;
    }
    return result;
  }
}

//打印结果
3628800

上述代码：

使用 for 循环完成需求，func2 方法只会执行一次，最终，只需要开辟一块内存执行 func2 方法即可

解法一和解法二对比：很明显解法二占用的内存空间更小

三、总结

本篇文章我们介绍了：

1、数据结构

数据结构就是把元素按照一定的关系组织起来的集合，用于组织和存储数据

2、数据结构分类

1、逻辑结构：

1、集合结构

2、线性结构

3、树形结构

4、图形结构

2、物理结构

1、顺序存储结构

2、链式存储结构

3、算法

根据一定的条件，对一些数据进行计算，得到需要的结果

4、举了算法的两个例子

1、计算 1 到 100 的和，对比时间复杂度

2、计算 10 的阶乘，对比空间复杂度

本篇文章到这里就结束了，感谢你的阅读🤝