当前位置：文档之家› 稀疏矩阵的压缩计算

稀疏矩阵的压缩计算

（1）实验描述

在稀疏矩阵中，由于绝大部分是零元素，而这些零元素如果也要储存在计算机里，则会浪费大量的储存空间。因此，在实际储存稀疏矩阵时，可以只储存非零元素，而大量的零元素不储存，这就是稀疏矩阵的压缩储存。本实验进行稀疏矩阵的加减和乘除运算，并且探索如何用线性链表实现稀疏矩阵的加减和乘除。

（2）实验内容

（1）在稀疏矩阵中生成三列二维数组

在稀疏矩阵类中生成三列二维重要是由一般的稀疏矩阵生成一个结构体类型B 的数组。

（2）用三列二维数组表示后的稀疏矩阵的输出

根据三列二维数组，按行判断稀疏矩阵中的每一个元素，如果在三列二维数组中有，则是非零元素，输出该非零元素值，否则输出0.

（3）用三列二维数组表示后的稀疏矩阵的相加

1：先判断两个矩阵相加的可能性

2：临时申请一个三列二维数组空间A（和矩阵A中的非零元素的个数为矩阵C 和矩阵B中非零元素个数之和。

3：按行同时扫描三列二维数组表示的稀疏矩阵C和三列二维数组表示的稀疏矩阵B。

4：正式申请一个三列二维数组空间，由于存放和矩阵中所有非零元素的信息。5：构造用三列二维数组表示的和矩阵的POS向量和NUM向量。

（3）用三列二维数组表示后的稀疏矩阵的相乘

（4）用三元组链表表示后的稀疏矩阵的相加

1：判断相加的合理性

2：按行同时扫描三列二维数组表示的稀疏矩阵C和三列二维数组表示的稀疏矩阵B。

3：当一个矩阵中本行的所有非零元素都处理完后，则将另一个矩阵中的每一个剩余非零元素申请一个三元组结点，复制非零元素信息后将他们依次链接到和矩阵三元组链表的链尾。

（3）实验结果及分析

三列二维数组的生成有三种途径：（1）以三元组形式从键盘输入稀疏矩阵中各非零元素。（2）将存有稀疏矩阵非零元素信息的已有三列二维数组复制到稀疏矩阵类中。（3）直接将原有的稀疏矩阵用三列二维数组表示。

稀疏矩阵相加时：对于行号相同的两个矩阵中的非零元素，如果列号相同，则值相加。如果相加后值非零，则将相加结果依次存放在A中。如果列号不同，则将列号小的那个非零元素信息依次复制到A中，当一个矩阵中本行的所有非零元素都处理完后，则将另一个矩阵中的剩余非零元素信息也都依次复制到A中。

（4）实验结论

规则矩阵经压缩储存后，虽然节省了储存空间，但还要求比较方便的访问每一个元素，可以用三角矩阵，对称矩阵，三对角矩阵解决。

线性链表表示矩阵的加减乘除时，当产生新的非零元素时，可以直接申请一个存放三元组的结点，然后顺序链接到线性链表中，可以更方便进行稀疏矩阵的运算。

附录//代码:

#include

using namespace std;

//定义节点类型

template

struct B

{

int i;//非零元素所在的行号

int j;//非零元素所在的列号

T v;//非零元素值

};

//三列二维数组表示的稀疏矩阵类

template//类模板，T为虚拟类型

class Z_Array

{

private://成员函数

int mm;//稀疏矩阵行数

int nn;//稀疏矩阵列数

int tt;//稀疏矩阵中非零元素个数

B*bb;//三列二维数组空间

int*pos;//某行第一个非零元素在b中的下标

int*num;//某行非零元素的个数

public://成员函数

void in_Z_Array();//以三元组形式键盘输入稀疏矩阵非零元素void cp_Z_Array(int,int,int,B []);//复制三元组数组

void th_Z_Array(int,int,T []);//由一般稀疏矩阵转换

void prt_Z_Array();//按行输出稀疏矩阵

Z_Array tran_Z_Array();//稀疏矩阵转置

Z_Array operator+(Z_Array &);//稀疏矩阵相加

Z_Array operator*(Z_Array &);//稀疏矩阵相乘

};

//以三元组形式键盘输入稀疏矩阵非零元素

template//函数模板，T为虚拟类型

void Z_Array::in_Z_Array()

{

int k,m,n;

cout<<"输入行数列数非零元素个数：";

cin>>mm>>nn>>tt;

bb=new B[tt];//申请三列二维数组空间

cout<<"输入行号列号非零元素值："<

for(k=0;k

{

cin>>m>>n>>bb[k].v;

bb[k].i=m-1;bb[k].j=n-1;

}

pos=new int[mm];//申请POS向量空间

num=new int[mm];//申请NUM向量空间

for(k=0;k

num[k]=0;

for(k=0;k

num[bb[k].i]=num[bb[k].i]+1;

pos[0]=0;

for(k=1;k

pos[k]=pos[k-1]+num[k-1];

return;

}

//复制三元组数组

template//函数模板，T为虚拟类型

void Z_Array::cp_Z_Array(int m,int n,int t,Bb[])

{

int k;

mm=m;nn=n;tt=t;//复制稀疏矩阵的行号，列号和非零元素个数bb=new B[tt];//申请三列二维数组空间

for(k=0;k

{bb[k].i=b[k].i-1;bb[k].j=b[k].j-1;bb[k].v=b[k].v;}

pos=new int[mm];//申请POS向量空间

num=new int[mm];//申请NUM向量空间

for(k=0;k

num[k]=0;

for(k=0;k

num[bb[k].i]=num[bb[k].i]+1;

pos[0]=0;

for(k=1;k

pos[k]=pos[k-1]+num[k-1];

return;

}

//由一般稀疏矩阵转换

template//函数模板，T为虚拟类型

void Z_Array::th_Z_Array(int m,int n,T a[])

{

int k,t=0,p,q;

T d;

for(k=0;k

if(a[k]!=0) t=t+1;

mm=m;nn=n;tt=t;

bb=new B[tt];//申请三列二维数组空间

k=0;

for(p=0;p

for(q=0;q

{

d=a[p*n+q];

if(d!=0)//非零元素

{

bb[k].i=p;bb[k].j=q;bb[k].v=d;

k=k+1;

}

pos=new int[mm];//申请POS向量空间

num=new int[mm];//申请NUM向量空间

for(k=0;k

num[k]=0;

for(k=0;k

num[bb[k].i]=num[bb[k].i]+1;

pos[0]=0;

for(k=1;k

pos[k]=pos[k-1]+num[k-1];

return;

}

//按行输出稀疏矩阵

template//函数模板，T为虚拟类型

void Z_Array::prt_Z_Array()

{

int k,kk,p;

for(k=0;k

{

p=pos[k];//按行输出

for(kk=0;kk

if((bb[p].i==k)&&(bb[p].j==kk))//输出非零元素

{cout<

else cout<

cout<

}

return;

}

//稀疏矩阵转置

template//函数模板，T为虚拟类型

Z_ArrayZ_Array::tran_Z_Array()

{

Z_Arrayat;//定义转置矩阵对象

int k,p,q;

at.mm=nn;at.nn=mm;at.tt=tt;//转置矩阵行，列数以及非零元素个数

at.bb=new B[tt];//申请转置矩阵三列二维数组空间

k=0;

for(p=0;p

for(q=0;q

{

if(bb[q].j==p)//将非零元素信息依次存放到转置矩阵的三列二维数组中

{

at.bb[k].i=bb[q].j;

at.bb[k].j=bb[q].i;

at.bb[k].v=bb[q].v;

k=k+1;

}

at.pos=new int[at.mm];//申请POS向量空间

at.num=new int[at.mm];//申请NUM向量空间

for(k=0;k

at.num[k]=0;

for(k=0;k

at.num[at.bb[k].i]=at.num[at.bb[k].i]+1;

at.pos[0]=0;

for(k=1;k

at.pos[k]=at.pos[k-1]+at.num[k-1];

return(at);//返回转置矩阵

}

//稀疏矩阵相加

template//函数模板，T为虚拟类型

Z_Array Z_Array::operator+(Z_Array&b)

{

Z_Array c;//定义矩阵对象

B*a;

T d;

int m,n,k,p;

if((mm!=b.mm)||(nn!=b.nn)) cout<<"不能相加！"<

else

{

a=new B[tt+b.tt];//临时申请一个三列二维数组空间

p=0;

for(k=0;k

{

m=pos[k];n=b.pos[k];

while((bb[m].i==k)&&(b.bb[n].i==k))//行号相同

{

if(bb[m].j==b.bb[n].j)//列号相同则相加

{

d=bb[m].v+b.bb[n].v;

if(d!=0)//相加后非零

{

a[p].i=k;a[p].j=bb[m].j;

a[p].v=d;p=p+1;

}

m=m+1;n=n+1;

}

else if(bb[m].j

{

a[p].i=k;a[p].j=bb[m].j;

a[p].v=bb[m].v;p=p+1;

m=m+1;

}

else//列号不同复制另一项

{

a[p].i=k;a[p].j=b.bb[n].j;

a[p].v=b.bb[n].v;p=p+1;

n=n+1;

}

while(bb[m].i==k)//复制矩阵中本行剩余的非零元素{

a[p].i=k;a[p].j=bb[m].j;

a[p].v=bb[m].v;p=p+1;

m=m+1;

}

while(b.bb[n].i==k)//复制另一矩阵中本行剩余非零元素

{

a[p].i=k;a[p].j=b.bb[n].j;

a[p].v=b.bb[n].v;p=p+1;

n=n+1;

}

c.mm=mm;c.nn=nn;c.tt=p;

c.bb=new B[p];//申请一个三列二维数组空间

for(k=0;k

c.bb[k].i=a[k].i;

c.bb[k].j=a[k].j;

c.bb[k].v=a[k].v;

}

delete a;//释放临时三列二维数组空间

c.pos=new int[c.mm];//申请POS向量空间

c.num=new int[c.mm];//申请NUM向量空间

for(k=0;k

c.num[k]=0;

for(k=0;k

c.num[c.bb[k].i]=c.num[c.bb[k].i]+1;

c.pos[0]=0;

for(k=1;k

c.pos[k]=c.pos[k-1]+c.num[k-1];

}

return(c);//返回相加结果

}

//稀疏矩阵相乘

template//函数模板，T为虚拟类型

Z_Array Z_Array::operator*(Z_Array &b)

{

Z_Arraycc;

int k,m,n,p,t;

T*c;//定义乘积矩阵

if(nn!=b.mm)

cout<<"两矩阵无法相乘！"<

else

{

c=new T[mm*b.nn];//申请乘积矩阵的临时空间

k=0;

for(m=0;m

for(n=0;n

{c[k]=0;k=k+1;}//乘积矩阵元素清零

for(m=0;m

{

k=bb[m].j;//左矩阵中非零元素的列值k

n=b.pos[k];//右矩阵中行号与k相同的第一个非零元素的位置

t=b.pos[k]+b.num[k];//右矩阵中行号与k相同的最后一个非零元素的位置

while(n!=t)

{

p=bb[m].i*b.nn+b.bb[n].j;//在乘积矩阵中的位置

c[p]=c[p]+bb[m].v*b.bb[n].v;//累加非零元素的乘积

n=n+1;

}

cc.th_Z_Array(mm,b.nn,c);//由一般稀疏矩阵转换成用散列二维数组表示

delete c;//释放乘积矩阵的临时空间

}

return(cc);//返回用三列二维数组表示的乘积矩阵

}

int main()

{

Ba[8]={{1,3,3.0},{1,8,1.0},{3,1,9.0},{4,5,7.0},{5,7,6.0},{6,4,2.0},{6,6,3 .0},{7,3,5.0}};

Z_Array x,y,z,xt,c;//定义稀疏矩阵类对象，矩阵元素为双精度型

x.cp_Z_Array(7,8,8,a);//复制三元组数组生成稀疏矩阵类对象x

cout<<"输出稀疏矩阵x："<

x.prt_Z_Array();

xt=x.tran_Z_Array();//稀疏矩阵转置

cout<<"输出稀疏矩阵x的转置:"<

xt.prt_Z_Array();

y.in_Z_Array();//以三元组形式键盘输入稀疏矩阵非零元素

cout<<"输出稀疏矩阵y:"<

y.prt_Z_Array();

z=x+y;//稀疏矩阵相加

cout<<"输出稀疏矩阵z=x+y:"<

c=x*xt;//稀疏矩阵相乘

cout<<"输出c=x*xt:"<

c.prt_Z_Array();

return 0;

稀疏矩阵的计算概论

#include #include #include typedef int ElemType;// 稀疏矩阵的十字链表存储表示 typedef struct OLNode { int i,j; // 该非零元的行和列下标 ElemType e; // 非零元素值 struct OLNode *right,*down; // 该非零元所在行表和列表的后继链域}OLNode, *OLink; typedef struct// 行和列链表头指针向量基址,由CreatSMatrix_OL()分配{ OLink *rhead, *chead; int mu, nu, tu; // 稀疏矩阵的行数、列数和非零元个数 }CrossList; // 初始化M(CrossList类型的变量必须初始化,否则创建、复制矩阵将出错) int InitSMatrix(CrossList *M) { (*M).rhead=(*M).chead=NULL; (*M).mu=(*M).nu=(*M).tu=0; return 1; } // 销毁稀疏矩阵M int DestroySMatrix(CrossList *M) { int i; OLNode *p,*q; for(i=1;i<=(*M).mu;i++) // 按行释放结点 { p=*((*M).rhead+i); while(p) { q=p; p=p->right; free(q); } } free((*M).rhead); free((*M).chead); (*M).rhead=(*M).chead=NULL; (*M).mu=(*M).nu=(*M).tu=0; return 1; }

数据结构实验五矩阵的压缩存储与运算学习资料

数据结构实验五矩阵的压缩存储与运算

第五章矩阵的压缩存储与运算【实验目的】 1. 熟练掌握稀疏矩阵的两种存储结构(三元组表和十字链表)的实现； 2. 掌握稀疏矩阵的加法、转置、乘法等基本运算； 3. 加深对线性表的顺序存储和链式结构的理解。第一节知识准备矩阵是由两个关系（行关系和列关系）组成的二维数组，因此对每一个关系上都可以用线性表进行处理；考虑到两个关系的先后，在存储上就有按行优先和按列优先两种存储方式，所谓按行优先，是指将矩阵的每一行看成一个元素进行存储；所谓按列优先，是指将矩阵的每一列看成一个元素进行存储；这是矩阵在计算机中用一个连续存储区域存放的一般情形，对特殊矩阵还有特殊的存储方式。一、特殊矩阵的压缩存储 1. 对称矩阵和上、下三角阵若n阶矩阵A中的元素满足= （0≤i，j≤n-1 ）则称为n阶对称矩阵。对n阶对称矩阵，我们只需要存储下三角元素就可以了。事实上对上三角矩阵（下三角部分为零）和下三角矩阵（上三角部分为零），都可以用一维数组ma[0.. ]来存储A的下三角元素（对上三角矩阵做转置存储），称ma为矩阵A的压缩存储结构，现在我们来分析以下，A和ma之间的元素对应放置关系。问题已经转化为：已知二维矩阵A[i，j]，如图5-1，我们将A用一个一维数组ma[k]来存储，它们之间存在着如图5-2所示的一一对应关系。任意一组下标(i,j)都可在ma中的位置k中找到元素m[k]= ；这里： k=i(i+1)/2+j (i≥j) 图5-1 下三角矩阵 a00 a10 a11 a20 … an-1,0 … an-1,n-1

k= 0 1 2 3 …n(n- 1)/2 …n(n+1)/2-1 图5-2下三角矩阵的压缩存储反之，对所有的k=0,1，2,…,n(n+1)/2-1，都能确定ma[k]中的元素在矩阵A中的位置（i,j）。这里，i=d-1，（d是使sum= > k的最小整数），j= 。 2. 三对角矩阵在三对角矩阵中，所有的非零元素集中在以主对角线为中心的带内状区域中，除了主对角线上和直接在对角线上、下方对角线上的元素之外，所有其它的元素皆为零，见图5-3。图5-3 三对角矩阵A 与下三角矩阵的存储一样，我们也可以用一个一维数组ma[0..3n-2]来存放三对角矩阵A，其对应关系见图5-4。 a00 a01 a10 a11 a12 … an-1,n-2 an-1,n-1 k= 0 1 2 3 4 … 3n-3 3n-2 图5-4下三角矩阵的压缩存储 A中的一对下标(i,j)与ma中的下标k之间有如下的关系：公式中采用了C语言的符号，int()表示取整，‘%’表示求余。

MATLAB数值计算功能(向量、矩阵、数组、稀疏矩阵)

数值计算功能向量及其运算 1、向量生成（1)、直接输入向量元素用“［］”括起来，用空格或逗号生成行向量，用分号生成列向量 a１=［１１1４1７1８] ａ2＝[１1,14,１７,１8] a2=[１1;1４;1７;1８] %列向量用“’”可以进行向量转置 a1＝[11 14 １７１８] a4=ａ1'??%a1行向量，a4列向量也可以用组合方法： A=[１ 2 3]； B=［7 8 9]; Ｃ=［A ４onｅｓ(1,2)B］ (2)、等差元素向量生成冒号生成法：Vec＝Vｅｃ0:ｎ：Ｖｅcn,其中Ｖec表示生成的向量，Veｃ０表示第一个元素，ｎ表示步长，Vecn表示最后一个元素使用ｌiｎｅspａce函数：Vec＝ｌinesｐacｅ(Vｅc０,n,Vecn），其中Ｖｅc表示生成的向量，Vec0表示第一个元素,n表示生成向量元素个数(默认n＝100)，Vｅcn表示最后一个元素 veｃ1=10:5：５0 veｃ2=50：-5:1０ vｅc3＝linspace(１0,50,６) ２、向量的基本运算（1）、向量与数的四则运算向量中每个元素与数的加减乘除运算(除法运算时,向量只能作为被除数,数只能作为除数）vec1＝liｎspａcｅ(10,5０，６） vec1+10０ vec2=lｏｇspace(0,10,6)??％对数等分向量ｖｅｃ2／100 (2)、向量与向量之间的加减运算向量中的每个元素与另一个向量中相对应的元素的加减运算 veｃ１=lｉnsｐace(10,５0,6) ｖec2=lｏgspaｃe（０,２,6) vec３＝vｅc1+vec2 (3）、点积、叉积和混合机点积：dｏt函数，注意向量维数的一致性 x1=［11 22 33 44] x2=[1 2 3 4]

第3章矩阵及其运算

第3章矩阵及其运算 3.1 基本要求、重点难点基本要求： 1．1．掌握矩阵的定义. 2．2．掌握矩阵的运算法则. 3．3．掌握伴随矩阵的概念及利用伴随矩阵求逆矩阵的方法. 4．4．掌握矩阵秩的概念及求矩阵秩的方法. 5．5．掌握初等变换和初等矩阵的概念，能够利用初等变换计算矩阵的秩，求可逆矩阵的逆矩阵. 6．6．掌握线形方程组有解得判定定理及其初等变换解线形方程组的方法. 重点难点：重点是矩阵定义，矩阵乘法运算，逆矩阵的求法，矩阵的秩，初等变换及线性方程组的解. 难点是矩阵乘法，求逆矩阵的伴随矩阵方法. 3.2 基本内容 3.2.1 3.2.1 重要定义定义3.1 由n m ?个数)2,1;,2,1(n j m i a ij ==组成的m 行n 列的数表成为一个m 行n 列矩阵，记为 ????????????mn m m n n a a a a a a a a a 2122221 11211 简记为A n m ij a ?=)(，或A )(ij a =,n m A ?,mn A 注意行列式与矩阵的区别：（1）（1）行列式是一个数，而矩阵是一个数表. （2）（2）行列式的行数、列数一定相同，但矩阵的行数、列数不一定相同. （3）（3）一个数乘以行列式，等于这个数乘以行列式的某行（或列）的所有元素，而一个数乘以矩阵等于这个数乘以矩阵的所有元素. （4）（4）两个行列式相等只要它们表示的数值相等即可，而两个矩阵相等则要求两个矩阵对应元素相等. （5）（5）当0||≠A 时，||1A 有意义，而A 1 无意义.

n m =的矩阵叫做阶方阵或m 阶方阵.一阶方阵在书写时不写括号，它在运算中可看做一个数. 对角线以下（上）元素都是0的矩阵叫上（下）三角矩阵，既是上三角阵，又是下三角的矩阵，也就是除对角线以外的元素全是0的矩阵叫对角矩阵.在对角矩阵中，对角线上元素全一样的矩阵叫数量矩阵；数量矩阵中，对角线元素全是1的n 阶矩阵叫n 阶单位矩阵，常记为n E （或n I ），简记为E （或I ），元素都是0的矩阵叫零矩阵，记为n m 0?，或简记为0. 行和列分别相等的两个矩阵叫做同型矩阵，两个同型矩阵的且对应位置上的元素分别相等的矩阵叫做相等矩阵. 设有矩阵A =n m ij a ?)(，则A -n m ij a ?-=)(称为A 的负矩阵. 若A 是方阵，则保持相对元素不变而得到的行列式称为方针A 的行列式，记为||A 或A Det . 将矩阵A 的行列式互换所得到的矩阵为A 的转置矩阵，记为T A 或A '. 若方阵A 满足A A T =，则称A 为对称矩阵，若方阵A 满足A A T -=，则称A 为反对称矩阵. 若矩阵的元素都是实数，则矩阵称为实矩阵.若矩阵的元素含有复数，则称矩阵为复矩阵，若A =n m ij a ?)(是复矩阵，则称矩阵n m ij a ?)(（其中ij a 为ij a 的共轭矩阵，记为A n m ij a ?=)(. 定义3.2 对于n 阶矩阵A ，如果存在n 阶矩阵B ，使得E BA AB ==，则称方阵A 可逆，B 称为A 的逆矩阵，记做1-=A B . 对于方阵A n m ij a ?=)(，设ij a 的代数余子式为ij A ，则矩阵 *A ????????????=nm n n n n A A A A A A A A A 2122212 12111 称为A 的伴随矩阵，要注意伴随矩阵中元素的位置. 定义3.3 设有矩阵A ，如果：（1）（1）在A 中有一个r 阶子式D 不为零.

数据结构稀疏矩阵基本运算实验报告

课程设计课程：数据结构题目：稀疏矩阵4 三元组单链表结构体(行数、列数、头) 矩阵运算重载运算符优班级：姓名：学号：设计时间：2010年1月17日——2010年5月XX日成绩：指导教师：楼建华

一、题目二、概要设计 1.存储结构 typedef struct{ int row,col;//行，列 datatype v;//非0数值 }Node; typedef struct{ Node data[max];//稀疏矩阵 int m,n,t;//m 行，n 列，t 非0数个数 … … 2.基本操作 ⑴istream& operator >>(istream& input,Matrix *A)//输入 ⑵ostream& operator <<(ostream& output,Matrix *A){//输出 ⑶Matrix operator ~(Matrix a,Matrix b)//转置 ⑷Matrix operator +(Matrix a,Matrix b)//加法 ⑸Matrix operator -(Matrix a,Matrix b)//减法 ⑹Matrix operator *(Matrix a,Matrix b)//乘法 ⑺Matrix operator !(Matrix a,Matrix b)//求逆三、详细设计（1）存储要点 position[col]=position[col-1]+num[col-1]; 三元组表(row ，col ，v) 稀疏矩阵（（行数m ，列数n ，非零元素个数t ），三元组，...，三元组） 1 2 3 4 max-1

矩阵数值算法

计算实习报告一实习目的（1）了解矩阵特征值与相应特征向量求解的意义，理解幂法和反幂法的原理，能编制此算法的程序，并能求解实际问题。（2）通过对比非线性方程的迭代法，理解线性方程组迭代解法的原理，学会编写Jacobi 迭代法程序，并能求解中小型非线性方程组。初始点对收敛性质及收敛速度的影响。（3）理解 QR 法计算矩阵特征值与特征向量的原理，能编制此算法的程序，并用于实际问题的求解。二问题定义及题目分析 1. 分别用幂法和幂法加速技术求矩阵 2.5 2.5 3.00.50.0 5.0 2.0 2.00.50.5 4.0 2.52.5 2.5 5.0 3.5-?? ?- ?= ?-- ?--?? A 的主特征值和特征向量． 2. 对于实对称矩阵n n ?∈A R ，用Jacobi 方法编写其程序，并用所编程序求下列矩阵的全部特征值． 1515 4 1141144114114?-?? ?-- ? ?- ?= ? ?- ?-- ? ?-??A 3. 对于实矩阵n n ?∈A R ，用QR 方法编写其程序，并用所编程序求下列矩阵的全部特征值: 111 21 113,4,5,62311111n n n n n n ? ???? ?????==+? ????? ??+??A 三概要设计（1）幂法用于求按模最大的特征值及其对应的特征向量的一种数值算法，

它要求矩阵 A 的特征值有如下关系： 12n ...λλλ>≥≥ ，对于相应的特征向量。其算法如下： Step 0：初始化数据0,, 1.A z k = Step 1：计算1k k y A z +=。 Step 2：令 k k m y ∞=。 Step 3：令 k k k z y m = ；如果1k k m m +≈或1k k z z +≈，则 goto Step 4；否则， k = k + 1 ，goto Step 1。 Step 4：输出结果算法说明与要求输入参数为实数矩阵、初始向量、误差限与最大迭代次数。输出参数为特征值及相对应的特征向量。注意初始向量不能为“0”向量。（2）迭代法的原理如果能将方程 Ax =b 改写成等价形式：x=Bx+f 。如果B 满足：ρ(B )<1，则对于任意初始向量 x (0) ，由迭代 x ( k + 1) = Bx (k ) + f 产生的序列均收敛到方程组的精确解。迭代法中两种最有名的迭代法就是Jacobi 迭代法，它的迭代矩阵 B 为： 1()J D L U -=-+,1 f D b -= 其中，D 为系数矩阵 A 的对角元所组成对角矩阵，L 为系数矩阵 A 的对角元下方所有元素所组成的下三角矩阵，U 为系数矩阵 A 的对角元上方所有元素所组成的上三角矩阵。算法如下： Step 0：初始化数据 00,,,,k A b x δ=和ε。 Step 1：计算D,L,U,J 或G, 得到迭代矩阵B. Step 2：:1k k =+ 0x B x f * =+ 0x x = 如果0x x δ-<或()f x ε≤，goto Step 3?否则 goto Step ２。 Step 3：输出结果。程序说明与要求

稀疏矩阵的运算(完美版)

专业课程设计I报告（2011 / 2012 学年第二学期）题目稀疏矩阵的转换专业软件工程学生姓名张鹏宇班级学号 09003018 指导教师张卫丰指导单位计算机学院软件工程系日期 2012年6月18号

指导教师成绩评定表

附件：稀疏矩阵的转换一、课题内容和要求 1．问题描述设计程序用十字链表实现稀疏矩阵的加、减、乘、转置。 2．需求分析（1）设计函数建立稀疏矩阵，初始化值。（2）设计函数输出稀疏矩阵的值。（3）构造函数进行两个稀疏矩阵相加，输出最终的稀疏矩阵。（4）构造函数进行两个稀疏矩阵相减，输出最终的稀疏矩阵。（5）构造函数进行两个稀疏矩阵的相乘，输出最终的稀疏矩阵。（6）构造函数进行稀疏矩阵的转置，并输出结果。（7）退出系统。二、设计思路分析（1）设计函数建立稀疏矩阵，初始化值。（2）设计函数输出稀疏矩阵的值。（3）构造函数进行两个稀疏矩阵相加，输出最终的稀疏矩阵。（4）构造函数进行两个稀疏矩阵相减，输出最终的稀疏矩阵。（5）构造函数进行两个稀疏矩阵的相乘，输出最终的稀疏矩阵。（6）构造函数进行稀疏矩阵的转置，并输出结果。（7）退出系统。三、概要设计为了实现以上功能，可以从3个方面着手设计。 1．主界面设计为了实现对稀疏矩阵的多种算法功能的管理，首先设计一个含有多个菜单项的主

控菜单子程序以链接系统的各项子功能，方便用户交互式使用本系统。本系统主控菜单运行界面如图所示。 2．存储结构设计本系统采用单链表结构存储稀疏矩阵的具体信息。其中：全部结点的信息用头结点为指针数组的单链表存储。 3．系统功能设计本系统除了要完成稀疏矩阵的初始化功能外还设置了4个子功能菜单。稀疏矩阵的初始化由函数i typedef int ElemType 实现。建立稀疏矩阵用void Creat()实现，依据读入的行数和列数以及非零元素的个数，分别设定每个非零元素的信息。4个子功能的设计描述如下。（1）稀疏矩阵的加法：此功能由函数void Xiangjia( )实现，当用户选择该功能，系统即提示用户初始化要进行加法的两个矩阵的信息。然后进行加法，最后输出结果。（2）稀疏矩阵的乘法：此功能由函数void Xiangcheng( )实现。当用户选择该功能，系统提示输

数据结构实验五矩阵的压缩存储与运算

第五章矩阵的压缩存储与运算【实验目的】 1. 熟练掌握稀疏矩阵的两种存储结构(三元组表和十字链表)的实现； 2. 掌握稀疏矩阵的加法、转置、乘法等基本运算； 3. 加深对线性表的顺序存储和链式结构的理解。第一节知识准备矩阵是由两个关系（行关系和列关系）组成的二维数组，因此对每一个关系上都可以用线性表进行处理；考虑到两个关系的先后，在存储上就有按行优先和按列优先两种存储方式，所谓按行优先，是指将矩阵的每一行看成一个元素进行存储；所谓按列优先，是指将矩阵的每一列看成一个元素进行存储；这是矩阵在计算机中用一个连续存储区域存放的一般情形，对特殊矩阵还有特殊的存储方式。一、特殊矩阵的压缩存储 1. 对称矩阵和上、下三角阵若n阶矩阵A中的元素满足 = （0≤i，j≤n-1 ）则称为n阶对称矩阵。对n阶对称矩阵，我们只需要存储下三角元素就可以了。事实上对上三角矩阵（下三角部分为零）和下三角矩阵（上三角部分为零），都可以用一维数组ma[0.. ]来存储A的下三角元素（对上三角矩阵做转置存储），称ma为矩阵A的压缩存储结构，现在我们来分析以下，A和ma之间的元素对应放置关系。问题已经转化为：已知二维矩阵A[i，j]，如图5-1，我们将A用一个一维数组ma[k]来存储，它们之间存在着如图5-2所示的一一对应关系。任意一组下标(i,j)都可在ma中的位置k中找到元素m[k]= ；这里： k=i(i+1)/2+j (i≥j) 图5-1 下三角矩阵 a00 a10 a11 a20 … an-1,0 … an-1,n-1 k= 0 1 2 3 … n(n-1)/2 … n(n+1)/2-1 图5-2下三角矩阵的压缩存储反之，对所有的k=0,1，2,…,n(n+1)/2-1，都能确定ma[k]中的元素在矩阵A中的位置（i,j）。这里，i=d-1，（d是使sum= > k的最小整数），j= 。 2. 三对角矩阵

稀疏矩阵的运算课程设计

数据结构课程设计说明书题目: 稀疏矩阵的运算院系：计算机科学与工程学院专业班级：计算机10-**班学号： 201030**** 学生姓名： ****** 指导教师： ****** 2011年 12 月 28 日

安徽理工大学课程设计（论文）任务书计算机科学与工程学院 2011年 11 月 8 日

安徽理工大学课程设计（论文）成绩评定表

目录 1 问题描述 (1) 2 需求分析 (1) 3 总体设计 (2) 3.1 Matrix结构的定义 (2) 3.2 系统流程图 (3) 4 详细设计 (4) 4.1 “菜单”界面 (4) 4.2 建立矩阵 (4) 4.3 显示矩阵 (6) 4.4 矩阵的转置 (7) 4.5 矩阵的加法运算 (8) 4.6 矩阵的减法运算 (9) 4.7 矩阵的乘法运算 (9) 5 程序运行 (11) 5.1 输入矩阵 (11) 5.2 矩阵转置 (11) 5.3 矩阵加法 (12) 5.4 矩阵减法 (12) 5.5 矩阵乘法 (12) 5.6 退出及错误提示 (13) 6 总结 (13) 参考文献 (14)

1 问题描述 (1)题目内容：设计稀疏矩阵运算系统实现两个稀疏矩阵的加法、减法、乘法以及转置操作。 (2)基本要求： ①存储结构选择三元组存储方式； ②实现一个稀疏矩阵的转置运算； ③实现两个稀疏矩阵的加法运算； ④实现两个稀疏矩阵的减法运算； ⑤实现两个稀疏矩阵的乘法运算。 (3)设计目的：通过本次课程设计，了解稀疏矩阵的一些基本运算操作，并通过相关的程序代码实现。 2 需求分析经过本次的课程设计，我认为稀疏矩阵运算系统主要实现的功能如下：(1)建立矩阵：只有先建立了矩阵，才能够对矩阵进行运算操作，包括建立矩阵 A和矩阵B； (2)转置运算操作：对矩阵A或者矩阵B进行转置运算，输出相应的转置矩阵； (3)四则运算操作：该步骤由两个矩阵同时参与，对其进行加法运算(A+B)、减法运算(A-B)以及乘法运算(A*B和B*A)； (4)退出：当做完矩阵的运算操作之后，就可以点击它退出该界面。在这次设计中用到了一些变量和函数，例如：void Display(Matrix M)；int Max(int i,int j)；Matrix Zero(Matrix M)等，下面会做进一步详细的介绍。

三角矩阵在压缩存储下的转置矩阵源代码

#include #include #define max 20 #define zero 0 typedef struct{ int i,j,v; }node; typedef struct{ node data[max]; int m; }TSmatrix; TSmatrix *Setmatrix(){ //建三对角矩阵TSmatrix *T; T=(TSmatrix *)malloc(sizeof(TSmatrix)); printf("请输入矩阵行数或列数:\n"); scanf("%d",&T->m); printf("建立三对角矩阵:\n"); for(int n=0;n<3*T->m-2;n++) scanf("%d%d%d",&T->data[n].i,&T->dat a[n].j,&T->data[n].v); return T; } TSmatrix *Trabsmatrix(TSmatrix *T){ //三对角矩阵转置 int n,k,temp; TSmatrix *F; F=(TSmatrix *)malloc(sizeof(TSmatrix)); F->m=T->m; for(n=0;n<3*T->m-2;n++){ //将结点信息存入新三元组表中 temp=2*T->data[n].j+T->data[n].i; //计算待存入三元数组下标 F->data[temp].i=T->data[n].j; F->data[temp].j=T->data[n].i; F->data[temp].v=T->data[n].v; } return F; } void TSmatrixout(TSmatrix *T){ //三对角矩阵输出 int a,b,n; n=0; for(a=0;am;a++){ for(b=0;bm;b++){ if(T->data[n].i==a&&T->data[n].j==b){ printf("%-5d",T->data[n].v); n++; } else printf("%-5d",zero); } printf("\n"); } } void main(){ TSmatrix *T; T=Setmatrix(); printf("三对角矩阵:\n"); TSmatrixout(T); T=Trabsmatrix(T); printf("转置后三对角矩阵:\n"); TSmatrixout(T); } 问题分析：本程序要求实现对压缩存储下的三对角矩阵进行转置，为实现上述功能，需要解决的关键问题是三对角矩阵压缩存储及转置过程。概要设计：利用三元组表以行序为主序压缩存储三对角矩阵。转置时，先利用三元数组中的行标i 和列标j计算出待放入新三元数组的下标temp。由于转置时需要将行标和列标交换，所以temp=2*j+i。找出待存入的下标后，将相应的信息存入下标为temp的三元数组中。详细设计：

稀疏矩阵及其压缩存储方法

稀疏矩阵及其压缩存储方法 1.基本概念稀疏矩阵(SparseMatrix)：是矩阵中的一种特殊情况，其非零元素的个数远小于零元素的个数。设m行n列的矩阵含t个非零元素，则称以二维数组表示高阶的稀疏矩阵时，会产生零值元素占的空间很大且进行了很多和零值的运算的问题。特殊矩阵：值相同的元素或0元素在矩阵中的分布有一定的规律。如下三角阵、三对角阵、稀疏矩阵。压缩存储：为多个值相同的元素只分配一个存储空间；对0元素不分配空间。目的是节省大量存储空间。 n x n的矩阵一般需要n2个存储单元，当为对称矩阵时需要n(1+n)/2个单元。 2.三元组顺序表——压缩存储稀疏矩阵方法之一（顺序存储结构）三元组顺序表又称有序的双下标法，对矩阵中的每个非零元素用三个域分别表示其所在的行号、列号和元素值。它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。当矩阵中的非0元素少于1/3时即可节省存储空间。（1）稀疏矩阵的三元组顺序表存储表示方法 #define MAXSIZE 12500 // 假设非零元个数的最大值为12500 typedef struct { int i, j; // 该非零元的行下标和列下标 ElemType e; //非零元素的值 } Triple; // 三元组类型 typedef union { //共用体 Triple data[MAXSIZE + 1]; // 非零元三元组表，data[0]未用 int mu, nu, tu; // 矩阵的行数、列数和非零元个数 } TSMatrix; // 稀疏矩阵类型（2）求转置矩阵的操作 ◆用常规的二维数组表示时的算法 for (col=1; col<=nu; ++col) for (row=1; row<=mu; ++row) T[col][row] = M[row][col]; 其时间复杂度为: O(mu×nu) ◆用三元组顺序表表示时的快速转置算法 Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T) { // 采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵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; for (t=1; t<=M.tu; ++t) ++num[M.data[t].j];// 求M 中每一列所含非零元的个数

矩阵压缩1

为了节省存储空间并且加快处理速度，需要对这类矩阵进行压缩存储，压缩存储的原则是：不重复存储相同元素；不存储零值元素。一、相关概念㈠特殊矩阵：矩阵中存在大多数值相同的元,或非0元，且在矩阵中的分布有一定规律。 ⒈对称矩阵：矩阵中的元素满足 a ij=a ji 1≤i,j≤n ⒉三角矩阵：上（下）三角矩阵指矩阵的下（上）三角（不包括对角线）中的元素均为常数c或0的n阶矩阵。 ⒊对角矩阵（带状矩阵）：矩阵中所有非0元素集中在主对角线为中心的区域中。㈡稀疏矩阵：非0元素很少（≤ 5%）且分布无规律。二、存储结构及算法思想 1、对称矩阵存储分配策略：每一对对称元只分配一个存储单元,即只存储下三角（包括对角线）的元, 所需空间数为: n(n+1)/2。存储分配方法：用一维数组sa[n(n+1)/2]作为存储结构。 sa[k]与a ij之间的对应关系为: 2、三角矩阵也是一个n阶方阵，有上三角和下三角矩阵。下(上)三角矩阵是主对角线以上（下）元素均为零的n阶矩阵。设以一维数组sb[0..n(n+1)/2]作为n阶三角矩阵B的存储结构，仍采用按行存储方案，则B中任一元素b i,j和sb[k]之间仍然有如上的对应关系，只是还需要再加一个存储常数c的存储空间即可。如在下三角矩阵中，用n(n+1)/2的位置来存储常数。

对特殊矩阵的压缩存储实质上就是将二维矩阵中的部分元素按照某种方案排列到一维数组中，不同的排列方案也就对应不同的存储方案 2、稀疏矩阵常见的有三元组表示法、带辅助行向量的二元组表示法（也即行逻辑链表的顺序表），十字链表表示法等。 1）、三元组表示法三元组表示法就是在存储非零元的同时，存储该元素所对应的行下标和列下标。稀疏矩阵中的每一个非零元素由一个三元组(i,j,a ij)唯一确定。矩阵中所有非零元素存放在由三元组组成的数组中。