首页 > 代码库 > C语言：十字链表的相加相减
C语言：十字链表的相加相减
#include<stdio.h>
#include<stdlib.h>
#define N 100
typedef struct node
{
int row, col;
int v;
struct node *r, *d;
}*link;
typedef struct crosslist
{
link rowhead[N], colhead[N];
int rows, cols, nums;
}*list;
int i, j;
list init(list cl);
list copy(list s1);
list add(list a, list b);
list sub(list s1, list s2);
void output(list cl);
list init(list cl)
{
link p, q, s;
int n, m, data;
cl=(list)malloc( sizeof(struct crosslist) );
if( !cl )
{
printf("\n无法生成十字链表\n");
return 0;
}
printf("\n矩阵总行数: ");
scanf("%d", &n);
printf("\n矩阵总列数: ");
scanf("%d", &m);
cl->rows=n;
cl->cols=m;
cl->nums=0;
for(i=0; i<n; i++)
{
cl->rowhead[i]=(link )malloc( sizeof(struct node) );
cl->rowhead[i]->r=NULL;
}
for(j=0; j<m; j++)
{
cl->colhead[j]=(link )malloc( sizeof(struct node) );
cl->colhead[j]->d=NULL;
}
for(i=0; i<n; i++)
{
printf("\n第%d行:", i+1);
q=cl->rowhead[i];
for(j=0; j<m; j++)
{
scanf("%d", &data);
if(data != 0)
{
p=(link)malloc( sizeof(struct node) );
p->v=data;
p->row=i+1;
p->col=j+1;
cl->nums++;
p->r=q->r;
q->r=p;
q=p;
s=cl->colhead[j];
while( s->d )
s=s->d;
p->d=s->d;
s->d=p;
}
}
}
return cl;
}
list copy(list s1)
{
list s3;
link p, q, t, s;
s3=(list)malloc( sizeof(struct crosslist) );
if( !s3 )
{
printf("\n无法生成十字链表\n");
return 0;
}
s3->rows=s1->rows;
s3->cols=s1->cols;
s3->nums=s1->nums;
for(i=0; i<s3->rows; i++)
{
s3->rowhead[i]=(link )malloc( sizeof(struct node) );
s3->rowhead[i]->r=NULL;
}
for(j=0; j<s3->cols; j++)
{
s3->colhead[j]=(link )malloc( sizeof(struct node) );
s3->colhead[j]->d=NULL;
}
for(i=0; i<=s3->rows-1; i++)
{
p=s1->rowhead[i]->r;
q=s3->rowhead[i];
for(j=0; j<=s3->cols-1; j++)
{
if( !p )
{
break;
}
else
if(p->row==i+1 && p->col==j+1)
{
t=(link)malloc( sizeof(struct node) );
t->v=p->v;
t->row=i+1;
t->col=j+1;
t->r=q->r;
q->r=t;
q=t;
s=s3->colhead[j];
while( s->d )
s=s->d;
t->d=s->d;
s->d=t;
p=p->r;
}
}
}
return s3;
}
list add(list a, list b)//s1 = s1+s2;
{
list s1, s2;//复制矩阵a, b
link p, q, t, p1;
int count=0;
s1=copy(a);
s2=copy(b);
for(i=0; i<s1->rows; i++)
{
p=s1->rowhead[i];//按行序升序把第二个矩阵与第一个矩阵相加，一行一行相加
q=s2->rowhead[i]->r;
while(q)
{
if( !p->r )//q插入，第二个矩阵插入
{
p->r=q;//行连接,一个一个来
p1=s1->colhead[q->col-1];//列连接
while( p1->d && p1->d->row < q->row )
{
p1=p1->d;
}
q->d=p1->d;
p1->d=q;//
p=p->r;
q=q->r;
p->r=NULL;
count++;
continue;
}
if( p->r->col < q->col)
{
p=p->r;
count++;
continue;
}
if( p->r->col > q->col)
{
t=q->r;//保存q->r;
q->r=p->r; p->r=q;//行连接
p1=s1->colhead[q->col-1];//列连接
while( p1->d && p1->d->row < q->row )
{
p1=p1->d;
}
q->d=p1->d;
p1->d=q;
p=p->r; q=t;//下一轮比较
count++;
continue;
}
if(p->r->col == q->col)
{
p->r->v += q->v;
if(p->r->v != 0)
{
count++;
p=p->r;
q=q->r;
}
else
{
count--;
t=p->r;//行连接
p->r=t->r;
p1=s1->colhead[q->col-1]; //列是[0~~cols];
while( p1->d->row < q->row)
{
p1=p1->d;
}
p1->d=t->d;
free(t);
q=q->r;
}
}
}
}
s1->nums=count;
return s1;
}
list sub(list a, list b)//s1 = s1-s2;
{
list s1, s2;//复制矩阵a, b
link p, q, t, p1;
int count=0;
s1=copy(a);
s2=copy(b);
for(i=0; i<s1->rows; i++)
{
p=s1->rowhead[i];//按行序升序把第二个矩阵与第一个矩阵相加，一行一行相加
q=s2->rowhead[i]->r;
while(q)
{
if( !p->r )//q插入，第二个矩阵插入
{
q->v=0-q->v;
p->r=q;//行连接,一个一个来
p1=s1->colhead[q->col-1];//列连接
while( p1->d && p1->d->row < q->row )
{
p1=p1->d;
}
q->d=p1->d;
p1->d=q;//
p=p->r;
q=q->r;
p->r=NULL;
count++;
continue;
}
if( p->r->col < q->col)
{
p=p->r;
count++;
continue;
}
if( p->r->col > q->col)
{
q->v = 0-q->v;
t=q->r;//保存q->r
q->r=p->r; p->r=q;//行连接
p1=s1->colhead[q->col-1];//列连接
while( p1->d && p1->d->row < q->row )
{
p1=p1->d;
}
q->d=p1->d;
p1->d=q;
p=p->r; q=t;//下一轮比较
count++;
continue;
}
if(p->r->col == q->col)
{
p->r->v -= q->v;
if(p->r->v != 0)
{
count++;
p=p->r;
q=q->r;
}
else
{
count--;
t=p->r;//行连接
p->r=t->r;
p1=s1->colhead[q->col-1]; //列是[0~~cols];
while( p1->d->row < q->row)
{
p1=p1->d;
}
p1->d=t->d;
free(t);
q=q->r;
}
}
}
}
s1->nums=count;
return s1;
}
void output(list cl)
{
link p;
puts("\n");
for(i=0; i<cl->rows; i++)
{
p=cl->rowhead[i]->r;
while(p)
{
printf("(%d,%d) %d\t", p->row,p->col,p->v);
p=p->r;
}
}
puts("\n");
for(i=0; i<cl->rows; i++)
{
p=cl->rowhead[i]->r;
printf("\t\t");
for(j=0; j<cl->cols; j++)
{
if(p && p->row==i+1 && p->col==j+1)
{
printf("%3d", p->v);
p=p->r;
}
else
printf(" 0");
}
printf("\n");
}
puts("\n");
}
void output_2(list cl)
{
link p;
putchar('\n');
for(i=0; i<cl->cols; i++)
{
p=cl->colhead[i]->d;
while(p)
{
printf("(%d,%d) %d\t", p->row,p->col,p->v);
p=p->d;
}
}
putchar('\n');
}
void main()
{
list a, b, s;
a=init(a);
output(a);
b=init(b);
output(b);
puts("\n\t\t A + B");
s=add(a, b);
output(s);
puts("\n\t\t A - B");
s=sub(a, b);
output(s);
}
C语言：十字链表的相加相减
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。