☆~
2021-06-23 12:26
采纳率: 100%
浏览 30

怎么用c语言实现一下稀疏矩阵操作?

要求用C语言编写
实现三元组,十字链表下的稀疏矩阵的加、转、乘的实现。
(1)稀疏矩阵的存储
(2)稀疏矩阵加法
(3)矩阵乘法
(4)矩阵转置

求各位大神指点!!!求源代码,最好有注释

 

  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

1条回答 默认 最新

  • CSDN专家-sinjack 2021-06-23 12:29
    已采纳

    如有帮助,请采纳。点击我回答右上角【采纳】按钮。

    #include<iostream>
    using namespace std;
    typedef  int  ElemType ;
    #define M 4  //稀疏矩阵行数
    #define N 4  //稀疏矩阵列数
    #define MaxSize  6  //非零元素最多个数
    //三元组类型定义
    typedef struct
    {
    	int r;         //行号  
    	int c;          //列号  
    	ElemType d;     //元素值  
    } TupNode;         //三元组定义  
    typedef struct
    {
    	int rows;      //行数  
    	int cols;     //列数  
    	int nums;       //非零元素个数  
    	TupNode data[MaxSize];
    } TSMatrix;    //三元组顺序表定义  
    //十字链表类型定义
    typedef struct mtxn
    {
    	int row;   //行号
    	int col;    //列号
    	struct mtxn *right, *down;  //向右和向下的指针
    	union
    	{
    		ElemType value;   //非零元素值
    		struct mtxn *link;  //指向下一个头结点
    	}tag;
    }MatNode;
    
    
    //三元组创建
    void Create_1(TSMatrix &t, ElemType A[M][N])
    {
    	int i, j;
    	t.rows = M;
    	t.cols = N;
    	t.nums = 0;
    	for (i = 0; i < M; i++)
    	{
    		for (j = 0; j < N; j++)
    		{
    			if (A[i][j] != 0)    //元素值不为零,建立三元组
    			{
    				t.data[t.nums].r = i;
    				t.data[t.nums].c = j;
    				t.data[t.nums].d = A[i][j];
    				t.nums++;
    			}
    		}
    	}
    }
    //十字链表创建
    void Create_2(MatNode *&mh, ElemType a[M][N])
    {
    	int i, j;
    	MatNode *h[MaxSize], *p, *q, *r;
    	mh = (MatNode *)malloc(sizeof(MatNode));   //创建十字链表的头节点
    	mh->row = M;
    	mh->col = N;
    	r = mh;   //r指向尾节点
    	for (i = 0; i < MaxSize; i++)   //采用尾插法创建循环表
    	{
    		h[i] = (MatNode *)malloc(sizeof(MatNode));
    		h[i]->down = h[i]->right = h[i];	//将down和right方向量置为循环的
    		r->tag.link = h[i];  //将h[i]加到链表中
    		r = h[i];
    	}
    	r->tag.link = mh;   //置为循环链表
    
    
    	for (i = 0; i < M; i++)    //处理每一行
    	{
    		for (j = 0; j < N; j++)    //处理每一列
    		{
    			if (a[i][j] != 0)   //处理非零元素
    			{
    				p = (MatNode *)malloc(sizeof(MatNode));	  //创建一个新节点
    				p->row = i;
    				p->col = j;
    				p->tag.value = a[i][j];
    				q = h[i];   //查找在行表中插入位置
    				while (q->right != h[i] && q->right->col < j)
    				{
    					q = q->right;
    				}
    				p->right = q->right;
    				q->right = p;			//完成行表的操作
    				q = h[j];      //查找在链表中插入的位置
    
    				while (q->down != h[j] && q->down->row < i)
    				{
    					q = q->down;
    				}
    				p->down = q->down;
    				q->down = p;			//完成列表的插入
    			}
    		}
    
    	}
    }
    
    
    //输出三元组矩阵 
    void  DispMat_1(TSMatrix t)
    {
    	int k;
    	if (t.nums <= 0)
    	{
    		return ;
    	}
    	cout << t.rows << "\t" << t.cols << "\t" << t.nums << endl;
    	cout << "=====================" << endl;
    	cout << "行数" << " " << " 列数" << " " << "非零元素" << endl;
    	for (k = 0; k < t.nums; k++)
    	{
    		cout << t.data[k].r << '\t' << t.data[k].c << '\t' << t.data[k].d << endl;
    	}
    }
    //输出十字链表矩阵
    void DispMat_2(MatNode *mh)
    {
    	MatNode *p, *q;
    	cout << "行=" << mh->row << "列=" << mh->col << endl;
    	p = mh->tag.link;
    	while (p != mh)
    	{
    		q = p->right;
    		while (p != q)				//输出一行非零元素
    		{
    			cout << q->row << '\t' << q->col << '\t' << q->tag.value << endl;
    			q = q->right;
    		}
    		p = p->tag.link;
    	}
    
    }
    
    
    //三元组元素赋值  
    bool Value(TSMatrix &t, ElemType x, int i, int j)
    {
    	int k = 0, k1;
    	if (i >= t.rows || j >= t.cols)
    		return false;
    	while (k<t.nums && i>t.data[k].r)
    		k++;      //查找行  
    	while (k<t.nums && i == t.data[k].r && j>t.data[k].c)
    		k++;     //查找列  
    	if (t.data[k].r == i && t.data[k].c == j)   //存在这样的元素  
    		t.data[k].d = x;
    	else               //不存在这样的元素时插入一个元素  
    	{
    		for (k1 = t.nums - 1; k1 >= k; k1--)
    		{
    			t.data[k1 + 1].r = t.data[k1].r;
    			t.data[k1 + 1].c = t.data[k1].c;
    			t.data[k1 + 1].d = t.data[k1].d;
    		}
    		t.data[k].r = i;
    		t.data[k].c = j;
    		t.data[k].d = x;
    		t.nums++;
    	}
    	return true;
    }
    //将指定位置的元素值赋给变量 
    bool Assign(TSMatrix t, ElemType &x, int i, int j)
    {
    	int k = 0;
    	if (i >= t.rows || j >= t.cols)
    		return false;
    	while (k<t.nums && i>t.data[k].r)
    		k++;    //查找行  
    	while (k<t.nums && i == t.data[k].r && j>t.data[k].c)
    		k++;  //查找列  
    	if (t.data[k].r == i && t.data[k].c == j)
    		x = t.data[k].d;
    	else
    		x = 0;         //在三元组中没有找到表示是零元素  
    	return true;
    }
    
    
    //三元组下矩阵转置 
    void TranTat_1(TSMatrix t, TSMatrix &tb)
    {
    	int k, k1 = 0, v;		//k1记录tb中的元素个数
    	tb.rows = t.rows;
    	tb.cols = t.cols;
    	tb.nums = t.nums;
    	if (t.nums != 0)	//当存在非零元素时执行转置
    	{
    		for (v = 0; v < t.cols; v++)
    		{
    			for (k = 0; k < t.nums; k++)		//k用于扫描t.data的所有元素
    			{
    				if (t.data[k].c == v)		//找到一个列号为v的元素
    				{
    					tb.data[k].r = t.data[k].c;		//将行列交换后添加到tb中
    					tb.data[k].c = t.data[k].r;
    					tb.data[k].d = t.data[k].d;
    					k1++;
    				}
    			}
    		}
    	}
    
    }
    //十字链表下矩阵转置 
    void TranTat_2(ElemType a[M][N], ElemType c[M][N])
    {
    	int i,j;
    	for (i = 0; i < M; i++)
    	{
    		for (j = 0; j < N; j++)
    			c[j][i] = a[i][j];
    	}
    
    }
    
    
    //三元组下矩阵相加 
    bool  AddMat_1(TSMatrix a, TSMatrix b, TSMatrix &c)
    {
    	int i, j;
    	ElemType x, y, z;
    	if (a.rows != b.rows || a.cols != b.cols)
    		return false;            //行数或列数不等时不能相加
    	c.rows = a.rows;
    	c.cols = a.cols;       //c的行列数与a的相同  
    	c.nums = 0;
    	for (i = 0; i<M; i++)
    		for (j = 0; j<N; j++)
    		{
    			Assign(a, x, i, j);
    			Assign(b, y, i, j);
    			z = x + y;
    			if (z!=0)
    				Value(c, z, i, j);
    		}
    	return true;
    }
    //十字链表下矩阵相加 
    void AddMat_2(ElemType a[M][N], ElemType b[M][N], ElemType c[M][N])
    {
    	int i;
    	int j;
    	for (i = 0; i < M; i++)
    	{
    		for (j = 0; j < N; j++)
    		{
    			c[i][j] = a[i][j] + b[i][j];
    		}
    	}
    }
    
    
    //三元组下矩阵相乘 
    bool  MulMat_1(TSMatrix a, TSMatrix b, TSMatrix &c)
    {
    	int i, j;
    	ElemType x, y, z;
    	if (a.rows != b.rows || a.cols != b.cols)
    		return false;            //行数或列数不等时不能相乘
    	c.rows = a.rows;
    	c.cols = a.cols;       //c的行列数与a的相同  
    	c.nums = 0;
    	for (i = 0; i<M; i++)
    		for (j = 0; j<N; j++)
    		{
    			Assign(a, x, i, j);
    			Assign(b, y, i, j);
    			z = x * y;
    			if (z)
    				Value(c, z, i, j);
    		}
    	return true;
    }
    //十字链表下矩阵相乘 
    void  MulMat_2(ElemType a[M][N], ElemType b[M][N], ElemType c[M][N])
    {
    	int i;
    	int j;
    	int k;
    	int temp;
    	for (i = 0; i < M; i++)
    	{
    		for (j = 0; j < N; j++)
    		{
    			temp = 0;
    			for (k = 0; k < 4; k++)
    			{
    				temp = temp + a[i][k] * b[k][j];
    			}
    			c[i][j] = temp;
    		}
    
    	}
    }
    
    
    //主函数实现
    int main()
    {
    	TSMatrix ta, tb, tc;
    
    	MatNode *td,*tf;
    
    	int x,y,z;
    
    	ElemType a[M][N] = { 1, 0, 3, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1 };
    	ElemType b[M][N] = { 3, 0, 0, 0, 0, 4, 0, 0, 0, 0, 1, 0, 0, 0, 0, 2 };
    	ElemType c[M][N] = { 0 };
    
    	while (1)
    	{
    		cout << "提示:输入1----是三元组下的矩阵运算" << endl;
    		cout << "      输入2----是十字链表下的矩阵运算" << endl;
    		cout << "      输入3----退出" << endl;
    		cout << "请输入:";
    		cin >> x;
    		switch (x)
    		{
    		case 1:
    			cout << "提示:输入1----三元组下矩阵的转置运算" << endl;
    			cout << "      输入2----三元组下矩阵的相加运算" << endl;
    			cout << "      输入3----三元组下矩阵的相乘运算" << endl;
    			cout << "请输入:";
    			cin >> y;
    			switch (y)
    			{
    			case 1:
    				Create_1(ta, a);
    				cout << "输出三元组下矩阵a:" << endl;
    				DispMat_1(ta);
    				cout << "三元组下矩阵a转置:" << endl;
    				TranTat_1(ta, tc);
    				DispMat_1(tc);
    				break;
    			case 2:
    				Create_1(ta, a);
    				Create_1(tb, b);
    				cout << "三元组下矩阵a,b相加:" << endl;
    				AddMat_1(ta, tb, tc);
    				DispMat_1(tc);
    				break;
    			case 3:
    				Create_1(ta, a);
    				Create_1(tb, b);
    				cout << "三元组下矩阵a,b相乘:" << endl;
    				MulMat_1(ta, tb, tc);
    				DispMat_1(tc);
    				break;
    			}
    			break;
    		case 2:
    			cout << "提示:输入1----十字链表下矩阵的转置运算" << endl;
    			cout << "      输入2----十字链表下矩阵的相加运算" << endl;
    			cout << "      输入3----十字链表下矩阵的相乘运算" << endl;
    			cout << "请输入:";
    			cin >> z;
    			switch (z)
    			{
    			case 1:
    				Create_2(td,a);
    				cout << "输出十字链表下矩阵a:" << endl;
    				DispMat_2(td);
    				cout << "十字链表下矩阵a转置:" << endl;
    				TranTat_2(a, c);
    				Create_2(tf, c);
    				DispMat_2(tf);
    				break;
    			case 2:
    				cout << "十字链表下矩阵a,b相加:" << endl;
    				AddMat_2(a, b, c);
    				Create_2(tf, c);
    				DispMat_2(tf);
    				break;
    			case 3:
    				cout << "十字链表下矩阵a,b相乘:" << endl;
    				MulMat_2(a, b, c);
    				Create_2(tf, c);
    				DispMat_2(tf);
    				break;
    			}
    		case 3: break; 
    		}
    	}
    	cout << endl;
    	system("pause");
    }
    
    
    已采纳该答案
    打赏 评论

相关推荐 更多相似问题