#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

/// <summary>
/// Структура узла списка
/// </summary>
struct node {
    int koeff;
    int power;
    struct node* next;
};

typedef struct node* list;

/// <summary>
/// Функция создания списка
/// </summary>
/// <param name="phead">"голова" списка</param>
void createList(list* phead)
{
    *phead = NULL;
}

/// <summary>
/// Функции для проверки существования в списке заданного элемента
/// </summary>
/// <param name="phead">"голова" списка</param>
/// <param name="power">степень элемента</param>
/// <param name="koeff">коэффициент при элементе</param>
/// <returns>True - если элемент есть в спике, иначе False</returns>
bool checkIfExist(list* phead, int power, int koeff)
{
    list p = *phead;
    while (p != NULL)
    {
        if (p->power == power)
        {
            p->koeff += koeff;
            return true;
        }
        p = p->next;
    }
    return false;
}

/// <summary>
/// Функция для добавления элемента в список
/// </summary>
/// <param name="phead">"голова" списка</param>
/// <param name="power">степень элемента</param>
/// <param name="koeff">коэффициент при элементе</param>
/// <returns>True - если элемент добавлен, иначе False</returns>
bool addToHead(list* phead, int koeff, int power)
{
    list p;
    if (checkIfExist(phead, power, koeff))
    {
        printf("Такая степень уже есть %d\n", power);
        return false;
    }
    p = (list)malloc(sizeof(*p));
    p->koeff = koeff;
    p->power = power;
    p->next = *phead;
    *phead = p;
    printf("Добавлено: %d*x^%d\n", p->koeff, p->power);
    return true;
}

/// <summary>
/// Функция ввода элементов списка с консоли, заполнение списка
/// </summary>
/// <param name="phead">"голова" списка</param>
void enterListElems(list* phead)
{
    cout << "Введите степень многочлена: ";
    int k = 0;
    cin >> k;
    int i_koeff = 1, i_power = 0;
    for (int i = 0; i < k + 1; i++)
    {
        cout << "Введите коэффициент для x^" << i_power << ": ";
        cin >> i_koeff;
        if (i_koeff != 0)
            addToHead(phead, i_koeff, i_power);
        i_power++;
    }
}

/// <summary>
/// Функция печати элементов списка на экран
/// </summary>
/// <param name="phead">"голова" списка</param>
void printList(list* phead)
{
    list p;
    cout << "P(x) = ";
    for (p = *phead; p != NULL; p = p->next)
    {
        if (p->next != NULL)
            printf("%d*x^%d + ", p->koeff, p->power);
        else
            printf("%d*x^%d", p->koeff, p->power);
    }
    cout << endl;
}

/// <summary>
/// Проверка двух списков на равенство
/// </summary>
/// <param name="phead1">"голова" первого списка</param>
/// <param name="phead2">"голова" второго списк</param>
/// <returns>True - если списки равны, иначе false</returns>
bool checkEquality(list* phead1, list* phead2)
{
    list p1 = *phead1;
    list p2 = *phead2;
    int len1 = 0, len2 = 0;
    for (p1; p1 != NULL; p1 = p1->next)
        len1++;
    for (p2; p2 != NULL; p2 = p2->next)
        len2++;
    if (len1 != len2)
        return false;
    p1 = *phead1;
    p2 = *phead2;
    for (p1, p2; p1 != NULL && p2 != NULL; p1 = p1->next, p2 = p2->next)
        if (p1->koeff != p2->koeff || p1->power != p2->power)
            return false;
    return true;
}

/// <summary>
/// Функция вычисления полинома в точке X
/// </summary>
/// <param name="phead">"голова" списка</param>
/// <param name="x">целочисленная точка X</param>
/// <returns>Результат вычислений</returns>
int getResult(list* phead, int x)
{
    list p = *phead;
    int res = 0;
    for (p = *phead; p != NULL; p = p->next)
        res += pow(x, p->power) * p->koeff;
    return res;
}

int main(void)
{
    setlocale(LC_ALL, "RUSSIAN");
    list L1, L2;
    int  x;

    // Создаем первый список, заполняем его и выводим на экран многочлен
    createList(&L1);
    enterListElems(&L1);
    printList(&L1);

    // Считаем первый многочлен в точке X
    cout << endl;
    cout << "Введите целочисленную точку X для вычисления многочлена: ";
    cin >> x;
    cout << "Многочлен в точке " << x << " = " << getResult(&L1, x) << endl;
    cout << endl;

    // Создаем второй список, заполняем его и выводим на экран многочлен
    createList(&L2);
    enterListElems(&L2);
    printList(&L2);

    // Считаем второй многочлен в точке X
    cout << endl;
    cout << "Введите целочисленную точку X для вычисления многочлена: ";
    cin >> x;
    cout << "Многочлен в точке " << x << " = " << getResult(&L2, x) << endl;
    cout << endl;

    // Проверяем 2 списка на равенство
    if (checkEquality(&L1, &L2))
        cout << "Многочлены равны" << endl;
    else
        cout << "Многочлены не равны" << endl;
    return 0;
}