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

课程设计

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

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

框架搭建：
1选择File|New菜单项，弹出New对话框，选择Files标签，选中C++ Source File项，在File编辑器中输入项目名称“十字链表表示稀疏矩阵实现加法”，在Location编辑框中输入项目所在目录，按下OK按钮即可。
2在操作界面中输入，程序代码。
（1） 结构体和共用体的定义
#include<stdio.h>
#include<malloc.h>
#define smax 45
typedef int datatype;
typedef struct lnode
（2） 建立稀疏矩阵的函数，返回十字链表头指针
int i,j;
struct lnode *cptr,*rptr;
union
{
struct lnode *next;
datatype v;
}uval;
}link;
int flag=0;
建立十字链表头结点
head=(link *)malloc(sizeof(link));
建立头结点循环链表
for(i=1;i<=s;i++)
（3） 插入结点函数
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;
}
return head;
（4） 输出十字链表的函数
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）定义两个矩阵的非零元素，及两个矩阵的行和列数。然后输入非零元素。将两个用十字链表表示的稀疏矩阵显示出来。
void print(link *a)
{
link *p,*q,*r;
int k,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;
int s,i;
if(a->i!=b->i||a->j!=b->j)
{ flag=1;return NULL; }
（5） 建立相加矩阵c的表头环链
c=(link *)malloc(sizeof(link));
c->i=a->i;c->j=a->j;
if(c->i>c->j)s=c->i; else s=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;
}
cp[s]->uval.next =c;
考虑复杂问题，实现矩阵相加。
p=a->uval.next;u=b->uval.next;
while(p!=a&&u!=b)
{
q=p->rptr;v=u->rptr;
if(q==p&&v!=u)
while(v!=u)
{insert(v->i,v->j,v->uval.v,cp);v=v->rptr;}
else if(v==u&&q!=p)
while(q!=p)
{insert(q->i,q->j,q->uval.v,cp);q=q->rptr;}
else if(q!=p&&v!=u)
{
while(q!=p&&v!=u)
{
if(q->j<v->j)
{insert(q->i,q->j,q->uval.v,cp);q=q->rptr;}
else if(q->j>v->j)
{insert(v->i,v->j,v->uval.v,cp);v=v->rptr;}
else
{if(q->uval.v+v->uval.v!=0)insert(q->i,q->j,(q->uval.v+v->uval.v),cp);
q=q->rptr;v=v->rptr;
}
}
if(q==p&&v!=u)
while(v!=u)
{insert(v->i,v->j,v->uval.v,cp);v=v->rptr;}
else if(v==u&&q!=p)
while(q!=p)
{insert(q->i,q->j,q->uval.v,cp);q=q->rptr;}
else;
}
else ;

p=p->uval.next;u=u->uval.next;
}
return c;
}
（6） 编写主函数
void main()
{
link *a,*b,*c;
a=creatlinkmat();print(a);
b=creatlinkmat();print(b);
c=add(a,b);
if(flag==1)printf("矩阵a、b不能相加!!");
else printf("和矩阵c为：\n");print(c);
}

实验总结：应掌握稀疏矩阵的各种表示方法。学会实现两个稀疏矩阵的加法运算。对十字链表法应熟练掌握。考虑矩阵相加时，情况要考虑全面。在输入出错时，要及时提示提醒操作者，该行为不能再继续运行该程序。