数据结构与算法915notes

LZC Lv4

2024-06-25 18:57:56 2024-08-26 14:15:59

数据结构

数据结构与算法915笔记

依照大纲目录结构

数据结构基本概念

考试内容

数据、数据元素、数据项、数据对象、数据结构的定义；

数据

数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据是计算机程序加工的原料。

数据元素

数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。

数据项

一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位。

数据对象

数据对象是具有相同性质的数据元素的集合，是数据的一个子集。

数据结构

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

在任何问题中，数据元素都不是孤立存在的，它们之间存在某种关系，这种数据元素相互之间的关系称为结构（Structure）。数据结构包括三方面的内容：逻辑结构、物理结构和数据的运算。

数据的逻辑结构和物理结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的物理结构。

数据的逻辑结构、数据的物理结构、数据的运算的定义；

数据的逻辑结构

逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。它与数据的存储无关，是独立于计算机的。

数据的逻辑结构分为线性结构和非线性结构，线性表是典型的线性结构；集合、树和图是典型的非线性结构。

数据的物理结构

存储结构是指数据结构在计算机中的表示（又称映像），也称物理结构。

它包括数据元素的表示和关系的表示。数据的存储结构是用计算机语言实现的逻辑结构，它依赖于计算机语言。

数据的存储结构主要有顺序结构、链式结构、索引存储和散列存储。

顺序结构

把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

其优点是可以实现随机存取，每个元素占用最少的存储空间；缺点是只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片。

链式结构

不要求逻辑上相邻的元素在物理位置上也相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。

其优点是不会出现碎片现象，能充分利用所有存储单元；缺点是每个元素因存储指针而占用额外的存储空间，且只能实现顺序存取。

索引结构

在存储元素信息的同时，还建立附加的索引表。索引表中的每项称为索引项，索引项的一般形式是（关键字，地址）。

其优点是检索速度快；缺点是附加的索引表额外占用存储空间。另外，增删数据时也要修改索引表，因此会花费较多的时间。

散列结构

根据元素的关键字直接计算出该元素的存储地址，又称哈希（Hash）存储。

其优点是检索、增加和删除结点的操作都很快；缺点是若散列函数不好，则可能出现元素存储的单元的冲突，而解决冲突会增加时间和空间的开销。

数据的运算

施加在数据上的运算包括运算的定义和实现。

运算的定义是针对逻辑结构的，指出运算的功能；

运算的实现是针对物理结构的，指出运算的具体操作步骤。

数据类型以及抽象数据类型的定义。

数据类型

数据类型是一个值的集合和定义在此集合上的一组操作的总称。

原子类型：其值不可再分的数据类型。
结构类型：其值可以再分解为若干成分（分量）的数据类型。
抽象数据类型。

抽象数据类型

一个数学模型及定义在该数学模型上的一组操作。

它通常是对数据的某种抽象，定义了数据的取值范围及其结构形式，以及对数据操作的集合。

考试要求

掌握数据、数据元素、数据项之间的关系；

数据元素是数据的基本单位，一个数据元素由若干个数据项组成。

假设由两张表，格式如下：

姓名	性别	身高	课程号
小西	女	170	A
小交	男	181	A
小大	男	178	B

课程号	课程名
A	数据结构
B	程序设计

这两张表就是数据，单独的一张表称为数据对象，每张表中的每一行称为数据元素，而姓名、性别、身高、课程号和课程名称为数据项。

掌握数据结构的定义；

见上文。

掌握数据结构的三要素；

数据结构的三要素包括数据逻辑结构、数据存储结构和数据的运算。

掌握数据类型、抽象数据类型和数据结构之间的关系。

数据类型是程序设计中的一个基本概念，它用来描述数据在内存中的表示形式以及可以进行的操作。数据类型是数据的一种属性，它限定了数据的变化范围和行为。

数据结构则是关于数据元素之间关系的描述，它研究如何有效地组织和管理数据。数据结构不仅包括数据间的逻辑结构（即数据元素之间的关系），还涉及数据的存储关系（即数据在计算机中的存储结构），以及数据运算（即定义在逻辑关系上的一组操作）。数据结构的主要目的是将数据元素组织成特定的结构，以便于高效地执行各种操作。

抽象数据类型（ADT）则是一种数学模型以及定义在该模型上的一组操作的集合。它描述了一组具有共同特性和行为的数据对象，以及这些对象上可以执行的操作。抽象数据类型强调的是数据的逻辑特性，而不关心数据在计算机内部的具体表示和实现方式。这使得抽象数据类型具有更高的灵活性和可移植性，可以在不同的系统和平台上使用。

三者之间的关系可以概括为：数据类型是基础，它定义了数据的属性和操作；数据结构是对数据类型的组织和管理的描述，它关心如何有效地存储和访问数据；而抽象数据类型则是对数据结构的进一步抽象，它隐藏了数据结构的实现细节，只暴露必要的操作接口，使得程序员可以在更高层次上理解和使用数据结构。

数据类型和抽象数据类型的相同点是他们都关心逻辑结构。

不同点是数据类型既关心逻辑结构又关心物理结构，也就是关注数据结构如何实现，而抽象数据类型只关心抽象特征。

算法和算法分析

考试内容

算法的定义

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

算法的特性

有穷性、确定性、可行性、输入和输出。

算法的时间复杂度的定义及计算

定义

一个语句的频度是指该语句在算法中被重复执行的次数。

算法中所有语句的频度之和记为 $T(n)$ ，它是该算法问题规模 $n$ 的函数，时间复杂度主要分析 $T(n)$ 的数量级。

算法中基本运算（最深层循环中的语句）的频度与 $T(n)$ 同数量级，因此通常将算法中基本运算的执行次数的数量级作为该算法的时间复杂度。

于是，算法的时间复杂度记为 $T(n)=O(f(n))$

式中， $O$ 的含义是 $T(n)$ 的数量级，其严格的数学定义是：若 $T(n)$ 和 $f(n)$ 是定义在正整数集合上的两个函数，则存在正常数 $C$ 和 $n_0$ ，使得当 $n \ge n_0$ 时，都满足 $0 \le T(n) \le Cf(n)$ 。

在分析一个程序的时间复杂性时，有以下两条规则：

加法规则： $O(f(n))+O(g(n))=O(max(f(n),g(n)))$

乘法规则： $O(f(n))×O(g(n))=O(f(n)×g(n))$

常见的渐进时间复杂度为

$O(1) \lt O(log_2 n) \lt O(n) \lt O(nlog_2 n) \lt O(n^2) \lt O(n^3) \lt O(2^n) \lt O(n!) \lt O(n^n)$

计算

一般总是考虑在最坏情况下的时间复杂度，即Big-oh.

第一步：统计操作数量

忽略 $T(n)$ 中的常数项。
省略所有系数。
循环嵌套时使用乘法。

第二步：判断渐进上界

时间复杂度由 $T(n)$ 中最高阶的项来决定，系数无法撼动阶数。

$T(n)$	$O(f(n))$
$1000000$	$O(1)$
$3n+10000$	$O(n)$
$2n^2+3n+2$	$O(n^2)$
$n^3+10000n^2$	$O(n^3)$
$2^n+10000n^{100000}$	$O(2^n)$

算法的空间复杂度的定义及计算

定义

算法的空间复杂度 $S(n)$ 定义为该算法所需的存储空间，它是问题规模 $n$ 的函数，记为 $S(n)=O(G(n))$ 。

一个程序在执行时除需要存储空间来存放本身所用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单位和存储一些为实现计算所需信息的辅助空间。若输入数据所占空间只取决于问题本身，和算法无关，则只需分析除输入和程序之外的额外空间。算法原地工作是指算法所需的辅助空间为常量，即 $O(1)$ 。

常见的渐进空间复杂度为

$O(1) \lt O(log_2 n) \lt O(n) \lt O(n^2) \lt O(2^n)$

计算

空间复杂度的推算方法与时间复杂度大致相同，只需将统计对象从“操作数量”转为“使用空间大小”。

我们通常只关注最差空间复杂度，这是因为内存空间是一项硬性要求，我们必须确保在所有输入数据下都有足够的内存空间预留。

最差空间复杂度中的“最差”有两层含义。

以最差输入数据为准
以算法运行中的峰值内存为准

考试要求

了解算法的定义以及特性；

定义见上文。

特性：

有穷性：一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成。
确定性：算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出。
可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。
输出：一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。

通常，设计一个“好”的算法应考虑达到以下目标：

正确性：算法应能够正确地解决求解问题。
可读性：算法应具有良好地可读性，以帮助人们理解。
健壮性：算法能对输入的非法数据做出反应或处理，而不会产生莫名其妙的输出。
高效率与低存储量需求：效率是指算法执行的时间，存储量需求是指算法执行过程中所需要的最大存储空间，这两者都与问题的规模有关。

了解衡量算法在资源上的两个方面；

算法效率的度量是通过时间复杂度和空间复杂度来描述的。

掌握算法的渐进性分析方法

会用该方法对算法进行评估

算法的渐进性分析方法是一种对算法性能进行事前分析的方法，主要关注当问题输入规模很大或者达到极限时，算法代价的变化。其核心在于讨论算法的复杂度，探讨具体算法对问题的适应性。

渐进分析研究的是随着输入规模的增长，算法所消耗的时间和空间会受到怎样的影响。

渐进分析中的一些记号： $O$ 渐进上界， $Ω$ 渐进下界， $Θ$ 渐进紧确界。

掌握Ο标记法，理解大Ο标记法的意义；

$O$ 表示函数具有渐进上界，对于给定的函数 $g(n)$ ，用 $O(g(n))$ 来表示以下函数的集合：

$O(g(n))=\{ f(n): \exist c \gt 0, n_0 \gt 0,s.t. \forall n \ge n_0,0\le f(n) \le cg(n) \}$

例如 $2n^2 = O(n^3)$ ，这里的 $=$ 并不是传统意义上的等于，而是 $2n^2 \in O(n^3)$ 的意思，即 $\exist c \gt 0, n_0 \gt 0,s.t. \forall n \ge n_0,0\le 2n^2 \le cn^3 \}$

大 $O$ 符号约束了 $T(n)$ 的上界（upper bound），当 $n$ 在趋近无穷大的时候， $T(n)$ 的大小总是小于等于某个函数。

![](G:\lizc\source\picture\Big-oh notation.png)

掌握Ω标记法，理解大Ω标记法的意义；

$Ω$ 表示函数具有渐进下界，对于给定的函数 $g(n)$ ，用 $Ω(g(n))$ 来表示以下函数的集合：

$O(g(n))=\{ f(n): \exist c \gt 0, n_0 \gt 0,s.t. \forall n \ge n_0,0\le cg(n) \le f(n) \}$

大 $Ω$ 符号约束了 $T(n)$ 的下界（lower bound），当 $n$ 在趋近无穷大的时候， $T(n)$ 的大小总是大于等于某个函数。

![](G:\lizc\source\picture\Big-omega notation.png)

掌握Θ标记法，理解大Θ标记法的意义；

$Θ$ 表示函数具有渐进紧确界，对于给定的函数 $g(n)$ ，用 $Θ(g(n))$ 来表示以下函数的集合：

$O(g(n))=\{ f(n): \exist c_1 \gt 0,c_2 \gt 0, n_0 \gt 0,s.t. \forall n \ge n_0,0\le c_1 g(n) \le f(n) \le c_2 g(n) \}$

大 $Θ$ 符号约束了 $T(n)$ 的确界（tight），当 $n$ 在趋近无穷大的时候跟它时间复杂度一样的一个函数。

![](G:\lizc\source\picture\Big-theta notation.png)

了解时空权衡原则。

通过降低或提高算法的空间效率来提高或降低时间效率以解决问题的方法。

线性表

考试内容

线性表的定义；

线性表是具有相同数据类型的 $n(n \ge 0)$ 个数据元素的有限序列，其中 $n$ 为表长，当 $n=0$ 时，线性表是一个空表。

线性表的特点如下：

表中元素的个数有限。
表中元素具有逻辑上的顺序性，表中元素有其先后次序。
表中元素都是数据元素，每个元素都是单个元素。
表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间。
表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。

顺序表的定义及其特点；

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

因此，顺序表的特点是表中元素的逻辑顺序与其存储的物理顺序相同。

顺序表的优点：

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

顺序表的缺点：

元素的插入和删除需要移动大量的元素，插入操作平均需要移动 $n/2$ 个元素，删除操作平均需要移动 $(n-1)/2$ 个元素；
顺序存储分配需要一段连续的存储空间，不够灵活。

链式表的定义及其特点；

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

单链表结点结构如下所示，其中data为数据域，存放数据元素；next为指针域，存放其后继结点的地址。

data	next

单链表中结点类型的描述如下：

typedef struct LNode {	//定义单链表结点类型
    ElemType data;	//数据域
    struct LNode *next;	//指针域
}LNode, *LinkList;

利用单链表可以解决顺序表需要大量连续存储单元的缺点，但附加的指针域，也存在浪费存储空间的缺点。由于单链表的元素离散地分布在存储空间中，因此是非随机存取的存储结构，即不能直接找到表中某个特定结点。查找特定结点时，需要从表头开始遍历，依次查找。

通常用头指针L（或head等）来标识一个单链表，指出链表的起始地址，头指针为NULL时表示一个空表。此外，为了操作上的方便，在单链表第一个数据结点之前附加一个结点，称为头结点。头结点的数据域可以不设任何信息，但也可以记录表长等信息。单链表带头结点时，头指针L指向头结点。单链表不带头结点时，头指针L指向第一个数据结点。表尾结点的指针域为NULL（用“^”表示）。

头结点和头指针的关系：不管带不带头结点，头指针都始终指向链表的第一个结点，而头结点是带头结点的链表中的第一个结点，结点内通常不存储信息。

引入头结点后，可以带来两个优点：

由于第一个数据结点的位置被存放在头结点的指针域中，因此在链表的第一个位置上的操作和在表的其他位置上的操作一致，无须进行特殊处理。
无论链表是否为空，其头指针都是指向头结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就得到了统一。

线性表的应用。

考试要求

掌握线性表的逻辑结构，以及基本操作；

逻辑结构

若用 $L$ 命名线性表，则其一般表示为

$L=(a_1,a_2,...,a_i,a_{i+1},...,a_n)$

式中， $a_1$ 是唯一的“第一个”数据元素，又称表头元素； $a_n$ 是唯一的“最后一个”数据元素，又称表尾元素。除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后继（“直接前驱”和“前驱”、“直接后继”和“后继”通常被视为同义词）。

以上就是线性表的逻辑特性，这种线性有序的逻辑结构正是线性表名字的由来。

基本操作

一个数据结构的基本操作是指其最核心、最基本的操作。其他较复杂的操作可通过调用其基本操作来实现。

线性表的基本操作如下：

InitList(&L)：初始化表。构造一个空的线性表。
Length(L)：求表长。返回线性表L的长度，即L中数据元素的个数。
LocateElem(L, e)：按值查找操作。在表L中查找具有给定关键字值的元素。
GetElem(L, i)：按位查找操作。获取表L中第i个位置的元素的值。
ListInsert(&L, i, e)：插入操作。在表L中的第i个位置上插入指定元素e。
ListDelete(&L, i, &e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。
PrintList(L)：输出操作。按前后顺序输出线性表L的所有元素值。
Empty(L)：判空操作。若L为空表，则返回true，否则返回false。
DestroyList(&L)：销毁操作。销毁线性表，并释放线性表L所占用的内存空间。

掌握用顺序存储结构对线性表基本操作的实现；

顺序表的初始化

静态分配和动态分配的顺序表的初始化操作是不同的。静态分配在声明一个顺序表时，就已为其分配了数组空间，因此初始化时只需将顺序表的当前长度设为0。

//SqList L;	//声明一个顺序表
void InitList(SqList &L) {
    L.length = 0;	//顺序表初始长度为0
}

动态分配的初始化为顺序表分配一个预定义大小的数组空间，并将顺序表的当前长度设为0。MaxSize指示顺序表当前分配的存储空间大小，一旦因插入元素而导致空间不足，就进行再分配。

void InitList(SeqList &L) {
	L.data = (ElemType *)malloc(MaxSize*sizeof(ElemType));	//分配存储空间
    L.length = 0;	//顺序表初始长度为0
    L.MaxSize = InitSize;	//初始存储容量
}

插入操作

在顺序表L的第 $i(1 \le i \le L.length+1)$ 个位置插入新元素e。若 $i$ 的输入不合法，则返回false，表示插入失败；否则，将第 $i$ 个元素及其后的所有元素依次往后移动一个位置，腾出一个空位置插入新元素e，顺序表长度增加1，插入成功，返回true。

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;
}

最好情况：在表尾插入（即 $i=n+1$ ），元素后移语句将不执行，时间复杂度为 $O(1)$ 。

最坏情况：在表头插入（即 $i=1$ ），元素后移语句将执行 $n$ 次，时间复杂度为 $O(n)$ 。

平均情况：假设 $p_i(p_i = 1/(n+1))$ 是在第 $i$ 个位置上插入一个结点的概率，则在长度为 $n$ 的线性表中插入一个结点时，所需移动结点的平均次数为

\sum\limits_{i=1}^{n+1} p_i(n-i+1)=\sum\limits_{i=1}^{n+1} \frac{1}{n+1}(n-i+1)=\frac{1}{n+1}\sum\limits_{i=1}^{n+1}(n-i+1)=\frac{1}{n+1}\frac{n(n+1)}{2}=\frac n 2

因此，顺序表插入算法的平均时间复杂度为 $O(n)$ 。

删除操作

删除顺序表L中第 $i(1 \le i \le L.length)$ 个位置的元素，用引用变量e返回。若 $i$ 的输入不合法，则返回false；否则，将被删除元素赋给引用变量e，并将第 $i+1$ 个元素及其后的所有元素依次往前移动一个位置，返回true。

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

最好情况：删除表尾元素（即 $i=n$ ），无须移动元素，时间复杂度为 $O(1)$ 。

最坏情况：删除表头元素（即 $i=1$ ），需移动除表头元素外的所有元素，时间复杂度为 $O(n)$ 。

平均情况：假设 $p_i(p_i=1/n)$ 是删除第 $i$ 个位置上结点的概率，则在长度为 $n$ 的线性表中删一个结点时，所需移动结点的平均次数为

\sum\limits_{i=1}^{n} p_i(n-i)=\sum\limits_{i=1}^{n} \frac{1}{n}(n-i)=\frac{1}{n}\sum\limits_{i=1}^{n}(n-i)=\frac{1}{n}\frac{n(n-1)}{2}=\frac {n-1} 2

因此，顺序表删除算法的平均时间复杂度为 $O(n)$ 。

按值查找（顺序查找）

在顺序表L中查找第一个元素值等于e的元素，并返回其位序。

int LocateElem(SqList L,ElemType e) {
    int i;
    for (i = 0;i < L.length;i ++)
        if (L.data[i] == e)
            return i + 1;	//下标为i的元素值等于e，返回其位序i+1
	return 0;	//退出循环，说明查找失败
}

最好情况：查找的元素就在表头，仅需比较一次，时间复杂度为 $O(1)$ 。

最坏情况：查找的元素在表尾（或不存在）时，需要比较 $n$ 次，时间按复杂度为 $O(n)$ 。

平均情况：假设 $P_i(p_i=1/n)$ 是查找的元素在第 $i(1 \le i \le L.length)$ 个位置上的概率，则在长度为 $n$ 的线性表中查找值为e的元素所需比较的平均次数为

\sum\limits_{i=1}^{n} p_i i=\sum\limits_{i=1}^{n} \frac{1}{n}i=\frac{1}{n}\frac{n(n+1)}{2}=\frac {n+1} 2

因此，顺序表按值查找算法的平均时间复杂度为 $O(n)$ 。

掌握链式存储结构对线性表基本操作的实现；

单链表的初始化

带头结点和不带头结点的单链表的初始化操作是不同的。带头结点的单链表初始化时，需要创建一个头结点，并让头指针指向头结点，头结点的next域初始化为NULL。

bool InitList(LinkList &L) {	//带头结点的单链表的初始化
	L = (LNode*)malloc(sizeof(LNode));	//创建头结点
    L->next = NULL;	//头结点之后暂时还没有元素结点
    return ture;
}

不带头结点的单链表初始化时，只需将头结点L初始化为NULL。

bool InitList(LinkList &L) {	//不带头结点的单链表的初始化
	L = NULL;
	return true;
}

求表长操作

求表长操作是计算单链表中数据结点的个数，需要从第一个结点开始依次访问表中每个结点，为此需设置一个计数变量，每访问一个结点，其值加1，直到访问到空结点为止。

int Length(LinkList L) {
	int len = 0	//计数变量，初始为0
    LNode *p = L;
    while (p->next != NULL) {
        p = p->next;
        len ++;	//每访问一个结点，计数加1
    }
    return len;
}

求表长操作的时间复杂度为 $O(n)$ 。另需注意的是，因为单链表的长度是不包括头结点的，因此不带头结点的单链表在求表长操作上会略有不同。

按序号查找结点

从单链表的第一个结点开始，沿着next域从前往后依次搜索，直到找到第i个结点为止，则返回该结点的指针；若i小于单链表的表长，则返回NULL。

LNode *GetElem(LinkList L, int i) {
    LNode *p = L;	//指针p指向当前扫描到的结点
    int j = 0;	//记录当前结点的位序，头结点是第0个结点
    while (p != NULL && j < i) {	//循环找到第i个结点
        p = p->next;
        j ++;
    }
    return p;	//返回第i个结点的指针域NULL
}

按序号查找操作的时间复杂度为 $O(n)$ 。

按值查找表结点

从单链表的第一个结点开始，从前往后依次比较表中各节点的数据域，若某结点的data域等于给定值e，则返回该结点的指针；若整个单链表中没有这样的结点，则返回NULL。

LNode *LocateElem(LinkList L, ElemType e) {
	LNode *p = L->next;
    While (p != NULL && p->date != e)	//从第一个结点开始查e
        p = p->next;
    return p;	//找到后返回该结点指针，否则返回NULL
}

按值查找操作的时间复杂度为 $O(n)$ 。

插入结点操作

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

首先查找第i-1个结点，假设第i-1个结点为*p，然后令新结点*s的指针域指向*p的后继，再令结点*p的指针域指向新插入的结点*s。

bool ListInsert(LinkList &L,int i,ElemType e) {
    LNode *p = L;	//指针p指向当前扫描到的结点
    int j = 0;	//记录当前结点的位序，头结点是第0个结点
    while (p != NULL && j < i - 1) {
        p = p->next;
        j ++;
    }
    if (p == NULL)	//i值不合法
        return false;
    LNode *s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;	
    p->next = s;
    return true;
}

本算法主要的时间开销在于查找第i-1个元素，时间复杂度为 $O(n)$ 。若再指定结点后插入新结点，则时间复杂度仅为 $O(1)$ 。

删除结点操作

删除结点操作是将单链表的第i个结点删除。先检查删除位置的合法性，然后查找表中第i-1个结点，即被删结点的前驱，再删除第i个结点。

假设结点*p为找到的被删结点的前驱，为实现这一操作后的逻辑关系的变化，仅需修改*p的指针域，将*p的指针域next指向*q的下一结点，然后释放*q的存储空间。

bool ListDelete(LinkList &L,int i,ElemType &e) {
    LNode *p = L;	//指针p指向当前扫描到的结点
    int j = 0;	//记录当前结点的位序，头结点是第0个结点
    while(p != NULL && j < i - 1){	//循环找到第i-1个结点
        p = p->next;
        j ++;
    }
    if (p == NULL || p->next == NULL)	//i值不合法
        return false;
    LNode *q = p->next;	//令q指向被删除结点
    e = q->data;	//用e返回元素的值
    p->next = q->next;	//将*q结点从链中“断开”
    free(q);	//释放结点的存储空间
    return true;
}

同插入算法一样，该算法的主要时间也耗费在查找操作上，时间复杂度为 $O(n)$ 。当链表不带头结点时，需要判断被删结点是否为首结点，若是，则要做特殊处理，将头指针L指向新的首结点。当链表带头结点时，删除首结点和删除其他结点的操作是相同的。

采用头插法建立单链表

该方法从一个空表开始，生成新结点，并将读取到的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头，即头结点之后。

LinkList List_HeadInsert(LinkList &L) {	//逆向建立单链表
    LNode *s; int x;	//设元素类型为整型
    L = (LNode*)malloc(sizeof(LNode));	//创建头结点
    L->next = NULL;	//初始为空链表
    scanf("%d", &x);	//输入结点的值
    while(x != 9999) {	//输入9999表示结束
        s = (LNode*)malloc(sizeof(LNode));	//创建新结点
        s->data = x;
        s->next = L->next;
        L->next = s;	//将新结点插入表中，L为头指针
        scanf("%d", &x);
    }
    return L;
}

采用头插法建立单链表时，读入数据和顺序与生成的链表中元素的顺序是相反的，可用来实现链表的逆置。每个结点插入的时间为 $O(1)$ ，设单链表长为 $n$ ,则总时间复杂度为 $O(n)$ 。

采用尾插法表示建立单链表

头插法建立单链表的算法虽然简单，但生成的链表中结点的次序和输入数据的顺序不一致。若希望两者次序一致，则可采用尾插法。该方法将新结点插入到当前链表的表尾，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。

LinkList List_TailInsert(LinkList &L) {	//正向建立单链表
	int x;	//设元素类型为整型
    L = (LNode*)malloc(sizeof(LNode));	//创建头结点
    LNode *s, *r = L;	//r为表尾指针
    scanf("%d", &x);	//输入结点的值
    while(x != 9999) {	//输入9999表示结束
        s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;	//r指向新的表尾结点
        scanf("%d", &x);
    }
    r->next = NULL;	//尾结点指针置空
    return L;
}

掌握链式存储结构的实现技术

比如单向链表、双向链表、单循环链表、双向循环链表以及带头节点的链表；

具有在实际中选取不同存储结构的判断能力。

基于存储的考虑

难以估计线性表的长度或存储规模时，不宜采用顺序表；链表不用事先估计存储规模，但链表的存储密度较低，显然链式存储结构的存储密度是小于1的。

基于运算的考虑

在顺序表中按序号访问 $a_i$ 的时间复杂度为 $O(1)$ ，而链表中按序号访问的时间复杂度为 $O(n)$ ，因此若经常做的运算是按序号访问数据元素，则显然顺序表优于链表。

在顺序表中进行插入、删除操作时，平均移动表中一半的元素，当数据元素的信息量较大且表较长时，这一点是不应忽视的；在链表中进行插入、删除操作时，虽然也要找插入位置，但操作主要是比较操作，从这个角度考虑显然后者优于前者。

基于环境的考虑

顺序表容易实现，任何高级语言中都有数组类型；链表的操作是基于指针的，相对来讲，前者实现较为简单，这也是用户考虑的一个因素。

总之，两种存储结构各有长短，选择哪一种由实际问题的主要因素决定。通常较稳定的线性表选择顺序存储，而频繁进行插入、删除操作的线性表（即动态性较强）宜选择链式存储。

栈和队列

考试内容

栈和队列的定义；

栈（Stack）是只允许在一端进行插入或删除操作的线性表。后进先出。

队列（Queue）简称队，也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。先进先出。

顺序栈和链式栈的定义及其特点；

顺序栈：采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针（top）指示当前栈顶元素的位置。通常采用数组实现，顺序栈的入栈操作受数组上界的约束。

链式栈：采用链式存储的栈称为链式栈，链式栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。通常采用单链表实现，并规定所有操作都是在单链表的表头进行的。

顺序队列和链式队列的定义及其特点；

顺序队列：队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针：队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置。

链式队列：队列的链式表示称为链式队列，它实际上是一个同时有队头指针和队尾指针的单链表。头指针指向队头结点，尾指针指向队尾结点，即单链表的最后一个结点。

栈和队列的应用。

考试要求

掌握栈、队列的逻辑结构，以及基本操作；

栈的逻辑结构

栈顶（Top）。线性表允许进行插入删除的那一端。

栈底（Bottom）。固定的，不允许进行插入和删除的另一端。

空栈。不含任何元素的空表。

栈的数学性质：当 $n$ 个不同的元素进栈时，出栈元素不同排列的个数为 $\frac{1}{n+1}\C^n_{2n}$ 。这个公式称为卡特兰数公式。

栈的基本操作

InitStack(&S)：初始化一个空栈S。

StackEmpty(S)：判断一个栈是否为空，若栈S为空则返回true，否则返回false。

Push(&S, x)：进栈，若栈S未满，则将x加入使之称为新栈顶。

Pop(&S, x)：出栈，若栈S非空，则弹出栈顶元素，并用x返回。

GetTop(S, &x)：读栈顶元素，但不出栈，若栈S非空，则用x返回栈顶元素。

DestroyStack(&S)：销毁栈，并释放栈S占用的存储空间。

队列的逻辑结构

队头（Front）。允许删除的一端，又称队首。

队尾（Rear）。允许插入的一端。

空队列。不含任何元素的空表。

队列的基本操作

InitQueue(&Q)：初始化队列，构造一个空队列Q。

QueueEmpty(Q)：判队列空，若队列Q为空返回true，否则返回false。

EnQueue(&Q, x)：入队，若队列Q未满，将x加入，使之成为新的队尾。

DeQueue(&Q, &x)：出队，若队列Q非空，删除队头元素，并用x返回。

GetHead(Q, &x)：读队头元素，若队列Q非空，则将队头元素赋值给x。

掌握顺序存储结构对栈和队列基本操作的实现；

栈，王道p66；队列，王道p78

掌握链式存储结构对栈和队列基本操作的实现；

栈，王道p68；队列，王道p81

掌握顺序存储结构中实现循环队列的具体要求；

理解递归调用和栈之间的关系；

递归算法的设计就是利用了栈的“后进先出”的思想。递归程序设计是栈的一种典型应用。

掌握栈和队列的经典应用。

栈在括号匹配中的应用

很好理解，不做赘述。

二叉树、树和森林

考试内容

二叉树、树和森林的定义；

树

树是 $n(n\ge 0)$ 个结点的有限集。当 $n=0$ 时，称为空树。

在任意一棵非空树中应满足：

有且仅有一个特定的称为根的结点。
当 $n\gt 1$ 时，其余结点可分为 $m(m\gt0)$ 个互不相交的有限集 $T_1,T_2,...,T_m$ ，其中每个集合本身又是一棵树，并且称为根的子树。

树的定义是递归的，即在树的定义中又用到了其自身，树是一种递归的数据结构。

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

树的根结点没有前驱，除根节点外的所有结点有且仅有一个前驱。
树中所有结点都可以有零个或多个后继。

在 $n$ 个结点的树中有 $n-1$ 条边。

二叉树

二叉树是一种特殊的树形结构，其特点是每个结点至多只有两棵子书（即二叉树中不存在度大于2的结点），并且二叉树的子树有左右之分，其次序不能任意颠倒。

与树类似，二叉树也以递归的形式定义。二叉树是 $n(n\ge0)$ 个结点的有限集合：

或者为空二叉树，即 $n=0$
或者由一棵根结点和两个互不相交的称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。

二叉树是有序树，若将其左、右子树颠倒，则成为另一棵不同的二叉树。即使树中结点只有一棵子树，也要区分它是左子树还是右子树。

森林

森林是 $m(m\ge0)$ 棵互不相交的树的集合。

把树的根结点删去就成了森林，反之，只要给 $m$ 棵独立的树加上一个结点，并把这 $m$ 棵树作为该结点的子树，则森林就成了树。

二叉树的实现

（包括顺序存储结构和链式存储结构）

二叉树的遍历；

二叉树结构下的应用及扩展

例如二叉检索树、2-3-4树、B树、B+树、Huffman编码以及堆；

平衡二叉树的定义、平衡因子的定义以及平衡二叉树的旋转操作；

树和森林的存储结构

树和森林的遍历

森林与二叉树的转换；

森林结构的应用

例如并查集。

考试要求

掌握二叉树、树和森林的定义以及它们之间的异同点；

掌握二叉树的四种遍历，并具有能够依赖遍历完成对二叉树进行操作的能力；

理解二叉树采用顺序存储结构和链式存储结构的差异性；

掌握利用二叉树及其扩展下的检索技术；

掌握Huffman编码、堆的实现及应用；

理解平衡二叉树的意义；

掌握平衡二叉树的旋转操作；

掌握树、森林能够采用的各种存储方式的差异性；

掌握树和森林与二叉树的转换；

掌握树、森林在遍历方面和二叉树的不同以及相关性；

理解并查集的意义，以及掌握并查集的基本操作的实现。

图

考试内容

图的定义；

图的实现和基本操作；

（包括邻接矩阵和邻接表）

图的两种遍历；

图的基本应用

包括最小支撑树、最短路径、拓扑排序和关键路径。

考试要求

掌握图的定义

包括完全图、连通图、简单路径、有向图、无向图、无环图等，明确理解图和二叉树、树和森林这种结构之间的异同点；

掌握图采用邻接矩阵和邻接表进行存储的差异性；

掌握广度优先遍历

掌握深度优先遍历；

掌握最小生成树（Prim算法、Kruskal算法）

最短路径（Dijkstra算法、BellmanFord算法、Floyd算法）

拓扑排序以及关键路径的实现过程。

查找

考试内容

查找的定义；

在数据集合中寻找满足某种条件的数据元素的过程称为查找。

查找的结果一般分为两种：1、查找成功 2、查找失败

查找的如下算法：顺序查找法、折半查找法、散列（Hash）技术。

考试要求

理解查找的定义；

掌握对查找算法进行衡量的一些指标

平均查找长度、成功查找的查找长度、不成功查找的查找长度；

掌握顺序查找法和折半查找法，并理解二者之间的异同点；

掌握散列技术

包括散列函数、散列表、散列冲突的发生及其解决方法、以及负载因子；

理解不同查找技术的优缺点。

排序

考试内容

排序的定义，包括内排序和外排序；

排序：重现排列表中的元素，使之有序。
内排序：排序期间元素全部存放在内存中。
外排序：排序期间元素无法全部同时存放在内存中，必须在排序的过程中根据要求不断地在内、外存之间移动。

排序的稳定性定义；

相同元素在经过排序后的相对位置不变，则是稳定的。

直接插入排序

空间复杂度： $O(1)$

时间复杂度：最好情况 $O(n)$ 、最坏情况 $O(n^2)$

平均时间复杂度： $O(n^2)$

稳定。

适用于顺序存储和链式存储的线性表

Shell排序

希尔排序通过对直接插入排序进行改进而得来的，又称缩小增量排序。

空间复杂度： $O(1)$

时间复杂度：最好情况 $O(n)$ 、最坏情况 $O(n^2)$

时间复杂度： $O(n^{1.3})$

不稳定。

仅适用于顺序存储的线性表

冒泡排序

每轮都从前往后依次比较相邻的两个，逆序则交换。

空间复杂度： $O(1)$

时间复杂度：最好情况 $O(n)$ 、最坏情况 $O(n^2)$

平均时间复杂度： $O(n^2)$

稳定。

适用于顺序存储和链式存储的线性表

快速排序

任取一元素作为枢轴，划分成两部分，左≤枢轴，右≥枢轴，然后递归处理左右，直到空或只剩一个。

时间复杂度
最好： $O(n\log_2n)$
最坏： $O(n^2)$
平均： $O(n\log_2n)$

辅助空间复杂度
最好： $O(\log_2n)$
最坏： $O(n)$
平均： $O(\log_2n)$

不稳定。

仅适用于顺序存储的线性表。

简单选择排序

每次遍历无序序列，找到min/max，加入有序序列

比较次数： $n(n-1)/2$

时间复杂度： $O(n^2)$

辅助空间复杂度： $O(1)$

不稳定。

适用于顺序存储和链式存储的线性表，以及关键字较少的情况。

堆排序

时间复杂度： $O(n\log_2n)$

辅助空间复杂度： $O(1)$

不稳定。

仅适用于顺序存储的线性表。

归并排序

将前后相邻的两个有序表合并成一个有序表

归并次数： $\lceil \log_2n\rceil$

时间复杂度： $O(n\log_2n)$

辅助空间复杂度： $O(n)$

稳定。

适用于顺序存储和链式存储的线性表。

基数排序

按多关键字排序

时间复杂度： $O(d(n+r))$

辅助空间复杂度： $O(r)$

稳定。

适用于顺序存储和链式存储的线性表。

K路归并排序

一般而言，对于N个元素进行k路归并排序时，排序的趟数 $m$ 满足 $k^m=N$ ,从而 $m=\lceil \log_kN\rceil$ .

考试要求

理解内排序和外排序的区别；

外部排序指的是大文件的排序，因为文件中的记录很多，无法将整个文件复制进内存中进行排序。在排序的过程中需要多次进行内外存之间的交换。

掌握排序的稳定性；

掌握排序的特点

对直接插入排序、冒泡排序、简单选择排序、Shell排序、快速排序、堆排序、归并排序、基数排序这些算法，掌握其在时间复杂度、空间复杂度以及是否稳定等方面的特点；

算法	最好	平均	最坏	空间	稳定
直接插入	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	true
冒泡	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	true
简单选择	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	false
希尔				$O(1)$	false
快速	$O(n\log_2n)$	$O(n\log_2n)$	$O(n^2)$	$O(\log_2n)$	false
堆	$O(n\log_2n)$	$O(n\log_2n)$	$O(n\log_2n)$	$O(1)$	false
二路归并	$O(n\log_2n)$	$O(n\log_2n)$	$O(n\log_2n)$	$O(n)$	true
基数	$O(d(n+r)$ )	$O(d(n+r)$ )	$O(d(n+r)$ )	$O(r)$	true

了解K路归并的外排序算法；

具有在不同的应用需求下，能够根据各种排序算法特点选择合适排序算法的能力。

矩阵和串

考试内容

矩阵和串的定义；

数组（矩阵）的定义

数组是由 $n(n\ge1)$ 个相同类型的数据元素构成的有限序列，每个数据元素称为一个数组元素，每个元素在 $n$ 个线性关系中的序号称为该元素的下标，下标的取值范围称为数组的维界。

数组是线性表的推广。一维数组可视为一个线性表；二维数组可视为其元素是定长数组的线性表，以此类推。

串的定义

串（string）是由零个或多个字符组成的有限序列。

一般记为：

S='a_1a_2...a_n'(n\ge0)

其中， $S$ 是串名，单引号括起来的字符序列是串的值，字符的个数 $n$ 称为串的长度。 $n=0$ 时的串称为空串（用 $\empty$ 表示）。

串中任意多个连续的字符组成的子序列称为该串的子串，包含子串的串称为主串。

特殊矩阵的压缩存储、稀疏矩阵的三元组表示法；

串的模式匹配。

考试要求

掌握特殊矩阵的压缩存储方法；

掌握稀疏矩阵的三元组表示法以及相应的操作；

掌握多维数组和一维数组的映射；

掌握模式匹配的两个算法：Brute-Force和KMP。

数据结构与算法915notes

2024/06/25/数据结构915笔记/

作者

LZC

发布于

2024-06-25 18:57

许可

数据结构与算法915笔记

数据结构与算法915笔记