数据结构--多项式相加

#include<iostream>
using namespace std;

typedef struct node{
    float coef;
    int expn;
    struct node *next;
} polynode;

void initlist(polynode *&sq)
{
    sq=(polynode *) malloc(sizeof(polynode));
    sq->next=NULL;
}


int getlen(polynode *sq)
{
    int i=0;
    polynode *p=sq->next;

    while(p!=NULL){
    i++;
    p=p->next;
    }

    return i;
}

polynode *getelem(polynode *sq,int i)
{
    int j=1;
    polynode *p=sq->next;

    if(i<1||i>getlen(sq))
    return NULL;

    while(j<i){
        p=p->next;
        j++;
    }

    return p;

}


polynode *locate(polynode *sq,float c,int e)
{
    polynode *p=sq->next;

    while(p!=NULL && (p->coef!=c||p->expn!=e)) p=p->next;
    
    return p;
}


int inselem(polynode *sq,float c,int e,int i)
{
    int j=1;
    polynode *p=sq,*s;

    s= (polynode *)malloc(sizeof(polynode));
    s->coef=c;
    s->expn=e;
    
    if(i<1||i>getlen(sq)+1)
        return 0;
    while(j<i){
        p=p->next;
        j++;
    }

    s->next=p->next;
    p->next=s;

    return 1;

    
}


int delelem(polynode *sq,int i)
{
    int j=1;
    polynode *p=sq,*q;
    if(i<1||i>getlen(sq))
        return 0;

    while(j<i){
        p=p->next;
        j++;
    }

    q=p->next;
    p->next=q->next;
    
    free(q);
    return 1;
}


void displist(polynode *sq)
{
    polynode *p=sq->next;
    while(p->next!=NULL){
        cout<<"<"<<p->coef<<","<<p->expn<<"> ";
        p->next;
    }

    cout<<endl;
}


void crealist(polynode *&sq,float C[],int E[],int n)
{
    int i;
    initlist(sq);
    for(i=0;i<n;i++)
    {
        inselem(sq,C[i],E[i],i+1);
    }
}


void order(polynode *sq)
{
    polynode *p=sq->next,*q,*pre;
    sq->next=NULL;

    while(p!=NULL)
    {
        if(sq->next==NULL)
        {

            sq->next=p;
            p=p->next;
            sq->next->next=NULL;
        }
        else
        {
            pre=sq;
            q=pre->next;
            
            while(q!=NULL&&p->expn > q->expn){
            pre=q;
            q=q->next;

            }
            q=p->next;
            p->next=pre->next;
            pre->next=p;
            p=q;

        }
    }
}
polynode *addpolyn(polynode *pa,polynode *pb)
{
    polynode *pc,*p1=pa->next,*p2=pb->next,*p,*rear,*s;
    pc=(polynode *)malloc(sizeof(polynode));
    pc->next=NULL;
    rear=pc;
    while(p1!=NULL&&p2!=NULL){
        if(p1->expn<p2->expn){
        s=(polynode *)malloc(sizeof(polynode));
        s->coef=p1->coef;s->expn=p1->expn;s->next=NULL;
        rear->next=s;rear=s;
        p1=p1->next;
        }
        else if(p1->expn>p2->expn){
            s=(polynode *)malloc(sizeof(polynode));
            s->coef=p1->coef;s->expn=p1->expn;s->next=NULL;
         rear->next=s;rear=s;
         p2=p2->next;
        }
        else{
            if(p1->coef+p2->coef!=0){
                s=(polynode *)malloc(sizeof(polynode));
                s->coef=p1->coef+p2->coef;
                s->expn=p1->expn;
                s->next=NULL;
                rear->next=s;
                rear=s;
                rear->next=NULL;
            }
            p1=p1->next;p2=p2->next;
    }
}
    if(p1!=NULL)p=p1;
    else p=p2;
    while(p!=NULL){
        s=(polynode *)malloc(sizeof(polynode));
         s->coef=p->coef;s->expn=p->expn;s->next=NULL;
         rear->next=s;rear=s;
         p=p->next;
    }
    return pc;
}

void main()
{
     polynode *sq1,*sq2,*sq3;
     float C1[]={3,7,5,9},C2[]={-9,8,22};
     int E1[]={1,0,17,8},E2[]={8,1,7};
     crealist(sq1,C1,E1,4);
     //crealist(sq2,C2,E2,3);

     //cout<<"两多项式相加运算"<
     cout<<" 原多项式A:"<<endl;displist(sq1);
 // cout<<" 原多项式B:"<
 // order(sq1);

    // order(sq2);

    //cout<<"排序后A：";displist(sq1);

 // cout<<"排序后B：";displist(sq2);

    // sq3=addpolyn(sq1,sq2);

    // cout<<"多项式相加结果:"; displist(sq3);


}