多项式加法-->动态实现

以你之姓@ 2022-06-06 13:17 141阅读 0赞

*  前面多项式的加法实现使用的是数组进行实现的，这里介绍的使用链表进行实现的，使用链表进行实现更加高效；
 *  对于多项式使用链表来进行实现，首先应该解决的是创建多项式的问题；

void CreatPolynomial(polyPointer *phead, polyNode item)
    {
        polyPointer temp = (polyPointer)malloc(sizeof(polyPointer));
        if (temp == NULL)
        {
            fprintf(stderr, "malloc error\n");
            exit(EXIT_FAILURE);
        }
        polyPointer templink = *phead;
        temp->coef = item.coef;
        temp->expon = item.expon;
        temp->link = NULL;
        if (*phead == NULL) *phead = temp;
        else
        {
            while (templink->link != NULL) templink = templink->link;
            templink->link = temp;
        }
    }

*  在进行多项式加法运算过程中，需要通过`attach`函数来连接各个多项式；

void attach(float coefficient, int exponent, polyPointer *ptr)
    {
        polyPointer temp;
        temp = (polyPointer)malloc(sizeof(polyPointer));
        if (temp == NULL)
        {
            fprintf(stderr, "malloc error.\n");
            exit(EXIT_FAILURE);
        }
        temp->coef = coefficient;
        temp->expon = exponent;
        (*ptr)->link = temp;
        *ptr = temp;
    }

*  多项式相加函数，这个函数需要处理的情况包括;  
    
    
     *  系数相加；
     *  指数比较；
     *  并且需要创建新节点；

polyPointer padd(polyPointer a, polyPointer b)
    {
        polyPointer c, rear, temp;
        int sum;
        rear = (polyPointer)malloc(sizeof(*rear));
        if (rear == NULL)
        {
            fprintf(stderr, "malloc error.\n");
            exit(EXIT_FAILURE);
        }
        c = rear;
        while (a && b)
            switch (COMPARE(a->expon, b->expon))
            {
            case -1:
                attach(b->coef, b->expon, &rear);
                b = b->link;
                break;
            case 0:
                sum = a->coef + b->coef;
                if (sum)
                    attach(sum, b->expon, &rear);
                a = a->link;
                b = b->link;
                break;
            case 1:
                attach(a->coef, a->expon, &rear);
                a = a->link;
            }
        for (; a; a = a->link) attach(a->coef, a->expon, &rear);
        for (; b; b = b->link) attach(b->coef, b->expon, &rear);
        rear->link = NULL;
        temp = c;
        c = c->link;
        free(temp);
        return c;
    }

*  完整的程序过程：

#include<stdio.h>
    #include<stdlib.h>
    #define COMPARE(X,Y)  (((X)<(Y)) ? -1:(X)==(Y) ? 0 :1)
    
    typedef struct Node *polyPointer;
    typedef struct Node polyNode;
    struct Node
    {
        int coef;
        int expon;
        polyPointer link;
    };
    
    void attach(float coefficient, int exponent, polyPointer *ptr)
    {
        polyPointer temp;
        temp = (polyPointer)malloc(sizeof(polyPointer));
        if (temp == NULL)
        {
            fprintf(stderr, "malloc error.\n");
            exit(EXIT_FAILURE);
        }
        temp->coef = coefficient;
        temp->expon = exponent;
        (*ptr)->link = temp;
        *ptr = temp;
    }
    
    
    polyPointer padd(polyPointer a, polyPointer b)
    {
        polyPointer c, rear, temp;
        int sum;
        rear = (polyPointer)malloc(sizeof(*rear));
        if (rear == NULL)
        {
            fprintf(stderr, "malloc error.\n");
            exit(EXIT_FAILURE);
        }
        c = rear;
        while (a && b)
            switch (COMPARE(a->expon, b->expon))
            {
            case -1:
                attach(b->coef, b->expon, &rear);
                b = b->link;
                break;
            case 0:
                sum = a->coef + b->coef;
                if (sum)
                    attach(sum, b->expon, &rear);
                a = a->link;
                b = b->link;
                break;
            case 1:
                attach(a->coef, a->expon, &rear);
                a = a->link;
            }
        for (; a; a = a->link) attach(a->coef, a->expon, &rear);
        for (; b; b = b->link) attach(b->coef, b->expon, &rear);
        rear->link = NULL;
        temp = c;
        c = c->link;
        free(temp);
        return c;
    }
    void CreatPolynomial(polyPointer *phead, polyNode item)
    {
        polyPointer temp = (polyPointer)malloc(sizeof(polyPointer));
        if (temp == NULL)
        {
            fprintf(stderr, "malloc error\n");
            exit(EXIT_FAILURE);
        }
        polyPointer templink = *phead;
        temp->coef = item.coef;
        temp->expon = item.expon;
        temp->link = NULL;
        if (*phead == NULL) *phead = temp;
        else
        {
            while (templink->link != NULL) templink = templink->link;
            templink->link = temp;
        }
    }
    
    void polyNodeErase(polyPointer *phead)
    {
        polyPointer temp;
        while(*phead){
            temp=*phead;
            *phead=(*phead)->link;
            free(temp);
        }
    }
    void PolynomialPrint(polyPointer phead)
    {
        while (phead != NULL)
        {
            printf("[%d]--[%d]\n", phead->coef, phead->expon);
            phead = phead->link;
        }
    }
    int main()
    {
        polyPointer aphead = NULL;
        polyNode item;
        item.coef = 10;
        item.expon = 3;
        CreatPolynomial(&aphead, item);
        item.coef = 11;
        item.expon = 2;
        CreatPolynomial(&aphead, item);
        item.coef = 9;
        item.expon = 1;
        CreatPolynomial(&aphead, item);
        printf("a contains:\n");
        PolynomialPrint(aphead);
    
    
        polyPointer bphead = NULL;
        polyNode item2;
        item2.coef = 22;
        item2.expon = 4;
        CreatPolynomial(&bphead, item2);
        printf("b contains:\n");
        PolynomialPrint(bphead);
        polyPointer c = padd(aphead, bphead);
        printf("the result is:\n");
        PolynomialPrint(c);
    
    
        polyNodeErase(&aphead);
        polyNodeErase(&bphead);
        polyNodeErase(&c);
    
    
        return 0;
    }

*  程序的执行结果：  
    ![这里写图片描述][SouthEast]

[SouthEast]: /images/20220606/7b1752a45547416388669ef137041a98.png