欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构学习--稀疏矩阵的三元组表示

程序员文章站 2022-07-12 09:53:27
...
// 稀疏矩阵的三元组表示

#include <stdio.h>


#define M 6
#define N 7
#define MaxSize M*N
typedef int ElemType;
struct TupNode
{

	int i, j;
	ElemType data;


};




class TSMatrix
{
private:
	int rows, cols, nums;
	struct TupNode data[MaxSize];
public:

	TSMatrix(ElemType A[M][N]);
	TSMatrix(const TSMatrix &other);
	TSMatrix()
	{
		nums = 0;
	}
	bool SetValue(int i, int j, ElemType x);
	bool GetValue(int i, int j, ElemType &x) const;
	void print() const;
	TSMatrix Trans() const; //转置

};


template <typename T>
void inline Swap(T &a, T &b)
{
	T tmp = a;
	a = b;
	b = tmp;
}



TSMatrix::TSMatrix(const TSMatrix &other)
{
	rows = other.rows;
	cols = other.cols;
	nums = other.nums;
	for (int i = 0; i<nums; i++)
	{
		data[i] = other.data[i];

	}


}

TSMatrix TSMatrix::Trans() const {  //求转置矩阵
	TSMatrix value;
	if (nums != 0){
		for (int k = 0; k<cols; k++)
		{
			for (int w = 0; w<nums; w++)
			{
				if (data[w].j == k)
				{
					value.data[value.nums].i = data[w].j;
					value.data[value.nums].j = data[w].i;
					value.data[value.nums].data = data[w].data;
					value.nums++;

				}


			}

		}
	}
	return value;
}



TSMatrix::TSMatrix(ElemType A[M][N]) //以二元数组构造稀疏矩阵
{
	rows = M;
	cols = N;
	nums = 0;
	for (int i = 0; i<M; i++)
	{
		for (int j = 0; j<N; j++)
		{
			if (A[i][j] != 0)
			{
				data[nums].i = i;
				data[nums].j = j;
				data[nums].data = A[i][j];
				nums++;

			}

		}

	}
}
void TSMatrix::print() const
//打印
{

	for (int i = 0; i<nums; i++)
	{
		printf("[  %d  |  %d  |  %d  ]\n", data[i].i, data[i].j, data[i].data);

	}


}

bool TSMatrix::SetValue(int i, int j, ElemType x) 
{
	int  k, w;
	if (i >= rows || j >= cols) return false;
	if (x == 0) //有可能出现设定值为0的情况(删除)
	{
		for (k = 0; data[k].i<i || data[k].j<j&&k < nums; k++);
		if (data[k].i == i&&data[k].j == j)
		{
			//删除第k个元素
			nums--;
			for (w = k; w<nums; w++)
			{
				Swap(data[w], data[w + 1]);
			}
			return true;



		}
		else  //本来就是0了
		{
			return true;
		}

	}
	else
	{

		for (k = 0; data[k].i<i || data[k].j<j&&k < nums; k++);  //空循环直接查找待插入的位置

		if (data[k].i == i&&data[k].j == j)
		{
			data[k].data = x;
			return true;
		}
		else
		{
			data[nums].data = x;
			data[nums].i = i;
			data[nums].j = j;
			nums++;
			for (w = k; w<nums; w++)
			{
				Swap(data[w], data[k]);
			}
			return true;

		}

	}


}




bool TSMatrix::GetValue(int i, int j, ElemType &x) const
{
	int k;

	if (i >= rows&&j >= cols) return false;
	for (k = 0; k<rows&&data[k].i<i || data[k].j<j; k++);
	if (data[k].i == i&&data[k].j == j)
	{
		x = data[k].data;


	}
	else {
		x = 0;

	}

	return true;

}

int main()
{

	ElemType A[M][N] =
	{
		{ 0, 0, 1, 0, 0, 0, 0 },
		{ 0, 2, 0, 0, 0, 0, 0 },
		{ 3, 0, 0, 0, 4, 0, 0 },
		{ 0, 0, 0, 5, 0, 0, 0 },
		{ 0, 0, 0, 0, 6, 0, 0 },
		{ 0, 0, 0, 0, 0, 7, 4 }
	};
	TSMatrix t = A;

	printf("三元组为:\n");
	t.print();

	printf("设定2,0,1;2,3,9之后三元组为:\n");
	t.SetValue(2, 0, 1);
	t.SetValue(2, 3, 9);
	t.print();
	printf("设定5,5,0;5,6,0之后三元组为:\n");
	t.SetValue(5, 5, 0);
	t.SetValue(5, 6, 0);
	t.print();

	ElemType x;
	if (t.GetValue(2, 4, x)) printf("[2,4]=%d\n", x);
	if (t.GetValue(1, 7, x)) printf("[1,7]=%d\n", x);
	printf("转置矩阵三元组为:\n");
	t.Trans().print();



	
	return 0;


}