一、 数组
- 定义：
数组是由一组名字相同､下标不同的n(n≥1)个相同数据类型的数据元素a0,a1,a2,...,an-1构成的占用一块地址连续的内存单元的有限集合。从定义中可以看a.数组中的元素都是相同类型的，b.数组是有界限的，定义好后就不能改变了 - 数组的存储：
二维数组的数据元素受到行ROW和列COL的约束，每个元素对应一组下标（i，j），推广到n维数组，每个元素受到n个关系的约束，对应的下标为（j1, j2…jn），所以只要知道a.数组起始点的存储地址，b.维数及界限，c.每个元素占用的单元数，就可以求出任意元素的地址
二、 矩阵
由于矩阵是由m行n列组成，逻辑上与二维数组相同，所以通常用二维数组来做矩阵的存储结构｡
-
矩阵的压缩：
在某些矩阵中存在很多值相同的元素，或是0元素，为了节省存储空间，可以对这些矩阵进行压缩，若元素分部有一定规律的矩阵称为特殊矩阵（如：对称矩阵：以主对角线为轴对应相等的矩阵，aij = aji，三角矩阵：矩阵的上/下三角（不包括对角线）中的元素均为常数或0），若0元素比非零元素多，且分部没有规律，则称为稀疏矩阵（如，6*7的矩阵，42个单元只有8个非零元素）。
image.png
image.png
image.png
对于以上的矩阵，我们可以使用一个三元组（i, j, aij）来确定矩阵中的非零元素，上图的稀疏矩阵用三元组就可以表示为：((1,2,12), (1,3,9), (3,1,-3), (3,5,14), (4,3,24), (5,2,18), (6,1,15), (6,4,-7))
-
矩阵的运算：
A. 转置：
对于传统矩阵，转置是很简单的，一个m * n的矩阵M，转置为n*m的矩阵N，并且N(i, j) = M(j, i)。
image.png
而对于用三元组表示的稀疏矩阵，有两种算法：
image.png
一种简单的算法：M.data从头至尾扫描，第一次循环，将M.data中列号为1的三元组赋值到T.data中，第二次循环，将M.data中列号为2的三元组赋值到T.data中，以此类推，直至将M.data所有三元组赋值到T.data中，不难看出，这种算法时间复杂度高。
第二种快速转置方法
a. 原理：
上图的a.data是一个稀疏矩阵的三元表，转置后形成b.data一个新的三元表，这个新的三元表是按照行的顺序i进行排列的。观察a.data，j=1有2个、j=2有2个、j=3有2个、j=4有1个、j=6有1个。根据这些数据按照从小到大排列，j=1的项在新的三元表中应占据第1、2位，j=2的项在新的三元表中应占据第3、4位，j=3的项在新的三元表中应占据第5、6位，j=4应占据第7位，j=6应占据第8位。
转置的时候从第一项读起，取j的值， a.data这个三元表的第一项的j值为2，而j=1有2个，所以j=2应该占据第3、4位，接下来如果再取到一个j也是2，就放在第4位。因为j=2的项只有2个，所以第5位就不会是j=2的项，而应该存放j=3的。这样，读取每一项，都能在三元表中找到相应的位置，这就是稀疏矩阵快速转置的原理。
b. 算法实现：
image.png
在算法中需要两个变量，第一个num[col]用于记录原三元表中列数为col的项的数目，例如col=3时，num[col]=2，第二个cpot[col]用于记录原三元表中列数为col的项在新三元表中的首位置，例如col=3时，cpot[col]=5。
Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T) {
//初始化T，将矩阵M的行数mu，列数nu，以及非零元个数tu传给矩阵T
T.mu = M.nu; T.nu = M.mu; T.tu = M.tu;
if(T.tu) { //至少有一个非零元素
for(col = 1; col <= M.nu; ++col) {
num[col] = 0;//初始化num数组
}
for(t=1; t <= M.tu; ++t) {
//当原三元表M中某两项或多项的j值相同时，M.data[t].j的值是相等的
//因此这个循环完成后，比如说num[3]的值就是原三元表M列数为3的个数
++num[M.data[t].j];
}
//cpot[1]=1表示第一列的在新三元表T的第一个插入位置为1。
//cpot[0]是留给储存三元表行列数和非零元个数的
cpot[1] = 1;
for(col = 2; col < M.nu; ++col) {
//求除第一列外其它每一列的第一个非零元在新三元表T中的位置。
//第col列第一个非零元的位置为:
//第col-1列第一个非零元的位置加上第col-1列非零元的个数
cpot[col] = cpot[col - 1] + num[col - 1];
}
// M.tu的值是原三元表M的非零元个数，遍历原三元表M的每一项
for(p = 0; p < M.tu; ++p) {
//col=M.data[p].j得到循环当前项i的列数值j，
//赋给col，cpot[col]的值即为第col列的第一个插入位置，
//q=cpot[col]作用是用q来记录当前第col列的插入位置
col = M.data[p].j; q = cpot[col];
//将原三元表M的当前第p项的i，j值进行交换后给新三元表T的第q项，
//这样第p项就转置后正确的插入到新三元表的正确位置。
T.data[q].i = M.data[p].j; T.data[q].j = M.data[p].i;
//将原三元表M的第p项的非零元的值给新三元表的第q项。
//后一句++cpot[col]这个自增语句是使列数位col的项在新三元表的插入位置移动一位
//下次再碰到列数位col的列时，插入位置即为此次插入位置的下一个
T.data[q].e = M.data[p].e; ++cpot[col];
}
}
}
B. 相乘：
image.png
计算规则：第一个矩阵第一行的每个数字（2和1），各自乘以第二个矩阵第一列对应位置的数字（1和1），然后将乘积相加（ 2 x 1 + 1 x 1），得到结果矩阵左上角的那个值3
image.png
Q=M * N
image.png
算法：m1 * n1的M矩阵与m2 * n2的N矩阵相乘，采用三层循环
for(int i=0;i<m1;i++)
for(int j=0;j<n2;j++)
for(int k=0;k<n1;k++)
Q[i][j]+=M[i][k]*N[k][j];
但是对于用三元组表示的稀疏矩阵M，N的乘法，就不能用上面的公式了。从上面的算法可以看出，无论M[i][k]和N[k][j]的值是否为0，都要相乘一次，对于有很多0元素的稀疏矩阵来说，可以免去许多无效操作，只要找到a.data中j值和b.data中i值相等的元素相乘即可。
image.png
例如：a.data[1]表示的元素(1, 1, 3)只要和b.data[1]表示的元素(1, 2, 2)相乘，而a.data[2]表示的元素(1, 4, 5)则不需要和b中任何元素相乘，因为b.data中没有i=4的元素。
实现：
image.png
num[row]用于记录矩阵N，第row行非零元素的个数，rpos[row]表示矩阵N的第row行中第一个非零元素在b.data中的序号，rpos[row+1]-1表示第row行中最后一个非零元素在b.data中的序号，rpos的规则可以总结为rpos[1] = 1; rpos[row] = rpos[row-1] + num[row-1]。
IF a.tu*b.tu ≠ 0 THEN //保证两个相乘的矩阵不为空
{
rpos[brow]; //矩阵N中第brow行第1个非零元素在b.data的序号
//初始化存储相乘结果的矩阵Q的三元表c
c.mu = a.mu; c.nu = b.nu; c.tu = 0; p = 1;
REPEAT
crow = a.data[p].i; //从a.data表中获得当前处理的行号
FOR k = 1 TO c.nu DO ctemp[k] = 0;
WHILE (p≤a.tu) CAND (a.data[p].i = crow) DO {
brow = a.data[p].j; //brow表示b.data在矩阵N中的行号
//矩阵N在brow行上有几个非零元素，设为循环次数
FOR q = rpos[brow] TO rpos[brow + 1] DO {
k = b.data[q].j;
ctemp[k] = ctemp[k] + a.data[p].v * b.data[q].v;//相乘
}
p = p + 1;
}
FOR k = 1 TO c.nu DO
IF ctemp[k] ≠ 0 THEN {
c.tu = c.tu + 1;
c.data[c.tu] = (crow, k, ctemp[k]);
}
UNTIL p > a.tu;
}
网友评论