此篇文章仅基于自己对数据结构的理解如果还有大佬有自己的想法真心希望您在下方留言如果发现我有写的不好的地方恳请大家指出来1.顺序表1).静态顺序表2.).动态顺序表2.链表1).单向链表2).双向链表3).顺序表和链表对比总结3.栈和队列4.二叉树5.堆1).堆排序6.各数据结构使用场景数据结构是计算机专业的核心必修课也是计算机相关领域的基础理论知识。它和算法紧密联系是理解程序运行逻辑、设计高效代码的关键不管是软件开发、人工智能、大数据还是网络工程等方向都离不开数据结构的支撑。什么是数据结构?数据结构是计算机中组织、存储和管理数据的方式旨在高效地支持数据的访问、插入、删除等操作是算法设计的基础。我们常见的基础数据结构可分为两大类1.线性结构。比如数组、链表、栈、队列这里所谓的线性结构也就是逻辑上是连续的它们在物理上的储存空间未必连续。2.非线性结构。比如树二叉树、红黑树、图、哈希表。这里我们只讲解二叉树。它们在逻辑上是不连续的。下面我们来认识认识它们1.顺序表顺序表是用一组地址连续的存储单元依次存储数据元素的线性结构是数组在逻辑结构层面的抽象实现。它的特点是元素物理存储位置与逻辑顺序一致支持随机访问通过下标直接定位元素但插入、删除操作需要移动大量元素时间复杂度较高。顺序表有两种静态顺序表、动态顺序表。1).静态顺序表静态顺序表是顺序表的一种它使用固定长度的数组来存储数据元素在创建时就确定了存储空间的大小且运行过程中无法动态扩容。因为存储空间固定当元素个数达到数组长度上限时就无法再插入新元素容易出现“溢出”问题。这里的size是顺序表里有效元素的个数2).动态顺序表动态顺序表是对静态顺序表的改进它的存储空间大小可以在程序运行过程中动态扩容。这里的size是顺序表里有效元素的个数capacity是这个动态数组的容量我们可以看到对于静态顺序表来说它提前就被分配好了空间大小而动态顺序表却没有告诉分配的空间大小意味着它可以动态扩容。下面我们重点讲解动态顺序表1.初始化让整型指针指向空把size和capacity置为02.尾插插入数据时首先要判断空间是否足够这很重要否则会出现越界访问的风险如果空间不够sizecapacity,那就申请空间。程序45、46行是对容量进行判断如若开始的容量为0那就先为它分配4个空间。然后更新容量capacity将元素尾插到顺序表中再次更新元素个数size。3.在特定位置插入数据它的逻辑和前面的尾插大部分一致只是多了个移动元素的流程4.特定位置删除通过下标访问到要删除的位置的元素将其后面的元素向前移动进行覆盖实现删除。2.链表1).单项链表单向链表是一种线性数据结构逻辑连续空间不连续由若干节点组成每个节点包含数据域和指针域指针域只指向链表中的下一个节点尾节点的指针域指向空 null 。1.尾插定义时定义了节点指针所以在尾插传参时传的是指针的地址那么函数接受值就是二级指针SLTNode*最后就是将每个链表进行链接。2).双向链表双向链表是每个节点包含数据域、前驱指针和后继指针的线性数据结构前驱指针指向当前节点的上一个节点后继指针指向下一个节点头节点前驱指针和尾节点后继指针通常指向 null 。头结点的前驱指针指向链表的尾节点尾结点的前驱指针指向核心特点1. 支持双向遍历既能从头节点向后遍历也能从尾节点向前遍历灵活性比单向链表更高。2. 增删效率提升已知目标节点时删除或插入操作无需像单向链表那样从头遍历找前驱节点时间复杂度仍为 O(1)。3. 空间换时间每个节点多存储一个指针占用的内存空间略高于单向链表。1.哨兵位哨兵位哨兵节点的核心意义是统一链表操作逻辑避免处理空指针和边界情况让增删等操作的代码更简洁、不易出错。它的前驱指针指向空后继指针指向头结点。具体作用体现在两点1. 消除边界判断普通链表在头插、头删时需要单独判断头节点是否为 null 添加哨兵位通常作为伪头节点后无论链表是否为空头节点和其他节点的操作逻辑完全一致不用额外区分。2. 简化代码无需在每次操作时检查指针是否越界减少了 if 判断语句降低代码的复杂度和出错概率。举个例子普通链表头删时要先判断头节点是否存在而带哨兵位的链表直接删除哨兵后的第一个节点即可逻辑完全统一。这里我们加入了哨兵位目的是为了增加增删效率。2.尾插首先要申请节点将数据初始化然后将节点进行链接使之连续。这里有一个小技巧先连后继再改前驱最后处理边界1. 定位目标位置明确要插入的新节点 newNode 位于前驱节点 prev 和后继节点 next 之间。2. 先绑定新节点的指针先让 newNode.prev prev 、 newNode.next next 这一步不会影响原有链表的结构。3. 再修改原有节点的指针接着更新 prev.next newNode 、 next.prev newNode 顺序反过来容易导致 next 节点的指针丢失。4. 哨兵/循环结构适配如果是带哨兵位的双向链表直接把哨兵当作普通节点处理即可无需额外判断空链表如果是循环结构注意首尾节点和哨兵的互相指向。3.尾删尾删时只需找到尾结点的前一个节点和头结点将其进行链接释放尾结点即可。4.查找3).顺序表和链表对比总结了解了顺序表和链表和它们的特性那我们总结一下它们各自的优缺点顺序表优点1.查找方便支持随机访问时间复杂度 O(1缺点1.空间不够时需要申请空间尤其是当连续的空间不够的时候需要寻找一段合适的空间将原有的数据拷贝过去时间复杂度高O(N)2.插入删除时需要挪动大量数据时间复杂度高O(N)3.申请的空间未必能全部利用到会有空间浪费链表优点1.增加元素时只需要申请节点就可以删除时只需改变指针指向即可,灵活度高时间复杂度低O(1)2.需要时按需申请不会有空间浪费缺点1.不支持随机访问需要遍历链表才能拿到想要的数据时间复杂度高O(N)总结顺序表适用于频繁查找的对象链表适用于频繁插入删除的对象。3.栈和队列栈和队列通常是用顺序表实现的但是有链表实现的情况主要看实际需求。栈的特性后进先出对列的特性先进先出顺序表实现适用于操作频繁、对效率要求高且能预估数据规模的场景比如编程语言内置的栈、队列结构大多基于此。链表实现适用于数据规模不确定、需要频繁扩容缩容的场景比如处理动态变化的数据流。这是栈和队列的一些常用到的接口。4.二叉树单一的二叉树并没有太大的利用价值通常用到很多算法中。二叉树是一种每个节点最多只有两个子节点的树形数据结构这两个子节点分别被称为左子节点和右子节点。二叉树有多种常见类型比如满二叉树除叶子节点外每个节点都有两个子节点、完全二叉树按层序编号节点编号与满二叉树一一对应、二叉搜索树左子树所有节点值小于根节点右子树所有节点值大于根节点等。1.二叉树节点的申请2.前序遍历3.中序遍历4.后序遍历5.堆大堆和小堆都属于完全二叉树结构是堆排序和优先队列的核心数据结构二者的核心区别在于父节点与子节点的数值大小关系。大堆大顶堆1. 定义任意一个父节点的数值 大于或等于 其左右子节点的数值。2. 特性堆顶元素根节点是整个堆中的最大值。小堆小顶堆1. 定义任意一个父节点的数值 小于或等于 其左右子节点的数值。2. 特性堆顶元素根节点是整个堆中的最小值。1.堆排序这个堆排序表面上是二叉树实现但是实际上是基于数组实现的。因为我们不难发现当我们把它们看成一个连续的集合那么这些父子之间有一个规律左孩子是父亲节点下标*21右孩子是左孩子1既然它们有这样的规律那我们就可以利用这个特性来实现堆排序。1.插入数据这是一个建大堆的算法每次在尾部插入数据后让它和父亲节点进行对比如果比父亲大那就一直向上调整直到满足大堆特性。2.删除堆顶数据当我们想要删除堆顶的数据时如果直接删除堆顶的数据那么堆的结构就被破坏了根节点没有数据就不再是堆了。那我们不妨换个思想将最后一个数据和堆顶的数据进行交换删除最后面的数据。此时根节点还存在只不过是不符合大堆的特性了那就将根节点和左右孩子作比较找出孩子中较大的数据和父亲进行交换依次向下调整。6.各数据结构使用场景数据结构 日常接触的应用场景顺序表数组1. 手机相册的图片列表按顺序存储且可快速滑动查看2. 音乐播放器的歌曲列表支持按索引快速定位曲目3. Excel表格的单元格存储通过行列下标直接访问4. 编程语言中的数组、列表如Python的list、Java的ArrayList链表 1. 浏览器的前进/后退功能通过双向链表记录访问历史2. 音乐播放器的随机播放列表便于动态插入、删除歌曲3. 操作系统的内存碎片管理灵活分配不连续内存4. 编程语言中的链表结构如Java的LinkedList二叉树1. Windows、macOS的文件系统目录结构文件夹和文件构成树形层级2. 搜索引擎的关键词自动补全基于二叉搜索树快速检索3. 办公软件的多级菜单如Word的菜单栏层级分明4. 数据库的索引结构如B树基于二叉树优化堆大顶堆/小顶堆1. 手机购物APP的商品推荐排序按热度大顶堆或价格小顶堆优先展示2. 任务管理器的进程优先级调度高优先级进程优先执行大顶堆3. 直播平台的弹幕热度排行热度高的弹幕优先显示4. 编程语言的优先队列如Java的PriorityQueue实现任务按优先级处理栈1. 浏览器的页面跳转新打开页面入栈关闭页面出栈2. 计算器的表达式求值如逆波兰表达式计算3. 文本编辑器的撤销操作每一步编辑动作入栈撤销时出栈4. 手机APP的页面导航如从首页进入详情页再返回首页队列 1. 外卖平台的订单排队按下单顺序依次派单2. 打印机的任务队列按提交顺序依次打印文档3. 医院的挂号排队叫号系统先挂号先就诊4. 操作系统的任务调度按优先级或顺序执行进程