三元组

发表于 | 分类于

首先先痛斥下vc6.0，并记住以后遇到模板类的，一定要全部重建。

一、介绍

如果在矩阵中，多数的元素为0，称此矩阵为稀疏矩阵（sparse matrix）。
概念很清楚，矩阵中，0元素比较多的矩阵是稀疏矩阵，
这样的矩阵可以用三元组以及十字链表存贮，这里介绍三元组的用法。

二、三元组介绍

含有在矩阵中的行列数，以及元素值的结构体。定义如下：

1
2
3
4
5
6
7
8
9
10
template<class T>
struct Triple
{
	int r,c;
	T elem;
	bool operator <(const Triple<T>& rhs) const // 升序排序时必须写的函数  
    {  
        return r < rhs.r;  
    }  
};

重载运算符是为了后面调用vector的排序，省的自己费心的按顺序插入，这样全部插好了，直接排序就好了。

三、稀疏矩阵

这是一个类，类里面包含行数，列数，还有非零元的个数，同时非零元的具体值，即三元组，用的是向量存储，动态扩容，随机访问复杂度为o(1),很强大的工具。

3.1构造函数的撰写

构造函数，我准备写两种形式，

  • 第一种无参，那就要求从键盘键入值，
  • 第二种有参，那数据来源是文件

3.1.1无参

先存储数据的个数，如行数，列数，非零元个数，然后循环读取数据，存入，并压入向量，最后对其排序。
最好能对重复元素位置做检测，这边没有实现这个功能，以后再补吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
template<class T>
SparseMatrix<T>::SparseMatrix()
{
	do {
		cout<<"请分别输入矩阵的行数、列数和非零元个数：\n";
		cout<<"行数：";
		cin>>this->row;
		cout<<"列数：";
		cin>>this->col;
		cout<<"非零元的个数：";
		cin>>this->num;
		if(this->row < 0 || this->col < 0 || this->num < 0 || this->num > this->row * this->col) cout<<"有错。。";
	} while(this->row < 0 || this->col < 0 || this->num < 0 || this->num > this->row * this->col);

	//保证了数据的正确性。。
	if (this->num==0) return ;//每个元素都是空的。
	for(int k =0;k<this->num;k++)
	{
		Triple<T> tmp;
		do {
			cout<<"请输入第"<<k+1<<"个非零元的行和列：\n";
			cout<<"行：";
			cin>>tmp.r;
			cout<<"列：";
			cin>>tmp.c;          
			cout<<"元素:";
			cin>>tmp.elem;
			if(tmp.r <= 0 || tmp.r > this->row || tmp.c <= 0 || tmp.c > this->col)	 cout<<"有错。。重输";
		} while(tmp.r <= 0 || tmp.r > this->row || tmp.c <= 0 || tmp.c > this->col);//检测输入是否合法 
		triList.push_back(tmp);
	}
	sort(triList.begin(), triList.end());
/*	for (int i=0;i<triList.size();i++)
	{
		cout<<triList[i].r<<"   ";
	}
*///	std::sort(triList,0);	！！！重要的，一定要排序或者想办法顺序插入。
}

3.1.2有参构造函数

这边的数据，准备来源于文件，所以先介绍文件的格式

5
5 5
2 3 1
3 2 2
2 4 3
5 5 4
1 2 5

第一行为非零元个数
第二行是矩阵规模
后面是三元组的内容。
所以设计load函数也很方便。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int num;
int r;
int c;
Triple<int> * Load(char *fname)
{
	ifstream fin(fname);
	int n;
	fin>>n;
	num=n;
	fin>>r;
	fin>>c;
	Triple<int> *list=new Triple<int> [n];
	int i=0;
	while(!fin.eof())
	{
		fin>>list[i].r;
		fin>>list[i].c;
		fin>>list[i++].elem;
	}
	fin.close();
	return list;
}

全局变量num，r，c便于传递有参函数的参数，Load函数返回的是结构体数组，我们利用这个来构造矩阵。同样也需要判重，这边不写。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template<class T>
SparseMatrix<T>::SparseMatrix(int rs,int cs,int n,Triple<T> *list)
{
	this->col=cs;
	this->row=rs;
	this->num=n;
	for (int i=0;i<n;i++)
	{
		Triple<T> tmp;
		tmp.r=list[i].r;
		tmp.c=list[i].c;  
		tmp.elem=list[i].elem;
		triList.push_back(tmp);
	}
	sort(triList.begin(), triList.end());
}

这样，调用的方式为
SparseMatrix<int> sm(r,c,num,Load("data.txt"));
但是很奇怪的是，
如果声明为：
SparseMatrix(Triple<T> *list,int rs,int cs,int n);
这样在调用时错的，这个问题我前面也遇到过，尝试解释过，但不知道对不对。

3.2输出矩阵

目的很明确，把矩阵输出。
没什么好办法，一个个的遍历，因为triList里面的元素是按照行来排序的，所以依次遍历，对比该位置是否存在值，存在输出，不存在输出0.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template<class T>
void SparseMatrix<T>::print()
{
	int i, j, k;//中间变量
	//输出
	for(i = 1, k = 0; i <= this->row; i++)
	{
		for(j = 1; j <=this->col; j++)
		{
			int r=this->triList[k].r;
			int c=this->triList[k].c;
			if(i ==  r &&j == c) 
			{
				cout<<this->triList[k].elem<<"\t";
				k++;
			}
			else cout<<0<<"\t";
		}
		cout<<endl;
	}
}

3.3转置

这块运用的是快速转置。这边遇到的问题是，调试的时候，多次遇到错，检测不出来，到最后发现，是因为没有全部重建，导致部分语句并没有被重编译，给debug带来巨大的麻烦，切记。
代码本身还是很好理解的，书上也给了详细的说明：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/*
输出
*/
template<class T>
void SparseMatrix<T>::trans(SparseMatrix<T>& B)
{
	int co=col;
	B.row = this->col;
	B.col = this->row;
	B.num = this->num;
	B.triList.resize(num);
	if(num == 0)
		return;
	int* cnum = new int [100];
	int* cpot = new int [100];


	for(int i=0; i<co; i++)
		cnum[i] = 0;
	for(int t=0; t<num;t++)
	{
	//	cout<<t<<endl;
	//	cout<<triList[t].c ;
		++cnum[triList[t].c];	
	}
	cpot[1] = 0;

	for(i=2; i<=co; i++)
		cpot[i] = cpot[i-1]+cnum[i-1];
	for(int p=0; p<num; p++)
	{
		int n = triList[p].c;
		int q = cpot[n];
		B.triList[q].r = triList[p].c;
		B.triList[q].c = triList[p].r;
		B.triList[q].elem = triList[p].elem;
		++cpot[n];
	}
	delete[] cnum;
	delete[] cpot;
}

四、测试

最后，做一个小小的测试，由于无参构造函数也需要输入值，如果不真的需要值，可以输入0 0 0；

1
2
3
4
5
6
7
8
9
10
int main()
{
	SparseMatrix<int> sm(r,c,num,Load("data.txt"));
	sm.print();
	SparseMatrix<int> sm1;
	sm.trans(sm1);
		cout<<"转置后"<<endl;
	sm1.print();
	return 0;
}

测试截图：
此处输入图片的描述

2015年4月22日晚