�ݺ�ߣ

D2조 자료구조
3. 다항식 계산

조장 : 20093539 황준호
조원 : 20093447 김도형
20093536 홍준표
20113324 최수영
2010 조영래

과제수행일지
소속 조원
D2 조장 : 황준호 자료조사 : 김도형, 최수영 코딩 : 홍준표, 조영래
과제수행기간 13일 8시간
I. 계획의 작성
연구제목 다항식 계산

연구배경 연결 리스트(Linked list)를 사용하여 다항식 계산을 구현한다.

참고자료 참고 URL http://blog.naver.com/rudrbs3?Redirect=Log&logNo=50135830391

II. 계획의 실행
첫째 날 2012년 4월 12일 목요일
오늘의 작업 주제에 대한 이해와 업무 분담

조장을 중심으로 각자 임무를 분담하고, 다항식의 계산을 c로 구현하는 것에 앞서, 컴퓨터
토의 내용
가 어떤식으로 계산을 할지를 먼저 파악하였다.

과제준비에서 이번 다항식 계산 프로젝트를 어떤식으로 설계하면 좋을지 이해하는게 중요했고, 첫 회의라
느낀 점 자료가 부족하여 토의가 제대로 진행이 안된점이 좀 아쉬웠다.

둘째 날 2012년 4월 17일 화요일

오늘의 작업 개인이 조사해 온 자료를 토대로 연결리스트에 대해 이해하는 시간을 가졌다.

연결 리스트(Linked list)의 개념

링크드 리스트는 배열의 단점인 데이터의 삽입/삭제가 불리하다는 점을 보완하기위해 설계
된 자료구조이다.
토의 내용 삽입/삭제가 불리한 이유는 선형적으로 나열된 데이터행렬 중 중간 값을 제거하거나 삽입
할때 데이터들을 밀거나 당겨야하므로 좋지 않다.

데이터들이 선형적으로 나열되어 있으면서 중간데이터의 삽입/삭제시 데이터의 당김 혹은
밀어내는 행위없이 처리할 수 있는 방법이 바로 링크드 리스트이다.

위 그림을 보면 하나의 데이터공간은 데이터를 저장할 공간과 포인터를 저장할 공간으로
구성되어있다.

즉, 구조체를 이용하여 데이터공간과 포인터공간을 하나의 데이터공간으로 만들어두고

데이터공간에는 실제 데이터 포인터공간에는 선형적으로 나열시킬 메모리주소를 저장시켜
삽입 혹은 삭제시 포인터값만 바꿔주면 되도록 설계한 것이다.

- 링크드리스트의 장점과 단점
링크드 리스트는 다음데이터의 포인터주소를 가지고 있기에 연속적인 메모리가 아니여도
상관없다.
또 데이터크기 조정이 쉽고 자료를 사용하는 방식에 따라 단일링크드리스트로 할지 더블
링크드리스트로 할지 결정할 수 있다.

하지만 접근속도가 느리다.
(배열같은 경우 인덱스를 통해 한번에 접근가능하지만 리스트는 처음 혹은 끝에서 포인터
를 타고 들어가야한다.)

- 링크드리스트의 성능
접근시(검색) : 배열 : O(c) Linked List : O(n)

변경시(삽입/삭제/수정) : 배열 : O(n) Linked List : O(c)

- 링크드리스트의 종류
지금까지 설명된 링크드 리스트는 포인터를 이용한 링크드리스트이다.

즉, 동적할당으로 데이터를 담을 공간을 확보하는 방식이다.

앞서 언급한대로 게임에서는 퍼포먼스가 아주 중요한데 그러기 위해서는 잦은 동적할당은
금지해야될 사항이라는 것이다.

그렇다면 링크드리스트를 사용하면서도 퍼포먼스를 떨어트리지 않는 방법은 무엇일까. 이
개념 그대로 배열과 믹싱이 가능하다면 해답은 바로 그것이다. 다른건 변함없이 포인터를
저장할 공간에 배열인덱스를 저장하면 일명, 배열 링크드리스트이다.

- LinkedList를 구현한 예제소스

#include <stdio.h>

#include <malloc.h>

typedef char element;

//링크드리스트 구현.

//노드

typedef struct QNode{

element data;

struct QNode *link;

}QNode;

//좌우..

typedef struct{

QNode *front,*rear;

}LQueueType;

//생성 초기화.

LQueueType *createLinkedQueue(){

LQueueType *LQ;

LQ = (LQueueType *)malloc(sizeof(LQueueType));

LQ->front = NULL;

LQ->rear = NULL;

return LQ;

}

int isEmpty(LQueueType *LQ){

if (LQ->front == NULL){

return 1;

}else{

return 0;

}

}

//삽입

void enQueue(LQueueType *LQ, element item){

QNode *newNode = (QNode *)malloc(sizeof(QNode));

newNode->data = item;

newNode->link = NULL;

if(LQ->front == NULL){

LQ->front = newNode;

LQ->rear = newNode;

}else{

LQ->rear->link = newNode;

LQ->rear = newNode;

}

}

//디큐

element deQueue(LQueueType *LQ){

QNode *old = LQ->front;

element item;

if(isEmpty(LQ)) return 0;

else{

item = old->data;

LQ->front = LQ->front->link;

if(LQ->front == NULL)

LQ->rear = NULL;

free(old);

return item;

}

}

//삭제

int del(LQueueType *LQ){

QNode *old = LQ->front;


else{

LQ->front = LQ->front->link;

if(LQ->front == NULL) LQ->rear = NULL;

free(old);

return 1;

}

}

//픽업.

element peek(LQueueType *LQ){

element item;


else{

item = LQ->front->data;

return item;

}

}

//출력.

void printLQ(LQueueType *LQ){

QNode *temp = LQ->front;

printf("Q [");

while(temp){

printf("%3c",temp->data);

temp = temp->link;

}

printf(" ]n");

}

연결 리스트에 대해 필요한 구조들은 알았으나 다항식에 어떻게 적용해야 할지 감이 오지
느낀점
않았다.

셋째 날 2012년 4월 19일 목요일
다항식 계산을 어떻게 해야될지에 대해서 토의를 하였고, 초안을 작성하는데 덧셈밖에
오늘의 작업
구현하지 못하였다.
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

초안
typedef struct ListNode { //리스트 노드 구조
int coef; //계수
int exp; //지수
struct ListNode *link;

} ListNode;

typedef struct ListHeader { //리스트 헤더 노드 구조
int length;
ListNode *head;
ListNode *tail;
} ListHeader;

void init(ListHeader *plist) // 초기화, 공백 헤더 노드
{
plist->length = 0; //length를 0으로
plist->head = plist->tail = NULL; // head와 tail을 NULL으로
}

// 연결 리스트에 삽입
// plist는 헤더를 가리키는 포인터, coef는 계수, exp는 지수
void insert_node_last(ListHeader *plist, int coef, int exp)
{
//공백 연결리스트 생성
ListNode *temp = (ListNode *)malloc(sizeof(ListNode));
if(temp == NULL){
exit(1);
}
temp->coef=coef;
temp->exp=exp;
temp->link=NULL;
if(plist->tail == NULL){
plist->head = plist->tail = temp;
}
else {
plist->tail->link = temp;
plist->tail = temp;
}
plist->length++; //length 증가
}

// 다항식 덧셈
// 다항식3 = 다항식1 + 다항식2
void poly_add(ListHeader *plist1, ListHeader *plist2, ListHeader *plist3)
{
ListNode *a = plist1->head;
ListNode *b = plist2->head;
int sum; //계수를 담을 변수

while(a &&b){
if(a->exp == b->exp){ //지수가 같을경우
sum = a->coef + b-> coef;
list3, sum, a->exp);if( sum != 0 ) insert_node_last(p
a=a->link; b=b->link;
}
else if(a->exp >b->exp){ //다항식1의 지수가 클경우
insert_node_last(plist3, a->coef, a->exp);
a=a->link;
}
else {
insert_node_last(plist3, b->coef, b->exp);
b=b->link;
}
}
//남아있는 항들을 모두 다항식3으로 복사
for(; a != NULL; a=a->link)
insert_node_last(plist3, a->coef, a->exp);
for(; b != NULL; b=b->link)
insert_node_last(plist3, b->coef, b->exp);
}

//다항식 출력
void poly_print(ListHeader *plist)
{
ListNode *p=plist->head;
for(;p;p=p->link){
if (p->coef == 0 || p->exp == 0){
printf(""); //계수 or 지수가 0이면 표시하지 않음
}else if (p->exp == 1){
printf("%d",p->coef); //지수가 1이면 계수만 표시
}else{
printf("%dx^%d", p->coef, p->exp);
//계수 or 지수가 0이 아니면 계수x^지수 형태로 표시
if (p->link == NULL)
{
printf("");
}else{
printf(" + ");
}
}
}

printf("n");
}

int main(void)
{
ListHeader list1, list2, list3; //다항식 입력받을 변수 선언

init(&list1);//init 함수 호출로 공백 리스트
init(&list2);
init(&list3);

int a,b; //항의 계수와 지수를 입력받기 위한 변수
char num;
//다항식1을 입력받는 부분
printf("다항식1의 항(계수,지수)을 입력하세요. (0 0 이면 입력종료)n");
while (1)
{
scanf("%d %d",&a,&b);
if (a==0 &&b==0)
{
break;
}
insert_node_last(&list1, a, b);
}
printf("다항식1 : ");
poly_print(&list1); //다항식1 출력
printf("n");

//다항식2을 입력받는 부분
printf("다항식2의 항(계수,지수)을 입력하세요. (0 0 이면 입력종료)n");
while (1)
{
scanf("%d %d",&a,&b);
if (a==0 &&b==0)
{
break;
}
insert_node_last(&list2, a, b);
}
printf("다항식2 : ");
printf("n");

// 다항식3 = 다항식1 + 다항식2
poly_add(&list1, &list2, &list3);

printf("결과 : ");

getch();
}

지수를 비교해 같으면 계수로 빠지고 다시 지수를 비교했을 때 더 큰수가 빠져나오는 식의
과제준비에서
덧셈을 구현했는데 뺄셈도 비슷한 식으로 하면 될 것 같았지만 곱셈 나눗셈에서 특히 의견
느낀 점
이 많아 시간을 많이 지연한점이 조금 아쉬웠다.

결과

#include <iostream.h>
#include <ctype.h>
#define max 50

/**** Term 클래스 **/
최종프로그램 class Term
소스와 설명 {
public:
int coef;//계수
int exp; //지수
Term *link; //링크

};
/*** Polynomial 클래스 ***/

class Polynomial
{
public:
Term *first; //Term클래스형의 포인터변수
Polynomial() //생성자
{
first=new Term;
first->link=first;
first->exp = -1;
}
void Attach(int, int); //노드를 붙이는것
void insert(char *string); //string을 넣어서 리스트에 넣는것.
Polynomial Sum(const Polynomial& a, const Polynomial& b); //다항식을 더
하는 것.
Polynomial Sub(const Polynomial& a, const Polynomial& b); //다항식을 빼
는 것.
Polynomial Multi(const Polynomial& a, const Polynomial& b); //다항식을 곱
하는 것.
float Evaluate(const Polynomial& c, float x); //계산 결과를 출력하
는 함수.
};

/*** 노드를 붙이는 함수 ***/
void Polynomial::Attach(int c, int e)
{
Term *t = new Term; //붙일 노드는 t
Term *k;
k = first;
t->coef = c; t->exp = e;

while(k->link != first) //k가 마지막 노드를 가리키도록.
{
k = k->link;
}
k->link=t;
t->link=first; //끝의 노드 링크가 first를 가리킴.
}

/*** string을 노드에 입력하는 함수 ***/
void Polynomial::insert(char *string)

{
int c, e;
while(1)
{
if(*string == '-') //처음에 입력값이 마이너스 일때
{
string++;
c = (int)(*string - 48); //char을 숫자로 바꿔줌.
string++;
if(*string == '_')
{
c = -c;//한자리수면 마이너스를 붙임.
string++;
}
else if(isdigit(*string)) //두자리 숫자일때
{
c = -((c*10) + ((int) (*string-48)));
string+=2;
}
e = (int)(*string - 48); //지수부분 숫자로 바꿔줌
string++;
if(*string == '_') string++;
else if(isdigit(*string)) //지수가 두자리일때
{
e = (e*10) + ((int) (*string-48));
string+=2;
}
Attach(c, e); //노드를 붙임.
}
else if(isdigit(*string)) //처음 입력값이 숫자일때
{
c = (int)(*string - 48);
string++;
else if(isdigit(*string)){ //두자리일때
c = (c*10) + ((int) (*string-48));
string+=2;
}

e = ((int)(*string - 48));
string++;
else if(isdigit(*string)) //두자리일때

{
e = (e*10) + ((int) (*string-48));
string+=2;
}
Attach(c, e);
}
//다음 char가 문자도 아니고 마이너스도 아닐경우
if(!isdigit(*string) && *string != '-') break;
}
}

/ cout 오버로딩 /
ostream& operator<<(ostream& os, Polynomial& x)
{
Term *s = x.first -> link;
while(1)
{
if(s->link->exp == -1) //객체의 값이 끝이면
{
os<<"("<<s->coef<<"x^"<<s->exp<<")"; //계수와 지수를
출력
s = s->link; //다음노드
break;
}
else //끝이 아닐때
{
os<<"("<<s->coef<<"x^"<<s->exp<<")"<<"+"; / / 계
수와 지수를 출력
s = s->link; //다음노드
}
}
return os;
}

/* 다항식의 지수를 비교하는 함수 ****/
char compare(int a, int b)
{
if(a == b)
return '=';
else if(a > b)
return '>';
else
return '<';

}

/ 다항식을 덧셈하는 함수 ***/
Polynomial Polynomial::Sum(const Polynomial& a, const Polynomial& b)
{
Term *s = a.first->link; //객체 a의 first다음값.
Term *t = b.first->link; //객체 b의 first다음값.
int sum;
Polynomial c; //연산결과가 들어갈 객체
while(1)
{
switch(compare(s->exp, t->exp))
{
case'=': //지수가 같으면 계수를 더하고 더한 값을 노드를 만든다.
if (t->exp == -1) return c;
sum = s->coef + t->coef;
if (sum) c.Attach(sum, t->exp);
s = s->link; t = t->link;
break;

case'<': //t가 크면 t의 노드를 이동
c.Attach(t->coef, t->exp); //t를 c에 붙임.
t = t->link;
break;

case'>': //s가 크면 s의 노드를 이동
c.Attach(s->coef, s->exp); //s를 c에 붙임.
s = s->link;
break;
}
}
}

/ 다항식을 뺄셈하는 함수 ***/
Polynomial Polynomial::Sub(const Polynomial& a, const Polynomial& b)
{
Term *s = a.first->link; //객체 a의 first다음값.
Term *t = b.first->link; //객체 b의 first다음값.
int sub;
Polynomial c; //연산결과가 들어갈 객체
while(1)
{
switch(compare(s->exp, t->exp))

{
case'=': //지수가 같으면 계수를 빼고 더한 값의 노드를 만든다.
if (t->exp == -1) return c;
sub= s->coef - t->coef;
if (sub) c.Attach(sub, t->exp);
s = s->link; t = t->link;
break;

case'<': //t가 크면 t의 노드를 이동
c.Attach(t->coef, t->exp); //t를 c에 붙임.
t = t->link;
break;

case'>': //s가 크면 s의 노드를 이동
c.Attach(s->coef, s->exp); //s를 c에 붙임.
s = s->link;
break;
}
}
}

/**** 다항식을 곱셈하는 함수 ***/
Polynomial Polynomial::Multi(const Polynomial& a, const Polynomial& b)
{
Term *x = a.first->link; //객체 a의 first다음값
Term *y = b.first->link; //객체 b의 first다음값
Polynomial c;
int coef_result, exp_result; //계산결과가 들어갈 변수
while(x != a.first) //x가 first가 아니면
{
y = b.first->link; //다시 초기화시켜주어야 함.
while(y != b.first)
{
coef_result = x -> coef * y -> coef; //계수 곱함.
exp_result = x -> exp + y -> exp; //지수 더함.
c.Attach(coef_result, exp_result); //결과를 c에 붙임
y = y -> link; //y노드 이동
}
x = x -> link; //x노드 이동
}
return c;
}

/** 실수 x를 대입했을때 계산결과 ****/
float Polynomial::Evaluate(const Polynomial& c, float f)
{
Term *a = c.first->link; //객체 c의 first다음값
float s=0; //초기화
int eval_coef, eval_exp, i; //연산한값들을 저장할 변수
while(a != c.first) //a가 first가 아니면
{
eval_coef = (int)a->coef; //계수
eval_exp = (int)f; //지수
for(i=1; i<a->exp; i++)
{
eval_exp *= (int)f; //지수 계산
}
s += (float)eval_coef * (float)eval_exp; //하나의 노드 연산
a = a->link; //노드 이동
}
return s; //연산결과 리턴
}

/ main 함수 */
int main()
{
Polynomial a,b,c;//객체 생성
char string[max]; //입력받는 문자 배열로 만듬.
float f; //계산할 x의 값

cout<<endl<<"**다음과 같은 형식으로 다항식을 입력하시오**"<<endl;
cout<<" ex) 3x^3+2x^2+2 = 3_3_2_2_2_0"<<endl<<"
-23x^3+2x^1 = -23_3_2_1"<<endl<<endl;
cout<<"첫번째 다항식을 입력하세요: ";
cin>>string; //char입력
a.insert(string); //a리스트 생성
cout<<"첫번째 입력 다항식: "<<a<<endl<<endl;

cout<<"두번째 다항식을 입력하세요: ";
cin>>string;
b.insert(string); //b리스트 생성
cout<<"두번째 입력 다항식: "<<b<<endl<<endl;

cout<<"계산을 위한 x의 값을 넣어주세요: ";
cin>>f; //계살할 x값 입력

cout<<"**"<<endl;
cout<<" 연산 수행 결과 *"<<endl;
c = c.Sum(a,b); //두 링크드리스트 다항식을 더함
cout<<"O두 다항식의 덧셈결과: "<<c<<"="<<c.Evaluate(c, f)<<endl;
c = c.Sub(a,b); //두 링크드 리스트를 뺌
cout<<"O두 다항식의 뺄셈결과: "<<c<<"="<<c.Evaluate(c, f)<<endl;
c = c.Multi(a,b); //두 링크드 리스트를 곱함
cout<<"O두 다항식의 곱셈결과: "<<c<<"="<<c.Evaluate(c, f)<<endl;

cout<<"**"<<endl<<endl;
return 0;
}

/*■ 덧 셈: 두개의 원형링크드 리스트의 노드의 지수를 비교하
여 컴패얼 함수의 리턴값에 따라 케이스문을 이용하
여 두개의 값이 같을 때는 더하고 다를때는 노드를
이동하여 계산함.

■ 뺄 셈: 덧셈과 마찬가지로 노드의 지수를 비교하여 컴패얼
함수의 리턴값에 따라 케이스문을 이용하여 두개의
값이 같을 때는 빼고 다를때는 노드를 이동하여 계
산함.

■ 곱 셈: 첫 번째 링크드리스트의 첫째항과 두 번째 링크드리
스트 노드 전부를 곱하여 더하고 첫 번째링크드 리
스트의 둘째항과 두 번째 링크드리스트 노드 번부
를 곱하여 더하고 이런 방식으로 두개의 링크드 리
스트가 마지막이 될 때까지 계산함
링크드리스트에 대해 알아보다가 원형 링크드리스트가 있다는
것을 되어 원형 링크드 리스트를 이용하였다. 다항식의 계산하는
것을 처음에는 책을 보면서 책의 소스를 전부 사용해보고 이해도
하였지만 너무 힘든점이 많았다. 그래서 책의 내용대로 완벽하게
구현하는 것은 제쳐두고 우리가 아는 방식으로 클래스를 만들어
서 구현하였다. 책을 보고 똑같이 구현할려고 할때는 조그만 것
과제를 마치면서
느낀 점
을 코딩할때도 막혀서 답답했지만 책을 바탕으로 하지 않고 코딩
을 하니 좀 더 하기가 좋았다.

�ݺ�ߣ

2012 Ds D2 03

Recommended

More Related Content

What's hot (20)

Viewers also liked (7)

Similar to 2012 Ds D2 03 (20)

2012 Ds D2 03