数据结构实验一—— 线性表（一元多项式相加）

墨蓝 2023-06-18 13:55 2阅读 0赞

一、实验目标

（1）掌握线性表的链式存储结构

（2）掌握链表的基本操作，并能进行应用实践

（3）实验C/C++语言和线性表实现“一元多项式相加”专题

二、实验任务

本程序是一个控制台程序，用户可以根据自己的需求分别输入两个一元多项式，并且能够实现显示输入的一元多项式，再将这两个一元多项式相加，输出结果。

输入的需求是按照指数从小到大进行输入，并且项数必须为正整数，指数需为整数，系数为双精度型且不能为0.

三、实验代码

#include<iostream>
    using namespace std;
    
    struct ListNode///链表的一个结点
    {
        double coef;///系数域
        int expn;///指数域
        ListNode* next;///指针域，指向下一个结点
    };
    
    void ShowNode(ListNode* p)
    {
        double a=p->coef;///指向系数
        int b=p->expn;///指向指数
        if(a==1)///系数为1时
        {
           if(b==0)///输出常数
            cout<<a;
           else if(b==1)///系数为1
            cout<<'x';
           else
            cout<<"x^"<<b;
        }
        else if(a==-1)///系数为-1
        {
            if(b==0)
                cout<<-1;
            else if(b==1)
                cout<<"-x";
            else
                cout<<"-x^"<<b;
        }
        else///系数为其他
        {
            cout<<a;
            if(b==0)///直接输出a系数
                ;
            else if(b==1)
                cout<<'x';
            else
                cout<<"x^"<<b;
        }
    }
    
    ///多项式连接
    void Show(ListNode* p)
    {
        ShowNode(p->next);
        p=p->next->next;///首个结点不需要连接符，故指向第二个结点
        while(p)///下一个结点不为空
        {
            if(p->coef>0)///只要下一个结点的系数不为0就输出‘+’
                cout<<'+';
            ShowNode(p);///输出结点连接
            p=p->next;///继续指向下一个结点
        }
    }
    
    ///输入多项式
    ListNode* Print(int i)///传入的i表示该多项式有几项
    {
        double a;///系数
        int b;///指数
        ListNode* head=new ListNode;///创建空结点
        head->coef=0;///系数为0
        head->expn=0;///指数为0
        head->next=NULL;///下一个结点为空
        ListNode* p=head;///p取头位置
        for(int k=0;k<i;k++)///循环输入，次数等于项数
        {
            ListNode* pNode=new ListNode;///每次循环创建一个新的尾结点
            cout<<"请输入第"<<k+1<<"项系数:";///k从0开始，故+1
            cin>>a;
            cout<<"请输入第"<<k+1<<"项指数:";
            cin>>b;
            pNode->coef=a;///系数
            pNode->expn=b;///指数
            pNode->next=NULL;
            p->next=pNode;///p的下一个节点就是刚刚建立的结点，于是尾结点改变
            p=pNode;///p指针再次指向尾结点
        }
        cout<<"该多项式为:";
        ListNode* p2=head;///用于显示
        Show(p2);
        return head;///主函数中赋值用
    }
    
    ///多项式进行相加
    ListNode* Add(ListNode* list1,ListNode* list2)
    {
        ListNode* p1=list1->next;///定义指针指向第一个多项式的第一项
        ListNode* p2=list2->next;///定义指针指向第二个多项式的第一项
        ///创建和多项式空链表
        ListNode* p3=new ListNode;
        p3->coef=0;
        p3->expn=0;
        p3->next=NULL;
        ListNode* p4=p3;
    
        while(p1&&p2)///1，2都存在时
        {
            ListNode* pNode=new ListNode;///要插入的新节点
            double coef1=p1->coef;///list1的系数
            int expn1=p1->expn;///list1的指数
            double coef2=p2->coef;///list2的系数
            int expn2=p2->expn;///list2的指数
            if(expn1==expn2)///指数相等时
            {
                if(coef1+coef2!=0)///没有抵消
                {
                    pNode->coef=coef1+coef2;///和多项式的系数
                    pNode->expn=expn1;///和多项式的指数
                    pNode->next=NULL;
                    p4->next=pNode;///连接p4和pNode
                    p4=pNode;///p4指向pNode,pNode为链表中的最后一个节点
                }
                 p1=p1->next;///p1,p2后移
                 p2=p2->next;
            }
            if(expn1<expn2)///1的指数比2小，则该项与1重合
            {
                pNode->coef=coef1;
                pNode->expn=expn1;
                pNode->next=NULL;
                p4->next=pNode;
                p4=pNode;
                p1=p1->next;///1继续后指
            }
            if(expn1>expn2)
            {
                pNode->coef=coef2;
                pNode->expn=expn2;
                pNode->next=NULL;
                p4->next=pNode;
                p4=pNode;
                p2=p2->next;
            }
        }
        if(p1==NULL)///p1空了，就把p2直接接在后面
        {
            while(p2)
            {
                ListNode* ppNode=new ListNode;
                ppNode->coef=p2->coef;
                ppNode->expn=p2->expn;
                ppNode->next=NULL;
                p4->next=ppNode;
                p4=ppNode;
                p2=p2->next;
            }
        }
        else if(p2==NULL)///p2空了，就把p1接上去
        {
            while(p1)
            {
                ListNode* ppNode=new ListNode;///新链表存储list1所以剩余项
                ppNode->coef=p1->coef;
                ppNode->expn=p1->expn;
                ppNode->next=NULL;
                p4->next=ppNode;
                p4=ppNode;
                p1=p1->next;
            }
        }
        return p3;
    }
    
    ///主函数
    int main()
    {
        int m,n;
        cout<<"请输入第1个多项式的项数:";
        cin>>m;
        ListNode* list1=Print(m);
        cout<<endl;
        cout<<"请输入第2个多项式的项数:";
        cin>>n;
        ListNode* list2=Print(n);
        cout<<endl;
        ListNode* list3=Add(list1,list2);
        cout<<"多项式之和为:";
        Show(list3);
        cout<<endl;
        cout<<"第一个多项式为：";
        Show(list1);
        cout<<endl;
        cout<<"第二个多项式为：";
        Show(list2);
    }

程序结果截图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk2NTU5Nw_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk2NTU5Nw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191202205348901.jpeg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk2NTU5Nw==,size_16,color_FFFFFF,t_70