#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct pnode {
    double coeff;
    int exp;
    struct pnode *next;
} PolyNode, *Polynomial;

void createPoly(Polynomial *PL, double coeffs[], int exps[], int size) {
    *PL = (Polynomial)malloc(sizeof(PolyNode));
    (*PL)->next = NULL;

    for (int i = 0; i < size; i++) {
        Polynomial newNode = (Polynomial)malloc(sizeof(PolyNode));
        newNode->coeff = coeffs[i];
        newNode->exp = exps[i];

        Polynomial prev = *PL, curr = (*PL)->next;
        while (curr != NULL && curr->exp > newNode->exp) {
            prev = curr;
            curr = curr->next;
        }

        if (curr != NULL && curr->exp == newNode->exp) {
            curr->coeff += newNode->coeff;
            free(newNode);
        } else {
            newNode->next = curr;
            prev->next = newNode;
        }
    }
}

void printPoly(Polynomial PL) {
    Polynomial current = PL->next;
    if (current == NULL) {
        printf("The polynomial is empty.\n");
        return;
    }

    int first = 1;  // 用来控制是否是第一个项
    while (current != NULL) {
        if (current->coeff != 0) {
            // 对第一个项特殊处理，避免开头的正数前加 "+"
            if (first) {
                if (current->coeff < 0) {
                    printf("%.1f", current->coeff);  // 负数系数直接输出
                } else {
                    printf("%.1f", current->coeff);  // 正数系数直接输出，不加 "+" 
                }
                first = 0;  // 之后的项不再是第一个
            } else {
                // 对后续项根据符号输出 "+" 或 "-"
                if (current->coeff < 0) {
                    printf(" %.1f", current->coeff);  
                } else {
                    printf(" +%.1f", current->coeff); 
                }
            }

            if (current->exp != 0) {
                printf("x^%d", current->exp); 
            }
        }
        current = current->next;
    }
    printf("\n");
}


void add(Polynomial PA, Polynomial PB, Polynomial *PC) {
    *PC = (Polynomial)malloc(sizeof(PolyNode));
    (*PC)->next = NULL;

    Polynomial currA = PA->next;
    Polynomial currB = PB->next;
    Polynomial currC = *PC;

    while (currA != NULL && currB != NULL) {
        Polynomial newNode = (Polynomial)malloc(sizeof(PolyNode));
        if (currA->exp > currB->exp) {
            newNode->coeff = currA->coeff;
            newNode->exp = currA->exp;
            currA = currA->next;
        } else if (currA->exp < currB->exp) {
            newNode->coeff = currB->coeff;
            newNode->exp = currB->exp;
            currB = currB->next;
        } else {
            newNode->coeff = currA->coeff + currB->coeff;
            newNode->exp = currA->exp;
            currA = currA->next;
            currB = currB->next;
        }
        if (newNode->coeff != 0) {
            newNode->next = NULL;
            currC->next = newNode;
            currC = newNode;
        } else {
            free(newNode);
        }
    }

    while (currA != NULL) {
        Polynomial newNode = (Polynomial)malloc(sizeof(PolyNode));
        newNode->coeff = currA->coeff;
        newNode->exp = currA->exp;
        newNode->next = NULL;
        currC->next = newNode;
        currC = newNode;
        currA = currA->next;
    }

    while (currB != NULL) {
        Polynomial newNode = (Polynomial)malloc(sizeof(PolyNode));
        newNode->coeff = currB->coeff;
        newNode->exp = currB->exp;
        newNode->next = NULL;
        currC->next = newNode;
        currC = newNode;
        currB = currB->next;
    }
}
//求导函数
void derivative(Polynomial PL, Polynomial *PD) {
    *PD = (Polynomial)malloc(sizeof(PolyNode));
    (*PD)->next = NULL;

    Polynomial current = PL->next;
    Polynomial currD = *PD;

    while (current != NULL) {
        if (current->exp > 0) {  // 只有指数大于0的项才有导数
            Polynomial newNode = (Polynomial)malloc(sizeof(PolyNode));
            newNode->coeff = current->coeff * current->exp;
            newNode->exp = current->exp - 1;
            newNode->next = NULL;

            currD->next = newNode;
            currD = newNode;
        }
        current = current->next;
    }
}

//  x 有具体的值时，某个多项式的值
double calValue(Polynomial PL, double x) {
    double value = 0;
    Polynomial current = PL->next;

    while (current != NULL) {
        value += current->coeff * pow(x, current->exp);  // 计算（系数 * x^exp）
        current = current->next;
    }

    return value;
}

// 逆置多项式链表
void reverse(Polynomial *PL) {
    Polynomial prev = NULL;
    Polynomial current = (*PL)->next;
    Polynomial nextNode;

    while (current != NULL) {
        nextNode = current->next;
        current->next = prev;
        prev = current;
        current = nextNode;
    }

    (*PL)->next = prev;  // 更新头结点的指向
}
//计算A*B=D
void multiply(Polynomial PA, Polynomial PB, Polynomial *PD) {
    *PD = (Polynomial)malloc(sizeof(PolyNode));
    (*PD)->next = NULL;

    Polynomial currA = PA->next;
    while (currA != NULL) {
        Polynomial currB = PB->next;
        while (currB != NULL) {
            double newCoeff = currA->coeff * currB->coeff;
            int newExp = currA->exp + currB->exp;

            // 插入到结果多项式中
            Polynomial prev = *PD, currD = (*PD)->next;
            while (currD != NULL && currD->exp > newExp) {
                prev = currD;
                currD = currD->next;
            }

            if (currD != NULL && currD->exp == newExp) {
                currD->coeff += newCoeff;
            } else {
                Polynomial newNode = (Polynomial)malloc(sizeof(PolyNode));
                newNode->coeff = newCoeff;
                newNode->exp = newExp;
                newNode->next = currD;
                prev->next = newNode;
            }
            currB = currB->next;
        }
        currA = currA->next;
    }
}

void destroyPoly(Polynomial *PL) {
    Polynomial current = *PL;
    while (current != NULL) {
        Polynomial temp = current;
        current = current->next;
        free(temp);
    }
    *PL = NULL;
}

int main() {
/*设置了八个函数
1.createPoly:创建带头结点的有序单链表：ABCD
2.printPoly：打印链表表，其中我们设置了一个要求，保留系数的一位小数，并且开头的系数若为正数则不带有+
3.add：两个链表相加
4.derivative：模拟求导法则，多次调用可以求多次导数
5.calValue：代入x的值计算多项式
6.multiply：计算A*B=D
7.reverse：逆置链表
*/

    Polynomial polyA, polyB, polyC,polyC1,polyD;
    //这里的C1就是C的一次导数结果

    //  A(x)
    double coeffsA[] = {5, 9, 3, 7};
    int expsA[] = {17, 8, 1, 0};
    int sizeA = 4;
    createPoly(&polyA, coeffsA, expsA, sizeA);

    // B(x)
    double coeffsB[] = {-9, 22, 8};
    int expsB[] = {8, 7, 1};
    int sizeB = 3;
    createPoly(&polyB, coeffsB, expsB, sizeB);

    // 输出 A(x)和B(x)
    printf("A(x) = ");
    printPoly(polyA);
    printf("B(x) = ");
    printPoly(polyB);

    // 计算 A + B 并输出
    add(polyA, polyB, &polyC);
    printf("C(x) = A(x) + B(x) =  ");
    printPoly(polyC);

    // 求 C(x) 的一阶导数并输出
    derivative(polyC, &polyC1);
    printf("C'(x) = ");
    printPoly(polyC1);

    // 求 C'(π) 的值
    double result = calValue(polyC1, 3.14);//我们这里用3.14来粗略计算，代替π
    printf("C'(π) = %.2f\n", result);

     // 逆置 C(x) 并输出
    reverse(&polyC);
    printf("Reversed C(x) = ");
    printPoly(polyC);

    //求两个一元多项式的积 ，并输出
    multiply(polyA, polyB, &polyD);
    printf("D(x) = A(x) * B(x) = ");
    printPoly(polyD);

    // 销毁多项式
    destroyPoly(&polyA);
    destroyPoly(&polyB);
    destroyPoly(&polyC);

    return 0;
}