数据结构题目（实验报告题目）———用单链表ha 存储多项式

数据结构题目（实验报告题目）———用单链表ha 存储多项式

用单链表ha 存储多项式A（x ）=a0+a1x1+a2x2+…+anxn(其中aI为非零系数)，用单链表hb 存储多项式B（x ）=b0+b1x1+b2x2+…+bmxm(其中bj为非零系数)，要求计算C（x ）= A（x ）+B（x ），结果存到单链表hc中。 

算法思想：首先传入两个多项式链表，申请一个链表存放相加的结果，依次取出两个多项式的节点。如果指数相等则相加，结果为零，释放该节点，不为零申请节点将加和结果存入节点，并将节点插入和多项式；如果不相等，则把指数大的节点插入和多项式。在一个链表计算完成之后若另一个链表还有节点，则将剩余节点全部插入和多项式。

#include   
#include   
#include   
  
typedef struct PolyNode * Polynomial;  
struct PolyNode{  
    int coef;//系数   
    int expon;//指数   
    Polynomial link;  
};  
void Attach(int c, int e, Polynomial * rear);//将新读入的系数和指数加到多项式的末尾   
Polynomial ReadPoly();//读入多项式   
Polynomial AddPoly(Polynomial P1, Polynomial P2);//计算两个多项式之和   
void PrintPoly(Polynomial P);//输出多项式运算结果   
int main()  
{  
    Polynomial P1 = ReadPoly();  
    Polynomial P2 = ReadPoly();  
    Polynomial PA = AddPoly(P1, P2);  
    PrintPoly(PA);  
    system("pause");  
    return 0;  
}  
void Attach(int c, int e, Polynomial * rear)  
{  
    Polynomial input = (Polynomial)malloc(sizeof(struct PolyNode));  
    //申请新节点并赋初值   
    input->coef = c;  
    input->expon = e;  
    input->link = NULL;  
    (*rear)->link = input;  
    *rear = input; //修改末尾指针，因为是修改指针，故此处使用指针的指针   
}  
Polynomial ReadPoly()  
{  
    Polynomial P1, rear, t;  
    int N;//多项式项数   
    int c,e;//用来暂存系数和指数   
    P1 = (Polynomial)malloc(sizeof(struct PolyNode));//申请头节点   
    //申请头节点是为了方便使用Attach函数时，不用区分rear是空还是非空，有了头节点都是非空，插入方便   
    P1->link = NULL;  
      
    rear = P1;//尾指针指向头节点   
    printf("请输入多项式项数：n");  
    scanf("%d",&N);  
    printf("请输入多项式(格式为a**b c**d,指数递减)：n");  
    while(N--)   
    {  
        scanf("%d**%d",&c, &e);  
        Attach(c, e, &rear);  
    }  
    t = P1;   
    P1 = P1->link;  
    free(t);//释放头节点  
    return P1;   
}  
Polynomial AddPoly(Polynomial P1, Polynomial P2)  
{  
    Polynomial t1,t2,rear,t;  
    t1 = P1;  
    t2 = P2;  
    Polynomial P = (Polynomial)malloc(sizeof(struct PolyNode));  
    P->link = NULL;  
    rear = P;  
    while(t1 && t2)  
    {  
        if(t1->expon == t2->expon)//如果指数相同则进行相加   
        {  
            if(t1->coef + t2->coef)//如果系数相加不为零，则将计算结果加入P中   
            {  
                Attach(t1->coef + t2->coef, t1->expon, &rear);  
            }  
            t1 = t1->link;  
            t2 = t2->link;  
        }  
        else if(t1->expon > t2->expon)//找到指数大的加入到P中   
        {  
   
            Attach(t1->coef, t1->expon, &rear);  
            t1 = t1->link;  
        }  
        else  
        {  
            Attach(t2->coef, t2->expon, &rear);  
            t2 = t2->link;  
        }  
    }  
    while(t1)//如果t1还有多余节点，则继续加入   
    {  
        Attach(t1->coef, t1->expon, &rear);  
        t1 = t1->link;  
    }  
    while(t2)//如果t2还有多余节点，则继续加入   
    {  
        Attach(t2->coef, t2->expon, &rear);  
        t2 = t2->link;  
    }  
    t = P;  
    P = P->link;  
    free(t);//释放头节点   
    return P;  
}  
  
void PrintPoly(Polynomial P)  
{  
    printf("多项式运算结果为:n");   
    int flag = 0;  
    if(!P)  
    {  
        printf("0 0n");  
        return;  
    }  
    while(P)  
    {  
        if(!flag)  
            flag = 1;  
        else  
            printf(" ");  
        printf("%d**%d",P->coef, P->expon);  
        P = P->link;       
    }  
    printf("n");  
}