对角矩阵
●定义
• 若一个n阶方阵A满足,其所有非零元素都集中在以对角线为中心的带状区域中,则称其为n阶对角矩阵
●术语
• b - 矩阵半带宽:主对角线上下方各有b条次对角线
• (2b+1)--矩阵的带宽
● 特征
• 对于半带宽为 b(0<=b<(n-1))的对角矩阵,其|i-j|<=b的元素 ai,j不为零,其余元素为零.
●存储策略:
•为了压缩存储空间,为0的空间,我们就不存储,或者判断出不是带状区域就输出 0
•找到对角矩阵坐标和一维数组的关系,进而对坐标进行换算,映射一维数组位序
•设计算法,保证逻辑结构不变,存储空间减小
• 利用一维数组,按顺序存储对角矩阵的元素
●观察对角矩阵的结构(我们此处以三对角矩阵举例):
•在三对角矩阵中,除了第一行和最后一行各有两个元素,其余各行非零元素aij均有三个,所以共有(3n-2)个非零元素 ,(第一行和最后一行,节点个数为2两个)
• 处于对角线下方的节点,(a10,a21,a32,...),观察得出,有:j = i-1;
• 处于对角线上的节点,(a00,a11,a22,...),有 : j=i;
• 处于对角线上方的节点,(a01,a12,a23,...),有: j=i+1;
●寻找二维坐标和一位数组的位序关系
•方法一: 输入坐标的时候,可以判断,然后确定是哪个位置上的节点,从而得出对应的一维数组的位序
•方法二:① 观察
② 先确定节点,前i行的元素个数,为: 2+3*(i-1)=3i-1;
因为,第一行和最后一行有两个元素,所以先把第一行算上,然后再算剩余i-1行,即可.
③ 对角线下方的节点, aij是本行第一个非零元素,所以其前面的元素是k = 3i-1 = 2i+j
④ 对角线的节点,是本行的第二个非零元素, k = 3i = 2i+j
⑤ 对角线上方的节点,是本行的第三个非零元素, k = 3i+1 = 2i+j;
•我们一维数组是从0开始计算的,所以元素前面的节点个数,就是对应的坐标位序
●下面我们开始构建三对角矩阵代码:
#include <stdio.h>
#include <malloc.h>
#define N 6
//构建一维数组数组
void Init(int *&b)
{
b = (int*)malloc(sizeof(int)*(3*N-1));
}
//将e赋值给对应的二维数组A[i][j]里面的值,存储在一维数组里面
void Assign(int b[],int e,int i, int j)
{
if(j == i-1)
{
b[3*i-1] = e;
}
else if(j == i)
{
b[3*i] = e;
}
else if(j==i+1)
{
b[3*i+1] = e;
}
}
//返回特定坐标里面的数值
int Value(int b[],int i, int j)
{
if(j == i-1)
{
return b[3*i-1];
}
else if(j == i)
{
return b[3*i];
}
else if(j==i+1)
{
return b[3*i+1];
}
else
{
return b[3*N-2];
}
}
//逐个输出二维数组里面的数据
void Disp(int b[])
{
int i,j;
for(i=0; i<N; i++)
{
for(j = 0; j<N; j++)
{
printf("%4d",Value(b,i,j));
}
printf("\n");
}
}
//销毁存储空间
void Destroy(int b[])
{
free(b);
}
int main()
{
//构建一维数组
//一维数组在元素矩阵个数的基础上加一,存放两侧的数据
int *b1;
//坐标
int i,j;
//承载输入数据
int v;
//构建一位数组
Init(b1);
printf("请输入要压缩的带状数据两侧的数据是多少?\n");
scanf("%d",&v);
b1[3*N-2] = v;
printf("请一次输入矩阵内的数据");
for(i=0;i<N;i++)
{
printf("请输入第%d行的%d个元素\n",i+1,N);
for(j = 0;j < N;j++)
{
scanf("%d",&v);
Assign(b1,v,i,j);
}
}
Disp(b1);
Destroy(b1);
return 0;
}
运行结果如图:
文章来源地址https://www.toymoban.com/news/detail-736214.html文章来源:https://www.toymoban.com/news/detail-736214.html
到了这里,关于对角矩阵的压缩存储的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!