数据结构与算法基础知识分享

前言

数据结构与算法是程序员内功体现的重要标准之一，且数据结构也应用在各个方面，业界更有程序=数据结构+算法这个等式存在。各个中间件开发者，架构师他们都在努力的优化中间件、项目结构以及算法提高运行效率和降低内存占用，在这里数据结构起到相当重要的作用。此外数据结构也蕴含一些面向对象的思想，故学好掌握数据结构对逻辑思维处理抽象能力有很大提升。

为什么学习数据结构与算法？如果你还是学生，那么这门课程是必修的，考研基本也是必考科目。工作在内卷严重的大厂中找工作数据结构与算法也是面试、笔试必备的非常重要的考察点。如果工作了数据结构和算法也是内功提升一个非常重要的体现，对于程序员来说，想要得到满意的结果，数据结构与算法是必备功力！

数据结构

概念

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。

简言之，数据结构是一系列的存储结构按照一定执行规则、配合一定执行算法所形成的高效的存储结构。在我们所熟知的关系数据库、非关系数据库、搜索引擎存储、消息队列等都是比较牛的大型数据结构良好的运用。当然这些应用中间件不单单要考虑单纯的结构问题。还考虑实际os、网络等其他因素。

而对于数据结构与算法这个专栏。我们程序员更改掌握的首先是在内存中运行的抽象的数据结构。是一个相对比较单一的数据结构类型，比如线性结构、树、图等等.

相关术语

在数据结构与算法中，数据、数据对象、数据元素、数据项很多人搞不清其中的关系。通过画一张图来捋一捋，然后下面举个例子给大家分享一下。

用户信息表users

users的pojo对象

class users
{ 
     //略
     int id;
     String name;
     String sex;
}
//list和woman是数据
List<users>list;//数据对象list
List<users>woman;//数据对象woman
list.add(new users(001,"bigsai","man"));//添加数据元素 一个users由（001，bigsai，man）三个数据项组成 
list.add(new users(002,"smallsai","man"));//数据元素
list.add(new users(003,"菜虚鲲","woman"));//数据元素
woman.add(list.get(2));//003,"菜虚鲲","woman"三个数据项构成的一个数据元素

数据：对客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的集合总称。上述表中的三条用户信息的记录就是数据(也可能多表多集合这里只有一个)。这些数据一般都是用户输入或者是自定义构造完成。当然，还有一些图像、声音也是数据。

数据元素：数据元素是数据的基本单位。一个数据元素由若干数据项构成！可认为是一个pojo对象、或者是数据库的一条记录。比如菜虚鲲那条记录就是一个数据元素。

数据项： 而构成用户字段/属性的有id、name、sex等，这些就是数据项.数据项是构成数据元素的最小不可分割字段。可以看作一个pojo对象或者一张表(people)的一个属性/字段的值。

数据对象：是相同性质数据元素的集合。是数据的一个子集。比如上面的users表、list集合、woman集合都是数据对象。单独一张表，一个集合都可以是一个数据对象。

总的捋一捋，数据范围最广，所有数据即数据，而数据对象仅仅是有相同性质的一个集合，这个集合是数据的子集，但并不是数据的基本单位，而数据元素才是数据的基本单位。举个例子表cat和表dog都是数据，然后表cat是个数据对象(因为都描述cat这种对象)，但是数据的基本单位并不是猫和狗，而是他们的具体的每一条，比如小猫咪1号，大猫咪二号，哈士奇1号，藏獒2号这些每一条才是数据的基本单位。

还有数据类型，抽象数据类型也在下面讲一讲。

数据类型

原子类型：其值不可再分的类型。比如int，char，double，float等。

结构类型：其值可以再分为若干成分的数据类型。比如结构体构造的各种结构等。

抽象数据类型(ADT)：抽象数据类型（ADT）是一个实现包括储存数据元素的存储结构以及实现基本操作的算法。使得只研究和使用它的结构而不用考虑它的实现细节成为可能。比如我们使用List、Map、Set等等只需要了解它的api和性质功能即可。而具体的实现可能是不同的方案，比如List的实现有数组和链表不同选择。

三要素

逻辑结构：数据元素之间的逻辑关系。逻辑结构分为线性结构和非线性结构。线性结构就是顺序表、链表之类。而非线性就是集合、树、图这些结构。

存储结构：数据结构在计算机中的表示(又称映像，也称物理结构)，存储结构主要分为顺序存储、链式存储、索引存储和散列(哈希)存储，这几种存储通过下面这张图简单了解一下(仅仅为理解不考虑更多)：

数据的运算：施加在数据上的运算包括运算的定义和实现,运算的定义基于逻辑结构，运算的实现基于存储结构。

在这里容易混淆的是逻辑结构与存储结构的概念。对于，不难看得出逻辑二字，逻辑关系也就是两者存在数据上的关系而不考虑物理