Elian's blog page

数据、数据元素、数据项核心定义 数据：数据是信息的载体，是描述客观事物属性的数、字符，以及所有能输入计算机并被程序识别、处理的符号集合。数据是程序加工的原料。 数据元素：数据的基本单位，通常作为一个整体被考虑和处理。 数据项：构成数据元素的不可分割的最小单位。 数据对象：具有相同性质的数据元素的集合，是数据的一个子集。 数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 层级关系数据对象由多个数据元素组成；数据元素又可由多个数据项组成。数据结构课程主要关心数据元素之间的关系，以及基于这些关系的操作，不重点关心某个数据项内部的业务含义。 易混点数据元素和数据项的划分取决于问题需求。同一份现实信息，在不同任务中可能有不同粒度：如果“学生”作为整体处理，学生就是数据元素，学号、姓名、成绩是数据项；如果只研究成绩序列，单个成绩也可以成为数据元素。 关联理解这一层级后，再看 数据结构的三要素 会更自然：逻辑结构讨论数据元素之间的关系，存储结构讨论这些关系在计算机中的表示，数据运算讨论在这些元素及关系上做什么。

数据结构的三要素讨论一种数据结构时，始终抓住三个方面：逻辑结构、存储结构、数据运算。 逻辑结构逻辑结构回答“数据元素之间是什么关系”。它不关心数据具体放在内存哪里，只描述抽象关系。常见类型见 逻辑结构类型。 存储结构存储结构也叫物理结构，回答“如何在计算机中表示这些逻辑关系”。常见方式包括顺序存储、链式存储、索引存储、散列存储，见 存储结构类型。 数据运算数据运算包括运算的定义和实现： 运算的定义：针对逻辑结构，说明运算功能，例如队列的入队、出队、求长度。 运算的实现：针对存储结构，说明具体操作步骤，例如顺序队列和链队列的入队实现不同。 考点提示抽象地定义一种数据结构，通常是在定义它的逻辑结构和基本运算；真正写程序时，必须选定存储结构，才能落实这些运算的实现方式。存储结构不同，会直接影响空间分配是否方便、插入删除是否高效、查找是否快捷。 关联抽象数据类型 用数学化方式定义逻辑结构和运算。选定存储结构后，运算实现的效率还需要结合具体代码分析。

数据类型与抽象数据类型数据类型数据类型是一个值的集合，以及定义在这个集合上的一组操作的总称。 原子类型：值不可再分的数据类型，例如 bool、int。 结构类型：值可以再分解为若干分量的数据类型，例如结构体。 数据类型不仅包含“能取哪些值”，还包含“能做哪些操作”。例如 int 不只是整数范围，还包括加、减、乘、除、取模等操作。 抽象数据类型抽象数据类型（ADT）是抽象的数据组织及与之相关的一组操作。ADT 用数学化语言定义数据的逻辑结构和运算，与具体存储实现无关。 与数据结构的关系定义一个 ADT，本质上是在定义一种数据结构的逻辑结构和运算；选择存储结构后，才能实现这种数据结构。比如“线性表”作为 ADT 可以规定插入、删除、查找等操作，而它可以用 顺序表或链表 实现。 ADT 强调抽象与实现解耦。

双链表 定义双链表的每个结点包含数据域、前驱指针和后继指针： 1234typedef struct DNode { ElemType data; struct DNode *prior, *next;} DNode, *DLinkList; 相比单链表，双链表可以从当前结点直接访问前驱和后继，弥补单链表无法逆向检索的局限。 初始化：带头结点空的带头结点双链表通常满足： 12L->prior = NULL;L->next = NULL; 头结点不存储有效数据。 后插操作在结点 prev 后插入结点 newNode，若 prev 有后继结点： ↻ + − 1234newNode->next = prev->next;prev->next->prior = newNode;newNode->prior = prev;prev->next = newNode; 若 prev 是最后一个结点，prev->next == NULL，不能执行 prev->next->prior...

线性表定义与基本操作 定义线性表是具有相同数据类型的 n (n >= 0) 个数据元素的有限序列。n 为表长，n = 0 时为空表。 一般表示为： $$L = (a_1, a_2, …, a_i, a_{i+1}, …, a_n)$$ 其中 a_i 是第 i 个元素，i 称为位序。位序从 1 开始，数组下标通常从 0 开始，这是顺序表代码题常见易错点。 $a_1$ 是表头元素，$a_n$ 是表尾元素。表头元素没有直接前驱，表尾元素没有直接后继。 逻辑特征 所有数据元素具有相同数据类型。 元素有次序。 除第一个元素外，每个元素有且仅有一个直接前驱。 除最后一个元素外，每个元素有且仅有一个直接后继。 线性表强调有限序列。若只说“所有整数按递增次序排列”，由于整数集合无限，不能直接看作通常意义上的线性表。 基本操作 InitList(&L)：初始化表，构造空表并分配必要空间。 DestroyList(&L)：销毁表，释放占用空间。 ListInsert(&L, i, e)：在第 i 个位置插入元素 e。 ListDelete(&L,...

逻辑结构类型逻辑结构描述数据元素之间的抽象关系，常见四类如下。 集合结构各元素同属一个集合，除此之外没有其他关系。重点是“属于同一整体”，元素之间无前驱、后继、层级或连接关系。 线性结构数据元素之间是一对一关系。除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继。线性表 是典型线性结构。 树形结构数据元素之间是一对多关系。一个元素可以有多个后继，但通常只有一个直接前驱。树、二叉树属于这一类。 图结构数据元素之间是多对多关系。任意两个元素之间都可能存在关系，适合描述网络、路线、依赖关系等。 记忆框架集合：同属一个整体；线性：一对一；树：一对多；图：多对多。复习时不要被具体存储方式干扰，逻辑结构只问“关系是什么”。

顺序表的插入与删除插入操作ListInsert(&L, i, e) 表示在顺序表 L 的第 i 个位置插入元素 e。 ↻ + − 合法范围：1 <= i <= L.length + 1。 基本步骤： 判断插入位置是否合法。 判断表是否已满。 从最后一个元素开始，到第 i 个元素为止，依次后移一位。 将 e 放入第 i 个位置，即数组下标 i - 1。 length 加 1。 注意移动顺序必须从后往前，否则会覆盖尚未移动的元素。 1234567891011bool ListInsert(SqList *list, int index, ElemType value) { if (index < 1 || index > list->length + 1) return false; if (list->length >= MaxSize) return false; for (int moveIndex = list->length; moveIndex >= index;...

顺序表的存储与实现 定义顺序表是用顺序存储方式实现的 线性表。它把逻辑上相邻的数据元素存放在物理位置也相邻的存储单元中。 若第一个元素地址为 LOC(L)，每个元素占 sizeof(ElemType) 字节，则第 i 个元素的地址为： LOC(a_i) = LOC(L) + (i - 1) * sizeof(ElemType) 因此顺序表可通过地址公式直接定位元素。 静态分配典型结构： 12345#define MaxSize 10typedef struct { ElemType data[MaxSize]; int length;} SqList; 特点： data 是固定长度数组。 length 记录当前表长。 存储空间大小在定义后固定，容量不可变。 若数组未初始化，未使用区域可能有脏数据；合法访问应依据 length，不应把未使用位置当作有效元素。 一个最小初始化函数： 123void InitList(SqList *L) { L->length = 0;} 不必把 data...

顺序表的查找按位查找GetElem(L, i) 获取顺序表中第 i 个位置的元素。 由于顺序表连续存储，可通过地址公式或数组下标直接访问： L.data[i - 1] 时间复杂度：O(1)。 按值查找LocateElem(L, e) 查找第一个值等于 e 的元素，并返回其位序。 基本思路：从表头开始依次比较，找到则返回 i + 1，遍历结束仍未找到则返回失败标记。 时间复杂度： 最好情况：第一个元素命中，O(1)。 最坏情况：最后一个元素命中或查找失败，O(n)。 平均情况：元素位置等概率时，O(n)。 结构类型比较C 语言中结构体通常不能直接用 == 比较整体是否相等，应逐个比较关键分量，或定义专门的比较函数。 有序表补充若顺序表内元素有序，按值查找可使用二分查找，时间复杂度可降为 O(log_2 n)。无序顺序表通常只能顺序查找。 关联顺序表按位查找优于链表，见 顺序表与链表对比。链表查找见 单链表的查找与建立。

顺序表与链表对比共同点顺序表和链表都用于实现 线性表，逻辑结构都是线性结构。区别主要来自存储结构不同。 存储结构对比 项目 顺序表 链表 存储方式 顺序存储 链式存储 空间要求 需要连续空间 可使用离散空间 存储密度 高，只存数据元素 低，需要额外指针域 容量变化 不方便，扩容代价高 较方便，按需申请结点 随机存取 支持 不支持 初始化与销毁顺序表初始化通常需要预分配一大片连续空间。静态分配容量不可变；动态分配容量可变，但扩容仍可能需要移动大量元素。 链表初始化只需建立头指针或头结点，之后按需申请结点。销毁链表时需要依次释放各结点。 插入与删除顺序表插入、删除时，主要时间开销来自移动元素，平均时间复杂度为 O(n)。 链表插入、删除时，修改指针本身是 O(1)，但若需要先查找目标位置或前驱结点，总时间通常仍为 O(n)。它的优势是找到位置后不需要移动大量元素。 查找 顺序表按位查找：O(1)。 链表按位查找：O(n)。 顺序表和链表按值查找：通常都是 O(n)。 若顺序表有序，可使用二分查找达到 O(log_2...