使用列表在 C 中多项式的乘法

Question

我正在使用列表来实现多项式的乘法。我的代码是：

typedef struct node *node_ptr;
typedef struct node
{
    unsigned int power;
    int coeff;
    node_ptr next;
}POLY;
typedef node_ptr polynomial; 

void mult_polynomial(polynomial poly1, polynomial poly2, polynomial poly_mult)
{
    assert(!is_null(poly1) && !is_null(poly2) && is_null(poly_mult));
    node_ptr p1 = poly1->next;
    node_ptr p2;
    node_ptr p3;
    node_ptr tmp, cell;

    while (p1) {
        p2 = poly2->next;
        while (p2) {
            p3 = poly_mult;
            cell = p3->next;
            tmp = (node_ptr)malloc(sizeof(struct node));
            tmp->power = p1->power + p2->power;
            tmp->coeff = p1->coeff * p2->coeff;
            tmp->next = NULL;
            if (!cell)
                p3->next = tmp;
            else { 
                if (cell->power == tmp->power) {
                    cell->coeff += tmp->coeff;
                    free(tmp);   
                } else if (cell->power < tmp->power) {
                    p3->next = tmp;
                    tmp->next = cell;
                } else if (cell->power > tmp->power) {
                    while (cell->power > tmp->power) {
                        if(!cell->next || cell->next->power < tmp->power) {
                            cell->next = tmp;
                            break; 
                        } else if (cell->next->power == tmp->power) {
                            cell->next->coeff += tmp->coeff;
                            break;
                        }
                        p3 = cell;
                        cell = p3->next;
                    }
                }
            }
            p2 = p2->next;
        }
        p1 = p1->next;
    }
}

不过好像太多余了；如何简化？

Answer 1

这是我的解决方案。它基本上是一个完整的重写——虽然使用的结构只是重命名但在结构上等同于你拥有的。

函数 add_term() 被证明是至关重要的——它是 mult_polynomial() 中部分函数的变体，但它也适用于 add_polynomial() 和 sub_polynomial() — 一个因素表明它是一个有用的抽象。请注意，mult_polynomial() 本身非常简单紧凑，因此 add_polynomial() 和 sub_polynomial() 都不复杂。

我对 add_term() 中的代码不是很满意（有太多特殊情况），但我相信它的工作相当不错。您最终可以得到一个多项式，其中有许多项的系数为 0；该代码不会删除此类条款，但可以（应该）对其进行升级以这样做。因此，打印代码必须跳过这些项——并且有一个特殊情况来处理所有项为零（当然，它打印 0）。

另外，题中mult_polynomial()的设计不合理。如果你有void mult_polynomial(polynomial *p1, polynomial *p2, polynomial *p3)，你无法从函数中获取p3中的新数据。选项是使用 polynomial **p3 或 return 新多项式 — 此代码 return 是新值。

而且，正如评论中已经提到的，通常最好不要将 typedef 用于数据指针（函数指针是另一回事）。您可以在 Is it a good idea to typedef pointers 找到更多信息。我最终得到了一种多项式结构，它与多项式中一项的结构相同。（测试代码使用一对结构，term 和 termlist 来描述用于测试目的的多项式。它们使生活更轻松。测试代码数量适中。add_polynomial()和 sub_polynomial() 功能在 10 分钟内完成，包括修复 0 多项式的打印，这证明了 add_term() 功能的实用性。

print_polynomial() 函数很重要也很有用。它还必须处理一些繁琐的特殊情况（负系数、第一个负系数、零系数、一的幂和零的幂）。可以说它应该被概括为允许指定变量名；它是 hard-coded 和 x。可能有一些更简单的函数试图逃逸 — 一种可能性是 print_term() 函数可以在其他地方使用并在 print_polynomial() 中调用。当然，处理棘手的特殊情况需要棘手的沟通。

仅供参考：我将所有函数（main() 除外）定义为 static，除非有第二个引用它们的源文件和一个声明它们的 header 文件。显然，如果代码要被重用，其中一些函数将变得可公开访问，然后将被制作成 extern（非 static）并在 header 中声明。类型的详细信息不会在 header 中； typedef struct polynomial polynomial; 会在那里，但仅此而已。该定义将隐藏在实现文件中。这将是一个 不透明类型 。 add_term() 和 make_term() 等函数将保留为 static 函数。

该代码使用 C99 指定的初始值设定项和复合文字。它可以使用 C89/C90 代码编写，但会更难 and/or 更混乱。不一定非常难，但是…

话不多说，下面是代码（很长）：

/* SO 4313-7847 */
#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include "emalloc.h"

typedef struct polynomial polynomial;

struct polynomial
{
    unsigned int power;
    int          coeff;
    polynomial  *next;
};

static void print_polynomial(const char *tag, const polynomial *poly);

static polynomial *make_term(unsigned int power, int coeff, polynomial *next)
{
    polynomial *new_term = MALLOC(sizeof(*new_term));
    new_term->power = power;
    new_term->coeff = coeff;
    new_term->next  = next;
    return new_term;
}

static polynomial *add_term(polynomial *poly, unsigned int power, int coeff)
{
    if (coeff == 0)
        return poly;
    if (poly == NULL)
        return make_term(power, coeff, NULL);

    /* Find where this term goes */
    polynomial *term = poly;
    polynomial *prev = NULL;
    while (term != NULL && term->power > power)
    {
        prev = term;
        term = term->next;
    }

    if (term != NULL && term->power == power)
    {
        term->coeff += coeff;
        /* Eliminate zero terms here */
    }
    else
    {
        assert(term == NULL || term->power < power);
        polynomial *new_term = make_term(power, coeff, term);
        if (prev == NULL)
            poly = new_term;
        else
            prev->next = new_term;
    }
    return poly;
}

static polynomial *mult_polynomial(polynomial *poly1, polynomial *poly2)
{
    assert(poly1 != NULL && poly2 != NULL);
    polynomial *result = NULL;

    for (polynomial *p1 = poly1; p1 != NULL; p1 = p1->next)
    {
        for (polynomial *p2 = poly2; p2 != NULL; p2 = p2->next)
            result = add_term(result, p1->power + p2->power, p1->coeff * p2->coeff);
    }
    return result;
}

static polynomial *add_polynomial(polynomial *poly1, polynomial *poly2)
{
    assert(poly1 != NULL && poly2 != NULL);
    polynomial *result = NULL;

    for (polynomial *p1 = poly1; p1 != NULL; p1 = p1->next)
        result = add_term(result, p1->power, p1->coeff);
    for (polynomial *p2 = poly2; p2 != NULL; p2 = p2->next)
        result = add_term(result, p2->power, p2->coeff);
    return result;
}

static polynomial *sub_polynomial(polynomial *poly1, polynomial *poly2)
{
    assert(poly1 != NULL && poly2 != NULL);
    polynomial *result = NULL;

    for (polynomial *p1 = poly1; p1 != NULL; p1 = p1->next)
        result = add_term(result, p1->power, p1->coeff);
    for (polynomial *p2 = poly2; p2 != NULL; p2 = p2->next)
        result = add_term(result, p2->power, -p2->coeff);
    return result;
}

static void print_polynomial(const char *tag, const polynomial *poly)
{
    int printed = 0;
    printf("%s:", tag);
    char sign = ' ';
    while (poly != NULL)
    {
        int coeff = poly->coeff;
        if (coeff != 0)
        {
            if (sign != ' ' && coeff < 0)
            {
                sign = '-';
                coeff = -coeff;
            }
            if (poly->power == 0)
                printf(" %c %d", sign, coeff);
            else if (poly->power == 1)
                printf(" %c %dx", sign, coeff);
            else
                printf(" %c %dx^%u", sign, coeff, poly->power);
            printed++;
        }
        poly = poly->next;
        sign = '+';
    }
    if (printed == 0)
        printf("   0");
    putchar('\n');
    fflush(stdout);
}

static void free_polynomial(polynomial *poly)
{
    while (poly != NULL)
    {
        polynomial *next = poly->next;
        free(poly);
        poly = next;
    }
}

typedef struct term
{
    unsigned int power;
    int coeff;
} term;

typedef struct termlist
{
    int n_terms;
    term *terms;
} termlist;

static polynomial *make_polynomial(termlist *terms)
{
    polynomial *poly = 0;
    for (int i = 0; i < terms->n_terms; i++)
    {
        printf("Term: %dx^%u\n", terms->terms[i].coeff, terms->terms[i].power);
        fflush(stdout);
        poly = add_term(poly, terms->terms[i].power, terms->terms[i].coeff);
    }
    return poly;
}

int main(void)
{
    termlist p1[] =
    {
        { .n_terms = 4, .terms = (term[]){ { 3, 2 }, { 2,  1 }, { 1,  4 }, { 0, -9 } } },
        { .n_terms = 3, .terms = (term[]){ { 2, 3 }, { 1, -4 }, { 0,  8 } } },
        { .n_terms = 3, .terms = (term[]){ { 1, 5 }, { 0,  3 }, { 2, -4 } } },
        { .n_terms = 2, .terms = (term[]){ { 4, 5 }, { 0, -5 } } },
        { .n_terms = 4, .terms = (term[]){ { 3, 2 }, { 2,  1 }, { 1,  4 }, { 2, -9 } } },
    };
    enum { NUM_POLYS = sizeof(p1) / sizeof(p1[0]) };
    polynomial *poly[NUM_POLYS] = { 0 };

    for (int i = 0; i < NUM_POLYS; i++)
    {
        poly[i] = make_polynomial(&p1[i]);
        print_polynomial("Building", poly[i]);
    }

    printf("Checking:\n");
    for (int i = 0; i < NUM_POLYS; i++)
        print_polynomial("Next", poly[i]);
    putchar('\n');

    printf("Multiplying polynomials:\n");
    for (int i = 0; i < NUM_POLYS; i++)
    {
        for (int j = 0; j < NUM_POLYS; j++)
        {
            print_polynomial("Term 1", poly[i]);
            print_polynomial("Term 2", poly[j]);
            polynomial *prod = mult_polynomial(poly[i], poly[j]);
            print_polynomial("Product", prod);
            free_polynomial(prod);
        }
        putchar('\n');
    }

    printf("Adding polynomials:\n");
    for (int i = 0; i < NUM_POLYS; i++)
    {
        for (int j = 0; j < NUM_POLYS; j++)
        {
            print_polynomial("Term 1", poly[i]);
            print_polynomial("Term 2", poly[j]);
            polynomial *sum = add_polynomial(poly[i], poly[j]);
            print_polynomial("Sum", sum);
            free_polynomial(sum);
        }
        putchar('\n');
    }

    printf("Subtracting polynomials:\n");
    for (int i = 0; i < NUM_POLYS; i++)
    {
        for (int j = 0; j < NUM_POLYS; j++)
        {
            print_polynomial("Term 1", poly[i]);
            print_polynomial("Term 2", poly[j]);
            polynomial *diff = sub_polynomial(poly[i], poly[j]);
            print_polynomial("Difference", diff);
            free_polynomial(diff);
        }
        putchar('\n');
    }

    for (int i = 0; i < NUM_POLYS; i++)
        free_polynomial(poly[i]);

    return 0;
}

输出分为三个部分，因此您可以看到测试的乘法、加法和减法部分的开始：

Term: 2x^3
Term: 1x^2
Term: 4x^1
Term: -9x^0
Building:   2x^3 + 1x^2 + 4x - 9
Term: 3x^2
Term: -4x^1
Term: 8x^0
Building:   3x^2 - 4x + 8
Term: 5x^1
Term: 3x^0
Term: -4x^2
Building:   -4x^2 + 5x + 3
Term: 5x^4
Term: -5x^0
Building:   5x^4 - 5
Term: 2x^3
Term: 1x^2
Term: 4x^1
Term: -9x^2
Building:   2x^3 - 8x^2 + 4x
Checking:
Next:   2x^3 + 1x^2 + 4x - 9
Next:   3x^2 - 4x + 8
Next:   -4x^2 + 5x + 3
Next:   5x^4 - 5
Next:   2x^3 - 8x^2 + 4x

乘法：

Multiplying polynomials:
Term 1:   2x^3 + 1x^2 + 4x - 9
Term 2:   2x^3 + 1x^2 + 4x - 9
Product:   4x^6 + 4x^5 + 17x^4 - 28x^3 - 2x^2 - 72x + 81
Term 1:   2x^3 + 1x^2 + 4x - 9
Term 2:   3x^2 - 4x + 8
Product:   6x^5 - 5x^4 + 24x^3 - 35x^2 + 68x - 72
Term 1:   2x^3 + 1x^2 + 4x - 9
Term 2:   -4x^2 + 5x + 3
Product:   -8x^5 + 6x^4 - 5x^3 + 59x^2 - 33x - 27
Term 1:   2x^3 + 1x^2 + 4x - 9
Term 2:   5x^4 - 5
Product:   10x^7 + 5x^6 + 20x^5 - 45x^4 - 10x^3 - 5x^2 - 20x + 45
Term 1:   2x^3 + 1x^2 + 4x - 9
Term 2:   2x^3 - 8x^2 + 4x
Product:   4x^6 - 14x^5 + 8x^4 - 46x^3 + 88x^2 - 36x

Term 1:   3x^2 - 4x + 8
Term 2:   2x^3 + 1x^2 + 4x - 9
Product:   6x^5 - 5x^4 + 24x^3 - 35x^2 + 68x - 72
Term 1:   3x^2 - 4x + 8
Term 2:   3x^2 - 4x + 8
Product:   9x^4 - 24x^3 + 64x^2 - 64x + 64
Term 1:   3x^2 - 4x + 8
Term 2:   -4x^2 + 5x + 3
Product:   -12x^4 + 31x^3 - 43x^2 + 28x + 24
Term 1:   3x^2 - 4x + 8
Term 2:   5x^4 - 5
Product:   15x^6 - 20x^5 + 40x^4 - 15x^2 + 20x - 40
Term 1:   3x^2 - 4x + 8
Term 2:   2x^3 - 8x^2 + 4x
Product:   6x^5 - 32x^4 + 60x^3 - 80x^2 + 32x

Term 1:   -4x^2 + 5x + 3
Term 2:   2x^3 + 1x^2 + 4x - 9
Product:   -8x^5 + 6x^4 - 5x^3 + 59x^2 - 33x - 27
Term 1:   -4x^2 + 5x + 3
Term 2:   3x^2 - 4x + 8
Product:   -12x^4 + 31x^3 - 43x^2 + 28x + 24
Term 1:   -4x^2 + 5x + 3
Term 2:   -4x^2 + 5x + 3
Product:   16x^4 - 40x^3 + 1x^2 + 30x + 9
Term 1:   -4x^2 + 5x + 3
Term 2:   5x^4 - 5
Product:   -20x^6 + 25x^5 + 15x^4 + 20x^2 - 25x - 15
Term 1:   -4x^2 + 5x + 3
Term 2:   2x^3 - 8x^2 + 4x
Product:   -8x^5 + 42x^4 - 50x^3 - 4x^2 + 12x

Term 1:   5x^4 - 5
Term 2:   2x^3 + 1x^2 + 4x - 9
Product:   10x^7 + 5x^6 + 20x^5 - 45x^4 - 10x^3 - 5x^2 - 20x + 45
Term 1:   5x^4 - 5
Term 2:   3x^2 - 4x + 8
Product:   15x^6 - 20x^5 + 40x^4 - 15x^2 + 20x - 40
Term 1:   5x^4 - 5
Term 2:   -4x^2 + 5x + 3
Product:   -20x^6 + 25x^5 + 15x^4 + 20x^2 - 25x - 15
Term 1:   5x^4 - 5
Term 2:   5x^4 - 5
Product:   25x^8 - 50x^4 + 25
Term 1:   5x^4 - 5
Term 2:   2x^3 - 8x^2 + 4x
Product:   10x^7 - 40x^6 + 20x^5 - 10x^3 + 40x^2 - 20x

Term 1:   2x^3 - 8x^2 + 4x
Term 2:   2x^3 + 1x^2 + 4x - 9
Product:   4x^6 - 14x^5 + 8x^4 - 46x^3 + 88x^2 - 36x
Term 1:   2x^3 - 8x^2 + 4x
Term 2:   3x^2 - 4x + 8
Product:   6x^5 - 32x^4 + 60x^3 - 80x^2 + 32x
Term 1:   2x^3 - 8x^2 + 4x
Term 2:   -4x^2 + 5x + 3
Product:   -8x^5 + 42x^4 - 50x^3 - 4x^2 + 12x
Term 1:   2x^3 - 8x^2 + 4x
Term 2:   5x^4 - 5
Product:   10x^7 - 40x^6 + 20x^5 - 10x^3 + 40x^2 - 20x
Term 1:   2x^3 - 8x^2 + 4x
Term 2:   2x^3 - 8x^2 + 4x
Product:   4x^6 - 32x^5 + 80x^4 - 64x^3 + 16x^2

加法：

Adding polynomials:
Term 1:   2x^3 + 1x^2 + 4x - 9
Term 2:   2x^3 + 1x^2 + 4x - 9
Sum:   4x^3 + 2x^2 + 8x - 18
Term 1:   2x^3 + 1x^2 + 4x - 9
Term 2:   3x^2 - 4x + 8
Sum:   2x^3 + 4x^2 - 1
Term 1:   2x^3 + 1x^2 + 4x - 9
Term 2:   -4x^2 + 5x + 3
Sum:   2x^3 - 3x^2 + 9x - 6
Term 1:   2x^3 + 1x^2 + 4x - 9
Term 2:   5x^4 - 5
Sum:   5x^4 + 2x^3 + 1x^2 + 4x - 14
Term 1:   2x^3 + 1x^2 + 4x - 9
Term 2:   2x^3 - 8x^2 + 4x
Sum:   4x^3 - 7x^2 + 8x - 9

Term 1:   3x^2 - 4x + 8
Term 2:   2x^3 + 1x^2 + 4x - 9
Sum:   2x^3 + 4x^2 - 1
Term 1:   3x^2 - 4x + 8
Term 2:   3x^2 - 4x + 8
Sum:   6x^2 - 8x + 16
Term 1:   3x^2 - 4x + 8
Term 2:   -4x^2 + 5x + 3
Sum:   -1x^2 + 1x + 11
Term 1:   3x^2 - 4x + 8
Term 2:   5x^4 - 5
Sum:   5x^4 + 3x^2 - 4x + 3
Term 1:   3x^2 - 4x + 8
Term 2:   2x^3 - 8x^2 + 4x
Sum:   2x^3 - 5x^2 + 8

Term 1:   -4x^2 + 5x + 3
Term 2:   2x^3 + 1x^2 + 4x - 9
Sum:   2x^3 - 3x^2 + 9x - 6
Term 1:   -4x^2 + 5x + 3
Term 2:   3x^2 - 4x + 8
Sum:   -1x^2 + 1x + 11
Term 1:   -4x^2 + 5x + 3
Term 2:   -4x^2 + 5x + 3
Sum:   -8x^2 + 10x + 6
Term 1:   -4x^2 + 5x + 3
Term 2:   5x^4 - 5
Sum:   5x^4 - 4x^2 + 5x - 2
Term 1:   -4x^2 + 5x + 3
Term 2:   2x^3 - 8x^2 + 4x
Sum:   2x^3 - 12x^2 + 9x + 3

Term 1:   5x^4 - 5
Term 2:   2x^3 + 1x^2 + 4x - 9
Sum:   5x^4 + 2x^3 + 1x^2 + 4x - 14
Term 1:   5x^4 - 5
Term 2:   3x^2 - 4x + 8
Sum:   5x^4 + 3x^2 - 4x + 3
Term 1:   5x^4 - 5
Term 2:   -4x^2 + 5x + 3
Sum:   5x^4 - 4x^2 + 5x - 2
Term 1:   5x^4 - 5
Term 2:   5x^4 - 5
Sum:   10x^4 - 10
Term 1:   5x^4 - 5
Term 2:   2x^3 - 8x^2 + 4x
Sum:   5x^4 + 2x^3 - 8x^2 + 4x - 5

Term 1:   2x^3 - 8x^2 + 4x
Term 2:   2x^3 + 1x^2 + 4x - 9
Sum:   4x^3 - 7x^2 + 8x - 9
Term 1:   2x^3 - 8x^2 + 4x
Term 2:   3x^2 - 4x + 8
Sum:   2x^3 - 5x^2 + 8
Term 1:   2x^3 - 8x^2 + 4x
Term 2:   -4x^2 + 5x + 3
Sum:   2x^3 - 12x^2 + 9x + 3
Term 1:   2x^3 - 8x^2 + 4x
Term 2:   5x^4 - 5
Sum:   5x^4 + 2x^3 - 8x^2 + 4x - 5
Term 1:   2x^3 - 8x^2 + 4x
Term 2:   2x^3 - 8x^2 + 4x
Sum:   4x^3 - 16x^2 + 8x

减法：

Subtracting polynomials:
Term 1:   2x^3 + 1x^2 + 4x - 9
Term 2:   2x^3 + 1x^2 + 4x - 9
Difference:   0
Term 1:   2x^3 + 1x^2 + 4x - 9
Term 2:   3x^2 - 4x + 8
Difference:   2x^3 - 2x^2 + 8x - 17
Term 1:   2x^3 + 1x^2 + 4x - 9
Term 2:   -4x^2 + 5x + 3
Difference:   2x^3 + 5x^2 - 1x - 12
Term 1:   2x^3 + 1x^2 + 4x - 9
Term 2:   5x^4 - 5
Difference:   -5x^4 + 2x^3 + 1x^2 + 4x - 4
Term 1:   2x^3 + 1x^2 + 4x - 9
Term 2:   2x^3 - 8x^2 + 4x
Difference: + 9x^2 - 9

Term 1:   3x^2 - 4x + 8
Term 2:   2x^3 + 1x^2 + 4x - 9
Difference:   -2x^3 + 2x^2 - 8x + 17
Term 1:   3x^2 - 4x + 8
Term 2:   3x^2 - 4x + 8
Difference:   0
Term 1:   3x^2 - 4x + 8
Term 2:   -4x^2 + 5x + 3
Difference:   7x^2 - 9x + 5
Term 1:   3x^2 - 4x + 8
Term 2:   5x^4 - 5
Difference:   -5x^4 + 3x^2 - 4x + 13
Term 1:   3x^2 - 4x + 8
Term 2:   2x^3 - 8x^2 + 4x
Difference:   -2x^3 + 11x^2 - 8x + 8

Term 1:   -4x^2 + 5x + 3
Term 2:   2x^3 + 1x^2 + 4x - 9
Difference:   -2x^3 - 5x^2 + 1x + 12
Term 1:   -4x^2 + 5x + 3
Term 2:   3x^2 - 4x + 8
Difference:   -7x^2 + 9x - 5
Term 1:   -4x^2 + 5x + 3
Term 2:   -4x^2 + 5x + 3
Difference:   0
Term 1:   -4x^2 + 5x + 3
Term 2:   5x^4 - 5
Difference:   -5x^4 - 4x^2 + 5x + 8
Term 1:   -4x^2 + 5x + 3
Term 2:   2x^3 - 8x^2 + 4x
Difference:   -2x^3 + 4x^2 + 1x + 3

Term 1:   5x^4 - 5
Term 2:   2x^3 + 1x^2 + 4x - 9
Difference:   5x^4 - 2x^3 - 1x^2 - 4x + 4
Term 1:   5x^4 - 5
Term 2:   3x^2 - 4x + 8
Difference:   5x^4 - 3x^2 + 4x - 13
Term 1:   5x^4 - 5
Term 2:   -4x^2 + 5x + 3
Difference:   5x^4 + 4x^2 - 5x - 8
Term 1:   5x^4 - 5
Term 2:   5x^4 - 5
Difference:   0
Term 1:   5x^4 - 5
Term 2:   2x^3 - 8x^2 + 4x
Difference:   5x^4 - 2x^3 + 8x^2 - 4x - 5

Term 1:   2x^3 - 8x^2 + 4x
Term 2:   2x^3 + 1x^2 + 4x - 9
Difference: - 9x^2 + 9
Term 1:   2x^3 - 8x^2 + 4x
Term 2:   3x^2 - 4x + 8
Difference:   2x^3 - 11x^2 + 8x - 8
Term 1:   2x^3 - 8x^2 + 4x
Term 2:   -4x^2 + 5x + 3
Difference:   2x^3 - 4x^2 - 1x - 3
Term 1:   2x^3 - 8x^2 + 4x
Term 2:   5x^4 - 5
Difference:   -5x^4 + 2x^3 - 8x^2 + 4x + 5
Term 1:   2x^3 - 8x^2 + 4x
Term 2:   2x^3 - 8x^2 + 4x
Difference:   0

使用列表在 C 中多项式的乘法

multiplication of polynomial in C using list

c

polynomials