Умножение полинома в C с использованием списка
Я использую списки для реализации умножения полиномов. Мой код:
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;
}
}
Но это кажется слишком избыточным; как это упростить?
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 или вернуть новый полином - этот код возвращает новое значение.
И, как уже упоминалось в комментариях, как правило, лучше не использовать typedef для указателей данных (другое дело указатели функций). Вы можете узнать больше на Это хорошая идея, чтобы печатать указатели. В итоге я получил одну структуру для полиномов, которая совпадает со структурой для члена в полиноме. (Тестовый код использует пару структур, term и termlist, чтобы описать полиномы для целей тестирования. Они делают жизнь проще. Там скромное количество тестового кода. add_polynomial() а также sub_polynomial() функции были завершены в течение 10 минут, включая исправление печати для 0 полиномы, что является свидетельством полезности add_term() функция.
print_polynomial() Функция важна и полезна. Он также должен иметь дело с некоторыми особенно сложными случаями (отрицательные коэффициенты, первый отрицательный коэффициент, нулевые коэффициенты, степень единицы и степень нуля). Возможно, его следует обобщить, чтобы можно было указать имя переменной; это жестко закодировано как x, Там могут быть некоторые более простые функции, пытающиеся избежать - одна возможность print_term() функция, которая может быть использована в другом месте, а также вызывается в print_polynomial(), Конечно, было бы непростое общение, чтобы справиться со сложными особыми случаями.
К вашему сведению: я определяю все функции (кроме main()) как static если нет второго исходного файла, который ссылается на них, и заголовочного файла, который их объявляет. Очевидно, что некоторые из этих функций станут общедоступными, если код будет использоваться повторно, а затем будут выполнены extern (неstatic) и объявлено в шапке. Детали типа не будут в заголовке; typedef struct polynomial polynomial; будет там, но это все, что будет необходимо. Определение будет скрыто в файле реализации. Это будет непрозрачный тип. Некоторые функции, такие как add_term() а также make_term() останется как static функции.
Код использует обозначенные C99 инициализаторы и составные литералы. Это может быть написано с использованием кода C89/C90, но это будет сложнее и / или сложнее. Не обязательно намного сложнее, но...
Без лишних слов, вот код (он довольно длинный):
/* 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