数据结构（C语言）用单链表存储一元多项式,并实现两个多项式的相加运算

数据结构（C语言）用单链表存储一元多项式,并实现两个多项式的相加运算

#include<stdio.h>  
#include<stdlib.h>  
#include<malloc.h>  
typedef int ElemType;  
  
/*单项链表的声明*/  
typedef struct PolynNode{  
    int coef; // 系数  
    int expn; // 指数  
    struct PolynNode *next;  
}PolynNode,*PolynList;  
  
/*正位序(插在表尾)输入n个元素的值,建立带表头结构的单链线性表*/  
/*指数系数一对一对输入*/  
void CreatePolyn(PolynList &L,int n)  
{  
    int i;  
    PolynList p,q;  
    L=(PolynList)malloc(sizeof(PolynNode)); // 生成头结点  
    L->next=NULL;  
    q=L;  
    printf("成对输入%d个数据\n",n);  
    for(i=1;i<=n;i++)  
    {  
        p=(PolynList)malloc(sizeof(PolynNode));  
        scanf("%d%d",&p->coef,&p->expn);    //指数和系数成对输入  
        q->next=p;  
        q=q->next;  
    }  
    p->next=NULL;  
}  
  
// 初始条件：单链表L已存在  
// 操作结果: 依次对L的每个数据元素调用函数vi().一旦vi()失败,则操作失败  
void PolynTraverse(PolynList L,void(*vi)(ElemType, ElemType))  
{  
    PolynList p=L->next;  
    while(p)  
    {  
        vi(p->coef, p->expn);  
        if(p->next)  
        {  
            printf(" + ");   //“+”号的输出,最后一项后面没有“+”  
        }  
        p=p->next;  
    }  
    printf("\n");  
}  
  
/*ListTraverse()调用的函数(类型要一致)*/  
void visit(ElemType c, ElemType e)   
{  
    if(c != 0)  
    {  
        printf("%dX^%d",c,e);   //格式化输出多项式每一项  
    }  
}  
  
/*    多项式相加,原理：归并        */  
/* 参数：两个已经存在的多项式       */  
/* 返回值：归并后新的多项式的头结点 */  
PolynList MergeList(PolynList La, PolynList Lb)  
{  
    PolynList pa, pb, pc, Lc;  
    pa = La->next;  
    pb = Lb->next;  
    Lc = pc = La;   // 用La的头结点作为Lc的头结点  
    while(pa&&pb)  
    {  
        if(pa->expn < pb->expn)          
        {                                
            pc->next = pa;             //如果指数不相等,pc指针连上指数小的结点,  
            pc = pa;  
            pa = pa->next;             //指向该结点的指针后移  
        }  
        else if (pa ->expn > pb->expn )      
        {  
            pc->next = pb;               //pc指针连上指数小的结点,  
            pc = pb;  
            pb = pb->next;               //指向该结点的指针后移  
        }  
        else   //(pa ->expn = pb->expn )  
        {  
            pa->coef = pa->coef + pb->coef;     //指数相等时,系数相加  
            pc->next = pa;  
            pc = pa;  
            pa = pa->next;             //两指针都往后移  
            pb = pb->next;  
        }  
    }  
  
    pc->next = pa ? pa:pb;  // 插入剩余段  
  
    return Lc;  
}  
  
void main()  
{  
    PolynList ha,hb,hc;  
    printf("非递减输入多项式ha, ");  
    CreatePolyn(ha,5);   // 正位序输入n个元素的值  
  
    printf("非递减输入多项式hb, ");  
    CreatePolyn(hb,5);   // 正位序输入n个元素的值  
  
    printf("多项式ha :");  
    PolynTraverse(ha, visit);  
    printf("\n");  
    printf("多项式hb :");  
    PolynTraverse(hb, visit);  
    printf("\n");  
  
    hc = MergeList(ha,hb);  
    PolynTraverse(hc, visit);  
}