利用單連結清單實作一進制多項式的表示及相加

完善教材上的單連結清單實作一進制多項式的表示及相加

#include <iostream>

using namespace std;
//定義結構體；
typedef struct Polynode
{
    int coef;
    int exp;
    struct Polynode *next;
}Polynode,*Polylist;

//建立關于多項式結構體的單連結清單，以系數0結束輸入
Polylist Polycreate()
{
    Polynode *head,*rear,*s;
    int c,e;
    head=(Polynode *)malloc(sizeof(Polynode));//申請空間建立多項式的頭結點
    rear=head;
    scanf("%d %d",&c,&e);
    while(c!=0)
    {
        s=(Polynode *)malloc(sizeof(Polynode));
        s->coef=c;
        s->exp=e;
        rear->next=s;
        rear=s;
        scanf("%d %d",&c,&e);
    }//尾插法建立單連結清單
    rear->next=NULL;
    return(head);
}

//多項式polya和polyb相加，結果存放在head單連結清單中
Polylist Polyadd(Polylist polya,Polylist polyb)
{
    Polynode *head,*p,*q,*tail,*s;//head為相加後單連結清單的頭結點，tail為尾插法的尾巴節點
    int sum;
    head=(Polynode *)malloc(sizeof(Polynode));
    p=polya->next;
    q=polyb->next;
    tail=head;
    while(p!=NULL&&q!=NULL)
    {
        s=(Polynode *)malloc(sizeof(Polynode));
        if(p->exp<q->exp)
        {
            s->coef=p->coef;
            s->exp=p->exp;
            tail->next=s;
            tail=s;
            p=p->next;
        }
        else if(p->exp==q->exp)
        {
            sum=p->coef+q->coef;
            if(sum!=0)
            {
                s->coef=sum;
                s->exp=p->exp;
                tail->next=s;
                tail=s;
                p=p->next;
                q=q->next;
            }
            else return(head);
        }
        else
        {
            s->coef=q->coef;
            s->exp=q->exp;
            tail->next=s;
            tail=s;
            q=q->next;
        }
    }
    if(p!=NULL)
        tail->next=p;
    else
        tail->next=q;
    return(head);
}

//列印多項式
void show(Polylist poly)
{
    Polynode *p;
    int c;
    int e;
    p=poly->next;
    while(p->next!=NULL)//避免最後一項也出現加号
    {
        c=p->coef;
        e=p->exp;
        printf("%dX^%d+",c,e);
        p=p->next;
    }
    c=p->coef;
    e=p->exp;
    printf("%dX^%d",c,e);
}
int main()
{
    printf("請按升幂輸入多項式A,以系數為0結束：\n");
    Polylist pa=Polycreate();
    printf("你輸入的多項式為：\n");
    show(pa);
    printf("\n");
    printf("請按升幂輸入多項式B,以系數為0結束：\n");
    Polylist pb=Polycreate();
    printf("你輸入的多項式為：\n");
    show(pb);
    printf("\n");
    Polylist pc=Polyadd(pa,pb);
    printf("相加之後的多項式為：\n");
    show(pc);
    return 0;
}
           

實驗結果如下：