数据结构概念

一、逻辑结构（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. 集合结构（无明确关系）
核心特征：数据元素同属一个集合，元素之间无固定逻辑关系，仅强调 “属于 / 不属于”。
典型代表：哈希集合、有序集合
适用场景：
去重与存在性判断：统计唯一访客、过滤重复数据、快速判断元素是否存在。
交集 / 并集 / 差集运算：好友推荐（共同好友）、数据筛选、集合类数学运算。
一句话速记
一对一 → 线性结构：适合顺序、排队、后进先出等线性场景
一对多 → 树形结构：适合层次化、分类、层级管理场景
多对多 → 图状结构：适合网络、路径、复杂关联场景
无固定关系 → 集合结构：适合去重、存在性判断、集合运算场景