[Exercises 1]
/*
How much time does it take to locate an arbitrary element A[i][j] in the representation of this section and to change its value
이번 섹션에서 나타낸 이차행렬의 임의 원소인 A[i][j]를 찾고 값을 변경하는데 걸리는 시간은?
*/
일반적인 방법을 쓸 경우 : O(rows*cols)
FastTranspose를 쓸 경우 : O(cols + terms)
[Exercises 2]
/*
Analyze carefully the computing time and storage requirements of function FastTranspose
FastTranspose 함수의 작동시간과 저장 크기 조건을 분석해라
O(terms+cols)
*/
#include <iostream>
using namespace std;
class SparseMatrix;
class MatrixTerm
{
friend class SparseMatrix;
private:
int row, col, value;
};
class SparseMatrix
{
private:
int rows, cols, terms, capacity;
MatrixTerm *smArray;
public:
SparseMatrix(int MaxRow, int MaxCol, int term)
{
rows = MaxRow;
cols = MaxCol;
terms = term;
capacity = 0;
}
SparseMatrix FastTranspose()
{
//Return the transpose of *This in O(terms+cols) time
SparseMatrix b(cols, rows, terms);
if (terms > 0)
{
//nonzero matrix, 0이 아닌 행렬
int *rowSize = new int[cols];
int *rowStart = new int[cols];
//compute rowSize[i]=number of terms in row i of b
//RowSize[i]=b의 행 i에 들어갈 항의 수를 계산
fill(rowSize, rowSize + cols, 0); //초기화
for (int i = 0; i < terms; i++)
rowSize[smArray[i].col]++;
//rowStart[i]=starting position of b
//rowStart[i]는 b의 행 i의 시작 지점
rowStart[0] = 0;
for (int i = 1; i < cols; i++)
rowStart[i] = rowStart[i - 1] + rowSize[i - 1];
for (int i = 0; i < terms; i++)
{
//copy from *this to b
//b로 복사
int j = rowStart[smArray[i].col];
b.smArray[j].row = smArray[i].col;
b.smArray[j].col = smArray[i].row;
b.smArray[j].value = smArray[i].value;
rowStart[smArray[i].col]++;
}
delete[]rowSize;
delete[]rowStart;
}
return b;
}
};
[Exercises 3]
/*
Write C++ functions to input and output a sparse matrix.
sparse matrix를 입출력하는 C++ 함수를 작성한다.
These should be implemented by overloading the >> and << operators
이를 위해 >> 와 << 연산자가 오버로딩되어야한다.
You should design the input and output formats.
입출력 형식은 본인이 직접 디자인한다.
However, the internal representation should be a one dimensional array of nonzero terms as used in this section.
하지만, 이번 섹션에서 표현했듯이 희소행렬은 일차원 배열로 표현되어야한다.
*/
#include <iostream>
using namespace std;
class SparseMatrix;
class MatrixTerm
{
friend class SparseMatrix;
friend ostream &operator<<(ostream &os, const SparseMatrix S); //출력
friend istream &operator>>(istream &is, SparseMatrix S); //입력
private:
int row, col, value;
};
class SparseMatrix
{
private:
int rows, cols, terms, capacity;
MatrixTerm *smArray;
public:
SparseMatrix(int MaxRow = 1, int MaxCol = 1, int term = 0)
{
rows = MaxRow;
cols = MaxCol;
terms = term;
if (term > 0)
capacity = term;
else
capacity = 1;
smArray = new MatrixTerm[capacity];
}
SparseMatrix FastTranspose()
{
//Return the transpose of *This in O(terms+cols) time
SparseMatrix b(cols, rows, terms);
if (terms > 0)
{
//nonzero matrix, 0이 아닌 행렬
int *rowSize = new int[cols];
int *rowStart = new int[cols];
//compute rowSize[i]=number of terms in row i of b
//RowSize[i]=b의 행 i에 들어갈 항의 수를 계산
fill(rowSize, rowSize + cols, 0); //초기화
for (int i = 0; i < terms; i++)
rowSize[smArray[i].col]++;
//rowStart[i]=starting position of b
//rowStart[i]는 b의 행 i의 시작 지점
rowStart[0] = 0;
for (int i = 1; i < cols; i++)
rowStart[i] = rowStart[i - 1] + rowSize[i - 1];
for (int i = 0; i < terms; i++)
{
//copy from *this to b
//b로 복사
int j = rowStart[smArray[i].col];
b.smArray[j].row = smArray[i].col;
b.smArray[j].col = smArray[i].row;
b.smArray[j].value = smArray[i].value;
rowStart[smArray[i].col]++;
}
delete[]rowSize;
delete[]rowStart;
}
return b;
}
friend ostream &operator<<(ostream &os, const SparseMatrix S); //출력
friend istream &operator>>(istream &is, SparseMatrix S); //입력
};
ostream &operator<<(ostream &os, const SparseMatrix S)
{
os << "열: " << S.rows << " 행: " << S.cols << endl;
os << "0이 아닌 요소의 수: " << S.terms << endl;
for (int i = 0; i < S.terms; i++)
{
os << "(" << S.smArray[i].row << ", " << S.smArray[i].col << ", " << S.smArray[i].value << ")" << endl;
}
return os;
}
istream &operator>>(istream &is, SparseMatrix S)
{
cout << "열, 행, 그리고 0이 아닌 요소의 수 입력: ";
cin >> S.rows >> S.cols >> S.terms;
if (S.terms > S.capacity)
{
cout << "범위를 초과했습니다";
exit(1);
}
for (int i = 0; i < S.terms; i++)
{
cout << i + 1 << "-> 열, 행, 그리고 값 입력: " << endl;
is >> S.smArray[i].row >> S.smArray[i].col >> S.smArray[i].value;
}
return is;
}
[Exercises 5]
/*
Develop a corrctness proof for function Multiply(Program 2.14)
희소행렬 곱셈 함수의 정확성을 증명해라?
질문의 의도를 모르기 때문에 우선 곱셈 함수만 작성하겠습니다
*/
#include <iostream>
using namespace std;
class SparseMatrix;
class MatrixTerm
{
friend class SparseMatrix;
friend ostream &operator<<(ostream &os, const SparseMatrix S); //출력
friend istream &operator>>(istream &is, SparseMatrix S); //입력
private:
int row, col, value;
};
class SparseMatrix
{
private:
int rows, cols, terms, capacity;
MatrixTerm *smArray;
public:
SparseMatrix(int MaxRow=1, int MaxCol=1, int term=0)
{
rows = MaxRow;
cols = MaxCol;
terms = term;
if (term > 0)
capacity = term;
else
capacity = 1;
smArray = new MatrixTerm[capacity];
}
SparseMatrix FastTranspose()
{
//Return the transpose of *This in O(terms+cols) time
SparseMatrix b(cols, rows, terms);
if (terms > 0)
{
//nonzero matrix, 0이 아닌 행렬
int *rowSize = new int[cols];
int *rowStart = new int[cols];
//compute rowSize[i]=number of terms in row i of b
//RowSize[i]=b의 행 i에 들어갈 항의 수를 계산
fill(rowSize, rowSize + cols, 0); //초기화
for (int i = 0; i < terms; i++)
rowSize[smArray[i].col]++;
//rowStart[i]=starting position of b
//rowStart[i]는 b의 행 i의 시작 지점
rowStart[0] = 0;
for (int i = 1; i < cols; i++)
rowStart[i] = rowStart[i - 1] + rowSize[i - 1];
for (int i = 0; i < terms; i++)
{
//copy from *this to b
//b로 복사
int j = rowStart[smArray[i].col];
b.smArray[j].row = smArray[i].col;
b.smArray[j].col = smArray[i].row;
b.smArray[j].value = smArray[i].value;
rowStart[smArray[i].col]++;
}
delete[]rowSize;
delete[]rowStart;
}
return b;
}
void ChangeSize1D(const int newSize)
{
MatrixTerm *temp = new MatrixTerm[newSize];
copy(smArray, smArray + terms, temp);
delete[] smArray;
smArray = temp;
}
void StoreSum(const int v, const int r, const int c)
{
if (v != 0)
{
if (terms == capacity)
ChangeSize1D(2 * capacity);
smArray[terms].row = r;
smArray[terms].col = c;
smArray[terms++].value = v;
}
}
SparseMatrix Multiply(SparseMatrix b)
{
if (cols != b.rows)
throw "Incompatible matrices";
SparseMatrix bXpose = b.FastTranspose();
SparseMatrix d(rows, b.cols, 0);
int currRowIndex = 0, currRowBegin = 0, currRowA = smArray[0].row;
//set boundary conditions
if (terms == capacity)
ChangeSize1D(terms + 1);
bXpose.ChangeSize1D(bXpose.terms + 1);
smArray[terms].row = rows;
bXpose.smArray[b.terms].row = b.cols;
bXpose.smArray[b.terms].col = -1;
int sum = 0;
while (currRowIndex < terms)
{
int currColB = bXpose.smArray[0].row;
int currColIndex = 0;
while (currColIndex <= b.terms)
{
if (smArray[currRowIndex].row != currRowA)
{
d.StoreSum(sum, currRowA, currColB);
sum = 0;
currRowIndex = currRowBegin;
while (bXpose.smArray[currColIndex].row == currColB)
currColIndex++;
currColB = bXpose.smArray[currColIndex].row;
}
else if (bXpose.smArray[currColIndex].row != currColB)
{
d.StoreSum(sum, currRowA, currColB);
sum = 0;
currRowIndex = currRowBegin;
currColB = bXpose.smArray[currColIndex].row;
}
else
{
if (smArray[currRowIndex].col < bXpose.smArray[currColIndex].col)
currRowIndex++;
else if (smArray[currRowIndex].col == bXpose.smArray[currColIndex].col)
{
sum += smArray[currRowIndex].value*bXpose.smArray[currColIndex].value;
currRowIndex++;
currColIndex++;
}
else
currColIndex++;
}
}
while (smArray[currRowIndex].row == currRowA)
currRowIndex++;
currRowBegin = currRowIndex;
currRowA = smArray[currRowIndex].row;
}
return d;
}
friend ostream &operator<<(ostream &os, const SparseMatrix S); //출력
friend istream &operator>>(istream &is, SparseMatrix S); //입력
};
ostream &operator<<(ostream &os, const SparseMatrix S)
{
os << "열: " << S.rows << " 행: " << S.cols << endl;
os << "0이 아닌 요소의 수: " << S.terms << endl;
for (int i = 0; i < S.terms; i++)
{
os << "(" << S.smArray[i].row << ", " << S.smArray[i].col << ", " << S.smArray[i].value << ")" << endl;
}
return os;
}
istream &operator>>(istream &is, SparseMatrix S)
{
for (int i = 0; i < S.terms; i++)
{
cout << i + 1 << "-> 열, 행, 그리고 값 입력: " << endl;
is >> S.smArray[i].row >> S.smArray[i].col >> S.smArray[i].value;
}
return is;
}
int main(void)
{
SparseMatrix s(3, 3, 3), t(3, 3, 3);
cout << "s 행렬 입력"<<endl;
cin >> s;
cout << "s 희소행렬" << endl << s << endl;
cout << "t 행렬 입력" << endl;
cin >> t;
cout << "t 희소행렬" << endl << t << endl;
SparseMatrix mul = s.Multiply(t);
cout << "s*t 희소행렬" << endl << mul << endl;
return 0;
}
[참고] Fundamentals of Data Structures in C++(Horowitz, Sahni, Mehta) 원서,
*영어로 적혀있는 문제를 제가 의역한 것이기 때문에 오역이 있을 수 있습니다. 양해 부탁드립니다.
*4, 6, 7번 문제는 생략하였습니다.
*벌써부터 어려워진 듯한 느낌입니다... 문제를 푸는데 몇시간씩이나 걸리다니...
'C++ > Fundamentals of Data Structures in C++(Horowitz)' 카테고리의 다른 글
| C++ Fundamentals of Data Structures(C++ 자료구조론) 2.6 연습문제 (0) | 2017.07.31 |
|---|---|
| C++ Fundamentals of Data Structures(C++ 자료구조론) 2.5 연습문제 (0) | 2017.07.31 |
| C++ Fundamentals of Data Structures(C++ 자료구조론) 2.3 연습문제 7~9 (0) | 2017.07.28 |
| C++ Fundamentals of Data Structures(C++ 자료구조론) 2.3 연습문제 1~6 (0) | 2017.07.28 |
| C++ Fundamentals of Data Structures(C++ 자료구조론) 2.2 연습문제 (0) | 2017.07.25 |