栈

栈的基本概念

栈的定义

栈是只允许在一端进行插入或删除操作的线性表，即栈是一种操作受限的线性表

栈顶是线性表允许进行插入的那一端；栈底是固定的不允许进行插入的另一端；空栈是不含任何元素的空表

由于栈只能在栈顶进行插入和删除操作，所以栈的操作可以明显的概括为后进先出

栈满还存为上溢，栈空再取即下溢。上溢和下溢都修改了栈之外的内存，因此有可能导致程序崩溃

核心结论：出入栈流向与卡特兰数（2010、2011、2013、2018、2020、2022）

1. 出栈合法性：若 $a,b,c$ 依次入栈，则不可能出现先出 $c$ 后再出 $a$ 但 $b$ 还在栈内的情况（即“后入先出”约束）。

2. Catalan 数应用：$n$ 个不同元素进栈，不同的出栈序列总数为 ${\displaystyle \frac{1}{n+1}}{C}_{2n}^n$。

3. 共享栈（2014）：两个栈顶向中间靠拢，top1 - top0 == 1 时栈满。优点：空间利用率高，减少溢出。

n 个不同元素进栈，出栈元素不同排列的个数为 ${\displaystyle \frac{1}{n+1}}C(2n,n)={\displaystyle \frac{1}{n+1}}{C}_{2n}^n={\displaystyle \frac{1}{n+1}}{\displaystyle \frac{(2n)!}{n!\cdot n!}}$，这是卡特兰数。

核心结论：出栈序列合法性判定 (2025 技巧)

对于输入序列 $1,2,\dots ,n$，任何一个出栈元素 $x$ 之后出的所有比 $x$ 小的元素，必须是降序排列的。

• 示例：$4,1,2,3$ 不合法（$4$ 之后，$1,2,3$ 应该降序）。

• 示例：$3,2,4,1$ 合法。

出栈排列个数思考

把 n 个元素的出栈个数的记为 f(n)，显然有 f(1) = 1、f(2) = 2

第一个元素在出栈时可能会在位置 1、位置 2......一直到位置 n

如 1234 出栈的话会是 1234, 2134, 3214, 4321 其中 1 的位置分别是 1, 2, 3, 4

1. 假设第一个元素在位置 1，那么就和后面 n - 1 个元素的排序，即 f(n - 1)

2. 假设第一个元素在位置 2，那么有前面 1 个元素的排列和后面 n - 2 的元素排列，排列个数为 f(1) * f(n - 2)

3. 那么第一个元素在位置 i，那么有前面 i - 1 个元素的排列和后面 n - i 个元素的排列，排列个数为 f(i - 1) * f(n - i)

4. 把上面的都加起来就是 $f(n)=f(n-1)+f(1)\ast f(n-2)+\cdots +f(i-1)\ast f(n-i)+\cdots +f(n-1)$

5. 令 f(0) = 1，就有 $f(n)={\displaystyle \sum _{i=1}^{n}f(i-1)\ast f(n-i)}$

栈的基本操作

InitStack(&S);  // 初始化空栈

StackEmpty(S);  // 判断一个栈是否为空

Push(&S, x);  // 入栈

Pop(&S, &x);  // 出栈

GetTop(S, &x);  // 读取栈顶元素

DestroyStack(&s);  // 销毁栈

在解答算法题时，若题干未做出限制，则可直接使用这些基本的操作函数

栈的顺序存储结构

顺序栈的实现

采用顺序存储的栈称为顺序栈，它利用数组存放栈的数据元素，并附上一个指针指示当前栈顶元素的位置

#define MaxSize 50

typedef struct DNode{

    ElemType data[MaxSize];  // 存放栈中元素

    int top;  // 栈顶指针

}SqStack;

栈顶指针：S.top，出事时设置 S.top = -1

栈顶元素：S.data[S.top]

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

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

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

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

栈长：S.top + 1

顺序栈的基本操作

初始化

void InitStack(SqStack &S){

	S.top = -1;

}

栈判空

bool StackEmpty(SqStack &S){

    // 为什么不 return S.top == -1;

	if(S.top == -1)

		return true;

	else

		return false;

}

进栈

bool Push(SqStack &S, ElemType x){

	if(S.top == MaxSize-1)  // 栈满

		return false;

	S.data[++S.top] = x;  // 指针加 1 再入栈

	return true;

}

出栈

bool Pop(SqStack &S, ElemType &x){

	if(-1 == S.top)  // 栈空

		return false;

	x = S.data[S.top--];  // 先出栈，指针再减 1

	return true;

}

读取栈顶元素

bool GetTop(SqStack &S, ElemType &x){

	if(-1 == S.top)  // 栈空

		return false;

	x = S.data[S.top];  // 记录栈顶元素

	return true;

}

注意：栈顶指针的初始化差异

若栈初始化为 S.top = 0 (指向栈顶元素的下一个位置)，那么入栈就变成了 S.data[S.top++] = x 出栈就变成了 x = S.data[--S.top]。做题时务必根据题目中 top 的初始化设定位序！

共享栈

利用栈第位置相对不变的特性，可让两个顺序栈共享一个以为数组空间

将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸

top0 == -1 时 0 号栈为空，top1 == MaxSize 时 1 号栈为空；当两个栈顶指针相邻（top1 - top0 = 1）时，栈满

当 0 号栈进栈时先加 1 再赋值，1 号栈进栈时先减 1 再赋值；出栈时相反

共享栈是为了更有效地利用存储空间，两个栈地空间相互调节，只有在整个存储空间被占满时才发生上溢

原本一个栈用得多一个栈用的少，两个分配同样的内存，用的多的容易上溢，现在共享栈自己用完了会用另外一个栈的空间，没那么容易上溢

栈的链式存储结构

采用链式存储的栈称为链栈，链栈的优点是便于多个栈共享空间和提高其效率，且不存在栈满上溢的情况（这里的共享空间是指更方便多个栈共享内存空间）

链栈通常使用单链表来实现，并规定所有操作都是在单链表的表头进行的，通常链栈没有头结点

typedef struct Linknode {

    ElemType data;  // 数据域

    struct Linknode *next;  // 指针域

} *LiStack;

链栈的操作和链表相似，只是入栈和出栈的操作都在链表的表头进行

队列

队列的基本概念

队列的定义

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

向队列插入元素称为入队或进队；删除元素称为出队或离队，其操作的特性是先进先出

队列常见的基本操作

InitQueue(&Q);  // 初始化队列

QueueEmpty(Q);  // 判队列是否为空

EnQueue(&Q, x);  // 入队

DeQueue(&Q, &x);  // 出队

GetHead(Q, &x);  // 读取头元素

队列的顺序存储结构

队列的顺序存储

队列的顺序是指分配一块连续的存储单元存放队列中的元素，并附有队头指针和队尾指针

#define MaxSize 5

typedef int ElemType;

typedef struct {

	ElemType data[MaxSize];  // 存放队列元素

	int front, rear;  // 对头指针和队尾指针

} SqQueue;

初始条件：Q.front = Q.rear = 0

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

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

出队操作：队不空时，先取队头元素，再将队头指针加 1

顺序队列缺点：没用重复利用使用过的空间，造成空间上的浪费

循环队列

环形队列即把存储队列元素的表从逻辑上视为一个环，当队首指针 Q.front = MaxSize - 1 后，再前进就变成 0，这就利用到了之前顺序队列所没用利用的空间

初始时：Q.front = Q.rear = 0

3. 类型中增加标志 tag 成员。入队置 tag=1，出队置 tag=0。因为只有入队会导致队满，只有出队会导致队空。队空条件为 Q.front == Q.rear && tag == 0；队满条件为 Q.front == Q.rear && tag == 1

考点追踪：循环队列核心公式（2023 高频）

1. 队空：front == rear

2. 队满（牺牲一单元）：(rear + 1) % MaxSize == front

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

4. 入队：rear = (rear + 1) % MaxSize

5. 出队：front = (front + 1) % MaxSize

核心结论：双端队列

1. 输入受限：一端入，两端出。

2. 输出受限：两端入，一端出。

3. 常考点：判断某个序列是否能通过上述队列得到（2010、2021）。

核心结论：循环队列判全满/全空 (三种方案)

1. 少用一个单元（最常用）：队满 (rear+1)%M == front，队空 rear == front。

2. 设置 Size 字段：队满 size == M，队空 size == 0。

3. 设置 Tag 字段：tag=1 为入，tag=0 为出。front == rear 时看 tag。

循环队列的操作

初始化

void InitQueue(SqQueue &Q) {

	Q.rear = Q.front = 0;

}

判队空

bool isEmpty(SqQueue &Q) {

	if(Q.rear == Q.front)

		return true;

	else	

		return false;

}

入队

bool EnQueue(SqQueue &Q, ElemType x) {

	if((Q.rear + 1) % MaxSize == Q.front)  // 队满

		return false;

	Q.data[Q.rear] = x;

	Q.rear = (Q.rear + 1) % MaxSize;  // 表尾向前进 1

	return true;

}

出队

bool DeQueue(SqQueue &Q, ElemType &x){

	if(Q.rear == Q.front)  // 队空

		return false;

	x = Q.data[Q.front];

	Q.front = (Q.front + 1) % MaxSize;  // 表头向前进 1

	return true;

}

队列的链式存储结构

队列的链式存储

队列的链式表示称为链队列，实际上就是一个带队头指针和队尾指针的单链表

头指针指队头结点，尾指针指队尾结点，队列的链式存储结构为：

typedef struct LinkNode {  // 链式队列结点

	ElemType data;

	struct LinkNode *next;

} LinkNode;



typedef struct {

	LinkNode *front, *rear;  // 队头和队尾指针

} LinkQueue;

当 Q.front == NULL && Q.rear == NULL 时，链式队列为空

入队时，若队列不为空，从队头弹出一个元素；出队时，直接把新元素插入队尾

由于不带头结点的链式队列在操作上往往比较麻烦，因此通常会把链接队列设计成带头结点的单链表

单链表表示的链式队列适合数据元素变动比较大的情形，且不存在队列满且产生溢出问题

当程序中要使用多个队列，域多个栈的情形一样，最好使用链式队列，这样就不会出现存储分配不合理和溢出

链式队列的基本操作

初始化

void InitQueue(LinkQueue &Q){

    // 这里是带头结点单链表实现的链式队列

	Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));

	Q.front -> next = NULL; 

}

判队空

bool IsEmpty(LinkQueue &Q){

	if(Q.front == Q.rear)

		return true;

	else

		return false;

}

入队

void EnQueue(LinkQueue &Q, ElemType x){

	LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));

	s -> data = x;

	s -> next = NULL;

	Q.rear -> next = s;  // 插入到队尾

	Q.rear = s;

}

出队

bool DeQueue(LinkQueue &Q, ElemType &x){

	if(Q.front == Q.rear) return false;

	LinkNode *p = Q.front -> next;  // 弹出一个头结点

	x = p -> data;

	Q.front -> next = p -> next;

	if (Q.rear == p)  // 弹出后队列为空，设置一下 Q.rear 位置

		Q.rear = Q.front;

	free(p);

	return true;

}

双端队列

双端队列是指允许两端都可以进行入队和出队操作的队列，其元素的逻辑结构仍是线性结构，将队列的两端分别称为前端和后端，两端都可以入队和出队

在两端队列进队时，前端进的元素会在后端进的元素前面，后端进的元素会在前端进的元素后面；出队时先出的元素排在后出的元素的前面

例如：前端入 a 队中是 a，后端入 b 队中是 ab，前端入 c 队中是 cab；后端出队队中 ca 队外 b，后端再出队中 c 队外 ba，前端出队队外 bac

输出受限的双端队列：允许在一端进行插入和删除，但在另一端只允许插入的双端队列

输入受限的双端队列：允许在一端进行插入和删除，但在另一端只允许删除的双端队列

例子：如果有 1，2，3，4 四个数字，要令他输出 2，4，1，3 那么双向队列操作为：

1. 左入，内部 1，外部

2. 左入，内部 21，外部

3. 左出，内部 1，外部 2

4. 右入，内部 13，外部 2

5. 左入，内部 413，外部 2

6. 左出，内部 13，外部 24

7. 左出，内部 3，外部 241

8. 右出，内部，外部 2413

考点追踪：双端队列出入队操作的分析（2010、2021）

对于输入序列 1, 2, 3, 4：

1. 能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的是：4, 1, 3, 2

2. 能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的是：4, 2, 1, 3

3. 既不能由输入受限的得到，也不能由输出受限得到的是：4, 2, 3, 1 和 4, 1, 3, 2 (其中 4,2,3,1 完全无法得到)

元素复用且空间可增的队列

请设计一个队列，要求满足（会做）：

1. 初始时队列为空

2. 入队时，允许增加队列占用空间

3. 出队后，出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减

4. 入队操作和出队操作的时间复杂度始终保持为 O(1)

设计出的队列：循环单链表，最好带头结点

因为队列是循环的，所以弹出元素不需要释放掉，等下次入队时重复利用，当队满时入队也可以分配结点链上去

队空条件：front == rear；队满条件：front == rear -> next

// 入队

if (front == rear -> next)

    在 rear 后面插入一个新空结点;

入队元素保持到 rear 所致结点中;

rear = rear -> next;



// 出队

if (front == rear)

    则出队失败，return false;

取 front 所指结点中的元素 e;

front = front -> next;

return e;

栈和队列的应用

栈在括号匹配中的应用

假设表达式中允许包括两种括号：圆括号和方括号，其嵌套的顺序任意即 ([]()) 或 [([][])] 等均为正确格式，[(]) 或 ([()) 等均为不正确的格式，先需要设计一个算法来检验表达式是否是正确格式

分析如下：

检测所有括号是否匹配，就是检查每一个局部的括号是否匹配

只要我们匹配好每一个局部的括号，并把匹配好的括号去掉，继续向外匹配，那么就可以了

那么我们只需要用一个空间放左括号，然后那它与右括号匹配，匹配上了就可以了

而左括号很明显是最后看见的最先匹配，所以要用到栈，后进先出

算法思想：

1. 初始化设置一个栈

2. 如果是左括号压入栈，如果是右括号就和栈顶的括号匹配，匹配成功出栈继续，失败退出

栈在表达式求值中的应用

中序表达式 A + B * (C - D) - E / F 所对应的后缀表达式为 ABCD-*+EF/-，后缀表达式没有括号，它已经考虑了运算符的优先级，后缀表达式的运算符在操作数后面

通过后缀表示计算表达式值得过程为：

扫描表达式得每一项，根据它的类型做如下操作

1. 若是操作数，那么压入栈

2. 若是操作符 <op> 则连续从栈弹出两个操作数 Y 和 X，做运算 X <op> Y，并将运算结果压入栈中

3. 当表达式扫描完时，栈顶存放的就是最终结果

中缀转后缀的过程

| 操作符 | # | ( | *, / | +, - | ) |

| ------ | ---- | ---- | ---- | ---- | ---- |

| isp | 0 | 1 | 5 | 3 | 6 |

| icp | 0 | 6 | 4 | 2 | 1 |

其中 isp 是栈内优先数，icp 是栈外优先数，在表达式后面加上符号 '#' 表示表达式结束

扫描中缀表达式的没一项做以下操作：

1. 先把 '#' 入栈然后继续下面操作

2. 如果是操作数直接输出

3. 如果是操作符 op 分下面三种情况

   1. isp(栈顶) < icp(op) 把 op 进栈，下一个

   2. isp(栈顶) == icp(op) 把栈顶出栈输出，废弃 op，下一个

   3. isp(栈顶) > icp(op)，把栈顶出栈输出，重新判断 op

4. 读取到结束标识 '#' 结束

手工转缀（括号法）

示例表达式 a / b + (c * d - e * f) / g

1. 按照运算符优先级队所有的运算单位加括号，((a / b) + (((c * d) - (e * f)) / g))

2. 如果把每个操作符提到自己的括号前面就是前缀表达式：+(/(ab)/(-(*(cd)*(ef))g))=+/ab/-*cd*efg

3. 如果把每个操作符提到自己的括号后面就是后缀表达式：((ab)/(((cd)*(ef)*)-g)/)+=ab/cd*ef*-g/+

核心结论：中缀转后缀逻辑 (2025 必查)

• 操作数：直接输出。

• 左括号：直接入栈。

• 右括号：不断出栈直至弹出左括号。

• 运算符：若优先级高于栈顶，入栈；否则不断出栈，直到遇到更低优先级的或左括号。

栈在递归中的应用

若在一个函数、过程或数据结构的定义中又应用了它自身，则这个函数、过程或数据结构称为是递归定义的

递归策略只需要少了的代码就可以描述出解题过程所需要的多次重复运算，大大减少了程序的代码量，但通常情况下，递归的效率不是很高

注意递归模型不能是死循环，必须满足两个条件：

• 队规表达式（递归体）

• 边界条件（递归出口）

递归过程中，系统会使用栈来存储返回点、局部变量、传参等，递归次数过多会造成栈溢出

有序递归过程中可能会包含很多重复的运算，这是其效率不高的原因

将递归算法转换为非递归算法，通常需要借助栈来实现

队列在层次遍历中的应用

在信息处理中有一大类问题需要逐层或逐行处理，需要等到当前层或当前行处理完成才会处理下一层或下一行

这时需要使用队列保存下一步处理的顺序，例如层次遍历二叉树过程：

1. 根节点入队

2. 队空即遍历完成，则结束遍历，否则进行第三步

3. 队列中第一个结点出队，若有左儿子，则左儿子入队；右儿子也一样，返回第二部

队列在计算机系统中的应用

队列在计算机系统中的应用非常广泛，下面仅从两个方面来简述队列在计算机系统中的作用：

• 解决主机与外部设备之间速度不匹配的问题

  主机输出数据的速度比打印机快很多，直接把数据全塞给打印机是不行的

  使用我们会在打印机设置一个数据缓存区，而这个缓存区是队列确保输入和输出的数据位置一样

  主机把数据写入这个缓冲区，写满就暂停做其他时，等打印机消化完数据再通知主机继续发送

• CPU 资源竞争问题

  再带多终端的计算机系统上，右多个用户需要 CPU 运行主机的程序，它们向操作系统提出占用 CPU 的请求

  操作系统按照每个请求的时间拍成一个队列，然后弹出运行相应的时间后再塞回队列，直到程序运行完

  这样既能满足每个用户的请求，又使 CPU 能够正常运行

数组和特殊矩阵

数组的定义

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

数组是线性表的推广，一维数组可视为一个线性表；二位数组是视为元素是定长线性表的线性表

数组一旦被定义，其维数和维界就不再改变，除结构的初始化和销毁外，数组只会有存取元素和修改元素的操作

数组的存储结构

一个数组在内存中占用一段连续的空间，以一维数组 A[0...n - 1] 为例，存储结构关系为 $LOC(a_i)=LOC(a_0)+i\times L(0\le i<n)$，其中 L 是每个数组元素所占的存储单元

对于多维数组，有两种映射方法：按行优先和按列优先，以二维数组为例：

• 按行优先：先行后列，先存储行号较小的元素，再存储列较小的元素，设行标和列标范围为 $[0,h_1]$ 和 $[0,h_2]$

  则它的存储结构关系式为 $LOC(a_{i,j})=LOC(a_{0,0})+[i\times (h_2+1)+j]\times L$

  

• 按列优先：先列后行，先存储列号较小的元素，再存储行较小的元素，设行标和列标范围为 $[0,h_1]$ 和 $[0,h_2]$

  则它的存储结构关系式为 $LOC(a_{i,j})=LOC(a_{0,0})+[j\times (h_1+1)+i]\times L$

  

矩阵的压缩存储

压缩存储：指多个值相同的元素只分配一个存储空间，队零元素不分配存储空间

特殊矩阵：指具有许多相同矩阵元素或零元素，并且这些矩阵元素分布有一定的规律性，通常有：对称矩阵、上（下）三角矩阵、对角矩阵等

特殊矩阵的压缩方法：找出特殊矩阵的分布规律，把那些规律性分布、值相同的多个矩阵元素压缩存储到一个存储空间

对称矩阵

对称矩阵是指对于任意一个矩阵内元素 $a_{i,j}$ 都有 $a_{i,j}=a_{j,i}$，其中元素可以分成 3 个部分，上三角区、主对角线、下三角区

对于 n 阶对称矩阵，上三角的元素和下三角的元素相同，如果使用二维数据存储会浪费空间，所有应该采用一维数组存储，舍弃上三角的元素，仅存储下三角的元素和主对角线元素

一维数组的大小应该是除主对角元素个数的一半再加上主对角元素的个数 $n(n-1)/2+n=n(n+1)/2$

在一维数组中，元素 $a_{i,j}(i\ge j)$ 前面元素的个数为：

1. 第 1 行：1 个元素

2. 第 i - 1 行：i - 1 个元素

3. 第 i 行：j - 1 个元素

所以元素 $a_{i,j}$ 在一维数组中的下标 $k=1+...+(i-1)+j-1=i(i-1)/2+j-1$（数组从 0 开始时）

而对称矩阵元素是对称的，对于 $a_{i,j}(i<j)$ 就是计算 $a_{j,i}$ 的位置

那么就得出元素下标之间的对应关系：$k=\{\begin{array}{cc}{\displaystyle \frac{i(i-1)}{2}}+j-1,& i\ge j（\mathrm{下}\mathrm{三}\mathrm{角}\mathrm{区}\mathrm{和}\mathrm{主}\mathrm{对}\mathrm{角}\mathrm{线}\mathrm{元}\mathrm{素}）\\ {\displaystyle \frac{j(j-1)}{2}}+i-1,& i<j（\mathrm{上}\mathrm{三}\mathrm{角}\mathrm{区}\mathrm{元}\mathrm{素}）\end{array}$

注意：如果数组下标从 1 开始的话，运算出来的结果要加 1

注意：这里使用的是行优先来计算，如果是列优先的话可以对称过来当作行优先计算

三角矩阵

下三角矩阵

下三角矩阵中，上三角区域的所有元素均为同一常量，使用一个位置来存储就好了，设置在数组最后

因此我们只需要存储下三角元素和主对角元素以及额外常量，大小为 $n(n+1)/2+1$

当 i < j 时，取上三角元素，就访问数组的最后一个元素 $n(n+1)/2$ 拿到常量就好了

当 $i\ge j$ 时，取下三角元素，这里的计算思路和对称矩阵的一样，结果是 $i(i-1)/2+j-1$

上三角矩阵

上三角矩阵中，下三角区域的所有元素均为同一常量，也是使用数组最后的元素来存储，数组大小和上三角矩阵一样

与下三角不同这里第 1 行是有 n 个元素的，所以不能套用对称矩阵的公式

在一维数组中，元素 $a_{i,j}(i\le j)$ 前面元素的个数为：

1. 第 1 行：1 个元素

2. 第 i - 1 行：n - i + 2 个元素

3. 第 i 行：j - i 个元素

所以元素 $a_{i,j}$ 在一维数组中的下标 $k=n+(n-1)+\cdots +(n-i+2)+j-i=(i-1)(2n-i+2)/2+(j-i)$

那么就得出元素下标之间的对应关系：$k=\{\begin{array}{cc}{\displaystyle \frac{(i-1)(2n-i+2)}{2}}+(j-i),& i\le j（\mathrm{上}\mathrm{三}\mathrm{角}\mathrm{区}\mathrm{和}\mathrm{主}\mathrm{对}\mathrm{角}\mathrm{线}\mathrm{元}\mathrm{素}）\\ {\displaystyle \frac{n(n+1)}{2}},& i>j（\mathrm{下}\mathrm{三}\mathrm{角}\mathrm{区}\mathrm{元}\mathrm{素}）\end{array}$

注意：如果数组下标从 1 开始的话，运算出来的结果要加 1

注意：这里使用的是行优先来计算。上三角的列优先和下三角的行优先类似；下三角的列优先于上三角行优先类似

三对角矩阵

三对角矩阵也称带状矩阵，对于 n 阶矩阵的任意元素 $a_{i,j}$ 当 |i - j| > 1时，有 $a_{i,j}=0$

三对角矩阵的所有非零元素都集中在以主对角线为中心的 3 条对角线区域，其余区域元素都为零

对三角矩阵采用压缩存储，按行优先方式存储放在一维数组中，数组长度为 3n - 2

元素在一维数组的下标计算为：第一行的个数 + 前面三个元素的行数 + 当前行前面的元素

即元素 $a_{i,j}$ 的下标 $k=2+3(i-2)+(j-i+1)=2i+j-3$

考点追踪：特殊矩阵下标计算（2016、2018、2020、2021、2024）

1. 对称矩阵（行优先存储下三角）：$k=\frac{i(i-1)}{2}+j-1$ (下标从 0 开始)。

2. 三对角矩阵：第 $i$ 行非零元素起始下标为 $2i-3$；元素 $a_{i,j}$ 位序 $k=2i+j-2$。

3. 普通数组地址推导：

• 行优先：$Loc(a_{i,j})=Loc(0,0)+(i\times n+j)\times size$

• 列优先：$Loc(a_{i,j})=Loc(0,0)+(j\times m+i)\times size$

注意：如果数组下标从 1 开始的话，运算出来的结果要加 1

注意：这里使用的是行优先来计算。不过列优先和行优先差不多

稀疏矩阵

矩阵中非零的元素的个数对于矩阵元素的个数来说非常少，如 $100\times 100$ 的矩阵只有不到 100 的非零元素

如果采用常规法来存储就很浪费空间了，所以将非零元素及其相应的行和列构成一个三元组（行标、列标、值）

核心结论：稀疏矩阵存储方式

1. 三元组表：$O(\mathrm{非}\mathrm{零}\mathrm{元}\mathrm{个}\mathrm{数})$。失去了随机存取特性（需遍历查找行列）。

2. 十字链表：每一行、每一列各有一个带头结点的循环链表。适合频繁增删非零元素。

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