稀疏矩阵的基础

目录

一、采用矩阵的正常存储方式，实现矩阵转置的经典算法

二、利用三元组表实现稀疏矩阵的转置

方法一：为了保证转置后的矩阵的三元组表B也是以“行序为主序”进行存放，则需要对行，列互换后的三元组表B按B的行下标（即A的列下标）大小重新排序

方法二：依次按三元组A的次序进行转置，转置后直接访到三元组B的正确位置上。这种转置算法称为快速转置算法。

三、稀疏矩阵的链式存储结构：十字链表

（一）在进行行链表插入的时候3中情况

情况1

情况2

情况3 

（二）在进行列链表插入的时候3种情况

情况1

情况2 

情况3 

---

一、采用矩阵的正常存储方式，实现矩阵转置的经典算法

#pragma once
#include
#include
#include
#include
using namespace std;
typedef int ElemType;
int main()
{
	//int v1[4][3]={{1,2,3},{4,5,6},{7,8,9},{10,11,12}};
	//int v2[3][4];
	vectorint>> v1{ {1,2,3},{4,5,6},{7,8,9},{10,11,12} };
	vectorint>> v2{{0,0,0,0},{0,0,0,0},{0,0,0,0}};
	int i = 0, j = 0;
	for (i = 0; i < 4; i++)
	{
		for (j = 0; j < 3; j++)
		{
			v2[j][i] = v1[i][j];
		}
	}
	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < 4; j++)
		{
			cout << v2[i][j] << " ";
		}
		cout << endl;
	}
	return 0;
 
}

• 时间复杂度为：O（A.m×A.n） 

二、利用三元组表实现稀疏矩阵的转置

• 三元组线性表中一个元素是用来描述一个非零元素的信息.
• 稀疏矩阵的顺序存储就是用一段连续的存储单元依次存储其对应的三元组线性表，并称这种存储结构的三元组线性表为三元组顺序表。 

方法一：为了保证转置后的矩阵的三元组表B也是以“行序为主序”进行存放，则需要对行，列互换后的三元组表B按B的行下标（即A的列下标）大小重新排序

  

#pragma once
#include
#include
#include
#include
using namespace std;
typedef int ElemType;
#define MAXSIZE 100//非零元素的个数最多为1000
typedef struct
{
	int row, col;//非零元素的行下标和列下标
	ElemType e;//该非零元素的值
}Triple;
typedef struct
{
	Triple data[MAXSIZE+1];//非零元素的三元组表，data[0]未用
	int m, n, len;//矩阵的行数，列数和非零元素的个数
}TSMatrix;
void Init(TSMatrix &S);//初始化
bool Push(TSMatrix &S);//录入数据
void Transpose(TSMatrix A, TSMatrix &B);//转置矩阵
void print(TSMatrix S);//打印三元组

#include"Array.h"
void Init(TSMatrix& S)
{
	S.m = 0;
	S.n = 0;
	S.len = 0;
}
bool Push(TSMatrix &S)
{
	vector < vector<int>> v{ {0,0,0,0,0,1},{0,0,2,3,0,0},{0,0,0,0,6,0} };
	int k = 1;
	S.m = v.size();
	S.n = v[0].size();
	for (int i = 0; i < v.size(); i++)
	{
		for (int j = 0; j < v[0].size(); j++)
		{
			if (v[i][j] != 0)
			{
				S.data[k].row = i + 1;
				S.data[k].col = j + 1;
				S.data[k].e = v[i][j];
				k++;
				S.len++;
			}
		}
	}
	return true;
}
void Transpose(TSMatrix A, TSMatrix &B)
{
	int i = 0, j = 0;
	B.m = A.n;
	B.n = A.m;
	B.len = A.len;
	if (B.len > 0)
	{
		int k = 1;//位置计数器用于指向当前转置后元素应放入三元组表B中的位置
		for (i = 1; i <= A.n; i++)//A数组中非零元素所在列最高可能为A.n，当寻找位于第1列的非零元素时
			//需要遍历A.len（表示非零元素个数）次，再寻找位于第2列的非零元素时，也要遍历A.len次
		{
			for (j = 1; j<= A.len; j++)//遍历A数组列
			{
				if (A.data[j].col == i)
				{
					B.data[k].row = A.data[j].col;
					B.data[k].col = A.data[j].row;
					B.data[k].e = A.data[j].e;
					k++;
				}
			}
		}
	}
}
 
void print(TSMatrix S)
{
	int i = 1, j = 1;
	for (i = 1; i <= S.len; i++)
	{
		cout << S.data[i].row << " " << S.data[i].col << " " << S.data[i].e << endl;
	}
	cout << endl;
}

#include"Array.h"
int main()
{
	TSMatrix S;
	Init(S);
	Push(S);
	print(S);
	cout << S.m << " " << S.n<
	TSMatrix B;
	Transpose(S,B);
	print(B);
	return 0;
}

• 算法的时间耗费主要是在双重循环中，其时间复杂度为O（A.n×A.len）（其中A.n表示原始矩阵的列数，A.len表示原始矩阵中非零元素的个数），最坏的情况是矩阵A全是非零元素即A.len=A.m×A.n，其时间复杂度为O（A.m×A.n^2）。

方法二：依次按三元组A的次序进行转置，转置后直接访到三元组B的正确位置上。这种转置算法称为快速转置算法。

• 为了能将待转置三元组表A中元素一次定位到三元组表B的正确位置上，需要预先计算一下数据：

1. 待转置矩阵source每一列中非零元素的个数（即转置后矩阵dest每一行中非零元素的个数）。
2. 待转置矩阵source每一列中第一个非零元素在三元组表B中的正确位置（即转置后矩阵dest每一行中第一个非零元素在三元组B中国的正确位置） 

• 实现：设两个数组

1. num[col]：表示矩阵M中第col列中非零元素个数
2. pos[col]：指示M中第col列第一个非零元素在三元表B中的位置：

pos[1]=1;
pos[col]=pos[col-1]+num[col-1];(2<=col<=原始矩阵的列数)

 

#pragma once
#include
#include
#include
#include
using namespace std;
#define MAXSIZE 100//非零元素的个数最多为100
typedef int ElemType;
typedef struct
{
	int row, col;//非零元素的行下标和列下标
	ElemType e;//该非零元素的值
}Triple;
typedef struct
{
	Triple data[MAXSIZE+1];//非零元素的三元组表，data[0]未用
	int m, n, len;//矩阵的行数，列数和非零元素的个数
}TSMatrix;
void Init(TSMatrix& S);//初始化
bool Push(TSMatrix& S);//给TSMatrix对象的三元组中录入数据
bool TastTransposeTSMatrix(TSMatrix A,TSMatrix &B);//转置矩阵
void print(TSMatrix S);//打印三元组
void print2(TSMatrix S);//打印稀疏矩阵

#include"Array.h"
void Init(TSMatrix& S)
{
	S.m = 0;
	S.n = 0;
	S.len = 0;
}
bool Push(TSMatrix& S)//给TSMatrix对象的三元组中录入数据
{
	vector < vector<int>> v{ {0,0,0,0,0,1},{0,0,2,3,0,0},{0,0,0,0,6,0} };
	int k = 1;
	S.m = v.size();
	S.n = v[0].size();
	for (int i = 0; i < v.size(); i++)
	{
		for (int j = 0; j < v[0].size(); j++)
		{
			if (v[i][j] != 0)
			{
				S.data[k].row = i + 1;
				S.data[k].col = j + 1;
				S.data[k].e = v[i][j];
				k++;
				S.len++;
			}
		}
	}
	return true;
}
bool TastTransposeTSMatrix(TSMatrix A, TSMatrix& B)//转置矩阵
{
	int num[MAXSIZE];//表示原始矩阵A中第col列中非零元素个数
	int pos[MAXSIZE];//指示原始矩阵A中第col列第一个非零元素在转置矩阵B中的三元组中的位置
	B.m = A.n;
	B.n = A.m;
	B.len = A.len;
	int col = 0;
	if (A.len!=0)
	{
		for (int col = 1; col <= A.n; col++)//先将原始矩阵A中每一列的非零元素个数都初始化为0
		{
			num[col] = 0;
		}
		for (int j = 1; j <= A.len; j++)//对矩阵A的三元组的列从头开始向下扫描
		{
			num[A.data[j].col]++;//比如A.data[1].col对应矩阵A的三元组表col中的第一个数据2，
			//2表示第2列，即A.data[1].col=2，说明原始矩阵A中第2列出现了一个非零元素，则num[A.data[j].col]++
		}
 
		pos[1] = 1;
		for (int col = 2; col <= A.n; col++)//求原始矩阵A中的第col列中第一个非零元素在转置矩阵B的三元组中的位置
		{
			pos[col] = pos[col - 1] + num[col - 1];
		}
 
		for (int p = 1; p <= A.len; p++)
		{
			col = A.data[p].col;
			int k = pos[col];
			B.data[k].row = A.data[p].col;
			B.data[k].col = A.data[p].row;
			B.data[k].e = A.data[p].e;
			pos[col]++;//当原始矩阵A的三元组col中的A.data[p].col=A.data[p+1].col的时候，pos[col]后移动
			//一位
		}
	}
	return true;
 
}
 
void print(TSMatrix S)
{
	int i = 1, j = 1;
	for (i = 1; i <= S.len; i++)
	{
		cout << S.data[i].row << " " << S.data[i].col << " " << S.data[i].e << endl;
	}
	cout << endl;
}
 
void print2(TSMatrix S)//打印稀疏矩阵
{
	int a[30][30];
	for (int i = 0; i <  S.m; i++)
	{
		for (int j = 0; j <  S.n; j++)
		{
			a[i][j] = 0;
		}
	}
	for (int i = 1; i <= S.len; i++)
	{
		int m = S.data[i].row;
		int n = S.data[i].col;
		a[m - 1][n - 1] = S.data[i].e;
	}
	for (int i = 0; i < S.m; i++)
	{
		for (int j = 0; j < S.n; j++)
		{
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
 
}

#include"Array.h"
int main()
{
	TSMatrix S;
	Init(S);
	Push(S);
	cout << "原始矩阵：" << endl;
	print2(S);
	cout << "原始矩阵的三元组：" << endl;
	print(S);
 
	cout << endl;
	TSMatrix B;
	TastTransposeTSMatrix(S, B);
	cout << "转置后的矩阵：" << endl;
	print2(B);
	cout << "转置后的矩阵的三元组：" << endl;
	print(B);
	return 0;
}

• 注意：为什么pos[col]++ 

三、稀疏矩阵的链式存储结构：十字链表

• 用两个一维的指针数组分别存放各行链表的头指针和各列链表的头指针，从而得到了矩阵的十字链表存储结构 

（一）在进行行链表插入的时候3中情况

情况1

情况2

情况3 

（二）在进行列链表插入的时候3种情况

情况1

情况2 

情况3 

#pragma once
#include
#include
#include
#include
using namespace std;
typedef int ElemType;
typedef struct OLNode
{
	int row, col;//非零元素的行下标，列下标
	ElemType value;
	struct OLNode* right, * down;//非零元素所在行表，列表的后继链域
}OLNode,*OLink;
 
typedef struct
{
	OLink* row_head, * col_head;//行、列链表的头指针向量
	int m, n, len;//稀疏矩阵的行数，列数，非零元素个数
}CrossList;
bool CreatCrossList(CrossList* M);
void Print(CrossList* M);//打印

 
#include"Array.h"
bool CreatCrossList(CrossList* M)
{
	int m, n, t;
	cout << "请依次输入矩阵的行数，列数和非零元素个数：" << endl;
	cin >> m >> n >> t;//输入M的行数，列数和非零元素个数
	M->m = m;
	M->n = n;
	M->len = t;
	M->row_head = (OLink*)malloc((m + 1) * sizeof(OLink));
	if (M->row_head == NULL)//开辟空间失败直接退出
	{
		exit(-1);
	}
	M->col_head = (OLink*)malloc((n + 1) * sizeof(OLink));
	if (M->col_head == NULL)
	{
		exit(-1);
	}
	
	for (int i = 1; i <= M->m; i++) //初始化行头指针，为空链表
	{
		M->row_head[i] = NULL;
	}
	for (int j = 1; j <= M->n; j++) //初始化行头指针，为空链表
	{
		M->col_head[j] = NULL;
	}
	cout << "请按次序输入非零元的行，列，元素值：" << endl;
	for (int k = 0; k < t; k++)//非零元素的行，列，值
	{
		int i, j;
		ElemType e;
		cin >> i >> j >> e;
		OLNode* p = (OLNode*)malloc(sizeof(OLNode));
		if (p == NULL)//开辟空间失败直接退出
		{
			exit(-1);
		}
		p->row = i;
		p->col = j;
		p->value = e;
		//先进行行链表插入
		if (M->row_head[i] == NULL || p->col < M->row_head[i]->col)
			//第i行头结点为空，或者新建结点的列号小于第i行第1个结点的列号
		{
			p->right = M->row_head[i];
			M->row_head[i] = p;
		}
      //第2种将上面的if分开写
		//if (M->row_head[i] == NULL )
		//	//第i行头结点为空
		//{
		//	M->row_head[i] = p;
		//	p->right = NULL;
		//}
		//else if (p->col < M->row_head[i]->col)//新建结点的列号小于第i行第1个结点的列号
		//{
		//	p->right = M->row_head[i];
		//	M->row_head[i] = p;
		//}
		else
		{
			OLNode* q = M->row_head[i];
			for (q; q->right != NULL && q->right->col < j; q = q->right)
			{
				p->right = q->right;
				q->right = p;
			}
		}
 
		//再进行列链表插入
		if (M->col_head[j] == NULL || p->row < M->col_head[j] -> row)
			//第j列头结点为空，或者新建结点的行号小于第j列第1个结点的行号
		{
			p->down = M->col_head[j];
			M->col_head[j] = p;
		}
        //第2种将上面的if分开写
		//if (M->col_head[j] == NULL )
		//	//第j列头结点为空 
		//{
		//	M->col_head[j] = p;
		//	p->down = NULL;
		//}
		//else if (p->row < M->col_head[j]->row)//新建结点的行号小于第j列第1个结点的行号
		//{
		//	p->down = M->col_head[j];
		//	M->col_head[j] = p;
		//}
		else
		{
			OLNode* q2 = M->col_head[j];
			for (q2; q2->down != NULL && q2->down->row < i; q2 = q2->down)
			{
				p->down = q2->down;
				q2->down = p;
			}
		}
	}
	return true;
}
 
 
void Print(CrossList* M)//打印
{
	OLNode* p;
	for (int i = 1; i <= M->m; i++)//从矩阵的第一行开始扫描到最后一行
	{
		p = M->row_head[i];
		for (int j = 1; j <= M->n; j++)//从矩阵第一列开始扫描到最后一列
		{
			if (p == NULL || p->col != j)//已经扫描到该行表尾或当前结点的列值不等于当前列值
			{
				cout << "0" << " ";
			}
			else
			{
				cout << p->value << " ";
				p = p->right;
			}
		}
		cout << endl;
	}
}

#include"Array.h"
int main()
{
	CrossList S;
	CreatCrossList(&S);
	cout << "以矩阵形式输出：" << endl;
	Print(&S);
	return 0;
}