Home DS复习 Part 1
Post
Cancel

DS复习 Part 1

考研复习进入了白热化阶段. 博客好久没更了. 代码好久没写了. fo 和 ⭐️ 都快要掉没了.

绪论

数据结构

数据元素: 数据的基本单位

数据项: 构成数据元素的不可分割的最小单位

一个数据元素可以由若干个数据项组成

数据对象: 性质相同的数据元素的集合, 是数据的子集

数据类型: 一个值的集合和定义在此集合上的一组操作的总称. 包括: 原子类型, 结构类型, 抽象数据类型 (ADT)

数据结构: 相互之间存在一种或多种特定关系数据元素的集合. 结构就是数据元素之间的关系. 由三个方面决定:

  • 逻辑结构: 集合, 线性, 树形, 图状或网状
  • 存储结构: 顺序, 链式, 索引, 散列
  • 数据的运算: 运算的定义和实现 (运算的定义针对逻辑结构, 运算的实现针对存储结构)

要定义一个数据结构, 就要包括: 数据对象 (是数据的子集 -> 就是数据 -> 包含数据的基本单位“数据元素”)、数据关系 (数据元素之间的关系)、数据运算 (施加在数据上的运算, 是各种基本操作的集合)

ADT 描述了数据的逻辑结构和数据的运算, 用 (数据对象, 数据关系, 数据运算) 来描述. 因此 ADT 可以定义一个完整的数据结构.

逻辑结构: 包括线性结构和非线性结构. 线性结构就是线性表 (一般线性表, 受限线性表, 数组), 非线性结构就是集合、树、图 (网).

存储结构也称物理结构, 是用计算机语言实现的逻辑结构.

  • 顺序: 逻辑上相邻的物理上也相邻. 可以随机存取. 但是只能连续存储, 会产生碎片.
  • 链式: 逻辑上相邻的物理上不一定相邻. 不能随机存取, 只能顺序存取. 要存指针. 但是不会产生碎片.
  • 索引: 用索引表来存储数据元素的地址. 既可以随机存取, 又可以顺序存取. 检索快. 要存索引表. 索引项格式: (关键字, 地址).
  • 散列: Hash. 用散列函数根据元素的关键字直接计算存储地址. 既可以随机存取, 又可以顺序存取. 检索快, 增/删快. 散列函数的设计要尽量避免冲突.

有序表: 关键字有序的线性表.

链式存储中, 结点间可以不连续, 但结点内一定连续, 因为是数据类型是结构类型 (相当于一个结构体).

算法

算法: 问题求解步骤的描述、指令的有限序列 (每一条指令表示一个或多个操作).

算法的五个特性 (必要条件): 有穷性, 确定性, 可行性, 输入, 输出.

算法的设计要求: 正确性, 可读性, 健壮性, 高效率与低存储量需求.

算法的度量: 时间复杂度 (取决于: 问题的规模、输入数据的性质)、空间复杂度 (包括: 存储程序指令及常/变量数据的空间、操作和运算所需的辅助空间).

算法原地工作: 算法所需的辅助空间为常量.

线性表

线性表: 相同数据类型的数据元素的有限序列.

\[L=(a_1, a_2, \cdots, a_n)\]

表头元素: $a_1$, 表尾元素: $a_n$.

性质:

  • 除了 $a_1$, 其他元素都有且仅有一个直接前驱; 除了 $a_n$, 其他元素都有且仅有一个直接后继.
  • 有前驱后继关系 -> 表中元素具有逻辑上的顺序性.
  • 数据类型相同: 每个数据元素占有相同大小的存储空间.

线性表是逻辑结构, 邻接表是存储结构. 我认为这个很好区分, 因为邻接表就是一种可以用 C++ 实现出来的数据结构. 而线性表不行, 不能直接用计算机语言实现.

一些约定俗成的题目中的写法:

  • L 表示线性表. 线性表结构体中的 data 表示数据元素数组, length 表示线性表的长度.
  • SqList 表示顺序表的类型结构体, 因此函数参数通常写成 SqList &L.
  • ElemType 表示数据元素.
  • 如果题目说要“显示出错信息并退出运行”, 则函数的返回类型要是 bool.

顺序表

顺序表: 用一段地址连续的存储单元依次存储线性表的数据元素 (线性表的顺序存储. 结合上一节所说的顺序存储结构, 那就是逻辑顺序和物理顺序相同).

性质:

  • $a_i$ 中的 i 是元素 $a_i$ 在线性表中的位序. 其内存地址: $LOC(L)+(i-1)\cdot sizeof(ElemType)$.
  • 可随机存取. 但插入和删除操作需要移动大量元素, 效率低 (因此不方便).
  • 存储密度高 (因为每个结点只存储数据元素, 不需要存储指针).

线性表中的位序是从 1 开始的, 数组的下标是从 0 开始的.

静态分配:

1
2
3
4
5
#define MAXSIZE 50
typedef struct {
    ElemType data[MAXSIZE];
    int length;
} SqList;

动态分配: 仍然是顺序存储, 只是分配的空间大小可以动态决定.

1
2
3
4
typedef struct {
    ElemType *data;
    int MAXSIZE, length;
} SqList;

动态分配语句:

1
L.data = (ElemType *)malloc(InitSize * sizeof(ElemType));
1
L.data = new ElemType[InitSize];

插入: 可插入的位置有 n+1 个. 在第 i 个位置插入, 需要移动 n+1-i 个元素. 平均 O(n).

删除: 可删除的位置有 n 个. 在第 i 个位置删除, 需要移动 n-i 个元素. 平均 O(n).

查找: 顺序查找, 位于第 i 个位置就需要比较 i 次. 平均 O(n).

链式存储

链表: LinkList L, L.data 表示数据元素, L.next 表示指针域.

结构体被 typedef 之后, 可以直接用 LNode 来表示结构体类型.

1
2
3
4
typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

头结点头指针: 无论有没有头结点, 头指针都一定要有, 并且指向链表中的第一个结点. 在带头结点的链表中, 头指针就指向头结点; 在不带头结点的链表中, 头指针就指向第一个数据结点.

使用头结点的目的: 方便运算的实现. 因为这样就可以让每个结点的操作得到统一, 不用考虑当前结点是不是第一个数据结点的特殊情况.

创建带头结点的链表: L = (LinkList)malloc(sizeof(LNode)) 创建头结点, L->next = NULL 初始化为空表.

创建结点: LNode *p = new LNode;LNode *p = (LNode *)malloc(sizeof(LNode));

判空:

  • 带头结点的链表: L->next == NULL.
  • 不带头结点的链表: L == NULL.

插入:

  • 头插法: O(n). 用头指针 L 就可以指示插入位置;
  • 尾插法: O(n). 除了一定要有的头指针 L 外, 还需要一个尾指针指向最后一个结点, 指示插入位置.

查找:

  • 按序号查找: O(n). 从第一个结点开始, 顺着 next 依次向后查找, 直到找到第 i 个结点为止. 头结点的序号是 0, 第一个数据结点的序号是 1. 因此, 查找第 i 个结点其实是查找第 i 个数据结点, 不包括头结点. 需要比较 i 次 (比较的是 i).
  • 按值查找: O(n). 从第一个结点开始, 顺着 next 依次向后查找, 直到找到第一个值为 e 的结点为止. 最坏需要比较 n 次 (比较的是 p->data).

在第 i 个位置插入元素 e: O(n). 需要找到第 i-1 个结点 (找到待插入位置的前驱结点), 然后插入.

删除第 i 个位置的元素: O(n). 需要找到第 i-1 个结点 (找到待删除位置的前驱结点), 然后释放该结点 (free(q)).

求表长: O(n). 从第一个结点开始, 顺着 next 依次向后查找, 每访问一个节点计数器就加 1, 直到为 NULL. 需要比较 n 次.

双向链表

双向链表: DLinkList L, 结构体是 DNode.

有前驱、后继指针.

1
2
3
4
typedef struct DNode {
    ElemType data;
    struct DNode *prior, *next;
} DNode, *DLinkList;

循环链表

循环单链表

尾指针 *rnext 指向头结点.

判空: L == r.

仅设尾指针, 不设头指针. 因为头结点就是尾结点的后继.

如果设头指针, 则操作表尾需要 O(n); 如果设尾指针, 则操作表头和表尾都只是 O(1).

循环双链表

判空: L->next == L && L->prior == L.

静态链表

借助数组来描述线性表的链式结构.

链表: SLinkList L, 结构体是 SNode.

数组: SNode L[MAXSIZE].

1
2
3
4
typedef struct SNode {
    ElemType data;
    int next;
} SNode, SLinkList[MAXSIZE];

或者直接:

1
2
3
4
typedef struct {
    ElemType data;
    int next;
} SLinkList[MAXSIZE];

next 是游标, 为 -1 时表示无指向.

和顺序表一样, 静态链表也需要预先分配一块连续的存储空间.

线性表的顺序存储结构和链式存储结构的比较

  1. 存取方式: 顺序表可以顺序存取、随机存取, 链表只能 (从表头) 顺序存取.
  2. 逻辑/物理结构: 顺序存储时, 逻辑相邻的物理上也相邻, 要分配连续存储空间; 链式则不需要, 但是结点的存储密度低,多出了指针域.
  3. 查找/插入/删除操作: 按值查找时, 若顺序表有序, 则可以二分查找, 时间复杂度为 O(logn), 否则顺序表和链表都是 O(n). 按序号查找时, 顺序表支持随机访问, 仅 O(1). 顺序表的插入和删除需要移动大量元素, 时间复杂度为 O(n), 链表的插入和删除只需要修改指针, 时间复杂度为 O(1).
  4. 空间分配: 静态存储分配的顺序表不能扩充, 动态存储分配的顺序表虽能扩充但要移动大量元素. 链表就很灵活, 需要时就可申请.

如何选择存储结构:

  • 顺序表适合查找多、插入删除少的情况, 否则最好用链表 (对于链表, 虽然在特定位置插入或者删除特定元素也需要从头开始比较和查找, 但是不用移动大量元素!).
  • 难以估计线性表存储规模时, 用链表.

需要注意的地方

有尾指针的链表在删除某个结点后, 需要判断这个结点是不是尾结点, 如果是, 则需要将尾指针指向新的尾结点.

This post is licensed under CC BY 4.0 by the author.