struct TListItem {
	int Step;
	double Koef;
	TListItem *Next, *Prev;
};
struct TList {
	TListItem *First, *Last;
};

TList InitList() {
	TList r;
	r.First = NULL;
	r.Last = NULL;
	return r;
}

void AddListItem(TList &List, int step, double koef) {
	TListItem *tmp;
	if (List.First == NULL) {
		List.First = new TListItem;
		List.First->Step = step;
		List.First->Koef = koef;
		List.First->Prev = NULL;
		List.First->Next = NULL;
		List.Last = List.First;
	}
	else {
		tmp = new TListItem;
		tmp->Step = step;
		tmp->Koef = koef;
		tmp->Next = NULL;
		tmp->Prev = List.Last;
		List.Last->Next = tmp;
		List.Last = tmp;
	}
}

void AddSortedListItem(TList &List, int step, double koef) {
	TListItem *i, *p_i, *tmp;
	if (List.First == NULL) {
		List.First = new TListItem;
		List.First->Step = step;
		List.First->Koef = koef;
		List.First->Prev = NULL;
		List.First->Next = NULL;
		List.Last = List.First;
	}
	else {
		for (i = List.First; i != NULL; i = i->Next) {
			if (i->Step<step) {
				p_i = i->Prev;
				tmp = new TListItem;
				tmp->Step = step;
				tmp->Koef = koef;
				tmp->Next = i;
				p_i->Next = tmp;
				i->Prev = tmp;
				break;
			}
		}
		if (i == NULL)
		{
			tmp = new TListItem;
			tmp->Step = step;
			tmp->Koef = koef;
			tmp->Next = NULL;
			tmp->Prev = List.Last;
			List.Last->Next = tmp;
			List.Last = tmp;
		}

	}
}


void DestroyList(TList &List) {
	TListItem *t = List.Last, *r;
	while (t != NULL) {
		r = t->Next;
		delete(t);
		t = r;
	}
	List.First = List.Last = NULL;
}

void PrintList(TList &List) {
	TListItem *t = List.First;
	cout << "p= ";
	char znak = ' ';
	while (t != NULL) {
		cout << znak << t->Koef << "* X^" << t->Step;
		t = t->Next;
		if (znak == ' ') znak = '+';
	}
	cout << endl;
}

void Multiply(TList p1, TList p2, TList &res) {
	TListItem *i1, *i2, *i3;
	int st, isPresent;
	double k;
	res = InitList();
	for (i1 = p1.First; i1 != NULL; i1 = i1->Next) {
		for (i2 = p2.First; i2 != NULL; i2 = i2->Next) {
			st = i1->Step + i2->Step;
			k = i1->Koef*i2->Koef;
			isPresent = 0;
			for (i3 = res.First; i3 != NULL; i3 = i3->Next) {
				if (i3->Step == st) {
					isPresent = 1;
					i3->Koef = i3->Koef + k;
				}
			}
			if (isPresent == 0)
				AddSortedListItem(res, st, k);
		}
	}

}
int main(int argc, char* argv[])
{
	int Step1[4]={4,3,2,1};
	double Koef1[4]={ 5.5,	3.4,	2.8,	1.1	};

	int Step2[3]={5,3,0};
	double Koef2[3]={ 3.76,	4.9,1.1	};

	//randomize();
	TList L1, L2, L3;
	int n, p;
	double k;
	L1 = InitList();
	L2 = InitList();
	/*cout << "N=";
	cin >> n;*/
	n=4;
	cout << "elements: " << endl;
	for (int i = 0; i<n; i++) {
		//cin >> p >> k;
		AddListItem(L1,Step1[i],Koef1[i]);
		//AddListItem(L1, p, k);
	}
	n=3;
	/*cout << "N=";
	cin >> n;*/
	for (int i = 0; i<n; i++) {
		//cin >> p >> k;
		AddListItem(L2,Step2[i],Koef2[i]);
		//AddListItem(L2, p, k);
	}
	/*for(int i=0; i<ListSize; i++)
	AddListItem(L, random(MaxValue)); */
	PrintList(L1);
	PrintList(L2);
	Multiply(L1, L2, L3);
	PrintList(L3);
	DestroyList(L3);
	DestroyList(L1);
	DestroyList(L2);
	_getch();
	return 0;
}
//---------------------------------------------------------------------------