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

typedef struct PNode
{   
    int index;  //指数
    int coe;   // 系数
    struct PNode  *next;  //指针域
}PNode,*Polynomial;

// 初始化三个多项式链表
void chushihua(Polynomial *L, Polynomial *M, Polynomial *N)
{
    //todo list 1: 为三个链表分配头节点并初始化
    *L = (Polynomial)malloc(sizeof(PNode));
    (*L)->next = NULL;
    *M = (Polynomial)malloc(sizeof(PNode));
    (*M)->next = NULL;
    *N = (Polynomial)malloc(sizeof(PNode));
    (*N)->next = NULL;
}

// 判断链表是否为空
void Emp(Polynomial L)
{
    if (L->next == NULL)
        printf("链表为空表。\n");
    else
        printf("链表为非空表。\n");
}

// 求链表长度
void Length(Polynomial L)
{
    PNode *p;
    int length = 0;
    //todo list 2: 遍历链表统计节点个数
    p = L->next;
    while (p != NULL) {
        length++;
        p = p->next;
    }
    printf("链表长度为：%d\n", length);
}

// 1、构造两个按指数递增的有序链表：插入节点，创建一元多项式
// 1、构造两个按指数递增的有序链表：插入节点，创建一元多项式
void charu_1(Polynomial L) {
    PNode *q, *p;
    int n, i;
    printf("请输入你要创建的一元多项式的项数：\n");
    scanf("%d", &n);
    for (i = 1; i <= n; i++) {
        p = L;
        q = (Polynomial)malloc(sizeof(PNode));
        printf("请输入第%d项的系数和指数：", i);
        scanf("%d%d", &q->coe, &q->index);
        q->next = NULL;
        
        // 查找插入位置，保持指数递增
        while (p->next != NULL && p->next->index < q->index) {
            //todo list 3: p指针移动到合适的位置
            p = p->next;
        }
        
        // 直接插入，不合并相同指数的项
        //todo list 4: 将*q结点插入到*p结点后
        q->next = p->next;
        p->next = q;
    }
}


// 显示函数 - 使用H分隔系数和指数
void xianshi(Polynomial L)
{
    PNode *p;
    p = L->next;
    if (p == NULL) {
        printf("多项式为空");
        return;
    }
    while (p != NULL)
    {
        printf("%dH%d", p->coe, p->index);  // 系数H指数
        p = p->next;
        if (p != NULL) {
            printf("    ");  // 项之间的分隔
        }
    }
    printf("\n");
}

//2、两个一元多项式相加 
void hebiao(Polynomial J, Polynomial O, Polynomial H) 
{
    PNode *p = J->next, *q = O->next, *r = H, *s;
    
    // 初始化结果链表
    H->next = NULL;
    
    while (p != NULL && q != NULL) {
        if (p->index < q->index) {
            s = (Polynomial)malloc(sizeof(PNode));
            //todo list 5: 复制p节点的数据到新节点s
            s->coe = p->coe;
            s->index = p->index;
            s->next = NULL;
            //todo list 6: 将s节点插入到结果链表H的末尾
            r->next = s;
            r = s;
            p = p->next;
        } else if (p->index > q->index) {
            s = (Polynomial)malloc(sizeof(PNode));
            //todo list 7: 复制q节点的数据到新节点s
            s->coe = q->coe;
            s->index = q->index;
            s->next = NULL;
            //todo list 8: 将s节点插入到结果链表H的末尾
            r->next = s;
            r = s;
            q = q->next;
        } else {
            //todo list 9: 处理指数相等的项
            int sum = p->coe + q->coe;
            if (sum != 0) {
                s = (Polynomial)malloc(sizeof(PNode));
                s->index = p->index;
                s->coe = sum;
                s->next = NULL;
                //todo list 10: 将合并后的项插入结果链表
                r->next = s;
                r = s;
            }
            p = p->next;
            q = q->next;
        }
    }
    
    //todo list 11: 处理剩余节点 - 多项式J
    while (p != NULL) {
        s = (Polynomial)malloc(sizeof(PNode));
        s->coe = p->coe;
        s->index = p->index;
        s->next = NULL;
        r->next = s;
        r = s;
        p = p->next;
    }
    
    //todo list 12: 处理剩余节点 - 多项式O
    while (q != NULL) {
        s = (Polynomial)malloc(sizeof(PNode));
        s->coe = q->coe;
        s->index = q->index;
        s->next = NULL;
        r->next = s;
        r = s;
        q = q->next;
    }
    
    printf("两个多项式相加的结果为：");
    xianshi(H);
}

// 清空链表函数
void clearList(Polynomial L) {
    PNode *p = L->next;
    while (p != NULL) {
        PNode *temp = p;
        p = p->next;
        free(temp);
    }
    L->next = NULL;
}

int main()
{
    Polynomial head[3];
    int i;
    for (i = 0; i < 3; i++) {
        head[i] = (Polynomial)malloc(sizeof(PNode));
        head[i]->next = NULL;
    }

    int choose = -1;
    
    printf("*********************************************************\n");
    printf("**********            实验二                      *******\n");
    printf("*********************************************************\n");
    printf("**********     1.初始化单链表                     *******\n");
    printf("**********     2.建立递增链表(按指数递增)         *******\n");
    printf("**********     3.显示单链表整体                   *******\n");
    printf("**********     4.求单链表长度                     *******\n");
    printf("**********     5.判断单链表是否为空               *******\n");
    printf("**********     6.求一元多项式的和                 *******\n");
    printf("**********     0.退出                             *******\n");
    printf("*********************************************************\n");
    
    while (choose != 0) {
        printf("请输入你的选择项：");
        scanf("%d", &choose);
        
        // 在switch外部声明变量
        PNode *temp;
        
        switch (choose) {
            case 1:
                chushihua(&head[0], &head[1], &head[2]); 
                printf("链表已经初始化。\n");
                break;
            case 2:
                for (i = 0; i < 2; i++) {
                    printf("创建的第%d个一元多项式：\n", i+1);
                    charu_1(head[i]);
                }
                break;
            case 3: 
                printf("显示第1个链表：");
                xianshi(head[0]);
                printf("显示第2个链表：");
                xianshi(head[1]);
                break;
            case 4:  
                printf("计算第1个链表的长度：");
                Length(head[0]);
                printf("计算第2个链表的长度：");
                Length(head[1]);
                break;
            case 5:
                printf("判断第1个链表是否为空：");
                Emp(head[0]);
                printf("判断第2个链表是否为空：");
                Emp(head[1]);
                break;   
            case 6:
                // 先清空结果链表
                clearList(head[2]);
                hebiao(head[0], head[1], head[2]); 
                break;
            case 0:
                printf("程序退出，感谢使用！\n");
                // 释放内存
                for (i = 0; i < 3; i++) {
                    clearList(head[i]);
                    free(head[i]);
                }
                return 0;
            default:
                printf("输入错误，请重新输入！\n");
                break;
        }
    }
    return 0;
}