다항식 덧셈 프로그램 이중 연결리스트

#include <stdio.h>

#include <stdlib.h>

/* 

   double linked list 

   term adder

*/

typedef struct ListNode {

   int coef;

   int expon;

   struct ListNode *Llink;

   struct ListNode *Rlink;

}ListNode;

//typedef struct ListHeader {

//        int length;

//        ListNode *head;

//        ListNode *tail;

//}ListHeader;

//오류 처리 함수 

void error(char *message){

   fprintf(stderr, "%s\n", message);

   exit(1);

}

//초기화 함수 

void init(ListNode *phead){

   phead -> Llink = phead;

   phead -> Rlink = phead;

}

//plist는 연결리스트의 헤더를 가리키는 포인터, coef는 계수, expon은 지수 

void insert_node(ListNode *phead, int coef, int expon){

   ListNode *temp;

   temp = (ListNode *)malloc(sizeof(ListNode));

   if(temp == NULL) error("메모리 할당 에러");

   temp->coef = coef;

   temp->expon = expon;

   

   temp->Llink = phead;

   temp->Rlink = phead -> Rlink;

   phead->Rlink->Llink = temp;

   phead->Rlink = temp;

   //plist->length++;

}

//list3 = list1+ list2

void poly_add(ListNode *plist1, ListNode *plist2, ListNode *plist3){

   ListNode *a = plist1->Llink;

   ListNode *b = plist2->Llink;

   int sum;

   while(a != plist1 && b != plist2){

      if(a->expon == b->expon){

         sum = a->coef + b->coef;

         if(sum != 0)

            insert_node(plist3, sum, a->expon);

         a = a -> Llink;

         b = b -> Llink;

      }

      else if(a->expon > b->expon){

         insert_node(plist3, a->coef, a->expon);

         a = a->Llink;

      }

      else{

         insert_node(plist3, b->coef, b->expon);

         b = b->Llink; 

      } 

   }

   //a나 b중의 하나가 먼저 끝나게 되면 남아있는 항들을 모두 결과 다항식으로 복사 

   if(a != plist1){

      for( ; a != plist1 ; a = a->Llink){

         insert_node(plist3, a->coef, a->expon);

      }

   }

   if(b != plist2){

      for( ; b != plist2 ; b = b->Llink){

         insert_node(plist3, b->coef, b->expon);

      }

   }

}

//다항식 출력 함수 

void poly_print(ListNode *plist){

   ListNode *p;

   for(p = plist->Llink; p != plist; p = p->Llink){

      printf("%d %d\n", p->coef, p->expon);

   }

} 

//이중연결리스트의 응용테스트 프로그램

int main() {

   ListNode list1, list2, list3;

   //연결리스트의 초기화

   init(&list1);

   init(&list2);

   init(&list3);

   //다항식 1을 생성

   insert_node(&list1, 3, 12); 

   insert_node(&list1, 2, 8); 

   insert_node(&list1, 1, 0); 

   //다항식 2를 생성

   insert_node(&list2, 8, 12); 

   insert_node(&list2, -3, 10); 

   insert_node(&list2, 10, 6); 

   //다항식3 = 다항식1 + 다항식2

   poly_add(&list1, &list2, &list3);

   poly_print(&list3);

   //system("pause");

   return 0;

}