数据结构回顾

绝地灬酷狼 2022-03-11 01:37 102阅读 0赞

很多人都说程序=数据+逻辑，数据存放到了缓存、数据库、硬盘等，而逻辑却让这些数据根据人的操作、时间的变化等变起来。那么，在逻辑处理过程中，怎么更快、更省空间、更方便的进行数据变化，那么就是合理的选择数据结构，往往可以达到事半功倍的效果。

这段时间，经常和我媳妇聊一些衣柜啊、储物柜啊、收纳箱啊等各种储物容器，她给我说，这放这个合适，那放那个合适，这个放这个东西方便拿取，那个放这些东西方便分类……听的我不亦说乎。回过头来，想想我们从事的软件，不一样么？“任何东西都来源于生活”，我一直觉的这句话说的非常对。

好，咱们再看数据结构，再最开始学习的时候，大家都会学习此门课程，13年我学习此门课程，还进行了简单总结：[软考（1）——看图心想数据结构][1]。可是知识这玩意每次看，每边学，都有不一样的理解，不一样的感悟。在这个浮躁的社会，静下心来，独处独处，读读书，大脑时而静一静，时而在知识的海洋飞翔飞翔，是不是也是一件很惬意的事？

说到数据结构，大家都会想到“时间复杂度”、“空间复杂度”，这里先简单提一下复杂度增长率的几个级别，从上到下复杂度量级依次递增，这几个函数足够覆盖我们大部分的算法结构复杂度了：

<table style="width:500px;"> 
 <thead> 
  <tr> 
   <th>函数</th> 
   <th>名称</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>c</td> 
   <td>常数</td> 
  </tr> 
  <tr> 
   <td>logN</td> 
   <td>对数级</td> 
  </tr> 
  <tr> 
   <td>log²N</td> 
   <td>对数平方根</td> 
  </tr> 
  <tr> 
   <td>N</td> 
   <td>线性级</td> 
  </tr> 
  <tr> 
   <td>NlogN</td> 
   <td>&nbsp;</td> 
  </tr> 
  <tr> 
   <td>N²</td> 
   <td>平方级</td> 
  </tr> 
  <tr> 
   <td>N³</td> 
   <td>立方级</td> 
  </tr> 
  <tr> 
   <td>2^N</td> 
   <td>指数级</td> 
  </tr> 
 </tbody> 
</table>

数据结构分为：数组-array、链表-linked list、栈-stack、队列-queue（线性）；散列-hash（非线性）、树-tree、堆（优先队列）-heap、图-graph。好，依次来看下。

--------------------

** 一，数组**：在内存中连续存储多个元素，具有固定大小的结构。类似我们写字的方格本。

**                         优点**：按照索引查询、遍历元素效率高；

**                         缺点**：1，数组的大小固定；2，数组只能存储一种类型的数据；3，添加、删除效率低，由于内存的连续性。

**使用场景**：查询频繁，增删较少，存储空间相对来说稳定。

**       二，链表**：由一系列节点组成，在内存存储上非连续，每个节点包含表元素和到后继元素的链。类似火车一样。链表恰好和数组的特点相反。

**                         优点**：1，不需要初始化容量；2，可以任意增加删除元素，添加、删除只需要改动前后链即可，效率高；

**                         缺点**：1，含有大量指针，占用空间大；2，查找元素需要遍历链，效率低；

**使用场景**：查询较少，增删频繁，数据量不大，变化多。

**       三，栈：**是限制插入和删除只能在一个位置进行的LIFO（后进先出）的表。类似生活的桶、集装箱。是非常有其特点的一种数据结构，Java中Stack类供我们使用。程序中的方法调用、递归算法、斐波那契数列等都是栈能够完美解决的问题。

**       四，队列：**是插入在一端进行，而删除则在另一段进行的FIFO（先进先出）的表。类似生活中我们排队。也是非常有特点的数据结构，Java中LinkedList类、redis中的List、SortedSet等。程序中的MQ，事件的顺序性等。

上边几种都属于线性表，相对来说比较简单。也都会经常使用到。

--------------------

**       五，散列表：**我们经常用到的map，通过一个标识和其内容组成，彼此之间没有什么联系，因此叫做散列。类似我们生活，给每个学生，每个员工，每本书添加学号、工号、序列等。其中重要两点是：1，散列函数：即怎么对应标识和内容，在数学中我们用f(x)表示x与y的关系；2，冲突解决：结果散列函数后一样，例如，2^2和（-2)^2。

1，散列函数常见构造方法：**直接定址法**：取关键字的某个线性函数值为散列地址；**数字分析法**：例如对手机号的分析；**平方取中法**；其它自定义构造函数；我们经常用的**hashcode**等。通过这些映射-f(x)，我们就能很快的通过key定位value了。

2，冲突解决也有很多方法：**分离链表法**，将冲突的value用链表进行存储；**线性探测**，移动有值的线性移动寻找无值的空间；**平方探测**，平方移动寻找空间；**双散列**，多个散列函数进行。

当然散列表如果存的太满，我们就需要进行扩容，这时候，我们需要在散列到更大的空间中进行存储。

--------------------

**       六，树：**为什么会出现这种数据结构呢 ？因为会使线性表的层级降低。想想我们生活中：电脑文件夹、管理架构图、任务分解图、思维导图……都是为了减少层级，降低深度，提高查询效率。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9saXVqaWFoYW4uYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70][]

树，大大提高了查询效率，排序效率，在HashMap中，数据库索引，磁盘存放数据等方面有着高性能解决之道。

**       七，堆：**可以被看做是一棵树的数组对象，堆中某个节点的值总是不大于（大顶堆）或不小于（小顶堆）其父节点的值，而且总是一颗完全二叉树。由于顶堆根元素一直是最大或者最小，利用这个特性，就实现了优先队列，在Java中PriorityQueue类。因此也有了堆排序，还有加权优先级，例如线程的执行等。其中几个重要的操作就是：insert、delete、buildHeap。

**       八，图：**是由顶点和边组成，每条边对应一副点。现实生活中，机场的相连组成了飞机的航线；网络流量的流动情况；任务节点图……都可以画出相关联的图。其中有方向的为有向图，没有方向的为无向图。

1，表示，我们可以通过邻接矩阵、邻接表进行表示。

2，拓扑排序，有向图中，各种节点的排序，后续节点，只能出现在前序节点的后边，在任务节点图中经常会用到。哪些任务节点可以并排，哪些任务节点，必须等着前边的完成才能实施等。

3，最短路径：通过广度优先搜索、深度优先搜索可以完成，也可以使用Dijkstra算法，“贪婪算法”的典型使用；

4，关键路径：也成为至少经过路径。例如完成任务的中的最少用时，可以考虑多线程、单线程耗时。

--------------------

**       **其实每种数据结构都对应着我们生活中的某些场景，每种数据结构都有其特点，优势是哪些、劣势是哪些……我们需要不断思考，不断联想，来构建我们脑中的知识网。通过联想建立联系，通过联系使之能够“牵一发动全身”，构建属于自己知识体系。数据结构简单汇总了一下，还是每个点都可以深入学习。有了宏观，有了微观，再看宏观，再用微观……

[1]: https://liujiahan.blog.csdn.net/article/details/11820241
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9saXVqaWFoYW4uYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70]: /images/20220311/4b1e429313b2499d985b3fadfa6b5947.png