数据结构入门：从逻辑结构到抽象数据类型

"这是一份适合初学者的数据结构学习笔记，源自青岛大学王卓老师在B站上的课程。笔记主要涵盖了数据结构的逻辑结构和存储结构两大方面，并通过实例介绍了抽象数据类型的定义方法。笔记使用typora软件进行阅读。" 在数据结构中，逻辑结构和存储结构是两个核心概念。 **逻辑结构**主要关注数据元素之间的关系，而不是它们在内存中的具体位置。根据关系的不同，逻辑结构可以划分为两类： 1. **线性结构**：每个数据元素最多只有一个直接前驱和一个直接后继。常见的线性结构有线性表（如数组、链表）、栈和队列，以及字符串。 2. **非线性结构**：数据元素可能存在多个前驱和后继。典型的非线性结构包括树（如二叉树、AVL树等）和图（如有向图、无向图）。 此外，还可以按照不同的标准将逻辑结构分为集合、线性、树状和图状结构： - **集合结构**：所有数据元素仅属于同一集合，没有特定关系。 - **线性结构**：数据元素间存在一对一的线性关系。 - **树状结构**（层次关系）：数据元素间是一对多的关系，形成层级结构。 - **图状结构或网状结构**：数据元素间存在多对多的任意关系。 **存储结构**决定了数据在计算机内存中的组织方式，通常包括以下四种： 1. **顺序存储结构**：数据元素存储在一组连续的内存单元中，逻辑关系通过元素的位置体现，比如数组。 2. **链式存储结构**：数据元素的存储位置可以不连续，通过指针连接，如链表。 3. **索引存储结构**：使用索引表来快速定位数据元素，如B树、B+树。 4. **散列存储结构**：通过散列函数将数据映射到特定位置，实现快速查找，如哈希表。 **抽象数据类型（ADT）**是数据结构理论中的一个重要概念，它定义了一组数据对象，这些对象的数据关系和对这些对象的操作。例如，ADT Circle 表示一个圆，包括圆的半径作为数据对象，而操作如设置半径、计算面积等则是其基本操作。同样，ADT Complex 表示复数，包含实部和虚部，提供了构造复数、加法、乘法等操作。 在定义ADT时，需要明确基本操作的参数类型（赋值参数或引用参数），以及操作的初始条件和操作结果，确保操作的正确性和有效性。 通过这份笔记，初学者可以逐步理解数据结构的基本概念，为进一步深入学习算法和编程打下坚实基础。