数据结构--稀疏矩阵运算器
数据结构
课程设计报告
设计题目:稀疏矩阵运算器 年 级
班 级
姓 名
学 号指导教师
起止时间
学期
一、实验目的
通过实习,了解并初步掌握设计、实现较大系统的完整过程,包括系统分析、编码设计、系统集成、以及调试分析,熟练掌握数据结构的选择、设计、实现以及操作方法,为进一步的应用开发打好基础。
二、问题描述(具体任务)
设计、实现两个稀疏矩阵在十字链表表示方法下的相加、相减、相乘。稀疏矩阵是指那些多数元素为零的矩阵。利用稀疏特点进行储存和计算可以大大节省储存空间,提高计算效率。实现一个能进行称稀疏矩阵基本运算的运算器。
三、需求分析
该程序所做的工作的是稀疏矩阵运算器,实现两个稀疏矩阵的基本运算。此程序规定:
1、按照压缩存储的概念,只存储稀疏矩阵的非零元,以两个三元组{i,j,e}来表示矩阵的非零元的行,列和数值,就确定了一个非零元.由此,稀疏矩阵可由表示非零元的三元数组及行列数确定
2、用户输入数据作为三元组的行,列和非零元的个数,用空格隔开.并输入非零元的行,列和数值
3、本程序只对两个矩阵进行四则运算,所的结果矩阵应该另生成,用十字链表存放,并放入新的矩阵中,只要对矩阵求解就能求出答案.
四、算法设计思想及流程图
用十字链表存储方式实现稀疏矩阵的基本运算,此程序用到以下函数:
void CreateSMatrix(CrossList &R) //创建储存稀疏矩阵
void PrintSMatrix(CrossList R) //输出十字链表的函数
void MultSMatrix(CrossList M,CrossList N,CrossList &Q) //实现矩阵乘法
int AddMatrix(CrossList M,CrossList N,CrossList &Q) //实现矩阵加法
int SubtSMatrix(CrossList M,CrossList N,CrossList &Q) //实现矩阵减法
void main()//主函数调用以上函数来实现其功能:
首先调用CreateSMatrix()创建矩阵M和N,并输入稀疏矩阵的行数,列数,非零元素个数,通过PrintSMatrix()输出矩阵M和N,根据提示选择相应的运算,当进行加或减运算时,如果两个矩阵的行和列不相等时,就无法得到结果,并出现提示错误信息,当进行乘法运算时,要求矩阵M的列数必须等于矩阵N的行数,否则无法进行乘法运算,为了进行多种运算通过主函数的Do----While循环来实现,退出循环条件是输入”+”、”-”、”*”以外的任意字符即可退出循环。
五、C语言源代码
#include
#include
#define OVERFLOW -1
#define OK 1
#define NULL 0
//建立十字链表
typedef struct OLNode
{
int row,col; //该非零元的行和列下标
int e;
struct OLNode *right,*down; //该非零元所在行表和列表的后继链域 }OLNode,*OLink;
typedef struct{
OLink *rhead,*chead; //行和列链表头指针向量基址由CreateSMatrix分配
int mu,nu,tu; //系数矩阵的行数,列数和非零元个数
}CrossList;
// 创建储存稀疏矩阵
void CreateSMatrix(CrossList &R)
{
int m,n,t,i,j,k,a;
OLink p,q;
if(R.rhead)
{
R.rhead=NULL;
R.chead=NULL;
R.mu=0;
R.nu=0;
R.tu=0;
}
printf("\n请输入稀疏矩阵的行数 列数 非零元个数:");
scanf("%d %d %d",&m,&n,&t);
R.mu=m;
R.nu=n;
R.tu=t;
if(!(R.rhead=(OLink *)malloc((m+1)*sizeof(OLink))))exit(OVERFLOW);
if(!(R.chead=(OLink *)malloc((n+1)*sizeof(OLink))))exit(OVERFLOW);
for(i=1;i
{
R.rhead[i]=NULL;
}
for(i=1;i
{
R.chead[i]=NULL;
}
for(k=1;k
{
printf("\n请输入第%d个非零元的行号 列号 非零元素值:",k);
scanf("%d %d %d",&i,&j,&a);
if(!(p=(OLNode *)malloc(sizeof(OLNode))))exit(OVERFLOW);
p->row=i;
p->col=j;
p->e=a;
if(R.rhead[i]==NULL||R.rhead[i]->col>j)
{
p->right=R.rhead[i];
R.rhead[i]=p;
}
else
{
for(q=R.rhead[i];(q->right)&&q->right->colright);
p->right=q->right;
q->right=p;
}
if(R.chead[j]==NULL||R.chead[j]->row>i)
{
p->down=R.chead[j];
R.chead[j]=p;
}
else
{
for(q=R.chead[j];(q->down)&&q->down->rowdown);
p->down=q->down;
q->down=p;
}
}
}
//输出十字链表的函数
void PrintSMatrix(CrossList R)
{
int i,j;
int b=0;
OLink p;
for(i=1;i
{
p=R.rhead[i];
printf("\t\t\t\t|");
for(j=1;j
{
if(p!=NULL)
{
if(j==p->col)
{
printf("%4d",p->e);
p=p->right;
}
else
printf("%4d",b);
}
else
printf("%4d",b);
}
printf(" |\n");
}
}
//实现矩阵乘法
void MultSMatrix(CrossList M,CrossList N,CrossList &Q)
{
int i,j,temp=0;
OLink q,pm,pn,pq;
Q.mu=M.mu;
Q.nu=N.nu;
Q.tu=0;
if(M.nu!=N.mu)
{
printf("这两个矩阵不能相乘!");
exit(OVERFLOW);
} //矩阵相乘条件,矩阵1的行数必须等于矩阵2的列数
if(M.tu*N.tu!=0)
{
for(i=1;i
{
for(j=1;j
{
temp=0;
pm=M.rhead[i];
pn=N.chead[j];
while(pm)
{
while(pn&&pm&&(pm->col>pn->row))
{if(pn->down!=NULL)
pn=pn->down;
else pn=NULL;
}
if((pm&&pn&&pm->col==pn->row))
{
temp+=(pm->e)*(pn->e);
if(pm->right!=NULL) pm=pm->right;
else pm=NULL;
if(pn->down!=NULL) pn=pn->down;
else pn=NULL;
}
else
{if(pm->right!=NULL) pm=pm->right;
else pm=NULL;}
}//while(pm)
if(temp)
{
if(!(pq=(OLNode *)malloc(sizeof(OLNode))))exit(OVERFLOW);
pq->row=i;
pq->col=j;
pq->e=temp;
if(Q.rhead[i]==NULL||Q.rhead[i]->col>j)
{
pq->right=Q.rhead[i];
Q.rhead[i]=pq;
}
else
{
for(q=Q.rhead[i];(q->right)&&q->colright);
pq->right=q->right;
q->right=pq;
}
if(Q.chead[j]==NULL||Q.chead[j]->row>i)
{
pq->down=Q.chead[j];
Q.chead[j]=pq;
}
else
{
for(q=Q.chead[j];(q->down)&&q->rowdown);
pq->down=q->down;
q->down=pq;
}
(Q.tu)++;
}//if temp
}//for j
}//for i
}//for if
}//MultSMatrix()
//实现矩阵加法
int AddMatrix(CrossList M,CrossList N,CrossList &Q)
{ /* 初始条件: 稀疏矩阵M与N的行数和列数对应相等。 */ /* 操作结果: 求稀疏矩阵的差Q=M+N */
int i,k;
OLink p,pq,pm,pn;
OLink *col;
if(M.mu!=N.mu||M.nu!=N.nu)
{
printf("两个矩阵不是同类型的,不能相加\n");
exit(OVERFLOW);
}
Q.mu=M.mu; /* 初始化Q矩阵 */
Q.nu=M.nu;
Q.tu=0; /* 元素个数的初值 */
Q.rhead=(OLink*)malloc((Q.mu+1)*sizeof(OLink));
if(!Q.rhead)
exit(OVERFLOW);
Q.chead=(OLink*)malloc((Q.nu+1)*sizeof(OLink));
if(!Q.chead)
exit(OVERFLOW);
for(k=1;k
for(k=1;k
Q.chead[k]=NULL;
col=(OLink*)malloc((Q.nu+1)*sizeof(OLink)); /* 生成指向列的最后结点的数组 */ if(!col)
exit(OVERFLOW);
for(k=1;k
col[k]=NULL;
for(i=1;i
{
pm=M.rhead[i]; /* pm指向矩阵M的第i行的第1个结点 */ pn=N.rhead[i]; /* pn指向矩阵N的第i行的第1个结点 */ while(pm&&pn) /* pm和pn均不空 */
{
if(pm->colcol) /* 矩阵M当前结点的列小于矩阵N当前结点的列 */
{
p=(OLink)malloc(sizeof(OLNode)); /* 生成矩阵Q的结点 */
if(!p)
exit(OVERFLOW);
Q.tu++; /* 非零元素数加1 */
p->row=i;
p->col=pm->col;
p->e=+pm->e;
p->right=NULL;
pm=pm->right; /* pm指针向右移 */
}
else if(pm->col>pn->col) /* 矩阵M当前结点的列大于矩阵N当前结点的列 */
{
p=(OLink)malloc(sizeof(OLNode)); /* 生成矩阵Q的结点 */
if(!p)
exit(OVERFLOW);
Q.tu++; /* 非零元素数加1 */
p->row=i;
p->col=pn->col;
p->e=+pn->e;
p->right=NULL;
pn=pn->right; /* pn指针向右移 */
}
else if(pm->e+pn->e)
{
p=(OLink)malloc(sizeof(OLNode));
if(!p)
exit(OVERFLOW);
Q.tu++;
p->row=i;
p->col=pn->col;
p->e=pm->e+pn->e;
p->right=NULL;
pm=pm->right;
pn=pn->right;
}
else /* 矩阵M、N当前结点的列相等且两元素之差为0 */ {
pm=pm->right; /* pm指针向右移 */
pn=pn->right; /* pn指针向右移 */
continue;
}
if(Q.rhead[i]==NULL) /* p为该行的第1个结点 */
Q.rhead[i]=pq=p; /* p插在该行的表头且pq指向p(该行的最后一个结点) */ else /* 插在pq所指结点之后 */
{
pq->right=p; /* 完成行插入 */
pq=pq->right; /* pq指向该行的最后一个结点 */ }
if(Q.chead[p->col]==NULL) /* p为该列的第1个结点 */
Q.chead[p->col]=col[p->col]=p; /* p插在该列的表头且col[p->j]指向p */
else /* 插在col[p->]所指结点之后 */ {
col[p->col]->down=p; /* 完成列插入 */
col[p->col]=col[p->col]->down; /* col[p->j]指向该列的最后一个结点 */
}
}
while(pm) /* 将矩阵M该行的剩余元素插入矩阵Q */ {
p=(OLink)malloc(sizeof(OLNode)); /* 生成矩阵Q的结点 */
if(!p)
exit(OVERFLOW);
Q.tu++; /* 非零元素数加1 */
p->row=i; /* 给结点赋值 */
p->col=pm->col;
p->e=pm->e;
p->right=NULL;
pm=pm->right; /* pm指针向右移 */
if(Q.rhead[i]==NULL) /* p为该行的第1个结点 */
Q.rhead[i]=pq=p; /* p插在该行的表头且pq指向p(该行的最后一个结点) */
else /* 插在pq所指结点之后 */
{
pq->right=p; /* 完成行插入 */
pq=pq->right; /* pq指向该行的最后一个结点 */ }
if(Q.chead[p->col]==NULL) /* p为该列的第1个结点 */
Q.chead[p->col]=col[p->col]=p; /* p插在该列的表头且col[p->j]指向p */
else /* 插在col[p->j]所指结点之后 */ {
col[p->col]->down=p; /* 完成列插入 */
col[p->col]=col[p->col]->down; /* col[p->j]指向该列的最后一个结点 */ }
}
while(pn) /* 将矩阵N该行的剩余元素插入矩阵Q */ {
p=(OLink)malloc(sizeof(OLNode)); /* 生成矩阵Q的结点 */
if(!p)
exit(OVERFLOW);
Q.tu++; /* 非零元素数加1 */
p->row=i; /* 给结点赋值 */
p->col=pn->col;
p->e=+pn->e;
p->right=NULL;
pn=pn->right; /* pm指针向右移 */
if(Q.rhead[i]==NULL) /* p为该行的第1个结点 */
Q.rhead[i]=pq=p; /* p插在该行的表头且pq指向p(该行的最后一个结点) */
else /* 插在pq所指结点之后 */
{
pq->right=p; /* 完成行插入 */
pq=pq->right; /* pq指向该行的最后一个结点 */
}
if(Q.chead[p->col]==NULL) /* p为该列的第1个结点 */
Q.chead[p->col]=col[p->col]=p; /* p插在该列的表头且col[p->j]指向p */
else /* 插在col[p->j]所指结点之后 */ {
col[p->col]->down=p; /* 完成列插入 */
col[p->col]=col[p->col]->down; /* col[p->j]指向该列的最后一个结点 */ }
}
}
for(k=1;k
if(col[k]) /* k列有结点 */
col[k]->down=NULL; /* 令该列最后一个结点的down指针为空 */ free(col);
return OK;
}
//实现矩阵减法
int SubtSMatrix(CrossList M,CrossList N,CrossList &Q)
{ /* 初始条件: 稀疏矩阵M与N的行数和列数对应相等。 */ /* 操作结果: 求稀疏矩阵的差Q=M-N */
int i,k;
OLink p,pq,pm,pn;
OLink *col;
if(M.mu!=N.mu||M.nu!=N.nu)
{
printf("两个矩阵不是同类型的,不能相减\n");
exit(OVERFLOW);
}
Q.mu=M.mu; /* 初始化Q矩阵 */
Q.nu=M.nu;
Q.tu=0; /* 元素个数的初值 */
Q.rhead=(OLink*)malloc((Q.mu+1)*sizeof(OLink));
if(!Q.rhead)
exit(OVERFLOW);
Q.chead=(OLink*)malloc((Q.nu+1)*sizeof(OLink));
if(!Q.chead)
exit(OVERFLOW);
for(k=1;k
Q.rhead[k]=NULL;
for(k=1;k
Q.chead[k]=NULL;
col=(OLink*)malloc((Q.nu+1)*sizeof(OLink)); /* 生成指向列的最后结点的数组 */ if(!col)
exit(OVERFLOW);
for(k=1;k
col[k]=NULL;
for(i=1;i
{
pm=M.rhead[i]; /* pm指向矩阵M的第i行的第1个结点 */ pn=N.rhead[i]; /* pn指向矩阵N的第i行的第1个结点 */ while(pm&&pn) /* pm和pn均不空 */
{
if(pm->colcol) /* 矩阵M当前结点的列小于矩阵N当前结点的列 */
{
p=(OLink)malloc(sizeof(OLNode)); /* 生成矩阵Q的结点 */
if(!p)
exit(OVERFLOW);
Q.tu++; /* 非零元素数加1 */
p->row=i; /* 给结点赋值 */
p->col=pm->col;
p->e=pm->e;
p->right=NULL;
pm=pm->right; /* pm指针向右移 */
}
else if(pm->col>pn->col) /* 矩阵M当前结点的列大于矩阵N当前结点的列 */
{
p=(OLink)malloc(sizeof(OLNode)); /* 生成矩阵Q的结点 */
if(!p)
exit(OVERFLOW);
Q.tu++; /* 非零元素数加1 */
p->row=i; /* 给结点赋值 */
p->col=pn->col;
p->e=-pn->e;
p->right=NULL;
pn=pn->right; /* pn指针向右移 */
}
else if(pm->e-pn->e) /* 矩阵M、N当前结点的列相等且两元素之差不为0 */
{
p=(OLink)malloc(sizeof(OLNode)); /* 生成矩阵Q的结点 */
if(!p)
exit(OVERFLOW);
Q.tu++; /* 非零元素数加1 */
p->row=i; /* 给结点赋值 */
p->col=pn->col;
p->e=pm->e-pn->e;
p->right=NULL;
pm=pm->right; /* pm指针向右移 */
pn=pn->right; /* pn指针向右移 */
}
else /* 矩阵M、N当前结点的列相等且两元素之差为0 */ {
pm=pm->right; /* pm指针向右移 */
pn=pn->right; /* pn指针向右移 */
continue;
}
if(Q.rhead[i]==NULL) /* p为该行的第1个结点 */
Q.rhead[i]=pq=p; /* p插在该行的表头且pq指向p(该行的最后一个结点) */ else /* 插在pq所指结点之后 */
{
pq->right=p; /* 完成行插入 */
pq=pq->right; /* pq指向该行的最后一个结点 */ }
if(Q.chead[p->col]==NULL) /* p为该列的第1个结点 */
Q.chead[p->col]=col[p->col]=p; /* p插在该列的表头且col[p->j]指向p */
else /* 插在col[p->]所指结点之后 */ {
col[p->col]->down=p; /* 完成列插入 */
col[p->col]=col[p->col]->down; /* col[p->j]指向该列的最后一个结点 */
}
}
while(pm) /* 将矩阵M该行的剩余元素插入矩阵Q */ {
p=(OLink)malloc(sizeof(OLNode)); /* 生成矩阵Q的结点 */
if(!p)
exit(OVERFLOW);
Q.tu++; /* 非零元素数加1 */
p->row=i; /* 给结点赋值 */
p->col=pm->col;
p->e=pm->e;
p->right=NULL;
pm=pm->right; /* pm指针向右移 */
if(Q.rhead[i]==NULL) /* p为该行的第1个结点 */
Q.rhead[i]=pq=p; /* p插在该行的表头且pq指向p(该行的最后一个结点) */
else /* 插在pq所指结点之后 */
{
pq->right=p; /* 完成行插入 */
pq=pq->right; /* pq指向该行的最后一个结点 */ }
if(Q.chead[p->col]==NULL) /* p为该列的第1个结点 */
Q.chead[p->col]=col[p->col]=p; /* p插在该列的表头且col[p->j]指向p */
else /* 插在col[p->j]所指结点之后 */ {
col[p->col]->down=p; /* 完成列插入 */
col[p->col]=col[p->col]->down; /* col[p->j]指向该列的最后一个结点 */ }
}
while(pn) /* 将矩阵N该行的剩余元素插入矩阵Q */ {
p=(OLink)malloc(sizeof(OLNode)); /* 生成矩阵Q的结点 */
if(!p)
exit(OVERFLOW);
Q.tu++; /* 非零元素数加1 */
p->row=i; /* 给结点赋值 */
p->col=pn->col;
p->e=-pn->e;
p->right=NULL;
pn=pn->right; /* pm指针向右移 */
if(Q.rhead[i]==NULL) /* p为该行的第1个结点 */
Q.rhead[i]=pq=p; /* p插在该行的表头且pq指向p(该行的最后一个结点) */
else /* 插在pq所指结点之后 */
{
pq->right=p; /* 完成行插入 */
pq=pq->right; /* pq指向该行的最后一个结点 */
}
if(Q.chead[p->col]==NULL) /* p为该列的第1个结点 */
Q.chead[p->col]=col[p->col]=p; /* p插在该列的表头且col[p->j]指向p */
else /* 插在col[p->j]所指结点之后 */ {
col[p->col]->down=p; /* 完成列插入 */
col[p->col]=col[p->col]->down; /* col[p->j]指向该列的最后一个结点 */ }
}
}
for(k=1;k
if(col[k]) /* k列有结点 */
col[k]->down=NULL; /* 令该列最后一个结点的down指针为空 */ free(col);
return OK;
}
//主函数
void main()
{
int m,i,n;
char c;
CrossList M,N,Q;
printf(" ******** 创建稀疏矩阵 M ********* \n");
CreateSMatrix(M);
printf("\t*** 稀疏矩阵M的通常阵列形式为:\n");
PrintSMatrix(M);
printf("\n\t******** 创建稀疏矩阵 N ********\n\n");
CreateSMatrix(N);
printf("\t*** 稀疏矩阵N的通常阵列形式为:\n");
PrintSMatrix(N);
m=M.mu;
n=N.nu;
if(!(Q.rhead=(OLink*)malloc((m+1)*sizeof(OLink)))) exit(OVERFLOW); if(!(Q.chead=(OLink*)malloc((n+1)*sizeof(OLink)))) exit(OVERFLOW); for(i=1;iN.nu)?(M.mu+1):(N.nu+1));i++)
{
Q.rhead[i]=NULL;
Q.chead[i]=NULL;
}
Q.mu=M.mu;
Q.nu=N.nu;
Q.tu=0;
do
{
printf("如做加法,请输入+,如做减法,请输入-,如做乘法,请输入*:\t "); getchar();
scanf("%c",&c);
if(c=='+')
{
AddMatrix(M,N,Q);
printf("\t*** 稀疏矩阵M+N的通常阵列形式为:\n");
PrintSMatrix(Q);
}
else if(c=='-')
{
SubtSMatrix(M,N,Q);
printf("\t*** 稀疏矩阵M-N的通常阵列形式为:\n");
PrintSMatrix(Q);
}
else if(c=='*')
{
MultSMatrix(M,N,Q);
printf("\t*** 稀疏矩阵M*N的通常阵列形式为:\n");
PrintSMatrix(Q);
}
else
break;
}
while(1);
}
六、测试分析(运行结果)
七、总结(收获及体会)
通过此次的课程设计对十字链表存储的稀疏矩阵更深一步的理解和认识,一开始我们从参考书上找来了课题,但是毕竟是参考书,做到后来发现很多程序都是不完整的,这让我们伤透了脑筋。看着别的小组都弄得有模有样了,可是我们还没有一点头绪,好不容易又从网络和参考书找到了相关信息,可是结果还是很不尽人意。程序都弄好了,调试也没有问题,可是就是无法达到预期想要的结果。查阅的资料只是一个参考,最后还是要靠自己动脑筋,然后我们大家一起齐心协力,虽然内容并不是很复杂,但是我们觉得设计的过程相当重要,学到了很多,收获了很多。我觉得课程设计反映的是一个从理论到实际应用的过程,但是更远一点可以联系到以后毕业之后从学校转到踏上社会的一个过程。小组人员的配合﹑相处,以及自身的动脑和努力,都是以后工作中需要的。
八、参考文献
数据结构(C语言版)严蔚敏 吴伟明 编著 清华大学出版社
五、调试分析
1、本程序中相乘部分较易,但是相加的部分则是让人伤脑筋,但最还仔细分析还是可以实现的。
2、在用十字链表表示稀疏矩阵时,相加或相减所得的结果应该另生成,乘积矩阵也可用二维数组表示。
3、通过数据的测试,能按要求实现功能。