Пример. Сложение многочленов
В этом примере исходными данными являются два многочлена от трех переменных:
Априорно известно, что лишь немногие из коэффициентов этих полиномов отличны от нуля. Если воспользоваться прямоугольными массивами для хранения коэффициентов многочленов, то, во-первых, основной объем памяти будет потрачен на хранение нулей, а, во-вторых, основное время работы алгоритма будет потрачено на сложение с нулем и умножение на нуль.
В данном примере полином представлен линейным односвязным циклическим списком с головой. Структура узла имеет вид :
struct NODE{
float A; // коэффициент при одночлене
int px,py,pz; // степени x,y,z
NODE *next;
};
Многочлен 3x2y2z+8x2y3z2-7x3yz4 будет представлен списком, изображенным на рис.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.