:::info{title="本章重点"}
矩阵的压缩存储、广义表的操作。
:::



# 第五章 数组和广义表
## 5.1 数组的定义和表示方法
1. **数组**：是由n(n>=1)个相同类型的数据元素构成的有限序列；
 **数组下标**：每个元素的符号，数组下标从0开始；
2. **存储结构**：一个数组的所有元素在内存中占用一段连续的存储空间；
 **多维数组存储**：行优先和列优先；
 

:::tip{title="例"}
二维数组：<img src="https://data.handyzyg.cn/img/d0b903fdb5856c41416da5ca2727c67d.4_1.png" width=200px alt="4_1.png" />

- 按行优先

| a00 | a01 | a02 | a10 | a11 | a12 |
| --- | --- | --- | --- | --- | --- |

- 按列优先

| a00 | a10 | a01 | a11 | a02 | a12 |
| --- | --- | --- | --- | --- | --- |
:::

## 5.2 压缩矩阵
为矩阵中多个值相同的元素只分配一个空间，不为0元素分配空间。节省存储空间；
1. **对称矩阵**：$ {a}_{ij} $ = $ {a}_{ji} $，可以将一个n阶方阵分为上三角区、下三角区和主对角线三部分；
 只存储下三角部分（含对角线），存储使用的一维数组大小为`n(n+1)/2`；
2. **上三角矩阵**：下三角区为同一常量，通常为0，存储完下三角区和主对角元素后，将常量存在最后，使用的数组大小`n(n+1)/2+1`；
 元素$ {a}_{ij} $对应的数组下标 <img src="https://data.handyzyg.cn/img/3c083db2ddc640919cd56edc8f51d94e.4_3.png" width=400px alt="4_3.png" />

 在数组内的压缩存储形式：
 

 <table>
 <tr>
 <td>0</td><td>1</td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td><td>2(n+1)/2</td>
 <tr>
 <tr>
 <td>a11</td><td>a12</td><td>...</td><td>a1n</td><td>a22</td><td>a23</td><td>...</td><td>a2n</td><td>...</td><td>C</td>
 <tr>
 <tr>
 <td colspan="4">第1行</td><td colspan="4">第2行</td><td></td><td>常数项</td>
 <tr>
 </table>



3. **下三角矩阵**：上三角区为同一常量，通常为0，存储完下三角区和主对觉元素后，将常量存在最后，使用的数组大小`n(n+1)/2+1`；
 元素$ {a}_{ij} $对应数组下标 <img src="https://data.handyzyg.cn/img/11cf302af48baaa25b84337a4a5202fb.4_4.png" width=400px alt="4_4.png" />
 
 在数组内的压缩存储形式：
 
 <table>
 <tr>
 <td>0</td><td>1</td><td>2</td><td>3</td><td>...</td><td> </td><td> </td><td>...</td><td> </td><td>2(n+1)/2</td>
 <tr>
 <tr>
 <td>a11</td><td>a21</td><td>a22</td><td>a31</td><td>...</td><td>an1</td><td>an2</td><td>...</td><td>ann</td><td>C</td>
 <tr>
 <tr>
 <td colspan="1">第1行</td><td colspan="2">第2行</td><td></td><td></td><td colspan="4">第n行</td><td>常数项</td>
 <tr>
 </table>

4. **稀疏矩阵**：当矩阵中非零元素的个数<<j矩阵元素的个数即可视为稀疏矩阵；
 零元素的分布通常没有规则，因此用非零元素的行、列和值构成一个三列的表格，可以用数组或十字链表法存储。

## 5.3 广义表
1. **广义表**：线性表的推广，一般记作 LS = ($ {a}_{1} $,$ {a}_{2} $,...,$ {a}_{n} $)
 其中，a可以是单个元素称为**LS的原子**，也可以是广义表称为**LS的子表**；
2. **表头(Head)**：LS非空时的第一个元素，可以是一个元素也可以是一个表；
3. **表尾(Tail)**：LS除了表头以外的其余元素，是一个类；

:::tip{title="例"}
1⃣ A = () ———— A 是一个空表，长度为0；
2⃣ B = (e) ———— B 只有一个原子e，长度为1；
3⃣ C = (a, (b, c, d)) ———— C 的长度为2，两个元素分别为原子a和子表(b, c, d)；
4⃣ D = (A, B, C) ———— D 的长度为3，三个元素都是列表，D = ((), (e), (a, (b, c, d)))；
5⃣ E = (a, E) ———— E 是一个递归的表，长度为2，E = (a, (a, (a, ...)))；
 
 
 GetHead(B) = e; GetTail(B) = ();
 GetHead(D) = A; GetTail(D) = (B, C);
 
:::

数据结构-数组和广义表#5

:::info{title="本章重点"}
串的定义与匹配
:::



# 第四章 串
## 4.1 串
#### 1. 定义
- **串（string）**：`s = 'a1a2a3...an'`；
- n为**串的长度**，a可以是**数字字母或其他字符**（包括空格），0个字符成为**空串**；
- **主串**：包含子串的串；
- **子串**：串中任意个连续的字符组成的子序列。
#### 2. 存储类型
- **定长顺序存储表示**：用一组地址连续的存储单元存储串的字符序列。超过规定的最大长度时，串序列会被截断；
- **堆分配存储表示**：仍以一组地址连续的存储单元存放串值的字符序列，但存储空间是动态分配的，存在堆区，用`malloc()`申请，`free()`释放；
- **块链存储表示**：用链表存储，每个结点可以放一个或多个字符，每个结点称为块。
## 4.2 模式匹配算法
#### 1. 简单的模式匹配算法
- 逐个比较子串（模式串）和主串的字符，相同比较下一个，不相同则从主串+1处重新比较；
- 每趟匹配失败都是主串后移一位再从子串的头开始比较。
#### 2. 改进的模式匹配算法——KMP算法
- 如果已匹配相等的前缀序列中有某个后缀正好是模式的前缀，那么就可以将模式向后移动到与这些相等字符对其的位置，主串`i`指针无需回溯，并继续从该位置开始进行比较；
- 前缀：除最后一个字符以外，字符串的所有头部子串；
- 后缀：除第一个字符以外，字符串的所有尾部子串；
- 部分匹配值（PM）：前后缀中最长相等的前后缀长度；
- next数组：下一次匹配时的位置。


:::tip{title="提示：KMP算法"}
- 我们可以用一个简单的流程来解释这个算法：
 令主串'**S**'为：`ABC ABCDAB ABCDABCDABDE`；
 令子串'**W**'为：`ABCDABD`；
 令'**m**'为主串字符串位数，令'**i**'为子串字符串位数；
- 第一轮：

 
 ![5_1.png](https://data.handyzyg.cn/img/9c4f2f748a5421dc07b79eda13cc96c3.5_1.png)
 `S[3] != W[3]`且前缀`{A,AB}`与后缀`{C,CB}`不同，故令`m = 4, i = 0`，继续比较；
- 第二轮：
 
 ![5_2.png](https://data.handyzyg.cn/img/59ad0720af98623534b8e205a4b7e287.5_2.png)
 `S[10] != W[6]`但前缀`{A,AB,ABC,ABCD,ABCDA}`与后缀`{B,AB,DAB,CDAB,BCDAB}`有最长相等前后缀长度为**2**，故接下来从`S[8]`开始比较，令`m = 8, i = 0`继续比较；
- 第三轮：

 ![5_3.png](https://data.handyzyg.cn/img/f4be7f6a8f196a9885d460c30e8adc9b.5_3.png)
 `S[10] != W[2]`且前缀`{A}`与后缀`{B}`不同，故令`m = 11, i = 0`，继续比较；
- 第四轮：
 
 ![5_4.png](https://data.handyzyg.cn/img/b8b9e908aed01c51c47bd7c114c665a6.5_4.png)
 `S[17] != W[6]`且前缀`{A,AB,ABC,ABCD,ACBDA}`与后缀`{B,AB,DAB,CDAB,BCDAB}`有最长相等前后缀长度为**2**，故接下来从`S[15]`开始比较，令`m = 15, i = 0`继续比较；
- 第五轮：

 ![5_5.png](https://data.handyzyg.cn/img/30ff271e369da769cf5505b139f01daf.5_5.png)
 `S[21] == W[6]`比较完成，其起始位置在`S[15]`。
:::

:::note{title="例"}
- 设有字符串`S = 'abbaabaabaac', P = 'aabaac';`
 1⃣ 求P的`next`数组。2⃣ 若S作为主串，P作为模式串，试给出KMP的匹配过程。
- 【解】
 1⃣ 步骤一：通过前缀、后缀求出字符串的部分匹配值（PM）
 `'a'`的前缀和后缀都是空集，最长相等前后缀长度0；
 `'aa'`的前缀为`{a}`，后缀为`{a}`，最长相等前后缀长度1；
 `'aab'`的前缀为`{a,aa}`后缀为`{b,ab}`，最长相等前后缀长度0；
 `'aaba'`的前缀为`{a,aa,aab}`后缀为`{a,ba,aba}`，最长相等前后缀长度1；
 `'aabaa'`的前缀为`{a,aa,aab,aaba}`后缀为`{a,aa,baa,abaa}`，最长相等前后缀长度2；
 `'aabaac'`的前缀为`{a,aa,aab,aaba,aabaa}`后缀为`{c,ac,aac,baac,abaac}`，最长相等前后缀长度0；
 故字符串P的部分匹配值为：010120；
 步骤二：根据PM计算next数组：首个为0，填入前一个序号的PM值加一，即`next[i] = PM[i-1]+1`；
 
 | 模式串 | a | a | b | a | a | c |
 | -- | -- | -- | -- | -- | -- | -- |
 | 序号 | 1 | 2 | 3 | 4 | 5 | 6 |
 | PM | 0 | 1 | 0 | 1 | 2 | 0 |
 | next | 0 | 1 | 2 | 1 | 2 | 3 |
 
 2⃣ KMP匹配过程：
 | 主串 | a | a | b | a | a | b | a | a | b | a | a | c |
 | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- |
 | 第一次比较 | a | a | b | a | a | c | 
 | 第二次比较 | | | | a | a | b | a | a | c |
 | 都三次比较 | | | | | | | a | a | b | a | a | c |
 
 - 第一次匹配：从主串和子串的第一个字符开始比较，`i = 6 ,j = 6`时失败；
 - 第二次匹配：`next[6] = 3`，主串当前位置和子串的第三个字符比较，`i = 9, j = 6` 时失败；
 - 第三次匹配：`next[6] = 3`，主串当前位置和子串的第三个字符比较，匹配成功。
:::

数据结构-串#4

:::info{title="本章重点"}
栈和队列的特性和基本操作，出栈顺序，输出队列。
:::



# 第三章 栈和数列

## 3.1 栈
#### 1. 定义
- **栈（`stack`）**：只允许在一端进行插入或删除操作的线性表；
- **栈顶**：线性表允许进行插入删除操作的一端，栈顶指针：`S.top`；
- **栈底**：固定不允许进行插入删除操作的一端；
- **空栈**：为存储任何元素的栈。空栈条件：栈顶指针指向栈底；
- **结构特性**：先进后出（`LIFO`）。
#### 2. 栈的存储结构
1. **顺序栈**：栈的顺序存储结构，运用一组地址连续的存储单元依次存储自栈底到栈顶的数据元素，指针`top`指示栈顶元素在顺序栈中的位置；
 1. **进栈**：若栈不满，栈顶指针+1，赋值栈顶元素；
 2. **出栈**：若栈非空，取出栈顶元素，栈顶指针-1；
2. **链栈**：采用链式存储，优点是便于多个栈共享存储空间和提高效率，避免栈上溢。通常采用单链表实现，在表头进行插入删除操作。

## 3.2 队列
#### 1. 定义
- **队列（`queue`）**：只允许在表的一端进行插入，在另一段删除；
- **队尾（`rear`）**：允许插入的一端；
- **队头（`front`）**：允许删除的一端；
- **结构特性**：先入先出（`FIFO`）。
#### 2. 队的存储结构
1. **顺序结构**：用一组地址连续的存储单元依次存储从队头到队尾的元素，需要队头指针（front）和队尾指针（rear）；
 1. 初始化空队列：`front = rear = 0`；
 2. 插入新元素时队尾指针增一，删除队尾指针是队头指针增一；
 3. 头指针永远指向向头元素、尾指针永远指向向尾元素；
2. **双端队列**：两端都可以输入输出，实际使用中还有输出受限的双端队列，输入受限的双端队列（先指某一端只能输入或限制某一端只能输出）；
3. **链队列**：用链表表示的队列，需要定义队头和队尾指针；
 1. **判空条件**：`front == rear`；
4. **循环队列**：解决顺序队列假溢出，把存储队列从逻辑上视为环状。当队头指针`Q.front = Maxsize - 1`时，再前进一个位置自动到0，通过取余实现；
 1. **初始化**：`Q.front = Q.rear = 0;`
 2. **队头指针进1**:`Q.front = (Q.front + 1) % MaxSize;`
 3. **队尾指针进1**:`Q.rear = (Q.rear + 1) % MaxSize;`
 4. **判空**：
 1. 另设一个标志位区分空还是满；
 2. 少用一个空间元素，以“**队头指针在队尾指针的下一个位置上**”表示满状态
 5. **队满条件**：`(Q.rear + 1) % MaxSize == Q.front;`
 6. **队空条件**：`Q.front == Q.rear;`
 7. **队列中元素的个数**：`(Q,rear - Q.front + MaxSize) % MaxSize;`

数据结构-栈和队列#3

:::info{title="本章重点"}
线性表的定义，顺序表和链表的定义与特点，顺序表和链表的插入删除查找移动等基本操作
:::



# 第二章 线性表

## 2.1 线性表的顺序表示
1. **线性表（list）**：n个具有相同数据类型的数据元素的优先序列。
2. **顺序表**：用一组地址连续的存储单元依次存储线性表中的数据元素。
3. **特点**：
 1. 逻辑相邻的两个元素在物理地址上也相邻；
 2. 随机存取；
 3. 存储密度高；
 4. 插入删除不方便，需要移动大量元素。
4. **操作**：
 1. 插入：在表长为n的顺序表的第i个位置上插入元素，将插入位置开始的元素都向后移动一个位置，移动 `n-i+1` 个元素，平均时间复杂度：`O(n)`。
 2. 删除：在表长为n的顺序表中删除第i个元素，将`ai~an`都向前移动一个位置，共移动`n-i`个元素，平均时间复杂度：`O(n)`。
 3. 查找：
 - 按照序号查找：根据线性表随机存取的特点，时间复杂度为`O(1)`；
 - 按值查找：比较次数与查找值在表中位置、表长有关，平均比较次数`(n+1)/2`，时间复杂度`O(n)`。

## 2.2 线性表的链式存储
#### 一、单向链表
1. **单链表**：通过指针连接各数据元素，不需要使用物理地址连续的存储单元，非随机存取

 ```js
 //线性表的单链表存储结构：
 typedef struct LNode{
 ElemType data;
 struct LNode *next;
 }LNode, *LinkList;
 ```
2. **结点(node)**：结点构成链表，由数据域和指针域（存储后续位置）构成，结构为：

 | 数据域(data) | 指针域(next) |
 | --- | --- |

3. **头指针**：用来标识单链表，指向链表中第一个结点的存储位置。头指针为`NULL`时为空表。
4. **头结点**：为了方便操作，在单链表的第一个结点之前设置一个数据域不存储任何信息、指针域指向第一结点的指针的结点。
 - 头结点与头指针：无论带不带头结点，头指针始终指向链表的第一个结点；
 - 头结点是带头结点的链表的第一个结点，结点内通常不存储信息。
5. **带头结点的优点**：
 - 由于第一个数据结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作和在表中其他位置上的操作一致，无需进行特殊处理。
 - 无论链表是否为空，其头指针都指向头结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就得到了统一。
6. **基本操作**
 1. **头插法建表**：从空表开始将新结点插入当前链表的头结点后。
 读入数据的顺序与生成链表中元素的顺序相反。时间复杂度为`O(n)`
 **核心代码**：
 ```js
 s->next = L->next; //1⃣先用新结点S的指针指向原链表的第一个结点；
 L->next = s; //2⃣再将头结点的指针L指向新结点。
 ```
 2. **尾插法**：将新结点插入当前表尾，使用尾指针r始终指向尾结点。
 读入数据的顺序与生成链表中元素的顺序一致。时间复杂度为`O(n)`
 **核心代码**：
 
 
 ```js
 r->next = s; //1⃣原尾结点指向新的结点；
 r = s; //2⃣插入的结点成为新的尾结点。
 ```
 3. **查找**：按值查找和按序号查找；链表非随机存取，两种查找方式都需要从头结点开始遍历查找。时间复杂度为`O(n)`
 4. **插入**：将数据域为x的新结点S插入第i个位置。时间复杂度为`O(n)`
 **核心代码**：
 ```js
 p = GetElem(L, i-1); //1⃣找到插入的位置；
 s->next = p->next; //2⃣新结点s指向插入位置的下一结点；
 p->next = s; //3⃣结点P指向S
 ```
 5. **删除**：删除链表中的第i个结点。时间复杂度为`O(n)`
 **核心代码**：
 
 ```js
 p = GetElem(L, i-1);
 q = p->next;
 p->next = q->next
 ```
 
 :::note{title="注"}
 插入删除时注意顺序，插入时要让新结点先指向插入位置的后一个结点，删除时要先让前驱结点指向删除位置的后继结点，避免链表断开结点丢失。
 :::
#### 二、循环链表
- 表中最后一个结点的指针域指向头结点，整个链表形成一个环。可以从表的任意位置开始遍历整个链表。
- 判空条件：头结点的指针等于头指针。
#### 三、双向链表
- 克服单链表只能顺指针往后查找其他结点的缺点，双向链表中有两个指针域：一个指向前驱，一个指向后继。
- 双向链表也可以有循环表示。

数据结构-线性表#2

:::info{title="本章重点"}
数据结构相关定义 算法的特性 时间空间复杂度
:::



# 第一章 绪论
## 1.1 关键定义：
#### 1. 数据元素：是数据的基本单位，数据元素可以分为若干个数据项，数据项是数据的不可分割的最小单位。
#### 2. 数据对象：是性质相同的数据元素的集合，是数据的一个子集。
#### 3. 数据结构：是相互之间有一种或多种特定关系的数据元素的集合，数据元素之间的关系叫结构。
#### 4. 数据类型：1⃣️原子类型、 2⃣️结构类型、3⃣️抽象数据类型。
#### 5. 数据结构的三要素：1⃣️数据的逻辑结构，2⃣️数据的存储结构，3⃣️数据的运算。
1. **数据的逻辑结构**：1⃣️集合、2⃣️线性结构、3⃣️树形结构、4⃣️图状结构（网状结构）
2. **数据的存储结构**：1⃣️顺序存储、2⃣️链式存储、3⃣️索引存储、4⃣️散列存储
#### 6. 算法的五个特性：**入穷定出行**，输入、有穷性、确定性、输出、可行性。
#### 7. 算法效率：
1. **时间复杂度**：T(n)：算法中的基本运算（最深层次的循环语句）的执行次数的数量级，可以只考虑高阶的部分。
 **在加法中**：取最高阶数量级。
 **在乘法中**：取乘积的最高阶数量级。
2. **空间复杂度**：S(n)：运算过程中使用辅助空间的大小。

数据结构-绪论#1

这里是handy张鱼哥的小窝～不定期更新有关编程、模拟飞行、管制生涯、心路历程的博客平台