c - 如何在 C 中乘以多项式？

Question

我希望这段代码有意义......我创建了两个多项式并尝试将它们相乘。问题是我不知道我应该怎么做才能正确地将它们相乘。该程序将多项式相乘，将结果存储到另一个多项式，但不添加具有相同幂的系数。

What should I do in order to do that?? Also how should I use free() in this program?

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

typedef struct poly {
  int coef;
  int exp;
  struct poly *next;
} poly;

int main(void) {
  poly * po1, *head, *po2, *head2, *po3, *head3 = NULL;
  int sel, c = 1;

  head = NULL;
  printf(
      "\nInsert elements for the first polynomial from the biggest to the smallest power of x. (Enter a power of zero (0) to stop)\n");
  while (1) {
    po1 = (poly *) malloc(sizeof(poly));
    printf("Give number: ");
    scanf("%d", &po1->coef);
    printf("Give power of x: ");
    scanf("%d", &po1->exp);
    po1->next = head;
    head = po1;
    if (po1->exp == 0) break;
  }

  head2 = NULL;
  printf(
      "\nInsert elements for the second polynomial from the biggest to the smallest power of x. (Enter a power of zero (0) to stop)\n");
  while (1) {
    po2 = (poly *) malloc(sizeof(poly));
    printf("Give number: ");
    scanf("%d", &po2->coef);
    printf("Give power of x: ");
    scanf("%d", &po2->exp);
    po2->next = head2;
    head2 = po2;
    if (po2->exp == 0) break;
  }

  po1 = head;
  po2 = head2;

  printf("Multiplying********\n");
  po1 = head;
  po2 = head2;
  while (po1 || po2) {
    po2 = head2;
    while (po1 && po2) {
      po3 = (poly *) malloc(sizeof(poly));
      po3->coef = (po1->coef) * (po2->coef);
      po3->exp = (po1->exp) + (po2->exp);
      po3->next = head3;
      head3 = po3;
      po2 = po2->next;
    }
    po1 = po1->next;
  }
  while (po3) {
    printf("%+d(x^%d)", po3->coef, po3->exp);
    po3 = po3->next;
  }
  printf("\n");

}

 }

Answer 1

扩展我的评论...

如果将系数存储在数组中，使数组位置与指数相对应，那么管理系数的时间将会远。例如，您将代表 3.0x<sup>2</sup> - 2.0x + 1.0作为

double c[3] = { 1.0, -2.0, 3.0 };

因此，2 次多项式需要 3 元素数组，3 次多项式需要 4 元素数组，等等。

将两个多项式相乘就变成了一个简单的嵌套循环:

void polymul( double *x, size_t xsize, double *y, size_t ysize, double *r, size_t rsize )
{
  memset( r, 0, sizeof *r * rsize );

  for ( size_t i = 0; i < xsize; i++ )
  {
    for ( size_t j = 0; j < ysize; j++ )
    {
      r[i + j] += x[i] * y[j];
    }
  }
}

如果将 I/O 和内存管理与计算分开，生活也会变得更简单。如果你知道你的输入多项式有多大，你就知道输出多项式需要有多大:

double *x, *y;
size_t xsize, ysize;

getcoeffs( &x, &xsize );
getcoeffs( &y, &ysize );

size_t rsize = xsize + ysize - 1;
double *r = malloc( sizeof *r * rsize );

polymul( x, xsize, y, ysize, r, rsize );
...
free( r );
free( x );
free( y );

如果您致力于使用结构列表方法，那么 QuestionC 的答案是一个很好的答案。我只是认为这种方法要简单得多。