当前位置：搜档网 › 稀疏矩阵的存储实现

稀疏矩阵的存储实现

课程设计任务书

学生姓名：宋吉松专业班级：软件1202班

指导教师：李晓红工作单位：计算机科学与技术学院题目: 稀疏矩阵的存储实现

初始条件：

理论：学习了《数据结构》课程，掌握了一种计算机高级语言。

实践：计算机技术系实验中心提供计算机及软件开发环境。

要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写

等具体要求）

1、系统应具备的功能：

（1）实现稀疏矩阵的三元组和十字链表两种存储结构

（2）实现稀疏矩阵的基本运算

（3）输出结果

2、数据结构设计；

3、主要算法设计；

4、编程及上机实现；

5、撰写课程设计报告，包括：

（1）设计题目；

（2）摘要和关键字（中文和英文）；

（3）正文，包括引言、需求分析、数据结构设计、算法设计、有关技术的讨论、设计体会等；

（4）结束语；

（5）参考文献。

时间安排：2013年12月16日--25日

指导教师签名：李晓红 2013年12月14日系主任（或责任教师）签名：年月

日

摘要本课程设计在学习数据结构的前提下，运用c语言，对稀疏矩阵进行三元组存储和十字链表存储，并完成稀疏矩阵的转置，相加，相乘等基本运算。关键词稀疏矩阵三元组十字链表基本运算

Abstract This course is designed on the premise of learning data

structures using c language, for sparse matrix triple store to store and cross-linked, and were achieved under the two storage sparse matrix transpose, add, multiply, and other basic operations.

Keywords sparse matrix triples Crusaders basic operations

引言 (1)

1 需求分析

1.1稀疏矩阵三元组表和十字链表两种存储的实现 (2)

1.2稀疏矩阵转置 (2)

1.3稀疏矩阵的相加相乘 (2)

1.4输出结果 (2)

2 数据结构设计

2.1 三元组的结构体 (2)

2.2 十字链表的结构体 (3)

3算法设计

3.1三元组

3.1.1三元组的创建 (3)

3.1.2三元组的转置 (5)

3.1.3三元组的相加 (5)

3.1.4三元组的相乘 (8)

3.1.5三元组的显示 (10)

3.2十字链表

3.2.1十字链表的创建 (11)

3.2.2十字链表的显示 (12)

3.3 主函数 (13)

4 设计体会 (16)

5 结束语 (16)

附1 参考文献 (16)

附2 源代码 (17)

附3 运行结果 (38)

引言

什么是稀疏矩阵？人们无法给出确切的定义，它只是一个凭人们的直觉来了解的概念。假设在m×n的矩阵中，有t个元素不为零。令q=t/(m×n),称q为矩阵的稀疏因子。通常认为q<=0.05时称为稀疏矩阵。

按照压缩存储的概念，值存稀疏矩阵的非零元。因此，除了寻出非零元的值外，还必须同时记下它所在的行和列的位置。反之，一个三元组唯一确定了矩阵A 的一个非零元。由此，稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。其存储方法有三种，分别是三元组顺序表，行逻辑链接的顺序表，十字链表。分别是以顺序存储结构，带行连接信息的三元组表，及链式存储结构进行存储表示。

1需求分析

1.1稀疏矩阵三元组表和十字链表两种存储的实现

三元组表的实现通过建立两个结构体，分别用来表示三元组的行数、列数、非零元数和元素的行、列坐标、值。然后通过for循环进行赋值。并求出每行含有的非零元个数。十字链表与三元组的不同在于用链表来存储每一行，每一列的元素信息。

1.2稀疏矩阵的转置

稀疏矩阵的转置即将行列值进行调换，将元素的行列值进行调换，重排每个元素的次序。如何重排？三元组按照原矩阵M的列序进行转置。为了找到M的每个元素，要对三元组表从第一行开始进行扫描，便可得到转置后矩阵的顺序。十字链表需要将元素的行指针和列指针调换。

1.3稀疏矩阵的相加相乘

两个矩阵相加及每个元素分别对应相加。

两个矩阵的相乘M×N=S，即M的行元素与N的列元素分别对应乘积的累加，得到的即为S以M的行，N的列为坐标的元素的值。

1.4输出结果

可以用for或while循环，输出两种表示下的稀疏矩阵。

2 数据结构设计

2.1 三元组的结构体

typedef struct{

int i,j; //三元组每个元素的行坐标，列坐标，值int e;

}Triple;

typedef struct{

Triple data[MAXSIZE+1];

int rpos[MAXSIZE + 1]; //三元组各行第一个元素的位置

int mu,nu,tu; //三元组矩阵的行数，列数，非零元个数}TSMatrix; //三元组结构体定义；

2.2 十字链表的结构体

typedef struct OLNode{

int i,j;

int e; //十字链表每个元素的行坐标，列坐标，值struct OLNode *right,*down;

}OLNode,*OLink;

typedef struct {

int mu,nu,tu; //矩阵的行数，列数，非零元个数OLink *rhead,*chead; //行和列头指针

}CrossList; //十字链表结构体定义

3算法设计

3.1.1三元组的创建

void CreateSMatrix(TSMatrix &M){

//采用三元组顺序表存储表示，创建稀疏矩阵M

printf("请输入稀疏矩阵的行数列数非零元个数：\n");

scanf("%d%d%d",&M.mu,&M.nu,&M.tu);

if((M.mu<=0)||(M.nu<=0)||(M.tu<=0)||(M.tu>M.mu*M.nu))

//判断行值、列值、元素个数是否合法

printf("输入有误！");

for(int i=1;i<=M.tu;i++){ //输入稀疏矩阵元素

printf("请输入请输入非零元的行坐标列坐标值:");

scanf("%d%d%d",&M.data[i].i,&M.data[i].j,&M.data[i].e);

if((M.data[i].i<=0)||(M.data[i].j<=0)){

printf("输入错误，请重新输入!");

scanf("%d%d%d",&M.data[i].i,&M.data[i].j,&M.data[i].e);

}//if

}//for

int num[100];

if(M.tu)

{int i;

for(i = 1; i <= M.mu; i++) num[i] = 0; //初始化

for(int t = 1; t <= M.tu; t++) ++num[M.data[t].i]; //求M中每一行含非零元素个数

//求rpos

M.rpos[1] = 1;

for(i = 2; i <= M.mu; i++) M.rpos[i] = M.rpos[i-1] + num[i-1];

}

}//创建三元组

3.1.2三元组的转置

void TransposeSMatrix(TSMatrix M,TSMatrix &T){

T.nu=M.mu; //通过三元组表示，将M转置为T

T.mu=M.nu;

T.tu=M.tu;

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++;

} //三元组转置

3.1.3三元组的相加

int Compare(int a1,int b1,int a2,int b2){ //先建立Compare函数

if(a1>a2)return 1;

else if(a1

else if(b1>b2)return 1;

if(b1

else return 0;

}

void AddTMatix(TSMatrix M,TSMatrix T,TSMatrix &S){ //矩阵S存放相加后的矩阵

S.mu=M.mu>T.mu?M.mu:T.mu; //对S矩阵的行数赋值

S.nu=M.nu>T.nu?M.nu:T.nu; //对S矩阵的列数赋值

S.tu=0;

int ce;

int q=1;int mcount=1,tcount=1;

while(mcount<=M.tu&&tcount<=T.tu){

switch(Compare(M.data[mcount].i,M.data[mcount].j,T.data[tcount].i,T.data[tcount].j) )

//用switch分支语句，用compare函数对需要相加的两个矩阵的某元素行数列数进行比较

{case -1: S.data[q].e=M.data[mcount].e; S.data[q].i=M.data[mcount].i;

S.data[q].j=M.data[mcount].j; q++;

mcount++;

break;

case 1: S.data[q].e=T.data[tcount].e; S.data[q].i=T.data[tcount].i;

S.data[q].j=T.data[tcount].j; q++;

tcount++;

break;

case 0: ce=M.data[mcount].e+T.data[tcount].e;//其他情况下把两个矩阵的值相加if(ce){ S.data[q].e=ce;

S.data[q].i=M.data[mcount].i;

S.data[q].j=M.data[mcount].j;

q++;

mcount++;

tcount++;}

else {mcount++;

tcount++;}

break;

while(mcount<=M.tu){

S.data[q].e=M.data[mcount].e;

S.data[q].i=M.data[mcount].i;

S.data[q].j=M.data[mcount].j;

q++;

mcount++; }//在case=-1的情况下对S矩阵的非零值，行数，列数进行赋值while(tcount<=M.tu){

S.data[q].e=T.data[tcount].e;

S.data[q].i=T.data[tcount].i;

S.data[q].j=T.data[tcount].j;

q++;

tcount++;

}//在case=1的情况下对S矩阵的非零值，行数，列数进行赋值

S.tu=q-1;

}//三元组相加

3.1.4三元组的相乘

int MultSMatrix(TSMatrix M, TSMatrix N, TSMatrix &Q)

{

int arow, brow, ccol, i, t, ctemp[100], p, q, tp;//定义相乘函数中所需要用到的变量

if(M.nu != N.mu) return 0;//如果第一个矩阵的行数不等于第二个矩阵的列数，则退出

Q.mu = M.mu, Q.nu = N.nu, Q.tu = 0;//三元组结构类型Q存放相乘后的结果

if(M.tu * N.tu != 0)//如果两个矩阵元素相乘不为零，则进行运算

{

for(arow = 1; arow <= M.mu; ++arow)//最外侧循环以矩阵行数作为循环变量

{

for(i = 0; i <= N.nu; ++i) ctemp[i] = 0;

Q.rpos[arow] = Q.tu + 1;

if(arow < M.mu) tp = M.rpos[arow + 1];

else tp = M.tu +1;

for(p = M.rpos[arow]; p < tp; ++p)//把每行与每列相乘

{

brow = M.data[p].j;

if(brow < N.mu) t = N.rpos[brow+1];

else t = N.tu + 1;

for(q = N.rpos[brow]; q < t; ++q)

{

ccol = N.data[q].j;

ctemp[ccol] += M.data[p].e * N.data[q].e;//值相乘

}

for(ccol = 1; ccol <= Q.nu; ++ccol) //把运算后的结果存放到Q 中

{

if(ctemp[ccol])

{

if(++(Q.tu) > MAXSIZE) return 1;

Q.data[Q.tu].i = arow, Q.data[Q.tu].j = ccol, Q.data[Q.tu].e = ctemp[ccol];

}

return 1;

}//三元组相乘

3.1.5三元组的显示

void ShowTMatrix(TSMatrix M){

for(int col=1;col<=M.mu;col++)//通过双重循环，把稀疏矩阵中不为零的元素的行数、列数和值显示出来

for(int p=1;p<=M.tu;p++)

if(M.data[p].i==col)printf("%4d %4d %4d\n",M.data[p].i,M.data[p].j,M.data[p].e);

}//三元组显示

3.2.1十字链表的创建

void CreateSMatix_OL(CrossList &M){

int i,j,e;

OLink p,q;

printf("请输入稀疏矩阵的行数列数非零元素的个数:\n"); //矩阵行数，列数下标均从开始；

scanf("%d%d%d",&M.mu,&M.nu,&M.tu);

if(!(M.rhead=(OLink *)malloc((M.mu+1)*sizeof(OLNode)))) exit(1);//分配内存空间if(!(M.chead=(OLink *)malloc((M.nu+1)*sizeof(OLNode)))) exit(1);//分配内存空间for( i=1;i<=M.mu;i++)M.rhead[i]=NULL; //把矩阵

每个元素置空值

for( i=1;i<=M.nu;i++)M.chead[i]=NULL;

printf("请输入非零元素的行坐标列坐标值：");

scanf("%d%d%d",&i,&j,&e);

while(i!=0){

p=(OLink)malloc(sizeof(OLNode));

p->i=i;p->j=j;p->e=e;

if(M.rhead[i]==NULL||M.rhead[i]->j>j){p->right=M.rhead[i];M.rhead[i]=p;}

else{

q=M.rhead[i];

while(q->right&&q->right->jright;

p->right=q->right;

q->right=p;}

if(M.chead[j]==NULL||M.chead[j]->i>i){p->down=M.chead[j];M.chead[j]=p;}

else{

q=M.chead[j];

while(q->down&&q->down->idown;

p->down=q->down;

q->down=p;

}

scanf("%d%d%d",&i,&j,&e);

}

} //创建十字链表

3.2.2十字链表的显示

int ShowMAtrix(CrossList *A){

int col;

OLink p;

for(col=1;col<=A->mu;col++)if(A->rhead[col]){p=A->rhead[col];

while(p){printf("%3d%3d%3d\n",p->i,p->j,p->e);p=p->right;}

}

return 1;

} //十字链表显示

3.3 主函数

//主函数

void main(){

int n,i;

TSMatrix M,T,S;

CrossList MM,TT,SS;

printf("*******稀疏矩阵的应用*******\n");

printf("\n1：用三元组创建稀疏矩阵\n2:用十字链表创建稀疏矩阵\n3:退出程序"); printf("\n");

scanf("%d",&n);

switch(n){

case 1:

CreateSMatrix(M);

printf("您输入的稀疏矩阵为：\n 行列大小\n");

ShowTMatrix(M);

printf("已经选择三元组创建稀疏矩阵,请继续选择：\n1：稀疏矩阵转置\n2：稀疏矩阵相加\n3：稀疏矩阵相乘\n4：退出程序\n");

scanf("%d",&i);

switch(i){

case 1:TransposeSMatrix(M,T);

printf("转置后的矩阵为：\n 行列大小\n");

ShowTMatrix(T);

break;

case 2:printf("请你输入另一个稀疏矩阵:");

CreateSMatrix(T);

AddTMatix(M,T,S);

printf("相加后的矩阵为：\n 行列大小\n");

ShowTMatrix(S);

break;

case 3:printf("请你输入另一个稀疏矩阵:");

CreateSMatrix(T);

MultSMatrix(M,T,S);

printf("相乘后的矩阵为：\n 行列大小\n");

ShowTMatrix(S);

break;

case 4:

exit(0);};break;

case 2:{CreateSMatix_OL(MM);

printf("您输入的稀疏矩阵为：\n 行列大小\n");

ShowMAtrix(&MM);

printf("已经选择十字链表创建稀疏矩阵，请选择操作:\n1：稀疏矩阵转置\n2：稀疏矩阵相加\n3：稀疏矩阵相乘\n4：退出程序\n");

scanf("%d",&i);

switch(i){

case 1:

TurnSMatrix_OL(MM);

printf("转置后的矩阵为：\n 行列大小\n");

ShowMAtrix(&MM);

break;

case 2:

printf("请你输入另一个稀疏矩阵:");

CreateSMatix_OL(TT);

SMatrix_ADD(&MM,&TT);

printf("相加后的矩阵为：\n 行列大小\n");

ShowMAtrix(&MM);break;

case 3:printf("请你输入另一个稀疏矩阵:");

CreateSMatix_OL(TT);

MultSMatrix_OL(MM,TT,SS);

printf("相乘后的矩阵为：\n 行列大小\n"); ShowMAtrix(&SS);break;

case 4:exit(0);

}};break;

case 3:exit(0);

default :printf("输入错误！");

}

4 设计体会及结束语

通过设计本程序，加深了对矩阵存储的了解，掌握了稀疏矩阵三元组存储和十字链表存储两种存储方法。课本上介绍的较简略，有的地方甚至有个错误，经过不断检查才最终发现，发现课本上的不一定是对的，同样的问题也许有更好的方法。很多不懂的地方通过上网查资料，借鉴别人的设计经验，学习新的函数最终完成了本设计。通过这次课程设计，丰富了自己的专业知识，增强了自己解决问题的能力，有很大帮助。

完成这次设计要感谢指导老师李晓红老师，及室友们的帮助。

附1 参考文献

【1】数据结构（c语言版）严蔚敏吴伟民清华大学出版社 2007

【2】C程序设计教程张蕊吕涛华中科技大学出版社 2012.9

【3】C++面向对象程序设计教程第3版陈维兴林小茶清华大学出版社2009.6

【4】百度文库稀疏矩阵十字链表运算

附2 源代码

#include

#define MAXSIZE 10000

typedef struct OLNode{

int i,j;

int e; //十字链表每个元素的行坐标，列坐标，值struct OLNode *right,*down;

}OLNode,*OLink;

typedef struct {

int mu,nu,tu; //矩阵的行数，列数，非零元个数

OLink *rhead,*chead; //行和列头指针

}CrossList; //十字链表结构体定义

typedef struct{

int i,j; //三元组每个元素的行坐标，列坐标，值

int e;

}Triple;

typedef struct{

Triple data[MAXSIZE+1];

int rpos[MAXSIZE + 1]; //三元组各行第一个元素的位置

int mu,nu,tu; //三元组矩阵的行数，列数，非零元个数

}TSMatrix; //三元组结构体定义；

void CreateSMatrix(TSMatrix &M){

//采用三元组顺序表存储表示，创建稀疏矩阵M

printf("请输入稀疏矩阵的行数列数非零元个数：\n");

scanf("%d%d%d",&M.mu,&M.nu,&M.tu);

if((M.mu<=0)||(M.nu<=0)||(M.tu<=0)||(M.tu>M.mu*M.nu))

//判断行值、列值、元素个数是否合法

printf("输入有误！");

for(int i=1;i<=M.tu;i++){ //输入稀疏矩阵元素

printf("请输入请输入非零元的行坐标列坐标值:");

scanf("%d%d%d",&M.data[i].i,&M.data[i].j,&M.data[i].e);

if((M.data[i].i<=0)||(M.data[i].j<=0)){

printf("输入错误，请重新输入!");

scanf("%d%d%d",&M.data[i].i,&M.data[i].j,&M.data[i].e);

}//if

}//for

int num[100];

if(M.tu)

{int i;

for(i = 1; i <= M.mu; i++) num[i] = 0; //初始化

for(int t = 1; t <= M.tu; t++) ++num[M.data[t].i]; //求M中每一行含非零元素个数

//求rpos

M.rpos[1] = 1;

for(i = 2; i <= M.mu; i++) M.rpos[i] = M.rpos[i-1] + num[i-1];

}

}//创建三元组

void TransposeSMatrix(TSMatrix M,TSMatrix &T){

T.nu=M.mu; //通过三元组表示，将M转置为T

T.mu=M.nu;

T.tu=M.tu;

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 Compare(int a1,int b1,int a2,int b2){

if(a1>a2)return 1;

else if(a1

else if(b1>b2)return 1;

if(b1

else return 0;

}

void AddTMatix(TSMatrix M,TSMatrix T,TSMatrix &S){//矩阵S存放相加后的矩阵

实现稀疏矩阵(采用三元组表示)的基本运算实验报告

实现稀疏矩阵（采用三元组表示）的基本运算实验报告一实验题目: 实现稀疏矩阵（采用三元组表示）的基本运算二实验要求: （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已经存在