利用链表实现一元多项式加法减法|数据结构

发布于 2021-07-10  23 次阅读


1、说明:

链表的应用之一:一元多项式运算,这里先说明一元多项式加法,减法类同

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

2、代码实现

//一元多项式的运算
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
typedef struct node
{
    int coef;
    int exp;
    struct node* next;

}polynode;

//创建一元多项式
polynode* Creatlist(int n)
{
    polynode* head,*p,* r=NULL;
    int i;

    head = (polynode*)malloc(sizeof(polynode));
    head->coef = 0;
    head->exp = -1;
    head->next = NULL;
    p = head;

    for (i = 1; i <= n; i++)
    {
        r = (polynode*)malloc(sizeof(polynode));
        printf("input (coef exp):");
        scanf("%d%d", &r->coef,&r->exp);
        p->next = r;
        p = r;
    }r->next = NULL;
    printf("生成完毕\n");
    return head;

}

//排序
void Sort(polynode* head)
{
    polynode* p, * q;
    int coef;
    int exp;
    for (p=head->next;p;p=p->next)
    {
        for (q=p->next;q;q=q->next)
        {
            if (p->exp>q->exp)
            {
                coef = p->coef;
                p->coef = q->coef;
                q->coef = coef;

                exp = p->exp;
                p->exp = q->exp;
                q->exp = exp;
            }
        }
    }
}

//输出
void Out(polynode*head)
{
    polynode* p;
    p= head->next;
    while (p)
    {
        printf("%dx^%d",p->coef,p->exp);
        p = p->next;
        if (p!=NULL)
        {
            if (p->coef>=0)
            {
                printf("+");
            }
        }
    }
    printf("\n");
}

//加法运算
polynode* PolyAdd(polynode*a,polynode*b)
{
    polynode* c, * p1, * p2, * p3, * r;
    int sum;

    p1 = a->next;
    p2 = b->next;
    c = a;
    p3 = c;
    while (p1&&p2)
    {
        if (p1->exp<p2->exp)
        {
            p3->next = p1;
            p3 = p1; 
            p1 = p1->next;
        }
        else if (p1->exp>p2->exp)
        {
            p3->next = p2;
            p3 = p2;
            p2 = p2->next;
        }
        else
        {
            sum = p1->coef + p2->coef;
            if (sum)
            {
                p1->coef = sum;
                p3->next = p1;
                p3 = p1;
                p1 = p1->next;
                r = p2;
                p2 = p2->next;
                free(r);
            }
            else
            {
                r = p1; p1 = p1->next; free(r);
                r = p2; p2 = p2->next; free(r);
            }
        }
    }

    if (p1)
    {
        p3->next = p1;
    }
    else
    {
        p3->next = p2;
    }
    free(b);
    return c;
}

//减法运算
/*
两个多项式相减得一个新多项式,并且返回新多项式的头结点的指针
相减就是先将减数中每一项的系数变为负,再将两个多项式相加
*/
polynode* Polyminus(polynode* a, polynode* b)
{
    polynode* c, * p1, * p2, * p3, * r;
    int sum;

    p1 = a->next;
    p2 = b->next;
    c = a;
    p3 = c;
    while (b)
    {// 将pb中每一项的系数变为负 
        b->coef = 0 - b->coef;
        b = b->next;
    }
    while (p1 && p2)
    {
        if (p1->exp < p2->exp)
        {
            p3->next = p1;
            p3 = p1;
            p1 = p1->next;
        }
        else if (p1->exp > p2->exp)
        {
            p3->next = p2;
            p3 = p2;
            p2 = p2->next;
        }
        else
        {
            sum = p1->coef + p2->coef;
            if (sum)
            {
                p1->coef = sum;
                p3->next = p1;
                p3 = p1;
                p1 = p1->next;
                r = p2;
                p2 = p2->next;
                free(r);
            }
            else
            {
                r = p1; p1 = p1->next; free(r);
                r = p2; p2 = p2->next; free(r);
            }
        }
    }

    if (p1)
    {
        p3->next = p1;
    }
    else
    {
        p3->next = p2;
    }
    free(b);
    return c;
}

//代入确定的x到多项式中求值 
void Calculate(polynode *p, float x)
{
    polynode *q = p->next;
    float sum;
    float result = 0;//求的结果 
    while (q) 
    {
        sum = 1;
        //利用循环求出每一项x^exp的值
        for (int i = 1; i <= q->exp; i++) 
        {
            sum = sum * x;
        }
        result += sum * q->coef; //再使系数与sum相乘后求每一项的值,最后累加
        q = q->next;
    }
    printf("将X的值代入多项式中计算的结果为:%.5f\n", result);
}

int main()
{
    polynode* headA,* headB,*headC;
    int n1, n2;
    int choice_01;
    char choice_02;
    float x;

    headA = (polynode*)malloc(sizeof(polynode));
    headB = (polynode*)malloc(sizeof(polynode));
    headC = (polynode*)malloc(sizeof(polynode));
    //一元多项式A
    do
    {
        printf("请输入第一个多项式的项数:");
        scanf("%d",&n1);
        if (n1<=0)
        {
            printf("请重新输入\n");
        }
    } while (n1<=0);
    headA=Creatlist(n1);
    Sort(headA);
    printf("A:");
    Out(headA);
    getch();
    //一元多项式B
    do
    {
        printf("请输入第二个多项式的项数:");
        scanf("%d", &n2);
        if (n2 <= 0)
        {
            printf("请重新输入\n");
        }
    } while (n2 <= 0);
    headB = Creatlist(n2);
    Sort(headB);
    printf("B:");
    Out(headB);
    getch();

    do
    {
        printf("请输入要选择的运算 (1)加法(2)减法:");
        scanf("%d",&choice_01);
        if (choice_01!=1&&choice_01!=2)
        {
            printf("请重新输入\n");
        }
    } while (choice_01 != 1&&choice_01 != 2);

    switch (choice_01)
    {
    case 1:
        //加法
        printf("两个一元多项式相加:A+B= ");
        headC = PolyAdd(headA, headB);
        Out(headC);
        break;
    case 2:
        //减法
        printf("两个一元多项式相减:A-B= ");
        headC = Polyminus(headA, headB);
        Out(headC);
        break;
    }
    getchar();//清除掉缓冲区的回车符  
    printf("\n是否代入X进行求值?(Y/N): ");
    choice_02 = getchar();        
    getchar();
    switch (choice_02)
    {
    case 'Y':
    {
        printf("\n请输入多项式中X的值:");
        scanf("%f", &x);
        Calculate(headC, x);
        break;
    }
    case 'N':break;
    default:printf("你输入了错误指令 %c !", choice_02);
    }
    return 0;
}