快速复习数据结构

发表于 更新于 分类于 ， 阅读次数： Waline： 本文字数： 10k 阅读时长 ≈ 9 分钟

快速理解数据结构，方便记忆。

[[toc]]

第一章 绪论

本章重点为时间复杂度的计算，还有逻辑结构和物理结构，能够分清哪些是线性结构，哪些属于非线性结构。

1.1 基本概念

数据结构 是互相之间存在一种或多种特定关系的数据元素的集合。

可以用抽象数据类型定义一个完整的数据结构。

数据的逻辑结构和物理结构可以看上面的思维导图。

存储结构：

  • 顺序存储
  • 链式存储
  • 索引存储
  • 散列存储

在链式存储设计时，不同节点的存储单元可以不连续，但是节点内的存储单元必须连续。

在存储数据时，通常不仅要存储各数据元素之间的值，而且要存储数据元素之间的关系。

1.2 算法和算法评价

算法 是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或多个操作。

5个重要特性：

  1. 有穷性
  2. 确定性
  3. 可行性
  4. 输入
  5. 输出

常见的时间复杂度：

\[ O(1) < O(log_2n) < O(n) < O(nlog_2n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n) \]

算法的时间复杂度为 \(O(n^2)\) ，表明该算法的执行时间与\(n^2\) 成正比。

例：

1
2
3
4
5
void fun(int n) {
    int i = 1;
    while(i <= n)
        i = i * 2;
}

此时时间复杂度为：

执行次数设为t,i每次都乘2，那么总的次数就为

$$

2^t n \ t log_2n

$$

时间复杂度就为：\(O(log_2n)\)

需要注意的一些问题：

算法原地工作的含义是指需要常量的额外辅助空间
在相同规模下，复杂度为O(n)的算法在时间上总是优于复杂度为 \(O(2^n)\) 的算法
所谓时间复杂度，是指最坏情况下估算算法执行时间的一个上界
同一个算法，实现语言的级别越高，执行效率越低

第二章 线性表

线性表是算法命题的重点！！！

2.1 线性表定义和基本操作

线性表 是具有相同数据结构的 n 个数据元素的有限序列。

在线性表中，除开始元素外，每个元素只有唯一的前驱元素。

需要注意线性表是从下标1开始的！！！！！

2.2 线性表的顺序表示

线性表的顺序存储又称 顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相连。 因此可以 随机存储 表中的任何一个元素。

缺点：

元素的插入和删除需要移动需要大量的元素，插入操作平均需要移动 \(n / 2\) 个元素，删除操作平均需要移动 \((n - 1) / 2\) 个元素，而且存储 分配需要一段连续的存储空间。

优点：

  1. 随机访问，即通过首地址和元素序号可在时间O(1)内找到指定的元素。
  2. 顺序表存储密度高，每个节点只存储数据元素。

顺序表的类型描述：

1
2
3
4
5
#define MaxSize 50              // 定义线性表的最大长度
typedef struct {
    ElemType data[MaxSize];     // 顺序表的元素
    int length;                 // 顺序表的当前长度
} SqList;

顺序表的插入操作

对于插入算法，若表长为n，则在第i个位置插入元素，则从 \(a_n\) 到 \(a_i\) 都需要向后移动一个位置，共需移动n - i + 1 个元素，平均时间复杂度为O(n)

对于移动了多少个元素来说，更好的做法是可以举例去数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 判断i 的范围是否有效，否则非法
// 判断当前存储空间是否已满，否则不能插入

bool ListInsert(SqList &L, int i, ElemType e) {
    if(i < 1 || i > L.length + 1)           // 判断 i 的范围是否有效
        return false;
    if(L.length >= MaxSize)                 // 当前存储空间已满，不能插入
        return false;
    for(int j = L.length; j >= i; j--)      // 将第 i 个元素及之后的元素后移
        L.data[j] = L.data[j - 1];
    L.data[i - 1] = e;                      // 在位置 i 处放入 e
    L.length++;                             // 线性表长度加 1
    return true;
}

顺序表的删除操作

对于删除算法，若表长为n，当删除第i个元素时，从\(a_{i+1}\)到\(a_n\)都需要向前移动一个位置，则共需移动n-i个元素，平均时间复杂度为：O(n)。

1
2
3
4
5
6
7
8
9
bool ListDelete(SqList &L, int i, Elemtype &e) {
    if( i < 1 || i > L.length)          // 判断 i 的范围是否有效
        return false;
    e = L.data[i-1];                    // 将被删除的元素赋值给e
    for(int j = i; j < L.length; j++)   // 将第i个位置后的元素前移
        L.data[j-1] = L.data[j];
    L.length--;                         // 线性表长度减一
    return true;
}

顺序表的查找

  1. 按序号查找，时间复杂度为O(1)。
  2. 按值x查找，主要运算是比较操作，比较次数与值x在表中的位置有关，也与表长有关，平均比较次数为\((n + 1)/2\)，时间复杂度为O(n)。

小结

存储空间 = 表长 * sizeof(元素的类型)

2.3 线性表的链式表示

单链表 是指通过一组任意的存储单元来存储线性表中的元素。为了建立元素之间的线性关系，对每个链表节点，除了存放元素自身的 信息，还需要存放一个指向其后继的指针。

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

利用单链表可以解决顺序表需要大量连续存储单元的缺点。

引入头节点：

  • 由于第一个数据节点的位置被存放在头节点的指针域中，因此在链表的第一个位置上的操作和在表的其他位置上的操作一致，无须进行特殊处理。

  • 无论链表是否为空，其头指针都指向头节点的非空指针（空表中头节点的指针域为空），因此空表和非空表的处理也就得到了统一。

单链表的建立

头插法建立单链表

核心代码：

1
2
s->next = L->next;      // 1.新结点的指针指向原链表的第一个指针
L->next = s;            // 2.头节点的指针指向新结点，L为头指针

采用头插法建立单链表时，读入数据的顺序与生成的链表中的元素的顺序是相反的。

每个结点插入时间为O(1)，设单链表长为n，则总的时间复杂度为o(n).

尾插法建立单链表

若希望读入数据的顺序与生成的链表中元素的顺序一致，可采用尾插法。为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。

核心代码：

1
2
r->next = s;        // 原链表中的尾结点（r所指）的指针指向新结点
r = s;              // r指向新的表尾结点

时间复杂度为：O(n)

单链表的插入

插入操作是将值为x的新结点插入到单链表的第i个位置。先检查插入位置的合法性，然后找到待插入位置的前驱结点，即第i-1个结点，再在其后插入新结点。

1
2
3
p = GetElem(L, i-1);        // 查找插入位置的前驱节点
s->next = p->next;          // 1
p->next = s;                // 2

删除同理

2.4 双链表

单链表结点中只有一个指向其后继结点的指针，使得单链表只能从头节点依次顺序地向后遍历。访问后继结点的时间复杂度为O(1)， 访问前驱结点的时间复杂度为O(n)。

双链表结点中有两个指针prior和next，分别指向其前驱结点和后继结点。

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

插入和删除和单链表差不多，注意保持链不断就可以了。

2.5 循环链表

1. 循环单链表

仅设尾指针。

判空条件不是头节点的指针是否为空，而是尾结点是否等于头结点。

  • 若设头指针，对表尾进行操作需要O(n)的时间复杂度。
  • 若设尾指针r，r->next即为头指针，对表头与表尾进行操作都只需要O(1)的时间复杂度。

2. 循环双链表

和循环单链表不同的是，在循环双链表中，头结点的prior指针还需要指向表尾结点。

某结点*p为尾结点时，p->next == L;

当循环双链表为空表时，其头结点的prior域和next域都等于L。

2.6 静态链表

和顺序表一样，静态链表也需要预先分配一块连续的内存空间。

2.7 顺序表和链表的比较

顺序表 链表
存取（读写）方式 顺序存取，随机存取 顺序存取
逻辑结构与物理结构 逻辑上相邻的元素，对应的物理存储位置也相邻 逻辑上相邻的元素，物理存储位置不一定相邻
查找，插入和删除操作（按值查找） 无序时：O(n),有序：O(log2n)折半查找 O(n)
查找，插入和删除操作（按序号查找） O(1) O(n)
空间分配 静态存储下，需要预先分配 在需要时申请分配

第三章 栈，队列和数组

3.1 栈

栈是只允许在一端进行插入和删除的线性表。

栈顶：允许进行删除的那一端。

栈的特性为：后进先出

n个不同元素进栈，出栈元素不同的排列个数为 \(\frac{1}{n + 1}C_{2n}^n\)

3.1.1 栈的顺序存储

进栈： 栈不满时，栈顶指针先加1，再送值到栈顶元素。

出栈： 栈非空时，先取栈顶元素值，再将栈顶指针减1.

栈空条件： s.top == -1

栈满条件： s.top == MaxSize - 1

共享栈

仅当两个栈顶指针相邻（top1 - top0 = 1）时，判断为栈满。

共享栈是为了更有效地利用存储空间，存取数据的时间复杂度为O(1)

3.1.2 栈的链式存储

不存在栈满上溢的情况。

3.2 队列

队列是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。

特性：先进先出

1
2
3
4
5
#define MaxSize 50
typedef struct {
    ElemType data[MaxSize];
    int front, rear;
}SqQueue;

队头(Front)： 允许删除的一端

队尾(Rear)： 允许插入的一端

3.2.1 队列的顺序存储结构

队列的顺序实现是指分配一块连续的存储单元存放队列中的元素。

初始状态： q.front == q.rear == 0

进队： 队不满时，先送值到队尾元素，再将队尾指针加1

出队： 先取队头元素值，再将队头指针加1

队空：q.front == q.rear == 0

队满不能使用q.rear == MaxSize,因为会出现假溢出

3.2.2 循环队列

把存储队列元素的表从逻辑上视为一个环。

初始：q.front = q.rear = 0

队首指针进1: q.front = (q.front + 1) % MaxSize

队尾指针进1: q.rear = (q.rear + 1) % MaxSize

队列长度： (q.rear + MaxSize - q.front) % MaxSize

队空：q.front == q.rear

队满也是 q.front == q.rear

所以为了区分队空和队满，有三种处理方式：

  1. 牺牲一个单元来区分队空和队满，入队时少用一个队列单元，

队满条件：(q.rear + 1) % MaxSize == q.front

队空条件：q.front == q.rear

队列中元素个数：(q.rear - q.front + MaxSize) % MaxSize

元素出队：q.front = (q.front + 1) % MaxSize

元素入队：q.rear = (q.rear + 1) % MaxSize

  1. 类型中增设表示元素个数的数据成员。

队空：q.size == 0

队满：q.size == MaxSize

  1. 类型中增设tag数据成员，以区分是队满还是队空。tag = 0时，若因删除导致q.front == q.rear,则为队空， tag = 1时，若因插入导致q.front == q.rear,则为队满

3.2.3 队列的链式存储结构

当q.front == NULL 且 q.rear == NULL时，链式队列为空。

3.2.4 双端队列

双端队列是指允许两端都可以进行入队和出队操作的队列。

输出受限的双端队列

输入受限的双端队列

这里建议手动模拟

3.3 栈和队列的应用

  • 栈在括号匹配中的应用
  • 栈在表达式求值中的应用
  • 栈在递归中的应用
  • 队列在层次遍历中的应用
  • 队列在计算机系统中的应用（缓冲区）

重点讲下在表达式中的应用

例：

已知操作符包括+,-,*,/,(,),将中缀表达式a+b-a*((c+d)/e-f)+g转换为等价的后缀表达式ab+acd+e/f-*-g+时，用栈来存放暂时还 不能确定运算次序的操作符，栈初始时为空时，转换过程中同时保存在栈中的操作符的最大个数是（5）

将中缀表达式转换为前缀和后缀的快速方法：

我们可以画出对应的树后再求对应的前缀或后缀表达式。

我们以a/b+(c*d-e*f)/g为例

  1. 按照运算符优先级对所有的运算单位加括号

式子变为：( (a/b) + ( ( (c*d) - (e*f) ) / g ) )

  1. 转换为前缀表达式或后缀表达式

前缀：把运算符号移动到对应的括号前面

+ ( /(ab) /( -( *(cd) * (ef) ) g ))

去掉括号：

+/ab/-*cd*efg就是前缀表达式

后缀：把运算符移动到对应的括号后面，式子变为：

( (ab)/ (( (cd)* (ef)* ) -g) / ) +

去掉括号：

ab/cd*ef*-g/+就是后缀表达式

3.4 数组和特殊矩阵

数组是由n个相同类型的数据元素构成的有限数列。

3.4.1 对称矩阵

只存放主对角线和下三角区的元素。

对n阶对称矩阵压缩存储时，需要表长为n(n+1)/2的顺序表。

3.4.2 三角矩阵

具体的对应关系可以画图举例求证。

3.4.3 三对角矩阵

\[ 1 \le i,j \le n \] 在一维数组中存放的下标为k = 2i + j - 3 这里需要注意k是从0开始的。

在二维数组中的下标为：

\[ i = \lfloor (k + 1)/3 + 1 \rfloor \\ j = k - 2i + 3 \]

3.4.4 稀疏矩阵

稀疏矩阵压缩后便失去了随机存取特性。

稀疏矩阵的三元组既可以采用数组存储，也可采用十字链表法存储。

第四章 串

只需要掌握字符串的模式匹配，重点掌握KMP匹配算法的原理及next数组的推理过程，了解nextval数组的求解方法.

普通模式匹配的时间复杂读为O(mmn),KMP算法的时间复杂度为O(m + n)

KMP算法

右移位数： = 已匹配的字符数 - 对应的部分匹配值

j 1 2 3 4 5
S a b c a c
next

我们先理解下next[j]的含义：

在子串的第j个字符与主串发生失配时，则跳到子串的next[j]位置重新与主串当前位置进行比较。

现在我们讲下如何求解next数组：

我们把子串第一位的next值定义为0，后一位的next值则取决与它前面的字符，如果前面的字符与它的next值对应的字符相等， 则结果为这个next值加1，否则继续往前寻找，如果找到第一位后还没有找到，则结果为第一位的next值加1.

j 1 2 3 4 5
S a b c a c
next 0 1 1 1 2

j = 2时，前一位为a，前面没有字符了，结果为0+1=1;

j = 3时，前一位为b,它的next值对应的字符为a,继续往前匹配，前面没有字符了，结果为a对应的next值加1，即0+1=1;

j = 4时，前一位为c,它的next值对应的字符为a，继续往前匹配，前面没有字符了，所以结果为0+1=1；

j = 5时，前一位为a,它的next值对应的字符为a,匹配，则结果为前一位的a的next值加1，即1+1=2;

为了巩固我们再计算以下字符串的next数组：

j 1 2 3 4 5 6 7 8 9
S a b a a b c a b a
next 0 1 1 2 2 3 1 2 3

KMP 算法的进一步优化

求解nextval数组

j 1 2 3 4 5
S a a a a b
next 0 1 2 3 4
nextval 0 0 0 0 4

nextval值第一位也为0，

如果j对应的字符等于next[j]对应的字符，则继续往前寻找，如果不等于，或者到了开头，则nextval等于next[j]的值;

j = 2，对应的字符为a,next[2] = 1对应的字符为a，相等，继续寻找，但是到了开头，则nextval = next = 0;

j = 3，对应的字符为a,next[3] = 2对应的字符为a,相等，继续往前找，还是相等，直到开头，nextval = 0;

j = 4,同理；

j = 5,对应的字符为b,next[5] = 4对应的字符为a,不想等，所以nextval值直接就等于对应的next值，即 nextval = 4;

树与二叉树

需要掌握树与二叉树的性质，遍历操作，转换，存储结构和操作特性等，满二叉树，完全二叉树线索二叉树，哈夫曼树的定义与性质， 二叉排序树和二叉平衡树的性质与操作等。

树的基本概念

树是一种递归的数据结构，树作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点：

  1. 树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱
  2. 树中所有的结点可以有零个或多个后继

  1. 树中一个结点的孩子个数称为该结点的度，树中结点的最大度数称为树的度。图中的树中度为3.
  2. 度大于0的结点称为分支结点（非终端结点），度为0的结点称为叶子结点（终端结点）
  3. 结点的层次从根开始定义，根结点为第一层，结点的深度是从根结点开始自顶向下逐层累加，结点的高度是从叶结点开始自底向上逐层累加。树的高度是树中结点的最大层数
  4. 树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，而路径长度是路径上所经过的边的个数

以上不需要刻意记住，理解即可

树的性质

  1. 树中的结点数等于所有结点的度数之和加一
  2. 度为m的树中第i层上至多有\(m^{i-1}\)个结点（i >= 1）
  3. 高度为h的m叉树至多有\((m^h-1)/(m-1)\)个结点
  4. 具有n个结点的m叉树的最小高度为\(\lceil lom_m(n(m-1) + 1) \rceil\)

例：

在一颗度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是（）

我们根据性质1可以得出：

设叶结点个数为x

$$ 20 + 10 + 1 + 10 + x = 20 * 4 + 10 * 3 + 1 * 2 + 10 * 1 + 1 \

x = 82 $$

二叉树的概念

  1. 二叉树可以为空二叉树，即 n = 0

二叉树与度为2的有序树的区别：

  1. 度为2的树至少有3个结点，而二叉树可以为空
  2. 度为2的有序树的孩子的左右次序是相对与另一孩子而言的，若某个结点只有一个孩子，则无须区分左右次序，而二叉树孩子必须分左右

特殊的二叉树

术语 定义
满二叉树 一颗高度为h，且含有\(2^h - 1\)个结点的二叉树
完全二叉树 高度为h,有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时

完全二叉树的性质：

对完全二叉树按从上到下，从左到右的顺序编号，1,2,3,4...n

  1. 最后一个分支结点（非页结点）的编号：\(\lfloor n/2 \rfloor\),若\(i \le \lfloor n/2 \rfloor\),则结点i为分支结点，否则为叶子结点
  2. 叶子结点只可能在层次最大的两层上出现
  3. 如果有度为1的结点，只可能有一个且该结点只有左孩子，没有右孩子
  4. 按层序编号后，一旦出现某结点（其编号为i）为叶子结点或只有左孩子，则编号大于i的结点均为叶子结点
  5. 若n为奇书，则每个分支结点都有左子女和右子女；若n为偶数，则编号最大的分支结点(n/2)只有左子女，没有右子女。
  6. 结点i所在的层次（深度）为\(\lfloor log_2i \rfloor + 1\)
  7. 具有n个结点的完全二叉树的高度为\(\lceil log_2(n + 1) \rceil\)或\(\lfloor log2_n \rfloor + 1\)
  8. 当i > 1时，编号为i的结点的双亲结点的编号为\(\lfloor i/2 \rfloor\)
  9. 当\(2i \le n\)时，编号为i的结点的左孩子编号为2i;当\(2i + 1 \le n\)时，编号为i的结点的右孩子编号为 2i + 1

上面的需要在做题当中去理解，最好画图判断

二叉树的性质

  1. 非空二叉树上的叶子结点数等于度为2的结点数加1，即\(n_0 = n_2 + 1\)
  2. 非空二叉树上第k层上至多有\(2^{k-1}\)个结点
  3. 高度为h的二叉树至多有\(2^h - 1\)个结点

二叉树的存储结构

顺序存储结构

二叉树的顺序存储在最坏情况下，一个高度为h且只有h个结点的单支树却需要占据近\(2^h - 1\)个存储单元

链式存储结构

结构

lchild data rchild

在含有n个结点的二叉链表中，含有n + 1个空链域！！！！！

二叉树的遍历和线索二叉树

常见的遍历次序有先序（NLR）,中序(LNR)，后序(LRN)

先序遍历

  1. 访问根结点
  2. 先序遍历左子树
  3. 先序遍历右子树
1
2
3
4
5
6
7
void preOrder(Bitree T) {
    if(T != nullptr) {
        visit(T);
        preOrder(T->lchild);
        preOrder(T->rchild);
    }
}

中序遍历

  1. 中序遍历左子树
  2. 访问根结点
  3. 中序遍历右子树
1
2
3
4
5
6
7
void inOrder(Bitree T) {
    if(T != nullptr) {
        inOrder(T->lchild);
        visit(T);
        inOrder(T->rchild);
    }
}

后序遍历

  1. 后序遍历左子树
  2. 后序遍历右子树
  3. 访问根结点
1
2
3
4
5
6
7
void postOrder(Bitree T) {
    if(T != nullptr) {
        postOrder(T->lchild);
        postOrder(T->rchild);
        visit(T);
    }
}

时间复杂度为：O(n)

空间复杂度：O(n)

递归算法和非递归算法的转换

代码题

主要是DFS

层次遍历

需要借助一个队列

BFS

又遍历序列构建二叉树

  • 先序序列和中序序列可以唯一确定一颗二叉树
  • 后序序列和中序序列也可以唯一确定一颗二叉树
  • 层次序列和中序序列也可以唯一确定一颗二叉树
  • 只知道先序序列和后序序列，则无法唯一确定一颗二叉树

线索二叉树

除了第一个和最后一个结点，其他每个结点都有一个直接前驱和直接后继

在含有n个结点的二叉树中，有n + 1个空指针

线索二叉树是一种物理结构！！！！！

线索二叉树的结点结构

lchild ltag data rtag rchild

线索二叉树的存储结构：

1
2
3
4
5
typedef struct ThreadNode {
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;
}ThreadNode, *ThreadTree;

以这种结构构成的二叉链表作为二叉树的存储结构，称为线索链表，其中指向结点前驱和后继的指针称为索引。加上索引的二叉树称为线索二叉树

中序线索二叉树的构造

二叉树的线索化是将二叉链表中的空指针改为指向前驱或后继的线索。而前驱或后继的信息只有在遍历时才能得到，因此线索化的实质就是遍历一次二叉树。

下面我们以中序线索二叉树为例：

先序线索二叉树和后序线索二叉树

构建和中序线索一样，先遍历

如何在先序线索二叉树中找到结点的后继？

如果有左孩子，则左孩子就是其后继；如果无左孩子但有右孩子，则右孩子就是其后继；如果为叶结点，则右链域直接指示了结点的后继

在后序线索二叉树中找到结点的后继较为复杂，分为三种情况：

  1. 若结点x是二叉树的根，则其后继为空
  2. 若结点x是其双亲的右孩子，或是其双亲的左孩子且其双亲没有右子树，则其后继即为双亲
  3. 若结点x是其双亲的左孩子，且其双亲有右子树，则其后继为双亲的右子树上按后序遍历列出的第一个结点。

在后序线索二叉树上找后继需知道结点双亲，即采用带标记域的三叉链表作为存储结构。