Java数据结构和算法（1）之概述

我就是我 2022-12-23 00:57 207阅读 0赞

我们知道，程序=数据结构+算法，那么，什么是数据结构，有什么是算法呢？如何系统的学习数据结构和算法呢？

（1）为什么要学习数据结构和算法？

数据data结构(structure)是一门研究组织数据方式的学科，数据为信息的载体，当很多信息组合在一起时，我们就需要考虑如何有效的组织信息，即通过考虑数据内在的结构类实现对于数据的增删改查，算法是用于描述问题和解决问题的思路或方式，简单来说，即为解决问题的步骤。

遇到一个实际问题，需要解决两个事情：

（1）问题涉及到哪些数据信息；

（2） 用什么方法策略解决问题。

前者是数据结构，后者是算法。数据是一切能输入到计算机的信息总和，结构是指数据之间的关系，数据结构就是将数据及其之间的关系有效地存储在计算机中。如何将数据中的问题存储到计算机中，使其变得可用，成为有组织有效的可用信息，即为数据结构的任务，当面对问题时，如何解决，即解决方法和步骤，即为算法。 算法是指对特定问题求解步骤的一种描述，说白了就是解决问题的方法策略。

只有数据结构没有算法，相当于只把数据存储到计算机中而没有有效的方法去处理，就像一幢只有框架的烂尾楼；若只有算法，没有数据结构，就像沙漠里的海市蜃楼，只不过是空中楼阁罢了。

遇到一个实际问题，充分利用所学的数据结构，将数据及其之间的关系有效地存储在计算机中，然后选择合适的算法策略，并用程序高效实现。，这就是N.Wirth教授所说的：**数据结构+算法＝程序**。

### **以编程为例：** ###

>  编程好比是一辆汽车，而数据结构和算法是汽车内部的变速箱。一个开车的人不懂变速箱的原理也是能开车的，同理一个不懂数据结构和算法的人也能编程。但是如果一个开车的人懂变速箱的原理，比如降低速度来获得更大的牵引力，或者通过降低牵引力来获得更快的行驶速度。那么爬坡时使用1档，便可以获得更大的牵引力；下坡时便使用低档限制车的行驶速度。回到编程而言，比如将一个班级的学生名字要临时存储在内存中，你会选择什么数据结构来存储，数组还是ArrayList，或者HashSet，或者别的数据结构。如果不懂数据结构的，可能随便选择一个容器来存储，也能完成所有的功能，但是后期如果随着学生数据量的增多，随便选择的数据结构肯定会存在性能问题，而一个懂数据结构和算法的人，在实际编程中会选择适当的数据结构来解决相应的问题，会极大的提高程序的性能 。

诚然，不懂数据结构和算法的人也能编程，但熟悉数据结构和算法的人能够更好的编程。

数据结构和算法知识体系如下：

![ç¥è¯ä½ç³»][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MjAzMTgx_size_16_color_FFFFFF_t_70]

（2）数据结构简介

对于数据结构而言，有一对一，一对多，多对多的关系，常见的数据结构如下：

![a2d1252b80f9047fc769057d83ae3b15.png][]

通常而言，数据结构分为线性结构和非线性结构，常见的线性结构有：数组、队列、链表、栈。非线性结构有：二维数组、多维数组、广义表、树结构、图结构。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg_size_16_color_FFFFFF_t_70][]

但凡涉及到数据，均会考虑数据的操作，即增删改查，而操作的时间复杂度和空间复杂度是我们考虑使用何种的数据结构的考虑标准之一，

常见数据结构优缺点比较：

![d9a359c8ebc5d7f640fc807f63acb8d0.png][]

（3）算法简介

算法，顾名思义，即为解决问题的步骤，那么，面对不同问题的解决方法和同一问题的不同方法之间，应该怎么去衡量算法的好坏呢？衡量算法优越性的三个尺度：空间复杂度，时间复杂度，及稳定性。

> 空间复杂度：一句来理解就是，此算法在规模为n的情况下额外消耗的储存空间。
> 
> 时间复杂度：一句来理解就是，此算法在规模为n的情况下，一个算法中的语句执行次数称为语句频度或时间频度。
> 
> 稳定性：主要是来描述算法，每次执行完，得到的结果都是一样的，但是可以不同的顺序输入，可能消耗的时间复杂度和空间复杂度不一样。

**算法的五个特征：有穷性，确定性，输入输出，可行性。**

>  *  **　　`有穷性：对于任意一组合法输入值，在执行又穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成。`**
>  *  **　　确定性：在每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。**
>  *  **　　`可行性：算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。`**
>  *  **　　有输入：作为算法加工对象的量值，通常体现在算法当中的一组变量。有些输入量需要在算法执行的过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。**
>  *  **　　`有输出：它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法功能。`**

常见的算法有：递归、排序、二分查找、搜索、哈希、贪心、分治、回溯、动态规划、字符串匹配

一些大名鼎鼎的算法：

⒈辗转相除法：已知世界上最古老的算法

⒉割圆术：刘徽首创，祖冲之改进，计算圆周率

⒊秦九韶算法：大大简化多项式的计算

⒋快速排序算法：20世纪十大算法之一

⒌赫夫曼编码：数据压缩的基本算法

⒍RSA加密：现代计算机网络数据加密算法的基础

⒎蒙特卡洛搜索树算法：人工智能基础算法，让计算机“可以像人类般思考”的算法

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MjAzMTgx_size_16_color_FFFFFF_t_70]: /images/20221120/bc625a8a86f042a2b84978b9f0b5123a.png
[a2d1252b80f9047fc769057d83ae3b15.png]: /images/20221120/84ec1f088fde4eeeaafa57c6cc3280ac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTc5MjE2Mg_size_16_color_FFFFFF_t_70]: /images/20221120/36271f9ab3ce41188a484e0811ed044f.png
[d9a359c8ebc5d7f640fc807f63acb8d0.png]: /images/20221120/26d6efab9b684a1aa1c309e0f03eb19c.png