精华内容
下载资源
问答
  • 三元组表示稀疏矩阵M与N,设计算法实现两个稀疏矩阵加法Q=M+N
  • [2]2带行表的矩阵相乘算法在用矩阵表示的图形中,可以发现矩阵中的零元素非常多,通常认为δ时称为稀疏矩阵(δ=非零元素个数/元素总数)。用上面的算法中,不论M(i,k)和N(k,j)的值是否为零,都要进行一次乘法运算,而实际...
  • 三元组稀疏矩阵

    千次阅读 2010-05-07 09:55:00
    允许自由转载,但必须注明作者和出处 Author: goal00001111 Date: 07-05-10 09:51 Description: 三元组稀疏矩阵类:实现了矩阵的转置,加法和乘法运算 */#include #include using namespace std;const int MAXTE

    /*
      Name: 三元组稀疏矩阵类
      始发于goal00001111的专栏;允许自由转载,但必须注明作者和出处
      Author: goal00001111
      Date: 07-05-10 09:51
      Description: 三元组稀疏矩阵类:实现了矩阵的转置,加法和乘法运算
    */
    #include <cstdlib>
    #include <iostream>

    using namespace std;

    const int MAXTERMS = 10000;

    template <typename T> class SparseMatrix;//前置声明

    template <typename T>
    class Trituple //三元组类
    {
        friend class SparseMatrix<T>;
    private:
        Trituple<T> & operator = (const Trituple<T> & b);
        int row, col;
        T value;
    };

    template <typename T> //重载赋值运算符
    Trituple<T> & Trituple<T>::operator = (const Trituple<T> & b)
    {
        if (this != &b)
        {
            row = b.row;
         col = b.col;
         value = b.value;
        }
       
        return *this;
    }

    template <typename T>
    class SparseMatrix //三元组稀疏矩阵类
    {
    public:
        SparseMatrix(int maxRow, int maxCol, int maxTerms = 0); //构造函数1
        SparseMatrix(const T a[], int maxRow, int maxCol);      //构造函数2
        SparseMatrix(const SparseMatrix<T> & b);      //拷贝构造函数
        SparseMatrix<T> & operator = (const SparseMatrix<T> & b);//重载赋值运算符
       
        void Display(); //输出三元组
        void DisArray();//输出矩阵
        SparseMatrix<T> Transpose();//三元组顺序表:转置矩阵
        SparseMatrix<T> FastTranspose();//三元组顺序表:快速转置矩阵
     SparseMatrix<T> Add(SparseMatrix<T> b);//矩阵相加
        SparseMatrix<T> Multiply(SparseMatrix<T> b);//矩阵相乘
    private:
        int rows, cols, terms;//矩阵的行数,列数和非零元素个数
        Trituple<T> smArray[MAXTERMS];//三元组顺序表
    };


    template <typename T> //构造函数1
    SparseMatrix<T>::SparseMatrix(int maxRow, int maxCol, int maxTerms):rows(maxRow), cols(maxCol), terms(maxTerms)
    {
    }

    template <typename T> //构造函数2:将二维数组转换为三元组
    SparseMatrix<T>::SparseMatrix(const T a[], int maxRow, int maxCol):rows(maxRow), cols(maxCol), terms(0)
    {
        for (int i=0; i<rows; i++)
        {
         for (int j=0; j<cols; j++)
         {
        if (a[i*cols+j] != 0)
        {
           smArray[terms].row = i;
        smArray[terms].col = j;      
            smArray[terms++].value = a[i*cols+j]; 
                }
       if (terms > MAXTERMS)
           return; 
      }
        }
    }

    template <typename T> //拷贝构造函数
    SparseMatrix<T>::SparseMatrix(const SparseMatrix<T> & b)
    {
        rows = b.rows;
        cols = b.cols;
        terms = b.terms;
       
        for (int i=0; i<terms; i++)
         smArray[i] = b.smArray[i];
    }

    template <typename T>//重载赋值运算符
    SparseMatrix<T> & SparseMatrix<T>::operator = (const SparseMatrix<T> & b)
    {
        if (this != &b)
        {
            rows = b.rows;
         cols = b.cols;
         terms = b.terms;
         for (int i=0; i<terms; i++)
          smArray[i] = b.smArray[i];
        }
       
        return *this;
    }

    template <typename T>//输出三元组
    void SparseMatrix<T>::Display()
    {
        cout << "rows = " << rows << ", cols = " << cols << ", terms = " << terms << endl;
        for (int i=0; i<terms; i++)
            cout << i+1 << "(" << smArray[i].row << ", " << smArray[i].col << ", "  << smArray[i].value << ")/t";
        cout << endl;
    }

    template <typename T>//输出矩阵:包括非零元素
    void SparseMatrix<T>::DisArray()
    {
        int top = 0;
        for (int i=0; i<rows; i++)
        {
         for (int j=0; j<cols; j++)
         {
        if (i == smArray[top].row && j == smArray[top].col)   
            cout << smArray[top++].value << " "; 
                else
                    cout << "0 ";
      }
      cout << endl;
        }
        cout << endl;
    }

    template <typename T>
    SparseMatrix<T> SparseMatrix<T>::Transpose()//三元组顺序表:转置矩阵
    {
     SparseMatrix<T> t(cols, rows, terms);
     
     if(terms > 0)
     {
            int top = 0;
      for(int j=0; j<cols; j++) //按照T的行序(M的列序)为主序依次排列
       for(int i=0; i<terms; i++)//扫描M的所有元素
        if(smArray[i].col == j)
        {
         t.smArray[top].row = smArray[i].col;
         t.smArray[top].col = smArray[i].row;
         t.smArray[top++].value = smArray[i].value;
        }//if
     } //else
     return t;
    }

    template <typename T>
    SparseMatrix<T> SparseMatrix<T>::FastTranspose()//三元组顺序表:快速转置矩阵
    {
        SparseMatrix<T> t(cols, rows, terms);
     int * colSize = new int[cols];//存储每列的非零元素个数
     int * colStart = new int[cols];//存储每列第一个非零元素在三元组中的位置(下标)
     
     if(terms > 0)
     {
            for(int i=0; i<cols; i++)
       colSize[i] = 0;
      for(int i=0; i<terms; i++)//扫描M的所有元素
       colSize[smArray[i].col]++; //确定矩阵M每一列中非零元素的个数
       
      colStart[0] = 0;// 确定矩阵M第i列中第一个非零元素在t.smArray中的位置
      for(int i=1; i<cols; i++)
       colStart[i] = colStart[i-1] + colSize[i-1];
       
      for(int i=0; i<terms; i++)//扫描M的所有元素
      {
       int k = colStart[smArray[i].col]; //k即矩阵M第col列中第一个非零元素在t.smArray中的位置
       t.smArray[k].row = smArray[i].col;
       t.smArray[k].col = smArray[i].row;
       t.smArray[k].value = smArray[i].value;
       colStart[smArray[i].col]++; //矩阵M第col列中第一个非零元素在t.smArray中的位置向前移动一位
      }//for    
     }//if
     
     delete []colSize;
     delete []colStart;
     
     return t;
    }

    template <typename T>
    SparseMatrix<T> SparseMatrix<T>::Add(SparseMatrix<T> b)//矩阵相加:采用合并算法,行序优先
    {
        SparseMatrix<int> c(cols, rows); 
     int i = 0, j = 0, k = 0;
     
     while (i < terms && j < b.terms)
     {
            if (smArray[i].row == b.smArray[j].row && smArray[i].col == b.smArray[j].col)
            {
                c.smArray[k].row = smArray[i].col;
       c.smArray[k].col = smArray[i].row;
       c.smArray[k].value = smArray[i++].value + b.smArray[j++].value; 
       if (c.smArray[k].value != 0)
           k++; 
            }
            else if ((smArray[i].row < b.smArray[j].row) ||(smArray[i].row == b.smArray[j].row && smArray[i].col < b.smArray[j].col))
          c.smArray[k++] = smArray[i++];
            else
                c.smArray[k++] = b.smArray[j++];
        }//while 
       
        if (i > terms) //A结束,若B还有元素,则将B的元素直接放入C中
        {
            while (j < b.terms)
                c.smArray[k++] = b.smArray[j++];
        }
        else //B结束,若A还有元素,则将A的元素直接放入C中
        {
            while (i < terms)
                c.smArray[k++] = smArray[i++];
        }
       
        c.terms = k;
       
        return c;
    }

    template <typename T> //矩阵相乘:快速乘法
    SparseMatrix<T> SparseMatrix<T>::Multiply(SparseMatrix<T> b)
    {  
     SparseMatrix<T> t(0, 0 , 0);
     if(b.rows != cols)
         return t;
        
     SparseMatrix<T> c(rows, b.cols);
     int * rowSize = new int[b.rows]; //存储b每行的非零元素个数
     int * rowStart = new int[b.rows];//存储b每行的首个非零元素位置
     int * ctemp = new int[b.cols]; //存储b中与a某个元素做乘法运算的第col列元素的累积值
     
     if(terms * b.terms != 0)//若C是非零矩阵
     {
      for(int i=0; i<b.rows; i++)
       rowSize[i] = 0;
      for(int i=0; i<b.terms; i++)//扫描b的所有元素
       rowSize[b.smArray[i].row]++; //确定矩阵b每一行中非零元素的个数
       
      rowStart[0] = 0;// 确定矩阵b第i行中第一个非零元素在b.smArray中的位置
      for(int i=1; i<b.rows; i++)
       rowStart[i] = rowStart[i-1] + rowSize[i-1];
      
      int k = 0, top = 0; 
      for(int i=0; i<rows; i++)//对A进行逐行处理,即对C进行逐行处理
      {
       for(int j=0; j<b.cols; j++)//当前各元素累加器清零
        ctemp[j] = 0;
       
       while (k < terms && smArray[k].row == i)//处理A的第i行元素
       {
                 int tc = smArray[k].col;
                 for (int j=rowStart[tc]; b.smArray[j].row == tc; j++)//处理B的第tc行数据:进行累积
                 {
          ctemp[b.smArray[j].col] += smArray[k].value * b.smArray[j].value;
        }
        k++;
             }
            
       for(int j=0; j<b.cols; j++)//得到C的第i行中每一个元素的值
       {
        if(ctemp[j] != 0)//压缩存储该行非零元
        {
         if(top == MAXTERMS)
          return t;
         c.smArray[top].row = i;
         c.smArray[top].col = j;
         c.smArray[top++].value = ctemp[j];//C的元素值等于A的行数ctemp[j]的累积值
        } //if(ctemp[j] != 0)
       }
      }//for arow
      c.terms = top;
     }
     
     delete []rowSize;
     delete []rowStart;
     delete []ctemp;
     
     return c;
    } //  MultSMatrix

    int main(int argc, char *argv[])
    {
      SparseMatrix<int> obja(2, 3);
      obja.Display();
      
      int arr[100] = {0};
      int r = 3, c = 3;
      for (int i=0; i<r; i++)
          for (int j=0; j<c; j++)
              cin >> arr[i*c+j];
       //
    //   for (int i=0; i<r; i++)
    //   {
    //      for (int j=0; j<c; j++)
    //          cout << arr[i*c+j] << " ";
    //        cout << endl;
    //   }
    //   cout << endl;
      
       SparseMatrix<int> objb(arr, r, c);
       objb.DisArray();
      
       SparseMatrix<int> objc = objb.Transpose();
       objc.DisArray();
      
       //obja = objc;
    //   objc.Display();
    //   objc.DisArray();
    //  
    //   SparseMatrix<int> objd = obja.Transpose();
    //   objd.Display();
    //   objd.DisArray();
    //  
       SparseMatrix<int> obje = objb.Multiply(objc);
       obje.Display();
       obje.DisArray();

      
        system("PAUSE");
        return EXIT_SUCCESS;
    }

    展开全文
  • 数据结构学习笔记9————马鞍点问题&三元组稀疏矩阵&十字链表稀疏链表的加减法 1.马鞍点问题 2.三元组稀疏矩阵的加减法 3.十字链表稀疏矩阵的加减法

    数据结构12————马鞍点问题&三元组稀疏矩阵&十字链表稀疏链表的加减法

    一.内容

    1. 马鞍点问题
    2. 三元组稀疏矩阵的加减法
    3. 十字链表稀疏矩阵的加减法

    二.求矩阵的马鞍点

    1.问题描述

    这里写图片描述

    2.思路

    • 求出每一行的最小值,存到minrows数组中
    • 求出每一列的最大值,存到maxcols数组中
    • 寻找是否存在i和j,使minrows[i]==maxcols[j],如果存在a[i][j]就是马鞍点,否则不存在。

    3.代码

    #include <stdio.h>
    #define MAX 50 
    int main(void){
    	int i,j;
    	int a[MAX][MAX];
    	int rows,cols;
    	int minrows[MAX],maxcols[MAX];//存储这一行最小和这一行最大值 
    	int flag=0;
    	scanf("%d%d",&rows,&cols);
    	for(i=0;i<rows;i++){
    		for(j=0;j<cols;j++){
    			scanf("%d",&a[i][j]);
    		}
    	}
    	
    	for(i=0;i<rows;i++){
    		minrows[i]=a[i][0];
    		for(j=1;j<cols;j++){
    			if(minrows[i]>a[i][j])
    				minrows[i]=a[i][j];
    		}
    	}	
    	
    	for(j=0;j<cols;j++){
    		maxcols[j]=a[0][j];
    		for(i=0;i<rows;i++){
    			if(maxcols[j]<a[i][j])
    				maxcols[j]=a[i][j];
    		}
    		
    	}
    	
    	for(i=0;i<rows;i++){
    		for(j=0;j<cols;j++){
    			if(minrows[i]==maxcols[j])
    			{
    				printf("(%d,%d,%d)",i+1,j+1,a[i][j]);
    				flag=1;
    			}	
    		}
    	}
    	if(flag==0){
    		printf("NONE");
    	}
    } 
    

    三.三元组稀疏矩阵的加减法

    1.问题描述

    这里写图片描述

    2.代码

    #include <stdio.h>
    #define MAXSIZE 100
    typedef int ElementType;
    typedef struct{
    	int row,col;           //row行号,col列号 
    	ElementType value;
    }Triple;
    typedef struct{
    	Triple data[MAXSIZE+1];
    	int rows,clos,nums;       //rows稀疏矩阵的行数,clos稀疏矩阵的列数,nues非0原的个数 
    }TSMatrix; 
    
    TSMatrix *Creation(){      //创建 
    	TSMatrix *TS;
    	Triple Tr;
    	char c;
    	TS = (TSMatrix *)malloc(sizeof(TSMatrix));
    	scanf("%d%d%d",&TS->rows,&TS->clos,&TS->nums); 
    	int i;
    	getchar();;//这句是为了应付学校的acm
    	for(i=0;i<TS->nums;i++){
    		scanf("%c%d%c%d%c%d%c",&c,&Tr.row,&c,&Tr.col,&c,&Tr.value,&c);
    		TS->data[i]=Tr;
    	}
    	return TS;
    } 
    
    void Output(TSMatrix *TS){ //输出 
    	int i;
    	printf("%d %d %d\n",TS->rows,TS->clos,TS->nums);
    	for(i=0;i<TS->nums;i++){
    		printf("(%d,%d,%d)",TS->data[i].row,TS->data[i].col,TS->data[i].value);
    	}
    	printf("\n");
    }
    TSMatrix *Add(TSMatrix *TS1,TSMatrix *TS2){ //加法 
    	int i=0,j=0;
    	TSMatrix *TS3;
    	Triple Tr;
    	TS3 = (TSMatrix *)malloc(sizeof(TSMatrix));
    	TS3->nums=0;
    	
    	while(i<TS1->nums&&j<TS2->nums){
    		if(TS1->data[i].row<TS2->data[j].row){       //TS1行号小于TS2 
    			Tr=TS1->data[i];
    			i++;
    		}else if(TS1->data[i].row>TS2->data[j].row){ //TS1行号大于TS2 
    			Tr=TS2->data[j];
    			j++; 
    		}else if(TS1->data[i].col<TS2->data[j].col){  //TS1行号等于TS2 TS1列号小于TS2 
    			Tr=TS1->data[i];
    			i++;
    		}else if(TS1->data[i].col>TS2->data[j].col){  //TS1行号等于TS2 TS1列号大于TS2 
    			Tr=TS2->data[j];
    			j++;
    		}else {         //TS1行号列号等于TS2 ,即相加 
    			Tr=TS1->data[i];
    			Tr.value= TS1->data[i].value+TS2->data[j].value;
    			i++;
    			j++;
    		} 
    		if(Tr.value	!=0){
    				TS3->data[TS3->nums]=Tr;
    				TS3->nums++;
    		}	
    	}
    	while(i<TS1->nums){
    		TS3->data[TS3->nums]=TS1->data[i];
    		i++;TS3->nums++;
    	}
    	while(j<TS2->nums){
    		TS3->data[TS3->nums]=TS2->data[j];
    		j++;TS3->nums++;
    	}
    	TS3->rows=TS2->rows;
    	TS3->clos=TS2->clos;
    	return TS3;
    }
     
    TSMatrix *Sub(TSMatrix *TS1,TSMatrix *TS2){  //减法 
    	int i=0,j=0,t;
    	TSMatrix *TS3;
    	Triple Tr;
    	TS3 = (TSMatrix *)malloc(sizeof(TSMatrix));
    	TS3->nums=0;
    	while(i<TS1->nums&&j<TS2->nums){
    		if(TS1->data[i].row<TS2->data[j].row){       //TS1行号小于TS2 
    			Tr=TS1->data[i];
    			i++;
    		}else if(TS1->data[i].row>TS2->data[j].row){ //TS1行号大于TS2 
    			Tr=TS2->data[j];
    			Tr.value=-Tr.value;
    			j++;
    		}else if(TS1->data[i].col<TS2->data[j].col){  //TS1行号等于TS2 TS1列号小于TS2 
    			Tr=TS1->data[i];
    			i++;
    		}else if(TS1->data[i].col>TS2->data[j].col){  //TS1行号等于TS2 TS1列号大于TS2 
    			Tr=TS2->data[j];
    			Tr.value=-Tr.value;
    			j++;
    		}else { 
    			Tr=TS1->data[i];									//TS1行号列号等于TS2 
    			Tr.value=TS1->data[i].value - TS2->data[j].value;
    			i++;j++;
    		} 
    		
    		if(Tr.value!=0){
    				TS3->data[TS3->nums]=Tr;
    				TS3->nums++;
    		}	
    	}
    	while(i<TS1->nums){
    		TS3->data[TS3->nums]=TS1->data[i];
    		i++;TS3->nums++;
    	}
    	while(j<TS2->nums){
    		Tr=TS2->data[j];
    		Tr.value=-TS2->data[j].value;
    		TS3->data[TS3->nums]=Tr;
    		j++;TS3->nums++;
    	}
    	TS3->rows=TS2->rows;
    	TS3->clos=TS2->clos;
    	return TS3;
    }
    int main(void){
    	TSMatrix *TS1;
    	TSMatrix *TS2;
    	TSMatrix *TS3;
    	TSMatrix *TS4;
    	TS1=Creation();
    	TS2=Creation(); 
    	TS3=Add(TS1,TS2);
    	TS4=Sub(TS1,TS2); 
    	Output(TS3);
    	Output(TS4);
    	
    }
    

    四.十字链表稀疏矩阵的加减法

    1.问题描述

    这里写图片描述

    2.代码

    #include <stdio.h>
    #include <stdlib.h>
    #define MAX 50
    typedef int Elemtype;
    typedef struct OLnode{
    	int row,col;
    	Elemtype value;
    	struct OLnode *right,*down;
    }OLNode,*OLink;
    typedef struct {
    	OLink rowhead[MAX],colhead[MAX];
    	int rows,cols,nums;
    }CrosList;
    
    void Insert(CrosList *CL,OLNode *node){ //插入 
    	OLNode *p;
    	node->right=NULL;
    	node->down=NULL;
    	
    	//插入到行中 
    	if(CL->rowhead[node->row-1]==NULL)
    		CL->rowhead[node->row-1]=node;
    	else{                           //插入到行链里 
    		p=CL->rowhead[node->row-1];
    		while(p->right&&node->row > p->right->row){
    			p=p->right;
    		};
    		node->right=p->right;
    		p->right=node;
    	}
    		
    	if(CL->colhead[node->col-1]==NULL)
    		CL->colhead[node->col-1]=node;
    	else{                           //插入到列链中 
    		p=CL->colhead[node->col-1];
    		while(p->down&&node->col > p->down->col){
    			p=p->down;
    		};
    		node->down=p->down;
    		p->down=node;
    	}
    }
    
    CrosList *Creation(){ //创建 
    	CrosList *CL;
    	OLNode *node;
    	OLNode *p;
    	CL = (CrosList *)malloc(sizeof(CrosList));
    	scanf("%d%d%d",&CL->rows,&CL->cols,&CL->nums);
    	int i;
    	for(i=0;i<CL->rows;i++)
    		CL->rowhead[i]=NULL;
    	for(i=0;i<CL->cols;i++)
    		CL->colhead[i]=NULL;
    		 
    	 getchar();
    	for(i=0;i<CL->nums;i++){
    		node = (OLNode*)malloc(sizeof(OLNode));
    		scanf("(%d,%d,%d)",&node->row,&node->col,&node->value);
    		Insert(CL,node); //插入 
    	}
    	return CL;
    } 
    void Output(CrosList *CL){  //输出 
    	int i;
    	OLNode *node;
    	if(CL==NULL)
    		return; 
    	printf("%d %d %d\n",CL->rows,CL->cols,CL->nums);
    	for(i=0;i<CL->rows;i++){
    		node = CL->rowhead[i];
    		while(node){
    			printf("(%d,%d,%d)",node->row,node->col,node->value);
    			node=node->right;			
    		}
    		
    	} 
    	printf("\n");
    	
    	/*printf("%d %d %d",CL->rows,CL->cols,CL->nums); //列优先输出 
    	for(i=0;i<CL->cols;i++){
    		node = CL->colhead[i];
    		while(node){
    			printf("(%d,%d,%d)",node->row,node->col,node->value);
    			node=node->down;			
    		}
    	} 
    	printf("\n");*/
    
    } 
    
    int Inquire (CrosList *CL,OLNode *node){  //查询该位置是否有元素
    	int i=node->row;
    	int j=node->col;
    	OLNode *p;
    	if(CL->rowhead[i]==NULL||CL->colhead[j]==NULL)
    		return 0;
    	p=CL->rowhead[i];
    	while(p&&p->row!=node->row&&p->col!=node->col){
    		p=p->right;	
    	} 
    	if(p->row==node->row && p->col==node->col)
    		return 1;
    		
    	return 0;
    } 
    CrosList *ADD(CrosList *CL1,CrosList *CL2){
    	OLNode *pi,*pj,*pk;
    	int i;
    	CrosList *CL3;
    	CL3 = (CrosList *)malloc(sizeof(CrosList));
    	CL3->rows=CL1->rows;
    	CL3->cols=CL2->cols;
    	CL3->nums=0; 
    	for(i=0;i<CL3->rows;i++)//初始化 
    		CL3->rowhead[i]=NULL;
    	for(i=0;i<CL3->cols;i++)
    		CL3->colhead[i]=NULL;
    		
    	for(i=0;i<CL1->rows;i++){
    		pi = CL1->rowhead[i];
    		pj = CL2->rowhead[i];
    		while(pi&&pj){
    			pk=(OLNode*)malloc(sizeof(OLNode));
    			if(pi->row < pj->row){        //CL1行号小于CL2 
    				pk->row=pi->row;
    				pk->col=pi->col;
    				pk->value=pi->value;
    				pi=pi->right;
    			}else if(pi->row > pj->row){   //CL1行号大于CL2 
    				pk->row=pj->row;
    				pk->col=pj->col;
    				pk->value=pj->value;
    				pj=pj->right;
    			}else if(pi->col < pj->col ){   //CL1行号等于Cl2 Cl1列号小于Cl2
    				pk->row=pi->row;
    				pk->col=pi->col;
    				pk->value=pi->value;
    				pi=pi->right;
    			}else if(pi->col > pj->col ){    //CL行号等于CL2 Cl1列号大于Cl2 
    				pk->row=pj->row;
    				pk->col=pj->col;
    				pk->value=pj->value;
    				pj=pj->right;
    			}else{							//CL1行号列号等于CL2 ,即相加 
    				pk->row=pi->row;
    				pk->col=pi->col;
    				pk->value=pi->value+pj->value;
    				pi=pi->right;
    				pj=pj->right;
    			}
    			if(pk->value!=0){
    				Insert(CL3,pk);//插入 
    				CL3->nums++;	
    			}		
    						
    		}
    		while(pi){
    			pk=(OLNode*)malloc(sizeof(OLNode));
    			pk->row=pi->row;
    			pk->col=pi->col;
    			pk->value=pi->value;
    			pi=pi->right;	
    			Insert(CL3,pk);//插入 
    			CL3->nums++;
    		}
    		while(pj){
    			pk=(OLNode*)malloc(sizeof(OLNode));
    			pk->row=pj->row;
    			pk->col=pj->col;
    			pk->value=pj->value;
    			pj=pj->right;	
    			Insert(CL3,pk);//插入 
    			CL3->nums++;
    		}
    	} 
    	return CL3;
    } 
    CrosList *Sub(CrosList *CL1,CrosList *CL2){
    	OLNode *pi,*pj,*pk;
    	int i;
    	CrosList *CL4;
    	CL4 = (CrosList *)malloc(sizeof(CrosList));
    	CL4->rows=CL1->rows;
    	CL4->cols=CL2->cols;
    	CL4->nums=0; 
    	for(i=0;i<CL4->rows;i++)//初始化 
    		CL4->rowhead[i]=NULL;
    	for(i=0;i<CL4->cols;i++)
    		CL4->colhead[i]=NULL;
    		
    	for(i=0;i<CL1->rows;i++){
    		pi = CL1->rowhead[i];
    		pj = CL2->rowhead[i];
    		while(pi&&pj){
    			pk=(OLNode*)malloc(sizeof(OLNode));
    			if(pi->row < pj->row){        //CL1行号小于CL2 
    				pk->row=pi->row;
    				pk->col=pi->col;
    				pk->value=pi->value;
    				pi=pi->right;
    			}else if(pi->row > pj->row){   //CL1行号大于CL2 
    				pk->row=pj->row;
    				pk->col=pj->col;
    				pk->value=-pj->value;
    				pj=pj->right;
    			}else if(pi->col < pj->col ){   //CL1行号等于Cl2 Cl1列号小于Cl2
    				pk->row=pi->row;
    				pk->col=pi->col;
    				pk->value=pi->value;
    				pi=pi->right;
    			}else if(pi->col > pj->col ){    //CL行号等于CL2 Cl1列号大于Cl2 
    				pk->row=pj->row;
    				pk->col=pj->col;
    				pk->value=-pj->value;
    				pj=pj->right;
    			}else{							//CL1行号列号等于CL2 ,即相加 
    				pk->row=pi->row;
    				pk->col=pi->col;
    				pk->value=pi->value-pj->value;
    				pi=pi->right;
    				pj=pj->right;
    			}
    			if(pk->value!=0){
    				Insert(CL4,pk);//插入 
    				CL4->nums++;	
    			}		
    						
    		}
    		while(pi){
    			pk=(OLNode*)malloc(sizeof(OLNode));
    			pk->row=pi->row;
    			pk->col=pi->col;
    			pk->value=pi->value;
    			pi=pi->right;	
    			Insert(CL4,pk);//插入 
    			CL4->nums++;
    		}
    		while(pj){
    			pk=(OLNode*)malloc(sizeof(OLNode));
    			pk->row=pj->row;
    			pk->col=pj->col;
    			pk->value=- pj->value;
    			pj=pj->right;	
    			Insert(CL4,pk);//插入 
    			CL4->nums++;
    		}
    	} 
    	return CL4;
    } 
    int main(void){
    	CrosList *CL1=NULL;
    	CrosList *CL2=NULL;
    	CrosList *CL3=NULL;
    	CrosList *CL4=NULL;
    	CL1=Creation();
    	CL2=Creation();
    	CL3=ADD(CL1,CL2);
    	CL4=Sub(CL1,CL2);
    	Output(CL3);
    	Output(CL4);
    }
    
    

    五.源代码

    test11中

    展开全文
  • 稀疏矩阵

    稀疏矩阵

    本文使用了C++封装稀疏矩阵类,静态数组存储,实现了矩阵加法与乘法。

    tips

    1. 稀疏矩阵:对零元素不分配存储空间
    2. 三元组结构——行,列,值
    3. 写程序与调试建议
    • 先实现构造函数,printTriple和printMatrix函数,分别显示三元组数组,显示稀疏矩阵
    • 实现getItem函数,给定一个行、列、非零元的值,看看能否正确读取稀疏矩阵中的内容
    • 写输入函数和setItem函数,实现稀疏矩阵的插入
    • 写加法
    • 写乘法

    难点

    • setItem函数,一定要记得测试三元组数组为空的时候能否正确插入,异常考虑
    • 加法和乘法要先验证能不能加(同型),能不能乘(a的列=b的行)
    #include <iostream>
    using namespace std;
    
    #define MAX 100
    #define ERROR 0
    #define OK 1
    typedef int Status;//函数结果状态类型 
    typedef int DataType;
    
    typedef struct
    {
    	int row, col;
    	DataType item;
    }Triple;
    
    class TripleMatrix
    {
    private:
    	Triple data[MAX];
    	int mu, nu;
    	DataType num;//行 列  非零元个数
    public:
    	TripleMatrix();
    	TripleMatrix(int m, int n);//行 列
    	~TripleMatrix() {};
    	Status setItem(int row, int col, DataType item);
    	int getItem(int row, int col);
    	void printMatrix();
    	void printTriple();
    	friend void inputMatrix(int m, int n, int num, TripleMatrix &triple);
    	friend bool matrixAdd(TripleMatrix &a, TripleMatrix &b);
    	friend bool matrixMulity(TripleMatrix &a, TripleMatrix &b);
    };
    
    TripleMatrix::TripleMatrix()//默认构造函数
    {
    	mu = 0;
    	nu = 0;
    	num = 0;
    }
    
    TripleMatrix::TripleMatrix(int m, int n)
    {
    	this->mu = m;
    	this->nu = n;
    	this->num = 0;
    }
    
    int TripleMatrix::getItem(int row, int col)
    {
    	if (row > mu || col > nu)
    		return ERROR;
    
    	for (int i = 0; i < num; i++)
    	{
    		if (data[i].row == row && data[i].col == col)
    		{
    			return data[i].item;
    		}
    	}
    	return 0;
    }
    
    Status TripleMatrix::setItem(int row, int col, DataType item)
    {
    	if (row > mu || col > nu)
    		return ERROR;
    
    	if (num == MAX)
    		return ERROR;//超出数组范围
    
    	if (item == 0)
    		return OK;//输入的是直接不做返回
    
    	int index = 0;
    
    	//找位置 
    	while (index < num) //num是非零元的个数 
    	{
    		if (row > data[index].row)
    		{
    			index++;
    		}
    		else if (row == data[index].row && col > data[index].col)
    		{
    			index++;
    		}
    		else break;
    	}
    
    	//如果已经有了,则改变item域的值 
    	if (row == data[index].row && col == data[index].col)
    	{
    		data[index].item = item;
    	}
    	else
    	{
    		//插入新元素,最后一位往后移
    		for (int i = num; i > index; i--)
    		{
    			data[i] = data[i - 1];
    			//以下同上! 
    			//data[i].row = data[i-1].row;
    			//data[i].col= data[i-1].col;
    			//data[i].item = data[i-1].item;
    		}
    
    		data[index].row = row;
    		data[index].col = col;
    		data[index].item = item;
    		num++;
    	}
    	return OK;
    }
    
    void TripleMatrix::printMatrix()
    {
    	int triplenum = 0;//控制三元组data下标,第几个三元组 
    	cout << "打印矩阵:\n";
    	for (int i = 1; i <= mu; i++)//i j从1开始 
    	{
    		for (int j = 1; j <= nu; j++)
    		{
    			if (i == data[triplenum].row && j == data[triplenum].col)
    			{
    				cout << data[triplenum].item << "\t";
    				triplenum++;
    			}
    			else
    			{
    				cout << "0\t";
    			}
    		}
    		cout << endl;
    	}
    	cout << "矩阵有" << mu << "行," << nu << "列," << "共" << num << "个非零元素" << endl;
    	return;
    }
    
    void TripleMatrix::printTriple()
    {
    	cout << "打印三元组:\n";
    	cout << "row\tcol\titem\n";
    	for (int i = 0; i < num; i++)
    	{
    		cout << data[i].row << "\t" << data[i].col << "\t" << data[i].item << "\t" << endl;
    	}
    }
    
    void inputMatrix(int m, int n, int num, TripleMatrix &triple)
    {
    	for (int i = 0; i < num; i++)
    	{
    		int r, c, val;
    		cout << "第" << i + 1 << "组:" << endl;
    		cout << "请输入行,列,值" << endl;
    		cin >> r >> c >> val;
    		if (triple.setItem(r, c, val) == ERROR)
    		{
    			cout << "行号列号不正确,或三元组满" << endl;
    			break;
    		}
    		if (triple.setItem(r, c, val) == OK)
    		{
    			cout << "成功" << endl;
    			continue;
    		}
    	}
    }
    
    bool matrixAdd(TripleMatrix &a, TripleMatrix &b)
    {
    	//同型矩阵才可以进行运算 
    	if (a.mu != b.mu && a.nu != b.nu)
    	{
    		cout << "矩阵不能进行计算" << endl;
    		return ERROR;
    	}
    	else
    	{
    		TripleMatrix c(a.mu, a.nu);
    		for (int i = 1; i <= a.mu; i++)
    		{
    			for (int j = 1; j <= a.nu; j++)
    			{
    				//if(a.getItem(i,j) != 0 && b.getItem(i,j) != 0)
    				//不能这么卡条件,因为可能3+(-3)=0 不用存储 
    				int temp = a.getItem(i, j) + b.getItem(i, j);
    				if (temp != 0)//如果计算结果为0,什么都不做setItem
    				{
    					c.setItem(i, j, temp);
    				}
    			}
    		}
    		c.printMatrix();
    		return OK;
    	}
    }
    
    bool matrixMulity(TripleMatrix &a, TripleMatrix &b)
    {
    	//a的列等于b的行:a.nu == b.mu
    	if (a.nu != b.mu)
    	{
    		cout << "矩阵不能进行计算" << endl;
    		return ERROR;
    	}
    	else
    	{
    		TripleMatrix c(a.mu, b.nu);
    		int i, j, k,sum;
    		for (i = 1; i <= a.mu; i++)
    		{
    			for (j = 1; j <= b.nu; j++)//j<=k
    			{
    				sum = 0;//这里要使sum=0重新算下一个值
    				for(k = 1; k<= a.nu; k++)//k<=b.mu
    				{
    					sum += a.getItem(i, k) * b.getItem(k, j);
    					
    				}
    				if (sum != 0)//如果计算结果为0,什么都不做setItem
    				{
    					c.setItem(i, j, sum);
    				}
    			}
    		}
    		c.printMatrix();
    		return OK;
    	}
    }
    
    
    int main()
    {
    	int m, n, num;
    	cout << "输入第一个矩阵的行,列,输入几组三元组" << endl;
    	cin >> m >> n >> num;
    
    	TripleMatrix triple1(m, n);
    	inputMatrix(m, n, num, triple1);
    	//triple.printTriple();
    	triple1.printMatrix();
    
    	cout << "输入第二个矩阵的行,列,输入几组三元组" << endl;
    	cin >> m >> n >> num;
    
    	TripleMatrix triple2(m, n);
    	inputMatrix(m, n, num, triple2);
    	//triple.printTriple();
    	triple2.printMatrix();
    
    	cout << "输入第三个矩阵的行,列,输入几组三元组" << endl;
    	cin >> m >> n >> num;
    
    	TripleMatrix triple3(m, n);
    	inputMatrix(m, n, num, triple3);
    	//triple.printTriple();
    	triple3.printMatrix();
    
    	if(matrixAdd(triple1, triple2)) cout<<"加法成功!";
    	if(matrixMulity(triple1, triple3)) cout << "乘法成功!";
    	
    	system("pause");
    	return 0;
    }
    

    测试案例

    第一组:3*4 43 4 4
    1 1 2
    2 1 13
    3 4 1
    2 2 1
    
    
    第二组:3*4 43 4 4
    1 1 2
    2 1 1
    3 3 2
    3 4 5
    
    第三组:4*3  54 3 5
    1 1 3
    1 2 1
    2 2 1
    4 1 1
    4 3 5
    

    结果

    第一组
    第二组
    第三组
    加法乘法

    改进方向

    1. 用十字链表实现
    2. 本文加法乘法实现在函数中打印出结果,最好还是将结果传出来
      比如类内的声明这样写:
    friend bool matrixAdd(TripleMatrix a,TripleMatrix b,TripleMatrix &result); 
    friend bool matrixMulity(TripleMatrix a,TripleMatrix b,TripleMatrix &result); 
    
    展开全文
  • 三元组实现的稀疏矩阵加法

    千次阅读 2019-04-14 19:30:39
    【问题】稀疏矩阵加法,输入任意两个稀疏矩阵A和B,求出它们的和矩阵C。 【思路】 比较满足条件(行数及列数都相同的两个矩阵)的两个稀疏矩阵中不为零的元素的行号及列号(即i与j),将i与j都相等的AB中两个元素...

    【问题】稀疏矩阵的加法,输入任意两个稀疏矩阵A和B,求出它们的和矩阵C。

    【思路】 比较满足条件(行数及列数都相同的两个矩阵)的两个稀疏矩阵中不为零的元素的行号及列号(即i与j),将i与j都相等的AB中两个元素值相加,若相加结果不为零则保持i,j不变存储在新的三元组C中 ;若不等的话则按行递增的顺序分别储存在新的三元组中。最后得到的这个新三元组表就是两个矩阵的和矩阵的三元组表。
    5种情况:
    A.data[m].row=B.data[n].row 且A.data[m].col=B.data[n].col
    A.data[m].row=B.data[n].row 且A.data[m].col<B.data[n].col
    A.data[m].row=B.data[n].row 且A.data[m].col>B.data[n].col
    A.data[m].row<B.data[n].row
    A.data[m].row>B.data[n].row

    【提醒】在解决此问题前先弄清楚稀疏矩阵的存储有利于更好的解决问题。本文处理的是以按行递增方式储存的稀疏矩阵。

    
    #include<iostream>
    using namespace std;
    const int MaxTerm = 100;
    
    template<class DataType>
    struct element
    {
        int row,col;
        DataType item;
    };
    
    template<class DataType>
    struct SparseMatrix
    {
        element<DataType> data[MaxTerm];
        int mu,nu,tu;     //行数列数与非零个数
    };
    
    bool MatAdd(SparseMatrix<int> Matrix_1, SparseMatrix<int> Matrix_2, SparseMatrix<int> &Matrix_tmp)
    {
        if(Matrix_1.mu != Matrix_2.mu || Matrix_1.nu != Matrix_2.nu)
            return 0;
    
        Matrix_tmp.mu = Matrix_1.mu;
        Matrix_tmp.nu = Matrix_1.nu;
    
        int i=0, j=0, k=0;
        int v;
        while(i<Matrix_1.tu && j<Matrix_2.tu)
        {
            if(Matrix_1.data[i].row == Matrix_2.data[j].row)
            {
                if(Matrix_1.data[i].col == Matrix_2.data[j].col)
                {
                    Matrix_tmp.data[k].row = Matrix_1.data[i].row;
                    Matrix_tmp.data[k].col = Matrix_1.data[i].col;
                    v = Matrix_1.data[i].item + Matrix_2.data[j].item;
                    if(v != 0)
                        Matrix_tmp.data[k].item = v;
                    i++;j++;k++;  //处理下一个元素
                }
                else if(Matrix_1.data[i].col < Matrix_2.data[j].col)
                {
                    Matrix_tmp.data[k].row = Matrix_1.data[i].row;
                    Matrix_tmp.data[k].col = Matrix_1.data[i].col;
                    Matrix_tmp.data[k].item = Matrix_1.data[i].item;
                    i++;k++;     
                 //Matrix_2还需进行下一轮比较(由稀疏矩阵的存储方式决的)
                }
                else if(Matrix_1.data[i].col > Matrix_2.data[j].col)
                {
                    Matrix_tmp.data[k].row = Matrix_2.data[j].row;
                    Matrix_tmp.data[k].col = Matrix_2.data[j].col;
                    Matrix_tmp.data[k].item = Matrix_2.data[j].item;
                    j++;k++;      //Matrix_1还需进行下一轮比较
                }
            }
    
            else if(Matrix_1.data[i].row < Matrix_2.data[j].row)
            {
                Matrix_tmp.data[k].row = Matrix_1.data[i].row;
                Matrix_tmp.data[k].col = Matrix_1.data[i].col;
                Matrix_tmp.data[k].item = Matrix_1.data[i].item;
                i++;k++;
            }
            else
            {
                Matrix_tmp.data[k].row = Matrix_2.data[j].row;
                Matrix_tmp.data[k].col = Matrix_2.data[j].col;
                Matrix_tmp.data[k].item = Matrix_2.data[j].item;
                j++;k++;
            }
        }
        Matrix_tmp.tu = k;
    
        return true;
    }
    
    SparseMatrix<int> CreatMat()
    {
        SparseMatrix<int> Matrix;
        int m,n,t;
        cout << "请输入矩阵行数列数以及非零元个数: ";
        cin >> m >> n >> t;
        Matrix.mu = m;
        Matrix.nu = n;
        Matrix.tu = t;
    
        for(int i=0; i<Matrix.tu; i++)
        {
            int row,col,item;
            cout << "输入矩阵元素所在的行、列以及它的值: ";
            cin >> row >> col >> item;
            Matrix.data[i].row = row;
            Matrix.data[i].col = col;
            Matrix.data[i].item = item;
        }
    
        return Matrix;
    }
    
    void Printf(SparseMatrix<int> T)
    {
        for(int i=0; i<T.tu; i++)
        {
            cout << " row: " << T.data[i].row << " "
                 << " col: " << T.data[i].col << " "
                 << " item: " << T.data[i].item << endl;
        }
    }
    
    int main()
    {
        SparseMatrix<int> Mat1,Mat2,Mat3;
        Mat1 = CreatMat();
        Mat2 = CreatMat();
        cout << "Mat1: " << endl;
        Printf(Mat1);
        cout << "Mat2: " << endl;
        Printf(Mat2);
        if(MatAdd(Mat1,Mat2,Mat3))
        {
            cout << "Mat1 + Mat2: " << endl;
            Printf(Mat3);
        }
        else
        {
            cout << "相加失败。" << endl;
        }
        return 0;
    }
    
    

    若有考虑不周之处,还望指正。

    展开全文
  • //稀疏矩阵加法 #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; }...
  • 利用三元组表对稀疏矩阵实现加法、减法及转置运算
  • 顺序执行下来,没有设置循环运行,有很多确认判断,很好用哦~
  • 稀疏矩阵加法

    2013-03-04 01:10:31
    稀疏矩阵A和B均以三元组顺序表作为存储结构。试设计算法,计算A+B,并将运算结果存于三元组顺序表C中。
  • 实现三元组表示的两个稀疏矩阵加法。相关定义如下: #define MAXSIZE 100 //假设非零元个数的最大值为100 typedef struct { int i,j; //非零元的行下标和列下标,i 和 j 从 1 开始计数,与数学中矩阵...
  • #include<stdio.h> #define MAXSIZE 1000 typedef struct node { int row,col,value; //行、列、值 }Triple; typedef struct lnode { Triple data[MAXSIZE];... //矩阵总行数、列数、非零元素个数 ... //矩阵输入
  • #include  #include  //函数结果状态码 #define OK 1 #define ERROR 0 #define OVERFLOW -1  //Status是函数的类型,其值是函数...// ----- 稀疏矩阵三元组顺序表存储表示 ----- #define MAXSIZE 100 
  • 目的: &nbsp;&nbsp;&nbsp;...1. 稀疏矩阵的存储结构采用行逻辑表示的三元组 2. #define MAXSIZE 12500 #define MAXRC 12500 typedef struct { int i, j; int e; }Triple; t...
  • 假设稀疏矩阵A和B均以三元组表作为存储结构。试写出矩阵相加的算法,另设三元组表C存放结果矩阵。稀疏矩阵三元组顺序表类型TSMatrix的定义:#define MAXSIZE 20 // 非零元个数的最大值typedef struct {int i,j; //...
  • 以下为功能函数的代码 #define MAXSIZE 12500 //最大非零元素 typedef int Elemtype; typedef struct Triple{ Elemtype value;... //三元组结点定义 typedef struct TSMatrix{ Triple data[MA...
  • 本程序以三元组表存储稀疏矩阵,可进行矩阵相加及转置运算。 TSMatrix A,B,C,D; cout请输入矩阵A和B的行数 列数 "; cin>>A.m>>A.n; B.m=C.m=D.m=A.m; B.n=C.n=D.n=A.n; cout请输入A中的非零元素个数: "; ...
  • 题目:假设稀疏矩阵A和B均以三元组表作为存储结构,试写出矩阵相加和相乘的算法,另设三元组表C存放结果矩阵。 要求: 从键盘输入稀疏矩阵A和B 检测A和B能否相加/相乘 如能,做矩阵相加和相乘运算,并打印运算结果 ...
  • 三元组表示稀疏矩阵并相加

    千次阅读 2020-06-27 08:53:47
    数据结构实验设计:三元组稀疏矩阵相加
  • (c语言)稀疏矩阵加法

    千次阅读 2020-04-17 15:01:38
    实现三元组表示的两个稀疏矩阵加法。相关定义如下 #define MAXSIZE 100 //假设非零元个数的最大值为100 typedef struct { int i,j; //非零元的行下标和列下标,i 和 j 从 1 开始计数,与数学中矩阵元素的...
  • 三元组顺序表加法实现A+B,不增加A,B之外的储存空间,O(M+N)的时间复杂度参考链接先定义需要用到类接下来便是算法的主体部分了(略微冗长)方法二 (效率较低的版本) 参考链接 链接: ...
  • 实现使用三元组表存储的稀疏矩阵加法 代码: #include<iostream> using namespace std; const int MAXSIZE=1000; typedef struct{ int row,col; int elem; //假设非零元素为整型 }triple; typedef ...
  • /* ...*All right resvered . *文件名称: 稀疏矩阵.cpp *作 者: 郑兆涵 *稀疏矩阵三元组表示的实现及应用(2) ...(2)采用三元组存储稀疏矩阵,设计两个稀疏矩阵相加的运算算法 提示1:两个行
  • 稀疏矩阵三元组进行加法

    千次阅读 多人点赞 2018-04-14 23:38:08
    算法思想:在进行三元组加法时前提条件:用while循环,它的出口条件为 i,j 都小于他们分别所对应的三元组中元素的个数。满足前提条件的情况下,分3种情况:1. 行列数相等;(1)相加等于零,则直接跳过,i++;j++;...
  • /* ... *All rights reserved. *文件名称:xishujuzhen.cpp *作者:朱希康 *完成日期:2015年11月9日 ...*问题描述:稀疏矩阵加法 *输入描述:无 *程序输出:稀疏矩阵的加法 */ #ifndef TUP_H_INCLUDED #define T
  • 稀疏矩阵计算器(三元组实现矩阵加减乘法)

    千次阅读 多人点赞 2019-10-25 19:06:07
    以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵,实现两个矩阵相加、相减和相乘的运算。稀疏矩阵的输入形式采用三元组表示,而运算结果的矩阵则以通常的阵列形式列出。稀疏矩阵的输出要求:矩阵的行数、列数、非...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 612
精华内容 244
关键字:

三元组稀疏矩阵的加法