[자료구조] 링크드리스트를 이용한 다항식 클래스

소개글

[자료구조] 링크드리스트를 이용한 다항식 클래스에 대한 보고서 자료입니다.

목차

1. 문제제기 :

2. 문제분석 & 문제해결 : 구현한 내용 (detail한 예외처리 포함)
①다항식 클래스 생성
② 가용 공간 리스트의 사용
③ 다항식 입력 받기
④ 항 생성하기
⑤ 다항식의 덧셈 / 뺄셈 기능 구현
⑥ 다항식의 단항곱셈 기능 sMultPoly(c,e)
⑦ 다항식의 다항곱셈 기능
⑧ 다항식의 출력
⑨ 다항식의 계산 (evaluate)

3. 프로그래밍 소스

4. 결과화면

본문내용

r1 = head;
walker2 = head->next;
double mExp = power(x,walker2->data->exp); //이 변수가 중요하다.
//곱셈연산의 횟수를 획기적으로 줄이기 위한 방안이다.
result += walker2->data->coef * mExp ;//첫번째항이 계산되었음
walker1 = walker2;//다음항으로 이동
walker2 = walker2->next;
//이제 반복문으로 계산을 시작한다
while(walker2 != tail)
{
//mExp값을 사용함으로써 곱셈연산의 횟수를 줄인다.
mExp = mExp / power(x, walker1->data->exp - walker2->data->exp);
//다항식은 이미 정렬이 되어있는 상태이기 때문에 앞에서부터 지수는 점점 감소한다.
//예를들어 x^7을 이미 계산했고, 그 뒤 항이 x^5이라면,
//굳이 x^5을 다시 계산할 필요 없이 이미 계산한 x^7에다가 x^(7-5=2)를 나눈다.
//즉, 계산된 값을 저장해두었다가, 그다음 항을 계산할 때 다시 이용하는 것이다.
//Divide & Conquer방법을 쓰더라도,
//n값이 커질수록 x^n값을 구하는 시간이 오래 걸리기 때문에
//이런 방식으로 계속해서 가능한 n제곱을 구하는 함수를 호출하는 횟수와
//n값 자체를 줄이려는 노력을 해야 한다.
result += walker2->data->coef * mExp;
//계산된 mExp값과 계수를 곱해서 result에 합해준다.
//다음 항으로 이동.
walker1 = walker2;
walker2 = walker2->next;
}
return result;
}
void polynomial::sMultPoly(int c, int e) //다항식의 단항 곱셈함수
{
walker1 = head;
walker2 = head->next;
while(walker2 != tail)
{
walker2->data->coef *= c;//계수끼리곱하고
walker2->data->exp += e;//지수끼리 더한다
//다음 항으로 이동.
walker1 = walker2;
walker2 = walker2->next;
}
}
Term* polynomial::GetTerm()//사용할 노드를 제공
{
Term* new_term;
if(av->next == av)
//자기자신을 가르키고있다면, 생성된 항이 없는 것이다.
{
new_term = new Term(0,-1);//새 항 생성
}
else//그렇지 않다면, 사용할 수 있는 항이 있다.
{
new_term = av;//그 항을 사용
av = av->next;//av는 그 뒷칸의 포인터를 지정
}
return new_term;
}
void polynomial::RetTerm(Term *x)//x가 가리키는 노드를 해방
{
x->next = av;//가용공간리스트에 붙인다
av = x;
x=0;
}
4. 결과화면 :
다항식을 스트링 형식으로 입력한다. 이때 입력순서에 상관없이 지수순서로 정렬하며, 입력 형태의 5가지 종류에 따라 각각 대응하여 항을 생성한다.
다항식의 덧셈/뺄셈 기능을 확인하기 위해 B 다항식을 추가로 입력받는다. 입력방식은 위와 동일하게 스트링 형식이다. B 다항식이 입력되면 각각 A+B와 A-B 식을 계산하여 출력한다.
다항식의 곱셈기능을 확인한다. 다항식 C를 추가로 입력받는다. 입력방식은 위와 동일. C다항식이 입력되면 위에서 계산된 T1과 C를 곱한 G 다항식을 생성하여 출력한다.
다항식의 단항곱셈을 확인한다. 사용자에게 계수와 지수를 입력받는다. 계수가 0일 경우는 예외처리이며 지수는 음수여도 상관없다. 단항식이 입력되면 그 값을 G다항식에 곱한 결과를 출력한다.
G 다항식에 x값을 대입하여 함수 값 G(x)을 계산한다. evaluate()함수에서 계산될 때 double 타입을 가지므로, 소수점 연산이 가능하며, 따라서 지수가 음수인 경우에 대해서도 계산이 가능하다.
다음은 위와 동일한 식에 x값 2를 대입했을 경우의 결과이다.
5. 느낀점 :
지난번에는 배열로 구현하였지만, 이번에는 링크드리스트를 사용하여 구현하였습니다. 링크드리스트 자체가 일정수준의 포인터 조작능력이 필요하므로, 쉽지 않은 과제였습니다. 특히 가용공간리스트의 개념은 처음 접한 개념이어서 이해하는데 약간의 시간이 걸렸습니다. 가용공간리스트를 잘 활용하면 메모리 공간을 정말 효율적으로 관리할 수 있음을 깨닫고 정말 효율적인 자료구조라는 것을 알게 되었습니다.
이번 과제에서도 수많은 경우의 예외처리에 대해 고려하였습니다. 지난 과제였던 postfix에서 스트링형식의 문자열에 포함된 숫자와 연산자들을 치환하였던 것을 응용하여 이번 과제에서는 다항식의 입력을 스트링형식으로 받을 수 있도록 구현하였습니다. 이때 일반적으로 수학에서 쓰는 표기방법을 그대로 따르기 위해 각각의 조건을 분류하고, 그에 따른 각각 항을 생성하는 과정을 구현하였습니다. 이는 굳이 잘 쓰지 않는 1x^1 과 같은 표현이나 3x^0과 같은 표현을 입력하지 않아도 수학에서 쓰는데로 x, 3 이와 같은 형태로 입력이 가능하도록 합니다. 그 외에 사용자가 고의적으로 정렬되지 않은 다항식을 입력하거나, 고의적으로 동류항을 연속해서 입력한다 하더라도, setTerm()함수에서 자동으로 처리할 수 있도록 구현하여서, 프로그램의 완성도를 높이기 위해 최선을 다했습니다.
그 밖에 Evaluate함수에서 x^n을 구하는 과정은 지난번 과제에 썼던 Divide & Conquer방법을 그대로 적용하되, 이번에는 다항식의 맨 처음부터 구해서 그 다음 항과의 차이만큼 나누는 방식으로 구현하였습니다. 이와 같은 방법으로 곱셈연산의 숫자를 가능한 줄이는 방법을 사용하였습니다.
이번 과제를 통해 수학적/논리적인 개념을 컴퓨터에 정확히 매치시키고, 보통 우리가 일상생활에서 사용하는 방식 그대로를 적용하여야 사용자에게 좀 더 친숙한 프로그램이 된다는 것을 알게 되었습니다. 또한 데이터를 정제할 때 적절한 알고리즘을 사용하여 메모리공간과 시간면에서 효율성을 고려하는 프로그래밍 기법에 대해 알게 되었습니다.

키워드

자료구조,   링크드리스트,   연결리스트,   다항식,   polynomial,   linked list