精华内容
下载资源
问答
  • 数据结构——一元多项式加法,使用数据结构线性表实现一元多项式加法
  • 数据结构 C语言 动态链表 议员多项式加减法 数据结构C语言 一元多项式的加减法算法实现 代码,用vs运行,已测试成功运行,
  • 数据结构一元多项式的表示与 相加 实验一 一元多项式的表示与相加 实验目的 1.复习并熟练掌握数据结构所使用程序设计 语言 C 语言 2.学会单步跟踪调试自己程序 3.加深对线性表特别是链表知识理解和掌握 并能够...
  • 数据结构一元多项式的相加 嗯,之前找到总是不太能运行,所以就传了这个上来了
  • 数据结构—— 一元多项式的加法运算

    万次阅读 多人点赞 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函数,在每一次存入多项式的值的时候,新的线性表就构成了一个新的链表,那么就算多项式中有相同指数的项,到了存储进新的线性表中的时候,也会和前面已经存过的指数相同项进行一次系数的相加而不是增多一个节点,但是这个方法每次都要遍历前面已经存储过的节点时间代价有些大是它的缺点。

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

    展开全文
  • 数据结构一元多项式相乘: 题目说明: 要求采用链表形式,求两个一元多项式的乘积:h3 = h1*h2。函数原型为:void multiplication( NODE * h1, NODE * h2, NODE * h3 )。 输入: 输入数据为两行,分别表示两个...

    (数据结构)一元多项式相乘:

    题目说明:

    要求采用链表形式,求两个一元多项式的乘积:h3 = h1*h2。函数原型为:void multiplication( NODE * h1, NODE * h2, NODE * h3 )。

    输入:

    输入数据为两行,分别表示两个一元多项式。每个一元多项式以指数递增的顺序输入多项式各项的系数(整数)、指数(整数)。
      例如:1+2x+x²表示为:<1,0>,<2,1>,<1,2>,

    输出:

    以指数递增的顺序输出乘积: <系数,指数>,<系数,指数>,<系数,指数>,
      零多项式的输出格式为:<0,0>,

    说明:本题目有预设代码,只要提交你编写的函数即可。

    预设代码

    前置代码:

    /* PRESET CODE BEGIN - NEVER TOUCH CODE BELOW */  
     
    #include <stdio.h>  
    #include <stdlib.h>  
      
    typedef struct node  
    {   int    coef, exp;  
        struct node  *next;  
    } NODE;  
      
    void multiplication( NODE *, NODE * , NODE * );  
    void input( NODE * );  
    void output( NODE * );  
      
    void input( NODE * head )  
    {   int flag, sign, sum, x;  
        char c;  
      
        NODE * p = head;  
      
        while ( (c=getchar()) !='\n' )  
        {  
            if ( c == '<' )  
            {    sum = 0;  
                 sign = 1;  
                 flag = 1;  
            }  
            else if ( c =='-' )  
                 sign = -1;  
            else if( c >='0'&& c <='9' )  
            {    sum = sum*10 + c - '0';  
            }  
            else if ( c == ',' )  
            {    if ( flag == 1 )  
                 {    x = sign * sum;  
                      sum = 0;  
                      flag = 2;  
              sign = 1;  
                 }  
            }  
            else if ( c == '>' )  
            {    p->next = ( NODE * ) malloc( sizeof(NODE) );  
                 p->next->coef = x;  
                 p->next->exp  = sign * sum;  
                 p = p->next;  
                 p->next = NULL;  
                 flag = 0;  
            }  
        }  
    }  
      
    void output( NODE * head )  
    {  
        while ( head->next != NULL )  
        {   head = head->next;  
            printf("<%d,%d>,", head->coef, head->exp );  
        }  
        printf("\n");  
    }  
      
    int main()  
    {   NODE * head1, * head2, * head3;  
      
        head1 = ( NODE * ) malloc( sizeof(NODE) );  
        input( head1 );  
      
        head2 = ( NODE * ) malloc( sizeof(NODE) );  
        input( head2 );  
      
        head3 = ( NODE * ) malloc( sizeof(NODE) );  
        head3->next = NULL;  
        multiplication( head1, head2, head3 );  
      
        output( head3 );  
        return 0;  
    }  
      
    /* PRESET CODE END - NEVER TOUCH CODE ABOVE */  
    

    测试用例1:

    测试输入:

    <1,0>,<2,1>,<1,2>,↵
    <1,0>,<1,1>,↵

    期待输出:

    <1,0>,< 3,1>,< 3,2>,<1,3>,↵

    测试用例2:

    测试输入:

    <0,0>,↵
    <1,20>,<-8,40>,↵

    期待输出:

    <0,0>,↵

    测试用例3:

    测试输入:

    <1,20>,<-8,40>,↵
    <0,0>,↵

    期待输出:

    <0,0>,↵

    测试用例4:

    测试输入:

    <-1,0>,<1,1>,↵
    <1,0>,<1,1>,↵

    期待输出:

    <-1,0>,<1,2>,↵

    测试用例5:

    测试输入:

    <5,0>,<10,1>,↵
    <2,0>,< 3,1>,<4,2>,<5,3>,↵

    期待输出:

    <10,0>,<35,1>,<50,2>,<65,3>,<50,4>,↵

    代码如下:

    void multiplication(NODE *head1, NODE *head2, NODE *head3)   
    {   
       	NODE*p1 = head3; NODE*p2 = head3;   
      	NODE*h1 = head1->next; NODE*h2 = head2->next;   
           
      while (h1)   
     {   
          while (h2)   
         {   
              int coef = h1->coef*h2->coef;   
                if (coef == 0)   
             	{   
                  h2 = h2->next;   
                  continue;   
             	}   
             	
             	int exp = h1->exp+h2->exp;   
               if (p1->next == NULL)   
               {   
                  NODE*tmp = (NODE*)malloc(sizeof(struct node));   
                 tmp->coef = coef; tmp->exp = exp;   
                    p1->next = tmp;   
                 tmp->next = NULL;   
               }   
              
              else   
              {   
                  while (p2->next && exp > p2->next->exp)   
                  {   
                      p2 = p2->next;   
                  }   
                  	NODE*tmp = p2->next;   
                   
                   if (p2->next == NULL)   
                   {   
                      NODE*pnew = (NODE*)malloc(sizeof (struct node));   
                       pnew->coef = coef;   
                      pnew->exp = exp;   
                        p2->next = pnew;   
                        pnew->next = NULL;   
                   }   
                   
                  else if (tmp->exp == exp)   
                  {   
                      tmp->coef += coef;   
                      if (tmp->coef == 0)   
                      {   
                          NODE*mark = tmp->next;   
                          p2->next = mark;   
                            free(tmp);   
                      }   
                  }   
                 
                 else if (tmp->exp > exp)   
                 {   
                      NODE*pnew = (NODE*)malloc(sizeof (struct node));   
                       pnew->coef = coef;   
                      pnew->exp = exp;   
                        p2->next = pnew;   
                        pnew->next = tmp;   
                  }   
             }   
             
              h2 = h2->next;   
              p2 = head3;   
           }   
          h2 = head2->next;   
           h1 = h1->next;   
      }   
      
      if (head3->next == NULL)   
      {   
          NODE*end = (NODE*)malloc(sizeof(struct node));   
          end->coef = 0;   
          end->exp = 0;   
          end->next = head3->next;   
          head3->next = end;   
      }   
    }  
    
    展开全文
  • 数据结构 编程 一元多项式的计算 原代码
  • 数据结构的相关知识中的链表实现一元多项式的运算,深入理解链表的插入删除等操作。
  • 数据结构设计一元多项式的加减 此文件为压缩文件 在VC++6.0 环境下进行编译
  • 数据结构一元多项式求和实验报告xx大学xxx学院算法与数据结构试验报告设计名称: 算法与数据结构设计题目: 链表应用学生学号: xx专业班级: xx学生姓名: xx学生成绩:指导教师(职称):课题工作时间: 2012年4月...

    数据结构一元多项式求和实验报告

    xx大学

    xxx学院

    算法与数据结构试验报告

    设计名称: 算法与数据结构

    设计题目: 链表的应用

    学生学号: xx

    专业班级: xx

    学生姓名: xx

    学生成绩:

    指导教师(职称):

    课题工作时间: 2012年4月10日

    说明:

    实验课程类别:课程内实验

    实验课程性质:必修

    适用专业、年级:2010级计算机工程、计算机网络

    开课院、系:计算机科学与工程学院计算机工程教研室

    学时:18

    编写依据:《算法与数据结构》实验教学大纲

    修订时间:2012年2月

    《算法与数据结构》课程实验指导书(以下简称:指导书)是针对计算机学院所开设的对应课程的上机实验而编写的教学文件,供学生上机实验时使用。

    上机的工作环境要求:Windows 2000或以上操作系统、VC++ 6.0或者其它高级程序设计语言。

    学生应按指导教师的要求独立完成实验,并按要求撰写实验报告。

    每一个实验,编程上机调试并且提交电子文档实验报告,以学号姓名作为文件名上传。报告内容至少包含如下内容:

    学生基本情况:专业班级、学号、姓名

    实验题目、实验内容

    设计分析

    源程序代码

    测试用例(尽量覆盖所有分支)

    实验总结

    一.实验内容与学时分配

    序次实验

    题目实验

    类型基本技能训练学时一线性结构综合应用综合性(1)掌握线性结构的常用操作;

    (2)能够应用线性结构解决比较简单的问题。10二非线性结构综合应用综合性(1)掌握树形、图形结构的插入、删除、查找等算法;

    (2)能够应用二叉树解决比较简单的问题。4三查找技术综合应用综合性(1)熟练熟练掌握常用的排序方法,并掌握用高级语言实现排序算法的方法;深刻理解排序的定义和各种排序方法的特点,并能加以灵活应用;了解各种方法的排序过程及其依据的原则,并掌握各种排序方法的时间复杂度的分析方法。把任意给定的两个一元多项式P(x)?,Q(x)?输入计算机,计算它们的和并输出计算结果。

    源程序代码

    #include

    #include

    /*链表数据类型定义*/

    typedef struct LNode

    {

    int x,z;

    struct LNode *next;

    }LinkList;

    void OutLinkList(LinkList *L); /*输出函数*/

    void PutLinkList(LinkList *&L,int n); /*输入函数*/

    LinkList *AddLinkList(LinkList *a,LinkList *b); /*求和函数*/

    void OutXLinkList(LinkList *L);

    void OutZLinkList(LinkList *L);

    void main()

    {

    int n,m;

    LinkList *a,*b,*c;

    printf("\t\t\t本程序可以完成两个一元多项式的加法运算。\n");

    printf("请输入一元多项式a的项数m:");

    scanf("%d",&m);

    printf("请按照从低次到高次的顺序依此输入一元多项式a的系数和指数:\n");

    PutLinkList(a,m);

    printf("a=");

    OutLinkList(a);

    printf("请输入一元多项式b的项数n:");

    scanf("%d",&n);

    printf("请按照从低次到高次的顺序依此输入一元多项式b的系数和指数:\n");

    PutLinkList(b,n);

    printf("b=");

    OutLinkList(b);

    c=AddLinkList(a,b);

    printf("两个多项式的和为:\na+b=");

    OutLinkList(c);

    }

    void PutLinkList(LinkList *&L,int n)

    {

    LinkList *s,*r;

    L=(LinkList *)malloc(sizeof(LinkList));

    r=L;

    for(int i=0;i

    {

    s=(LinkList *)malloc(sizeof(LinkList));

    printf("请输入第%d项的系数:",i+1);

    scanf("%d",&

    展开全文
  • 数据结构——一元多项式加法、减法、乘法运算实现,可以直接使用
  • 利用链式存储实现存储一元多项式,并计算两个一元多项式之和。一元多项式由系数和指数构成。 1、create()存储系数指数:首先建立一个头结点headLnode,从headLnode->next开始存入系数和指数,只有系数是0时,才表示...

    一、实验原理

    利用链式存储实现存储一元多项式,并计算两个一元多项式之和。一元多项式由系数和指数构成。

    1、create()存储系数指数:首先建立一个头结点headLnode,从headLnode->next开始存入系数和指数,只有系数是0时,才表示这个多项式的结束,否则每次把系数和指数存入结点后,就把指针向后移动一个接着存入,直到输入的系数是0为止。返回的是一个带头结点的链表

    2、Print()输出链表:只要当前指针指向的结点不是空,就把系数和指数输出,直到系数为0为止

    3、Compare()比较指数大小:根据这个结果确定先插入哪个结点

    4、AddLine()链表相加:先让hc=lc=ha,即相当于给hc和lc创建了一个头结点,然后以后通过比较得到的结点都插入了hc为头结点的链表中。

          比较:

           (1)ha为空,hb不为空,直接return(hb)

           (2)ha和hb都不空,通过比较指数大小,决定插入hc的顺序

    二、参考程序

    #include<stdio.h>

    #include<stdlib.h>

    #define NULL 0

    typedef struct Lnode

    {

      int coef;  //定义系数变量

      int exp;   //定义指数变量

      struct Lnode *next;   //定义指针next变量

     } Lnode,*LinkList;

     

     /*建立多项式列表*/

    LinkList  create()

    {                     

     int n;

      LinkList headLnode;

      LinkList  head;     

      LinkList p1,p2;    //定义p1,p2指针

      n=0;

      printf("请输入多项式(输入的数必须是整数,指数须从小到大依次输入,系数为零表示多项式结束)\n");

      p1=p2= ( LinkList)malloc(sizeof(Lnode)); /*开辟一个新单元*/

      scanf("%d%d",&p1->coef,&p1->exp);      /*录入多项式*/

      headLnode=(LinkList)malloc(sizeof(Lnode));

      if (p1->coef==0){//开始输入的就是0,创建空链表

       head=NULL;

      }

      else

      {

        while(p1->coef!=0)

          { n++;

            if(n==1){

    head=p1;//记录第一个输入的是头结点

    }

            else{

     p2->next=p1;//P1指向下一个结点,并输入数据

    }

            p2=p1;

            p1=( LinkList)malloc(sizeof(Lnode));

            scanf("%d%d",&p1->coef,&p1->exp);

           }

         p2->next=0;

         headLnode->next=head;//把头结点与第一个结点相连

        }

          return(headLnode);

         }

    /* 以下是输出多项式的函数 */

    void print (LinkList p)

         {

           LinkList p0;   //定义p0指针

           p0=p->next;

             if(p0!=NULL){ //只要不是头结点就输出

             do

              {

                printf("%dx的%d次幂",p0->coef,p0->exp);

                p0=p0->next;

                if(p0!=NULL){

     printf("+");

    }

              }while(p0!=0);

            }

               else  {

        printf("  空多项式!!");

       }

       printf("\n");

     }

     

    /*比较两个指数的大小的函数*/

    int compare(int m,int n)    

    {

     int j;

     if (m<n) j=-1;

     if (m==n) j=0;

     if (m>n) j=1;

     return(j);

    }

    /*两个非空多项式相加*/

    LinkList  AddLine(LinkList  ha, LinkList  hb)   

    {

     LinkList  la, lb, lc,hc;       //定义三个指针la,lb,lc

     int a,b,sum;

     lc=hc=ha;

     la=ha->next;//从头结点的下一个元素开始

     lb=hb->next;

     //如果ha为空,hb不为空,直接返回hb

     if ((ha->next==NULL)&&(hb->next!=NULL)){

        return(hb);  

    }   

    //如果ha,hb都不为空,根据指数大小,移动指针lc,形成新的链表hc

     while ((la!= NULL)&&(lb!= NULL))     //当两个多项式都不为空时

       {

        a=la->exp;     //将la的指数赋给a

    b=lb->exp;      //将lb的指数赋给b

        switch( compare(a,b) )     /*比较当前结点指数的大小 */

         {

          case -1:     //a<b,lc指向la

     {   lc->next =la;

      lc=la;

      la=la->next;//la向后移

                break;

     }

          case 0:   //a=b

             {

      sum=la->coef+lb->coef;

        if(sum!=0)//不等于0时,把sum值存入la的系数中,

          {               /* 将其不为零的系数和保存 */

               

          la->coef=sum;

          lc->next=la;

     lc=la;

    la=la->next;

    //释放掉lb,利用ha

    ha=lb;

    lb=lb->next;

    free(ha);

     

          }

        else  //两系数之和为0

         {   /* 分别删除系数和为零的对应的两个结点 */

           

       

        ha=la;

        la=la->next;

        free(ha);

        ha=lb;

        lb=lb->next;

        free(ha);

     

       } /* 刚开始时特殊处理头结点 */

     

       break;

      }

          case 1:     //a>b

      {              /* 将指数小的项插入到la的前部 */

        lc->next=lb;

        lc=lb;

        lb=lb->next;

        break;

      }

        }  /*end swtich*/

      }   /*end while*/

      //当两个链表长度不一致时,会有一个先都插入到lc中

       if (lb!= NULL ){

       lc->next=lb;

      }

      else{

       lc->next=la;

      }

     

       return(hc);

    } /*end AddLine */

     /*主程序*/

     main()

     {

      LinkList  la,lb,lc;

      printf("请输入多项式La: ");

      la=create();

      printf("请输入多项式Lb: ");

      lb=create();

      printf("多项式La:\n");

      print(la);

      printf("多项式Lb:\n");

      print(lb);

      printf("多项式La与Lb的和是: \n");

      lc=AddLine(la,lb);

      print(lc);

      }

     

    /*运行结果:请输入多项式La: 请输入多项式(输入的数必须是整数,指数须从小到大依次输入,系数为零表示多项式结束)

    2 1

    3 2

    4 5

    0 9

    请输入多项式Lb: 请输入多项式(输入的数必须是整数,指数须从小到大依次输入,系数为零表示多项式结束)

    2 3

    4 4

    5 6

    7 8

    0 9

    多项式La:

    2x的1次幂+3x的2次幂+4x的5次幂

    多项式Lb:

    2x的3次幂+4x的4次幂+5x的6次幂+7x的8次幂

    多项式La与Lb的和是:

    2x的1次幂+3x的2次幂+2x的3次幂+4x的4次幂+4x的5次幂+5x的6次幂+7x的8次幂

     

    --------------------------------

    Process exited after 24.31 seconds with return value 0

    请按任意键继续. . .

    */

     

     

     

    展开全文
  • 数据结构一元多项式(线性表)

    千次阅读 多人点赞 2020-07-24 15:37:04
    分别采用了顺序表、链表方式实现一元多项式完成多项式加、减运算并求值 1、实现功能描述: (1) 输入和输出: 需要输入信息有多项式系数和指数,用来向系统动态申请内存;系数和指数用来构造每个结点,形成表...
  • 数据结构-一元多项式加法

    千次阅读 2018-12-03 19:12:32
    7-17 一元多项式的加法 (20 分) 设计程序求两个一元多项式的和。 输入格式: 输入分2行,每行分别先给出多项式非零项个数,再以指数递降方式输入一个多项式非零项系数和指数。数字间以空格分隔。 输出格式: ...
  • 用于实现一元多项式的创建,相加,相减,相乘操作,适合大学新生对计算机软件学习
  • 使用c语言实现一元多项式线性表加减运算 #include<bits/stdc++.h> typedef struct component{//定义结构体 int coef;//系数 int inde;//指数 struct component *next;//下一个表地址 }...
  • 1467 数据结构一元多项式加法

    千次阅读 2016-04-01 19:26:53
    数据结构一元多项式加法 Time Limit(Common/Java):1000MS/3000MS Memory Limit:65536KByte Description 给定2个一元多项式,计算它们和。例如:f(x)=5x3-3x2+1和g(x)=3x4+3x2+x,则h(x)=f(x)+g(x)=3x4+5x3+...
  • 建立一元多项式的链式存储 用单链表存储多项式结点结构如下: struct Polynode { int coef; int exp; Polynode *next; } 多项式相加过程 1.两个多项式中所有指数相同对应系数相加, 若和不为零...
  • 一元多项式运算器分析与实现 首先,需要解决一元多项式在计算机中存储问题。 对于一元多项式: P = p0 + p1x + …+pnx^n 在计算机中,可以用一个线性表来表示: P = (p0,p1,…,pn), 但是对于形如 S(x) = 1 + 5x^...
  • 这道题呢,我写超级长- - 我觉得可以缩减很多,...02-线性结构2 一元多项式的乘法与加法运算(20 分) 设计函数分别求两个一元多项式的乘积与和。 输入格式: 输入分2行,每行分别先给出多项式非零项个数,...
  • 数据结构一元多项式的乘法与加法运算

    千次阅读 多人点赞 2019-04-10 14:16:12
    设计函数分别求两个一元多项式的乘积与和。 输入格式: 输入分2行,每行分别先给出多项式非零项个数,再以指数递降方式输入一个多项式非零项系数和指数(绝对值均为不超过1000整数)。数字间以空格分隔。 输出...
  • 7-2一元多项式的乘法与加法运算(15分) 时间限制: 200 ms 内存限制: 64 MB 代码长度限制: 16 KB 设计函数分别求两个一元多项式的乘积与和。 输入格式: 输入分2行,每行分别先给出多项式非零项个数,再以指数...
  • 用 C语言实现一元多项式的运算(相加,相减,相乘) 1.创建多项式时,无论指数项按什么顺序输入,输出均能实现以升幂顺序输出,且输入时有相同指数项时能够实现合并。 2.能够代入确切X计算出最终多项式值。 ...
  • 7-1 一元多项式的乘法与加法运算 (20 分) 设计函数分别求两个一元多项式的乘积与和。 输入格式: 输入分2行,每行分别先给出多项式非零项个数,再以指数递降方式输入一个多项式非零项系数和指数(绝对值均为不...
  • 一元多项式表示及相加完整代码是一个链表应用例子。下面给出了完整代码,在VC++ 6.0以及 Dev-C++ 下编译通过。 测试数据: A多项式输入: 7 0 3 1 9 8 5 17 0 0 B多项式输入: 8 1 22 7 -9 8 0 0 ...
  • 数据结构一元多项式计算器

    千次阅读 2020-04-22 04:11:32
    这个我也是借鉴网上,加了一些自己理解,改了一些小东西...输入第一个多项式为:2x^3-4x^5 输入第二个多项式为:4x^4+4x^5 #include <stdio.h> #include <stdlib.h> typedef struct pol...
  • 中南大学 数据结构与算法课程实验 实验报告 题目 实验一线性表操作 学生姓名 谭淇蔚 学生学号 3901130721 专业班级 软件工程 1307班 完成日期 2014 年 3 月 31 日星期一 实验一线性表操作一元多项式相加 1....
  • 本文所有代码均为伪码,仅阐述算法基本思想——《数据结构》清华大学出版社一元多项式的表示采用链式存储结构来实现,基本操作和链表合并类似。以下为算法部分:typedef struct{//项表示,多项式项作为...
  • 设计函数分别求两个一元多项式的乘积与和。 输入格式: 输入分2行,每行分别先给出多项式非零项个数,再以指数递降方式输入一个多项式非零项系数和指数(绝对值均为不超过1000整数)。数字间以空格分隔。 输出...
  • 数据结构一元多项式计算器(详解)

    千次阅读 多人点赞 2020-04-21 22:04:03
    一元多项式计算器没有用链表写这个多项式之前,哇,觉得这个好难啊!!!链表是人干出来事情??写完了才发现,“真香警告”。(︶^︶)我才不会承认。 构建输入函数 不管会不会,输入是必须,先把数据读入...

空空如也

空空如也

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

数据结构的一元多项式

数据结构 订阅