多项式加法

2021年4月6日

#include <stdio.h>
#include <stdlib.h>
#define status int
#define ture 1
#define error 0
typedef struct Node {
    int xi; //系数
    int coe; //指数
    struct node* next;
}*node,*Link;
           // 系数    指数   正负   是否输出系数   是否输出X    是否输出指数
void printL(int x, int c, int flag1, int flag2, int flag3, int flag4);  //打印格式
void print(Link head); //打印规则定义
status MergeList(Link headA, Link heada, Link headb); //两链表相加合成为一条
status Insert(Link head, node a);  // 排序并插入  指数大的排在前面，   若指数相同 ，则系数相加，并释放 a 
status InserNode(Link head, int xi, int coe); //创建节点并插入  头插法
int main(void) {
    int Flag;  //  是否继续输入的标志
    int xii;  //还未插入系数
    int coee;  //还未插入指数
    Link heada; 
    Link headb;
    Link headA;  //最终合成的链表
    //链表初始化
    heada = (Link)malloc(sizeof(struct Node));
    heada->next = NULL;
    headb = (Link)malloc(sizeof(struct Node));
    headb->next = NULL;
    headA = (Link)malloc(sizeof(struct Node));
    headA->next = NULL;
    Flag = 1;
    printf("请输入系数和指数，格式为 系数,指数 。 （输入 0,0 结束输入）\n");
    scanf_s("%d,%d",&xii,&coee,sizeof(int));
    fflush(stdin);
    while (Flag)
    {
        //如果 系数等于0 则不插入
        if (xii != 0) {                
            InserNode(heada, xii, coee);
        }
        printf("请继续输入系数和指数：");
        scanf_s("%d,%d", &xii, &coee, sizeof(int));
        fflush(stdin);
        //如果 系数，指数等于0 结束循环
        if (xii == 0 && coee == 0)
            Flag = 0;
    }
    printf("\n");
    printf("第一个多项式为：");
    print(heada);
    printf("\n\n");
    printf("请输入系数和指数，格式为 系数,指数 。 （输入 0,0 结束输入）\n");
    scanf_s("%d,%d", &xii, &coee, sizeof(int));
    fflush(stdin);
    Flag = 1;
    while (Flag)
    {
        if (xii != 0) {
            InserNode(headb, xii, coee);
        }
        printf("请继续输入系数和指数：");
        scanf_s("%d,%d", &xii, &coee, sizeof(int));
        fflush(stdin);
        if (xii == 0 && coee == 0)
            Flag = 0;
    }
    printf("\n");
    printf("第二个多项式为：");
    print(headb);
    printf("\n\n");
    MergeList(headA,heada,headb);
    printf("合并多项式为：");
    print(headA);
    return 0;
}
status InserNode(Link head, int xi, int coe) {
    //形参传入主函数的xii 和coee 并赋予新创建的节点a 
    node a;
    a = (node)malloc(sizeof(struct Node));
    a->next = NULL;
    a->coe = coe;
    a->xi = xi;
    Insert(head, a);
}
//将节点有序插入
status Insert(Link head, node a) {
    Link Q, P;
    Q = head;
    P = head->next;
    if (P == NULL)
    {
        Q->next = a;
        return 1;
    }
    //从头循环链表 。 Q为前指针 P为后指针
    while (P != NULL)
    {//系数大的插在前面
        if (a->coe > P->coe)
        {
            a->next = P;
            Q->next = a;
            return ture;
        }
        else {
            //若循环到的指数相等，则系数相加，并释放a节点
            if (a->coe == P->coe)
            {
                P->xi = P->xi + a->xi;
                free(a);
                return ture;
            }
            //否则 前后指针均向后移动一位
            Q = P;
            P = Q->next;
        }
    }
    //如果循环到P链表尾部仍然没有return ture 则说明节点a的指数是最小的，所以链表插入尾部
    Q->next = a;
    return 1;
}
status MergeList(Link headA, Link heada, Link headb) {
    Link q, p, m;
    int x, c;
    m = headA->next;
    q = heada->next;
    p = headb->next;
    //3个指针分别指向3条链表头节点的下一个节点    有三种情况： 1.q长p短   2.q短p长   3.qp长度相等
    while (q != NULL && p != NULL) {
        if (q->coe == p->coe)
        {
            c = q->coe;
            x = (q->xi + p->xi);
            InserNode(headA, x, c);
            q = q->next;
            p = p->next;
        }
        else if (q->coe > p->coe)
        {
            c = q->coe;
            x = q->xi;
            InserNode(headA, x, c);
            q = q->next;
        }
        else {
            c = p->coe;
            x = p->xi;
            InserNode(headA, x, c);
            p = p->next;
        }
    }
    while (q != NULL) {  //1.q长p短
        Insert(headA, q); //因为是有序的，因此直接插入即可
        q = q->next;
    }
    while (p != NULL) {  //q短p长
        Insert(headA, p);
        p = p->next;
    }
}
// 输出格式的考虑。  分为 系数 和 指数 两个部分。 由于主函数中 输入系数为 0 的数没有插入 因此不需要考虑系数为零的情况。
// 所以系数分为大于 0 和 小于 0 的情况。 指数 分为 等于 0 和 大于 0 （突然发现没有考虑小于0的情况，就不多说明了）
void printL(int x, int c, int flag1, int flag2, int flag3, int flag4) {
    if (flag1 == 1)
    {
        printf("+");
    }
    else if (flag1 == 2)
    {
        printf("-");
    }
    if (flag2 == 1)
        printf("%d", x);
    if (flag3 == 1)
        printf("%c", 'X');
    if (flag4 == 1)
        printf("^%d", c);
}
void print(Link head) {
    int flag = 1;
    int flag1, flag2, flag3, flag4;
    int X, C, n, i;
    Link p;
    p = head->next;
    while (p != NULL)
    {
        X = p->xi;
        C = p->coe;
        if (flag) {
            flag1 = 0;
            flag2 = 1;
            flag3 = 1;
            flag4 = 1;
            if (X < 0)
            {
                flag1 = 2;
            }
            //系数如果为1 则不输出
            if (abs(X) == 1)
            {
                flag2 = 0;
                //且如果指数为0 则输出，并且不输出 X 和 指数部分
                if (C == 0)
                {
                    flag2 = 1;
                    flag3 = 0;
                    flag4 = 0;
                }
            }
            //如果系数不为1  且 如果指数为 零 则不输出 X 和 指数部分
            else if (C == 0) {
                flag3 = 0;
                flag4 = 0;
            }
            if (X == 0)
            {
                flag1 = 0;
                flag2 = 0;
                flag3 = 0;
                flag4 = 0;
            }
            flag = 0;
        }
        //以下同上
        else {
            flag1 = 1;
            flag2 = 1;
            flag3 = 1;
            flag4 = 1;
            if (abs(X) == 1)
            {
                flag2 = 0;
                if (C == 0)
                {
                    flag2 = 1;
                    flag3 = 0;
                    flag4 = 0;
                }
            }
            else if (C == 0) {
                flag3 = 0;
                flag4 = 0;
            }
            if (X > 0)
                flag1 = 1;
            else if (X < 0)
            {
                flag1 = 2;
            }
            else if (X == 0)
            {
                flag1 = 0;
                flag2 = 0;
                flag3 = 0;
                flag4 = 0;
            }
        }
        printL(X, C, flag1, flag2, flag3, flag4);
        p = p->next;
    }
}