Пример. Сложение многочленов

В этом примере исходными данными являются два многочлена от трех переменных:

Априорно известно, что лишь немногие из коэффициентов этих полиномов отличны от нуля. Если воспользоваться прямоугольными массивами для хранения коэффициентов многочленов, то, во-первых, основной объем памяти будет потрачен на хранение нулей, а, во-вторых, основное время работы алгоритма будет потрачено на сложение с нулем и умножение на нуль.

В данном примере полином представлен линейным односвязным циклическим списком с головой. Структура узла имеет вид:

struct NODE{

float A; // коэффициент при одночлене

int px,py,pz; // степени x,y,z

NODE *next;

};

Многочлен 3x²y²z+8x²y³z²-7x³yz⁴ будет представлен списком, изобра­жен­ным на рис.9.

Рис.9. Многочлен в списке

Будем полагать, что показатели степеней ijk переменных следуют в списке в порядке возрастания (лексикографический порядок). Для сравнения степеней используется функция, возвращающая –1, 0,+1:

int PowerCmp(NODE *p, NODE *q){

if(p->px>q->px) return 1;

if(p->px<q->px) return -1;

if(p->py>q->py) return 1;

if(p->py<q->py) return -1;

if(p->pz>q->pz) return 1;

if(p->pz<q->pz) return -1;

return 0;

}

В поле ijk головы списка поместим максимально возможные значения (INT_MAX (см. файл limits.h)). Зачем это нужно будет ясно позднее. Алгоритм выполняет операцию P=P+Q, то есть результат сложения будет получен на месте первого многочлена.

void PoliAdd(NODE *p, NODE *q){

// p,q - головы списков многочленов-слагаемых

// p=p+q

NODE *p1,*p2,*q1;

NODE *x;

for(p1=p,p2=p1->next,q1=q->next; q1!=q;){

switch(PowerCmp(p2,q1)){

case 1:

// p2>q1

x=new NODE;

memcpy(x,q1,sizeof(NODE));

// вставка вслед за p1

x->next=p2;

p1->next=x;

p1=x;

p2=p1->next;

q1=q1->next;

break;

case -1:

// p2<q1

p1=p2;

p2=p2->next;

break;

case 0:

// p2==q1

p2->A+=q1->A;

if(fabs(p2->A)<1e-7){

// удалить p2

p1->next=p2->next;

delete p2;

p2=p1->next;

} else {

p1=p2;

p2=p2->next;

}

q1=q1->next;

break;

} //switch

} // for

}

Отметим, что приведенном алгоритме нет необходимости специально обрабатывать ситуацию, когда список p закончился, а список q нет. В головы списков помещены максимально возможные значения степеней, поэтому, когда закончится список p, его голова "пропустит" вперед себя весь остаток списка q.

Дата добавления: 2014-12-08