#include <stdio.h>
struct list {
  int pow,coef;
  struct list *next;
};
typedef struct list node;
typedef node *link;
void print_poly(link head) {
  link pt1;

  printf("the input polynomial ---> f(X)=");
  pt1=head;
  while (pt1 != NULL) {
    if (pt1->pow != 0) printf("%2dX%2d",pt1->coef,pt1->pow);
    else printf("%2d",pt1->coef);
    pt1=pt1->next; if (pt1 != NULL) printf("+");
  }
  printf("\n");
}

link create() {
  link head,pt1,pt2;
  int c,p,lastp;

  head=NULL;
  while (1) {
    printf("give me coefficient and power ?"); scanf("%d %d",&c,&p);
    if ((c == 0) && (p == 0)) break;
    if (head == NULL) lastp=p;
    if ((p <= lastp) && (c != 0)) {
      if ((head == NULL) || (p < lastp)) {
	pt2=(link)malloc(sizeof(node)); pt2->next=NULL;
	pt2->coef=c; pt2->pow=p; lastp=p;
	if (head == NULL) pt1=head=pt2;
	else pt1=pt1->next=pt2;
      }
      else pt2->coef+=c;
    }
    else printf("error input polynomial entry!!!\n");
  }
  return head;
}

int power(int x, int k) {
  int i,s=1;
  for (i=1; i<=k; i++) s*=x;
  return s;
}

void main() {
  int c,p,ff=0,tt,x;
  link h1,h2,h3,pp,p1,p2,p3;

  printf("give me the 1st polymonial -->"); p1=h1=create(); print_poly(h1);
  printf("give me the 2nd polymonial -->"); p2=h2=create(); print_poly(h2);
  p3=h3=(link)malloc(sizeof(node));
  while (1) {
    if (p1->pow > p2->pow) {
      if (ff == 0) { h3->pow=p1->pow; h3->coef=p1->coef; h3->next=NULL; ff=1; }
      else {
	pp=(link)malloc(sizeof(node)); pp->pow=p1->pow;
        pp->coef=p1->coef; p3=p3->next=pp;
      }
      p1=p1->next; if (p1 == NULL) break;
    }
    if (p1->pow < p2->pow) {
      if (ff == 0) { h3->pow=p2->pow; h3->coef=p2->coef; h3->next=NULL; ff=1; }
      else {
	pp=(link)malloc(sizeof(node)); pp->pow=p2->pow; pp->next=NULL;
        pp->coef=p2->coef; p3=p3->next=pp;
      }
      p2=p2->next; if (p2 == NULL) break;
    }
    else { /* p1->power = p2->power */
      tt=p1->coef+p2->coef;
      if (tt != 0) {
	if (ff == 0) { h3->pow=p1->pow; h3->coef=tt; h3->next=NULL; ff=1; }
        else {
	  pp=(link)malloc(sizeof(node)); pp->pow=p2->pow; pp->next=NULL;
          pp->coef=tt; p3=p3->next=pp;
        }
      }
      p2=p2->next; p1=p1->next; if (p1 == NULL) break; if (p2 == NULL) break;
    } /* else */
  }
  if (p1 == NULL)
    while (p2 != NULL) {
      pp=(link)malloc(sizeof(node)); pp->pow=p2->pow; pp->next=NULL;
      pp->coef=p2->coef; p2=p2->next; p3=p3->next=pp;
    }
  else if (p2 == NULL)
    while (p1 != NULL) {
      pp=(link)malloc(sizeof(node)); pp->pow=p1->pow; pp->next=NULL;
      pp->coef=p1->coef; p3=p3->next=pp; p1=p1->next;
    }
  print_poly(h3); p3=h3; tt=0;
  printf("give me the value to compute the polynomial--> "); scanf("%d",&x);
  while (p3 != NULL) {
   tt=tt+p3->coef*power(x,p3->pow); p3=p3->next;
  }
  printf("f(%d)=%d",x,tt);
}