第二章 数据结构与算法基础（占比较高）
2.1 基本概念和三要素
数据结构在学什么?
如何用程序代码把现实世界的问题信息化
如何用计算机高效地处理这些信息从而创造价值,
数据：数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。
数据元素、数据顶：数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
数据结构的三要素：逻辑结构、物理结构（存储结构）、数据的运算
逻辑结构：集合、线性结构、树形结构、图状结构(网状结构)
- 集合：各个元素同属一个集合，别无其他关系
- 线性结构：数据元素之间是一对一的关系。除了第一个元素，所有元素都有唯一前驱；除了最后一个元素，所有元素都有唯一后继
- 树形结构：数据元素之间是一对多的关系
- 图结构：数据元素之间是多对多的关系
物理结构：
- 顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中
- 链式存储：逻辑上相邻的元素在物理位置上可以不相邻
- 索引存储：在存储元素信息的同时，还建立附加的索引表
- 散列存储：根据元素的关键字直接计算出该元素的存储地址，又称哈希(Hash)存储
2.2 算法
程序=数据结构+算法
数据结构表示如何把现实世界的问题信息化，将信息存进金算计，同时还要实现对数据结构的基本操作
算法表示如何处理这些信息以解决实际问题
算法的五个特性：
- 有穷性：一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成。
- 确定性：算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出。
- 可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
- 输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合!
- 输出：一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。
算法效率的度量（衡量算法好坏的指标）：
- 时间复杂度：时间开销与问题规模n之间的关系
- 空间复杂度：空间开销(内存开销)与问题规模n之间的关系
函数递归调用带来的内存开销：空间复杂度 = 递归调用的深度
O(1) < O(log2n) < O(n) < O(nlog2n) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)
2.3 线性表
- 逻辑结构
- 物理结构
- 顺序表：顺序存储
- 链表：链式存储
- 双向链表
- 循环链表
- 静态链表
- 插入删除操作
线性表是具有相同数据类型的n(n≥0)个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。
若用L命名线性表，则其一般表示为
ai是线性表中的“第i个”元素线性表中的位序；a1是表头元素；an是表尾元素。除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外每个元素有且仅有一个直接后继。
线性表存储结构：
| 性能类别 | 具体项目 | 顺序存储 | 链式存储 |
|---|---|---|---|
| 空间性能 | 存储密度 | =1，更优 | <1 |
| 容量分配 | 事先确定 | 动态改变，更优 | |
| 时间性能 | 查找运算 | O(n/2) | O(n/2) |
| 读运算 | O(1)，更优 | O([n+1]/2)，最好情况为O(1)，最坏情况为O(n) | |
| 插入运算 | O(n/2)，最好情况为0，最坏情况为O(n) | O(1)，更优 | |
| 删除运算 | O([n-1]/2) | O(1)，更优 |
插入删除操作：
- 顺序存储：插入元素前要移动元素以挪出空的存储单元，然后再插入元素。删除元素时同样需要移动元素，以填充被删除元素的存储单元。
- 链式存储：(例如删除a2)
- 单链表删除节点：a1的指针指向a3
- 单链表插入节点：S指针指向新元素a4，先用a4的指针指向a2，然后a1的指针指向a4（顺序颠倒后就没有a2后面的数据了）
- 双向链表删除节点：P指针指向a2(要删除的节点)，a1指向a3，然后a3指向a1
- 双向链表插入节点：先引入q指针指向x(要插入的节点)，然后x的next指针指向a2，然后a2节点的前指针指向x，然后再连前面，a1的后指针指向x
2.4 栈和队列
栈(Stack)是只允许在一端进行插入或删除操作的线性表。栈顶是允许插入和删除的一端，栈底是不允许插入和删除的一端，可以进行括号匹配
队列是一种先进先出(FIFO)的线性表，它只允许在表的一端插入元素，而在表的另一端删除元素。允许插入元素的一端称为队尾(Rear)，允许删除元素的一端称为队头(Front)。
循环队列：
队空条件：head = tail
队满条件：(tail+1)%size = head
2.5 串、数组、矩阵和广义表
2.5.1 串
串是仅由字符构成的有限序列，是取值范围受限的线性表。
一般记为S = 'a1 a2 ~~~ an'，其中S是串名，a1 a2 an是串值。
- 空串：长度为零的串，空串不包含任何字符,
- 空格串：由一个或多个空格组成的串。
- 子串：由串中任意长度的连续字符构成的序列。含有子串的串称为主串。子串在主串中的位置指子串首次出现时，该子串的第个字符在主串中的位置。空串是任意串的子串。
- 串相等：指两个串长度相等且对应位置上的字符也相同,
- 串比较：两个串比较大小时以字符的ASCII码值作为依据。比较操作从两个串的第一个字符开始进行，字符的ASCI码值大者所在的串为大;若其中一个串先结束，则以串长较大者为大。
对串进行的基本操作有以下几种：
- 赋值操作
StrAssign(s,)：将串t的值赋给串s - 连接操作
Concat(s,t)：将串t接续在串s的尾部，形成一个新串 - 求串长
StrLength(s)：返回串s的长度 - 串比较
StrCompare(s,t)：比较两个串的大小。 - 求子串
SubString(start,len)：返回串s中从start开始的、长度为len的字符序列。
串的存储结构：
- 串的顺序存储：定长存储结构
- 串的链式存储：块链
子串的定位操作通常称为串的模式匹配，它是各种串处理系统中最重要的运算之一。子串也称为模式串。
