/*
희소행렬 SparseMatrix
*/
#include <iostream>
using namespace std;
class Matrix;
struct Triple
{
int row;
int col;
int val;
};
class MatrixNode
{
private:
MatrixNode *right; //행
MatrixNode *down; //열
bool isHead;
union
{
MatrixNode *next;
Triple triple; //row, col, val
};
public:
MatrixNode() //디폴트 생성자
{
}
MatrixNode(bool b, Triple *t)
{
isHead = b;
if (isHead)
{
right = down = next = this;
}
else
{
triple = *t;
}
}
friend class Matrix;
friend istream &operator>>(istream &is, Matrix &m);
friend ostream &operator<<(ostream &os, Matrix &m);
};
MatrixNode *av = 0; //~Matrix를 위한
class Matrix
{
private:
MatrixNode *headNode;
public:
Matrix() //디폴트 생성자
{
}
~Matrix()
{
if(!headNode)
return;
MatrixNode *x = headNode->right;
headNode->right = av;
av = headNode;
while (x != headNode)
{
MatrixNode *y = x->right;
x->right = av;
av = y;
x = x->next;
}
}
int max(int a, int b)
{
if (a > b)
return a;
else
return b;
}
friend istream &operator>>(istream &is, Matrix &m);
friend ostream &operator<<(ostream &os, Matrix &m);
};
istream &operator>>(istream &is, Matrix &matrix)
{
Triple s;
int count = 1;
cout << "행, 열, 0이 아닌 항 개수" << endl;
is >> s.row >> s.col >> s.val;
int p = matrix.max(s.row, s.col);
matrix.headNode = new MatrixNode(false, &s);
if (p == 0) //행이나 열 개수 중 하나라도 0이라면
{
matrix.headNode->right = matrix.headNode;
return is;
}
MatrixNode **head = new MatrixNode*[p]; //max(col, row)만큼 배열 생성
for (int i = 0; i < p; i++)
head[i] = new MatrixNode(true, 0);
int currentRow = 0;
MatrixNode *last = head[0]; //해당 열 중 마지막 노드
for (int i = 0; i < s.val; i++) //triple 입력
{
Triple t;
cout << count++ << "번째 행, 열, 원소 입력";
is >> t.row >> t.col >> t.val;
if (t.row > currentRow) //해당 열 끝
{
last->right = head[currentRow];
currentRow = t.row;
last = head[currentRow];
}
last = last->right = new MatrixNode(false, &t); //새로운 노드 행에 추가
head[t.col]->next = head[t.col]->next->down = last; //새로운 노드 열에 추가
}
last->right = head[currentRow]; //마지막 행 종료
for (int i = 0; i < s.col; i++)
head[i]->next->down = head[i]; //마지막 열 종료
//headNode와 head 연결
for (int i = 0; i < p - 1; i++)
head[i]->next = head[i + 1]; //head끼리 연결
head[p - 1]->next = matrix.headNode;
matrix.headNode->right = head[0];
delete[]head;
return is;
}
ostream &operator<<(ostream &os, Matrix &m)
{
MatrixNode *headNode = m.headNode->right;
while (headNode != m.headNode) //원형 리스트이므로 m.headNode에 도달하면 끝
{
for (MatrixNode *cur = headNode->right; cur != headNode; cur = cur->right)
os << "(" << cur->triple.row << ", " << cur->triple.col << ", " << cur->triple.val << ")" << endl;
headNode = headNode->next;
}
return os;
}
int main(void)
{
Matrix m;
cin >> m;
cout << endl << "희소행렬 출력" << endl;
cout << "(행, 열, 값)" << endl;
cout << m;
return 0;
}
[참고] Fundamentals of Data Structures in C++(Horowitz, Sahni, Mehta) 원서
*영어로 적혀있는 문제를 제가 의역한 것이기 때문에 오역이 있을 수 있습니다. 양해 부탁드립니다