考研笔记

数据结构的基本概念

这一节只在选择题里出现，考法几乎固定：给一个名词，判断它是逻辑结构、存储结构，还是一个完整的数据结构。 教材【复习提示】的原话是「本章内容是数据结构概述」，第 1 章真正的重点在 1.2 复杂度分析。

机制

1.1.1 六个术语

术语定义
数据信息的载体，是所有能输入计算机并被程序识别和处理的符号的集合
数据元素数据的基本单位，通常作为一个整体进行考虑和处理
数据项构成数据元素的不可分割的最小单位
数据对象具有相同性质的数据元素的集合，是数据的一个子集（如整数集 ）
数据类型一个值的集合和定义在此集合上的一组操作的总称
数据结构相互之间存在一种或多种特定关系的数据元素的集合

「基本单位」和「最小单位」是两个词。 数据元素是基本单位，数据项是最小单位。例如一条学生记录是一个数据元素，它由学号、姓名、性别等数据项组成。

数据类型分三类：

  • 原子类型：值不可再分。
  • 结构类型：值可以再分解为若干成分（分量）。
  • 抽象数据类型（ADT）：一个数学模型及定义在该模型上的一组操作。它定义了数据的取值范围、结构形式，以及对数据操作的集合。

ADT 可以定义一个完整的数据结构。 它通常用（数据对象，数据关系，基本操作集）这样的三元组表示，同时描述了逻辑结构和抽象运算。

1.1.2 数据结构三要素

数据结构包括三方面内容：逻辑结构、存储结构、数据的运算，缺一不可。三者的关系是：

  • 逻辑结构独立于存储结构：它从数据元素之间的逻辑关系描述数据，与计算机无关。
  • 存储结构不能独立于逻辑结构：它是逻辑结构在计算机中的映射，由计算机语言实现，依赖于计算机语言。
  • 算法的设计取决于逻辑结构，算法的实现依赖于存储结构。

逻辑结构的分类

flowchart TD
    L["数据的逻辑结构"] --> LIN["线性结构"]
    L --> NON["非线性结构"]
    LIN --> G1["一般线性表"]
    LIN --> G2["受限线性表<br/>栈和队列、串"]
    LIN --> G3["线性表推广<br/>数组"]
    NON --> S["集合"]
    NON --> T["树形结构<br/>一般树、二叉树"]
    NON --> GR["图状结构<br/>有向图、无向图"]

四类基本关系：

结构元素之间的关系
集合除「同属一个集合」外，别无其他关系
线性结构一对一
树形结构一对多
图状 / 网状结构多对多

集合在教材的分类图里属于非线性结构。 栈、队列、串、数组都是线性结构。

存储结构的四种方式

存储结构（物理结构）是数据结构在计算机中的表示，既要表示数据元素，也要表示元素之间的关系。

方式做法优点缺点
顺序存储逻辑上相邻的元素，物理位置也相邻；关系由存储单元的邻接关系体现随机存取；每个元素占用最少的存储空间只能使用一整块相邻的存储单元，可能产生较多外部碎片
链式存储不要求物理相邻，借助指针表示元素之间的逻辑关系不会出现碎片，能充分利用所有存储单元指针占用额外空间；只能顺序存取
索引存储存储元素的同时建立附加的索引表，索引项为（关键字，地址）检索速度快索引表占用额外空间；增删数据时也要修改索引表，花费较多时间
散列存储根据关键字直接计算存储地址，也称哈希（Hash）存储检索、增加和删除结点的操作都很快散列函数不好会产生冲突，解决冲突增加时间和空间开销

数据的运算

  • 运算的定义针对逻辑结构，指出运算的功能。
  • 运算的实现针对存储结构，指出运算的具体操作步骤。

同一逻辑结构、同一运算，换一种存储方式，效率就可能不同。例如在线性表中插入元素：顺序存储平均要移动近一半的元素，为 ；链式存储（已知插入位置时）为 。

边界

说法判断说明
「数据项是数据的基本单位」❌数据元素是基本单位，数据项是最小单位
「数据对象就是数据」❌数据对象是性质相同的数据元素的集合，是数据的子集
「有序表是一种存储结构」❌有序表只规定关键字有序这一逻辑关系，可以顺序存储也可以链式存储，属于逻辑结构
「顺序表、哈希表、单链表都是逻辑结构」❌三者同时描述逻辑结构、存储结构和运算，是三种完整的数据结构
「集合是线性结构」❌集合的元素之间除同属一个集合外别无关系，教材归入非线性结构
「栈、队列、字符串是非线性结构」❌都是线性结构；树和图才是典型的非线性结构
「存储结构独立于逻辑结构」❌方向反了：逻辑结构独立于存储结构，存储结构是逻辑结构在计算机上的映射
「逻辑结构唯一决定存储结构」❌同一逻辑结构可以有多种存储方式
「数据结构仅由逻辑结构和存储结构决定」❌三要素缺一不可，还有数据的运算
「存储数据时只需存储各元素的值」❌还要存储元素之间的关系
「两种不同的数据结构，逻辑结构或物理结构一定不同」❌二叉树和二叉排序树的逻辑结构、存储结构都可以相同，区别在运算的定义（查找的平均时间分别为 、）
「链式存储容易产生碎片」❌链式存储不会出现碎片；顺序存储才可能产生较多外部碎片
「链式存储可以随机存取」❌只能顺序存取

错题复盘：有序表属于哪一类（1.1.3 第 3 题）

四个选项是顺序表、哈希表、有序表、单链表，问哪个属于逻辑结构，答案是有序表。 另外三个名字里都带着存储方式（「顺序」「哈希」「链」），所以是完整的数据结构。 有序表只说了关键字有序，没说怎么存，因此只是逻辑结构。

错题复盘：数据结构的四个说法（1.1.3 第 4 题）

正确的是「数据的逻辑结构独立于其存储结构」。另外三个选项分别犯了三种错： 把依赖方向说反（存储结构独立于逻辑结构）；把「有多种选择」说成「唯一」（逻辑结构唯一决定存储结构）；漏掉运算（仅由逻辑结构和存储结构决定）。

考点

  • 基本单位（数据元素）与最小单位（数据项）。
  • 名词归类：有序表是逻辑结构；顺序表、哈希表、单链表是完整的数据结构。
  • ADT 可以定义一个完整的数据结构。
  • 三要素缺一不可；逻辑结构独立于存储结构，反之不成立。
  • 四种存储方式的优缺点，尤其是「顺序存储有外部碎片、链式存储无碎片」。

链接

反向链接