C / C++ / 系统课时

数据结构解决什么问题

数据结构解决什么问题

程序不仅要保存数据,还要频繁执行查找、插入、删除和遍历。数据结构解决的核心问题,是用合适的组织方式保存同一批数据,让程序关心的操作更容易实现,并把时间与空间代价控制在可接受范围内。

学习目标

  • 理解数据结构为什么不仅是“存放数据的容器”
  • 区分数组、链表和树的基本组织方式
  • 能根据主要操作判断应该关注哪类数据结构

同一批数据可以有不同组织方式

假设程序需要保存 10、20、30、40、50、60、70 这组数据。数据本身没有变化,但可以按完全不同的结构组织。

数组把元素放在连续位置,并用下标表示位置;链表把数据拆成节点,再用指针把节点连接起来;树则建立父子层级,让数据之间具有分支关系。组织方式一变,能够高效完成的操作也随之变化。

同一批数据在数组、链表和树中的组织方式

结构决定操作方式

数组最大的特点是位置规则。已知下标时,可以直接定位元素,因此按位置读取很方便。但如果要在数组中间插入一个元素,后面的元素通常需要移动,为新数据腾出位置。

链表没有连续存储的要求。已知插入位置附近的节点后,修改少量指针就能接入新节点;代价是不能像数组那样通过下标直接跳到第几个元素,寻找某个位置通常需要从链头逐个经过节点。

树适合表达层级或可递归缩小搜索范围的关系。例如二叉搜索树会利用节点之间的大小关系决定向左还是向右继续寻找,使查找过程不必始终扫描全部元素。不过树是否高效,还取决于树的具体类型和形态,不能简单认为“用了树就一定快”。

选择结构要从操作出发

面对一个问题时,不应先决定“我要用链表”或“我要用树”,而应先列出程序真正频繁执行的操作。

例如,一个需要大量按下标读取的数据集合通常更适合数组;一个经常在已知节点附近插入和删除元素的场景,可以考虑链表;需要表示目录、组织关系或支持层级搜索时,则可能更适合树。

数据结构与算法是配套关系

数据结构负责规定数据怎样组织,算法负责规定怎样对这些数据执行操作。二者往往不能分开评价:同一种查找算法放在不同结构上,执行方式和代价可能完全不同;同一种结构也可以配合不同算法完成不同任务。

因此,学习数据结构的目标不是记住数组、链表、树的名称,而是建立一个判断习惯:先明确要保存什么数据和执行什么操作,再选择能让关键操作付出合理代价的组织方式。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

数据结构解决什么问题

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通