一元多項式的運算

以一元多項式加法運算為例:

A,B可用線性鏈表可以表示為:

“和多項式”鏈表如下(圖中的長方框表示已經被釋放的結點):

#include <stdio.h>
#include <stdlib.h>
typedef struct Polyn{
    int data;
    int index;
    struct Polyn *next;
}Polyn,*Polynlist;
void CreatPolyn(Polynlist &p,int m)//輸入m項的繫數和指數,建立一元多項式P
{    
    //有頭結點
    Polyn *q=p;
    for(int i=0;i<m;i++)
    {
        q->next=(Polyn*)malloc(sizeof(Polyn));
        q=q->next;
//        printf("第%d項繫數、指數:",i+1);
        scanf("%d%d",&q->data,&q->index);
    }
    q->next=0;
}
void PrintPolyn(Polynlist &p)//列印一元多項式P
{
    Polyn *q=p->next;
    //(x^0)和(x^1)要做特別處理
    if(q->index == 0)                                                                                    
    {
        printf("%d",q->data);
        //可能第二項指數為x
        q=q->next;
        if(q && q->index == 1)
        {
            if(q->data != 1)
                printf("%+dx",q->data);//正數則在前面加+,否則不加
            else
                printf("+x");
            q = q->next;
        }
    }
    else if(q->index == 1){
        if(q->data != 1)
            printf("%dx",q->data);
        else
            printf("x");
        q = q->next;
    }
    else{
        printf("%dx^%d",q->data,q->index);
        q = q->next;
    }
    while(q)
    {
        printf("%+dx^%d",q->data,q->index);
        q=q->next;
    }
    printf("\n");
}
void CopyPolyn(Polynlist &q,Polyn *r)//空指針必須引用去創建,新開闢結點鏈表並複製(數據域和指針域)
{
    q = (Polyn *)malloc(sizeof(Polyn));
    Polyn *q1 = q,*r1 = r->next;
    while(r1)
    {
        q1->next = (Polyn *)malloc(sizeof(Polyn));
        q1 = q1->next;
        q1->data = r1->data;
        q1->index = r1->index;
        r1 = r1->next;
    }
    q1->next = NULL;
}
void ShowMenu()
{
    printf("\t\t\t1.多項式相加\n");
    printf("\t\t\t2.多項式相減\n");
    printf("\t\t\t3.多項式相乘\n");
    printf("\t\t\t4.退出\n");
}
void AddPolyn(Polyn *p,Polyn *p1)//完成多項式相加運算,p=p+p1,並銷毀p1
{
    Polyn *qa,*qb,*prior,*r;//設置prior是為B鏈表中的結點插入A鏈表用
    prior = p;
    qa = p->next;
    qb = p1->next;
    while(qa && qb)
    {
        if(qa->index < qb->index)
        {
            prior = qa;
            qa = qa->next;
        }
        else if(qa->index > qb->index){
            r = qb;
            qb = qb->next;
            //摘取qb到“和多項式”鏈表中
            r->next = qa;
            prior->next = r;
            //更新prior
            prior = r;
        }
        else{
            if(qa->data + qb->data != 0)
            {
                //修改qa所指結點的繫數值,同時釋放qb所指的結點
                qa->data = qa->data + qb->data;
                r = qb;
                qb = qb->next;
                free(r);
            }
            else{
                //釋放指針qa和qb所指的結點
                r = qa;
                qa = qa->next;
                prior->next = qa;//銜接
                free(r);
                r = qb;
                qb = qb->next;
                free(r);
            }
        }
    }
    //B鏈表還有結點
    if(qb)
    {
        prior->next = qb;//此時qa已為空指針
    }
    free(p1);//釋放B頭結點
}
void reverse(Polyn *p)
{
    Polyn *q = p->next;
    while(q)
    {
        q->data = -(q->data);
        q = q->next;
    }
}
void DestroyPolyn(Polyn *r)
{
    Polyn *q;
    do{
        q = r;
        r = r->next;
        free(q);
    }while(r);
}
void AdjustPolyn(Polyn *r,int data,int index)//調整每一項
{
    Polyn *q = r->next;
    while(q)
    {
        q->data *= data;
        q->index += index;
        q = q->next;
    }
}
void SubtractPolyn(Polynlist &p,Polynlist &p1)//完成多項式相減運算,p=p-p1,並銷毀p1
{
    reverse(p1);//將B鏈表的data域置反
    AddPolyn(p,p1);
}
void MultiplyPolyn(Polynlist &p,Polyn *p1)//完成多項式相乘運算,p=p*p1,並銷毀p1
{
    Polyn *q,*r = NULL,*r1 = NULL;
    q = p1->next;
    //A(x)--》bi*A(x)*x^ei
    CopyPolyn(r,p);
    AdjustPolyn(r,q->data,q->index);
    q = q->next;
    while(q)
    {
        CopyPolyn(r1,p);
        AdjustPolyn(r1,q->data,q->index);
        AddPolyn(r,r1);//r1將被銷毀
        r1 = NULL;//必須將r1置空
        q = q->next;
    }
    //r-->p，同時釋放r鏈表
    DestroyPolyn(p);
    p = NULL;
    CopyPolyn(p,r);
    DestroyPolyn(r);
}
int main()
{
    int m;
    Polyn *p=(Polyn*)malloc(sizeof(Polyn));
    Polyn *p1=(Polyn*)malloc(sizeof(Polyn));
    Polyn *p2 = NULL,*p3 = NULL;
    printf("按升冪輸入多項式A(x),B(x)的繫數,指數\n");
    printf("A(x)的項數:");
    scanf("%d",&m);
    CreatPolyn(p,m);
    printf("A(x)=");
    PrintPolyn(p);
    printf("B(x)的項數:");
    scanf("%d",&m);
    CreatPolyn(p1,m);
    printf("B(x)=");
    PrintPolyn(p1);
    //保存A,B原始多項式,此處的複製是新開闢結點鏈表
    CopyPolyn(p2,p);
    CopyPolyn(p3,p1);
    system("pause");
    system("cls");
    printf("A(x)=");
    PrintPolyn(p);
    printf("B(x)=");
    PrintPolyn(p1);
    printf("選擇以下一種操作方式:\n");
    ShowMenu();
    do{
        printf("請輸入你的選擇:");
        scanf("%d",&m);
        switch(m)
        {
        case 1:
            AddPolyn(p,p1);
            printf("A(x)+B(x)=");
            PrintPolyn(p);
            break;
        case 2:
            SubtractPolyn(p,p1);
            printf("A(x)-B(x)=");
            PrintPolyn(p);
            break;
        case 3:
            MultiplyPolyn(p,p1);
            printf("A(x)*B(x)=");
            PrintPolyn(p);
            break;
        default:
            exit(0);
        }
        fflush(stdin);
        DestroyPolyn(p);
        p1 = p = NULL;//此時的p、p1為游離指針,必須要置空
        CopyPolyn(p,p2);
        CopyPolyn(p1,p3);
    }while(1);
    return 0;
}

 運行結果截圖:

按Enter鍵之後