数据结构基础知识总结

一、核心概念

1. 数据与数据元素
   • 数据是信息的载体，包括数、字符及可被计算机处理的符号集合。
   • 数据元素是数据的基本单元，通常作为整体处理（如学生成绩表中的一条记录）。
   • 数据项是数据不可分割的最小单位（如成绩表中的“分数”字段）。
2. 数据对象与数据结构
   • 数据对象是性质相同的数据元素的集合（如所有学生的成绩记录）。
   • 数据结构是相互关联的数据元素的集合，包含逻辑关系和存储方式。
3. 数据类型与抽象数据类型（ADT）
   • 数据类型定义了数据的取值范围和操作（如整型、浮点型）。
   • 抽象数据类型（ADT）通过数学模型描述数据逻辑结构及操作，与具体实现无关（如栈、队列）。

二、逻辑结构与存储结构

1. 逻辑结构
   • 线性结构：元素间为一对一关系（如数组、链表、栈、队列）。
   • 非线性结构：
     • 树形结构：一对多关系（如二叉树、B树）。
     • 图形结构：多对多关系（如社交网络）。
     • 集合结构：元素间无特定关系。
2. 存储结构（物理结构）
   • 顺序存储：元素连续存放，支持随机访问（如数组）。
   • 链式存储：元素离散存放，通过指针关联（如链表）。
   • 索引存储：附加索引表加速检索（如数据库索引）。
   • 哈希存储：通过哈希函数直接计算存储地址（如哈希表）。

三、数据结构三要素

1. 逻辑结构：描述数据间的抽象关系。
2. 存储结构：实现逻辑关系的物理存储方式。
3. 数据运算：包括插入、删除、查找、排序等操作，需结合逻辑与存储结构实现。

四、常用数据结构

1. 线性结构
   • 数组：连续内存存储，支持随机访问，但插入/删除效率低。
   • 链表：动态分配内存，插入/删除高效，但访问需遍历。
   • 栈：后进先出（LIFO），用于函数调用、表达式求值。
   • 队列：先进先出（FIFO），用于任务调度、广度优先搜索。
2. 非线性结构
   • 树：
     • 二叉树：每个节点最多两个子节点，用于文件系统、数据库索引。
     • 平衡二叉树（如AVL、红黑树）：保持高度平衡，优化查询效率。
   • 图：表示复杂关系（如社交网络），分为有向图和无向图。
   • 堆：完全二叉树结构，支持快速获取最大/最小值（如优先队列）。
   • 散列表：通过哈希函数实现快速查找，解决冲突需额外开销。

五、算法基础

1. 算法特性
   • 有穷性：有限步骤内结束。
   • 确定性：相同输入产生相同输出。
   • 可行性：操作可分解为基本计算步骤。
2. 复杂度分析
   • 时间复杂度：衡量算法执行时间随数据规模增长的趋势（如O(n)、O(log n)）。
   • 空间复杂度：衡量算法所需存储空间。

六、数据结构与算法的关系

• 逻辑结构决定算法设计：例如树结构适合层次遍历，图结构需深度/广度优先搜索。
• 存储结构影响算法效率：顺序存储适合随机访问，链式存储适合频繁插入/删除。

总结

数据结构是计算机科学的基础，通过合理选择逻辑结构（线性/非线性）和存储结构（顺序/链式等），结合高效算法（如排序、查找），可显著提升程序性能。实际应用中需权衡时间与空间复杂度，例如哈希表适合快速查询但需处理冲突，树结构适合层次化数据但需维护平衡。