精华内容
下载资源
问答
  • 元多项式的表示运算 在数学上,一个一元多项式可以表示为: p(x)=p0+1x+2x2+3x3++pnx 元多项式表达式可以通过系数指数来唯一确定 方法一 用数组来表示: 令系数矩阵A={,1,p2,p3,pn] 为一个1Xn的1维数组 令指数举证B=0...
  • 数据结构—— 一元多项式的加法运算

    万次阅读 多人点赞 2019-09-24 12:01:56
    设Pn(x)和Qn(x)分别为两个一元多项式,请求出两个一元多项式的加法运算的结果,要求元素按照多项式的次数递减的次序排列。 1.问题分析 需求:实现两个一元多项式的加法运算。 实现功能:①通过键盘接收输入的整数...
    一、 需求分析
    0.问题描述

    在数学上,一个一元n次多项式 可按降序写成:
    在这里插入图片描述
    它由n+1个系数唯一确定,因此,在计算机里他可以用一个线性表表示:
    ( )。

    设Pn(x)和Qn(x)分别为两个一元多项式,请求出两个一元多项式的加法运算的结果,要求元素按照多项式的次数递减的次序排列。

    1.问题分析

    需求:实现两个一元多项式的加法运算。
    实现功能:①通过键盘接收输入的整数(浮点数)
    ②以系数和指数对应的形式,储存到计算机内存中
    ③实现一元多项式的加法运算
    ④通过屏幕输出一元多项式加法运算后的结果

    2.输入数据

    分别输入两组二元组数据,每一组二元组数据分别代表一个多项式,每个二元组包含两个整数(一个浮点数和一个整数),第一个整数(浮点数)代表多项式的项的系数,第二个整数代表该项的次数(指数),且在输入过程中,要求同一个多项式中不能出现两个项的指数相同。(使用模板设计,以下设计以系数为整数为例)

    3.输出数据

    输出两个一元二次多项式相加运算之后的结果,形式如 在这里插入图片描述

    4.测试样例设计
    (1)样例输入1:
    4
    3 2
    4 5
    1 1
    2 3
    3
    -3 2
    -4 5
    2 4
    
    (1)样例输出1:
    第一个多项式为:
    4x^5+2x^3+3x^2+1x^1
    第二个多项式为:
    -4x^5+2x^4-3x^2
    两个多项式的和为:
    2x^4+2x^3+1x^1
    

    目的:本例为了测试在两组多项式相加时,两个多项式中恰有相同指数项的系数互为相反数,即相加之后为0,能否实现正确计算。

    (2)样例输入2:
    2
    0 1
    2 3
    3
    2 6
    3 9
    4 3
    
    (2)样例输出2:
    第一个多项式为:
    2x^3
    第二个多项式为:
    3x^9+2x^6+4x^3
    两个多项式的和为:
    3x^9+2x^6+6x^3
    

    目的:本例为了检测若输入的项的系数是0,那么输出是否会出现错误,会不会把项 为0的也输出出来,能否实现正确运算。

    (3)样例输入3:
    1
    2 3
    1
    3 3
    
    (3)样例输出3:
    第一个多项式为:
    2x^3
    第二个多项式为:
    3x^3
    两个多项式的和为:
    5x^3
    

    目的:本例为了测试在两组多项式只有一项的情况下,并且这项的幂相等,观察输出是否是一项。

    (4)样例输入4:
    2
    0 5
    0 4
    5
    6 5
    3 8
    -2 2
    3 1
    2 4
    
    (4)样例输出4:
    第一个多项式为:
    (此处输出为空)
    第二个多项式为:
    3x^8+6x^5+2x^4-2x^2+3x^1
    两个多项式的和为:
    3x^8+6x^5+2x^4-2x^2+3x^1
    

    目的:当某一个多项式所有项的系数均为0时,观察该多项式样式输出 及运算结果。

    (5)样例输入5:
    3
    4 2
    -2 2
    -1 2
    2
    0 2
    6 2
    
    (5)样例输出5:
    第一个多项式为:
    4x^2-2x^2-1x^2
    第二个多项式为:
    6x^2
    两个多项式的和为:
    10x^2-2x^2-1x^2
    

    目的:本例是反例,若不符合要求同一个多项式不能有相同的幂的项存在,观察该多项式输出及运算结果。

    二、概要设计
    1.抽象数据类型

    问题的输入为多项式的,多项式由一个或者多个项构成,而每个项又是由一个指数和一个系数唯一确定,那么这个指数和这个系数就是一个具有关系的数对,我们可以用结构体进行存储,可以形象的定义为一个二元组(ai,bi),那么这些二元组按照多项式的次数递减的次序排列,则具有线性关系,则两个多项式可以分别用两个线性表表示,线性表中的数据元素即为多项式的项的二元组。

    数据对象:

    D={ 多项式的项,  项的系数, 项的指数,i=1,2,3....n,n≥1}

    数据关系:

    因为多项式按照多项式的次数递减的次序排列,相应的指数对应的系数也就排列好前后位置,因此具有线性结构,这些二元组之间都存在着有序的关系。即
    R={ D,i=1,2,3....n,n>0}

    基本操作:
    ①	link();                       // 构造线性表 
    ②	~link();                      // 摧毁线性表 
    ③	void init();                  // 初始化线性表 
    ④	void next();                  // 当前位置后移 
    ⑤	void movetostart();           // 移动当前位置到线性表表头 
    ⑥	arrary<E> getvalue();         // 获取当前位置存储单元内的数据元素
    ⑦	void insert(arrary<E> elem);   // 插入数据元素(实现线性表的有序性) 
    ⑧	int getsize();                // 返回线性表长度
    ⑨	void change(arrary<E> elem);  // 改变储存数据元素的值
    
    2.算法的基本思想

    存储:解决本问题首先要想到的就是怎么把一个乱序输入的二元组按照第二个数的从大到小的顺序排列下来,可以这么想,每次要添加一个二元组的时候都要把已经存在的二元组进行一次从头的搜索,查找到一个适当位置,使得二元组插入后,线性表数据元素满足以二元组第二个数依次递减的次序排列。把二元组的前后逻辑线性关系存储在链表中,通过修改插入函数实现上面存储中所提到的查找位置问题,然后把输入的二元组插入即可完成有序链表的构建。
    相加:把第二个多项式的线性表中的每一个数据元素二元组中第二个数依次与第一个多项式的线性表中的每一个数据元素二元组中第二个数比较,如果相同,通过修改第一个多项式的线性表中的每一个数据元素二元组中第一个数,实现相同指数项的相加,否则通过插入操作把该二元组插入到第一个多项式的线性表中。
    输出:完成相加后,计算结果储存在第一个多项式的线性表中,且由于插入时已完成了有序性的排列,按照线性表的线性顺序及多项式的写法规则输出完成相加后第一个多项式线性表中的数据元素。

    3.程序的流程

    ① 第一个模块:输入模块。提示输入多项式的项数,之后提示输入多项式的每一项的系数和指数,调用insert(有序插入)等基本操作实现有序存储数据,将多项式分别储存到线性表中,然后根据多项式的写法规则调用基本操作进行打印多项式。
    ② 第二个模块:计算模块。根据第一个模块接受的数据,利用多重循环,对第二个多项式与第一个多项式进行遍历比较,并调用change、insert等基本操作完成两个多项式的相加,计算结果存储到第一个多项式的线性表中。
    ③ 第三个模块:输出模块。通过提示,按照多项式的写法规则打印出相加后的多项式的形式。

    三、详细设计
    1.物理数据类型

    多项式的系数为整数(浮点数),指数为整数,所以物理数据类型可以为int等(采用模板)。
    多项式的项按照指数从大到小排列,相加运算时会改变项的个数。选用基于链表实现的线性表。
    ① 结点SNode的构造:结构体SNode在这个题中要存储的是一个多项式的项,其包含两个元素,多项式的系数和指数,所以我添加了一个结构体arrary作为一个二元组,包含系数(value),指数(element)将这个结构体类型的元素作为结点的数据元素
    伪代码:

    struct arrary
     {
     	      E value;
     	      E element;
    };
     struct SNode 
               {
                      arrary<E> elem;
                      SNode *next; 
    };
    

    ② 基本操作:基于有序链表实现线性表ADT,要进行的基本操作有:
    Ⅰ构造线性表
    伪代码:

    link()
    { init();}
    

    Ⅱ摧毁线性表
    伪代码:

    ~link()
    {removeall();}
    

    流程:通过link类的一个私有函数removeall完成操作。

    Ⅲ初始化线性表

    伪代码:

    void init()
        {
        	               curr=tail=head=new SNode<E>;
        	               linksize=0;
        }
    

    Ⅳ把当前位置从前到后移动一个存储单元。
    伪代码:

    void next()
    {
    			if(curr!=tail)
    		    curr=curr->next;
    }
    

    流程:当前位置移动到下一个节点,只要把当前位置的指针curr的指向修改为他所指向的节点中的指针next的指向就可以做到,但是要注意表尾操作。
    Ⅴ移动当前位置到线性表表头。
    伪代码:

    void moveToStart()
    {curr=head;}
    

    流程:把头节点的存储地址的值赋值给当前位置curr就可以实现当前位置头置。
    Ⅵ获取当前位置存储单元内的数据元素。
    伪代码:

    arrary<E> getvalue()
    {return curr->elem;}
    

    流程:函数返回当前位置指向的节点中包含的数据元素。

    Ⅶ向线性表插入一个数据元素(有序线性表的实现函数)。

    伪代码:

    void insert(arrary<E> elem)
        {
        	       for(curr=head;curr!=tail;curr=curr->next)
        	       {
        		        if(temp.element>curr->next->elem.element)break;
                    }
        	       SNode<E>* tempnew =new SNode<E>;
        	       tempnew->elem.value=temp.value;
        	       tempnew->elem.element=temp.element;
        	       tempnew->next=curr->next;
                    curr->next=tempnew;
        	       if(tail==curr)tail=curr->next;
        	       linksize++;
        }
    

    流程:首先把当前位置设定在头指针的位置,之后开始用函数参数elem的element和当前位置的数据元素(也就是栅栏后面的节点的二元组中的第二个数)比较大小,如果找到了一个位置使得后面的节点中的指数小于要输入的节点的指数那么终止循环,如果没找到这样的位置,说明输入的项指数比已经有的所有项都要小,那么就会把这个位置定在表尾,之后让当前位置所指节点的next指针指向新的节点,也就是存储新项的地方,新节点的前两个参数就是函数的两个参数,指针肯定指向下一节点,若新节点是最后一个节点,也就是他存储的项的指数最小,那么要让表尾指针指向新节点 ,同时链表长度加一。

    Ⅷ 获取线性表的长度。

    伪代码:

    int getsize()
        {return  linksize;}
    

    流程:在每一次进行插入等操作时,都会有一个变量linksize发生变化,它记录了链表的节点数目,函数返回他就可以得到线性表长度。

    Ⅸ修改当前存储单元的值。

    伪代码:

    void  change(arrary<E> temp)
        {
        	         curr->elem.value=temp.value;
        	         curr->elem.element=temp.element; 
        }
    

    流程:为了实现两个多项式相加的操作同时又不影响链表的通用性,那么将需要修改的数据元素的值作为函数的参数,把原来的节点中的value系数和element指数全部修改为函数的参数。

    2.输入和输出的格式

    输入
    ① 开始提示“请输入第一个一元多项式的项数:”,提示输入一个整数,之后提示"接下来 n行,分别输入每一项的系数和指数,如:3 2(其中3为系数,2为指数,中间以空格分隔)"。完成输入第一个多项式。
    ② 然后提示“请输入第二个一元多项式的项数:”,提示输入一个整数,之后提示"接下来 n行,分别输入每一项的系数和指数,如:3 2(其中3为系数,2为指数,中间以空格分隔)"。输入第二个多项式的输入。
    输出
    ① 提示"第一个多项式为:",之后打印第一个多项式多项式的排布,打印之后输出一行分隔符。
    ② 提示"第二个多项式为:",之后打印第二个多项式多项式的排布,打印之后输出一行分隔符。
    ③ 提示"两个多项式的和为:",之后打印两个多项式相加并存入第一个多项式线性表后的结果。

    3.算法的具体步骤
    (1)模块分析:

    ①第一个模块
    【1】第一个多项式的输入和输出:
    Ⅰ通过一个n代表第一个多项式的项数的输入进入第一个多项式的每一项系数和指数的输入,调用修改的插入函数实现数据的存入。

    cin>>n;
    cin>>temp.value>>temp.element;
    a.insert(temp);
    

    Ⅱ通过调用movetostart先把当前位置移动到表头,之后从头往后依次处理每个存储位置,特殊处理第一个输出还有系数为0的输出,调用getvalue和getelement实现输出。

    a.movetostart();
    a.getvalue();
    

    【2】第二个多项式的输入和输出
    Ⅰ通过一个m代表第二个多项式的项数的输入进入第二个多项式的每一项系数和指数的输入,调用修改的插入函数实现数据的存入。

    cin>>n;
    cin>>temp.value>>temp.element;
    b.insert(temp);
    

    Ⅱ通过调用movetostart先把当前位置移动到表头,之后从头往后依次处理每个存储位置,特殊处理第一个输出还有系数为0的输出,调用getvalue和getelement实现输出。

    b.movetostart();
    b.getvalue();
    

    ②第二个模块(实现多项式的加法运算,并将结果保存到第一个多项式的线性表中):首先对存储第二个多项式的线性表进行从头到尾的元素遍历,每一个第二个多项式中的元素都要再分别遍历第一个多项式中的元素,若查找到指数相同的项,那么调用change把第二个多项式中的系数加到第一个多项式中,如果没有找到,那就直接调用insert函数实现存入。
    b.movetoStart();
    a.movetoStart();
    如果查找到:

    if(b.getvalue().element==a.getvalue().element)
    {       arrary<int> temp2;
    	 	   temp2.value=a.getvalue().value+b.getvalue().value;
    	 	   temp2.element=a.getvalue().element;
    a.change(temp2); 
    }
    

    如果没查找到那么:

    arrary<int>temp;
    temp.value=b.getvalue().value;
    temp.element=b.getvalue().element;
    a.insert(temp);
    

    ③第三个模块(输出两个多项式相加的结果):和前文输出方法一致,通过调用movetoStart先把当前位置移动到表头,之后从头往后依次处理每个存储位置,特殊处理第一个输出还有系数为0的输出,调用getvalue和getelement实现输出。

    a.movetoStart();
    a.getvalue();
    

    流程图:
    第一个模块:
    在这里插入图片描述
    第二个模块:
    在这里插入图片描述
    第三个模块:
    在这里插入图片描述

    4.算法的时空分析

    第一个模块:对于第一个多项式的输入,首先要输入n个数对,存储时每个数对都要对已有的链表元素遍历一次,输入操作的时间代价根据化简规则略去低阶项和常数项,得到输入时间代价是Θ(n2);输出是从头到尾依次输出,所以时间代价是Θ(n),所以,输入并打印第一个多项式的时间代价是Θ(n2);与第一个多项式相同输入第二个多项式,所以第二个多项式输入并打印的时间代价是Θ(m2);综上,第一个模块的时间代价是Θ(max{ n2,m2 })。
    第二个模块:在对应多项式A,多项式B的每一个值都去遍历一次,这个双重嵌套for循环的时间代价为Θ(nm),之后进入一个也在第一重for循环中的if解决是否要用到插入操作,那么这个语句的时间代价是Θ(n2)。
    所以总共的时间代价是Θ(max{nm,n2 })。
    第三个模块:假设两个多项式相加之后的第一个多项式的长度为x,那么输出A的时间代价就是Θ(x),第四个模块的时间代价就是Θ(x)。
    综上所述:整个算法的时间代价就是Θ(max{ nm,n2 })

    四、调试分析
    1.调试方案设计

    调试目的:用手工或编译程序等方法进行测试,修正语法错误和逻辑错误的过程。这是保证计算机信息系统正确性的必不可少的步骤。编完计算机程序,必须送入计算机中测试。根据测试时所发现的错误,进一步诊断,找出原因和具体的位置进行修正。对于本题目,根据调试过程及结果检测两个多项式加法运算相关函数过程及正确性。
    样例:(设计样例中的第一个样例)

    (1)样例输入1:
    4
    3 2
    4 5
    1 1
    2 3
    3
    -3 2
    -4 5
    2 4
    
    (2)样例输出1:
    第一个多项式为:
    4x^5+2x^3+3x^2+1x^1
    第二个多项式为:
    -4x^5+2x^4-3x^2
    两个多项式的和为:
    2x^4+2x^3+1x^1
    

    调试计划:该样例的设计中两个多项式存在系数互为相反数且指数相同的项,按照设计,当两个多项式进行相加运算时,第二个多项式的项会与第一个多项式中指数相同的项通过函数修改第一个项中对应的元素值,完成相加运算,同时第一个多项式的项数不会改变,及线性表长度不变,观察第一个多项式线性表的长度,验证设计过程的正确性。
    设置:在加法运算循环处设置断点,观察调试过程。

    2.调试过程和结果,及分析

    设置断点
    在这里插入图片描述
    开始调试
    (1)当完成第一个模块输入之后,此时两个多项式线性表的长度均为项的个数,运行正常,结果如下图。
    在这里插入图片描述
    (2)从设置断点进入for循环语句,开始进行两个多项式的相加操作,由于两个多项式的第一个项的指数相同,程序进入if语句,如下图。
    在这里插入图片描述
    (3)和预测的结果相同,两个项的指数相同完成当前第一个项的相加操作之后,第一个多项式的线性表长度没有发生变化,如下图。
    在这里插入图片描述
    (4)接下来对第二个多项式中的第二项即指数为4的项在第一个多项式中查找,与预测相同,当循环到最后一个时,此时j==3,没有发现相同的项,进入第二个if语句完成插入操作,第一个线性表的长度发生改变,变为5,如下图。
    在这里插入图片描述
    (5)继续进行循环,第二个多项式中的第三项,根据预测与第一个多项式中的第四项相同,会同第一项完成相加时的操作相同,第一个多项式线性表长度不会改变,此时i=2,j=3,调试过程正确,如下图。
    在这里插入图片描述
    (6)完成相加操作后,最后输出第一个多项式,得到两个多项式相加的结果,与预测结果相同,调试结果为正确,如下图。
    在这里插入图片描述
    总结:调试结束,结果与预料一致,说明程序对这组数据的处理没有问题。

    五、测试结果
    (1) 测试样例1

    在这里插入图片描述
    结论分析:两组多项式相加时,两个多项式中恰有相同指数项的系数互为相反数,即相加之后为0,能够实现正确计算。

    (2) 测试样例2

    在这里插入图片描述
    结论分析:输入的项的系数是0,输出未出现错误,不会把项为0的也输出出来,能够实现正确运算。

    (3) 测试样例3

    在这里插入图片描述
    结论分析:在两组多项式只有一项的情况下,并且这项的幂相等,输出为一项,程序计算结果正确。

    (4) 测试样例4

    在这里插入图片描述
    结论分析:当某个多项式所有项的系数均为零时,该多项式不会输出,满足系数为0的项不会输出的设计,最后的计算结果正确,程序运行正常。

    (5) 测试样例5

    在这里插入图片描述
    结论分析:本例是反例,若不符合要求同一个多项式不能有相同的幂的项存在,当储存一个多项式时会把指数相同的项当作多个项进行储存,运算时,也会把这些所有项的系数对第一个多项式中的第一个该指数的元素进行操作,完成相加,这也是符合当前该设计的计算过程的,即程序运行正常,由于不符合同一个多项式不能有相同的幂的项存在的要求,输出结果错误。

    六、实验日志(选做)

    实验时间
    2018.10.24-2018.10.30
    实验过程
    10.24
    19:30-21:40
    ① 完成需求分析模块。
    ② 完成概要设计模块。
    10.25
    12:20-15:50
    完成详细设计模块。
    21:00-22:44
    基本完成线性表ADT的设计和实现。
    10.26
    13:00-17:24
    ① 完成有序插入基本操作的设计与实现。
    ② 完成修改储存数据元素的值基本操作的设计与实现。
    ③ 完成源代码。
    10.27
    13:00-15:25
    完成调试分析模块
    10.30
    14:30-16:00
    针对预备报告进行了完善与修改。
    19:30-21:18
    ① 修改源代码。
    ② 调试修改后的源代码。
    ③ 完成最终报告。
    实验中遇到的问题及解决分析
    (1) 如何实现有序线性表?
    分析及解决:对于线性表的有序性,可以通过修改插入基本操作,在插入储存时实现有序储存,即实现了线性表的有序性。
    (2)使用模板 template 实现数据对象的多用性。出现报错报错(GCC): error: need ‘typename’ before ‘E::xxx’ because ‘E’ is a dependent scope
    分析及解决:通过查询,得知了这样两个概念——
    从属名称(dependent names): 模板(template)内出现的名称, 相依于某个模
    (template)参数, 如 E t;
    嵌套从属名称(nested dependent names):从属名称在 class 内呈嵌套装, 如
    E::const_iterator ci;
    如果不特定指出 typename, 嵌套从属名称, 有可能产生解析(parse)歧义.
    所以,任何时候在模板(template)中指涉一个嵌套从属类型名称, 需要在前一个
    位置, 添加关键字 typename;进行如下操作解决了问题
    (3)如何实现加法运算?
    分析及解决:我们实现这样一个算法过程——遍历操作,每一个第二个多项式中的元素都要再分别遍历第一个多项式中的元素,若查找到指数相同的项,那么调用change把第二个多项式中的系数加到第一个多项式中,如果没有找到,那就直接调用insert函数实现有序存入,完成加法运算。

    实验心得
    实验设计比较完善,解决了基于有序链表实现多项式的输入输出和相加的功能,但是还是那个反例的问题怎么解决呢,我认为把两个多项式的项逐一存入另一个线性表中是一个好办法,这样的话,根据change函数,在每一次存入多项式的值的时候,新的线性表就构成了一个新的链表,那么就算多项式中有相同指数的项,到了存储进新的线性表中的时候,也会和前面已经存过的指数相同项进行一次系数的相加而不是增多一个节点,但是这个方法每次都要遍历前面已经存储过的节点时间代价有些大是它的缺点。

    具体代码实现:
    数据结构——一元多项式的加法运算
    伪代码部分排版有点问题,请见谅!

    展开全文
  • 用链表实现多项式的一元多项式运算,采用链表储存结构表示多项式。c语言编程实现,数据结构第一章作业,实验通用。
  • 一元多项式的加法运算,数据结构链表实现,代码加实验报告
  • 一元多项式加法运算  设计函数分别求两个一元多项式的和。 输入格式: 输入分2行,每行分别先给出多项式非零项的个数,再以指数递降方式输入一个多项式非零项系数和指数(绝对值均为不超过1000的整数)。数字间以...

     一元多项式加法运算 

    设计函数分别求两个一元多项式的和。

    输入格式:

    输入分2行,每行分别先给出多项式非零项的个数,再以指数递降方式输入一个多项式非零项系数和指数(绝对值均为不超过1000的整数)。数字间以空格分隔。

    输出格式:

    输出分2行,分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔,但结尾不能有多余空格。零多项式应输出0 0

    TIPS:1.关于链表,在最后一定要记得释放空表头结点;

                2.每进行一次运算都别忘了Attach;

                3.操作链表的标准步骤,定义P,rear,temp;然后申请内存,让P->next=NULL,rear=P;最后通过temp释放空表头结点。

    代码:

    #include<stdio.h>
    typedef struct Polynode *Polynomial;
    struct Polynode{
        int c;
        int e;
        Polynomial next;
    };
    Polynomial readPoly()
    {
        Polynomial P,rear,temp;
        int c,e,N;
        scanf("%d",&N);
        P=(Polynomial)malloc(sizeof(struct Polynode));
        P->next=NULL;
        rear=P;
        while(N--){
            scanf("%d %d",&c,&e);
            Attach(c,e,&rear);

       }
       temp=P;
       P=P->next;
       free(temp);//在最后释放空表头节点
       return P;

    }
    /*int compare(int a,int b)
    {
        if(a>b)return 1;
        if(a==b)return 0;
        return -1;
    }*/
    Polynomial Add(Polynomial P1,Polynomial P2)
    {
        Polynomial front,rear,temp;
        int sum;
        rear=(Polynomial)malloc(sizeof(struct Polynode));
        front=rear;
       while(P1&&P2)

                 if(P1->e>P2->e){
                    Attach(P1->c,P1->e,&rear);
                    P1=P1->next;
                 }
                 else if(P1->e<P2->e){
                    Attach(P2->c,P2->e,&rear);
                    P2=P2->next;
                 }
                else{
                    sum = P1->c+P1->c;
                    if(sum) Attach(sum,P1->e,&rear);
                    P1=P1->next;
                    P2=P2->next;


            }
        for(;P1;P1=P1->next)
            Attach(P1->c,P1->e,&rear);
        for(;P2;P2=P2->next)
            Attach(P2->c,P2->e,&rear);
        rear->next=NULL;
        temp=front;
        front=front->next;//释放空表头节点
        free(temp);
        return front;
    }

    /*Polynomial Add(Polynomial P1,Polynomial P2)
    {
        Polynomial front,rear,temp;
        int sum;
        rear=(Polynomial)malloc(sizeof(struct Polynode));
        front=rear;
       while(P1&&P2)
            switch(compare(P1->e,P2->e)){
                case 1:
                    Attach(P1->c,P1->e,&rear);
                    P1=P1->next;
                    break;
                case -1:
                    Attach(P2->c,P2->e,&rear);
                    P2=P2->next;
                    break;
                case 0:
                    sum = P1->c+P1->c;
                    if(sum) Attach(sum,P1->e,&rear);
                    P1=P1->next;
                    P2=P2->next;
                    break;

            }
        for(;P1;P1=P1->next)
            Attach(P1->c,P1->e,&rear);
        for(;P2;P2=P2->next)
            Attach(P2->c,P2->e,&rear);
        rear->next=NULL;
        temp=front;
        front=front->next;//释放空表头节点
        free(temp);
        return front;
    }
    */
    int Print(Polynomial p)
    {
        int flag=0;
        if(!(p->next)){
            printf("0 0\n");
            return 0;
        }
        while(p){
        if(!flag){
            flag+=1;
        }else{
            printf(" ");
        }
        printf("%d %d",p->c,p->e);
        p=p->next;
        }
        printf("\n");
        return 0;
    }

    void Attach(int c,int e,Polynomial *prear)
    {
        Polynomial P;
        P=(Polynomial)malloc(sizeof(struct Polynode));
        P->c=c;
        P->e=e;
        P->next=NULL;
        (*prear)->next=P;
        *prear=P;
    }
    int main()
    {
        Polynomial P1,P2,PP,PS;
        P1=readPoly();
        P2=readPoly();
       // PP=Mult(P1,P2);
        PS=Add(P1,P2);
        Print(PS);
        //Print(PP);
        return 0;

    }

    展开全文
  • 一元多项式的加法运算源程序 c++6.0运行
  • 一个一元多项式pn(x)可按升幂的形式写成: pn(x) = p0+p1X+p2X2+p3X3+…+pnXn 可以用线性表存储:(p0,p1,p2,…,pn) 例:2+x5+10x100 可以只存储非0项,用单链表存储多项式的结点结构: typedef struct Polynode{ ...

    一个一元多项式pn(x)可按升幂的形式写成:
    pn(x) = p0+p1X+p2X2+p3X3+…+pnXn
    可以用线性表存储:(p0,p1,p2,…,pn

    例:2+x5+10x100
    可以只存储非0项,用单链表存储多项式的结点结构:

    typedef struct Polynode{
    	int coef; 
    	int exp; 
    	Polynode *next;
    }Polynode,*Polylist;
    

    两个多项式相加

    A(x) = 7+3x+9x8+5x17
    B(x) = 8x+22x7-9x8

    在这里插入图片描述
    定义两个指针p,q分别指向两个多项式的第一个元素,判断p,q指向的指数域是否相同,相同就是同类项,系数加起来,然后释放另一个表里的同类项,没有同类项的直接插入到尾结点的位置。

    在这里插入图片描述

    • 若p->exp < q->exp,则结点p所指的结点应是“和多项式”中的一项,令指针p后移;
    • 若p->exp = q->exp,则将两个结点中的系数相加,当和不为零时修改结点p的系数域,释放q结点;若和为零,则和多项式中无此项,从A中删去p结点,同时释放p和q结点;
    • 若p->exp > q->exp,则结点q所指的结点应是“和多项式”中的一项,将结点q插入在结点p之前,且令指针q在原来的链表上后移。

    算法实现

    输入多项式的系数和指数,用尾插法建立一元多项式的链表。

    Polylist polycreate(){
    	Polynode *head,*rear,*s; 
    	int c,e; 
    	rear=head=(Polynode *)maloc(sizeof(Polynode)); 
    	scanf("%d,%d",&c,&e); 
    	while(c!=0){
    		s=(Polynode*)malloc(sizeof(Polynode); 
    		s->coef=c; 
    		s->exp=e; 
    		rear->next=s; 
    		rear=s; 
    		scanf("%d,%d",&c,&e);
    	} 
    	rear->next=NULL; 
    	return(head);
    }
    

    两个多项式相加

    void polyadd(Polylist polya,Polylist polyb){
    	.../*p和q分别指向polya和polyb链表中的当前计算结点*V*/
    	.../*rear指向和多项式链表中的尾结点*/
    	while(p!=NULL&&q!=NULL)
    	{
    		if(p->exp<q->exp)
    		{.../*将p结点加入到和多项式中*/)}
    		else if(p->exp==q->exp)
    		{.../*若指数相等,则相应的系数相加。
    		若系数为0则删除p,q节点*/}
    		else
    		{.../*将q结点加入到和多项式中*/}
    	}
    	/*将多项式polya或polyb中剩余的结点加入到和多项式中*/
    }
    
    展开全文
  • 一元多项式表示及相加运算(Java表示) 思路 Java代码 import java.util.Scanner; public class OneVariablePolynomialDemo { /** * 判断两个指数谁大 * * @param e1 指数1 * @param e2 指数2...

    一元多项式的表示及相加运算(Java表示)

    思路

    Java代码

    import java.util.Scanner;
    
    public class OneVariablePolynomialDemo {
        /**
         * 判断两个指数谁大
         *
         * @param e1 指数1
         * @param e2 指数2
         * @return 如果e1>e2返回1,如果e1<e2返回-1,如果e1=e2返回0
         */
        private static int compare(int e1, int e2) {
            // 比较两项指数e1和e2,根据大小等三种情况返回1、-1,0
            if (e1 > e2) {
                return 1;
            } else if (e1 < e2) {
                return -1;
            } else {
                return 0;
            }
        }
    
        /**
         * 添加新结点到结果链表
         *
         * @param coef     系数
         * @param expon    指数
         * @param rearNode 结果链表
         * @return 返回添加成功的结果链表
         */
        public static PolynomialNode attach(int coef, int expon, PolynomialNode rearNode) {
            // 创建一个新结点并存储指数项和系数项
            PolynomialNode newNode = new PolynomialNode();
            newNode.setCoef(coef);
            newNode.setExpon(expon);
            newNode.setNext(null);
            // 将新结点插入到当前结果表达式的后面,现在尾结点变成了newNode
            rearNode.setNext(newNode);
            // 将尾结点指向新插入的结点newNode
            rearNode = newNode;
            // 返回链表
            return rearNode;
        }
    
        /**
         * * 输入的各种情况:
         * * (1)如果系数为1,则不输出系数;(需要判断指数是否为1或者为0亦或者为负数的情况)
         * * (2)如果系数为0,则不输出任何;
         * * (3)如果系数小于0,则在括号内输出负数;(需要判断指数是否为1或者为0亦或者为负数的情况)
         * * (4)如果指数为1,则不输出指数;
         * * (5)如果指数为0并且系数不为0则输出系数;
         * * (6)如果指数是负数则在括号内输出负数;
         *
         * @param node 要打印的结点
         */
        public static void printNode(PolynomialNode node) {
            String polynomial = "";
            // 循环链表
            while (node != null) {
                // 判断系数和指数
                if (node.getCoef() == 1) {
                    if (node.getExpon() == 1) {
                        polynomial += "+x";
                    } else if (node.getExpon() == 0) {
                        polynomial += "+" + node.getCoef();
                    } else if (node.getExpon() < 0) {
                        polynomial += "+" + node.getCoef() + "x^(" + node.getExpon() + ")";
                    } else {
                        polynomial += "+" + "x^" + node.getExpon();
                    }
                } else if (node.getCoef() == 0) {
                    polynomial += "";
                } else if (node.getCoef() < 0) {
                    if (node.getExpon() == 1) {
                        polynomial += "+(" + node.getCoef() + ")x";
                    } else if (node.getExpon() == 0) {
                        polynomial += "+(" + node.getCoef() + ")";
                    } else if (node.getExpon() < 0) {
                        polynomial += "+(" + node.getCoef() + ")x^(" + node.getExpon() + ")";
                    } else {
                        polynomial += "+(" + node.getCoef() + ")x^" + node.getExpon();
                    }
                } else {
                    if (node.getExpon() == 1) {
                        polynomial += "+" + node.getCoef() + "x";
                    } else if (node.getExpon() == 0) {
                        polynomial += "+" + node.getCoef();
                    } else if (node.getExpon() < 0) {
                        polynomial += "+" + node.getCoef() + "x^(" + node.getExpon() + ")";
                    } else {
                        polynomial += "+" + node.getCoef() + "x^" + node.getExpon();
                    }
                }
                node = node.getNext();
            }
            System.out.println(polynomial.substring(1, polynomial.length()));
        }
    
        /**
         * 一元多项式相加
         *
         * @param p1 一元多项式链表1
         * @param p2 一元多项式链表2
         * @return 返回相加的结果
         */
        public static PolynomialNode polyAdd(PolynomialNode p1, PolynomialNode p2) {
            PolynomialNode front, rear, temp;
            int sum;
            // 为方便表头插入,先产生一个临时空结点作为结果多项式链表头
            rear = new PolynomialNode();
            // 由front记录结果多项式头结点
            front = rear;
            // 当两个多项式都有非零项待处理时
            while (p1 != null && p2 != null) {
                // 根据比较结点的指数返回的值进行操作
                switch (compare(p1.getExpon(), p2.getExpon())) {
                    // P1中的数据项指数较大时
                    case 1:
                        // 将P1的结点放到结果链表中并返回成功的结果链表
                        rear = attach(p1.getCoef(), p1.getExpon(), rear);
                        // 并将P1结点指向它的下一个结点
                        p1 = p1.getNext();
                        break;
                    // P2中的数据项指数较大时
                    case -1:
                        // 将P2的结点放到结果链表中并返回成功的结果链表
                        rear = attach(p2.getCoef(), p2.getExpon(), rear);
                        // 将P2结点指向它的下一个结点
                        p2 = p2.getNext();
                        break;
                    // 两数据项指数相等
                    case 0:
                        // 当指数相等时,让系数相加
                        sum = p1.getCoef() + p2.getCoef();
                        // 如果相加的系数不为0(大于或小于0都可)
                        if (sum != 0) {
                            //将该结点放到结果链表中并返回成功的结果链表
                            rear = attach(sum, p1.getExpon(), rear);
                        }
                        // 让P1结点和P2结点都指向下一个结点元素
                        p1 = p1.getNext();
                        p2 = p2.getNext();
                        break;
                    default:
                        break;
                }
            }
            // 将未处理完的另一个多项式的所有结点依次复制到结果链表中
            for (; p1 != null; p1 = p1.getNext()) {
                rear = attach(p1.getCoef(), p1.getExpon(), rear);
            }
            for (; p2 != null; p2 = p2.getNext()) {
                rear = attach(p2.getCoef(), p2.getExpon(), rear);
            }
            rear.setNext(null);
            temp = front;
            // 使front指向结果多项式的第一个非零项
            front = front.getNext();
            return front;
        }
    
        public static void main(String[] args) {
            // 注意:一元多项式的各项要按照指数递减的顺序排列各项
            Scanner scanner = new Scanner(System.in);
    
            // 获取第一个多项式链表
            System.out.println("【注意:一元多项式的各项要按照指数递减的顺序排列各项】");
            System.out.print("请输入第一个多项式的项数:");
            PolynomialNode p1 = new PolynomialNode();
            // 保存头结点
            PolynomialNode front1 = p1;
            // 获取第一个多项式的项数
            int itemCount = scanner.nextInt();
            // 循环获取多项式的系数和指数
            for (int i = 1; i <= itemCount; i++) {
                System.out.print("第" + i + "项的系数是:");
                int coef = scanner.nextInt();
                System.out.print("第" + i + "项的指数是:");
                int expon = scanner.nextInt();
                // 创建新结点,将数据赋给结点元素
                PolynomialNode p = new PolynomialNode(coef, expon, null);
                p1.setNext(p);
                p1 = p;
            }
            // 打印第一个多项式
            System.out.print("p1(x)=");
            printNode(front1);
    
            // 获取第二个多项式链表
            System.out.print("请输入第二个多项式的项数:");
            PolynomialNode p2 = new PolynomialNode();
            // 保存头结点
            PolynomialNode front2 = p2;
            // 获取第二个多项式的项数
            int itemCount2 = scanner.nextInt();
            // 循环获取多项式的系数和指数
            for (int i = 1; i <= itemCount2; i++) {
                System.out.print("第" + i + "项的系数是:");
                int coef = scanner.nextInt();
                System.out.print("第" + i + "项的指数是:");
                int expon = scanner.nextInt();
                PolynomialNode p = new PolynomialNode(coef, expon, null);
                p2.setNext(p);
                p2 = p;
            }
            // 打印第一个多项式
            System.out.print("p2(x)=");
            printNode(front2);
    
            // 计算两个一元多项式相加
            System.out.print("p1(x)+p2(x)=");
            printNode(polyAdd(front1, front2));
        }
    }
    

    结点类PolynomialNode.java

    public class PolynomialNode {
        private int coef;// 存储的一元多项式的系数
        private int expon;// 存储的一元多项式的指数
        private PolynomialNode next;// 下一个结点引用指针
    
        public PolynomialNode() {
            super();
        }
    
        public PolynomialNode(int coef, int expon, PolynomialNode next) {
            super();
            this.coef = coef;
            this.expon = expon;
            this.next = next;
        }
    
        public int getCoef() {
            return coef;
        }
    
        public void setCoef(int coef) {
            this.coef = coef;
        }
    
        public int getExpon() {
            return expon;
        }
    
        public void setExpon(int expon) {
            this.expon = expon;
        }
    
        public PolynomialNode getNext() {
            return next;
        }
    
        public void setNext(PolynomialNode next) {
            this.next = next;
        }
    }
    

    测试

    测试1

    p1=3X^5+4X^4-X^3+2X-1

    p2=2X^4+X^3-7X^2+X

    p1+p2=3X^5+6X^4-7X^2+3X-1

    测试2

    p1=4X^3-3X^2+4-5X{^{-2}}

    p2=-4x^3+3x^2+3x^{_{-3}}

    p1+p2=4-5x^{_{-2}}+3x^{_{-3}}

    注:算法思路具体讲解请参考中国大学MOOC浙大数据结构课程。

    展开全文
  • 1)算法要求:进行一元多项式的加、减、求导、乘法运算,多项式在某点处的函数值。 2.)输入要求:输入以系数、指数对的形式输入,表示多项式的某项的次数和系数 多项式每一项输入可以不按顺序,可以次数重复,需做...
  • 链表实现一元多项式的加法和乘法 #include<bits/stdc++.h> using namespace std; typedef struct Node{ int ceof; int exp; struct Node* next; }Node; Node *read(string s) { Node *head,*middle,*near;...
  • 一元多项式加法运算

    2020-08-26 06:46:20
    今天小编就为大家分享一篇关于一元多项式加法运算,小编觉得内容挺不错的,现在分享给大家,具有很好的参考价值,需要的朋友一起跟随小编来看看吧
  • [PAT] 一元多项式的乘法与加法运算 C语言实现 [PAT] 02-线性结构1 一元多项式的乘法与加法运算 设计函数分别求两个一元多项式的乘积与和。 输入格式: 输入分2行,每行分别先给出多项式非零...
  • 明天继续完善 Status cmp(PElemType a, PElemType b) { if (a.expn&gt;=b.expn) return 1; else return 0; } void CreatPolyn... // 输入m项的系数和指数,建立表示一元多项式的有序链表P PLink ...
  • 1、实现方式:可采用线性表的顺序存储结构,但是当多项式的每个项的指数差别很大时,会浪费很...3、一元多项式的加法运算: 设La和Lb分别表示两个多项式。Lc表示和多项式。p,q,r分别表示指向单链表的当前项比较指数...
  • 完美的数据结构大作业之选。C语言+链表 实现。不用提前知道多项式项数,可以自动排序,可以合并同类项,可以进行加法、乘法运算。VS环境可运行,其他编程软件找到cpp复制粘贴即可
  • * 程序功能:一元多项式的代数运算 * 程序作者:Yannis Zhao * */ #include #include //数据元素数据结构 typedef struct{ float coef; //系数 int expn; //指数 }Term; //多项式数据结构 typedef struct ...
  • 一元多项式运算

    2012-01-29 16:10:35
    一元多项式的基本运算包括加减乘求导,用的是c语言,c++的也通用
  • C语言链表的入门题,里面提供了两种思路供参考,用链表来实现一元多项式的加减法,并按照一定规律输出。也是练习链表和排序算法的一道小实验,初学链表的小伙伴可以参考参考噢
  • 依据一元多项式相加的运算规则:对于两个一元多项式中全部指数同样的项。相应系数相加,若其和不为零,则构成“和多项式”中的一项。对于两个一元多项式中全部指数不同样的项,则分别复抄到“和多项式”中去。 #...
  • 不用提前知道多项式项数,可以自动排序,可以合并同类项,可以进行加法、乘法运算。//#include&lt;stdio.h&gt; //#include&lt;stdlib.h&gt; #include"stdafx.h" #include&lt;malloc.h...
  • 利用顺序表或链表表示两个一元多项式,并完成两多项式的乘法运算。按指数的升序输入第一个一元多项式polya各项的指数和系数,且以输入0 0结束,按指数的升序输入第一个一元多项式polyb各项的指数和系数。输出两一元...
  • 实验目的:掌握用线性表实现一元多项式的基本运算。 实验内容:使用链式存储实现一元多项式的加法、减法、乘法和求导。即: C(x)= A(x)+B(x);C(x)= A(x)-B(x) C(x)= A(x)*B(x) C(x)= A’(x) 菜单: 1)C :分别创建...
  • 输入:第一个一元多项式A; 第二个一元多项式B。 以(0,0)作为输入结束。 输出:多项式A和多项式B的和。 样例输入 5,3 7,8 9,15 0,0 2,0 6,3 -7,8 0,0 样例输出 2x^0+11x^3+9x^15 #include <stdio.h&...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,641
精华内容 2,256
关键字:

一元多项式的表示及运算