Question

C语言：用链表表示多项式并完成输入、运算和输出。

可利用链表表示一个多项式，如3x^5-2x+1可用 （3，5）、（-2，1）、（1，0）序列的链表表示。请设计能进行两个多项式加、减、乘运算的函数，并设计相应程序能根据要求进行多项式输入、运算和输出。

Answer 1

#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);  
}