当前位置：文档之家› 数据结构三元组稀疏矩阵

数据结构三元组稀疏矩阵

一、课程设计的目的

1.将C++语言理论基础实例化。

2.掌握关于编程的技巧和方法。

3.培养解决综合性实际问题的能力。

二、课程设计任务

题目：稀疏矩阵A，B的和

题目要求：稀疏矩阵A,B用三元组顺序表存储。

三元组表C存放结果矩阵

A，B的和存到C中。

题目：用三元组C存放以三元组顺序表做存储结构的稀疏矩阵A，B的和

一、题目分析

三元组表C是结果矩阵，其中元素仍行优先排列，

按元素的行列去找A中的三元组，若有，则加入C，同时，这个元素

如果在B中也有，则加上B的这个元素值，否则这个值就不变;

如果A中没有，则找B，有则插入C，无则查找下一个矩阵元素。两

个稀疏矩阵的非零元素按三元组表形式存放，

二、程序代码

#include

#define max 10

typedef struct

{int i,j;

int v;

}spnode;

typedef struct

{int mu,nu,tu;

spnode data[max];

}spmatrix;

addmatrix(spmatrix *a,spmatrix *b)

{spmatrix *c;

int p=0;q=0;col;

c=(spmatrix*)malloc(sizeof(spmatrix));

c->mu=a->mu;

c->nu=a->nu;

c->tu=0;

while (ptu&&qtu)

{

if((a-> data[p].i==B-> data[q].i)&&(A-> data[p].j==B-> data[q].j)) { col=a-> data[p].v+B-> data[q].v;

if(col!=0)

{ c-> data[c-> tu].i=a-> data[p].i;

c-> data[c-> tu].j=a-> data[p].j;

c-> data[c-> tu++].v=col;

}

p++;

q++;

}

if ((a-> data[p].i==b-> data[q].i)&&(a-> data[k].j data[l].j))

{ c-> data[c-> tu].i=a-> data[p].i;

c-> data[c-> tu].j=a-> data[p].j;

c-> data[c-> tu++].v=a-> data[p].v;

p++;

}

if ((a-> data[p].i==b-> data[q].i)&&(a-> data[k].j >b-> data[l].j))

{ c-> data[c-> tu].i=a-> data[p].i;

c-> data[c-> tu].j=a-> data[p].j;

c-> data[c-> tu++].v=a-> data[p].v;

q++;

}

while (ptu)

{ c-> data[c-> tu].i=a-> data[p].i;

c-> data[c-> tu].j=a-> data[p].j;

c-> data[c-> tu++].v=a-> data[p].v;

p++;

}

while(qtu)

{ c-> data[c-> tu].i=b-> data[q].i;

c-> data[c-> tu].j=b-> data[q].j;

c-> data[c-> tu++].v=b-> data[q].v;

q++;

}

void Setmatrix(SPMatrix* p)

{

int n;

cout<<"请输入矩阵行数、列数及非0元个数"<

cin>>p->mu>>P->nu>>p->tu;

cout<<"三元组表"<

for(n=1;n<=p->tu;n++)

cin>>p->data[n].i>>p->data[n].j>>p->data[n].v;

}

void main()

{

spmatrix a;

spmatrix b;

int i,j,k = 1;

spmatrix *c;

Setmatrix(&a);

Setmatrix(&b);

c = addmatrix(&a,&b);

cout<<"三元组表c"<

for (i = 1; i <= c->mu; ++i)

{

for (j = 1;j <= c->nu ; ++j)

{

if (pc->data[k].i == i && pc->data[k].j == j)

{ cout<data[k].v);

k++;

}

free(c);

}

三、运行结果

四、总结

三元组存储的矩阵的加法关键在于算法的分析。而数据结构比较C语言层次性更强。写算法的时候不是很难，就是对主函数的写法有点模糊。总

体上讲，实践将理论具体化，也更容易进一步的学习。

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

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

第五章矩阵的压缩存储与运算【实验目的】 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()表示取整，‘%’表示求余。

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

课程设计课程：数据结构题目：稀疏矩阵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）生成如下两个稀疏矩阵的三元组 a 和 b；（上机实验指导 P92 ）（2）输出 a 转置矩阵的三元组；（3）输出a + b 的三元组；（4）输出 a * b 的三元组；三实验内容: 稀疏矩阵的抽象数据类型: ADT SparseMatrix { 数据对象:D={aij| i = 1,2,3,….,m; j =1,2,3,……,n; ai,j∈ElemSet,m和n分别称为矩阵的行数和列数} 数据关系: R={ Row , Col } Row ={ | 1≤i≤m , 1≤j ≤n-1} Col ={| 1≤i≤m-1,1≤j ≤n} 基本操作:

CreateSMatrix(&M) 操作结果：创建稀疏矩阵 M PrintSMatrix(M) 初始条件：稀疏矩阵M已经存在操作结果：打印矩阵M DestroySMatrix(&M) 初始条件：稀疏矩阵M已经存在操作结果：销毁矩阵M CopySMatrix(M, &T) 初始条件：稀疏矩阵M已经存在操作结果：复制矩阵M到T AddSMatrix(M, N, &Q) 初始条件：稀疏矩阵M、N已经存在操作结果：求矩阵的和Q=M+N SubSMatrix(M, N, &Q) 初始条件：稀疏矩阵M、N已经存在操作结果：求矩阵的差Q=M-N TransposeSMatrix(M, & T) 初始条件：稀疏矩阵M已经存在操作结果：求矩阵M的转置T MultSMatrix(M, N, &Q) 初始条件：稀疏矩阵M已经存在