数据结构实验之一元多项式相加

Love The Way You Lie 2022-07-14 04:12 168阅读 0赞

【实验内容】

结合书上第41页的例子，采用链式存储结构，将两个线性链表表示的一元多项式相加，并输出。此一元多项式遵循多项式相加运算规则：对于两个一元多项式中存在指数相同的项时，其对应系数相加。合并后系数和为零时，删除“和多项式”中此项；合并后系数和不为零时，则构成“和多项式”中的一项。对于两个一元多项式中存在的指数不相同的项，则分别复抄到“和多项式”中去，原多项式保持不变。  
【实验源码】：

#include<stdio.h>
    
    #include<stdlib.h>
    
    
    
    struct node{
    
    float cofe;//系数
    
    int expn;//指数
    
    };
    
    typedef struct pay{
    
    struct node  elem;
    
    struct pay *next;
    
    }*SqList;
    
    //创建一元多项式链表
    
    void CreateChain(SqList *ha,int n)
    
    {
    
    float x1;
    
    int x2;//x1表示系数，x2表示指数
    
    SqList p;
    
    *ha=NULL;
    
    printf("请依次输入多项式对应的系数跟指数:\n");
    
    while(n){
    
    scanf("%f%d",&x1,&x2);
    
    p=(SqList)malloc(sizeof(struct pay));
    
    p->elem.cofe=x1;
    
    p->elem.expn=x2;
    
    p->next=*ha;
    
    *ha=p;
    
    n--;
    
    }
    
    }
    
    //输出一元多项式
    
    void ShowSqList(SqList ha)
    
    {
    
    if(ha==NULL)
    
    printf("F(x)=0");
    
    else
    
    {
    
    printf("多项式F(x)=%.0fX^%d",ha->elem.cofe,ha->elem.expn);
    
    ha=ha->next;
    
    while(ha!=NULL)
    
    {
    
    if(ha->elem.cofe>0)
    
    printf("+");
    
       printf("%.0fX^%d",ha->elem.cofe,ha->elem.expn);
    
    ha=ha->next;
    
    }
    
    }
    
    printf("\n");
    
    }
    
    //冒泡排序链表
    
    void SortChain(SqList head,int n)
    
    {
    
    int i,j;
    
    struct node temp;
    
    SqList p1,p2;
    
    for(p1=head,i=0;i<n-1;i++,p1=p1->next)
    
    for(p2=p1->next,j=0;j<n-i-1;j++,p2=p2->next)
    
    if(p1->elem.expn<p2->elem.expn)
    
    {
    
    temp=p2->elem;
    
    p2->elem=p1->elem;
    
    p1->elem=temp;
    
    }
    
    }
    
    //多项式相加
    
    SqList add(SqList ha,SqList hb)
    
    {
    
    int t=0;
    
    int size=0;
    
        SqList p,hc=NULL;
    
    while(ha&&hb)
    
    {
    
    if(ha->elem.expn==hb->elem.expn)
    
    {
       //两指数相同时，系数相加
    
              t=ha->elem.cofe+hb->elem.cofe;
    
     if(t)
    
     {
       //系数和不为零，则插入和多项式hc链表中
    
    p=(SqList)malloc(sizeof(struct pay));
    
    p->elem.cofe=t;
    
    p->elem.expn=ha->elem.expn;
    
    p->next=hc;
    
    hc=p;
    
    ha=ha->next;
    
    hb=hb->next;
    
    size++;
    
     }
    
     else
    
     {
       //系数和为零，则ha、hb结点后移
    
     ha=ha->next;
    
     hb=hb->next;
    
     }
    
    }
    
    else
    
    if(ha->elem.expn>hb->elem.expn)
    
    {
       //ha的指数大则先行插入hc
    
                 p=(SqList)malloc(sizeof(struct pay)); 
    
    p->elem=ha->elem;
    
    p->next=hc;
    
    hc=p;
    
    ha=ha->next;
    
    size++;
    
    }
    
    else
    
    {
       //hb的指数大则先行插入hc
    
                 p=(SqList)malloc(sizeof(struct pay)); 
    
    p->elem=hb->elem;
    
    p->next=hc;
    
    hc=p;
    
    hb=hb->next;
    
    size++;
    
    }
    
    }
    
    while(ha)
    
    {
       //ha不为空，则将当前ha剩余项全部插入hc
    
    p=(SqList)malloc(sizeof(struct pay)); 
    
       p->elem=ha->elem;
    
    p->next=hc;
    
       hc=p;
    
       ha=ha->next;
    
    size++;
    
    }
    
    while(hb)
    
    {
       //hb不为空，则将当前hb剩余项全部插入hc
    
    p=(SqList)malloc(sizeof(struct pay)); 
    
       p->elem=hb->elem;
    
    p->next=hc;
    
       hc=p;
    
       hb=hb->next;
    
    size++;
    
    }
    
    SortChain(hc,size);
    
    return hc;
    
    }
    
    void main ()
    
    {
    
    SqList ha,hb,hc;
    
    int n,m;
    
    printf("请输入第一个一元多项式的项数：");
    
    scanf("%d",&n);
    
    CreateChain(&ha,n);
    
    SortChain(ha,n);
    
    
    
    printf("请输入第二个一元多项式的项数：");
    
    scanf("%d",&m);
    
    CreateChain(&hb,m);
    
    SortChain(hb,m);
    
    
    
    printf("两个多项式如下：\n");
    
    ShowSqList(ha);
    
    ShowSqList(hb);
    
    
    
        printf("\n---------------------------------------\n");
    
    printf("两多项式相加的和多项式如下：\n");
    
    hc=add(ha,hb);
    
        ShowSqList(hc);
    
        printf("相加后原两个多项式如下：\n");
    
    ShowSqList(ha);
    
    ShowSqList(hb);
    
    }