精华内容
下载资源
问答
  • 稀疏矩阵加法

    2021-04-21 17:36:30
    稀疏矩阵加法代码总结 代码 SparseMatrix operator+(const SparseMatrix& b) { SparseMatrix res(rn,cn,vn+b.vn); SparseMatrix &a = (*this);//这一步保证可以使用a.row等 int i = 1, j = 1; while ...

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档

    稀疏矩阵加法

    代码

      SparseMatrix operator+(const SparseMatrix& b)
        {
            SparseMatrix res(rn,cn,vn+b.vn);
            SparseMatrix &a = (*this);//有这行就可以使用a.row等写代码了,可以区分地更加清楚
            int i, j;
            for (i = 1, j = 1, res.vn = 1; i <= a.vn && j <= b.vn; )
            {
                if (a.row[i] < b.row[j])
                {
                    res.row[res.vn] = a.row[i];
                    res.col[res.vn] = a.col[i];
                    res.val[res.vn] = a.val[i];
                    res.vn++;
                    i++;
                }
                else if (a.row[i] > b.row[j])
                {
                    res.row[res.vn] = b.row[j];
                    res.col[res.vn] = b.col[j];
                    res.val[res.vn] = b.val[j];
                    res.vn++;
                    j++;
                }
                else
                {
                    if (a.col[i] < b.col[j])
                    {
                        res.row[res.vn] = a.row[i];
                        res.col[res.vn] = a.col[i];
                        res.val[res.vn] = a.val[i];
                        res.vn++;
                        i++;
                    }
                    else if (a.col[i] > b.col[j])
                    {
                        res.row[res.vn] = b.row[j];
                        res.col[res.vn] = b.col[j];
                        res.val[res.vn] = b.val[j];
                        res.vn++;
                        j++;
                    }
                    else
                    {
                        if (a.val[i] + b.val[j] != 0)
                        {
                            res.row[res.vn] = a.row[i];
                            res.col[res.vn] = a.col[i];
                            res.val[res.vn] = a.val[i] + b.val[j];
                            res.vn++;
                        }
                        i++, j++;//注意这个地方不管是否是0都要遍历下一个元素
                    }
                }
            }
            while (i <= a.vn)
            {
                res.row[res.vn] = a.row[i];
                res.col[res.vn] = a.col[i];
                res.val[res.vn] = a.val[i];
                res.vn++;
                i++;
            }
            while (j <= b.vn)
            {
                res.row[res.vn] = b.row[j];
                res.col[res.vn] = b.col[j];
                res.val[res.vn] = b.val[j];
                res.vn++;
                j++;
            }
            return res;
        }
    };
    

    总结

    其实思路很简单,分类讨论就可以,但是注意给res.vn赋值,否则就是零(当然可以直接赋值为a.vn+b.vn,但是这样逐个加的话不会浪费)

    展开全文
  • MyDS 稀疏矩阵加法

    2020-05-06 18:16:36
    #include<stdio.h> #include<string.h>...//稀疏矩阵加法,行优先,c=a+b,a和b都是nxm矩阵 int cmp(int a,int b,int c,int d){ if(a>c)return 1; if(a==c&&b>d) return 1;...
    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    //稀疏矩阵加法,行优先,c=a+b,a和b都是nxm矩阵
    int cmp(int a,int b,int c,int d){
        if(a>c)return 1;
        if(a==c&&b>d) return 1;
        return 0;
    }
    void add(int a[][3],int b[][3],int c[][3]){
        int n=a[0][1],m=a[0][2],pc=0,pb=1;
        for(int i=1;i<=a[0][0];i++){
            while(pb<=b[0][0]&&cmp(a[i][1],a[i][2],b[pb][1],b[pb][2])){
                c[++pc][0]=b[pb][0],c[pc][1]=b[pb][1],c[pc][2]=b[pb][2];
                pb++;
            }
            if(pb<=b[0][0]&&a[i][1]==b[pb][1]&&a[i][2]==b[pb][2]){
                c[++pc][0]=a[i][0]+b[pb][0];
                c[pc][1]=a[i][1],c[pc][2]=a[i][2];
                pb++;
            }
            else {
                c[++pc][0]=a[i][0];
                c[pc][1]=a[i][1],c[pc][2]=a[i][2];
            }
        }
        while(pb<=b[0][0]){
            c[++pc][0]=b[pb][0];
            c[pc][1]=b[pb][1],c[pc][2]=b[pb][2];
            pb++;
        }
        c[0][0]=pc;c[0][1]=n;c[0][2]=m;
    }
    
    int a[10005][3],b[10005][3],c[10005][3];
    int main(){
        int n,m;scanf("%d%d",&n,&m);
        a[0][0]=n,b[0][0]=m;
        a[0][1]=a[0][2]=b[0][1]=b[0][2]=100;
        for(int i=1;i<=n;i++){
            int sa,sb,sc;scanf("%d%d%d",&sa,&sb,&sc);
            a[i][0]=sa,a[i][1]=sb;a[i][2]=sc;
        }
        for(int i=1;i<=m;i++){
            int sa,sb,sc;scanf("%d%d%d",&sa,&sb,&sc);
            b[i][0]=sa,b[i][1]=sb;b[i][2]=sc;
        }
        add(a,b,c);
        printf("%d\n",c[0][0]);
        for(int i=1;i<=c[0][0];i++){
            printf("%d %d %d\n",c[i][0],c[i][1],c[i][2]);
        }
        return 0;
    }
    
    
    展开全文
  • 数据结构之稀疏矩阵加法稀疏矩阵加法的算法源程序,
  • 稀疏矩阵加法(十字链表)问题描述输入输出输入输出样例代码 问题描述 若将稀疏矩阵 \mathbf{A}A 的非零元素以行序为主序的顺序存于一维数组 VV 中,并用二维数组 BB 表示 AA 中的相应元素是否为零元素(以0和1分别...

    稀疏矩阵加法(十字链表)

    问题描述

    若将稀疏矩阵 \mathbf{A}A 的非零元素以行序为主序的顺序存于一维数组 VV 中,并用二维数组 BB 表示 AA 中的相应元素是否为零元素(以0和1分别表示零元素和非零元素)。例如,
    矩阵A
    可以使用一个数组和一个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 %d\n",&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("read\n");
            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("%d\n",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->j\n");
                }else if(p==NULL){
                    printf("0 ");
                }
            }
            //打印最后一个结点
            if(p==NULL){
                printf("0\n");
            }else{
                printf("1\n");
            }
            
        }
    }
    

    原本是将addnode单独写为一个函数,但是不知为何一直报错,所以就直接将代码加到getarray中了
    备注写的很详细呀,如果有什么问题欢迎一起讨论~

    展开全文
  • 稀疏矩阵加法 给定两个矩阵A和B,求其和矩阵C=A+B。 输入格式: 第一行包含两个数Row和Col,分别表示矩阵的行数和列数,A和B的维度是一致的。 第二行只有一个数N​​1​​,表示接下来要输入的A中的非零元素的个数。...

    稀疏矩阵加法

    给定两个矩阵A和B,求其和矩阵C=A+B。

    输入格式:

    第一行包含两个数Row和Col,分别表示矩阵的行数和列数,A和B的维度是一致的。

    第二行只有一个数N​​1​​,表示接下来要输入的A中的非零元素的个数。

    接下来是N1行,每一行都是i j A[i,j] 这样的形式,表示的A中第i行第j列的元素A[i,j],为了与大多数编程语言保持一致,它们都是从零开始的,也就是说下标的有效范围是[0,Row−1]×[0,Col−1]。

    在N1行之后,是一个数N2,表示矩阵B中非零元素的数量,此后N2行描述B中的非零元素,它们与此前描述A中非零元素的形式一致。

    矩阵元素的输入均遵循行主序。这里的所有的输入均可用int类型正确表示,可以假设输入均是合法的。

    输出格式:

    第一行输出和矩阵C=A+B中的绝对值大于0.1的元素个数N3,此后是N3行,按照行主序输出其中的非零元素,依次是行、列的下标和对应的元素。

    输入样例:

    2 2
    1
    1 1 1
    1
    0 0 1
    

    输出样例:

    2
    0 0 1
    1 1 1
    

    完整代码

    #include<stdio.h>
    #include<stdlib.h>
    #define MAX 100
    typedef struct {
    	int i,j;//行,列
    	int data;
    } matrix;
    
    int main() {
    	matrix a[MAX];
    	matrix b[MAX];
    	matrix c[MAX];
    	int row;
    	int col;
    	int n1,n2,n3;
    	int k,t;
    	scanf("%d %d",&row,&col);
    	scanf("%d",&n1);
    	int arr1[n1][3];
    	for(k=0; k<n1; k++) {
    		for(t=0; t<3; t++) {
    			scanf("%d",&arr1[k][t]);
    			if(t==0) {
    				a[k].i=arr1[k][t];
    			}
    			if(t==1) {
    				a[k].j=arr1[k][t];
    			}
    			if(t==2) {
    				a[k].data=arr1[k][t];
    			}
    		}
    	}//输入矩阵a的非零元素位置及数值,并将其存入结构体中
    
    	scanf("%d",&n2);
    	int arr2[n2][3];
    	for(k=0; k<n2; k++) {
    		for(t=0; t<3; t++) {
    			scanf("%d",&arr2[k][t]);
    			if(t==0) {
    				b[k].i=arr2[k][t];
    			}
    			if(t==1) {
    				b[k].j=arr2[k][t];
    			}
    			if(t==2) {
    				b[k].data=arr2[k][t];
    			}
    		}
    	}//输入矩阵b的非零元素位置及数值,并将其存入结构体中
    
    	//两矩阵元素相加
    	int m=0,n=0;
    	t=0;
    	int temp;
    	while(m<n1&&n<n2) {
    		if(a[m].i==b[n].i) {
    			if(a[m].j==b[n].j) {
    				temp=a[m].data+b[m].data;
    				if(temp!=0) {
    					c[t].i=a[m].i;
    					c[t].j=a[m].j;
    					c[t].data=temp;
    					t++;
    				}
    				m++;n++;
    				continue;
    			}
    			if(a[m].j<b[n].j) {
    				c[t].i=a[m].i;
    				c[t].j=a[m].j;
    				c[t].data=a[m].data;
    				t++;
    				m++;
    				continue;
    			}
    			if(a[m].j>b[n].j) {
    				c[t].i=b[n].i;
    				c[t].j=b[n].j;
    				c[t].data=b[n].data;
    				t++;
    				n++;
    				continue;
    			}
    		}
    		if(a[m].i<b[n].i) {
    			c[t].i=a[m].i;
    			c[t].j=a[m].j;
    			c[t].data=a[m].data;
    			t++;
    			m++;
    			continue;
    		}
    		if(a[m].i>b[n].i) {
    			c[t].i=b[n].i;
    			c[t].j=b[n].j;
    			c[t].data=b[n].data;
    			t++;
    			n++;
    			continue;
    		}
    	}
    
    	int p;
    	//a矩阵还有非零元素
    	if(m<n1) {
    		for(p=m; p<n1; p++) {
    			c[t].i=a[p].i;
    			c[t].j=a[p].j;
    			c[t].data=a[p].data;
    			t++;
    		}
    	}
    
    	//b矩阵还有非零元素
    	if(n<n2) {
    		for(p=n; p<n2; p++) {
    			c[t].i=b[p].i;
    			c[t].j=b[p].j;
    			c[t].data=b[p].data;
    			t++;
    		}
    	}
    
    	int q;
    	printf("%d\n",t);
    	for(q=0; q<t; q++) {
    		if(c[q].data>0.1) {
    			printf("%d %d %d\n",c[q].i,c[q].j,c[q].data);
    		}
    	}
    	return 0;
    }
    
    展开全文
  • 稀疏矩阵加法(PTA)

    千次阅读 2019-05-29 16:38:43
    稀疏矩阵加法 给定两个矩阵A和B,求其和矩阵C=A+B。 输入格式: 第一行包含两个数Row和Col,分别表示矩阵的行数和列数,A和B的维度是一致的。 第二行只有一个数N​1,表示接下来要输入的A中的非零元素的个数。 接...
  • 7-4 稀疏矩阵加法 给定两个矩阵A和B,求其和矩阵C=A+B。 输入格式: 第一行包含两个数Row和Col,分别表示矩阵的行数和列数,A和B的维度是一致的。 第二行只有一个数N ​1 ​​ ,表示接下来要输入的A中的非零元素的...
  • /* ... *All rights reserved. *文件名称:xishujuzhen.cpp *作者:朱希康 *完成日期:2015年11月9日 ...*问题描述:稀疏矩阵加法 *输入描述:无 *程序输出:稀疏矩阵的加法 */ #ifndef TUP_H_INCLUDED #define T
  • 题目:假设稀疏矩阵A和B均以三元组表作为存储结构,试写出矩阵相加和相乘的算法,另设三元组表C存放结果矩阵。 要求: 从键盘输入稀疏矩阵A和B 检测A和B能否相加/相乘 如能,做矩阵相加和相乘运算,并打印运算结果 ...
  • 稀疏矩阵加法,实现C=A+B Description: 输入两个稀疏矩阵,输出它们相加的结果。 Input: 第一行输入四个正整数,分别是两个矩阵的行m、列n、第一个矩阵的非零元素的个数t1和第二个矩阵的非零元素的个数t2。接下来的...
  • (c语言)稀疏矩阵加法

    千次阅读 2020-04-17 15:01:38
    实现三元组表示的两个稀疏矩阵加法。相关定义如下 #define MAXSIZE 100 //假设非零元个数的最大值为100 typedef struct { int i,j; //非零元的行下标和列下标,i 和 j 从 1 开始计数,与数学中矩阵元素的...
  • //稀疏矩阵加法 #include<stdio.h> #include<stdlib.h> #define MAXSIZE 100 typedef struct { int i,j; int e; }Triple; typedef struct { Triple data[MAXSIZE+1]; int mu,nu,tu; }...
  • 稀疏矩阵加法,用十字链表实现C=A+B Input: 第一行输入四个正整数,分别是两个矩阵的行m、列n、第一个矩阵的非零元素的个数t1和第二个矩阵的非零元素的个数t2。接下来的t1+t2行是三元组,分别是第一个矩阵的数据和...
  • [NOJ]数据结构实验2.2 稀疏矩阵加法,实现C=A+B #include<iostream> #include<cstdio> #include<cstdlib> using namespace std; typedef struct { int row,col; int e; }Triple; typedef ...
  • 7-4稀疏矩阵加法(20分) 给定两个矩阵A和B,求其和矩阵C=A+B。 输入格式: 第一行包含两个数Row和Col,分别表示矩阵的行数和列数,A和B的维度是一致的。 第二行只有一个数N​1​​,表示接下来要输入的A中的非零...
  • 7-4 稀疏矩阵加法 (20分) 来都来了点个赞再走呗,一键三连也行,可以点下方链接进入我的bilibili主页转转,也可以关注我的个人公众号~后期公众号会发送一些比较好玩的东西 bilibili:羊卓的杨 公众号:羊卓的杨 ...
  • #include <stdio.h> #include <stdlib.h> typedef struct OLNode { int r,c,v; struct OLNode *right,*down; }Node,*LNode; typedef struct { LNode *Rhead,*Chead;... int mu,n...
  • 稀疏矩阵加法,实现C=A+B

    千次阅读 2018-05-03 22:41:37
    输入两个稀疏矩阵,输出它们相加的结果。第一行输入四个正整数,分别是两个矩阵的行m、列n、第一个矩阵的非零元素的个数t1和第二个矩阵的非零元素的个数t2。接下来的t1+t2行是三元组,分别是第一个矩阵的数据和第二...
  • 稀疏矩阵加法,实现C=A+B

    千次阅读 多人点赞 2018-04-27 20:20:35
    Description输入两个稀疏矩阵,输出它们相加的结果。Input第一行输入四个正整数,分别是两个矩阵的行m、列n、第一个矩阵的非零元素的个数t1和第二个矩阵的非零元素的个数t2。接下来的t1+t2行是三元组,分别是第一个...

空空如也

空空如也

1 2 3 4 5 ... 14
收藏数 267
精华内容 106
关键字:

稀疏矩阵加法