NOJ-SparseMatrix

概述

  这是Noj上关于稀疏矩阵操作的几道题，包括稀疏矩阵的转置，加法和乘法。其中加法实现包括了稀疏矩阵的数组存储方式以及十字链表存储方式。

NOJ-29

题目

• 输出稀疏矩阵的转置矩阵。（行列均不大于20）
• Input：第一行输入两个正整数n和m,分别表示矩阵的行数和列数,然后输入矩阵三元组，
  最后输入（0 0 0）表示结束输入。
• Ouput：转置后的矩阵。

思路

  题目的思路较为明确。在进行完矩阵输入元素的储存之后，首先简单将元素的行和列进行交换，先不考虑顺序是否正确，这部操作由于我使用的是二维矩阵的存储方式，第一列存储元素的行，第二列存储元素的列，其实只需要进行简单的概念变换即可，即让第一列存储元素的列，第二列存储元素的行，这样就完成了矩阵元素的行号和列号的交换。
  然后需要执行的是按行列变换后的行号进行排序，运用简单的冒泡排序实现，其中调用的元素交换模块完成冒泡排序原子操作；在按行号进行排序之后执行的是按列号的排序，先判断时候行号相同再进行排序，同样使用的是冒泡排序，调用的元素交换模块。在完成两次排序之后，矩阵的转置操作完成，之后输出即可。

代码

  代码实现如下：

// No29.cpp
#include <iostream>

using namespace std;

int getArr(int arr[][3])
{
	int len = 0;
	cin >> arr[0][0];
	cin >> arr[0][1];
	cin >> arr[0][2];
	while (!(arr[len][0] == 0 && arr[len][1] == 0
		&& arr[len][2] == 0))
	{
		cin >> arr[++len][0];
		cin >> arr[len][1];
		cin >> arr[len][2];
	}

	return len;
}

void changeTwo(int arr[][3], int no1, int no2)
{
	int temp1 = 0;
	int temp2 = 0;
	int temp3 = 0;
	temp1 = arr[no1][0];
	temp2 = arr[no1][1];
	temp3 = arr[no1][2];
	arr[no1][0] = arr[no2][0];
	arr[no1][1] = arr[no2][1];
	arr[no1][2] = arr[no2][2];
	arr[no2][0] = temp1;
	arr[no2][1] = temp2;
	arr[no2][2] = temp3;

	cout << no1 << " , " << no2 << endl;
}

void sortArr_1(int arr[][3],int len)
{
	int sortCol = 1;

	for (int i = 0; i < len - 1; i++)
		for (int j = i + 1; j<len;j++)
			if (arr[i][sortCol] > arr[j][sortCol])
				changeTwo(arr,i,j);

}

void sortArr_2(int arr[][3], int len)
{
	int sortCol = 0;
	int sortCol2 = 1;

	for (int i = 0; i < len - 1; i++)
		for (int j = 0; j < len; j++)
			if (arr[i][sortCol] == arr[j][sortCol] &&
				arr[i][sortCol2] > arr[j][sortCol2])
				changeTwo(arr, i, j);
			else if (arr[i][sortCol] != arr[j][sortCol])
			    break;
}

void printArr(int arr[][3], int len)
{
	for (int i = 0; i < len; i++)
		cout << arr[i][1] << " " << arr[i][0] << " " << arr[i][2] << endl;
}

int main()
{
	int row = 0;
	int col = 0;
	int lenArr = 0;
	int oriArr[400][3];

	cin >> row;
	cin >> col;
	lenArr = getArr(oriArr);

	sortArr_1(oriArr, lenArr);
	sortArr_2(oriArr, lenArr);

	printArr(oriArr, lenArr);
	return 0;
}

NOJ-30

题目

• 输入两个稀疏矩阵，输出它们相加的结果。
• Input:第一行输入四个正整数，分别是两个矩阵的行m、列n、第一个矩阵的非零元素的个数t1和第二个矩阵的非零元素的个数t2。接下来的t1+t2行是三元组，分别是第一个矩阵的数据和第二个矩阵的数据。三元组的第一个元素表示行号，第二个元素表示列号，第三个元素是该项的值。
• Ouput:输出相加后的矩阵三元组。

思路

  这道题的关键在于根据两个矩阵中游标所在的两个元素的行号和列号，判断要执行的操作。先为两个矩阵设置两个游标，游标初始位置为两个矩阵的首个元素，并以此根据动作序号向后遍历。其中，当游标所在两个元素的行号和列号相同的时候，对两个元素进行相加并加入结果矩阵中；当游标所在的两个元素的第一个元素的行号小于第二个元素的行号或者第一个元素行号与第二个元素行号相同，但是第一个元素的列号小于第二个元素的列号的时候，将第一个元素加入结果矩阵中，其余情况下将第二个元素加入结果矩阵中。
  判断当其中一个矩阵的元素遍历完成之后，将第二个元素的剩余元素直接加入结果矩阵中。
  需要注意的是，在执行相加操作的时候需要有一步判断，若相加的和为0，则不加入结果矩阵中。

代码

  代码实现如下：

// No30.cpp
#include <iostream>

using namespace std;

void getMat(int mat[][3], int len)
{
	for (int i = 0; i < len; i++)
		for (int j = 0; j < 3; j++)
			cin >> mat[i][j];
}


int whichPush(int mat1[][3], int mat2[][3], int no1, int no2)
{
	if (mat1[no1][0] == mat2[no2][0] && mat1[no1][1] == mat2[no2][1])
		return 0;
	else if (mat1[no1][0] < mat2[no2][0])
		return 1;
	else if (mat1[no1][0] == mat2[no2][0] && mat1[no1][1] < mat2[no2][1])
		return 1;
	else
		return 2;
}

int oneAdd(int mat1[][3], int mat2[][3], int no1, int no2)
{
	return (mat1[no1][2] + mat2[no2][2]);
}

void pushToMat(int mat[][3], int row, int col, int num, int countNum)
{
	mat[countNum][0] = row;
	mat[countNum][1] = col;
	mat[countNum][2] = num;
}

int addMat(int mat1[][3], int mat2[][3], int mat3[][3], int len1, int len2)
{
	int cursor1 = 0;
	int cursor2 = 0;
	int judge = -1;
	int tempAdd = 0;
	int lenAftAdd = 0;

	while (cursor1 < len1 && cursor2 < len2)
	{
		judge = whichPush(mat1, mat2, cursor1, cursor2);
		if (judge == 0)
		{
			tempAdd = oneAdd(mat1, mat2, cursor1, cursor2);
			// !!!! Attention when sum == 0,the sum cannot be pushed into the Mat3 
			if (tempAdd != 0)
			{
				pushToMat(mat3, mat1[cursor1][0], mat1[cursor1][1], tempAdd, lenAftAdd++);
				cursor1++;
				cursor2++;
			}
			else
			{
				cursor1++;
				cursor2++;
			}

		}
		else if (judge == 1)
		{
			pushToMat(mat3, mat1[cursor1][0], mat1[cursor1][1], mat1[cursor1][2], lenAftAdd++);
			cursor1++;
		}
		else if (judge == 2)
		{
			pushToMat(mat3, mat2[cursor2][0], mat2[cursor2][1], mat2[cursor2][2], lenAftAdd++);
			cursor2++;
		}
	}
	if (cursor1 == len1 && cursor2 < len2)
	{
		for (int i = cursor2; i < len2; i++)
		{
			pushToMat(mat3, mat2[cursor2][0], mat2[cursor2][1], mat2[cursor2][2], lenAftAdd++);
			cursor2++;
		}
	}
	else if (cursor2 == len2 && cursor1 < len1)
	{
		for (int i = cursor1; i < len1; i++)
		{
			pushToMat(mat3, mat1[cursor1][0], mat1[cursor1][1], mat1[cursor1][2], lenAftAdd++);
			cursor1++;
		}
	}

	return lenAftAdd;

}

void printMat(int mat[][3], int len)
{
	for (int i = 0; i < len-1; i++)
	{
		for (int j = 0; j < 2; j++)
			cout << mat[i][j] << " ";
		cout << mat[i][2] << endl;
	}
	for (int j = 0; j < 2; j++)
		cout << mat[len-1][j] << " ";
	cout << mat[len-1][2];
}

int main()
{
	int countA = 0;
	int countB = 0;
	int countC = 0;
	int row = 0;
	int col = 0;
	int matA[100][3];
	int matB[100][3];
	int matC[200][3];
    
    cin >> row;
    cin >> col;
	cin >> countA;
	cin >> countB;
	getMat(matA, countA);
	getMat(matB, countB);

	countC = addMat(matA, matB, matC, countA, countB);
	printMat(matC, countC);
	return 0;
}

NOJ-31

题目

• 输入两个稀疏矩阵，输出它们相加的结果,用十字链表实现
• Input:第一行输入四个正整数，分别是两个矩阵的行m、列n、第一个矩阵的非零元素的个数t1和第二个矩阵的非零元素的个数t2。接下来的t1+t2行是三元组，分别是第一个矩阵的数据和第二个矩阵的数据。三元组的第一个元素表示行号，第二个元素表示列号，第三个元素是该项的值。
• Ouput：输出相加后的矩阵三元组。

思路

  这道题的难点在于十字链表存储方式的实现。在创建十字链表的时候，应根据首行输入的行号和列号分别建立相应长度的行头结点链表和列头结点链表，为其malloc相应的地址空间，然后根据输入元素的行号和列号找到相应的结点位置，加入十字链表中，完成输入矩阵的初始化。
  在进行加法操作的时候，以其中一个矩阵为基础，遍历另外一个矩阵，若第二个矩阵的遍历到的元素的行号和列号在第一个元素中，则把第一个元素中的相应结点值加上第二个元素的值；若不存在，则插入第二个元素结点。
  需要同样注意的是，若两个元素和的值为0，则应该将此结点删除。

代码

  代码实现如下：

// No31.cpp
#include <iostream>  
#include <cstdio>  
#include <stdlib.h>  

using namespace std;

typedef struct listNode
{
	int row, col;
	int value;
	struct listNode *rightNode, *downNode;
}*listLink;

typedef struct
{
	listLink*rowHead, *colHead;
	int numRow, numCol;
	int numItem;
}crossList;

void createList(crossList &operaList, int numR, int numC, int numIt)
{
	operaList.numRow = numR ;
	operaList.numCol = numC ;
	operaList.numItem = numIt;
	operaList.rowHead = (listLink*)malloc((operaList.numRow + 1)*sizeof(listLink));
	operaList.colHead = (listLink*)malloc((operaList.numCol + 1)*sizeof(listLink));
	
	int loop = 0;
	for (loop = 1; loop <= operaList.numRow; loop++)
		operaList.rowHead[loop] = NULL;
	for (loop = 1; loop <= operaList.numCol; loop++)
		operaList.colHead[loop] = NULL;
	for (loop = 1; loop <= operaList.numItem; loop++)
	{
		int Row = 0;
		int Col = 0;
		int Item = 0;
		listLink loopNode;
		listLink tempNode = (listNode*)malloc(sizeof(listNode));

		cin >> Row >> Col >> Item;
        tempNode->row = Row;
		tempNode->col = Col;
		tempNode->value = Item;
        if (operaList.rowHead[Row] == NULL || operaList.rowHead[Row]->col > Col)
		{
			tempNode->rightNode = operaList.rowHead[Row];
			operaList.rowHead[Row] = tempNode;
		}
		else
		{
			for (loopNode = operaList.rowHead[Row]; (loopNode->rightNode) && (loopNode->rightNode->col < Col); loopNode = loopNode->rightNode)
				;
			tempNode->rightNode = loopNode->rightNode;
			loopNode->rightNode = tempNode;
		}
		tempNode->downNode = NULL;
		if (operaList.colHead[Col] == NULL || operaList.colHead[Col]->row > Row)
		{
			tempNode->downNode = operaList.colHead[Col];
			operaList.colHead[Col] = tempNode;
		}
		else
		{
			for (loopNode = operaList.colHead[Col]; (loopNode->downNode) && (loopNode->downNode->row < Row); loopNode = loopNode->downNode)
				;
			tempNode->downNode = loopNode->downNode;
			loopNode->downNode = tempNode;
		}
		tempNode->rightNode = NULL;
	}
}

void DestroyList(crossList &operaList)
{
	listLink tempList;
	for (int k = 1; k <= operaList.numRow; k++)
	{
		tempList = operaList.rowHead[k];
		while (tempList)
		{
			operaList.rowHead[k] = tempList->rightNode;
			free(tempList);
			tempList = operaList.rowHead[k];
		}
	}
	operaList.numRow = 0;
	operaList.numCol = 0;
	operaList.numItem = 0;
}

void InsertNode(crossList &operaList, listLink &tempNode)
{
	int i = tempNode->row, j = tempNode->col;
	int numDeleted = 0, numAdd = 0;
	if (operaList.rowHead[i] == NULL)
	{
		operaList.rowHead[i] = tempNode;
		operaList.numItem++;
	}
	else
	{
		listLink q = operaList.rowHead[i];
		listLink pre = q;
		while (q && (q->col < tempNode->col))
		{
			pre = q;
			q = q->rightNode;
		}
		if (q != NULL && q->col == tempNode->col)
		{
			q->value += tempNode->value;
			if (q->value == 0)
			{
				if (pre == q)
					operaList.rowHead[i] = q->rightNode;
				else
					pre->rightNode = q->rightNode;
				operaList.numItem--;
				numDeleted = 1;
			}
			else
				numAdd = 1;
		}
		if (!numDeleted && !numAdd)
		{
			if (pre == q)
			{
				operaList.rowHead[i] = tempNode;
				tempNode->rightNode = q;
			}
			else
			{
				pre->rightNode = tempNode;
				tempNode->rightNode = q;
			}
			operaList.numItem++;
		}
	}

	if (operaList.colHead[j] == NULL)
		operaList.colHead[j] = tempNode;
	else
	{
		listLink q = operaList.colHead[j];
		listLink pre = q;
		while (q && (q->row < tempNode->row))
		{
			pre = q;
			q = q->downNode;
		}
		if (numDeleted)
		{
			if (q != NULL)
			{
				if (pre == q)
					operaList.colHead[j] = q->downNode;
				else
					pre->downNode = q->downNode;
				free(q);
				free(tempNode);
				return;
			}
		}
		if (!numAdd)
		{
			if (pre == q)
			{
				operaList.colHead[j] = tempNode;
				tempNode->downNode = q;
			}
			else
			{
				pre->downNode = tempNode;
				tempNode->downNode = q;
			}
		}
	}

}

void addList(crossList &M, crossList &N)
{
	listLink Node1, Node2;
	Node1 = (listNode*)malloc(sizeof(listNode));
	for (int k = 1; k <= N.numRow; k++)
	{
		Node1 = N.rowHead[k];
		while (Node1)
		{
			Node2 = (listNode*)malloc(sizeof(listNode));
			Node2->downNode = Node1->downNode;
			Node2->rightNode = Node1->rightNode;
			Node2->value = Node1->value;
			Node2->row = Node1->row;
			Node2->col = Node1->col;
			InsertNode(M, Node2);
			Node1 = Node1->rightNode;
		}
	}
}

void printList(crossList &operaList)
{
	for (int k = 1; k <= operaList.numRow; k++)
	{
		listLink p = operaList.rowHead[k];
		for (int t = 1; t <= operaList.numCol; t++)
		{
			if (p && (t == p->col))
			{
				printf("%d %d %d\n", p->row, p->col, p->value);
				p = p->rightNode;
			}
		}
	}
}
int main()
{

	int numRow = 0;
	int numCol = 0;
	int numItem1 = 0;
	int numItem2 = 0;

	cin >> numRow >> numCol >> numItem1 >> numItem2;
	crossList list1, list2;
	createList(list1, numRow, numCol, numItem1);
	createList(list2, numRow, numCol, numItem2);
	addList(list1, list2);
	printList(list1);
	return 0;
}

NOJ-32

题目

• 计算两个稀疏矩阵的乘法
• Input:首先输入第一个矩阵的行数和列数，再输入该矩阵的三元组形式，以0 0 0结束
  然后输入第二个矩阵的行数和列数，再输入该矩阵的三元组形式，以0 0 0结束
• Ouput:输出相加后的矩阵三元组。

思路

  思路参考lou_ye的博客。我是用不同的储存方式，即二维数组实现的。整体思路与原博客相似。思路简介如下：
  本题要求实现的是矩阵的乘法，解决的整体思路是设置一个暂存矩阵，用于存储结果矩阵中每行的元素，然后再将每行的元素加入结果矩阵中。具体实现的时候，引入两个变量，分别记录了第二个矩阵中第n行非零元素的个数和第n行中首个非零元素的位置。在进行乘法之前，先记录第二个矩阵中上述的两个变量数组，在计算的时候，根据已经计算好的两个数据进行结果矩阵中暂存数组的计算，然后每次讲暂存数组存入结果矩阵中即可。

代码

  代码实现如下：

// No32.cpp
#include <iostream>

using namespace std;

int getMat(int mat[][3])
{
	int len = 0;
	do
	{
		cin >> mat[len][0];
		cin >> mat[len][1];
		cin >> mat[len++][2];
	} while (!(mat[len-1][0] == 0 && mat[len-1][1] == 0
		     && mat[len-1][2] == 0));

	return len;
}


int mulMat(int mat1[][3], int row1, int col1,int len1,
	        int mat2[][3], int row2, int col2,int len2,
	        int mat3[][3])
{
	int notZeroMat2PerRow[1000];
	int indexNotZeroMat2PerRow[1000];
	int len3 = 0;
	int loopA = 0;
	int loopB = 0;
	int loopC = 0;
	int temp[1000];
	int firstNotZeroMat1 = 0;
	int lowIndexMat2 = 0;
	
	for (int i = 0; i <= row1; i++)
		notZeroMat2PerRow[i] = 0;
	for (int i = 0; i < len2; i++)
	{
		notZeroMat2PerRow[mat2[i][0]]++;
	}

	indexNotZeroMat2PerRow[1] = 0;
	for (int i = 2; i <= row2; i++)
	{
		indexNotZeroMat2PerRow[i] = indexNotZeroMat2PerRow[i - 1] + notZeroMat2PerRow[i - 1];
	}


	for (int i = 1; i <= row1; i++)
	{
		for (int j = 1; j <= col2; j++)
			temp[j] = 0;

		while (i == mat1[loopA][0])
		{
			firstNotZeroMat1 = mat1[loopA][1];
			if (firstNotZeroMat1 < row2)
				lowIndexMat2 = indexNotZeroMat2PerRow[firstNotZeroMat1+1];
			else
				lowIndexMat2 = len2;
			for (int q = indexNotZeroMat2PerRow[firstNotZeroMat1]; q < lowIndexMat2; q++)
			{
				loopB = mat2[q][1];
				temp[loopB] += mat1[loopA][2] * mat2[q][2];
			}
			loopA++;
		}
		for (int k = 1; k <= col2;k++)
			if (temp[k] != 0)
			{
				mat3[len3][0] = i;
				mat3[len3][1] = k;
				mat3[len3][2] = temp[k];
				len3++;
			}
	}

	return len3;

}

void printMat(int mat[][3], int len)
{
	for (int i = 0; i < len; i++)
		cout <<mat[i][0] << " " << mat[i][1] << " " << mat[i][2] << endl;
}

int main()
{
	int rowA = 0;
	int colA = 0;
	int rowB = 0;
	int colB = 0;
	int lenA = 0;
	int lenB = 0;
	int lenC = 0;
	int matA[1000][3];
	int matB[1000][3];
	int matC[1000][3];

	cin >> rowA >> colA;
	lenA = getMat(matA);
	cin >> rowB >> colB;
	lenB = getMat(matB);

	lenC = mulMat(matA, rowA, colA, lenA,
		matB, rowB, colB, lenB,
		matC);

	printMat(matC, lenC);
	return 0;
}

小结

  小结说句和博文无关的话，今天遇到了件不开心的事，但是对我来说也不一定是件坏事，一定是我前一段时间有点浮躁了吧，所以它好心蹦出来提醒我一下。
  放下浮躁的态度，毛糙的心；即使前途再是未知，即使未来再是无法把控，踏踏实实做好眼前的事情，才是我近期应该有的态度，祝看到这段话的你和我在接下来的时光中好运。