稀疏矩阵加法（十字链表） 问题描述输入输出输入输出样例代码
问题描述
若将稀疏矩阵 mathbf{A}A 的非零元素以行序为主序的顺序存于一维数组 VV 中，并用二维数组 BB 表示 AA 中的相应元素是否为零元素（以0和1分别表示零元素和非零元素）。例如，
可以使用一个数组和一个01矩阵表示
试写一算法，实现在上述表示法中实现矩阵相加的运算。并分析你的算法时间复杂度（在代码注释中给出）。
文章目录 问题描述输入输出输入输出样例代码
输入
输出
输入输出样例
输入：
2 2
1 1
1 0
0 1
-2 -1
1 0
0 1
输出：
-1
1 0
0 0
代码 #include <stdio.h>#include <stdlib.h>//十字链表的结点typedef struct olnode{ //line int i; //row int j; //elemtype int e; //right struct olnode *right; //down struct olnode *down;}ol;//存储行和列的头typedef struct { ol *rhead[100]; ol *chead[100]; //line int mu; //row int nu; //element int tu;}crosslist;//申请内存ol *lalloc(void){ return (ol *)malloc(sizeof(ol));}int main(){ int m,n; //读入行数和列数 scanf("%d %dn",&m,&n); //获取输入并返回数组长度 int getinput(int *p); //获取输入的矩阵 crosslist getarray(crosslist p,int v[]); //初始化头链表 crosslist initialhead(crosslist p); //相加 crosslist addarray(crosslist a,crosslist b); void addnode(crosslist p,int ia,int ja,int k,int v[]); //打印v数组 void printv(crosslist a); //打印01矩阵 void printm(crosslist a); //根据行数和列数 int va[m*n]; int vb[m*n]; int vc[m*n]; //存储行和列的头 crosslist listheada; crosslist listheadb; listheada.mu=m; listheada.nu=n; listheadb.mu=m; listheadb.nu=n; listheada=initialhead(listheada); listheadb=initialhead(listheadb); //读入va listheada.tu=getinput(va); int i,j; //读入数组a listheada=getarray(listheada,va); //读入vb listheadb.tu=getinput(vb); //读入数组b listheadb=getarray(listheadb,vb); //相加 listheada=addarray(listheada,listheadb); //输出 printv(listheada); printm(listheada); return 0;}//读入数组va，p为数组名int getinput(int *p){ int c; int i=0; //符号位 int sig=1;c=getchar(); if(c=='n'){ c=getchar(); } while(c!='n'){ sig=1;//printf("readn"); if(c==' '){ i++; c=getchar(); } if(c=='-'){ sig=-1; c=getchar(); } p[i]=c-'0'; while((c=getchar())!='n'&&c!=' '){ p[i]=p[i]*10+c-'0'; } //符号位 p[i]=p[i]*sig; } return i+1;}//读入二维数组作为矩阵，p为二维数组名crosslist getarray(crosslist p,int v[]){ int i,j; //表示获取的输入的值 int c; //对v数组计数 int k=0; ol *pwork; ol *ppoint; for(i=0;i<p.mu;i++){ for(j=0;j<p.nu;j++){ scanf("%d",&c); if(c==1){ //addnode(p,i,j,k,v); ppoint=lalloc(); ppoint->i=i; ppoint->j=j; ppoint->e=v[k]; //此处应初始化为null不然扫描时可能会出错吧 ppoint->down=NULL; ppoint->right=NULL; //先完成行插入 pwork=p.rhead[i]; while(pwork->right!=NULL){ pwork=pwork->right; } pwork->right=ppoint; //完成列插入 pwork=p.chead[j]; while(pwork->down!=NULL){ pwork=pwork->down; } pwork->down=ppoint; k++; } } } return p;}//在十字链表中增加结点，i,j为行，k为va中的位置//行和列的头初始化crosslist initialhead(crosslist p){ int i; ol *pwork; //将行的头结点初始化 for(i=0;i<p.mu;i++){ pwork=lalloc(); pwork->down=NULL; pwork->right=NULL; p.rhead[i]=pwork; } //将列的头结点初始化 for(i=0;i<p.nu;i++){ pwork=lalloc(); pwork->down=NULL; pwork->right=NULL; p.chead[i]=pwork; } return p;}//O(ta+tb)，//因为输出只要打印所以输出破坏了链表，//列并没有连接，只连接了行crosslist addarray(crosslist a,crosslist b){ int i,j; ol *pa; ol *pb; ol *pre; //记录pa和pb下一个要处理的结点 ol *pbnext; //ol *panext; //逐行扫描 for(i=0;i<a.mu;i++){ //初始化行 pa=a.rhead[i]->right; pre=a.rhead[i]; pb=b.rhead[i]->right; //扫描pb并将其中行结点插入a中 while(pb!=NULL){ pbnext=pb->right; if(pa==NULL || pa->j>pb->j){ //需要新增结点，pa不需要移动 pb->right=pa; pre->right=pb; pre=pb; //处理完当前pb结点，移到下一个 pb=pbnext; //多了一个数 a.tu++; }else if(pa!=NULL && pa->j<pb->j){ //pb没有对应结点，不操作，pa需要移动 pre=pa; pa=pa->right; //未处理pb结点，不移动 }else if(pa->j==pb->j){ //pa,pb同时有，增加 pa->e+=pb->e; //此处pa是否移动都可以吧 //不可以！！！ //pa=pa->right; //和为0，删除该结点 if(pa->e==0){ pre->right=pa->right; pa=pa->right; //少了一个数 a.tu--; } //pa=pa->right; //处理了pb结点，移动 pb=pbnext; } } } return a;}//怎么能不输出空格啊//有了，记录有多少数void printv(crosslist a){ int i; ol *p; int count=0; if(a.tu==0)printf("n"); for(i=0;i<a.mu;i++){ p=a.rhead[i]->right; while(p!=NULL){ count++; if(count<a.tu){ printf("%d ",p->e); }else if(count==a.tu){ printf("%dn",p->e); }else{ printf("n"); } p=p->right; } }}void printm(crosslist a){ int i,j; ol *p; for(i=0;i<a.mu;i++){ p=a.rhead[i]->right; for(j=0;j<a.nu-1;j++){ if(p!=NULL && j<p->j){ printf("0 "); }else if(p!=NULL && j==p->j){ printf("1 "); //打印当前结点，右移 p=p->right; }else if(p!=NULL && j>p->j){ printf("error:j>p->jn"); }else if(p==NULL){ printf("0 "); } } //打印最后一个结点 if(p==NULL){ printf("0n"); }else{ printf("1n"); } }}
原本是将addnode单独写为一个函数，但是不知为何一直报错，所以就直接将代码加到getarray中了
备注写的很详细呀，如果有什么问题欢迎一起讨论~