티스토리 뷰
자료구조를 처음 배운지 꽤 오래지났다. 그래서 그런지 몇몇 개념들은 희미해졌고 많이 까먹기도 했다. 그 동안 복습을 제대로 안한 문제도 있을 것이라 생각한다. 그래서 2020 상반기의 가장 큰 목표 중 하나를 자료구조 과목을 제대로 복습하는 것이다.
나는 처음 자료구조를 C언어 쓰여진 책으로 배웠지만, 그 책을 바탕으로 이제는 C++로 구현해보고자 한다. C++에 대한 이해도가 높지 않아 실수가 많기때문에 지적이나 조언은 언제나 환영이다!
- 다항식 계산
#include <iostream>
using namespace std;
#define MAX_ARR 101
int MAX(int a, int b)
{
if (a > b) return a;
else return b;
}
class polynomial { //coef와 expon 저장 클래스
int coef=0;
int expon=0;
public:
polynomial() {};
void setter(int ex, int co) {
coef = co;
expon = ex;
} //외부에서 생성
int get_coef() {
return coef;
}
int get_expon() {
return expon;
}
};
class term {
polynomial polyArray[MAX_ARR]; //객체배열
int A_num; //첫번째 식의 항의 개수
int B_num; //두번째 식의 항의 개수
int C_num; //결과 식의 항의 개수
public:
term(int A_num, int B_num) { //생성자 첫번째 식의 항 개수 , 두번째 식의 항 개수
this->A_num = A_num;
this->B_num = B_num;
this->C_num = MAX(A_num, B_num); //결과 식의 항 개수
}
void poly_setter(int index, int e, int c) {
polyArray[index].setter(e,c);
} //외부에서 식 입력
int add(polynomial res[]) { //더하기 함수
int c_index = 0;
int a_pos = 0; //첫번째 식의 시작인덱스
int b_pos = A_num; //두번째 식의 시작 인덱스
int bnum = b_pos; //첫번째 식의 마지막 인덱스 +1
int cnum = A_num+B_num; //두번째 식의 마지막 인덱스 +1
while (a_pos < bnum && b_pos <cnum)
{
if (polyArray[a_pos].get_expon() > polyArray[b_pos].get_expon()) { //expon이 a가 더 클 때
res[c_index].setter(polyArray[a_pos].get_expon(), polyArray[a_pos].get_coef());
c_index++; a_pos++;
}
else if (polyArray[a_pos].get_expon() < polyArray[b_pos].get_expon()) { //expon이 b가 더 클때
res[c_index].setter(polyArray[b_pos].get_expon(), polyArray[b_pos].get_coef());
c_index++; b_pos++;
}
else{ //같을 때
res[c_index].setter(polyArray[a_pos].get_expon(), polyArray[a_pos].get_coef()+polyArray[b_pos].get_coef());
c_index++; a_pos++; b_pos++;
}
}
while (a_pos < bnum) { //남은 a 저장
res[c_index].setter(polyArray[a_pos].get_expon(), polyArray[a_pos].get_coef());
c_index++; a_pos++;
}
while (b_pos < cnum) {//남은b 저장
res[c_index].setter(polyArray[b_pos].get_expon(), polyArray[b_pos].get_coef());
c_index++; b_pos++;
}
return c_index;
}
int sub(polynomial res[]) { //빼기 함수
int c_index = 0;
int a_pos = 0; //첫번째 식의 시작인덱스
int b_pos = A_num; //두번째 식의 시작 인덱스
int bnum = b_pos; //첫번째 식의 마지막 인덱스 +1
int cnum = A_num + B_num; //두번째 식의 마지막 인덱스 +1
while (a_pos < bnum && b_pos < cnum)
{
if (polyArray[a_pos].get_expon() > polyArray[b_pos].get_expon()) { //expon이 a가 더 클 때
res[c_index].setter(polyArray[a_pos].get_expon(), polyArray[a_pos].get_coef());
c_index++; a_pos++;
}
else if (polyArray[a_pos].get_expon() < polyArray[b_pos].get_expon()) { //expon이 b가 더 클때
res[c_index].setter(polyArray[b_pos].get_expon(), polyArray[b_pos].get_coef());
c_index++; b_pos++;
}
else { //같을 때
int sub;
//마이너스값 방지
if (polyArray[a_pos].get_coef() > polyArray[b_pos].get_coef())
sub = polyArray[a_pos].get_coef() - polyArray[b_pos].get_coef();
else
sub = polyArray[b_pos].get_coef() - polyArray[a_pos].get_coef();
res[c_index].setter(polyArray[a_pos].get_expon(), sub);
c_index++; a_pos++; b_pos++;
}
}
while (a_pos < bnum) { //남은 a 저장
res[c_index].setter(polyArray[a_pos].get_expon(), polyArray[a_pos].get_coef());
c_index++; a_pos++;
}
while (b_pos < cnum) {//남은b 저장
res[c_index].setter(polyArray[b_pos].get_expon(), polyArray[b_pos].get_coef());
c_index++; b_pos++;
}
return c_index;
}
};
int main(void) {
term t1(3,3);
//index, expon , coef
t1.poly_setter(0, 3, 8);
t1.poly_setter(1, 1, 7);
t1.poly_setter(2, 0, 1);
t1.poly_setter(3, 3, 10);
t1.poly_setter(4, 2, 3);
t1.poly_setter(5, 0, 1);
polynomial sum_res[MAX_ARR];
int index = t1.add(sum_res); // 해당 배열 개수 반환
for (int i = 0; i < index; i++) {
cout << sum_res[i].get_coef() << "^ " << sum_res[i].get_expon() << endl;
}
cout << endl;
/*뺄셈*/
polynomial sub_res[MAX_ARR];
int index2 = t1.sub(sub_res); // 해당 배열 개수 반환
for (int i = 0; i < index2; i++) {
cout << sub_res[i].get_coef() << "^ " << sub_res[i].get_expon() << endl;
}
}1. 클래스와 객체배열을 이용한 다항식 계산
기존의 구조체 배열을 객체 배열로 변경, 해당 객체 배열을 담는 객체 따로 생성 .
그 클래스 내에서 연산함수 실행 및 출력.
여기서는 하나의 객체배열을 생성하고, 해당 객체배열에 식 1, 식2 을 넣고,
다른 객체를 하나 생성하여, 두 식의 연산 결과를 저장해주었다. 책에서 이런 방식으로 구현하여서 나도 이렇게했다.
예전에 C밖에 할줄 몰랐을 때는 무조건 구조체 배열과 함수들만 짜서 하기 쉬웠는데 클래스가 도입되니 좀 더 복잡해졌다.
이 방법 외에도 구조체 대신 클래스를 이용해 클래스 내부의 멤버 변수를 차수와 array로 하는 방식이 있다. 이는 두 객체를 연산하여 결과 객체에 넣는식이다. 하지만 이렇게 구현할 경우 array에 들어갈 메모리가 너무 쓸데없이 커지기 때문에 (모든 expon 의 경우를 배열에 입력해야함)
- 희소행렬
#include <iostream>
#define MAX_TERM 10
using namespace std;
int MAX(int a, int b) {
if (a > b) return a;
else return b;
}
class element { //희소행렬 내 행렬을 나타낼 배열의 행, 열, 값을 위한 클래스
public: //멤버변수를 public으로 설정하여 클래스 외부에서도 값 접근 및 변경 가능
int col;
int row;
int value;
public:
element() {};
};
class SparseMatrix { //희소행렬 클래스
//배열 (행,열,값 저장) , 행의 수, 열의 수, 항의 수, 인덱스 저장
public:
element data[MAX_TERM];
int rows;
int cols;
int terms;
int index = 0;
public:
SparseMatrix() {};
SparseMatrix(int rows, int cols, int terms) {
this->rows = rows;
this->cols = cols;
this->terms = terms;
}
void setMatrix(int row, int col, int val) { //배열값 set
data[index].col = col;
data[index].row = row;
data[index++].value = val;
}
void add(SparseMatrix b, SparseMatrix& res) { //희소행렬 덧셈
//b는 덧셈 할 다른 희소행렬, res는 결과값 저장할 희소행렬 객체
if (rows != b.rows || cols!=b.cols) { //각각 행, 열 크기가 같지 않으면 에러
cout << "희소행렬 크기 에러" << endl;
return;
}
//결과 객체에 기본값 저장
res.rows = rows;
res.cols = cols;
res.terms =0;
//각각 이 클래스 내 객체의 인덱스, b 객체의 인덱스 , res 객체의 인덱스
int res_a = 0;
int res_b = 0;
int res_c = 0;
while (res_a < terms && res_b < b.terms) {//항의 수 넘어가지 않도록
int index_a = data[res_a].row * cols + data[res_a].col; //현재 항의 위치 계산
// 현재 속해있는 행 * 전체 열의 수 + 현재 속해있는 열
int index_b = b.data[res_b].row * b.cols + b.data[res_b].col;
if (index_a < index_b) { //a가 b보다 앞에 있다면
res.data[res_c++] = data[res_a++]; //a 데이터를 결과 객체 value에 추가
}
else if (index_a == index_b) { //두개의 위치가 같다면
if ((data[res_a].value + b.data[res_b].value) != 0) { //0이 아닌 이상
res.data[res_c].row = data[res_a].row;
res.data[res_c].col = data[res_a].col; //서로 더한 값을 저장
res.data[res_c++].value = data[res_a++].value + b.data[res_b++].value;
}
else { //두개 더한 값이 0이라면 저장X
res_a++; res_b ++;
}
}
else { //b가 a보다 앞에 위치한다면
res.data[res_c++] = b.data[res_b++];
}
}
while (res_a < terms) { // a 남는요소
res.data[res_c++] = data[res_a++];
}
while (res_b < b.terms) { //b 남는요소
res.data[res_c++] = b.data[res_b++];
}
res.terms = res_c - 1;
}
void print_element() { //객체 배열 출력함수
for (int i = 0; i <= terms; i++) {
cout << "col: " << data[i].col << " row: " << data[i].row << " value: " << data[i].value << endl;
}
}
};
int main(void) {
SparseMatrix s1(3, 3, 2);
SparseMatrix s2(3, 3, 2);
s1.setMatrix(1, 1, 5);
s1.setMatrix(2, 2, 9);
s2.setMatrix(0, 0, 5);
s2.setMatrix(2, 2, 9);
SparseMatrix s3;
s1.add(s2, s3);
s3.print_element();
}2. 두 개의 class이용한 희소행렬
1)element 클래스에 행렬 값 하나의 정보 ( 행 (row) 열 (col) 값(value) )를 저장한다.
2) SparseMatrix 클래스에는 element 객체 배열을 생성하고, 희소행렬의 행의 개수, 열의 개수를 저장한다. 멤버변수 index는 element 객체 배열을 저장하기 위해서 추가했다.
3) SparseMatrix 클래스 내부에 덧셈 멤버 함수를 추가한다. 매개변수는 계산할 SparseMatrix 객체와, 계산 결과를 저장할 SparseMatrix 객체가 된다.
4)덧셈 방식은 다항식의 그것과 같은데, 여기서 추가된 점은 이 객체 배열은 희소행렬의 0을 모두 지우고 자료가 있는 부분만 남긴 것이기 때문에 기존의 2차원 배열이었던 희소행렬에서의 각각 위치에 순차적 번호를 계산해야한다. 그리고 이 순차적 번호가 작은 순서대로 결과값에 넣어야한다.
순차적 번호를 구하는 식은 다음과 같다
index_number = 현재 데이터의 row * (열의 개수 ) + 현재 데이터의 col 이다.
이는 C/C++에서 배열 요소들이 저장되는 순서와 같다. (2차원 배열은 우리가 보기 좋으라고 2차원으로 그려놨지만 실제로는 하나의 배열일 뿐인 것을 기억하자.)
2차원 배열이 원래 이렇게 생겼다고하면 왜 index를 위와 같은 방법으로 구해야하는지 이해가 갈 것이다.
결국 2차원 배열의 실제 메모리가 저장되는 모습이 1차원 배열과 같다면, 현재의 row의 위치는 row 위치 * col의 개수 일 것이고, 여기에다가 현재 col의 위치까지 더해야만 정확한 해당 데이터의 현 위치로 이동하기 때문이다.
- 전체 내용 정리
여기까지가 기초적으로 array를 활용한 대표적인 자료구조인 다항식과 희소행렬이었다.
'algorithm > 자료구조 복습' 카테고리의 다른 글
| [자료구조 복습6] 이진 탐색 트리 (Binary Search Tree) (0) | 2020.03.21 |
|---|---|
| [자료구조 복습5] 이중연결리스트로 덱(double- ended queue) 구현하기 (0) | 2020.03.20 |
| [자료구조 복습4] 원형 큐와 연결리스트 큐 구현하기 (0) | 2020.03.18 |
| [자료구조 복습3] 연결리스트로 stack 구현하기 (0) | 2020.03.18 |
| [자료구조 복습2] Array List와 Linked List (단순, 원형,이중) (0) | 2020.03.15 |