[数据结构]链式存储: 多项式求和

#include<stdio.h>
#include<stdlib.h>
// Code by Titan 2020-03-09

//定义链表结构
typedef struct LNode *PtrToNode;
struct LNode {
  double val; // 系数
  int num; // 次数(幂)
  PtrToNode next; // 指向下一个结点
};
typedef PtrToNode List;

//初始化链表 
List initList(int n) {
  //先初始化一个头结点
  List Head = (List)malloc(sizeof(struct LNode));
  List L = Head;
  double a[n]; //用于存放输入数据，反向存储;
  int b[n];
  for(int i=0; i<n; i++) {
    scanf("%lf %d",&a[i],&b[i]);
  }
  for(int i=1;i<n;i++){
    if(b[i-1]==b[i]){
      a[i-1]+=a[i];
      a[i]=0;
    }
  }
  for(int i=n-1; i>=0; i--) {
    //初始化一个结点
    if(a[i]==0){
      continue;
    }
    List Temp = (List)malloc(sizeof(struct LNode));
    Temp->val=a[i];
    Temp->num=b[i];
    Temp->next=NULL;
    L->next=Temp;
    L=Temp;
  }
  //返回头结点
  return Head;
}

// 多项式加法
List addition(List L1,List L2) {
  //初始化一个链表
  List L = (List)malloc(sizeof(struct LNode));
  List P = L;
  L1=L1->next;
  L2=L2->next;
  while(L1 && L2) {
    List Temp=(List)malloc(sizeof(struct LNode));
    if(L1->num == L2->num) {
      Temp->val=L1->val+L2->val;
      Temp->num=L1->num;
      L1=L1->next;
      L2=L2->next;
    } else if(L1->num > L2->num) {
      Temp->val=L1->val;
      Temp->num=L1->num;
      L1=L1->next;
    } else {
      Temp->val=L2->val;
      Temp->num=L2->num;
      L2=L2->next;
    }
    P->next=Temp;
    P=Temp;
  }
  // 把剩余部分接到后面;
  if(L1) {
    P->next=L1;
  } else {
    P->next=L2;
  }
  return L;
}
// 多项式减法 将第二个链表取负数即可
List subtraction(List L1,List L2) {
  List NewL = L2->next;
  while(NewL) {
    NewL->val=-NewL->val;
    NewL=NewL->next;
  }
  List L=addition(L1,L2);
  return L;
}
void printList(List L) {
  if(L->next) {
    L=L->next;
    if(L->val==1.0){
      printf("X^%d",L->num);
    }else if(L->val==-1.0){
      printf("-X^%d",L->num);
    }else if(L->val!=0){
      printf("%gX^%d",L->val,L->num);
    }else{
      printf("0");
    }

  }
  while(L->next) {
    L=L->next;
    if(L->val==1.0) {
      if(L->num==1) {
        printf("+X",L->num);
      } else if(L->num==0) {
        printf("+1");
      } else {
        printf("+X^%d",L->num);
      }
    } else if(L->val==-1.0) {
      if(L->num==1) {
        printf("-X",L->num);
      } else if(L->num==0) {
        printf("-1");
      } else {
        printf("-X^%d",L->num);
      }
    } else if(L->val>1e-10) {
      if(L->num==1) {
        printf("+%gX",L->val,L->num);
      } else if(L->num==0) {
        printf("+%g",L->val);
      } else {
        printf("+%gX^%d",L->val,L->num);
      }
    } else if(L->val<-1e-10) {
      if(L->num==1) {
        printf("%gX",L->val,L->num);
      } else if(L->num==0) {
        printf("%g",L->val);
      } else {
        printf("%gX^%d",L->val,L->num);
      }
    }
  }
  printf("\n");
}

int main(void) {
  int n;
  scanf("%d",&n);
  List L1 =initList(n);
  scanf("%d",&n);
  List L2=initList(n);
  printf("输入的第一个多项式是:");
  printList(L1);
  printf("输入的第二个多项式是:");
  printList(L2);
  List L=(List)malloc(sizeof(struct LNode));
  printf("请输入运算符:");
  char op;
  getchar();
  scanf("%c",&op);
  if(op=='+') {
    L=addition(L1,L2);
  } else if(op=='-') {
    L=subtraction(L1,L2);
  } else {
    printf("输入的运算符有误");
    return -1;
  }
  printf("计算后的多项式结果为:");
  printList(L);
  free(L);

}