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

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

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

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

struct NODE{

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

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

NODE *next;

};

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