数据结构概念

一、逻辑结构Logical Structure定义数据元素之间抽象的逻辑关系与计算机存储无关只关注 “元素之间是什么关系”。作用描述数据 “怎么组织”是算法设计的基础。四大基本逻辑结构1.集合结构元素同属一个集合无其他关系。2.线性结构元素之间一对一关系如线性表、栈、队列、串。3.树形结构元素之间一对多关系如二叉树、B 树。4.图状结构网状结构元素之间多对多关系如图、网。线性表、栈、队列、串、数组 → 线性结构二叉树、森林 → 树形结构图 → 图状结构二、存储结构Storage Structure定义逻辑结构在计算机存储器中的具体实现形式也叫物理结构。作用决定数据如何存放、如何访问、效率如何。四大基本存储结构1.顺序存储结构用一段连续的存储单元存放数据。例数组。2.链式存储结构用任意存储单元通过指针链接。例单链表、双向链表。3.索引存储结构建立附加索引表通过索引查找。例数据库索引。4.散列存储结构哈希存储根据关键字直接计算存储地址。例哈希表。顺序表、数组 → 顺序存储单链表、双向链表 → 链式存储数据库索引 → 索引存储哈希表 → 散列存储三、两者关系必背1.逻辑结构是数据的 “抽象模型”2.存储结构是逻辑结构的 “物理实现”3.一种逻辑结构可以用多种存储结构实现例线性表 → 顺序表顺序存储、链表链式存储4.存储结构直接影响算法的时间与空间效率四、不同逻辑结构的使用场景总结1. 线性结构一对一关系核心特征数据元素之间存在严格的先后顺序每个元素最多只有一个前驱和一个后继。典型代表线性表、栈、队列、串、数组适用场景线性表需要频繁随机访问、顺序遍历的场景如学生成绩列表、商品清单。栈先进后出函数调用栈、表达式求值、括号匹配、浏览器前进 / 后退功能。队列先进先出消息队列、任务调度、打印队列、缓冲区管理。串文本编辑、字符串匹配、编译器词法分析。2. 树形结构一对多关系核心特征数据元素之间存在层次关系一个父节点可以对应多个子节点。典型代表二叉树、二叉搜索树、平衡树AVL / 红黑树、B 树、字典树适用场景层次化组织文件系统目录、公司组织架构、家谱、分类目录。高效查找与排序二叉搜索树、平衡树用于数据库索引、有序数据的快速增删查。路由与前缀匹配字典树Trie用于自动补全、IP 路由查找、字符串前缀匹配。决策与遍历决策树、表达式树用于 AI 决策、数学表达式解析。3. 图状结构多对多关系核心特征数据元素之间可以存在任意关联每个元素可以有多个前驱和多个后继。典型代表有向图、无向图、带权图适用场景网络建模社交网络用户关系、交通网络路线规划、通信网络路由算法。路径规划最短路径算法Dijkstra/Floyd用于地图导航、物流配送。依赖分析任务依赖调度、课程先修关系、编译依赖管理。连通性问题社交圈子发现、电路连通性检测、最小生成树Kruskal/Prim。4. 集合结构无明确关系核心特征数据元素同属一个集合元素之间无固定逻辑关系仅强调 “属于 / 不属于”。典型代表哈希集合、有序集合适用场景去重与存在性判断统计唯一访客、过滤重复数据、快速判断元素是否存在。交集 / 并集 / 差集运算好友推荐共同好友、数据筛选、集合类数学运算。一句话速记一对一 → 线性结构适合顺序、排队、后进先出等线性场景一对多 → 树形结构适合层次化、分类、层级管理场景多对多 → 图状结构适合网络、路径、复杂关联场景无固定关系 → 集合结构适合去重、存在性判断、集合运算场景