多维数组与特殊矩阵的压缩存储
数组是由类型相同的数据元素构成的有序集合,每个数据元素称为一个数组元素,每个元素受(n&=1)个线性关系的的约束,每个元素在n个线性关系中的序号i1,i2...in称为该元素的下标,并称该数组为n维数组.
数组的存储结构与寻址
由于数组一般要求实现随机存取,所以一般采用顺序存储结构.由于内存单元是一维,而多维数组是多维的结构，所以采用顺序存储结构存储数组首先需要将多维结构映射到一维结构中.二维数组的每个元素含有两个下标,需要将其映射为一维关系。通常有两种映射方式:按行存储和按列存储.
C++是按行优先存储的.
设二维数组行下标和列下标分别为闭区间[L1, H1],[L2,H2];则按行优先存储的任意一元素Aij的地址可以用以下公式计算:LOC(Aij) = LOC(aL1L2) + ((i-L1)*(H2-L2+1) + (J-L2))*c
行下标[0,2] 列下标[0,3]
根据上述公式a[2][3] = a + 2*4 + 3
按行存储的基本思想是,最右边的下标最先变化.
二维数组用寻址方式展示:
int a[][4] = {{1,2,3,4},{5,6,7,8},{4,5,6,7}};
for (int i = 0; i&3; i++) // 行下标
for (int j = 0; j&4; j++) // 列下标
printf(&%d &,
*((int*)a + i*4 + j));
printf(&\r\n&);
特殊矩阵的压缩存储:
1.对称矩阵:在一个n阶方阵中,有Aij = Aji(i&=0, j&=n-1)
{ 3 6 4 7 8
对称矩阵关于主对角线对称,因此只需要存储下三角(或上三角)部分即可.原来需要n*n个存储单元,
现在仅需要n*(n+1)/2个存储单元，一个S[n(n+1)/2]个元素的一维数组存储,aij存储在S[K]中,对于
下三角元素,i&=j有如下对应关系k = i*(i+1)/2+j;对于上三角元素,有如下对应关系:k = j*(j+1)/2+i
可以想象成求aij元素在下三角中的第几个元素,先求i*(i+1)/2(三角形面积),然后加上j.
// 将一个对称矩阵压缩存储,并输出存储后的数组
// 入参:int** array 要压缩的对称矩阵
// n 对称矩阵阶数
// Compress 压缩后的数组
void CompressSymMatrix(int** array, int n, int Compress[])
int k = 0;
for(int i = 0; i解压:// 将一个压缩矩阵解压成对称矩阵
// 入参:Compress[] 压缩的矩阵
// n n阶对称阵
// int** array 解压后的二维数组
void DeCompressSymMatrix(int Compress[], int n, int** array)
for (int i = 0; ij)
k = (i*(i+1))/2 +
k = (j*(j+1))/2 +
*((int*)array + i*n + j) = Compress[k];
int SymArray[5][5] = {{3,6,4,7,8},{6,2,8,4,2},{4,8,1,6,9},{7,4,6,0,5},{8,2,9,5,7}};
printf(&对称矩阵:\r\n&);
for (int i = 0; i&5; i++)
for (int j = 0; j&5; j++)
printf(&%d &, SymArray[i][j]);
printf(&\r\n&);
printf(&将其压缩后:\r\n&);
int Compress[15] = {0};
CompressSymMatrix((int**)SymArray, 5, Compress);
for (int i = 0; i&15; i++)
printf(&%d &, Compress[i]);
printf(&将其解压后:\r\n&);
int DeArray[5][5] = {0};
DeCompressSymMatrix(Compress, 5, (int**)DeArray);
for (int i = 0; i&5; i++)
for (int j = 0; j&5; j++)
printf(&%d &, DeArray[i][j]);
printf(&\r\n&);
2.三角矩阵
{3,c,c,c,c,
6,2,c,c,c,
4,8,1,c,c,
7,4,6,0,c,
8,2,9,5,7,
下三角矩阵与对称矩阵存储类似,只是需要多存储一个常数.需要存储空间为n(n+1)/2 + 1
aij与k的对应关系为:
i&=j k = i*(i+1)/2 +
i 上三角矩阵:
与下三角矩阵存储类似:
aij与k的对应关系为:
i&=j k = i*(2n-i+1)/2+j-i
i&j k = n*(n+1)/2
void CompressTriangle(int** array, int n, int compress[], bool bUp = true)
int m = 0;
for (int i = 0; i= j) )
compress[m++] = *((int*)array + i*n + j);
if ((!bUp) && (i&=j))
compress[m++] = *((int*)array + i*n + j);
compress[(n*(n+1))/2] = *((int*)array + 1);
compress[(n*(n+1))/2] = *((int*)array + n);
// 将压缩的下三角矩阵解压出来
// int** array 解压后的三角矩阵
// n N阶矩阵
// compress[] 压缩的一维数组
// bUp = true 上三角矩阵 bUp = false 下三角矩阵
void DeCompressTriangle(int** array, int n, int compress[], bool bUp = true)
int m = (n*(n+1))/2;
for (int i = 0; i= j)
k = (i*(i+1))/2 +
k = i*(2*n-i+1)/2 + j -
*((int*)array + i*n + j) = compress[k];
int UpTriArray[][5] = {{3,1,1,1,1}, {6,2,1,1,1},{4,8,1,1,1},{7,4,6,0,1},{8,2,9,5,7}};
int DownTriArray[][5] = {{3,4,8,1,0},{1,2,9,4,6},{1,1,1,5,7},{1,1,1,0,8},{1,1,1,1,7}};
printf(&下三角矩阵:\r\n&);
for (int i = 0; i&5; i++)
for (int j = 0; j&5; j++)
printf(&%d &, DownTriArray[i][j]);
printf(&\r\n&);
printf(&将其压缩后:\r\n&);
int Compress[16] = {0};
CompressTriangle((int**)DownTriArray, 5, Compress, false);
for (int i = 0; i&16; i++)
printf(&%d &, Compress[i]);
printf(&将其解压后:\r\n&);
int DeArray[5][5] = {0};
DeCompressTriangle((int**)DeArray,
5, Compress, false);
for (int i = 0; i&5; i++)
for (int j = 0; j&5; j++)
printf(&%d &, DeArray[i][j]);
printf(&\r\n&);
上三角矩阵的测试稍微改一下上面部分即可.
3.对角矩阵:
对角矩阵:在对角矩阵中,所有非0元素都集中在以主对角线为中心的带状区域中,除了主对角线和它的上下方若干条对角
线的元素外,其他元素都为0.
{2,1,0,0,0,
9,3,4,0,0,
0,7,5,3,0,
0,0,5,4,2,
0,0,0,1,1}
将一个m*n的w对角矩阵(w是占有非0元素对角线的个数,也成为带宽).压缩到m行,w列的二维数组B中.则Aij与Bts的映射关系
为:t = s = j - i + 1
// 入参: int** array 要压缩的对角矩阵
// m,n,w M行N列带宽w
// outArray 压缩后的矩阵
void CompressDiagonalMartix(int** array, int m, int n, int w, int** outArray)
int t = 0;
int s = 0;
for (int i = 0; ii) && ((j - i) & ((w-1)/2 + 1)) || (i&j) && ((i-j) & ((w-1)/2 + 1)))
*((int*)array + i*n + j) = *((int*)outArray + t*w + s);
*((int*)array + i*n + j)
int DiagonalArray[5][5] = {{1,2,0,0,0},{3,4,5,0,0},{0,6,7,8,0},{0,0,9,3,1},{0,0,0,2,3}};
int CompressDiagonalArray[5][3] = {0};
printf(&对角矩阵:\r\n&);
for (int i = 0; i&5; i++)
for (int j = 0; j&5; j++)
printf(&%d &, DiagonalArray[i][j]);
printf(&\r\n&);
printf(&将其压缩后:\r\n&);
//int Compress[16] = {0};
CompressDiagonalMartix((int**)DiagonalArray, 5, 5, 3, (int**)CompressDiagonalArray);
for (int i = 0; i&5; i++)
for (int j = 0; j&3; j++)
printf(&%d &, CompressDiagonalArray[i][j]);
printf(&\r\n&);
printf(&将其解压后:\r\n&);
int DeArray[5][5] = {0};
DeCompressDiagonalMartix((int**)DeArray,
5, 5, 3, (int**)CompressDiagonalArray);
for (int i = 0; i&5; i++)
for (int j = 0; j&5; j++)
printf(&%d &, DeArray[i][j]);
printf(&\r\n&);
对角矩阵另一种存储方法是压缩到一维数组中,按行存储非0元素,k = 2i+j;
4. 稀疏矩阵的压缩存储
稀疏矩阵的压缩存储
稀疏矩阵是0元素居多的矩阵.
1.对于稀疏矩阵,0元素分布没有规律.仅存储非0元素是没有用的,还要存储元素的行号和列号.
即每个非0元素可以表示成如下三元组
struct element
三元组顺序表,为了确定一个唯一稀疏矩阵,还要存储稀疏矩阵的行数,列数和非0元素的个数
const int MaxTerm = 256;
struct SparseMatrix
element data[MaxTerm];
int rowC //
int colC //
int notZeroC
// 稀疏矩阵压缩存储
// 入参:int** array要压缩的稀疏矩阵
// m,nM行N列
// 出参:SparseMatrix& 输出存储的结构
void CompressSpareMatrix(int** array, int m, int n, SparseMatrix& spareMatrix)
// 对稀疏矩阵非0元素存储
int nCount = 0;
for (int row = 0; row & row++)
for (int col = 0; col & col++)
int value = *((int*)array + row*n + col);
if (value != 0)
spareMatrix.data[nCount].data =
spareMatrix.data[nCount].row =
spareMatrix.data[nCount].col =
spareMatrix.notZeroCount = nC
spareMatrix.rowCount =
spareMatrix.colCount =
// 稀疏矩阵对三元组顺序表的转置
// 1)直接取,顺序存
// 描述:依次从A矩阵寻找0,1..n-1列的三元组,找到之后交换行列位置存入B中.
void Trans1(SparseMatrix& sparseMatrixA, SparseMatrix& sparseMatrixB)
sparseMatrixB.colCount = sparseMatrixA.rowC
sparseMatrixB.rowCount = sparseMatrixA.colC
sparseMatrixB.notZeroCount = sparseMatrixA.notZeroC
int pb = 0;
if (sparseMatrixA.notZeroCount & 0)
for (int col = 0; col & sparseMatrixA.colC col++)
for (int notZero = 0; notZero<sparsematrixa. .col="sparseMatrixA.data[notZero]." .data="sparseMatrixA.data[notZero]." .> 问题详情
设n阶方阵是一个上三角矩阵，则需存储的元素个数为（)。A．nB．n×nC．n×n／2D．n（n+1)／2
悬赏：0&答案豆
提问人：匿名网友
发布时间：
设n阶方阵是一个上三角矩阵，则需存储的元素个数为()。A．nB．n×nC．n×n／2D．n(n+1)／2请帮忙给出正确答案和分析，谢谢！
您可能感兴趣的试题
1在二叉树的顺序存储中，每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系，因此可与三叉链表对应。若某二叉树共有n个结点，采用三叉链表存储时，每个结点的数据域需要d个字节，每个指针域占用4个字节，若采用顺序存储，最后一个结点下标为k(起始下标为1)，那么(&&)时采用顺序存储更节省空间。A.d＜12n／(k-n)B.d＞12n／(k-n)C.d＜12n／(k+n)D.d＞12n／(k+n)2中缀表达式A-(B+C／D)*E的后缀形式是(&&)。A.AB-C+D／E*B.ABC+D／-E*C.ABCD／E*+-D.ABCD／+E*-3有m个叶子结点的哈夫曼树所具有的结点数为(&&)。A.mB.m+1C.2mD.2m-14简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图G有n个结点，其邻接矩阵为A[1…n，1…n]，且压缩存储在B[1…k]，则k的值至少为(&&)。A.n(n+1)／2B.n2／2C.(n-1)(n+1)／2D.n(n-1)／2
我有更好的答案
请先输入下方的验证码查看最佳答案
图形验证：
验证码提交中……
每天只需0.4元
选择支付方式
支付宝付款
郑重提醒：支付后，系统自动为您完成注册
请使用微信扫码支付(元)
支付后，系统自动为您完成注册
遇到问题请联系在线客服QQ：
恭喜你被选中为
扫一扫-免费查看答案！
请您不要关闭此页面,支付完成后点击支付完成按钮
遇到问题请联系在线客服QQ：
恭喜您！升级VIP会员成功
提示：请截图保存您的账号信息，以方便日后登录使用。
常用邮箱：
用于找回密码
确认密码：特殊矩阵压缩存储特殊矩阵压缩存储冲刺科技百家号矩阵研究比较多，矩阵结构用一个二维数组来表示比较恰当。但有些情况下，有些高阶矩阵中，阶次比较高，数据量大，非零元素很少，若仍采用二维数据存放，就会有很多存储单元都放0，不仅造成存储空间浪费，运算也不是很方便。就希望只存储部分有效元素。还有一些矩阵元素分布有一定规律，如三角矩阵／对称矩阵／带状矩阵等，那么根据规律，存储部分元素，提高空间利用率。此时需要对矩阵进行压缩，压缩原则是：对有规律的元素和值相同的元素只分配一个存储空间，对零元素不分配空间。三角矩阵：下三角矩阵、上三角矩阵、对称矩阵对于一个n阶矩阵A，若当i&j时，有aij=0或aij=c（c为常数），则称此矩阵为下三角矩阵；若当i&j时，有aij=0或aij=c（c为常数），则称此矩阵为上三角矩阵；若矩阵中所有元素均满足aij=aji，则为对称矩阵。如图，为下三角矩阵：对于下三角矩阵，只需存储下三角的非零元素。若以行序为主序进行存储，得到的序列是：a00,a10,a11,a20,……，an-1,0,an-1,1,……，an-1,n-1由于下三角矩阵的元素个数为n(n+1)/2，即第0行：1个第1行：2个第2行：3个……第n-1行：n个共有1+2+3+……+n=n(n+1)个，所以可将三角矩阵压缩到一个大小为n(n+1)/2的一维数组中，如图：设每个数据元素占size个存储单元，下三角矩阵中任意元素aij在一维数据中的存储位置可通过下计算：也就是，数组C中数据元素C[k]的下标为k，则k与下三角矩阵中数据元素aij的下标i，j之间的关系为：若上三角部分的一常数c，则数据的大小可设为C[n(n+1)/2+1]，其中C[n(n+1)/2]存放常数c。例如：一个下三角矩阵A，用一维数组C[15]对其进行压缩存储同理，对上三角矩阵，只需要存储上三角的非零元素，对于零元素不存储，同样可以将其压缩存储到一个大小为n(n+1)/2的一维数据中。若以行序为主序进行存储，得到序列是：a00,a01,a02,……，a0,n-1,a1,n-1,……，an-1,n-1其中元素aij(i&=j)在数据C中的存储位置为：k=i(2n-i+1)/2+j-i(i&=j);对于对称矩阵，则可以只存储上三角部分，也可只存储下三角部分，将其压缩存储到一个大小为n(n+1)/2的一维数组中。若只存储下三角部分，那么元素aij在数据C的存储位置为：k=i(i+1)/2+j(i&=j);k=j(j+1)/2+i(i&=j).以上，压缩矩阵就到这里～本文由百家号作者上传并发布，百家号仅提供信息发布平台。文章仅代表作者个人观点，不代表百度立场。未经作者许可，不得转载。冲刺科技百家号最近更新：简介:科学是“无知”的局部解剖学作者最新文章相关文章没有更多推荐了，
不良信息举报
举报内容：
判断上三角矩阵
举报原因：
原文地址：
原因补充：
最多只允许输入30个字
加入CSDN，享受更精准的内容推荐，与500万程序员共同成长！查看: 1452|回复: 8
求助帖-关于矩阵csr存储格式，如何将CSR格式上三角扩展到C...
惯用编译器:Intel Visual Fortran for Linux
帖子主题精华
我现在有个问题，就是我现在有一个CSR格式存储的是上三角矩阵，是一个全局矩阵的上三角，如何转换成CSR存储的全矩阵？？？请指教
UID性别保密
F 币1391 元
贡献939 点
惯用编译器:Intel Visual Fortran for Windows
帖子主题精华
F 币1391 元
贡献939 点
本帖最后由 li913 于
10:20 编辑
CSR用于存储稀疏矩阵，非零元素个数少于总个数的一半以上才能节省内存。没听过“”CSR存储的全矩阵“”。如果你只是想转为全矩阵，百度一下CSR就是。
F 币612 元
贡献279 点
惯用编译器:GFortran for Windows
帖子主题精华
F 币612 元
贡献279 点
他的意思，是不是说，这是一个对称阵，或者是一个厄米共轭矩阵。因此，只存储了其中一半。
（但是依然是稀疏的）
现在想要还原？
UID性别保密
F 币2921 元
贡献1741 点
惯用编译器:GFortran for Windows
帖子主题精华
F 币2921 元
贡献1741 点
ivf专业版自带转换程序
Auxiliary routines Matrix converters
mkl_?dnscsr
Converts a sparse matrix in uncompressed representation to CSR format (3-array variation) and vice versa.
mkl_?csrcoo
Converts a sparse matrix in CSR format (3-array variation) to coordinate format and vice versa.
mkl_?csrbsr
Converts a sparse matrix in CSR format to BSR format (3-array variations) and vice versa.
mkl_?csrcsc
Converts a sparse matrix in CSR format to CSC format and vice versa (3-array variations).
mkl_?csrdia
Converts a sparse matrix in CSR format (3-array variation) to diagonal format and vice versa.
mkl_?csrsky
Converts a sparse matrix in CSR format (3-array variation) to sky line format and vice versa.
惯用编译器:Intel Visual Fortran for Linux
帖子主题精华
他的意思，是不是说，这是一个对称阵，或者是一个厄米共轭矩阵。因此，只存储了其中一半。
（但是依然是稀 ...
是的，我就是这么个意思，，不知道有什么办法没有
惯用编译器:Intel Visual Fortran for Linux
帖子主题精华
CSR用于存储稀疏矩阵，非零元素个数少于总个数的一半以上才能节省内存。没听过“”CSR存储的全矩阵“”。如 ...
在MKL库中或者别的库都有关于矩阵格式之间函数转换的，我的意思就是原来的矩阵是个对称的复矩阵，但是现在是使用CSR格式只存储了上三角，我想还原成原来的对称矩阵，如果能还原成CSR存储的原对称矩阵就更好了
惯用编译器:Intel Visual Fortran for Linux
帖子主题精华
ivf专业版自带转换程序
https://software.intel.com/en-us/node/C4E66EF-D-8A43- ...
UID性别保密
F 币2921 元
贡献1741 点
惯用编译器:GFortran for Windows
帖子主题精华
F 币2921 元
贡献1741 点
在MKL库中或者别的库都有关于矩阵格式之间函数转换的，我的意思就是原来的矩阵是个对称的复矩阵，但是现 ...
师傅领进门，修行在自身
最无聊的办法，难度不是再开一个长度为2*NNZ-N的结构体存储行号、列号和元素数值，挨个赋值，碰到非对角元素，行号列号互换，元素值取共轭，最后得到coo形式的矩阵，接着想咋玩就咋玩呗。。。
UID性别保密
惯用编译器:Intel Visual Fortran for Windows
帖子主题精华
朋友能不能发我CSR存储上三角矩阵的程序参考一下
颁发给完成“有规有矩”任务的网友
颁发给论坛注册1年以上的网友
颁发给注册后积极发言的新人
颁发给发帖量超过一定数量的坛友
颁发给论坛热心帮助他人的网友
Powered by}