数据结构的基本概念

复习定位

数据结构是计算机存储、组织数据的方式。选择合适的数据结构直接影响算法的效率——一个电话本按姓名排序还是按号码排序直接决定"按号码查人"的速度差异。这一节厘清数据/数据元素/数据项这些基本名词和逻辑结构与存储结构的区别——后面的线性表/栈/队列/树等是这些概念的具体化。

数据、数据元素、数据项

数据——客观事物的符号表示——计算机程序可处理的数字、文本、图像、音视频等在计算机中的二进制编码。通常将所有输入计算机的内容统称为数据。

数据元素——数据的基本单位。在数据处理中——一个记录(如一个学生的信息)就是一个数据元素。有时一个数据元素由多个数据项组成——数据项是最小不可分割的原子单位(如学生的学号、姓名、年龄)。

数据对象——性质相同的数据元素的集合——整数的数据对象是全体整数集合、学生数据对象的全体学生的集合。

逻辑结构与物理结构

逻辑结构描述数据元素之间的逻辑关系——与数据在计算机中的存储无关：

逻辑结构	特征	典型
集合结构	元素同属一个集合——无其他关系	哈希表元素
线性结构	元素间一对一关系	链表、数组
树形结构	元素间一对多关系	目录树、家族树
图形结构	元素间多对多关系	社交网络图

物理结构(存储结构)描述数据在计算机中的表示和存储——依赖于具体的存储介质(内存/外存)：

顺序存储——用一组连续的内存单元依次存储数据元素——数据元素之间的逻辑关系通过元素在存储器中的"相对位置"隐含表示——C语言中的数组是顺序存储的典型。优点是随机存取快(任意下标O(1))、存储空间紧凑。缺点是插入/删除操作需要移动大量元素——效率较低。

链式存储——用一组不一定连续的存储单元存储数据元素——元素之间的逻辑关系通过附加的指针字段显式表示——C语言中的结构体+指针是链式存储的典型。优点是在已知元素所在位置的条件下插入/删除快(只需修改指针)不需要移动大量元素。缺点是每个元素需要额外的存储空间存放指针、不能随机存取(必须按顺序从第一个元素开始遍历)。

抽象数据类型的表示与实现

抽象数据类型(ADT)是指一个数学模型以及定义在该模型上的一组操作。ADT的定义只关心"做什么"——不关心"怎么做"(由具体的语言实现)。例如栈的ADT：结构——一个线性表——操作: push,pop,top,isEmpty,isFull。开发者使用栈时——不需要知道栈是用数组还是链表实现的——因为ADT封装了实现细节。C++的class和Java的interface都体现了ADT的封装理念。

数据结构三要素

数据结构 = 逻辑结构 + 存储结构 + 操作(运算)。同一逻辑结构可以选择不同的存储结构来应对不同的使用场景。同一个存储结构也可以支持多种操作。例如线性表——顺序存储时能快速随机访问但插入慢；链式存储时插入快但不能随机访问。在实际工程中——数据的组织方式决定算法的效率。理解了基本概念——后绪的各种结构选择需要考量的本质就是"时间与空间的权衡"。

复习检查

1. 数据、数据元素、数据项之间的关系——给出一个"员工表"的例子分别说明三项。

2. 逻辑结构中的线性结构和树形结构的本质差别——一对多和多对多的区别在哪个层次？

3. 顺序存储和链式存储各自什么优缺点——给出分别适合两种存储结构的实际场景。

4. 抽象数据类型(ADT)——用char*和链表分别实现一个队列的enqueue和dequeue操作——用户代码仅仅通过队列的头文件定义的结构体指针操作头尾节点——具体实现被藏在了哪里？

5. 数据结构的"三要素"之间的例子——二叉树的逻辑结构多种(前序/中序/后序下的抽象中表示了三种遍历操作)——两种存储结构(顺序/链式)——如何组合一棵二叉树的逻辑存储结构及其前序遍历操作？