十字链表稀疏矩阵的加法(用十字链表实现A=A+B)

码拜

8年 ago

题目：
描述：
输入两个稀疏矩阵A和B，用十字链表实现A=A+B，输出它们相加的结果。
输入：
第一行输入四个正整数，分别是两个矩阵的行m、列n、第一个矩阵的非零元素的个数t1和第二个矩阵的非零元素的个数t2，接下来的t1+t2行是三元组，分别是第一个矩阵的数据和第二个矩阵的数据, 三元组的第一个元素表示行,第二个元素表示列,第三个元素是该元素的值。
输出：
输出相加后的矩阵三元组。
输入样例：
3 4 3 2
1 1 1
1 3 1
2 2 2
1 2 1
2 2 3
输出样例：
1 1 1
1 2 1
1 3 1
2 2 5

求高手看看代码为什么输出超限。好像是个别数据点有问题

#include <stdio.h>
#include<stdlib.h>
typedef struct OLNODE
{
    int row,col;
    int data;
    struct OLNODE *right,*down;
} NODE,*LNODE;
typedef struct CORSS
{
    LNODE *rh,*ch; //行列的头指针，实际只用到了行指针
    int ra,ca,da;//行数、列数、非零元个数
} CROSS, *LCROSS;
void Create(LCROSS A);//创建链表表示稀疏矩阵
void PlusToA(LCROSS A,LCROSS B);//加，并保存到A中
void PrintCross(LCROSS A);//输出
int main()
{
    LCROSS A = (LCROSS)malloc(sizeof(CROSS));
    LCROSS B = (LCROSS)malloc(sizeof(CROSS));
    scanf("%d %d %d %d",&A->ra,&A->ca,&A->da,&B->da);
    B->ra = A->ra;
    B->ca = A->ca;
    Create(A);
    Create(B);
    PlusToA(A,B);
    PrintCross(A);
    return 0;
}
void Create(LCROSS M)
{
    int i;
    LNODE p,temp;
    M->rh = (LNODE *)malloc((M->ra+1)*sizeof(LNODE));
    M->ch = (LNODE *)malloc((M->ca+1)*sizeof(LNODE));
    for(i=1; i<=M->ra; i++)
    {
        M->rh[i]=NULL;
    }
    /*for(i=1; i<=M->ca; i++)
    {
        M->ch[i]=NULL;
    }*/
    if(M->da != 0)
    {
        for(i=1; i<=M->da; i++)
        {
            p=(LNODE)malloc(sizeof(NODE));
            scanf("%d %d %d",&p->row,&p->col,&p->data);
            if(M->rh[p->row] == NULL)
            {
                p->right=NULL;
                M->rh[p->row] = p;
            }
            else
            {
                for(temp=M->rh[p->row];; temp=temp->right)
                {
                    if(temp->right == NULL)
                    {
                        temp->right = p;
                        p->right =NULL;
                        break;
                    }
                    else if(temp->col < p->col && temp->right->col>p->col)
                    {
                        p->right = temp->right;
                        temp->right = p;
                        break;
                    }
                    else if(temp==M->rh[p->row] && temp->col>p->col)
                    {
                        p->right = temp;
                        temp=p;
                        break;
                    }
                }
            }
   /*         if(M->ch[p->col] == NULL|| M->ch[p->col]->row>(p->row))
            {
                p->down=M->ch[p->col];
                M->ch[p->col] = p;
            }
            else
            {
                for(temp=M->ch[p->col]; temp->down && temp->down->row<p->row; temp=temp->down);
                p->down = temp->down;
                temp->down = p;
            }*/
        }
    }
}
void PlusToA(LCROSS A,LCROSS B)
{
    int i;
    LNODE p,temp1,temp2;
    for(i=1; i<=A->ra; i++)
    {
        if(B->rh[i] == NULL) continue;
        else
        {
            if(A->rh[i] == NULL)
            {
                p=(LNODE)malloc(sizeof(NODE));
                p->col = B->rh[i]->col;
                p->row = B->rh[i]->row;
                p->data = B->rh[i]->data;
                A->rh[i]=p;
                p->right = NULL;
                B->rh[i]=B->rh[i]->right;
            }
            if(B->rh[i]==NULL)continue;
            for(temp1=B->rh[i];; temp1=temp1->right)
            {
                for(temp2=A->rh[i];; temp2=temp2->right)
                {
                    if(temp2->col == temp1->col)
                    {
                        temp2->data+=temp1->data;
                        break;
                    }
                    else if(temp2==A->rh[i] && temp1->col<temp2->col)
                    {
                        p=(LNODE)malloc(sizeof(NODE));
                        p->col = temp1->col;
                        p->row = temp1->row;
                        p->data = temp1->data;
                        p->right = temp2->right;
                        temp2->right=temp2;
                        temp2 = p;
                        break;
                    }
                    else if((temp2->right == NULL || temp2->right->col>temp1->col)  && temp1->col>temp2->col)
                    {
                        p=(LNODE)malloc(sizeof(NODE));
                        p->col = temp1->col;
                        p->row = temp1->row;
                        p->data = temp1->data;
                        p->right = temp2->right;
                        temp2->right=p;
                        break;
                    }
                }
                if(temp1->right == NULL) break;
            }
        }
    }
}
void PrintCross(LCROSS A)
{
    int i;
    LNODE p;
    for(i=1; i<=A->ra; i++)
    {
        p=A->rh[i];
        while(p!=NULL)
        {
            printf("%d %d %d\n",p->row,p->col,p->data);
            p=p->right;
        }
    }
}

解决方案

100

参考

A--矩阵A ，B--矩阵B，C--矩阵C
用p，q控制A的行列
用u，v控制B的行列
#include<stdio.h>
#include<malloc.h>
#define smax 45
typedef int datatype;
typedef struct lnode   //结构体和共用体的定义
{
int i,j;
struct lnode *cptr,*rptr;
union
{
   struct lnode *next;
   datatype v;
}uval;
}link;
int flag=0;
//建立稀疏矩阵的函数，返回十字链表头指针
link *creatlinkmat()
{
link *p,*q,*head,*cp[smax];
int i,j,k,m,n,t,s;
datatype v;
printf("输入行、列，非零元素个数(m,n,t数字间用逗号分隔)");
scanf("%d,%d,%d",&m,&n,&t);//输入行、列，非零元素个数 
if(m>n)s=m; else s=n;  
head=(link *)malloc(sizeof(link));   //建立十字链表头结点
head->i=m;head->j=n;
cp[0]=head;    //cp[]是指针数组，分别指向头结点和行、列表头结点
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;
}
return head;
}
//插入结点函数
void insert(int i,int j,int v,link *cp[])
{
link *p,*q;
p=(link *)malloc(sizeof(link));
p->i=i;p->j=j;p->uval.v=v;
//以下是经*p结点插入第i行链表中  
q=cp[i];
while((q->rptr!=cp[i])&&(q->rptr->j<j))
   q=q->rptr;//在第i行中找第一个列号大于j的结点*(q->rptr)
//找不到时，*q是该行表上的尾结点
p->rptr=q->rptr;
q->rptr=p;//*p插入在*q之后
//以下是将结点插入第j列链表中
q=cp[j];//取第j列表头结点
while((q->cptr!=cp[j])&&(q->cptr->i<i))
   q=q->cptr ;//在第j行中找第一个列号大于i的结点*(q->cptr)
//找不到时，*q是该行表上的尾结点
p->cptr=q->cptr;
q->cptr=p;//*p插入在*q之后
}
//输出十字链表的函数
void print(link *A)
{
link *p,*q,*r;//p是控制行q是控制列r是控制输出的格式
int k,col,t,row; 
col=A->j;//矩阵A的列数
printf("矩阵为：\n");
p=A->uval.next;//p指向第一个结点（不是头结点）
while(p!=A)
{
   q=p->rptr;//p指向这以一行的一个值
   if(q==A->cptr)break;//假如行或列处理完了，跳出
   r=p;//r指向这一行的头结点
   while(q!=p)
   {
    for(k=1;k<q->j-(r->j);k++)//输出同一行上两非零数据间的零
     printf(" 0");
    printf("%3d",q->uval.v);//输出那个非零值
    q=q->rptr;//q指向这一行的下一个元素
    r=r->rptr;//r指向q前面的一个非零元素 
   }
   k=r->j;//k的值是某一行的最后一个非零元的列数
   for(t=k;t<col;t++)//输出一行上最后一个非零元后面的零
    printf(" 0");
   printf("\n");
   p=p->uval.next;//p指向下一行
}
}
link *add(link *a,link *b)
{
link *p,*q,*u,*v,*r,*cp[smax],*c;//p,q控制十字链a的行列,u,v控制十字链b的行列
int s,i;
if(a->i!=b->i||a->j!=b->j)
{ flag=1;return NULL; }
//建立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)//矩阵a中第p行为空，矩阵b的第u行不为空
    while(v!=u)//将b的行的都复制到和矩阵中
    {insert(v->i,v->j,v->uval.v,cp);v=v->rptr;}
   else if(v==u&&q!=p)//矩阵a中第p行不为空，矩阵b的第u行为空
    while(q!=p)
    {insert(q->i,q->j,q->uval.v,cp);q=q->rptr;}
   else if(q!=p&&v!=u)//矩阵b的第u行和矩阵a的第p行都不为空
   {
    while(q!=p&&v!=u)
    {
     if(q->j<v->j)//假如a中有元素的列数小于b的，将a中的全部小于b的值都插到c中
     {insert(q->i,q->j,q->uval.v,cp);q=q->rptr;}
     else if(q->j>v->j)//假如b中有元素的列数小于a的，将a中的全部小于b的值都插到c中
     {insert(v->i,v->j,v->uval.v,cp);v=v->rptr;}
     else//a、b当前是在同一个位置，判断加的和能否为零，不为零才做加法运算
     {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)//假如b未处理完，将b中未处理的值都插入到和矩阵中
     while(v!=u)
     {insert(v->i,v->j,v->uval.v,cp);v=v->rptr;}
    else if(v==u&&q!=p)//假如a未处理完，将a中未处理的值都插入到和矩阵中
      while(q!=p)
      {insert(q->i,q->j,q->uval.v,cp);q=q->rptr;}
    else; //都处理完了，什么都不做
   }
   else ; //矩阵b的第u行和矩阵a的第p行都为空，什么都不做
   
   p=p->uval.next;u=u->uval.next;//a、b都指向下一行
}
return c;
}
//
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); 
}