[자료구조] C++로 쉽게 풀어쓴 자료구조 : 2장, 배열과 클래스 응용

내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다.

2장. 배열과 클래스의 응용

이번 단원에서는 배열과 class에 대한 간단한 복습시간이였다. 간단하게 연습문제 푼 부분만 코드를 적고 넘어가겠다.

 

프로그래밍 프로젝트

● 다항식 클래스의 C++ 구현

 

(1) 두 다항식 a와 b의 뺄셈을 구하는 멤버 함수 sub를 구현하라

 

(2) 두 닿항식의 곱셈을 구하는 멤버 함수 mult를 구현하라

 

(3) 다항식의 연산결과 최고차항의 계수가 0으로 변할 수 있다. 현재 다항식의 계수를 분석해 최고차항의 계수가 0이 아닌 값이 나오도록 다항식의 속성 값들을 변경하는 멤버 함수 trim을 구현하라

 

(4) 다항식의 출력 함수 display를 수정하여 계수가 0인 항은 출력되지 않도록 변경하라. 또한 계수가 1인 경우는 게수 1을 출력하지 않도록 변경하라

 

우선 직접 작성한 class 다이어그램을 확인해 보자.

교제와 다르게 구현한점들

- 우선 조건에서 sub, mult 함수를 구현하라고 하였는데 나는 함수를 구현하기보단 연산자 오버로딩을 하고 싶어서 오버로딩하는 방식을       취하였다. 좀더 능동적으로 C++을 사용하고 싶었다.

 

- display() 함수 또한 함수호출을 하는것이 아니라 << 연산자 오버로딩을 통하여 출력되도록 하였다.

 

- 교제에서는 int형에 대해서만 다루지만 나는 template화 시켰다.

 

코드는 다음과 같다.

#include <iostream>
#include <stdio.h>
#include <string>
#define MAX_DEGREE 80
using namespace std;

template <typename T> // 템플릿화
class Polynomial {
	int _degree;
	T _coef[MAX_DEGREE];
public:
	Polynomial() : _degree(0) {}
	bool isZero();
	void trim();
	void read();
	Polynomial& display(string str = " Poly = ");
	Polynomial& negate();
	Polynomial operator + (Polynomial& p) const; // 더하기 연산자 오버로딩
	Polynomial operator - (Polynomial& p) const; // 빼기 연산자 오버로딩
	Polynomial& operator * (Polynomial& p); // 곱하기 연산자 오버로딩
	friend ostream& operator << (ostream& out,  Polynomial& p) // 출력 연산자 오버로딩
	{
		p.display();
		return out;
	}
};

template <typename T>
Polynomial<T> Polynomial<T>::operator + (Polynomial& p) const // 더하기 연산자 오버로딩
{
	Polynomial temp;
	if (_degree > p._degree) {
		temp = *this;
		for (int i = 0; i <= p._degree; i++)
			temp._coef[i + (temp._degree - p._degree)] += p._coef[i];
		return temp;
	}
	else {
		temp = p;
		for (int i = 0; i <= _degree; i++)
			temp._coef[i + (temp._degree - _degree)] += _coef[i];
		return temp;
	}
}

template <typename T>
Polynomial<T> Polynomial<T>::operator - (Polynomial& p) const // 빼기 연산자 오버로딩
{
	Polynomial temp = p.negate(); // p의 부호를 -로 변경하여 더하기로 해결
	return *this + temp;
}

template <typename T>
Polynomial<T>& Polynomial<T>::operator * (Polynomial& p) // 곱하기 연산자 오버로딩
{
	Polynomial temp;
	temp._degree = (*this)._degree + p._degree; // 초기화 
	for (int i = 0; i < MAX_DEGREE; i++)
		temp._coef[i] = 0;

	for (int i = 0; i <= (*this)._degree; i++)
	{
		for (int j = 0; j <= p._degree; j++)
			temp._coef[i + j] += (*this)._coef[i] * p._coef[j];
	}
	return temp;
}

template <typename T>
void Polynomial<T>::read() {
	printf("다항식의 최고 차수를 입력하시오: ");
	cin >> _degree;
	printf("각 항의 계수를 입력하시오 (총 %d개): ", _degree + 1);
	for (int i = 0; i <= _degree; i++)
		cin >> _coef[i];
}

template <typename T>
Polynomial<T>& Polynomial<T>::display(string str) {
	cout << str;
	for (int i = 0; i < _degree; i++) {
		//if (_coef[i] == 0)
		//	cout << "";
		//else
			cout << _coef[i] << "x^" << _degree - i << " + ";
	}
	cout << _coef[_degree] << endl;
	return *this;
}

template <typename T>
bool Polynomial<T>::isZero() {
	return _degree == 0;
}

template <typename T>
Polynomial<T>& Polynomial<T>::negate() {
	Polynomial temp;
	temp._degree = (*this)._degree;
	for (int i = 0; i <= _degree; i++)
		temp._coef[i] = -_coef[i];
	return temp;
}

template <typename T>
void Polynomial<T>::trim() {
	int count = 0;

	while (0 != _coef[count]) //최고차항이 0이 아닐때까지
		count++;
	if (count) //최고차항이 0이 아니라면 실행 X
	{
		int temp = _degree; //기존꺼 저장
		_degree -= count; //최고차항 감소

		for (int i = 0; i <= temp - count; i++) //자리를 옮긴다
			_coef[i] = _coef[i + count];
	}
}

int main()
{
	Polynomial<int> a, b, add, sub, mul; // instantiation 필수
	a.read();
	b.read();
	add = a + b;
	sub = a - b;
	mul = a * b;
	cout << "a : " << a << endl;
	cout << "b : " << b << endl;
	cout << "add : " << add << endl;
	cout << "sub : " << sub << endl;
	cout << "mul : " << mul << endl;
               
	return 0;
}

 

결과를 확인해 보자

빼기 연산의 경우 직접 뺄셈을 구현하기보다는 negate()를 구현한 후 더하는 방식으로 연산하였다.

template <typename T>
Polynomial<T> Polynomial<T>::operator - (Polynomial& p) const // 빼기 연산자 오버로딩
{
	Polynomial temp = p.negate(); // p의 부호를 -로 변경하여 더하기로 해결
	return *this + temp;
}

 

 

---

2) 나의 현황

 

◆ 나도 C++로 연습문제들 풀어본것 말고는 막 뭐를 만들어본적이 없어 아직 많이 부족함을 알기에 좀더 연습겸 자료구조 공부를 한번더 하기로 했다. 이전에 C로 열혈자료구조를 공부한 덕에 기초적인 지식은 있지만, 또 막상 트리같은 부분은 생각안나는 부분도 많다. 다시 C++로 구현하면서 공부할 생각이다.

 

또 C++로 공부하는 이유는 ADT가 큰것같다. ADT의 참맛은 객체지향언어에서 명확히 느낄수있을것 같아 C++로 된 자료구조 책을 선택하였다. 요 몇일 자료구조 책 선택하느라 스트레스가 많았다. 이제 교제를 선택했으니 빡시게 공부하는일만 남았다!

​

이글의 모든 사진과 내용의 출처는 천인국, 최영규 님께 있습니다.