压缩储存

## 数组储存 #### $\color{White}jer$数组一般采用顺序储存结构，因为存储单位元是一维的，而数组可以是多维的，如何用一组连续的储存单位来储存多维数组呢？以二维数组为例，可以按行序储存即先存第一列 ，再存第二列 ，......; **如果按行序，如何找到$a_{ij}$的存储位置** $\begin{bmatrix}a_{00}\qquad a_{01}&\cdots\cdots&a_{0n-1}\\\vdots&\ddots&\vdots\\a_{m-1, 0} a_{m-1 ,1}&\cdots&a_{m-1 ,n-1}\end{bmatrix}$ **若表中大多数储存为空则浪费空间，需使用压缩存储的方法减少浪费** ### 知识点概述 1. **什么是压缩存储？** $\color{White}jer$把多个相同的元素分配一个存储空间 ，元素为0的不分配空间。 2. **什么样的矩阵能够压缩？** $\color{White}jer$特殊矩阵，如：对称矩阵，对角矩阵 ，三角矩阵，稀疏矩阵等。 3. **什么叫稀疏矩阵？** $\color{White}jer$矩阵中非零元素的个数较少 ，一般认为非零元素个数小于5%的矩阵为稀疏矩阵。 ### 稀疏矩阵的压缩储存 - **三元组法**  **M由{(1,2,12) ,(1,3,9) ,(3,1,-1) ,(3,6,14) ,(4,3,24) ,5,2,18) ,(6,1,15) ,(6,4,-7)}** **和矩阵(6，7)唯一确定。** - 十字链表法 **在十字链表中，矩阵的每一个非零元素用一个结点表示，该结点除了(row ,col ,value)以外，还有两个域：** - right：用于链接同一行中的下一个非零元素； - down：用以链接同一列中的下一个非零元素。 **十字链表中结点的结构示意图**   ## 集合—并查集 ### 1. 概念 **集合是由一个或多个确定的元素所构成的整体集合中的元素。** **并查集是一个维护集合的数据结构，它能高效支持集合的基本操作。** $(\mathfrak1)$ $\mathcal{Mack}(\mathcal{x})$ :建立一个新的集合，其仅有的成员（同时就是代表）是 $\mathcal{x}$ 。 由于各集合是分离的，要求$\mathcal{x}$没有在其它集合中出现 $(\mathfrak2)$ $\mathcal{Unionn}(\mathcal{x ,y})$ :合并两个集合 $(\mathfrak3)$ $\mathcal{Find}(\mathcal{x,y})$: 返回一个指向包含$\mathcal{x}$的集合的代表。 **程序清单$\color{White}jer\color{White}jer\color{White}jer$** **（1）初始化** ```cpp for(i=1;i<=n;i++)father[i]=i; ``` **（2）寻找根结点** ```cpp int find(int x){ if(fa[x] != x)fa[x]=find(fa[x]); return fa[x]; } ``` **（3）合并集合** ```cpp void unionn(int x ,int y){//合并 x=find(x);y=find(y); fa[y]=x; } ``` **（4）检查两个元素是否在一个集合中** ```cpp bool chk(int x ,int y){ x=find(x); y=find(y); if(x == y)return true; else return false; } ``` ### 经典例题 [P1551亲戚](https://www.luogu.com.cn/problem/P1551) [P1536村村通](https://www.luogu.com.cn/problem/P1536) [P3958 [NOIP2017 提高组] 奶酪](https://www.luogu.com.cn/problem/P3958)