数据结构基本概念：不要把逻辑关系和存放位置混在一起

同学，上一课已经把现实问题拆成对象、关系和操作。今天的新困难是给这些层次准确命名：同一句“相邻”，可能指逻辑上的前后，也可能指内存地址连续，两者不是一回事。

数据是能被计算机识别处理的符号集合；数据元素是讨论时的基本单位；一个元素内部还可由若干数据项构成。例如学生表是一组数据，一名学生是一条数据元素，学号和姓名是数据项。具有相同性质的数据元素集合可称为数据对象。

数据结构通常由三部分共同决定：

• 逻辑结构描述元素之间的关系，可概括为集合、线性、树形和图状结构；
• 存储结构描述这种关系怎样落到机器中，常见有顺序、链式、索引和散列；
• 数据运算规定允许执行什么，以及这些操作在具体存储下如何实现。

陪做：线性表 $(a_1,a_2,a_3)$ 中，$a_2$ 在逻辑上是 $a_1$ 的后继。用数组存储时，它们通常物理相邻；用链表存储时，两个结点的地址可以相距很远，只靠指针维持同一逻辑关系。因此“线性表必须连续存放”是错的，连续只是顺序存储的特征。

再区分抽象数据类型 ADT：它强调数据对象、关系和操作接口，例如“栈只允许在一端插入删除”；至于底层用数组还是链表，是实现选择。判断依据是题目在谈“允许做什么”，还是“具体怎样存和怎样做”。

针对性错解：把数据元素与数据项互换，会在题目层级上出错；把链表说成非线性结构，是拿物理地址替代逻辑关系；认为同一逻辑结构只有一种存储实现，也会错过时间与空间权衡。

迁移题：图的邻接矩阵与邻接表改变了图的逻辑结构吗？答案没有，它们都表达顶点和边的图状关系，只是存储结构不同；稠密图常用矩阵更直接，稀疏图用邻接表更省空间。独立验收是能为一个例子分别指出数据项、元素、逻辑结构、存储结构和操作。下一课用复杂度比较不同实现，而不是只看一次运行秒数。