采用十字链表表示稀疏矩阵,并实现矩阵的加法运算.doc

课程设计

所抽题目：采用十字链表表示稀疏矩阵，并实现矩阵的加法运算。
要求：要检查有关运算的条件，并对错误的条件产生报警。

问题分析和建立模型：本题目主要是运用所学知识，用十字链表的方法去表示稀疏矩阵，并使之可以在两矩阵间进行相加。而后，若有错误，则对错误进行警报。

框架搭建：
1选择File|New菜单项，弹出New对话框，选择Files标签，选中C++SourceFile项，在File编辑器中输入项目名称“十字链表表示稀疏矩阵实现加法”，在Location编辑框中输入项目所在目录，按下OK按钮即可。
2在操作界面中输入，程序代码。
结构体和共用体的定义
#include<stdio.h>
#include<malloc.h>
#definesmax45
typedefintdatatype;
typedefstructlnode
建立稀疏矩阵的函数，返回十字链表头指针
inti,j;
structlnode*cptr,*rptr;
union
{
structlnode*next;
datatypev;
}uval;
}link;
intflag=0;
建立十字链表头结点
head=(link*)malloc(sizeof(link));
建立头结点循环链表
for(i=1;i<=s;i++)
插入结点函数
p=(link*)malloc(sizeof(link));
p->i=0;p->j=0;
p->rptr=p;p->cptr=p;
cp[i]=p;cp[i-1]->uval.next=p;
}
cp[s]->uval.next=head;
for(k=1;k<=t;k++)
{
printf("\t第%d个元素(行号i列号j值v，数字间用空格分隔):",k);
scanf("%d%d%d",&i,&j,&v);
p=(link*)malloc(sizeof(link));
p->i=i;p->j=j;p->uval.v=v;
q=cp[i];
while((q->rptr!=cp[i])&&(q->rptr->j<j))
q=q->rptr;
p->rptr=q->rptr;
q->rptr=p;
q=cp[j];
while((q->cptr!=cp[j])&&(q->cptr->i<i))
q=q->cptr;
p->cptr=q->cptr;
q->cptr=p;
}
returnhead;
输出十字链表的函数
link*p,*q;
p=(link*)malloc(sizeof(link));
p->i=i;p->j=j;p->uval.v=v;

q=cp[i];
while((q->rptr!=cp[i])&&(q->rptr->j<j))
q=q->rptr;
p->rptr=q->rptr;
q->rptr=p;
q=cp[j];
while((q->cptr!=cp[j])&&(q->cptr->i<i))
q=q->cptr;
p->cptr=q->cptr;
q->cptr=p;
（5）定义两个矩阵的非零元素，及两个矩阵的行和列数。然后输入非零元素。将两个用十字链表表示的稀疏矩阵显示出来。
voidprint(link*a)
{
link*p,*q,*r;
intk,col,t,row;
col=a->j;
printf("矩阵为：\n");
p=a->uval.next;
while(p!=a)
{
q=p->rptr;
if(q==a->cptr)break;
r=p;
while(q!=p)
{
for(k=1;k<q->j-(r->j);k++)
printf("0");
printf("%3d",q->uval.v);
q=q->rptr;
r=r->rptr;
}
k=r->j;
for(t=k;t<col;t++)
printf("0");
printf("\n");
p=p->uval.next;
}
}
link*add(link*a,link*b)
{
link*p,*q,*u,*v,*r,*cp[smax],*c;
ints,i;
if(a->i!=b->i||a->j!=b->j)
{flag=1;returnNULL;}
建立相加矩阵c的表头环链
c=(link*)malloc(sizeof(link));
c->i=a->i;c->j=a->j;
if(c->i>c->j)s=c->i;elses=c->j;
cp[0]=c;
for(i=1;i<=s;i++)
{
r=(link*)malloc(sizeof(link));
r->i=0;r->j=0;
r->rptr=r;r->cptr=r;
cp[i]=r;
cp[i-1]->uval.next=r;
}