数组储存

数组一般采用顺序储存结构，因为存储单位元是一维的，而数组可以是多维的，如何用一组连续的储存单位来储存多维数组呢？以二维数组为例，可以按行序储存即先存第一列 ，再存第二列 ，......;

如果按行序，如何找到的存储位置

若表中大多数储存为空则浪费空间，需使用压缩存储的方法减少浪费

知识点概述

  1. 什么是压缩存储？

把多个相同的元素分配一个存储空间 ，元素为0的不分配空间。

  1. 什么样的矩阵能够压缩？

特殊矩阵，如：对称矩阵，对角矩阵 ，三角矩阵，稀疏矩阵等。

  1. 什么叫稀疏矩阵？

矩阵中非零元素的个数较少 ，一般认为非零元素个数小于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. 概念

集合是由一个或多个确定的元素所构成的整体集合中的元素。

并查集是一个维护集合的数据结构，它能高效支持集合的基本操作。

:建立一个新的集合，其仅有的成员（同时就是代表）是 。 由于各集合是分离的，要求没有在其它集合中出现

:合并两个集合

: 返回一个指向包含的集合的代表。

程序清单

（1）初始化 

1
for(i=1;i<=n;i++)father[i]=i;

（2）寻找根结点

1
2
3
4
int find(int x){
	if(fa[x] != x)fa[x]=find(fa[x]);
	return fa[x];
}

（3）合并集合

1
2
3
4
void unionn(int x ,int y){//合并
	x=find(x);y=find(y);
	fa[y]=x; 
}

（4）检查两个元素是否在一个集合中

1
2
3
4
5
6
bool chk(int x ,int y){
	x=find(x);
	y=find(y);
	if(x == y)return true;
	else return false;
}

经典例题

P1551亲戚

P1536村村通

P3958 [NOIP2017 提高组] 奶酪