数据结构主要研究什么?

数据结构（英语：data structure）是计算机中存储、组织数据的方式。

数据结构是一种具有一定逻辑关系，在计算机中应用某种存储结构，并且封装了相应操作的数据元素集合。它包含三方面的内容，逻辑关系、存储关系及操作。

逻辑结构和物理结构

数据的逻辑结构
指反映数据元素之间的相互关系，而与他们在计算机中的存储位置无关。按相互关系分类:集合结构,线性结构,树形结构

数据的物理结构(存储结构)
指数据的逻辑结构在计算机存储空间的存放形式. 常见的物理结构有顺序存储结构、链式存储结构

数据结构主要研究对象是逻辑结构

所有的算法必须基于数据结构生存。这也是为什么算法和数据结构两门分类不分家的原因

常见数据结构及其应用场景

数组(顺序表)

数组是可以在内存中连续存储多个元素的结构，在内存中的分配也是连续的，数组中的元素通过数组下标进行访问，数组下标从0开始。

适用场景：

• 频繁查询，对存储空间要求不大，很少增加和删除的情况

优点：

• 按照索引查询元素速度快
• 按照索引遍历数组方便

缺点：

• 数组的大小固定后就无法扩容了
• 数组只能存储一种类型的数据
• 添加，删除的操作慢，因为要移动其他的元素。

栈(先进后出)

栈是一种基于先进后出（FILO）的数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。

我们称数据进入到栈的动作为压栈，数据从栈中出去的动作为弹栈。

应用场景：

• 括号匹配问题；逆波兰表达式求值问题；实现递归功能方面的场景，例如斐波那契数列。

队列(先进先出)

队列是一种基于先进先出（FIFO）的数据结构，是一种只能在一端进行插入，在另一端进行删除操作的特殊线性表，它按照先进先出的原则存储数据，先进入的数据，在读取数据时先被读取出来。

使用场景：

• 因为队列先进先出的特点，在多线程阻塞队列管理中非常适用。

链表

链表是一种物理存储单元上非连续、非顺序的存储结构，其物理结构不能只表示数据元素的逻辑顺序，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
根据指针的指向，链表能形成不同的结构，例如单链表，双向链表，循环链表等

适用场景：

• 数据量较小，需要频繁增加，删除操作的场景；
• 快慢指针：求中间值问题、单向链表是否有环问题、有环链表入口问题；
• 循环链表：约瑟夫问题

树

树是我们计算机中非常重要的一种数据结构，同时使用树这种数据结构，可以描述现实生活中的很多事物，例如家谱、单位的组织架构等。

应用场景：

• JDK1.8中 HashMap的底层源码中用到了数组+链表+红黑树；
• 磁盘文件中使用B树做为数据组织，B树大大提高了IO的操作效率；
• mysql数据库索引结构采用B+树；

树具有以下特点：

• 每个结点有零个或多个子结点；
• 没有父结点的结点为根结点；
• 每一个非根结点只有一个父结点；
• 每个结点及其后代结点整体上可以看做是一棵树，称为当前结点的父结点的一个子树；

在日常的应用中，我们讨论和用的更多的是树的其中一种结构，就是

• 二叉树
• 平衡树
• 红黑树
• B树
• B+树

散列表(哈希表)

应用场景：

• 哈希表的应用场景很多，当然也有很多问题要考虑，比如哈希冲突的问题，如果处理的不好会浪费大量的时间，导致应用崩溃。
• 解决哈希冲突问题：1 可以对数组扩容； 2 优化hash计算方式；

堆

堆是计算机学科中一类特殊的数据结构的统称，堆通常可以被看作是一棵完全二叉树的数组对象。

应用场景：

• 因为堆有序的特点，一般用来做数组中的排序，称为堆排序。

堆的特性：

• 它是完全二叉树，除了树的最后一层结点不需要是满的，其它的每一层从左到右都是满的，如果最后一层结点不是满的，那么要求左满右不满；
• 它通常用数组来实现；

图

图的定义：图是由一组顶点和一组能够将两个顶点相连的边组成的

应用场景：

• 道路畅通工程
• 最短路径

图的搜索：

• 深度优先搜索：在搜索时，如果遇到一个结点既有子结点，又有兄弟结点，那么先找子结点，然后找兄弟结点。
• 广度优先搜索：在搜索时，如果遇到一个结点既有子结点，又有兄弟结点，那么先找兄弟结点，然后找子结点。

扩展阅读

关于数据存储引擎结构，没有比这篇更详细的
常用八大数据结构总结及应用场景-附示例截图
数据结构与算法

最后更新于  2023-04-27 12:51:39  并被添加「」标签，已有 438 位童鞋阅读过。

本站使用「署名 4.0 国际」创作共享协议，可自由转载、引用，但需署名作者且注明文章出处