[자료구조] 연결리스트의 활용 2 : 다항식 덧셈

단일 연결리스트

해당 포스팅에서 다루는 문제에 대한 설명과 알고리즘은 아래 링크의 포스팅에서 추가 및 수정하였다.
현재 포스팅을 이용해 주어진 다항식 문제를 풀어도 되나, 필자는 새로운 포스팅(아래 링크)를 이용하는 것을 추천한다.

[5] 리스트 ① 단일 연결리스트: 다항식

1. 다항식을 표현하는 연결 리스트 구조

• 하나의 다항식(polynomial)을 하나의 헤더 단일연결리스트로 표현하는 방식 사용
• 다항식의 각 항은 하나의 노드로 표현하고, 각 노드에는 다음 세 개의 필드를 저장 

coef	항의 계수
exp	항의 차수
next	다음 노드를 가리키는 링크

하나의 연결 리스트의 각 노드는 차수의 내림차순 순으로 유지하고, 계수가 0인 항의 노드는 유지하지 않음

예) 아래 세 개의 다항식을 나타내는 단일 연결 리스트 그림

a=3x^4 +8x
b=11x^3 -8x+4
c = -6x^2

2. 다항식에 항 추가

◦ 기존 다항식의 마지막 항을 표현하는 노드 k에 계수 c와 차수 e로 이루어진 새 항 추가

Alg appendTerm(k, c, e)
    input last term of a polynomial expression k, coefficient c, exponent e
    output cxe appended to k

1. t ← getnode()
2. t.coef ← c
3. t.exp ← e
4. t.next ← NULL
5. k.next ← t
6. k ← t {k advances to t}
7. return

3. 다항식 덧셈

◦ 두 개의 다항식 x, y에 대한 덧셈을 수행하여 그 결과를 새로운 헤더 단일 연결 리스트에 저장

예: 위 예의 다항식a,b의덧셈결과는3x4 +11x3 +4를 반환

Alg addPoly(x, y)
    input polynomial expression x, y
    output x + y

1. result ← getnode() 
2. result.next←NULL 
3. i ← x.next
4. j ← y.next 
5. k ← result
6. while ((i ≠ NULL) & (j ≠ NULL)) 
          if (i.exp > j.exp) 
                appendTerm(k, i.coef, i.exp) 
                i ← i.next 
          else if (i.exp < j.exp) 
               appendTerm(k, j.coef, j.exp) 
                j ← j.next 
          else
               sum ← i.coef + j.coef 
                if (sum ≠ 0) 
                        appendTerm(k, sum, i.exp) 
                i ← i.next 
                j ← j.next 
7. while (i ≠ NULL ) 
          appendTerm(k, i.coef, i.exp) 
          i ← i.next
8. while (j ≠ NULL) 
          appendTerm(k, j.coef, j.exp) 
          j ← j.next 
9. return result 

 

[문제 1 ] 위의 설명과 같이 다항식을 헤더 단일 연결 리스트로 표현하고, 다항식의 덧셈을 구하는 프로그램을 작성하라.

• 입력에 대한 설명 (아래 입출력 예시 참조)
  - 첫 번째 다항식의 항의 개수가 입력되고, 이후에 다항식의 각 항의 (계수, 지수) 쌍이 지수의
• 내림차순으로 입력됨
  - 동일한 방식으로 두 번째 다항식의 정보가 입력됨
• 출력에 대한 설명 (아래 입출력 예시 참조)
  - 결과 다항식의 각 항의 (계수, 지수) 쌍을 지수의 내림차순으로 출력

 

입출력 예제

답안 코드

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
/*연결 리스트를 구현할 구조체*/
typedef struct ListNode {
	int coef;// 항의 계수
    int exp; // 항의 차수
    struct ListNode *next;//다음 노드의 위치

    /*
    하나의 연결리스트의 각 노드는 차수의 내림차순으로 유지
    계수가 0인 항의 노드는 유지하지 않는다.

    노드의 정렬은 계수 -> 차수 수으로 정렬된다.
    */
}ListNode;

int main(void){
    int count,n,m,cnt=0,rep=0,max=-1;
    int numarr[1000][2]={0,0};

    for(int i=0;i<1000;i++)numarr[i][1] = i;
    //count: 첫 번째 다항식의 항의 계수 -> 입력받을 횟수는 count*2
    //항의 개수만큼 리스트가 필요. 단 헤더노드는 선언 후 입력받을 것.

    ListNode* firhead = (ListNode*)malloc(sizeof(ListNode)); //헤드 노드 생성(1)
    ListNode* sechead = (ListNode*)malloc(sizeof(ListNode)); //헤드 노드 생성(2)

    ListNode**arr[2] = {&firhead,&firhead};//구조체 이중 포인터 선언

    while(rep<2){
        scanf("%d",&count);
        for(int i=0;i<count;i++){//항의 계수만큼 반복하되, 한번의 입력과정에서 계수와 차수를 입력받음.
            scanf("%d %d",&n,&m);//차수와 계수를 입력받는다.

            ListNode* curr = *arr[rep]; //순회용 노드 생성
            for(cnt=0;cnt<i;cnt++)curr= curr->next;

            ListNode *new=(ListNode *)malloc(sizeof(ListNode));//추가할 노드를 동적할당한다.

            new->coef = n;//계수
            new->exp = m;//차수
            curr ->next = new;
        }
        
        ListNode* print = *arr[rep]; //순회용 노드 생성
        print = print->next;
        while(print != NULL){
            if(print->exp > max) max = print->exp;

            numarr[print->exp][0] += print->coef;//계수
            print = print->next;
        }free(print);
        rep ++;
        
    }
    // printf("max = %d",max);
    // for(int i=max;i>=0;i--)printf(" %d %d\n",numarr[i][0],numarr[i][1]);
    for(int i=max;i>=0;i--) if(numarr[i][0] != 0) printf(" %d %d",numarr[i][0],numarr[i][1]);

    /**
    차수가 높은 순서대로 덧셈 진행

    각각의 연결리스트를 순회하고(max를 찾기위한 조건문을 수행한다.)
    해당 (차수==인덱스)에 계수를 저장(더)한다.

    이후 찾은 max부터 0까지 인덱스값을 읽는다.
    */
 
}