logo标签列表

如何在C语言中进行多项式乘法？

c
3

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

为了实现这个功能，我应该怎么做？此外，在这个程序中如何使用 free() ？

#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");

}

 }
这里肯定有一些缺失的代码。请编辑您的问题，以便显示所有代码，并且格式正确。 - QuestionC
http://stackoverflow.com/q/11684058/971127 - BLUEPIXY
2
如果您将系数存储在数组中（例如 3x² + 2x - 1 可以表示为 double c[3] = {-1.0, 2.0, 3.0}），其中数组位置表示对应的指数，那么计算会更加便捷。您的乘积可以在一个嵌套循环中计算，如 r[i+j] += x[i] * y[j]。 - John Bode
3个回答
2

首先，您需要一种更有组织的方式来向多项式中添加项。仅仅将新系数添加到列表末尾是不够的。您需要在列表中搜索正确的位置并将多项式添加到那里。

// Adds coef * x ^ exp to poly.
void poly_add (poly ** add2me, int coef, int exp)
{
    poly ** p;

    // printf ("poly_add %d %d\n", coef, exp);

    // Advance p to the first node such that 
    //   *p is either the correct term or the subsequent term.
    for (p = add2me; *p != NULL && (*p)->exp > exp; p = &(*p)->next);

    // If *p is too small a coefficient / NULL,
    //   then it's pointing to the next term and you need to make a new node
    if (*p == NULL || (*p)->exp < exp)
    {
        poly * new_poly = malloc(sizeof(poly));
        new_poly->coef = coef;
        new_poly->exp = exp;
        new_poly->next = *p;
        *p = new_poly;
    }
    // Else *p is the correct exponent, in which case we add...
    else
    {
        (*p)->coef += coef;
    }
}

然后，只需要对你的乘法循环进行小修改即可使事情正常运行。
printf("Multiplying********\n");
po1 = head;
po2 = head2;
po3 = NULL;

while(po1||po2){
    po2 = head2;
    while(po1&&po2) {
        int new_coef = (po1->coef)*(po2->coef);
        int new_exp = (po1->exp)+(po2->exp);
        poly_add(&po3, new_coef, new_exp);

        po2 = po2->next;
    }
    po1 = po1->next;
}

补充说明： free()

每个多项式都是一个链表，因此您需要使用通用的列表销毁函数手动清除这些多项式...

void poly_free (poly * free_me)
{
  poly * next;
  for (; free_me != NULL; free_me = next)
  {
    next = free_me->next; // Safe because free_me != NULL
    free(free_me);
  }
}

在程序终止之前，为每个多项式调用该函数。像 valgrind 这样的工具可以帮助您知道是否存在内存泄漏。

2

进一步阐述我的评论...

如果你将系数存储在数组中，使得数组位置对应指数，那么管理系数将变得容易得多。例如，你可以将 3.0x2 - 2.0x + 1.0 表示为 

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

因此，二次多项式需要一个三元素数组，三次多项式需要一个四元素数组，以此类推。
将两个多项式相乘的过程变成了一个简单的嵌套循环：
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的答案是一个不错的选择。但我认为这种方法更加简单易懂。
1

您有两个选项：

  • 进行第二遍处理（例如按系数排序），并合并具有相同幂的系数。
  • 像在纸上一样进行乘法，计算列的总和（可以是滚动总和）。最简单的方法是先实现加法。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接