【 C 】 다항식 덧셈

과정: 프로 그래 밍 입문 - C 언어 (옹 케)
제목 내용:
하나의 다항식 은 x 의 각 차 멱 과 계수 곱 의 합 으로 표현 할 수 있다. 예 를 들 어:
2x6+3x5+12x3+6x+20
현재, 당신 의 프로그램 은 두 개의 다항식 을 읽 은 후에 이 두 개의 다항식 의 합 을 출력 해 야 합 니 다. 즉, 대응 하 는 멱 의 계 수 를 더 한 후에 출력 하 는 것 입 니 다.
프로그램 이 처리 할 멱 은 최대 100 이다.
입력 형식:
모두 두 개의 다항식 을 입력 해 야 하 며, 각 다항식 의 입력 형식 은 다음 과 같다.
줄 마다 두 개의 숫자 를 입력 하고 첫 번 째 는 멱 차 를 표시 하 며 두 번 째 는 이 멱 차 의 계 수 를 표시 하 며 모든 계 수 는 정수 이다.첫 줄 은 반드시 최고 멱 이 고, 마지막 줄 은 반드시 0 차 멱 이다.
첫 줄 과 마지막 줄 사이 에 반드시 멱 차 감소 순서에 따라 배열 되 지 않도록 주의 하 세 요.만약 어떤 幂 次 의 계수 가 0 이 라면 입력 데이터 에 나타 나 지 않 는 다.0 차 멱 의 계수 가 0 일 때 도 입력 데이터 에 나타 납 니 다.
출력 형식:
최고 멱 부터 차례대로 0 멱 으로 내 려 갑 니 다. 예 를 들 어:
2x6+3x5+12x3-6x+20
그 중의 x 는 소문 자 x 이 고 모든 기호 사이 에 빈 칸 이 없 으 며 특정한 멱 의 계수 가 0 이면 그 항목 이 필요 하지 않 습 니 다.
입력 예시:
6 2
5 3
3 12
1 6
0 20
6 2
5 3
2 12
1 6
0 20
출력 예시:
4x6+6x5+12x3+12x2+12x+40
시간 제한: 500 ms 메모리 제한: 32000 kb
사고방식 과 실현:
원 제 는 배열 을 사용 해 야 하 는데, 여 기 는 단일 체인 표 로 바 꾸 어 실현 해 야 한다.주의해 야 할 점 은:
1. 입력 데 이 터 는 반드시 강 멱 순서에 따라 야 하 는 것 이 아니 므 로 여러 가지 항목 에 대해 다시 강 멱 에 따라 정렬 하고 삽입 정렬 법 을 사용 해 야 한다.
2. 다항식 을 출력 할 때 계수 와 멱 의 여러 가지 상황 을 고려 해 야 하 며 형식 에 차이 가 있다.
C 언어 코드:
#include 
#include 

typedef struct poly{
    int expo;
    int coef;
    struct poly *next;
} *Poly;

Poly ReadPoly();
Poly Add(Poly p1, Poly p2);
void Print(Poly p);

int main(){
    Poly p1, p2, p;
    p1 = ReadPoly();
//    Print(p1);
    p2 = ReadPoly();
//    Print(p2);
    p = Add(p1, p2);
    Print(p);
    return 0;
}

/*
       ,                    ;	
*/
Poly ReadPoly(){
    Poly polynomial, a, temp;
    polynomial = (Poly)malloc(sizeof(struct poly));
    polynomial->next = NULL;
    while(1){
        Poly P = (Poly)malloc(sizeof(struct poly));
        scanf("%d %d", &(P->expo), &(P->coef));
        P->next = NULL;
		a = polynomial;
		while(a->next != NULL && P->expo < a->next->expo ){
			a = a->next;
		}
		P->next = a->next;
		a->next = P;

        if(P->expo == 0){
            break;
        }
    }    

    temp = polynomial;
    polynomial = polynomial->next;
    free(temp);
    return polynomial;
}

Poly Add(Poly p1, Poly p2){
    Poly s1, s2, polynomial, rear, temp;
    s1 = p1;
    s2 = p2;
    polynomial = (Poly)malloc(sizeof(struct poly));
    polynomial->next = NULL;
    rear = polynomial;
    while(s1 && s2){
        if(s1->expo > s2->expo){
            rear->next = s1;
            rear = rear->next;
            s1 = s1->next;
        }
        else if(s1->expo == s2->expo){
            int c = s1->coef + s2->coef;
            if(c != 0){
                temp = (Poly)malloc(sizeof(struct poly));
                temp->coef = c;
                temp->expo = s1->expo;
                rear->next = temp;
                rear = rear->next;
            }
            s1 = s1->next;
            s2 = s2->next;
        }
        else{
            rear->next = s2;
            rear = rear->next;
            s2 = s2->next;
        }
    }
    while(s1){
        rear->next = s1;
        rear = rear->next;
        s1 = s1->next;
    }
    while(s2){
        rear->next = s2;
        rear = rear->next;
        s2 = s2->next;
    }
    /*     0   */
    if(polynomial->next == NULL){
    	Poly zero = (Poly)malloc(sizeof(struct poly));
    	zero->coef = 0;
    	zero->expo = 0;
    	zero->next = NULL;
    	rear->next = zero;
    	rear = rear->next;
	} 
    temp = polynomial;
    polynomial = polynomial->next;
    free(temp);
    return polynomial;
}

void Print(Poly p){
	if(p->coef == 0){
		printf("0");
		return;
	}
	
    int flag = 0;
    while(p){
        if(flag++){
            if(p->coef > 0){
                printf("+");
            }
        }
        if(p->expo == 0){
            printf("%d",p->coef);
            break;
        }
        else if(p->expo == 1){
            if(p->coef == 1){printf("x");}
            else if(p->coef>1 || p->coefcoef);}
		    else if(p->coef == -1){printf("-x");}
		    p = p->next;
		}
		else{
			if(p->coef == 1){printf("x%d", p->expo);}
			else if(p->coef == -1){printf("-x%d", p->expo);}
			else if(p->coef>1 || p->coefcoef, p->expo);}
			p = p->next;
		}
    }
    printf("
"); }

좋은 웹페이지 즐겨찾기