[数据结构与算法]数据结构稀疏矩阵三元组的创建与插入

#include<iostream>
#define MaxSize 100
using namespace std;
typedef struct
{
	int row;//the row of the element(该元素所在的行)
	int column;//the column in  which the element is located(该元素所在的列)
	int element;
}TupNode;
class Triolet
{
private:
	TupNode tuple[MaxSize];
	int NR;//the number of rows in a triple(三元组所含的行数)
	int NC;//the number of columns in a triple(三元组所含的列数)
	int num;//number of triple element(三元组元素个数)
public:
	Triolet()
	{
		NC = 0;
		NR = 0;
		num = 0;
	}
	void CreatMat()
	{
		cout << "输入矩阵的行和列" << endl;
		cin >> NR >> NC;
		cout << "输入不为0的元素个数" << endl;
		cin >> num;
		for (int i = 1; i <= num; ++i)
		{
			cout << "输入第" << i << "个元素" << endl;
			cin >> tuple[i].element;
			//prevent position elements from crossing boundaries(防止输入元素越界)
			cout << "输入第" << i << "个元素所在的行" << endl;
			while (1)
			{
				cin >> tuple[i].row;
				if (tuple[i].row <= NR && tuple[i].row > 0)
					break;
				else
					cout << "该元素行位置输入越界，请重新输入" << endl;
			}
			cout << "输入第" << i << "个元素所在的列" << endl;
			while (1)
			{
				cin >> tuple[i].column;
				if (tuple[i].column <= NC && tuple[i].column > 0)
					break;
				else
					cout << "该元素列位置输入越界请重新输入" << endl;
			}
		}
		SortTriolet();

	}
	void SortTriolet()//sort triplesby roes and columns of the matrix(按矩阵的行与列，对三元组进行排序)
	{

		if (num == 1)return;
		//sort rows and columns from small to large(按行列从小到大排序)
		//shell sort(希尔排序)
		int d = num / 2;
		for (; d > 0; d = d / 2)
			for (int i = d + 1; i <= num; ++i)
			{
				tuple[0] = tuple[i];
				int j;
				for (j = i - d; j > 0 && tuple[j].row > tuple[0].row && tuple[j].column > tuple[0].row; tuple[j + d] = tuple[j], j = j - d);
				tuple[j + d] = tuple[0];

			}
		CheckDuplicate();//delete elements with duplicate rows and colums(删去行列重复的元素)
	}
	void CheckDuplicate()
	{
		//delete elements with duplicate rows and colums(删去行列重复的元素)
		int j = 0;
		for (int i = 1; i <= num; ++i)
		{
			if (tuple[i].row != tuple[i + 1].row && tuple[i].column != tuple[i + 1].column)
			{
				++j;
				tuple[j] = tuple[i];
				

			}
		}
		num = j;
	}

	void InsertElement()
	{
		
		cout << "输入插入的元素" << endl;
		cin >> tuple[0].element;
		cout << "输入该元素所在的行" << endl;
		while (1)
		{
			cin >> tuple[0].row;
			if (tuple[0].row > 0 && tuple[0].row <= NR)
				break;
			else
				cout << "行坐标输入有误，请重新输入" << endl;
		}
		cout << "输入该元素所在的列" << endl;
		while (1)
		{
			cin >> tuple[0].column;
			if (tuple[0].column > 0 && tuple[0].column <= NC)
				break;
			else
				cout << "列坐标输入有误，请重新输入" << endl;
		}

		for (int i = num; i > 0; --i)
		{
			if (tuple[i].row > tuple[0].row)
				tuple[i + 1] = tuple[i];
			else if (tuple[i].column > tuple[0].column)
				tuple[i + 1] = tuple[i];
			else if (tuple[i].row == tuple[0].row && tuple[i].column == tuple[0].column)
			{
				tuple[i].element = tuple[0].element;
				break;
			}
			else
			{
				tuple[i + 1] = tuple[0];
				++num;
				break;
			}
		}
		cout << "插入完成" << endl;
		OutputMatrix();
	}
	void OutputMatrix()
	{
		cout << "矩阵" << endl;
		int index = 1;
		for (int i = 1; i <=NR; ++i)
		{
			for (int j = 1; j <=NC; ++j)
			{
				if (i == tuple[index].row && j == tuple[index].column&&index<=num)
				{
					cout << tuple[index].element << '\t';
					++index;
				}
				else cout << "0" << '\t';

			}
			cout << endl;
			
		}
	}
	void OutputTriolet()
	{
		cout << "三元组" << endl;
		for (int i = 1; i <= num; ++i)
		{
			cout << tuple[i].element << " 在第 " << tuple[i].row << " 行,第 " <<tuple[i].column<< "列" << endl;
		}
	}
};
int main()
{
	Triolet triolet;
	triolet.CreatMat();
	triolet.OutputMatrix();
	triolet.OutputTriolet();
	triolet.InsertElement();
}