三元组实现矩阵相加

#include "stdio.h"#define MAXSIZE 100struct node{int i,j;int v;};struct sparmatrix{int rows,cols;int terms;struct node data[MAXSIZE];};void sum(struct sparmatrix a,struct sparmatrix b);main(){int m[MAXSIZE][MAXSIZE],n[MAXSIZE][MAXSIZE];int i,j,mrow,mcol,nrow,ncol,ano=0,bno=0,counter=0,t=0;struct sparmatrix a,b;printf("Please input row and col of matrix m(for example: row,col):"); scanf("%d,%d",&mrow,&mcol);printf("\n");printf("Please input row and col of matrix n(for example: row,col):"); scanf("%d,%d",&nrow,&ncol);if ((mrow!=nrow)||(mcol!=ncol)){printf("ERROR: dimensions of m,n are different!");getch();return; /*comapre dimension between matrix m and n*/ }for (i=0;i<mrow;i++)for (j=0;j<mcol;j++){ printf("input value of data element m[%d][%d] ",i,j);scanf("%d",&m[i][j]);} /*input value of matrix m*/for (i=0;i<nrow;i++)for (j=0;j<ncol;j++){ printf("input value of data element n[%d][%d] ",i,j);scanf("%d",&n[i][j]);} /*input value of matrix n*/printf("matrix m you input as follows:\n");for (i=0;i<mrow;i++)for (j=0;j<mcol;j++){if (t==mcol){printf("\n");t=0;}printf(" %d",m[i][j]);t++;} /*output matrix m*/printf("\n");printf("\n");printf("matrix n you input as follows:\n");t=0;for (i=0;i<nrow;i++)for (j=0;j<ncol;j++){if (t==ncol){printf("\n");t=0;}printf(" %d",n[i][j]);t++;} /*output matrix n*/printf("\n");printf("\n");for (i=0;i<mrow;i++)for (j=0;j<mcol;j++)if (m[i][j]!=0){ counter++;a.data[ano].i=i;a.data[ano].j=j;a.data[ano].v=m[i][j];ano++;}a.rows=mrow;a.cols=mcol;a.terms=counter;printf("tripule node of m: i j v \n");for(i=0;i<a.terms;i++)printf(" %5d %5d %5d\n",a.data[i].i,a.data[i].j,a.data[i].v);counter=0;for (i=0;i<nrow;i++)for (j=0;j<ncol;j++)if (n[i][j]!=0){ counter++;b.data[bno].i=i;b.data[bno].j=j;b.data[bno].v=n[i][j];bno++;}b.rows=nrow;b.cols=ncol;b.terms=counter;printf("tripule node of n: i j v\n");for(i=0;i<b.terms;i++)printf(" %5d %5d %5d\n",b.data[i].i,b.data[i].j,b.data[i].v);sum(a,b);getch();}void sum(struct sparmatrix a,struct sparmatrix b){struct sparmatrix c; /*c为a+b的转置*/int i,j,x,k=0,p=0,cno=0,counter=0,flag=0;int mn[MAXSIZE][MAXSIZE]; /*define variables*/c.cols=a.cols;c.rows=a.rows;if (a.terms==0&&b.terms==0){return ; /*check the numbers of data element that isn't zero*/}for(i=1;i<=c.rows;i++){for(j=1;j<=c.cols;j++){if(a.data[k].i==b.data[p].i)if(a.data[k].j==b.data[p].j){c.data[cno].v=a.data[k].v+b.data[p].v;c.data[cno].i=a.data[k].i;c.data[cno].j=a.data[k].j;cno++;k++;p++;}elseif(a.data[k].j>b.data[p].j){c.data[cno].v=b.data[p].v;c.data[cno].i=b.data[p].i;c.data[cno].j=b.data[p].j;cno++;p++;}else{c.data[cno].v=a.data[k].v;c.data[cno].i=a.data[k].i;c.data[cno].j=a.data[k].j;cno++;k++;}elseif(a.data[k].i>b.data[p].i){c.data[cno].v=b.data[p].v;c.data[cno].i=b.data[p].i;c.data[cno].j=b.data[p].j;cno++;p++;}else{c.data[cno].v=a.data[k].v;c.data[cno].i=a.data[k].i;c.data[cno].j=a.data[k].j;cno++;k++;};if (k==a.terms||p==b.terms){flag=1;break;}}if (flag==1)break;}if(k==a.terms&&p<b.terms)while(p<b.terms){c.data[cno].v=b.data[p].v;c.data[cno].i=b.data[p].i;c.data[cno].j=b.data[p].j;cno++;p++;}if(p==b.terms&&k<a.terms)while(k<a.terms){c.data[cno].v=a.data[k].v;c.data[cno].i=a.data[k].i;c.data[cno].j=a.data[k].j;cno++;k++;}if(k==a.terms&&p==b.terms)c.terms=cno;printf("the tripule of m+n is: i j v \n");for(i=0;i<c.terms;i++)printf(" %5d %5d %5d\n",c.data[i].i,c.data[i].j,c.data[i].v);for (i=0;i<c.rows;i++)for (j=0;j<c.cols;j++)mn[i][j]=0;for (i=0;i<c.rows;i++)for (j=0;j<c.cols;j++)for (x=0;x<c.terms;x++)if (i==c.data[x].i)if(j==c.data[x].j)mn[i][j]=c.data[x].v;printf("\n");printf("sum of matrix m+n as follows:\n");for (i=0;i<c.rows;i++)for (j=0;j<c.cols;j++){if (counter==c.cols){printf("\n");counter=0;}printf(" %d",mn[i][j]);counter++;}}。

三元组顺序结构实现稀疏矩阵相加，⾏序优先（Java语⾔描述）不⽤⼗字链表也可以稀疏矩阵相加时间复杂度最坏情况达到O(tuA + tuB);思路⽐较简单就不赘述了，代码如下：三元组：package ⾏逻辑链接的顺序表实现稀疏矩阵的相乘;public class Triple<T> {int row,col;T v;public Triple(){}public Triple(int row,int col, T v){this.row = row;this.col = col;this.v = v;}}构建矩阵存储结构：package ⾏逻辑链接的顺序表实现稀疏矩阵的相乘;public class Mat {final int MAXSIZE = 10;int mu,nu,tu;int rpos[] = new int[MAXSIZE + 1];//各⾏第⼀个⾮零元的位置表Triple<Integer> data[] = new Triple[MAXSIZE + 1];//Java不⽀持泛型数组public Mat(int mu,int nu,int tu){this.mu = mu;this.nu = nu;this.tu = tu;for(int i=1; i<=MAXSIZE; i++)data[i] = new Triple();}//三元组矩阵的输出public void display(){int i,j,k,m,n,count = 0;for(i=1; i<=mu; i++){for(j=1; j<=nu; j++){for(k=1; k<=tu; k++){if(i==data[k].row && j==data[k].col){System.out.print(data[k].v + " ");count = -1;break;}}if(count != -1)System.out.print("0 ");count = 0;}System.out.println();}}}相加：package ⾏逻辑链接的顺序表实现稀疏矩阵的相乘;import java.util.*;public class AddMat {public static void main(String[] args) {/** @author 王旭* @time 2014/10/14/23:50**/Scanner scan = new Scanner(System.in);int muA,nuA,tuA,muB,nuB,tuB;System.out.println("请输⼊A矩阵的⾏，列，⾮零元的个数：");muA = scan.nextInt();nuA = scan.nextInt();tuA = scan.nextInt();Mat A = new Mat(muA,nuA,tuA);System.out.println("请输⼊A矩阵的三元组：");for(int i=1; i<=tuA; i++){A.data[i].row = scan.nextInt();A.data[i].col = scan.nextInt();A.data[i].v = scan.nextInt();}System.out.println("A矩阵为：");A.display();System.out.println("请输⼊B矩阵的⾏，列，⾮零元的个数：");muB = scan.nextInt();nuB = scan.nextInt();tuB = scan.nextInt();Mat B = new Mat(muB,nuB,tuB);System.out.println("请输⼊B矩阵的三元组：");for(int i=1; i<=tuB; i++){B.data[i].row = scan.nextInt();B.data[i].col = scan.nextInt();B.data[i].v = scan.nextInt();}System.out.println("B矩阵为：");B.display();Mat C = new Mat(muA,nuA,1);add(A,B,C);System.out.println("相加后的矩阵C为：");C.display();}public static void add(Mat A, Mat B, Mat C){int k,l,temp;//C = new Mat(A.mu,A.nu,1);k = 1;l = 1;while(k<A.tu && l<B.tu){if((A.data[k].row == B.data[l].row) && (A.data[k].col == B.data[l].col)){temp = A.data[k].v + B.data[l].v;if(temp != 0){C.data[C.tu].row = A.data[k].row;C.data[C.tu].col = A.data[k].col;C.data[C.tu].v = temp;C.tu++;}k++;l++;}if(( (A.data[k].row == B.data[l].row) && (A.data[k].col < B.data[l].col) ) || (A.data[k].row<B.data[l].row)){ C.data[C.tu].row = A.data[k].row;C.data[C.tu].col = A.data[k].col;C.data[C.tu].v = A.data[k].v;C.tu++;k++;}if(( (B.data[l].row == A.data[k].row) && (B.data[l].col < A.data[k].col) ) || (B.data[l].row<A.data[k].row)){ C.data[C.tu].row = B.data[l].row;C.data[C.tu].col = B.data[l].col;C.data[C.tu].v = B.data[l].v;C.tu++;l++;}}}}。

//从文本读入矩阵，将其转化为三元组矩阵，并做矩阵相加//矩阵转置是个难点，要提高效率以下存入trematrix1.txt中7 8 81 2 51 4 62 6 42 7 24 2 15 6 216 7 5以下存入trematrix2.txt中9 8 82 5 94 1 84 2 85 6 47 2 98 5 108 7 55源程序如下：#include<stdio.h>#include<stdlib.h>typedef int datatype;typedef struct{datatype data[30][3];int size;}thrematrix;typedef thrematrix* matrix3;typedef struct{int data[100][100];int row,col;//存储稀疏矩阵，行为ROW 列为COL}matrix;typedef matrix * matr;int posi=1,posj=1;void readfile(FILE *fp,matrix3 mat){//从文件读取三元组矩阵int row,col;//存储稀疏矩阵的行和列int i,j;fscanf(fp,"%d%d%d",&mat->data[0][0],&mat->data[0][1],&mat->data[0 ][2]);mat->size=mat->data[0][2];for(i=1;i<mat->size;i++){fscanf(fp,"%d%d%d",&mat->data[i][0],&mat->data[i][1],&mat->data[i ][2]);}fclose(fp);}void prmatrix(matrix3 mat){ //打印该三元组矩阵int i,j;printf("\n三元组矩阵为：\n");for(i=0;i<mat->data[0][2];i++){for(j=0;j<3;j++)printf("%4d",mat->data[i][j]);printf("\n");}}void transpose(matr mat,matrix3 b,matrix3 c){//基于三元组矩阵的转置//将B三元组转化为C三元组int k;k=b->data[0][2];int i,j,x[k];//表示矩阵中的某一行有多少个元素int pos[k];//此B[i][]的起始位置是多少c->data[0][0]=b->data[0][1];c->data[0][1]=b->data[0][0];c->data[0][2]=b->data[0][2];c->size=b->size;for(i=0;i<k;i++)//取列{pos[i]=0;x[i]=0;}for(i=1;i<k;i++)//若列不为零则x[][]++{//保存B->data[i][1]中的列中有多少个元素x[b->data[i][1]]++;}pos[0]=1;for(i=1;i<k;i++)pos[i]=pos[i-1]+x[i-1];//计算出每个元素要插入的位置！for(i=1;i<k;i++){int t;t=pos[b->data[i][1]];c->data[t][0]=b->data[i][1];c->data[t][1]=b->data[i][0];c->data[t][2]=b->data[i][2];pos[b->data[i][1]]=t+1;//计数// printf("|%d",pos[t]);// printf("=%d| \n",pos[t]+count[t]);}/* printf("\n"); printf("xi=");for(i=0;i<k;i++)//测试打印printf(" %d",x[i]);printf("\n");printf("posi=");for(i=0;i<k;i++)//测试打印printf(" %d",pos[i]);printf("\n");*/}int judge(matrix3 m1,matrix3 madd,matrix3 m3,int k) {int k10=m1->data[posi][0];int k11=m1->data[posi][1];int k12=m1->data[posi][2];int k30=m3->data[posj][0];int k31=m3->data[posj][1];int k32=m3->data[posj][2];// printf(" %d",k);if(k10==k30){if(k11==k31){madd->data[k][0]=k10;madd->data[k][1]=k11;madd->data[k][2]=k12+k32; posi++;posj++;return k;}if(k11>k31){madd->data[k][0]=k30;madd->data[k][1]=k31;madd->data[k][2]=k32;posj++;return k;}else{madd->data[k][0]=k10;madd->data[k][1]=k11;madd->data[k][2]=k12;posi++;return k;}}if(k10>k30){madd->data[k][0]=k30;madd->data[k][1]=k31;madd->data[k][2]=k32;posj++;return k;}if(k30>k10){madd->data[k][0]=k10; madd->data[k][1]=k11;madd->data[k][2]=k12;posi++;return k;}}void matrixadd1(matrix3 m1,matrix3 m3,matrix3 madd){int count=0,temp,k=0;if(m1->data[0][1]!=m3->data[0][0]){printf("不合法矩阵，不能相加");exit(0);}madd->data[0][0]=m1->data[0][0];madd->data[0][1]=m3->data[0][1];// printf("%d %d \n",madd->data[k][0],madd->data[k][1]);while(posi<=m1->size&&posj<=m3->size){k++;// printf("%d %d\n",posi,posj);k=judge(m1,madd,m3,k);//k=temp;}while(posi>=m1->size&&posj<m3->size){madd->data[k][0]=m3->data[0][0];madd->data[k][1]=m3->data[0][1];madd->data[k][2]=m3->data[0][2];k++;// printf(" %d",k);posj++;}while(posj>=m3->size&&posi<m1->size){madd->data[k][0]=m1->data[0][0];madd->data[k][1]=m1->data[0][1];madd->data[k][2]=m1->data[0][2];// printf(" %d",k);k++;posi++;}madd->size=k;madd->data[0][2]=k;}void matrixadd(matrix3 m1,matrix3 m3,matrix3 madd){int count=0,i=1,j=1,temp,k=0;if(m1->data[0][1]!=m3->data[0][0]){printf("不合法矩阵，不能相加");exit(0);}madd->data[0][0]=m1->data[0][0];madd->data[0][1]=m3->data[0][1];printf("%d %d \n",madd->data[k][0],madd->data[k][1]);while(i<=m1->size&&j<=m3->size){// printf("%d %d %d \n",k,madd->data[0][0],madd->data[0][1]); k++;temp=k;// printf(" %d",k);// temp=judge(m1,madd,m3,&i,&j,k);int k10=m1->data[i][0];int k11=m1->data[i][1];int k12=m1->data[i][2];int k30=m3->data[j][0];int k31=m3->data[j][1];int k32=m3->data[j][2];if(k10==k30){if(k11==k31){madd->data[k][0]=k10;madd->data[k][1]=k11;madd->data[k][2]=k12+k32;i++;j++;}else if(k11>k31){madd->data[k][0]=k30;madd->data[k][1]=k31;madd->data[k][2]=k32;j++;}else{madd->data[k][0]=k10;madd->data[k][1]=k11;madd->data[k][2]=k12;i++;}}if(k10>k30){madd->data[k][0]=k30;madd->data[k][1]=k31;madd->data[k][2]=k32;j++;}if(k10<k30){madd->data[k][0]=k10;madd->data[k][1]=k11;madd->data[k][2]=k12;i++;}// printf("%d %d %d\n",madd->data[k][0],madd->data[k][1],madd->data [0][2]);}// printf("---- %d",k);while(i>=m1->size&&j<m3->size){madd->data[k][0]=m3->data[0][0];madd->data[k][1]=m3->data[0][1];madd->data[k][2]=m3->data[0][2];k++;printf(" %d",k);j++;}while(j>=m3->size&&i<m1->size){madd->data[k][0]=m1->data[0][0];madd->data[k][1]=m1->data[0][1];madd->data[k][2]=m1->data[0][2];printf(" %d",k);k++;i++;}madd->size=k;madd->data[0][2]=k;}void print(matrix3 array){//打印稀疏矩阵int i,t,j; t=1;printf("稀疏矩阵为%drows %dcols：\n",array->data[0][0],array->data[0][1]);for(i=1;i<=array->data[0][0];i++){//列优先for(j=1;j<=array->data[0][1];j++){if(i==array->data[t][0]&&j==array->data[t][1]) {printf("%4d",array->data[t][2]);t++;}else printf("%4c",'-');}printf("\n");}}main(){ //此函数实现三元组矩阵相加！FILE *fp1,*fp2;fp1=fopen("trematrix1.txt","r");fp2=fopen("trematrix2.txt","r");matrix3 mat1,mat2,mat3,mtadd;matr mat;mat=(matr)malloc(sizeof(mat));mat1=(matrix3)malloc(sizeof(thrematrix));mat2=(matrix3)malloc(sizeof(thrematrix));mat3=(matrix3)malloc(sizeof(thrematrix));mtadd=(matrix3)malloc(sizeof(thrematrix)); readfile(fp1,mat1);readfile(fp2,mat2);printf("\n矩阵1：\n");// prmatrix(mat1);print(mat1);// printf("\n矩阵2：\n");// prmatrix(mat2);// print(mat2);transpose(mat,mat2,mat3);printf("\n矩阵3：\n");// prmatrix(mat3);print(mat3);matrixadd1(mat1,mat3,mtadd);printf("矩阵1,3相加后结果为：\n");// prmatrix(mtadd);print(mtadd);}。

#include<stdio.h>#include<stdlib.h>#define MAXSIZE 12500//三元组结构typedef struct {int i,j; //矩阵行下标和列下标int e; //值}Triple;//矩阵结构typedef struct{Triple data[MAXSIZE+1];int rpos[MAXSIZE+1]; //这是存放各行第一非零元在矩阵中的位置int mu,nu,tu; //矩阵的行数、列数、非零元个数}Matrix;void Init(Matrix* M);void Add(Matrix* M,Matrix* T,Matrix* G);void Jian(Matrix* M,Matrix* T,Matrix* G);void Cheng(Matrix* M,Matrix* T,Matrix* G);void Cheng(Matrix* M,Matrix* T,Matrix* G);void PrintMatrix(Matrix* M);//2、初始化矩阵void Init(Matrix* M){int i;if(M->mu < 1 || M->nu < 1 || M->tu > M->mu*M->nu){printf("出错!\n"); //如果矩阵的行数、列数不符合要求，打印出错}for(i=1;i<=M->tu;i++) //data[0]不用{printf("第%d个非零元的行号：",i); //以下为数据初始化scanf("%d",&M->data[i].i);printf("第%d个非零元的列号：",i);scanf("%d",&M->data[i].j);printf("第%d个非零元的元素值：",i);scanf("%d",&M->data[i].e);}printf("\n");printf("您创建的矩阵如下:\n");PrintMatrix(M);}//3、矩阵相加void Add(Matrix* M,Matrix* T,Matrix* G){G->mu = M->mu; //因为加减运算必须维数相等，所以M、T行、列数相等，初始化第三方矩阵的行、列数。

实验二利用三元组表实现矩阵相加一、预备知识1.稀疏矩阵的三元组表压缩存储结构2.稀疏矩阵的三元组表表示方法下的相加算法二、实验目的1.掌握稀疏矩阵的三元组表存储结构的实现2.实现稀疏矩阵的三元组表表示下的相加算法三、实验内容1.编写程序，实现利用三元组表进行两个稀疏矩阵相加的算法。

要求：（1）随机产生两个可相加的稀疏矩阵（二维）；（2）将产生的稀疏矩阵用两个三元组表的顺序存储结构存储；（3）将两稀疏矩阵相加的结果存储在第三个三元组表中。

2.沿用实验一编写的操作菜单进行上述的操作。

四、实验说明1.三元组表的类型定义#define MAXSIZE 1000//非零元素个数的最大值typedef struct{int row,col;//非零元素的行下标和列下标ElemType e;//非零元素的值} Triple;typedef struct{Triple data[MAXSIZE+1];//非零元素的三元组表，data[0]未用int mu,nu,tu;//矩阵的行数、列数和非零元素个数} TSMatrix;五、注意问题1.首先应输入矩阵的行数和列数,并判别给出的两个矩阵的行、列数对于所要求作的运算是否相匹配。

可设矩阵的行数和列数均不超过20。

2.程序可以对三元组的输入顺序加以限制,例如,按行优先，以便提高计算效率。

3.在用三元组表示稀疏矩阵时,相加或相减所得结果矩阵应该另生成,相加结果矩阵也可用二维数组存放。

4.三元组表是线性表的一种应用，通过它可以更好地理解线性表的存储结构。

同时矩阵又是图的重要的存储方式，所以这个实验对更好地掌握线性表对将来对图的理解都有极大的帮助。

在Python中，三元组顺序表表示的稀疏矩阵加法是一个重要的主题。

稀疏矩阵是指大部分元素为零的矩阵，而三元组顺序表是一种压缩稀疏矩阵的方法，它将非零元素的行列坐标及对应的值存储起来，以节省空间和提高运算效率。

在本文中，我们将探讨稀疏矩阵加法在Python中的实现方法，并深入分析其原理和应用。

一、稀疏矩阵及三元组顺序表简介1. 稀疏矩阵稀疏矩阵是指大部分元素为零的矩阵，它在实际问题中的应用非常广泛，如图像处理、网络分析、物理建模等领域。

由于其大部分元素为零，传统的存储和计算方法会浪费大量的空间和时间，因此需要一种高效的表示方法。

2. 三元组顺序表三元组顺序表是一种压缩稀疏矩阵的方法，它将非零元素的行列坐标及对应的值存储起来。

比起普通的二维数组表示方法，三元组顺序表可以更加高效地存储和计算稀疏矩阵，节省空间和提高运算效率。

二、稀疏矩阵加法的原理稀疏矩阵加法是指将两个稀疏矩阵相加，得到一个新的稀疏矩阵。

在三元组顺序表表示的稀疏矩阵中，我们可以通过遍历两个矩阵的非零元素，并按照其行列坐标进行相加，得到新的稀疏矩阵。

三、Python中的实现在Python中，我们可以通过定义稀疏矩阵类和相应的加法运算方法来实现稀疏矩阵的加法。

我们需要定义稀疏矩阵的三元组顺序表表示方法，并实现相应的初始化方法和加法运算方法。

下面是一个简单的Python示例代码：```pythonclass SparseMatrix:def __init__(self, rows, cols, data):self.rows = rowsself.cols = colsself.data = datadef __add__(self, other):result = []i, j = 0, 0while i < len(self.data) and j < len(other.data):if self.data[i][0] == other.data[j][0] and self.data[i][1] == other.data[j][1]:result.append((self.data[i][0], self.data[i][1],self.data[i][2] + other.data[j][2]))i += 1j += 1elif self.data[i][0] < other.data[j][0] or (self.data[i][0] == other.data[j][0] and self.data[i][1] < other.data[j][1]):result.append((self.data[i][0], self.data[i][1],self.data[i][2]))i += 1else:result.append((other.data[j][0], other.data[j][1], other.data[j][2]))j += 1while i < len(self.data):result.append((self.data[i][0], self.data[i][1], self.data[i][2])) i += 1while j < len(other.data):result.append((other.data[j][0], other.data[j][1],other.data[j][2]))j += 1return SparseMatrix(self.rows, self.cols, result)```在上面的示例代码中，我们定义了一个SparseMatrix类，其初始化方法接受稀疏矩阵的行数、列数和三元组顺序表表示的数据。

内蒙古科技大学信息工程学院计算机系《数据结构与算法》实验报告
add(a,b,c);
nodeprint(c);
return 0;
}
实验过程及结果线性表的顺序存储和删除：线性表的链式存储和删除：
顺序栈：
链队列：
实验三：
实验总结
【实验1】
这次实验了解了线性表的顺序存储结构和线性表的链式存储结构的插入和删除的操作，了解了线性表这两种存储方式的不同以及这两种线性表的优缺点，顺序存储结构的效率较低而链式存储结构的插入和删除效率高一些，操作更容易一些。

【实验2】
这次实验初步掌握了栈和队列的简单应用，学会的创建栈和队列，向栈和队列中传入参数，销毁栈和队列。

【实验3】
这次实验掌握了数组的压缩存储和应用，用三元组实现了矩阵之间的相加
1、每个实验项目填写一份实验报告，电子版命名方式为：学号姓名项目号.doc。

例如：1167111182张三3.doc表示张三做的第3个项目的实验报告。

2、实验报告电子版应该在实验后一周内由学习委员收齐后存放在一个文件夹下，文件夹命
名方式为：软件12-1班3，表示软件12-1班第3个项目的实验报告，压缩。

第一时间发送
给任课教师。

必须以班级为单位上交。

#include<stdio.h>#include<stdlib.h> #define MAXSIZE 12500 // 三元组结构typedef structinti,j;int e; }Triple;{//矩阵行下标和列下标//值typedef struct {Triple data[MAXSIZE+1];int rpos[MAXSIZE+1]; // 这是存放各行第一非零元在矩阵中的位置int mu,nu,tu; // 矩阵的行数、列数、非零元个数}Matrix;void Init(Matrix* M);void Add(Matrix* M,Matrix* T,Matrix* G);void Jian(Matrix* M,Matrix* T,Matrix* G);void Cheng(Matrix* M,Matrix* T,Matrix* G);void Cheng(Matrix* M,Matrix* T,Matrix* G); void PrintMatrix(Matrix* M);//2、初始化矩阵void Init(Matrix* M){int i;if(M->mu < 1 || M->nu < 1 || M->tu > M->mu*M->nu){printf(" 出错!\n"); //如果矩阵的行数、列数不符合要求，打印出错} for(i=1;i<=M->tu;i++) //data[0] 不用{printf(“第%d个非零元的行号：“,i); //以下为数据初始化scanf("%d",&M->data[i].i);printf(“第%d个非零元的列号：",i); scanf("%d",&M->data[i].j); printf(”第％d个非零元的元素值：",i); scanf("%d",&M->data[i].e);}printf("\n");printf(" 您创建的矩阵如下:\n"); PrintMatrix(M);} //3、矩阵相加void Add(Matrix* M,Matrix* T,Matrix* G) {G->mu = M->mu;的行、列数。

一、实验内容和要求1、稀疏矩阵A,B均采用三元组表示，验证实现矩阵A快速转置算法，设计并验证A,B相加得到矩阵C的算法。

（1）从键盘输入矩阵的行数和列数，随机生成稀疏矩阵。

（2）设计算法将随机生成的稀疏矩阵转换成三元组顺序表示形式存储。

（3）设计算法将快速转置得到的与相加得到的三元组顺序表分别转换成矩阵形式。

（4）输出随机生成的稀疏矩阵A,B及其三元组顺序表、快速转置得到的与相加得到的三元组顺序表及其矩阵形式。

二、实验过程及结果一、需求分析1、将随机生成的数定义为int型（为方便起见设定范围为-20至20（不含0），可修改），三元组存储的元素分别为非零元的行下标、列下标及该位置的元素值，零元不进行存储。

实际上在生成稀疏矩阵时是随机选取一些位置生成非零元然后存入三元组中。

2、从键盘输入矩阵的行数和列数后应能输出三元组顺序表及相应矩阵（按行和列排列形式输出）。

3、程序能实现的功能包括：①随机产生稀疏矩阵；②输出阵列形式的矩阵；③输出三元组顺序表；④将矩阵快速转置；⑤将两个稀疏矩阵相加生成新的矩阵。

二、概要设计1、稀疏矩阵的抽象数据类型定义：ADT TSMatrix{数据对象：D={ aij|i=1,2,…,m,j=1,2,…,n;Ai,j∈ElemSet,m和n分别称为矩阵的行数和列数} 数据关系：R={Row，Col}Row={<ai,j，ai,j+1>|1≤i≤m, 1≤j≤n-1}Col ={<ai,j，ai+1,j>|1≤i≤m-1, 1≤j≤n}基本操作:CreateTSMatrix(&M)操作结果：创建矩阵MPrintTSMatrix(M)初始条件：矩阵M已存在操作结果：输出矩阵M中三元组形式的非零元素PrintTSMatrix1(M)初始条件：矩阵M已存在操作结果：以阵列形式输出矩阵UnZore(M, row, col)初始条件：矩阵M已存在操作结果：若位置(row,col)处存在非零元素，则返回该元素存储在矩阵中的序号TSMatrix_Add(M, N,&Q)初始条件：矩阵M，N已存在操作结果：将矩阵M,N相加得到Q并返回矩阵QFastTransposeSMatrix(M,&N)初始条件：矩阵M已存在操作结果：将矩阵M快速转置得到转置矩阵N并返回}ADT TSMatrix；⒊本程序模块结构⑴主函数模块void main(){初始化迷矩阵；创建矩阵并输出；将矩阵转置并输出；将矩阵相加并输出结果；｝三、详细设计1、基本数据类型操作⑴typedef int ElemType;typedef struct{int i,j;ElemType e;}Triple;//数据类型三元组typedef struct{Triple data[maxsize+1];//矩阵大小int mu,nu,tu; //}TSMatrix;//矩阵抽象数据类型2、参数设置：#define maxsize 10000//----------基本操作的算法描述--------------------Status CreateTSMatrix(TSMatrix *M){//创建一个随机矩阵（data[0]未用）srand((int)time(NULL));printf("Please Input The Lines And Columns Of The Matrix:\n");printf("...(矩阵的期望规格大于4*5(或5*4))...\n");scanf(M->mu，M->nu);for(m=0;m<M->mu;m++){for(n=0;n<M->nu;n++){k[m][n]=rand()%20;if(k[m][n]==0){if(rand()%2)M->data[p].e=rand()%20+1;elseM->data[p].e=rand()%20-20;M->data[p].i=m+1;M->data[p].j=n+1;p++;}}}M->tu=p-1; //p从1开始，非零元个数刚好等于p-1return OK;}void PrintTSMatrix(TSMatrix M){//输出矩阵的三元组顺序表if(M.tu==0)printf("无非零元!\n");else{printf("该矩阵的行数为%d、列数为%d、非零元素个数为%d.\n非零元的坐标及值:\n\n",M.mu,M.nu,M.tu);printf(" 行列元素值\n");for(i=1;i<=M.tu;i++){printf("%4d%4d%6d\n",M.data[i].i,M.data[i].j,M.data[i].e);}printf("\n");}}void PrintTSMatrix1(TSMatrix M){//输出矩阵的阵列形式printf("阵列形式为:\n");for(i=1;i<=M.mu;i++){for(j=1;j<=M.nu;j++)if (k<M.tu&&p->i==i&&p->j==j){printf("%4d",p->e); //data[0]未用，p从data[1]开始p++;k++;}elseprintf("%4d",0);printf("\n");}printf("\n");}int UnZore(TSMatrix M,int row,int col){while(order<=M.tu){if(M.data[order].i==row&&M.data[order].j==col)//order从1开始return order;order++;}return 0;}Status TSMatrix_Add(TSMatrix M,TSMatrix N,TSMatrix *Q){//矩阵相加得到新的矩阵，order从1开始if(M.mu==N.mu&&M.nu==N.nu){for(row=1;row<=M.mu;row++){for(col=1;col<=M.nu;col++){order1=UnZore(M,row,col);order2=UnZore(N,row,col);if(order1&&order2){Q->data[order].i=row;Q->data[order].j=col;Q->data[order].e=M.data[order1].e+N.data[order2].e;order++;}else if(order1&&(!order2)){Q->data[order].e=M.data[order1].e;Q->data[order].i=M.data[order1].i;Q->data[order].j=M.data[order1].j;order++;}else if((!order1)&&order2){Q->data[order].e=N.data[order2].e;Q->data[order].i=N.data[order2].i;Q->data[order].j=N.data[order2].j;order++;}}}Q->mu=M.mu;Q->nu=M.nu;Q->tu=order-1;return OK;}else{printf("\n不是同型矩阵不能进行相加!\n");return ERROR;}}Status FastTransposeSMatrix(TSMatrix M,TSMatrix *N){//采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵NN->mu=M.nu;N->nu=M.mu;N->tu=M.tu;if(N->tu){for(i=1;i<=M.nu;++i)num[i]=0;for(t=1;t<=M.tu;++t)++num[M.data[t].j];//求M中每一列非零元个数 cpot[1]=1;//求第col列中第一个元素在b.data中的序号for(i=2;i<=M.nu;++i)cpot[i]=cpot[i-1]+num[i-1];for(p=1;p<=M.tu;++p){i=M.data[p].j;q=cpot[i];N->data[q].i=M.data[p].j;N->data[q].j=M.data[p].i;N->data[q].e=M.data[p].e;++cpot[i];}}return OK;}⑶主函数算法：void main(){TSMatrix A,A1,B,C;printf("矩阵A:\n");CreateTSMatrix(&A);PrintTSMatrix(A);PrintTSMatrix1(A);printf("由矩阵A转置得矩阵A1...\n");FastTransposeSMatrix(A,&A1);PrintTSMatrix(A1);PrintTSMatrix1(A1);printf("矩阵B:\n");CreateTSMatrix(&B);PrintTSMatrix(B);PrintTSMatrix1(B);printf("矩阵A加矩阵B得到矩阵C...\n");if(TSMatrix_Add(A,B,&C)){PrintTSMatrix(C);PrintTSMatrix1(C);}}四、调试分析1、三元组顺序表的输出顺序应该是先按行排序再按列排序，即行主序，依次输出。

三元组压缩存储结构的稀疏矩阵的运算快速转置在计算机科学和数学领域中，稀疏矩阵是一种在大部分元素为零的矩阵。

由于其大部分元素为零，因此在存储和运算时存在着一些挑战。

为了解决这一问题，人们提出了三元组压缩存储结构，这种存储结构能够有效地压缩稀疏矩阵，并且能够实现快速的运算转置。

1.稀疏矩阵稀疏矩阵是一种大部分元素为零的矩阵，与之相对应的是稠密矩阵，其大部分元素为非零值。

稀疏矩阵通常在图像处理、文本处理、网络分析等领域中得到广泛应用。

然而，由于大部分元素为零，传统的存储方式会导致存储空间的浪费。

人们提出了三元组压缩存储结构，以解决稀疏矩阵存储的问题。

2.三元组压缩存储结构三元组压缩存储结构是一种用于表示稀疏矩阵的存储格式。

它采用三个数组来分别存储矩阵的非零元素的行坐标、列坐标和数值。

由于只需存储非零元素的信息，因此能够有效地压缩存储空间。

三元组压缩存储结构还能够实现快速的随机访问，这是由于它将矩阵的元素位置和数值分开存储，使得在进行运算时能够更为高效。

3.稀疏矩阵的运算稀疏矩阵的运算是对稀疏矩阵进行加法、减法、乘法等操作的过程。

在进行稀疏矩阵的运算时，三元组压缩存储结构能够显著提高计算效率。

这是由于在进行运算时，只需考虑非零元素，而无需考虑大量的零元素，从而减少了计算的复杂度。

4.稀疏矩阵的快速转置稀疏矩阵的转置是将矩阵的行和列交换，同时保持非零元素的位置和数值不变。

在传统的存储方式下，稀疏矩阵的转置操作相对复杂且耗时。

然而，采用三元组压缩存储结构后，稀疏矩阵的快速转置变得十分简便。

通过交换三元组中的行坐标和列坐标，即可完成稀疏矩阵的快速转置操作。

5.个人观点和理解我认为三元组压缩存储结构的出现，极大地解决了稀疏矩阵在存储和运算中的效率问题。

通过将矩阵的非零元素信息进行压缩存储，不仅节省了存储空间，同时也提高了计算效率。

在实际应用中，三元组压缩存储结构能够更好地满足对存储空间和计算效率有较高要求的场景，为稀疏矩阵的处理提供了更为便利和高效的途径。

矩阵相加实验目的：当具有相同行数和列数的稀疏矩阵A和B均以三元组表作为存储结构时，试写出矩阵相加算法，其结果存放在三元组表C中。

实验类容与步骤：（1）定义三元表的存储结构，输入具有相同行数和列数的稀疏矩阵A和B；（2）实现稀疏矩阵A和B相加，把相加的结果存放在C三元组中；（3）输出相加后C三元组的值。

（4）返回试验结果。

实验平台：Windows xp 操作系统，VC 6.0集成环境实验设计方案：本程序包含了3个函数：i）主函数main()ii）矩阵元素输入函数setmatrix()iii）两三元组相加函数add()源程序代码：#include "stdio.h"#include "malloc.h"#define smax 100 //一个大于非0元素个数的常数typedef struct{ //三元组的结点类型int i,j; //矩阵的行数和列数int v; //非0矩阵元素}node;typedef struct{ //稀疏矩阵的结构类型int m,n,t; //行数，列数，非0元素的个数node data[smax];//三元组表}spmatrix;spmatrix *setmatrix(){ //矩阵元素输入函数spmatrix *a;int i;a=(spmatrix *)malloc(sizeof(spmatrix));//申请结点空间printf("请输入矩阵的行数，列数及非零元素的个数:");scanf("%d%d%d",&(a->m),&(a->n),&(a->t));printf("建立三元组:\n");for(i=1;i<=a->t;i++) //当i小于三元组表中非0元素的个数时scanf("%d%d%d",&(a->data[i].i),&(a->data[i].j),&(a->data[i].v));return a;}void add(spmatrix *A,spmatrix *B,spmatrix *C) { //两个三元组相加算法int x,sum,pa,pb,pc;C->m=A->m; //将矩阵A的行数赋给CC->n=A->n; //将矩阵A的列数数赋给CC->t=0; //将一开始矩阵C的非零元个数定为0个pa=1; //pa,pb,pc分别为矩阵A，B，C的三元组下标pb=1;pc=1;for(x=1;x<=A->m;x++) //当x小于等于行数时，x++{while(A->data[pa].i<x) //当A的行数小于x时，pa加1pa++;while(B->data[pb].i<x) //当B的行数小于x时，pb加1pb++;while(A->data[pa].i==x&&B->data[pb].i==x) //在行数相等的情况下{if(A->data[pa].j==B->data[pb].j) //当列数相等时{sum=A->data[pa].v+B->data[pb].v; //矩阵相加if(sum!=0) //当相加不为零时{C->data[pc].i=x; //把x赋值给矩阵c的行数C->data[pc].j=A->data[pa].j; //把矩阵A的列数赋值给C的列数C->data[pc].v=sum; //把两矩阵想加的和赋值给Cpa++; //下标加一pb++;pc++;}}else //当列数不相等时if(A->data[pa].j>B->data[pb].j) //A的列数大于B的列数时{C->data[pc].i=x;C->data[pc].j=B->data[pb].j;C->data[pc].v=B->data[pb].v;pb++;pc++;}else //A的列数小于B的列数时{C->data[pc].i=x;C->data[pc].j=A->data[pa].j;C->data[pc].v=A->data[pa].v;pa++;pc++;}}while(A->data[pa].i==x) //插入A剩余的元素{C->data[pc].i=x;C->data[pc].j=A->data[pa].j;C->data[pc].v=A->data[pa].v;pa++;pc++;}while(B->data[pb].i==x) //插入B的元素{C->data[pc].i=x;C->data[pc].j=B->data[pb].j;C->data[pc].v=B->data[pb].v;pb++;pc++;}}C->t=pc-1;}void main(){spmatrix *a,*b,*c;int i;c=(spmatrix*)malloc(sizeof(spmatrix));a=setmatrix();printf("所得的三元组A如下:\n");for(i=1;i<=a->t;i++)printf("(%d,%d,%d)",a->data[i].i,a->data[i].j,a->data[i].v);printf("\n");b=setmatrix();printf("所得的三元组B如下:\n");for(i=1;i<=b->t;i++)printf("(%d,%d,%d)",b->data[i].i,b->data[i].j,b->data[i].v);printf("\n");add(a,b,c);printf("输出想加后所得的三元组c:\n");for(i=1;i<=c->t;i++)printf("%d,%d,%d\n",c->data[i].i,c->data[i].j,c->data[i].v);printf("\n");}实验结果及分析：。

三元组顺序表表示的稀疏矩阵加法三元组顺序表表示的稀疏矩阵加法引言：稀疏矩阵是指在矩阵中大部分元素为零的情况下，只有很少非零元素的矩阵。

由于矩阵运算的复杂性，对于大型稀疏矩阵，使用传统的矩阵加法算法会消耗大量的时间和内存资源。

因此，为了高效地进行稀疏矩阵的加法运算，可以使用三元组顺序表来表示稀疏矩阵，并通过特定的算法来实现加法操作。

本文将介绍三元组顺序表和稀疏矩阵加法，并逐步回答以下问题：1. 什么是三元组顺序表？2. 什么是稀疏矩阵加法？3. 如何使用三元组顺序表进行稀疏矩阵加法操作？一、什么是三元组顺序表？三元组顺序表是一种用来高效表示稀疏矩阵的数据结构。

在三元组顺序表中，每个非零元素用一个三元组表示，包括元素的行号、列号和值。

同时，三元组顺序表中还包含两个整数，分别表示矩阵的行数和列数。

例如，如果有一个3x3的稀疏矩阵如下：1 0 20 4 03 0 5使用三元组顺序表来表示这个矩阵，可以得到如下的三元组：(0, 0, 1), (0, 2, 2), (1, 1, 4), (2, 0, 3), (2, 2, 5)二、什么是稀疏矩阵加法？稀疏矩阵加法是指对两个稀疏矩阵进行加法运算的操作。

对于给定的两个稀疏矩阵A和B，稀疏矩阵加法的结果矩阵C的每个元素等于矩阵A和B中对应位置的元素之和。

三、使用三元组顺序表进行稀疏矩阵加法操作的步骤为了实现稀疏矩阵加法，可以按照以下步骤进行：1. 定义一个存储稀疏矩阵的三元组顺序表：使用一个结构体将矩阵的行、列和非零元素存储起来。

2. 输入矩阵A和B的维度：获取矩阵A和B的行数和列数，以及非零元素的个数。

3. 输入矩阵A和B的非零元素：获取矩阵A和B的非零元素的行号、列号和值，并将其存储到三元组顺序表中。

4. 对三元组顺序表进行排序：根据三元组的行号和列号进行排序，以便后续的加法运算。

5. 进行稀疏矩阵加法运算：从头开始遍历三元组顺序表，依次取出每个三元组，根据其行号和列号在结果矩阵C中进行加法运算。

1 问题要求及任务描述1.1 题目要求三元组表相加问题描述：利用数组的顺序存储结构，实现特殊矩阵的压缩存储和稀疏矩阵的三元组存储和加法实现基本要求：1）利用稀疏矩阵的三元组存储，来实现两矩阵相加2）利用稀疏矩阵的三元组存储，来实现两矩阵相乘两个希疏矩阵分别用两个文件存放，相加后的矩阵存入一个文件后在屏幕上显示1.2 主要任务我主要负责编写两个非零稀疏矩阵相乘的程序，两个已经经过压缩存储的矩阵，运用矩阵相乘的标准法来进行计算。

2 解决问题的主要思路和方法2.1 关键问题输入两个稀疏矩阵，进行两个矩阵相乘。

然后输出相乘后的结果。

2.2 拟采用解决问题的方法运用矩阵相乘的标准法进行编程序。

利用数组的顺序存储结构，实现特殊矩阵的压缩存储和稀疏矩阵的三元组存储和加法实现，利用稀疏矩阵的三元组存储，来实现两矩阵相乘。

先输入两个矩阵，判断前一个矩阵的列数是否已后一个矩阵的行数相等，不相等就返回错误，否则继续执行，接着就使用标准法进行计算。

完成后输出正确结果。

2.3 主要算法和处理流程图是是否是否是否i=1,j=1temp=0k=1,temp+=value(A,i,k)*value(B, k, j)A 的行数与B 的列数是否相等,p=1 输入矩阵A 、Bk++，k<= A.cols? 否C.rows=A.rows; C.cols = B.cols; eroNums= p-1;C.data[p].r = i;C.data[p].c = j; C.data[p].v = temp;p++;输出C 矩阵temp=0?j++，j <= B.cols ？i++，i <= A.rows?程序结束3 程序实现3.1 程序实现时应考虑的问题调用输入函数bool InputTSMatrix(T &M, int y)在三重循环中：for (i = 1; i <= A.rows; i++){for (j = 1; j <= B.cols; j++){temp = 0;for (k = 1; k <= A.cols; k++){temp += value(A, i, k) * value(B, k, j);调用函数int value(TSMatrix M, int i, int j)求得到矩阵元素M[i][j]的值。

课程数据结构题目3、三元组表相加1 问题要求及任务描述1.1 题目要求3、三元组表相加（2人）[问题描述] 利用数组的顺序存储结构，实现特殊矩阵的压缩存储和稀疏矩阵的三元组存储和加法实现[基本要求]利用稀疏矩阵的三元组存储，来实现两矩阵相加两个希疏矩阵分别用两个文件存放，相加后的矩阵存入一个文件后在屏幕上显示[测试数据]文件A：文件B：11 1110 1011，0，0，0，3，0，0，123，0，0 0，0，0，23，3，0，0，0，0，00，0，0，5，56，0，0，0，0，0 0，0，111，0，6，0，0，78，0，0 0，1，0，0，67，0，0，222，0，0 0，0，0，67，0，0，0，0，0，00，0，0，0，0，0，0，0，567，0 0，0，84，99，0，0，0，0，0，1 55，0，0，4，0，0，0，0，0，0 0，0，0，0，0，42，0，0，0，0 56，21，0，0，03，0，0，0，0，0 66，0，0，0，0，0，32，0，0，00，0，0，0，0，0，0，67，0，23 0，0，0，0，0，0，0，0，0,3450，0，0，0，55，0，0，0，0，0 88，0，0，0，0，0，0，0，0，00，0，23，0，0，0，0，0，234，0 0，0，0，0，0，0，0，0，0，00，0，0，0，6，0，0，123，0，0 0，0，0，11，0，0，0，0，0，01.2 主要任务[1]矩阵从文件中读取，并转化为稀疏矩阵的三元组存储。

[2]相加后的矩阵存入一个文件，从文件中读取矩阵在屏幕上显示。

2 解决问题的主要思路和方法2.1 关键问题1.矩阵的从文件当中读取，并转化为稀疏矩阵的三元组存储。

2.稀疏矩阵的三元组的加法实现。

3.相加后的矩阵存入文件。

2.2 拟采用解决问题的方法1.利用fgetc（）函数读取文件信息，并将读取到的矩阵转化为稀疏矩阵。

程序中的voidpp(FILE *fp, TriType *A) 函数；2.void AddMatrix(TriType a,TriType b,TriType *c)实现稀疏矩阵的三元组相加；3.void pull(FILE *fp,TriType &C)将矩阵C存入到文件中！期间用了fputc()；fprintf()函数。