课程设计实验报告稀疏矩阵应用

1、数据结构课程设计数据结构课程设计一. 题目： 稀疏矩阵应用（限1 人完成） 要求：实现三元组，十字链表下的稀疏矩阵的加、转、乘的实现。（1）稀疏矩阵的存储（2）稀疏矩阵加法（3）矩阵乘法（4）矩阵转置二. 算法思想描述：1. 算法概述：首先用两个结构体来定义十字链表元素： typedef struct OLNodeint i,j;int e;struct OLNode *right,*down;OLNode,*OLink;OLNode结构为链表结点，i,j,e分别表示稀疏矩阵中元素的行，列和值。typedef struct int mu,nu,tu; /行数mu，列数nu，非零元素的个数tuO

2、Link *rhead,*chead;CrossList;CrossList结构用于连接起各个结点，mu,nu,tu分别表示整个矩阵的行数列数和非零元素的个数。整个程序包含CreateSMatix_OL（用于创建十字链表），SMatrix_ADD（十字链表相加），ShowMAtrix(十字链表显示)，MultSMatrix_OL（十字链表相乘），TurnSMatrix_OL（十字链表转置），DestroySMatrix_OL（十字链表销毁）六个函数。CreateSMatix_OL的功能如下：首先输入稀疏矩阵的行数，列数，非零元素的个数，为*rhead和*chead分配内存空间，并将十字链表中节

3、点初始化为NULL。然后依次输入非零元素的行，列，值，以0 0 0为结尾结束链表的连接和while循环。SMatrix_ADD的功能如下：在初始化稀疏矩阵后选择十字链表相加会提示输入另一个稀疏矩阵，连接结束后SMatrix_ADD函数以循环的方式比较非零元素是否为同一行列，如果是则两值相加，如果不是则把第二个元素加入链表中。ShowMAtrix的功能如下：逐一输出链表的行，列，值三个元素知道达到表尾的NULL。MultSMatrix_OL的功能如下：与相加类似，在初始化稀疏矩阵后选择十字链表相加会提示输入另一个稀疏矩阵，连接结束后MultSMatrix_OL函数以循环的方式比较非零元素是否为同

4、一行列，如果是则两值相乘，如果不是则修改原来的元素值为0。TurnSMatrix_OL的功能如下：逐一查找十字链表中各个元素，将他们的i,j值对调已达到转置的目的.2. 算法具体分析（1） 、输入需要执行的操作：1为创建稀疏矩阵，调用CreateSMatix_OL函数，输入稀疏矩阵的行数列数和非零元素的个数（如 2 2 1，中间以空格分开）CreateSMatix_OL函数会将各个元素的信息保存在十字链表的结点中并连接起来。2为退出程序。（2） 、选择接下来要执行的操作：1为稀疏矩阵转置调用TurnSMatrix_OL函数逐一查找十字链表中各个元素，将他们的i,j值对调已达到转置的目的。2为稀

5、疏矩阵相加，调用SMatrix_ADD函数创建另一个稀疏矩阵并且将两矩阵中的非零元素相加。3为稀疏矩阵相乘，调用MultSMatrix_OL函数创建另一个稀疏矩阵并且将两矩阵中的同行列的非零元素项相乘，其余项修改为0。4为退出。（3） 、程序显示操作结果，运行正常，结果正确。三、程序结构main()函数退出CreateSMatix_OL()函数exit()函数TurnSMatrix_OL()函数Switch（）函数Switch（）函数ShowMAtrix()函数CreateSMatix_OL();函数SMatrix_ADD();函数ShowMAtrix()函数CreateSMatix_OL()

6、函数MultSMatrix_OL()函数ShowMAtrix()函数四、实验结果与分析上述程序在Visual C+ 6.0 环境下加以实现，经过多次的测试，程序运行正确。例如：输入1，再输入2 2 1接着输入非零元素为第2行第1列值为9（2 1 9）.运行结果如图2，图中创建十字链表成功可以选择后续操作稀疏矩阵转置，稀疏矩阵相加，稀疏矩阵相乘。图2选择稀疏矩阵相加实验，输入2，再输入2 2 2创建另一个稀疏矩阵，接着输入1 1 9和2 1 1两个非零元素，SMatrix_ADD函数会将两个矩阵的非零元素相比较，在同行列的值相加，不在同行列的为十字链表添加结点，计算结果如图3，可以看到第一行第一

7、列的元素9被加入到链表中，而第2行第1列的两个元素9和1相加得到10，程序运行成功。图3五体会通过这次课程设计，我有很深的体会，具体如下：1. 十字链表的建立，和使用有了更深层次的理解。2. 各种循环语句的使用和switch语句的应用比较熟悉了。3. 把各个功能写在不同的函数体里，分工明确，条理清晰，这样不但语句简洁，而且十分明了。4. 从用户角度出发来编写程序，使结果尽量简洁明了。附代码：#include<stdio.h>#include<stdlib.h>#include<malloc.h>#define MAXSIZE 100int num100;ty

8、pedef struct OLNodeint i,j;int e;struct OLNode *right,*down;OLNode,*OLink;typedef struct int mu,nu,tu; /行数mu，列数nu，非零元素的个数tuOLink *rhead,*chead;CrossList;int CreateSMatix_OL(CrossList &M)int i,j,e;OLink q; OLink p;printf("请输入稀疏矩阵的行数，列数，非零元素的个数:");scanf("%d%d%d",&M.mu,&

9、M.nu,&M.tu);M.rhead=(OLink *)malloc(M.mu+1)*sizeof(OLNode);M.chead=(OLink *)malloc(M.nu+1)*sizeof(OLNode);for( i=1;i<=M.mu;i+)M.rheadi=NULL;for( i=1;i<=M.nu;i+)M.cheadi=NULL;printf("请输入元素的行 列 值。最后输入0 0 0为结束n");scanf("%d%d%d",&i,&j,&e);while(i!=0)p=(OLink)mal

10、loc(sizeof(OLNode);p->i=i;p->j=j;p->e=e;if(M.rheadi=NULL|M.rheadi->j>j)p->right=M.rheadi;M.rheadi=p;elseq=M.rheadi;while(q->right&&q->right->j<j)q=q->right;p->right=q->right;q->right=p;if(M.cheadj=NULL|M.cheadj->i>i)p->down=M.cheadj;M.cheadj

11、=p;elseq=M.cheadj;while(q->down&&q->down->i<i)q=q->down;p->down=q->down;q->down=p;scanf("%d%d%d",&i,&j,&e);return 1;/创建十字链表int Compare(int a1,int b1,int a2,int b2)if(a1>a2)return 1;else if(a1<a2)return -1;else if(b1>b2)return 1;if(b1<

12、b2)return -1;else return 0;int SMatrix_ADD(CrossList *A,CrossList *B)OLNode *pa,*pb,*pre,*p,*cp100;int i,j,t;t=A->tu+B->tu;for(j=1;j<=A->nu;j+)cpj=A->cheadj;for(i=1;i<=A->mu;i+)pa=A->rheadi;pb=B->rheadi;pre=NULL;while(pb)if(pa=NULL|pa->j>pb->j)p=(OLink)malloc(size

13、of(OLNode);if(!pre)A->rheadi=p;else pre->right=p;p->right=pa;pre=p;p->i=i;p->j=pb->j;p->e=pb->e;if(!A->cheadp->j)A->cheadp->j=cpp->j=p;p->down=NULL;elsecpp->j->down=p;cpp->j=p;pb=pb->right;else if(pa->j<pb->j)pre=pa;pa=pa->right;else

14、if(pa->e+pb->e)t-;pa->e+=pb->e;pre=pa;pa=pa->right;pb=pb->right;else t=t-2;if(!pre)A->rheadi=pa->right;else pre->right=pa->right;p=pa;pa=pa->right;if(A->cheadp->j=p)A->cheadp->j=cpp->j=p->down;else cpp->j->down=p->down;free(p);pb=pb->rig

15、ht;A->mu=A->mu>B->mu?A->mu:B->mu;A->nu=A->nu>B->nu?A->nu:B->nu;return 1;/十字链表相加int ShowMAtrix(CrossList *A)int col; OLink p;for(col=1;col<=A->mu;col+)if(A->rheadcol)p=A->rheadcol;while(p)printf("%3d%3d%3dn",p->i,p->j,p->e);p=p->ri

16、ght;return 1;/十字链表显示int MultSMatrix_OL(CrossList M, CrossList N, CrossList &Q)int i, j, e; /中间变量OLink p0, q0, p, pl, pla; /中间变量/检查稀疏矩阵M的列数和N的行数是否对应相等if(M.nu != N.mu)printf ( "稀疏矩阵A的列数和B的行数不相等，不能相乘。n" );return 0; Q.mu = M.mu, Q.nu = N.nu, Q.tu = 0;if(!(Q.rhead = (OLink *)malloc(Q.mu + 1

17、) * sizeof(OLink) exit(-2);if(!(Q.chead = (OLink *)malloc(Q.nu + 1) * sizeof(OLink) exit(-2);for(i = 1; i <= Q.mu; i+) Q.rheadi = NULL;for(i = 1; i <= Q.nu; i+) Q.cheadi = NULL;/相乘for(i =1; i <= Q.mu; i+)for(j = 1; j <= Q.nu; j+)p0 = M.rheadi, q0 = N.cheadj, e = 0;while(p0&&q0)/M

18、第i行和N第j列有元素if( p0->j > q0->i) q0 = q0->down; /M的列大于N的行，则N的列指针后移else if(p0->j < q0->i) p0 = p0->right;/M的列小于N的行，则M的行指针右移else /M的行等于N的列e += p0->e * q0->e; /乘积累加q0 = q0->down, p0 = p0->right;/移动指针if(e)/乘积不为0if(!(p = (OLink)malloc(sizeof(OLNode) exit(-2);Q.tu+;/非零元素增加

19、p->i = i, p->j = j, p->e = e, p->right = NULL, p->down = NULL;/赋值，指针后移/将p插入十字链表/行插入if(Q.rheadi = NULL) /若p为该行的第1个结点Q.rheadi = pl = p; /p插在该行的表头且pl指向p(该行的最后一个结点)else pl->right = p, pl = p; /插在pl所指结点之后，pl右移/列插入if(Q.cheadj = NULL) /若p为该列的第一个结点Q.cheadj = p; /该列的表头指向pelse /插在列表尾pla = Q.

20、cheadj;/pla指向j行的第1个结点while(pla->down) pla = pla->down;/pla指向j行最后一个结点pla->down = p; return 1;/十字链表相乘void TurnSMatrix_OL(CrossList &M)int col,row;OLink p,q;for(col=1;col<=M.mu;col+) q=p=M.rheadcol;while(q)row=p->i;p->i=p->j;p->j=row;q=p->right;p->right=p->down;p-&g

21、t;down=q;/十字链表转置int DestroySMatrix_OL(CrossList &M)int i;/中间变量OLink p, q;/中间变量if(!M.rhead | !M.chead) return 1;/M不存在else /M存在if(M.chead)/所有列链表头指针置为空for(i = 1; i <= M.nu; i+)M.cheadi = NULL; if(M.rhead)/按行释放节点for(i = 1; i <= M.mu; i+)p = M.rheadi;while(p)q = p, p = p->right;free(q); /释放行和列链表头指针指向基址free(M.