[자료구조 /C언어]-⑤ 다항식 배열,다항식의 덧셈

배열의 응용 : 다항식

오늘은 ​수학에서 나오는 다항식들을 배열을 이용하여 표현 해 보겠습니다.

어떻게??

​모든 차수의 계수 값들을 배열에 저장한다

 

*설계방식

예를 들어 10x^5 + 0x*4 + 0x^3 +6x+ 3 이라는 식이 있으면

{10 , 0 , 0 , 0 , 6 , 3}​ 을 저장하는 방식입니다.

​이방법은 10x^100 + 6 이라는 다항식의 경우 다항식을 저장 할 공간이 101개나 필요하다는 문제점이 있습니다.

​ 그러나 차수와 계수를 쉽게 찾을 수 있고 프로그램을 간단히 설계할 수 있습니다.

 

*프로그래밍

다항식을 저장할 구조체 변수를 만들어 줍니다.

 

degree: 최고차항의 지수

coef    : 계수들을 저장 (이때 degree의 +1 만큼 동적할당을 하여 필요한 공간만 쓰겠습니다.)

 

배열의 덧셈을 하기위해서는 먼저 다항식 구조체에 값을 저장해줘야 합니다.

str과 str2에 문자열로 다항식을 입력하면 그 다항식 문자열에서 계수들을 잘라와서 int타입의 배열에 넣어보겠습니다!

coef에게 필요한 공간을 할당해주기 위해 먼저 degree의 값을 알아야겠죠??

​degree의 값을 알기위해 first()라는 함수를 만들어 줬습니다.

제일 처음에 나오는 ^뒤의 문자를 숫자로 바꿔주고 그 값을 리턴합니다!

만약 다항식의 최고차항이 1차라면 1을 리턴해야겠죠?? ex) x+5

(여기서 상수항만 있을 경우는 고려하지 않았습니다.)

그후 각각 poly변수 p,q의 degree에 각각의 최고차항을 넣어주고

coef에는 calloc을 이용하여 초기화를하여 ​동적할당을 해줍니다.

이 작업까지 완료하였다면 이제 다항식을 담을 그릇이 완성이 된 것 입니다.

ex) 3x^5 + 6x^3 + 2x + 1

degree=5

coef = {0,0,0,0,0,0}

이제 coef에 해당하는 차수에 해당하는 계수들을 넣어줍니다!

cut() 함수를 이용하여 숫자를 잘라와서 메인에서 넣어주도록 하였습니다.

이때 각 차수에 해당하는 계수가 없다면 ( 위의 예에서는 2제곱이 존재하지 않는다.) 그 자리는 건너뜁니다.

이 작업을 위해 위에서 공간을 할당할 때 0으로 초기화를 해줬습니다.

add함수는 다항식의 덧셈을 하는 함수입니다.

 

#include <stdio.h> #include <stdlib.h> typedef struct poly{ int degree; //최고차항 지수 int *coef; // 최고차항지수+1만큼 동적할당 -> 계 수 }poly; /*문자상수 -> 숫자 : 문자상수-'0' 문자열 ->정수 :atoi(문자열)*/ int first(char *p); int cut(char *p,int pos,int* expo); void add(poly a,poly b); int main(int argc, char *argv[]) { struct poly p,q; char str2[100]; char str[100]; int i=0,expo,temp; int cnt=0,j=0; /*; printf(">> "); gets(str); //2x^6-32x^5-4x^3+x-12*/ printf("식 1 입력:"); scanf("%s",str); printf("식 2 입력 :"); scanf("%s",str2); p.degree=first(str); q.degree=first(str2); printf("%s\n",str); printf("%s\n",str2); p.coef=(int*)calloc((p.degree+1), sizeof(int)); q.coef=(int*)calloc((q.degree+1), sizeof(int)); for(i=0;i<p.degree;i++){ temp=cut(str, i, &expo); //printf("i=%d 차수: %d 위치 %d\n",i,expo,p.degree-expo); p.coef[p.degree-expo]=temp; } for(i=0;i<q.degree;i++){ temp=cut(str2, i, &expo); //printf("i=%d 차수: %d 위치 %d\n",i,expo,q.degree-expo); q.coef[q.degree-expo]=temp; } printf("최고차항 지수 : %d\n", q.degree); printf("계수 : { "); for(j=0;j<p.degree+1;j++){ printf("%2d, ",p.coef[j]); } printf("}\n"); add(p,q); return 0; } int first(char *p){ int i=0; while(*p!='\0'){ if(*p=='^'){ return *(p+1)-'0'; } i++; p++; } return 1; } int cut(char *p, int pos, int *expo){ int i=0; int cnt=-1; char temp[10]; while(*p!='\0'){ if(pos==0){ while(1){ temp[i++]=*p; p++; if(*p=='x'){ temp[i]='\0'; (*expo)=*(p+2)-'0'; return atoi(temp); } } } else { while(1){ temp[i++]=*p; p++; if(*p=='\0'){ temp[i]='\0'; //x가 없을떄 상수 자르 (*expo)=0; return atoi(temp);} if(*p=='x') break; } p++; if(*p=='^'){ cnt++; } if(cnt==pos){ temp[i]='\0'; (*expo)=*(p+1)-'0'; return atoi(temp); } else if(*p!='^'){//x가 있을때 상수 자르기 if(*expo==1){ i=0; while(1){ temp[i++]=*p; p++; if(*p=='\0'){ temp[i]='\0'; (*expo)=0; return atoi(temp); } } } temp[i]='\0'; (*expo)=1; return atoi(temp); } p++; i=0; //마지막의 제곱승 } p++; } } void add(poly a,poly b){ poly c; int A_deg=a.degree; int B_deg=b.degree; int apos=0,bpos=0,cpos=0; int i,j; int temp=0; char aa[10]; char str[100]; if(a.degree>b.degree){ c.degree=a.degree; c.coef=(int *)calloc((c.degree+1),sizeof(int)); for(i=0;i<=b.degree;i++){ c.coef[c.degree-i]=a.coef[a.degree-i]+b.coef[b.degree-i]; } for(i=b.degree+1;i<=a.degree;i++){ c.coef[c.degree-i]=a.coef[a.degree-i]; } for(i=0;i<c.degree+1;i++) printf(" %2d",c.coef[i]); } else if(a.degree==b.degree){ c.degree=a.degree; c.coef=(int*)calloc((c.degree+1),sizeof(int)); for(i=0;i<=a.degree+1;i++){ c.coef[c.degree-i]=a.coef[a.degree-i]+b.coef[b.degree-i]; } for(i=0;i<c.degree+1;i++){ printf(" %2d",c.coef[i]); } } else if(a.degree<b.degree){ c.degree=b.degree; c.coef=(int *)calloc((c.degree+1),sizeof(int)); for(i=0;i<=a.degree;i++){ c.coef[c.degree-i]=a.coef[a.degree-i]+b.coef[b.degree-i]; } for(i=a.degree+1;i<=b.degree;i++){ c.coef[c.degree-i]=b.coef[b.degree-i]; } for(i=0;i<c.degree+1;i++) printf(" %2d",c.coef[i]); } strcpy(str,"\0"); /* int num=-123; char str[10] itoa(num, str, 10); itoa(정수형데이터, 문자배열, 10);*/ for(i=0;i<c.degree-1;i++){ if(c.coef[i]!=0){ if(c.coef[i]>0) strcat(str,"+"); itoa(c.coef[i],aa,10); strcat(str,aa); strcat(str,"x^"); itoa(c.degree-i,aa,10); strcat(str,aa); } } if(c.coef[c.degree-1]!=0){ if(c.coef[c.degree-1]>0) strcat(str,"+"); itoa(c.coef[c.degree-1],aa,10); strcat(str,aa); strcat(str,"x"); } if(c.coef[c.degree]!=0){ if(c.coef[c.degree]>0) strcat(str,"+"); itoa(c.coef[c.degree],aa,10); strcat(str,aa); } printf("\n%s",str); }

 

 

결과