经过长达半个月的革命死战，终于来到了数据结构里更常见也更深一步的栈，队列和数组这一部分内容。然后明天就是中秋节了，这里面呢，贫道先提前祝各位道友是中秋快乐，合家团圆，心想事成，幸福美满。然后的话，就是大家喜闻乐见的看博文的环节了（虽然我感觉这种类型的也不会有什么人看。。。），闲话少叙，各位，请上眼。

栈，队列和数组

基础补充

我先说个前提啊，本人平时用$C++$比较多，所以针对这些特殊的数据结构，我就直接用$C++$的$STL$标准模板库来写了。想搞编程竞赛的童鞋们也可以去自学一下$STL$这个东西，比你考试的时候手撕算法要方便多了。

  • 栈这个东西通俗讲就是一个线性表，不过对数据的存取操作只能在表的一端进行，就是插入数据和删除数据都只能通过对一个叫“栈顶”的东西进行操作完成（栈顶一般保存在指针里）。概括来说，栈的操作过程是“后进先出”。什么概念呢？举个例子：假设某栈$S = (a_1, a_2, a_3, a_4, a_5)$，其中$a_1$是栈底元素，$a_5$是栈顶元素。若元素按顺序$a_1, a_2, a_3, a_4, a_5$入栈，那么出栈顺序必定是$a_5, a_4, a_3, a_2, a_1$。

  • 队列的操作方式和栈正好相反，概括来说是“先进先出”，元素只允许在表的一端插入（这种操作叫入队），在另一端弹出（这种操作叫出队）。

注：这里要打个重点号。根据栈和队列的描述，我们不难看出，不论是栈还是队列，都是一种操作受限的线性表，即它们的操作只能在表的一端或两端完成，所以假设你声明了一个栈：

stack<int> s;

你是万万不能直接访问$s[1]$或$s[5]$还是其他什么东西的，因为栈和队列都不允许你直接访问中间的某个元素。

注：这里要打两个重点号。选择题经常会拿着一个入栈序列或者入队序列，然后让你分析当栈或队列中所有元素均被弹出之后可能会产生什么样子的序列。考队列的情况一般出现在双端队列的情况下。

  • 数组是由$n (n \ge 1)$个相同类型的数据元素组成的有限序列。道友们如果看过上一篇《线性表》的话，应该能看出来，很多大题的编码我是通过数组完成的。得益于数组的连续存储和随机访问的特性，在很多情况下，数组仍然有它活跃的舞台。

接下来我将分别讲讲这三个数据结构的应用和它们的大题。

栈

$\mathrm{STL}$中栈的操作

// 头文件
#include<stack>
using namespace std;

stack<int> s;           // 空栈

// 常用操作
s.push(x);              // 入栈，将 x 压入栈顶，O(1)
s.pop();                // 出栈，删除栈顶元素，O(1)，不返回被删元素
s.top();                // 返回栈顶元素，O(1)
s.empty();              // 判断栈是否为空，O(1)
s.size();               // 返回栈中元素个数，O(1)
s.emplace(args...);     // 原地构造并入栈，效率略高于 push，O(1)

如我们刚才所说的，栈和队列不能访问中间元素，因此不能遍历，也不能用迭代器（就是$\mathrm{for}$循环里那个$i$）。所以要访问栈中的所有元素，你只能不断.top()然后.pop()。

考试的时候如果写代码规定了栈的结构和相应操作，那就按照题目要求来。

栈的应用

括号匹配

假设表达式中允许包含两种括号：圆括号$( )$和方括号$[ ]$，嵌套顺序任意，例如$( [ ] ( ) )$或$[ ( [ ] [ ] ) ]$均是合法表达式，而$[ ( ] )$，$( [ ( ) )$和$( ( ) ]$均是非法格式。

算法初始化一个空栈，顺序扫描输入的括号序列，若遇到左括号，将其压入栈中，表示新增一个待匹配的期待，且优先级最高。若遇到右括号，则检查栈是否为空：若栈非空且栈顶左括号与当前右括号匹配，则弹出栈顶，完成一次匹配；否则，括号序列非法，算法终止。扫描结束后，若栈为空，则括号序列合法，否则非法。

#include <iostream>
#include <string>
#include <stack>
using namespace std;

bool checkBrackets(const string& exp) 
{
	stack<char> st;                     // 使用 STL 栈

	for (char ch : exp) 
	{
		if (ch == '(' || ch == '[') 
		{
			st.push(ch);                // 左括号入栈
		}
		else if (ch == ')') 
		{
			if (st.empty() || st.top() != '(') 
			{
				return false;           // 栈空或栈顶不是 '('
			}
			st.pop();                   // 匹配成功，弹出
		}
		else if (ch == ']') 
		{
			if (st.empty() || st.top() != '[') 
			{
				return false;           // 栈空或栈顶不是 '['
			}
			st.pop();
		}
		// 其他字符（字母、数字、运算符等）直接忽略
	}

	return st.empty();                  // 栈空说明全部匹配
}

栈在表达式求值中的应用

中缀表达式转后缀表达式

在开这个题之前，我先介绍一下相关的概念。

  • 中缀表达式：是人们常用的表达式，运算符位于两个操作数之间，如$3 + 4$。虽然符合人类阅读习惯，但不利于计算机求值。中缀表达式必须依靠括号来明确运算次序。

  • 前缀表达式：运算符位于两个操作数之前，如$+ 3 4$。

  • 后缀表达式：运算符位于两个操作数之后，如$3 4 +$。

然后见真题：

给定中缀表达式，将其转换成对应的后缀表达式。如中缀表达式$A + B * (C - D) - E / F$转换为$ABCD-*+EF/-$。（如果把中缀表达式写成表达式树，即非叶节点放运算符，叶节点放操作数）。

考试的时候可能会考手算，所以手算方法这里我也介绍一下：

1) 按运算优先级对整个表达式逐层加括号。

2) 将每个运算符都移到其所在括号的右括号之后，形成“左操作数 右操作数 运算符”的结构。

3) 删除所有括号，得到后缀表达式。

转化成算法的思想如下：

1) 遇到操作数：直接加入后缀表达式。

2) 遇到界限符：若为“$($”，直接入栈，若为“$)$”，不入栈，且不断弹出栈顶运算符并加入后缀表达式，直到遇到“$($”，将其弹出并丢弃。

3) 遇到运算符，分两种情况：

  • 若其优先级高于栈顶运算符或栈顶为“$($”，则直接入栈。

  • 若其优先级低于或等于栈顶运算符，则依次弹出栈中运算符并加入后缀表达式，直到栈空或栈顶为“$($”或栈顶运算符为优先级更低的运算符为止，再将当前运算符入栈。

代码如下：

// 返回运算符优先级，数字越大优先级越高
int priority(char op) 
{
	if (op == '+' || op == '-') return 1;
	if (op == '*' || op == '/') return 2;
	return 0;   // '(' 或 ')' 视为最低
}

// 中缀转后缀
string infixToPostfix(const string& infix) 
{
	stack<char> opStack;        // 运算符栈
	string postfix;             // 结果字符串

	for (int i = 0; i < (int)infix.size(); i++) 
	{
		char ch = infix[i];

		// 1. 跳过空格
		if (ch == ' ') continue;

		// 2. 如果是数字（支持多位数），直接加入结果
		if (isdigit(ch)) 
		{
			while (i < (int)infix.size() && isdigit(infix[i])) 
			{
				postfix += infix[i];
				i++;
			}
			postfix += ' ';     // 用空格分隔操作数，方便阅读
			i--;                // 回退一格，因为 for 循环会 i++
		}
		// 3. 左括号直接入栈
		else if (ch == '(') 
		{
			opStack.push(ch);
		}
		// 4. 右括号：弹出栈顶直到遇到左括号
		else if (ch == ')') 
		{
			while (!opStack.empty() && opStack.top() != '(') 
			{
				postfix += opStack.top();
				postfix += ' ';
				opStack.pop();
			}
			if (!opStack.empty()) opStack.pop();    // 弹出左括号，不输出
		}
		// 5. 运算符：比较优先级
		else 
		{
			// 栈顶运算符优先级 >= 当前运算符时，先弹出（保证左结合）
			while (!opStack.empty() && opStack.top() != '(' && priority(opStack.top()) >= priority(ch)) 
			{
				postfix += opStack.top();
				postfix += ' ';
				opStack.pop();
			}
			opStack.push(ch);
		}
	}

	// 6. 把栈中剩余运算符全部弹出
	while (!opStack.empty()) 
	{
		postfix += opStack.top();
		postfix += ' ';
		opStack.pop();
	}

	return postfix;
}

后缀表达式求值

算法执行过程：从左到右依次扫描表达式，若当前项是操作数，则将其入栈，若是操作符$op$，则从栈中弹出两个操作数，先弹出的是右操作数$Y$，后弹出的是左操作数$X$（左操作数就是中缀表达式里左边的数，右操作数就是右边的。加法和乘法里是不区分的，但减法和除法是必须要区分的）。执行运算$X op Y$并将结果作为操作数压回栈中。所有项处理完毕后，栈顶元素即为最终计算结果。

// 计算后缀表达式（操作数与运算符之间用空格分隔）
int evaluatePostfix(const string& postfix) 
{
	stack<int> st;                  // 操作数栈
	istringstream iss(postfix);
	string token;

	while (iss >> token) 
	{
		// 如果是运算符
		if (token == "+" || token == "-" || token == "*" || token == "/") 
		{
			int b = st.top(); st.pop();   // 先弹出的是右操作数
			int a = st.top(); st.pop();   // 后弹出的是左操作数
			int res = 0;
			if (token == "+")      res = a + b;
			else if (token == "-") res = a - b;
			else if (token == "*") res = a * b;
			else                   res = a / b;   // 整数除法
			st.push(res);
		}
		// 否则是操作数，转换为整数后入栈
		else 
		{
			st.push(stoi(token));
		}
	}
	return st.top();                // 栈顶即为最终结果
}

栈在递归中的应用

这部分内容不是编码，而是讲计算机在处理程序中的递归时的操作。首先，我们先给基础差的同学讲讲什么是递归。

  • 递归：一个函数，过程（过程其实就是函数，只不过没有返回值，一般在$Java$和$python$里区分。大家就把过程当函数就行）或数据结构在其定义中直接或间接地引用了自身，则称其为递归定义。简称递归。编程中最常见的是函数/过程的递归。

例如，斐波那契数列就是一个很经典的递归程序：

斐波那契数列（$F$）的$F_0$和$F_1$分别是$0$和$1$，其余项$F_n$均可用$F_{n - 1} + F_{n - 2}$表示。整理出来就是这个：

$$ F_n = \begin{cases} F_{n - 1} + F_{n - 2}, n \gt 1 \\\\ 1, n = 1 \\\\ 0, n = 0 \end{cases} $$

程序实现如下：

int F(int n) 
{
	if (n == 0) 
	{
		return 0;
	}
	else if (n == 1) 
	{
		return 1;
	}
	else 
	{
		return F(n - 1) + F(n - 2);
	}
}

由此可见，递归的精髓就在于能否将原问题转化成规模更小的问题。

那么栈是如何在运行递归程序的过程中工作的呢？在递归调用中，系统为每一层调用的返回地址、局部变量和形式参数等信息分配存储空间，这些信息被保存在递归工作栈中（这是硬件的东西了，没错，计算机硬件的存储部件里就有一个部分是栈空间）。

队列

$\mathrm{STL}$中队列的操作

#include <queue>
using namespace std;

queue<int> q;	// 和stack相同，不能用临时变量直接指定长度

// 常用操作
q.push(x);              // 入队，将 x 添加到队尾，O(1)
q.pop();                // 出队，删除队头元素，O(1)，不返回被删元素
q.front();              // 返回队头元素，O(1)
q.back();               // 返回队尾元素，O(1)
q.empty();              // 判断队列是否为空，O(1)
q.size();               // 返回队列中元素个数，O(1)
q.emplace(args...);     // 原地构造并入队，效率略高于 push，O(1)

几种特殊队列（$\mathrm{STL}$里是没有的）

循环队列

为解决顺序队列的假溢出问题，我们引入了循环队列。但是嘛叫假溢出呢？

在解释假溢出之前，我们先阐述一下顺序队列：

在顺序存储队列中，也就是在一块连续的存储单元中存放的队列中会设置两个指针：队头指针$front$指向队首元素，队尾指针$rear$指向队尾元素的下一位置（便于直接插入），那么这种情况下，队列的定义可以表示为：

#define MaxSize 50		// 定义队列的最大长度
typedef struct 
{
	ElemType data[MaxSize];	// 数组存放队列元素
	int front, rear;		// 队首指针和队尾指针
}SqQueue;

在顺序队列中：

  • 队列判空条件可以是$Q.front == Q.rear == 0$。

  • 入队操作是：元素存队尾，队尾指针加$1$。

  • 出队操作是：队列非空时，取出队首元素，再将队首指针加$1$。

大家发现了吗？随着队列元素不断入队出队，队首指针和队尾指针都会向前跑，并最终队尾指针$rear$跑到队列长度上限$MaxSize$。这个时候，队首指针$front$基本已经不在原来的位置上了，也就是说，队首指针和队尾指针之间的距离肯定小于队列的最大长度，也就是说队列根本没满。但如果这个时候我们继续向队列中插入元素，必然会导致队尾指针$rear$跑到比$MaxSize$大的地方，即发生上溢出。但实际上队列中仍然有空闲单元，因此这个现象叫做假溢出。

那么循环队列如何解决假溢出呢？循环队列就是在队列组织上，将顺序存储的物理空间在逻辑上组织成环状。当指针到达数组末尾时，通过对$MaxSize$取模回到起始位置。那么相应的就有：

  • 初始状态：$Q.front == Q.rear == 0$。

  • 入队：队尾指针进一：$Q.rear = (Q.rear + 1) \% MaxSize$。

  • 出队：队首指针进一：$Q.front = (Q.front + 1) \% MaxSize$。

  • 队列长度：$(Q.rear + MaxSize - Q.front) \% MaxSize$。

那么循环队列判空或判满怎么办呢？如果还是采用顺序队列的$Q.front == Q.rear$，那么在这样一种情况：入队速度远快于出队速度时，$rear$就会追上$front$。此时也有$Q.front == Q.rear$，但队列是满的。所以，仅凭$Q.front == Q.rear$无法判断队列空还是满。

所以为了解决这一问题，我们通常采用下面三个方法：

  • 牺牲一个存储单元（这个方法最常用）：入队时少用一个存储单元存数据，约定以“队尾指针的下一位置为队首”作为队满标志。即：

    • 队满条件：$(Q.rear + 1) \% MaxSize == Q.front$。

    • 队空条件：$Q.front == Q.rear$。

    • 队列中元素个数：$(Q.rear - Q.front + MaxSize) \% MaxSize$。

  • 增设$size$成员记录当前元素个数。若入队成功，则$size++$，出队成功则$size–$。相应的，队空条件就是$Q.size == 0$。队满条件就是$Q.size == MaxSize$。

  • 增设$tag$标记：

    • 出队后置$tag = 0$，若此时$Q.front == Q.rear$，则队空。

    • 入队后置$tag = 1$，若此时$Q.front == Q.rear$，则队满。

双端队列

双端队列允许在队列两端进行插入和删除操作，一般我们管左端叫做前端，右端叫做后端（不是软件系统开发的那个前后端！！！）

双端队列还有以下变体：

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

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

双端队列和栈一样最喜欢出选择题和简答题考判断序列的合法性。

队列的应用

队列在层次遍历中的应用

二叉树的层次遍历：按照每一层从左往右的顺序输出二叉树的所有节点。过程如下：

1) 将根节点入队。

2) 若队列为空（表示所有节点均已处理），则遍历结束，否则执行第三步

3) 取出队首节点并访问，若其存在左孩子，则将其左孩子入队；若其存在右孩子，则将其右孩子入队。

该过程用$\text{C++}$ $\mathrm{STL}$实现如下。二叉树本身的定义、存储和遍历细节详见《树与二叉树》，这里只保留层次遍历需要的最小结构。

// 代码里我只添加了一些必要的函数和结构，因为二叉树是第五章的内容，所以现在我们先不涉及
#include <iostream>
#include <queue>
using namespace std;

// 二叉树结点类
class Node 
{
private:
	int data;
	Node* left;
	Node* right;
public:
	Node(int val) : data(val), left(nullptr), right(nullptr) {}
	int getData() const { return data; }
	Node* getLeft() const { return left; }
	Node* getRight() const { return right; }
	void setLeft(Node* node) { left = node; }
	void setRight(Node* node) { right = node; }
};

// 二叉树类
class BinaryTree 
{
private:
	Node* root;
public:
	BinaryTree() : root(nullptr) {};
	// 其他相关操作，如析构函数等。
};

// 二叉树层次遍历函数
void LevelOrder(BinaryTree* tree) 
{
	if (tree->getRoot() == nullptr) 
	{
		return;
	}
	queue<Node*> q;
	q.push(tree->getRoot());	// 根节点入队
	while (!q.empty()) 
	{
		Node* current = q.front();	// 获取队首元素
		q.pop();	// 队首元素出队
		cout << current->getData() << " ";	// 访问当前节点
		if (current->getLeft() != nullptr) 
		{
			q.push(current->getLeft());	// 左子节点入队
		}
		if (current->getRight() != nullptr) 
		{
			q.push(current->getRight());	// 右子节点入队
		}
	}
}

队列在计算机中的作用

下面的内容就比较偏硬件了，事实上，你更有可能在《计算机组成原理》或《操作系统》中看到下面的内容的详细阐述。

  • 队列作为缓冲区缓解主机和外部设备$I/O$速度不匹配的问题：主机输出数据的速度远快于以打印机为例的外部设备处理数据的速度，如果主机直接将数据发送给外部设备，会导致数据丢失和打印错误。为此，通常设置一个打印数据缓冲区来缓解这一问题。具体来说：主机将待打印的数据依次写入缓冲区，当缓冲区满时，主机暂停输出并转向其他任务；打印机则从缓冲区中按先进先出的方式逐个取出数据并打印；打印完成后，打印机向主机发送中断请求，让主机再次向缓冲区写入新的打印数据。

是不是发现了什么？没错，缓冲区就是一个队列。

  • 队列作为多用户多任务调度序列缓解$\mathrm{CPU}$资源竞争问题：在一个多用户系统中，为保证每一个用户感觉在独占$\mathrm{CPU}$，操作系统将每个发送到$\mathrm{CPU}$的任务按照特定顺序进行排序。其中一个排序方法就是按照请求发送的时间进行排序形成一个请求队列。$\mathrm{CPU}$每次取队首任务执行，此时队首任务从就绪态转变为运行态。当任务执行完毕或者$\mathrm{CPU}$当前时间片耗尽或者任务所需的某个非$\mathrm{CPU}$资源缺失时，操作系统将其出队，并把$\mathrm{CPU}$分配给下一个队首任务。

数组和特殊矩阵

数组

很多道友们在学习$C$语言的时候就已经接触过数组了。没错，数组是一个很常用的数据组织形式。不过，编程的时候，很多道友都肯定犯过这样一个错误：

int n = 0;
scanf("%d",&n);
int a[n];
// 试图通过用户输入来指定数组长度

这种代码肯定会报错，连编译都不通过。这是为什么呢？

  • 因为$C$语言中，普通数组属于静态变量，你是不能给他一个未知的变量去给他动态指定长度的。所以我们也管上面这种数组叫静态数组。

但是那有的人想问了：“啊那编程的时候我们该怎么办呢？”

解决方法也有两个：

1) 按照题目要求（比方说，题目规定数据规模不超过$10$或$100$）指定数组的最大长度，如$int a[10]$或$int b[100]$。

2) 使用动态数组。

那么什么是动态数组呢？请各位继续往下看。

动态数组

动态数组的组织形式有三种，第一种是利用$malloc$去动态申请一块内存空间：

#include<malloc.h>
int* a = (int*)malloc(n * sizeof(int));
// 可正常使用a[0]到a[n - 1]，与静态数组使用方法相同。
free(a);

  • 只分配一块原始内存，返回$void*$，需要强制类型转换。

  • 不记录长度，你必须自己用变量保存$n$。

  • 内存大小在分配时固定，想扩容必须手动$realloc$。

  • 需要手动$free$，否则会导致内存泄漏。

第二种是通过$new$来动态申请内存空间：

int* a = new int[n];
// 也是可以使用a[0]到a[n - 1]，与静态数组使用方法相同。
delete[]a;

  • 也是只分配一块原始内存，但不需要强制类型转换。

  • 如果想扩容的话，需要手动$new$一个更大的数组，然后把原数组拷贝过去，再销毁原数组。

第三种就是$STL$提供的动态数组了。$STL$中$vector$的相应操作为：

#include<vector>
using namespace std;

vector<int> v;              // 空 vector
vector<int> v(n);           // 长度为 n，元素默认初始化为 0
vector<int> v(n, val);      // 长度为 n，所有元素初始化为 val
vector<int> v2(v);          // 拷贝构造，将v的内容拷贝到v2中
vector<int> v3 = { 1, 2, 3 }; // 列表初始化

v.push_back(x);        // 尾部添加元素 x，均摊 O(1)

v.pop_back();          // 删除尾部元素，O(1)，不返回被删元素

v.size();              // 返回元素个数，O(1)

v.empty();             // 判断是否为空，O(1)

v.clear();             // 清空所有元素，O(n)

v.front();             // 返回第一个元素，O(1)

v.back();              // 返回最后一个元素，O(1)

v[i];                  // 下标访问，O(1)，不检查越界

v.at(i);               // 下标访问，O(1)，越界会抛 out_of_range 异常

v.begin();             // 返回指向首元素的迭代器

v.end();               // 返回指向尾后位置的迭代器

v.insert(pos, x);      // 在迭代器 pos 前插入 x，O(n)

v.erase(pos);          // 删除迭代器 pos 处元素，O(n)

v.erase(first, last);  // 删除区间 [first, last) 内元素，O(n)

v.resize(n);           // 改变大小为 n，多出的元素默认初始化，O(n)

v.resize(n, val);      // 改变大小为 n，多出的元素初始化为 val

v.reserve(n);          // 预分配容量至少为 n，不改变 size，O(n)

v.capacity();          // 返回当前容量，就是当前分配的内存能容纳的元素个数，O(1)

v.swap(v2);            // 交换两个 vector 的内容，O(1)

所以一般编程里面，我们要么使用静态数组，要么使用$vector$。其实理论上这两个是可以互换的啦，所以具体在编程的时候使用什么，就看各位道友的喜好了。

数组的存储结构

选择题会考一维数组中某个元素的起始地址和二维数组的某个元素的起始地址（分按行优先存储还是按列优先存储）。

按行优先存储：数组中的元素先按行排满，然后才开始填充下一行。

按列优先存储：数组中的元素先按列排满，然后才开始填充下一列。

  • 例如求一维数组$A[n]$中元素$A[i]$的起始地址，设$A[0]$的起始地址为$LOC(a_0)$，每一个元素占$L$个存储单元。则$LOC(A_i) = LOC(A_0) + iL$。

  • 二维数组$A[m][n]$按行优先存储，其他题设条件和上面一样。那么元素$A[i][j]$的起始地址就是：$LOC(A_{ij}) = LOC(A_{00}) + (i * n + j) * L$。（第$i$行说明它前面已经有$i$行（$0$到$i - 1$）填满，每行$n$个元素）

  • 二维数组$A[m][n]$按列优先存储，其他题设条件和上面一样。那么元素$A[i][j]$的起始地址就是：$LOC(A_{ij}) = LOC(A_{00}) + (j * m + i) * L$。（第$j$列说明它前面已经有$j$列（$0$到$j - 1$）填满，每列$m$个元素）

特殊矩阵

在开始介绍特殊矩阵，我想先给大家讲一下矩阵这个东西。我相信准备考研的大家都知道什么是矩阵。在程序设计中，一般都用一个二维数组来存储矩阵。所以要存储一个$m$行$n$列的矩阵，就需要$O(mn)$的空间复杂度。

但什么是特殊矩阵呢？这里面说的特殊矩阵是线性代数里所有特殊矩阵的真子集。即具有大量相同元素或零元素，且这些元素分布具有规律性的矩阵。常见的特殊矩阵有对称矩阵，三角矩阵，对角矩阵，稀疏矩阵。而像线性代数里常用的范德蒙德行列式对应的矩阵什么的不算。

为了在存储上尽可能节省空间，特殊矩阵我们一般采用压缩方式存储，即通过分析矩阵中相同元素的分布规律，仅存储一份实际数据，其余的可通过下标映射访问。

对称矩阵：$A$的上三角区和下三角区完全对称，所以存储的时候可将$n$阶对称矩阵$A$压缩存储在一维数组$B[n * (n + 1) / 2]$中，通常仅存放下三角部分和主对角线。对于元素$a_{i, j}$，其在数组$B$中的位置由其前方元素的个数决定（不考虑上三角区）。所以元素$a_{i, j}$在数组$B$中的下标$k$该这样计算：

格式如下（$a_{i, j} = a_{j, i}$，以主对角线为轴上下三角区完全对称）：

$$ \begin{pmatrix} a_{11} & a_{12} & a_{13} & \cdots & a_{1n}\\\\ a_{12} & a_{22} & a_{23} & \cdots & a_{2n}\\\\ a_{13} & a_{23} & a_{33} & \cdots & a_{3n}\\\\ \vdots & \vdots & \vdots & \ddots & \vdots\\\\ a_{1n} & a_{2n} & a_{3n} & \cdots & a_{nn} \end{pmatrix} $$
$$ k = \begin{cases} 1 + 2 + \cdots + (i - 1) + (j - 1) = \frac{i(i - 1)}{2} + j - 1, i \ge j\\\\ 1 + 2 + \cdots + (j - 1) + (i - 1) = \frac{j(j - 1)}{2} + i - 1, i \lt j \end{cases} $$

三角矩阵：上三角矩阵和下三角矩阵唯一的区别在于同一常量元素所在的三角区位置不一样。下三角矩阵的上三角区都是同一常量，上三角矩阵的下三角区都是同一常量。三角矩阵的存储思想和对称矩阵类似，但是需要额外存储该常量一次（一般放在一维数组的末尾）。所以将三角矩阵$A$压缩存储在$B[n(n + 1) / 2 + 1]$中。对于元素$a_{i, j}$，其在数组$B$的下标为：

格式如下（$c$为公共常量，三角区其余位置均为此常量）：

$$ \begin{pmatrix} a_{11} & c & c & \cdots & c\\\\ a_{21} & a_{22} & c & \cdots & c\\\\ a_{31} & a_{32} & a_{33} & \cdots & c\\\\ \vdots & \vdots & \vdots & \ddots & \vdots\\\\ a_{n1} & a_{n2} & a_{n3} & \cdots & a_{nn} \end{pmatrix} \quad (\text{下三角矩阵}) $$
$$ \begin{pmatrix} a_{11} & a_{12} & a_{13} & \cdots & a_{1n}\\\\ c & a_{22} & a_{23} & \cdots & a_{2n}\\\\ c & c & a_{33} & \cdots & a_{3n}\\\\ \vdots & \vdots & \vdots & \ddots & \vdots\\\\ c & c & c & \cdots & a_{nn} \end{pmatrix} \quad (\text{上三角矩阵}) $$
  • 下三角矩阵：
$$ k = \begin{cases} \frac{i(i - 1)}{2} + j - 1, i \ge j\\\\ \frac{n(n + 1)}{2}, i \lt j \end{cases} $$
  • 上三角矩阵：
$$ k = \begin{cases} \frac{(i - 1)(2n - i + 2)}{2} + (j - i), i \le j\\\\ \frac{n(n + 1)}{2}, i \gt j \end{cases} $$

三对角矩阵：$n$阶矩阵$A$中任意元素$a_{i, j}$，在$\lvert i - j \rvert \gt 1$时均有$a_{i, j} = 0 (1 \le i, j \le n)$，则称为三对角矩阵。说人话就是以主对角线为中心，向外扩散一条线之后的范围内的三条对角线上存在非零元素，其他对角线上元素全是$0$。格式如下：

$$ \begin{pmatrix} a_1 & b_1 & 0 & \cdots & 0\\\\ c_1 & a_2 & b_2 & \cdots & 0\\\\ 0 & c_2 & a_3 & \cdots & 0\\\\ \vdots & \vdots & \vdots & \ddots & \vdots\\\\ 0 & 0 & \cdots & c_{n - 1} & a_n \end{pmatrix} $$

其中三条对角线上的非零元素个数为$n + (n - 1) + (n - 1) = 3n - 2$，所以可将其按行优先压缩存储到一维数组$B[0 .. 3n - 3]$中，只存这$3n - 2$个非零元素。位于三对角线上的元素（即$\lvert i - j\rvert \le 1$）在$B$中的下标为：

$$ k = 2i + j - 3, \quad (0 \le k \le 3n - 3, \ 1 \le i, j \le n) $$

当$\lvert i - j\rvert \gt 1$时，$a_{i, j} = 0$，压缩存储中直接跳过，不占空间。

稀疏矩阵：当矩阵中非零元素的个数远小于矩阵元素总数（一般规定非零元素占比不超过约$5\%$）时，称其为稀疏矩阵。若仍用二维数组存储，需要$O(mn)$的空间，对稀疏矩阵来说太浪费，所以一般用下面的两种方法压缩存储。

  • 三元组表（顺序存储）：用一个线性表只记录非零元素，每个非零元素对应一个三元组$(i, j, v)$，分别表示行号、列号和值；表头再用三个变量记录矩阵的总行数$mu$、总列数$nu$和非零元素个数$tu$。例如矩阵
$$ \begin{pmatrix} 0 & 0 & 5\\\\ 0 & 7 & 0\\\\ 0 & 0 & 0 \end{pmatrix} $$

的三元组表为（按行优先：先按行号递增，同行按列号递增）：

$i$（行） $j$（列） $v$（值）
$1$ $3$ $5$
$2$ $2$ $7$

在这种存储方式下定位某个元素需要顺序扫描三元组表，时间复杂度为$O(tu)$。

  • 十字链表法（链式存储）：每一个非零元素用一个结点表示，结点中除三元组$(i, j, v)$外还有两个指针——行指针和列指针，分别指向同一行的下一个非零元素和同一列的下一个非零元素。于是同一行的非零元素串成一条行链表，同一列的非零元素串成一条列链表，两种链表纵横交叉成一张网，故得名“十字链表”。它比三元组表更适合非零元素个数会频繁变化（如插入删除、矩阵转置）的场合。