[数据结构] 数组与特殊矩阵 - PlutoWan

偷懒，先写了数组，列表要画图，所以今天就先不写了

数组的定义

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

数组与线性表的关系：数组是线性表的推广。一维数组可视为一个线性表，二维数组可视为其元素是定长数组的线性表。因此，除结构的初始化和销毁外，数组只会有存取元素和修改元素的操作。

数组的顺序存储

以A[0…n−1]为例，其存储结构关系式为：

其中，L是每个数组元素所占的存储单元。

以二维数组为例。设二维数组的行下标与列下标的范围分别为[0,h1]和[0,h2]。

先行后列，先存储行号较小的元素，行号相等先存储列号较小的元素。存储结构关系式为：

例如对于数组A[2][3]。它按行优先方式在内存中的存储形式如下所示：

存储结构关系式为：

例如对于数组A[2][3]。它按行优先方式在内存中的存储形式如下所示：

特殊矩阵的压缩存储

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

特殊矩阵：指具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布具有一定规律性的矩阵；

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

对一个n阶矩阵A中的任意一个元素ai,j都有ai,j=aj,i(1≤i,j≤n)，则称其为对称矩阵

很显然，对于n阶对称矩阵，上三角区所有元素和下三角区的对应元素相同，采用二维数组存放，会造成大范围的空间浪费，因此我们把其存放在一维数组B[n(n+1)2]中。

比如只存放下三角部分的元素：

在数组B中，位于元素ai,j前的元素个数为：

第1行：1个（a1,1）

第2行：2个（a2,1,a2,2）

…

第i−1行：i−1个（ai−1,1,ai−1,2…,ai−1,i−1）

第i行：j−1个（ai,1,ai,2,…,ai,j−1）

因此，元素ai,j在数组B中的下标k=1+2+⋯+(i−1)+j−1=i(i−1)2+j−1

因此，元素下标之间对应关系如下：

下三角矩阵

上三角区为统一常量。元素下标之间的对应关系为：

上三角矩阵

与上文类似地，位于元素ai,j(i≤j)前面的元素个数为：

第1行：n个

第2行：n−1个

…

第i−1行：n−i+2个

第i行：j−1个

因此，元素ai,j在数组B中的下标k=n+(n−1)+⋯+(n−i+2)+(j−i+1)−1

因此，元素下标之间对应关系如下：

三对角矩阵

对n阶矩阵A中的任意元素ai,j，都有当|i−j|>1时，ai,j=0。

矩阵中非零元素的个数t，相对于矩阵元素的个数s来说非常少，即s>>t的矩阵称为稀疏矩阵

我们可以用对应的三元组线性表来存储稀疏矩阵，如下例：

对应的三元组为：

下面，上代码，可以实现稀疏矩阵的输入、输出，稀疏矩阵对应三元组的加法、乘法、转置：

#include <stdio.h>#include <stdlib.h>#define MAXSIZE 10000 typedef int ElemType; typedef struct { int i, j; ElemType e; }Triple; typedef struct { Triple data[MAXSIZE + 1]; int mu, nu, tu; //矩阵行数，列数和非0元个数 }TSMatrix; //输入稀疏矩阵数据void InPutM(TSMatrix& M) { printf("输入稀疏矩阵的 行数, 列数, 非0元个数 :\n"); scanf_s("%d %d %d", &M.nu, &M.mu, &M.tu); printf("输入矩阵非0元素的 所在行i, 所在列j, 值e:\n"); for (int k = 1; k <= M.tu; k++) { scanf_s("%d %d %d", &M.data[k].i, &M.data[k].j, &M.data[k].e); }} //打印稀疏矩阵三元组数据void PrintM(TSMatrix T) { printf(" %d %d %d\n", T.mu, T.nu, T.tu); printf(" ------------\n"); for (int k = 1; k <= T.tu; k++) { printf(" %d %d %d\n", T.data[k].i, T.data[k].j, T.data[k].e); }} //稀疏矩阵三元组加法void AddSMatrix(TSMatrix a, TSMatrix b, TSMatrix& c) { int i = 0, j = 0, k = 0; ElemType v; //用于计算和 if (a.mu != b.mu || a.nu != b.nu) //两矩阵无法相加 return; c.mu = a.mu; c.nu = a.nu; while (i < a.tu || j < b.tu) { //若行相等，看列 if (a.data[i + 1].i == b.data[j + 1].i) { //行相同时的第一种情况 if (a.data[i + 1].j < b.data[j + 1].j) { c.data[k + 1].i = a.data[i + 1].i; c.data[k + 1].j = a.data[i + 1].j; c.data[k + 1].e = a.data[i + 1].e; k++; i++; //前往下一个a中的非0元 } //行相同时的第二种情况 else if (a.data[i + 1].j > b.data[j + 1].j) { c.data[k + 1].i = b.data[j + 1].i; c.data[k + 1].j = b.data[j + 1].j; c.data[k + 1].e = b.data[j + 1].e; k++; j++; //前往下一个b中的非0元 } //行相同的第三种情况 else { v = a.data[i + 1].e + b.data[j + 1].e; if (v != 0) { c.data[k + 1].i = a.data[i + 1].i; c.data[k + 1].j = a.data[i + 1].j; c.data[k + 1].e = v; k++; } i++; j++; } } //若行不相同 的两种情况 else if (i == a.tu || a.data[i + 1].i > b.data[j + 1].i && j != b.tu) { c.data[k + 1].i = b.data[j + 1].i; c.data[k + 1].j = b.data[j + 1].j; c.data[k + 1].e = b.data[j + 1].e; k++; j++; //前往下一个b的非0元 } else if (j == b.tu || a.data[i + 1].i < b.data[j + 1].i && i != a.tu) { c.data[k + 1].i = a.data[i + 1].i; c.data[k + 1].j = a.data[i + 1].j; c.data[k + 1].e = a.data[i + 1].e; k++; i++; //前往下一个a的非0元 } } c.tu = k;} //乘法辅助函数int Getval(TSMatrix a, int i, int j) { int k = 1; while (k <= a.tu && (a.data[k].i != i || a.data[k].j != j)) k++; if (k <= a.tu) return a.data[k].e; else return 0;} //稀疏矩阵三元组乘法void MultSMatrix(TSMatrix a, TSMatrix b, TSMatrix& c) { int p = 0; ElemType s; if (a.nu != b.mu) return; for (int i = 1; i <= a.mu; i++) { for (int j = 1; j <= b.nu; j++) { s = 0; for (int k = 1; k <= a.nu; k++) s += Getval(a, i, k) * Getval(b, k, j); if (s != 0) { c.data[p + 1].i = i; c.data[p + 1].j = j; c.data[p + 1].e = s; p++; } } } c.mu = a.mu; c.nu = b.nu; c.tu = p;} //稀疏矩阵转置 （适用于 tu << mu × nu 的情况）void TransposeSMatrix(TSMatrix M, TSMatrix& T) { T.mu = M.nu; //T行数等于原矩阵列数 T.nu = M.mu; //T列数等于原矩阵行数 T.tu = M.tu; if (!T.tu) return; int q = 1; //从列数小的开始，一一对应赋值 for (int col = 1; col <= M.nu; ++col) { for (int p = 1; p <= M.tu; ++p) { if (M.data[p].j == col) { T.data[q].i = M.data[p].j; T.data[q].j = M.data[p].i; T.data[q].e = M.data[p].e; q++; } } }} //稀疏矩阵的快速转置算法int cpot[MAXSIZE + 1], num[MAXSIZE + 1]; //辅助数组 //cpot[col] 表示M中第col列第一个非0元在T.data中的位置//num[col] 表示M中第col列中非0元的个数void FastTransposeSMatrix(TSMatrix M, TSMatrix& T) { T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; if (!T.tu) return; for (int col = 1; col <= M.mu; col++) num[col] = 0; //初始化为0 for (int k = 1; k <= M.tu; k++) num[M.data[k].j]++; //记录M.data[k].j列中非0元个数 （简易哈希表） cpot[1] = 1; //初始化第一个非0元的序号 for (int col = 2; col <= M.mu; col++) //求第col列中第一个非零元在T.data中的序号 cpot[col] = cpot[col - 1] + num[col - 1]; for (int p = 1; p <= M.tu; p++) { int col = M.data[p].j; //此时M对应三元组中的非0元的所在列 int q = cpot[col]; //q为当前非0元的应当放置的序号位置 T.data[q].i = M.data[p].j; T.data[q].j = M.data[p].i; T.data[q].e = M.data[p].e; cpot[col]++; //cpot[col]++,对应下一个此列中非0元的序号 //cpot[col]最后一直加到等于cpot[col + 1],第col列也就不会有更多的非0元了 }} int main() { TSMatrix A, B, C, D; printf("输入稀疏矩阵A的三元组:\n"); InPutM(A); PrintM(A); printf("\n输入稀疏矩阵B的三元组:\n"); InPutM(B); PrintM(B); //printf("\n矩阵A与B相加得到矩阵C:\n"); //AddSMatrix(A, B, C); //PrintM(C); printf("\n矩阵A与B相乘得到矩阵D:\n"); MultSMatrix(A, B, D); PrintM(D); printf("\n"); system("pause"); system("cls"); TSMatrix M, T, FT; printf("————稀疏矩阵转置测试————\n\n"); InPutM(M); printf("\n稀疏矩阵转置前三元组: \n"); PrintM(M); printf("\n稀疏矩阵转置结果: \n"); TransposeSMatrix(M, T); PrintM(T); printf("\n稀疏矩阵的快速转置结果: \n"); FastTransposeSMatrix(M, FT); PrintM(FT);}