[数据结构与算法]链表应用--多项式相乘

polynomialList.h

#ifndef POLYNOMIAL_LIST_H
#define POLYNOMIAL_LIST_H
#define maxDegree 5000
typedef struct Polynomial
{
  int CoeffArray[maxDegree + 1];
  int highPower;
} * polynomial;

void zeroPolynomial(polynomial poly);
void addPolynomial(const polynomial poly1, const polynomial poly2, polynomial polySum);
void multiPolynomial(const polynomial poly1, const polynomial poly2, polynomial polyMulti);
void error(const char []);
polynomial generatePoly(int highPower);
void displayPolynomial(const polynomial poly);
int max(int a, int b);
#endif

polynomialList.c

#include "polynomialList.h"
#include <stdio.h>
#include <stdlib.h>
int max(int a, int b)
{
  if( a > b)
    return a;
  else
    return b;
}
void error(const char content[])
{
  printf(content);
  fflush(stdout);
}

void zeroPolynomial(polynomial poly)
{
  int i = 0;

  for (int i = 0; i < maxDegree; i++)
  {
    poly->CoeffArray[i] = 0;
  }
  poly->highPower = 0;
}

void addPolynomial(const polynomial poly1, const polynomial poly2, polynomial polySum)
{
  zeroPolynomial(polySum);

  for (int i = 0; i < maxDegree; i++)
  {
    polySum->CoeffArray[i] = poly1->CoeffArray[i] + poly2->CoeffArray[i];
  }

  polySum->highPower = max(poly1->highPower, poly2->highPower);
}

void multiPolynomial(const polynomial poly1, const polynomial poly2, polynomial polyMulti)
{
  zeroPolynomial(polyMulti);
  polyMulti->highPower = poly1->highPower + poly2->highPower;

  if (polyMulti->highPower > maxDegree)
  {
    error("两个多项式相乘，最高幂大于 maxDegree \n");
  }
  else
  {
    for (int i = 0; i < maxDegree; i++)
    {
      for (int j = 0; j < maxDegree; j++)
      {
        polyMulti->CoeffArray[i + j] += poly1->CoeffArray[i] * poly2->CoeffArray[j];
      }
    }
  }
}

polynomial generatePoly(int highPower)
{
  if (highPower <= maxDegree)
  {
    polynomial poly = (polynomial)malloc(sizeof(struct Polynomial));
    zeroPolynomial(poly);

    for (int i = 0; i <= highPower; i++)
    {
      poly->CoeffArray[i] = random() % 10;
    }
    poly->highPower = highPower;

    return poly;
  }
  else
  {
    error("参数highPower太大了 \n");
    return NULL;
  }
}


void displayPolynomial(const polynomial poly)
{
  printf("polynomial is : ");
  for(int i = poly->highPower; i >= 0; i--)
  {
    if(poly->CoeffArray[i] == 0)
    {
      continue;
    }
    if (i != 0)
      printf("%d*X^%d + ", poly->CoeffArray[i], i);
    else
      printf("%d \n", poly->CoeffArray[i]);
  }
}

polyListTest.c

#include"polynomialList.c"

int main()
{
  printf("generate polynomial: \n");
  polynomial poly1 = generatePoly(8);
  displayPolynomial(poly1);

  polynomial poly2 = generatePoly(8);
  displayPolynomial(poly2);

  printf("\n add: \n");
  polynomial polyAdd = (polynomial)malloc(sizeof(struct Polynomial));
  addPolynomial(poly1, poly2, polyAdd);
  displayPolynomial(polyAdd);

  printf("\n multi: \n");
  polynomial polyMulti = (polynomial)malloc(sizeof(struct Polynomial));
  multiPolynomial(poly1, poly2, polyMulti);
  displayPolynomial(polyMulti);

  return 0;
}