HW #2 제출일자 : 4/8까지 jano@sejong.edu로 제출 (문제 1) P150 문제를 프로그래밍 할 것 Source file (헤더파일포함), 실행화면 (학번_이름_1.txt) 을 학번_이름_1.zip으로 묶어서 제출할 것 (문제 2) 다항식 문제를 프로그래밍 할 것 을 학번_이름_2.zip으로 묶어서 제출할 것
(문제 2) 다항식(1) 다항식의 표현 리스트를 사용해서 다항식을 표현 ai : 0이 아닌 계수 ei : 음수가 아닌 정수 지수 em-1>em-2> ... >e1>e0≥ 0 리스트를 사용해서 다항식을 표현 계수, 지수, 다음 항을 가리키는 포인터 등 3개의 필드로 구성되는 노드로 표현 계수가 정수라고 가정 typedef struct polyNode *polyPointer; typedef struct polyNode { int coef; int expon; polyPointer link; }; polyPointer a,b; coef exp link polyNode
다항식 (2) 다항식의 표현 (계속 - 입력값) a = 3x14+2x8+1 b = 8x14-3x10+10x6 a
다항식 (3) 다항식의 덧셈 포인터 a와 b가 가리키는 노드에서 시작되는 항들을 비교 b가 가리키는 항의 지수보다 a가 가리키는 항의 지수가 작으 면, b의 항과 같은 항을 만들어 결과 다항식 d에 첨가시키고 포 인터 b를 다음 노드로 이동 반대의 경우(a->expon > b->expon)는 a에 대해 수행
다항식 (4) 다항식의 덧셈 (계속) c=a+b의 처음 세 항을 생성 a->expon == b->expon
다항식 (5) polyPointer padd(polyPointer a, polyPointer b) { /* a와 b가 합산된 다항식을 반환 */ polyPointer c, rear, temp; int sum; MALLOC(rear, sizeof(*rear)); c= rear; while(a && b) switch(COMPARE(a->expon, b->expon)) { case -1: /* a->expon < b->expon */ attach(b->coef, b->expon, &rear); b = b->link; break; case 0 : /* a->expon = b->expon */ sum = a->coef + b->coef; if(sum) attach(sum, a->expon, &rear); a = a->link; b = b->link; break; case 1: /* a->expon > b->expon */ attach(a->coef, a->expon, &rear); a = a->link; } /* 리스트 a와 리스트 b의 나머지를 복사 */ for(; a; a=a->link) attach(a->coef, a->expon, &rear); for(; b; b=b->link) attach(b->coef, b->expon, &rear); rear->link = NULL; /* 필요 없는 초기 노드를 삭제 */ temp = c; c= c->link; free(temp); return c;
다항식 (6) 다항식의 덧셈 (계속) padd의 분석 고려 요소 void attach(float coefficient, int exponent, polyPointer *ptr) { /* coef=coefficient 이고 expon=exponent인 새로운 노드를 생성하고, 그것을 ptr에 의해 참조되는 노드에 첨가한다. ptr을 갱신하여 이 새로운 노드를 참조하도록 한다. */ polyPointer temp; MALLOC(temp, sizeof(*temp)); temp->coef = coefficient; temp->expon = exponent; (*ptr)->link = temp; *ptr = temp; } 리스트의 끝에 노드를 첨가 padd의 분석 고려 요소 (1) 계수 덧셈 (2) 지수 비교 (3) c를 위한 새로운 노드 생성 a와 b가 각각 m개와 n개의 항을 가지고 있을 때 연산시간 : O(m+n) 계수 덧셈 : 0≤계수 덧셈의 횟수 ≤ min{m,n} 지수 비교 : while 루프 한번 반복될 때 마다 한번씩 while루프 수행 횟수는 m+n을 넘을 수 없음 최대 m+n개의 새로운 노드가 만들어짐