线性结构原创

一、线性结构概述

概念：线性结构是一种数据元素之间存在线性关系的数据结构。即所有数据元素排列成一个线性序列（除了第一个和最后一个元素外，每个元素都有唯一的前驱和后继）。
共同逻辑特征：
- 存在一个的数据元素（）。
- 存在一个的数据元素（）。
- 除外，每个元素都有唯一的。
- 除外，每个元素都有唯一的。
常见类型：。

线性结构的逻辑视图及其主要分类：

二、线性表 (Linear List)

2.1 概念

的线性结构，是具有的 `n` 个数据元素的。

2.2 存储结构

2.2.1 顺序存储（顺序表）

概念：用一组的存储单元线性表中的数据元素。通常用实现。
特点：
- 随机存取：通过（下标）可在 O(1) 时间内找到指定元素。
- 存储密度高：只，无需额外空间。
- 插入删除效率低：平均需要移动 half of the table 的元素，时间复杂度为 O(n)。

需要注意的问题

元素地址计算：假设首地址是 LOC(A)，每个元素占用 L 个存储单元，则第 i 个元素的地址为：

2.2.2 链式存储（链表）

概念：用一组存储数据元素，通过来表示元素之间的逻辑关系。
特点：
- 非随机存取：查找第 i 个元素需要访问，时间复杂度为 O(n)。
- 存储密度较低：需要。
- 插入删除效率高：只需，时间复杂度为 O(1)（已知操作位置时）。
核心考点与计算：
- 链表操作：下午题重点！单链表的插入、删除是高频考点。必须掌握指针修改的顺序，否则会导致链表断裂。 - s->next = p->next; p->next = s; // 将s结点插入到p之后 - q = p->next; p->next = q->next; free(q); // 删除p的后继结点
- 常见链表类型： - 单链表、双链表（可向前后遍历）、循环链表（尾指针指向头结点）。

需要注意的问题

常见的链表类型：、（可向前后遍历）、（尾指针指向头结点）。
头结点: 链表中引入的一个，其 next 指向。作用是操作，统一空表和非空表的处理。

链表操作: 链表的插入、删除操作的流程,。

的插入操作 - (在节点 p 之后插入新节点 s)

核心代码

  s->next = p->next; // 步骤1：新节点s指向p的后继
  p->next = s;       // 步骤2：节点p指向新节点s

图示

的删除操作 - (删除节点 p 的后继节点 q)

核心代码

q = p->next;        // 首先找到要删除的节点q
p->next = q->next;  // 将p的next指针指向q的后继
free(q);            // 最后释放q的内存

图示

的插入操作 - (在节点 p 之后插入新节点 s)

核心代码

 // 1. 处理s的前驱和后继指针
 s->prev = p;
 s->next = p->next;

 // 2. 处理原p的后继节点的前驱指针
 if (p->next != NULL) {
     p->next->prev = s;
 }

 // 3. 处理p的后继指针
 p->next = s;

示意图

的删除操作-(删除节点 p)

核心代码

// 1. 让p的前驱节点绕过p，直接指向p的后继节点
if (p->prev != NULL) {
    p->prev->next = p->next;
}

// 2. 让p的后继节点绕过p，直接指向p的前驱节点
if (p->next != NULL) {
    p->next->prev = p->prev;
}

// 3. 释放节点p
free(p);

示意图

: 循环链表的操作，唯一区别在于，形成一个环。因此，在操作时需要特别，避免出现断裂。
1. 插入操作示意图

循环链表注意事项：
1. 空链表处理：如果链表，新插入的节点其 next (和 prev) 指针。
2. 头尾操作：在插入/删除节点时，需要更新尾节点的 next 指针和头节点的 prev 指针，以确保循环的完整性。
3. 遍历终止条件：遍历循环链表时，判断条件不再是 p != NULL，而是 p != head (从头部开始遍历时)。

2.3 顺序表 vs. 链表对比

特性	顺序表	链表
存储空间	静态分配（通常）	动态分配
存储密度	高（=1）	低（<1）
存取方式	随机存取	顺序存取
插入删除	`O(n)`	`O(1)`（）
查找元素	`O(1)`	`O(n)`
适用场景	表长、	表长、

三、栈 (Stack) & 队列 (Queue)

栈和队列是的线性表，限制了的位置。

3.1 栈 (Stack) - LIFO (Last In First Out / 先进后出)

概念：只允许在（栈顶，Top）进行插入（Push）和删除（Pop）操作的。
考点：
- 栈的数学性质：n 个不同元素入栈，出栈序列的个数为 卡特兰数(Catalan number): 。
- 应用场景：
  1. ：系统调用栈，存储返回地址、实参、局部变量。
  2. ：中缀转后缀（），后缀表达式求值。
  3. ：遇到，遇到。
  4. 。
存储实现：既可以用（数组）实现，也可以用（链表）实现。

3.2 队列 (Queue) - FIFO (First In First Out / 先进先出)

概念：只允许在（队尾，Rear）进行（Enqueue），在（队头，Front）进行（Dequeue）的。
考点：
- ："假溢出"——队列中有空位，但 rear 指针已到数组末尾。
- ：解决假溢出的方法。把数组设想成一个环。
- 核心计算：front 队头指针，rear 队尾指针， QueueSize 队列数组的总长度（即可用的最大存储空间数，包括要牺牲的那个单元）
  - 最大可存元素数: QueueSize - 1
  - ：front == rear
  - ：(rear + 1) % QueueSize == front，这是牺牲一个单元的判断法，最常用，% QueueSize 是为了实现指针的循环（回绕），当 rear 指向数组最后一个位置时，rear + 1 会通过取模运算变成 0。
  - ：rear 和 front 之间有效元素的个数 (rear - front + QueueSize) % QueueSize。
- 应用场景：操作系统中的。
特殊队列：
- ：。
- ：用链表实现的队列，问题。

需要注意的问题

假溢出：假溢出是（用数组实现的队列）在后，出现的一种队列中有，但的现象。
- 示意图
- 解决方法: 使用循环队列

四、串 (String)

概念：由零个或多个组成的有限序列，是一种（数据元素仅为字符）。
特殊定义：
1. 空串：长度为 0 的串，
2. 空格串：长度不为 0 ，
3. 字串：由串种任意长度的连续字符构成的序列。子串在主串中的位置为子串在主串中时，出现在主串中的位置
4. 串相等：指两个，且
5. 串比较：两个串比较大小时，以字符的码值作为依据，比较操作从两个串的，字符的，若串

串操作：

基本操作：串最核心、最基本的操作，是定义串逻辑结构的基础。

操作名称	操作描述（基于教材常用定义）	示例（设 `S = "abc"`, `T = "def"`）
StrAssign(&T, chars)	：生成一个其值等于chars的串T。	`StrAssign(S, "Hello")` => `S = "Hello"`
StrCopy(&T, S)	：由串S复制得串T。	`StrCopy(T, S)` => `T = "abc"`
StrEmpty(S)	：若S为空串，则返回TRUE，否则返回FALSE。	`StrEmpty(S)` => `FALSE`
StrCompare(S, T)	：若S>T，则返回值>0；若S=T，则返回值=0；若S<T，则返回值<0。	`StrCompare("abc", "abd")` => `< 0`
StrLength(S)	求：返回S的元素个数，即串的长度。	`StrLength(S)` => `3`
ClearString(&S)	：将S清为空串。	`ClearString(S)` => `S = ""`
Concat(&T, S1, S2)	：用T返回由S1和S2联接而成的新串。	`Concat(U, S, T)` => `U = "abcdef"`
SubString(&Sub, S, pos, len)	：用Sub返回串S的第pos个字符起长度为len的子串。	`SubString(Sub, "Hello", 2, 3)` => `Sub = "ell"`

串的模式匹配操作:串操作中的部分

操作名称	算法描述	特点与时间复杂度	软考重要性
Index(S, T, pos)	：若主串S中存在与串T值相同的子串，则返回它在主串S中第pos个字符之后；否则函数值为0。	，是模式匹配的目标。	必考
朴素匹配(BF算法)	从主串的每一个位置开始，逐个字符与模式串进行比较，。	，但****。最坏时间复杂度。	要求会模拟过程
KMP算法	利用已匹配的信息，保持，仅移动模式串。。	，平均时间复杂度 O(n+m)。	重中之重，必考next数组计算和匹配过程
Next(T, next[])	求模式串T的next数组。`next[j]` 表示当 `T[j]` 失配时，j应该回溯到的位置。	KMP算法的预处理步骤，时间复杂度 O(m)。	下午题核心考点，必须手工熟练计算
NextVal(T, nextval[])	对next数组的优化，解决模式串中连续相同字符导致的冗余回溯。	比next数组更高效，但预处理稍复杂。	常考，理解其优化思想

其他重要操作：这些操作在很多高级语言中作为标准库函数提供，但其思想需要理解。

操作名称（或常用函数名）	操作描述
StrInsert(&S, pos, T)	插入：在串S的第插入串T。
StrDelete(&S, pos, len)	删除：从串S中删除第的子串。
Replace(&S, T, V)	替换：用V替换主串S中出现的所有与T相等的不重叠子串。
StrSplit(S, delim)	分割：根据分隔符delim将串S分割成一个子串数组。
Index/LastIndexOf(ch)	字符查找：返回某个字符在串中第一次/最后一次出现的位置。

考点：
- 模式匹配算法：确定一个子串（模式串）在主串中的位置。
- （朴素匹配）：简单但效率低，最坏时间复杂度 O(n*m)。
- ：
  - 核心思想：当匹配失败时，利用已经部分匹配这个有效信息，保持主串指针不回溯，只将模式串向后“滑动”尽可能远的一段距离后继续比较。
  - 需要计算：（用于告诉模式串在）。
  - 算法复杂度：O(n+m)。

需要注意的问题

计算 next 数组：设模式串 abcabed 求模式串的 next 数组

next(0) 为标志位，当模式串发生不匹配时，且获取到需要移动到 0 位时，需要将主串的指针和模式串的指针都执行 ++ 操作。
对于任意模式串都可以写成 next(1)、next(2) 都可以直接写成 next(1) = 0、next(2) = 1
计算 next 数组时将模式串的第一个数到第 n 个数记作 1 , 2 , 3 .......... , n

i 为主串指针，j 为模式串指针

next数组：
 | next(0) | next(1) | next(2) | next(3) | next(4) | next(5) | next(6) | next(7) |
  -------------------------------------------------------------------------------
 |---------|    0    |   1     |    ?    |    ?    |    ?    |    ?    |    ?    |

推算 next(3) 
 
        i                                      i                         i  
        ↓                                      ↓                         ↓
? a b | ? ? ? ? ?    第三位发生了不匹配  ? a b | ? ? ? ? ? ?       ? a b | ? ? ? ? ? ?   
  a b | c a b e d    ---------------->     a | b c a b e d             | a b c a b e d         next(3) = 1
↓ ↓ ↓ | ↓ ↓ ↓ ↓ ↓                        ↓ ↓ | ↓ ↓ ↓ ↓ ↓ ↓           ↓ | ↓ ↓ ↓ ↓ ↓ ↓ ↓   
0 1 2 | 3 4 5 6 7                        0 1 | 2 3 4 5 6 7           0 | 1 2 3 4 5 6 7    
        ↑                                      ↑                         ↑
        j                                      j                         j

推算 next(4) next(5) next(6) next(7) 与此类似

结论：，模式串一次次后移，此时 j 指向的模式串编号是几对应 next(?) 就为多少

五、数组 (Array)

概念：线性表的推广，其。
考点：
- ：对于 m 行， n 列的二维数组 A[m][n]。
  - ：公式1
  - ：公式2

知识点

对于一维数组 a[n] ，起始地址为 a ，数组每个元素占 len 字节，则任意 a[i] 的存储地址为
对于二维数组 a[i][j] ， i 为行号，j 为列号，行优先存储则先存行数据再存列数据，反之就现存列，具体计算公式区分详见公式1、公式2
公式1: 按行存储，使用当前列号乘列再加行
公式2: 按列存储，使用当前行号乘列再加列

六、矩阵

概念：矩阵是一个是线性表的扩展。

6.1 特殊矩阵的压缩存储

为节省空间，：只为多个的元素存储空间，对。
绝大多数情况下，矩阵采用，即用一组地址连续的存储单元依次存储矩阵的元素。
压缩存储的核心思想是：。

6.1.1 对称矩阵

特点：n 阶方阵，满足 a[i][j] = a[j][i]。
压缩策略：只需存储（或上三角区）的元素。总共需要存储 n(n+1)/2 个元素。

假设我们以行优先的方式存储下三角区（包括对角线）的元素到一维数组 B[] 中。那么，原矩阵中元素 a[i][j] (下标从0开始！) 在数组 B 中的位置 k 为：

常见问法:
1. 给定 i 和 j，求 k（即求 a[i][j] 的存储位置）。
2. 给定 k，求 i 和 j（即问 B[k] 是原矩阵的哪个元素）。

6.1.2 三角矩阵

特点：上三角（或下三角）区的所有元素均为（通常是零）。
压缩策略：存储的元素 + 常量 c。

有一个下三角矩阵，行优先存储，元素 a[i][j] 在数组 B 中的位置 k 为：

注意：常量 c 存储在数组 B 的最后一个位置 B[n(n+1)/2]。

6.1.3 三对角矩阵（带状矩阵）

特点：所有非零元素都集中在以主对角线为中心的三条对角线的区域中。即满足 |i - j| > 1 时，a[i][j] = 0。
压缩策略：只存储三条对角线上的元素。

有一个下三对角矩阵，行优先存储，元素 a[i][j] 在数组 B 中的位置 k 为： k = 2i + j - 2 (或其他等价形式，需根据存储的起始位置调整)
- 更通用的思路：k = 2i + j - 3（如果下标从1开始），务必注意题目中数组下标是从0还是1开始。

6.1.4 稀疏矩阵

特点：矩阵中非零元素的个数 t 远小于矩阵元素的总数 m×n（即 t << m×n）。没有明显的分布规律。
压缩策略：只存储非零元素。因此，必须同时存储该非零元素所在的行、列及其值。

6.1.4.1 三元组顺序表

方法：每个非零元素用一个三元组 (i, j, v) 表示，其中 i 是行号，j 是列号，v 是值。将所有三元组按行优先的顺序存储在一个线性表中。

数据结构定义（可能考代码填空）：

#define MAXSIZE 1000 // 假设非零元个数的最大值为1000
typedef struct {
        int i, j;       // 行号，列号
        ElemType e;     // 元素值
} Triple;
typedef struct {
        Triple data[MAXSIZE + 1]; // 三元组表，data[0]未用或存储矩阵信息
        int mu, nu, tu;           // 矩阵的行数、列数、非零元个数
} TSMatrix;

：
- 优点：节约了存储空间。
- 缺点：失去了随机存取特性。进行矩阵转置、加法等操作时，算法较复杂。

6.1.4.2 十字链表

适用场景：当矩阵的（如矩阵加法），三元组表就不太方便，此时采用。
方法：每个非零元素用一个结点表示，结点中包含、以及指向的指针(right)和的指针(down)。
：可以灵活地插入和删除非零元，适用于。

七、广义表

定义：广义表是 n (n ≥ 0) 个数据元素 a1, a2, ..., an 的有限序列。
递归性：广义表中的元素 ai 可以是一个（不可再分的数据单元），也可以是另一个（称为）。这是其最重要的特性。
表示：通常用，用。例如：LS = (a1, a2, ..., an)。是广义表的名称。

7.1 特点

层次结构：广义表是一个。
共享性：一个（通过引用其名称）。
递归性：广义表可以是，从而构成。例如：E = (a, E) = (a, (a, (a, ...)))。
扩展性：广义表是。线性表的所有元素都是原子，因此是广义表的特例；树也可以用它来表示。

7.2 基本术语

术语	定义与示例	说明
长度	所含元素的个数。`A = (a, (b, c))` 的长度为。	计算的是最顶层的元素个数。
深度	括号的（即展开后所含括号的层数）。`A = (a, (b, c))` 的深度为。	深度 ≥ 1。空表的深度为1。
表头 (Head)	广义表的元素。`Head(A) = a`。	表头可以是原子，也可以是子表。
表尾 (Tail)	。`Tail(A) = ((b, c))`。	，这是最容易出错的地方！

7.3 常见题目

求广义表的长度和深度
- 求长度：看成了几部分。
  - A = ()：长度 = 0（空表）
  - B = (e)：长度 = 1
  - C = (a, (b, c, d))：长度 = 2 （元素是 a 和子表 (b, c, d)）
  - D = (A, B, C)：若 A, B, C 是表，则长度 = 3
- 求深度：看。从宏观上看，找到。
  - A = (a, b)：深度 = 1 （所有元素都是原子）
  - B = (a, (b, c))：深度 = 2
  - C = ((a, (b)), c)：深度 = 3
  - D = (())：深度 = 2 （外层括号内有一个空表）
取表头 (GetHead) 和取表尾 (GetTail) 操作

设广义表 L = (a, (b, c, d), e)
- GetHead(L) = a （第一个元素）
- GetTail(L) = ((b, c, d), e) （取出 a 后，剩下的部分是 ( (b, c, d), e )，它是一个子表）
- GetHead(GetTail(L)) = (b, c, d) （取上一步结果的表头）
- GetTail(GetTail(L)) = (e) （取 ((b, c, d), e) 的表尾，结果是 (e)）

判断广义表的存储结构
- 广义表通常采用。
- 结点有两种类型：
  - 表结点：标志域、指向表头的指针域、指向表尾的指针域。
  - 原子结点：标志域、值域。
判断说法是否正确
- ( ) 和 ( ( ) ) 是相同的。（错误。前者是空表，长度为0；后者是包含一个空表的非空表，长度为1）
- 广义表的表尾一定是一个广义表。（正确）
- 广义表难以用顺序存储结构表示。（正确，因为其元素结构不一致且长度可变）

八、小结

理解本质：理解每种结构的特点和适用场景，特别是栈和队列的LIFO/FIFO特性。
掌握计算：
- 。
- 。
- 。
- 。
精通操作：
- 链表的插入删除（指针修改顺序）。
- 栈在表达式求值中的应用（中缀转后缀算法）。
矩阵：
- 死记公式不如理解推导：理解下标换算公式是如何来的（例如，对称矩阵的行优先存储，k 的值就是 a[i][j] 前面有多少个元素），做题时可。
- 注意下标起点：软考题一定要是从开始还是从开始，这直接影响计算结果。90%的考题默认下标从0开始。
- 掌握三元组结构：要能写出三元组顺序表的类型定义。
- 会比较优缺点：能说出三元组和十字链表分别。

计算机基础知识

数据结构与算法

算法

线性结构原创

一、线性结构概述

二、线性表 (Linear List)

2.1 概念

2.2 存储结构

2.2.1 顺序存储（顺序表）

2.2.2 链式存储（链表）

2.3 顺序表 vs. 链表对比

三、栈 (Stack) & 队列 (Queue)

3.1 栈 (Stack) - LIFO (Last In First Out / 先进后出)

3.2 队列 (Queue) - FIFO (First In First Out / 先进先出)

四、串 (String)

五、数组 (Array)

六、矩阵

6.1 特殊矩阵的压缩存储

6.1.1 对称矩阵

6.1.2 三角矩阵

6.1.3 三对角矩阵（带状矩阵）

6.1.4 稀疏矩阵

6.1.4.1 三元组顺序表

6.1.4.2 十字链表

七、广义表

7.1 特点

7.2 基本术语

7.3 常见题目

八、小结

线性结构 原创 ​

一、线性结构概述 ​

二、线性表 (Linear List) ​

2.1 概念 ​

2.2 存储结构 ​

2.2.1 顺序存储（顺序表） ​

2.2.2 链式存储（链表） ​

2.3 顺序表 vs. 链表 对比 ​

三、栈 (Stack) & 队列 (Queue) ​

3.1 栈 (Stack) - LIFO (Last In First Out / 先进后出) ​

3.2 队列 (Queue) - FIFO (First In First Out / 先进先出) ​

四、串 (String) ​

五、数组 (Array) ​

六、矩阵 ​

6.1 特殊矩阵的压缩存储 ​

6.1.1 对称矩阵 ​

6.1.2 三角矩阵 ​

6.1.3 三对角矩阵（带状矩阵） ​

6.1.4 稀疏矩阵 ​

6.1.4.1 三元组顺序表 ​

6.1.4.2 十字链表 ​

七、广义表 ​

7.1 特点 ​

7.2 基本术语 ​

7.3 常见题目 ​

八、小结 ​

线性结构原创

一、线性结构概述

二、线性表 (Linear List)

2.1 概念

2.2 存储结构

2.2.1 顺序存储（顺序表）

2.2.2 链式存储（链表）

2.3 顺序表 vs. 链表对比

三、栈 (Stack) & 队列 (Queue)

3.1 栈 (Stack) - LIFO (Last In First Out / 先进后出)

3.2 队列 (Queue) - FIFO (First In First Out / 先进先出)

四、串 (String)

五、数组 (Array)

六、矩阵

6.1 特殊矩阵的压缩存储

6.1.1 对称矩阵

6.1.2 三角矩阵

6.1.3 三对角矩阵（带状矩阵）

6.1.4 稀疏矩阵

6.1.4.1 三元组顺序表

6.1.4.2 十字链表

七、广义表

7.1 特点

7.2 基本术语

7.3 常见题目

八、小结