7-2 一元多项式的乘法与加法运算 题解

#include <stdio.h>
#include <stdlib.h>

typedef struct LNode {
  int a;  // 系数
  int n;  // 指数
  struct LNode *next;
} LNode, *LinkList;
typedef struct {
  LNode *head, *tail;
} Polynomial;

void PushBack(Polynomial *p, int a, int n);
void CreatePloyn(Polynomial *p, int k);
void DelFirst(LNode *head, LNode *q);
void CopyPloyn(Polynomial p, Polynomial *q, int a, int n);
void AddPloyn(Polynomial *pa, Polynomial *pb);  // p1+=p2 and free(p2)
Polynomial* MultiplyPolyn(Polynomial *pa, Polynomial *pb);
void PrintPloyn(Polynomial p) {
  LNode *cur = p.head->next;
  if(!cur)
    printf("0 0");
  else
    while (cur) {
      printf("%d %d", cur->a, cur->n);
      cur = cur->next;
      if (cur) printf(" ");
    }
  printf("\n");
}
int main() {
  int ka, kb;
  Polynomial pa, pb;
  scanf("%d", &ka);
  CreatePloyn(&pa, ka);
  scanf("%d", &kb);
  CreatePloyn(&pb, kb);
  PrintPloyn(*MultiplyPolyn(&pa, &pb));
  AddPloyn(&pa, &pb);
  PrintPloyn(pa);
  return 0;
}
void PushBack(Polynomial *p, int a, int n) {
  LNode *node = (LNode *)malloc(sizeof(LNode));
  node->a = a;
  node->n = n;
  p->tail->next = node;
  p->tail = node;
}
void CreatePloyn(Polynomial *p, int k) {
  LNode *node = (LNode *)malloc(sizeof(LNode));
  int a, n;
  p->head = p->tail = node;
  for (int i = 1; i <= k; i++) {
    scanf("%d", &a);
    scanf("%d", &n);
    PushBack(p, a, n);
  }
}
void DelFirst(LNode *head, LNode *q) {
  q = head->next;
  head->next = q->next;
}
void CopyPloyn(Polynomial p, Polynomial *q, int a, int n) {
  LNode *node = (LNode *)malloc(sizeof(LNode));
  q->head = q->tail = node;
  LNode *cur = p.head->next;
  while (cur) {
    if (a * cur->a) PushBack(q, a * cur->a, n + cur->n);
    cur = cur->next;
  }
}
void AddPloyn(Polynomial *pa, Polynomial *pb) {
  LNode *ha = pa->head, *hb = pb->head;  // head position
  LNode *ca = ha->next, *cb = hb->next;  // current position
  int na, nb, sum;
  while (ca && cb) {
    na = ca->n;
    nb = cb->n;
    if (na > nb) {
      ha = ca;        // a's head go to cur
      ca = ca->next;  // a's cur go on
    }
    else if (na < nb) {
      DelFirst(hb, cb);
      cb->next = ca;  // insert cb to ha's back
      // or cb->next = ha->next;
      ha->next = cb;
      ha = ha->next;  // a's head go on
      cb = hb->next;  // b's cur go on
    }
    else if (na == nb) {
      sum = ca->a + cb->a;
      if (sum) {
        ca->a = sum;
        ha = ca;  // a's head go to cur
      } else {
        DelFirst(ha, ca);
        free(ca);
      }
      DelFirst(hb, cb);
      free(cb);
      cb = hb->next;  // b's cur go on
      ca = ha->next;  // a's cur go on
    }
  }
  LNode *p=ha;
  if (cb) {
    while (p->next) p = p->next;
    p->next = cb;
    pa->tail = pb->tail;
  }
}
Polynomial* MultiplyPolyn(Polynomial *pa, Polynomial *pb) {
  LNode *cur = pb->head->next, *node = (LNode *)malloc(sizeof(LNode));
  Polynomial t;
  static Polynomial p;
  p.head = p.tail = node;
  while (cur) {
    CopyPloyn(*pa, &t, cur->a, cur->n);
    AddPloyn(&p, &t);
    cur = cur->next;
  }
  return &p;
}