精华内容
下载资源
问答
  • 利用C++,实现线性表的顺序存储,并利用线性表的顺序存储结构求解一元多项式的值。顺序表是数据结构课程中的重要的基础内容,应该熟练掌握。
  • 本案例实现了一下功能 1)首先判定多项式是否稀疏 2)分别采用顺序和动态存储结构实现; 3)结果M(x)中无重复阶项和无零系数项; 4)要求输出结果的升幂和降幂两种排列情况
  • 数据结构—— 一元多项式的加法运算

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

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

    展开全文
  • 对简单的一元多项式相加、相减、求导运算。 二、实验目的 实现对简单的一元多项式相加、相减、求导运算。 三、实验设计 1.逻辑结构 逻辑结构是指数据元素之间的逻辑关系,即从逻辑关系上描述数据。它与数据存储...

    实验报告格式规范,包括以下内容:(正文 宋体五号 )

    一、问题描述(标题黑体小四)

    对简单的一元多项式相加、相减、求导运算。

    二、实验目的

    实现对简单的一元多项式相加、相减、求导运算。

    三、实验设计

    1.逻辑结构

    逻辑结构是指数据元素之间的逻辑关系,即从逻辑关系上描述数据。它与数据的存储无关,是独立于计算机的。数据的逻辑结构分为线性结构和非线性结构,线性表是典型的线性结构;集合、树和图是典型的非线性结构。数据的逻辑结构分类见图1-1。

    • 集合结构中的数据元素之间除了 “同属于一个集合”的关系外,别无其他关系。
    • 线性结构结构中的数据元素之间只存在一对一的关系。
    • 树形结构结构中的数据元素之间存在一对多的关系。
    • 图状结构或网状结构结构中的数据元素之间存在多对多的关系。

    一般来讲,一个一元多项式,按照升幂写成

    多项式由(n+1)个系数唯一确定,按照原理上可以用线性表P来表示,实现计算机处理。
    image

    2.存储结构

    存储结构是指数据结构在计算机中的表示(又称映像),也称物理结构。它包括数据元素的表示和关系的表示。数据的存储结构是逻辑结构用计算机语言的实现,它依赖于计算机语言。数据的存储结构主要有:顺序存储、链式存储、索引存储和散列存储。

    • 顺序存储:把逻辑上相邻的元素存储在物理位置上也相邻的存储单元里,元素之间的关系由存储单元的邻接关系来体现。其优点是可以实现随机存取,每个元素占用最少的存储空间;缺点是只能使用相邻的一整块存储单元,因此可能产生较多的外部碎片。
    • 链接存储:不要求逻辑上相邻的元素在物理位置上也相邻,借助指示元素存储地址的指针表示元素之间的逻辑关系。其优点是不会出现碎片现象,充分利用所有存储单元;缺点是每个元素因存储指针而占用额外的存储空间,并且只能实现顺序存取。
    • 索引存储:在存储元素信息的同时,还建立附加的索引表。索引表中的每一项称为索引项,索引项的一般形式是:(关键字,地址)。其优点是检索速度快;缺点是增加了附加的索引表,会占用较多的存储空间。另外,在增加和删除数据时要修改索引表,因而会花费较多的时间。
    • 散列存储:根据元素的关键字直接计算出该元素的存储地址,又称为Hash存储。其优点是检索、增加和删除结点的操作都很快;缺点是如果散列函数不好可能出现元素存储单元的冲突,而解决冲突会增加时间和空间开销。

    如果用顺序表p[n]进行存储,下标代表指数,所存储的值代表系数。这样便可实现多个一元多项式的相加相减以及求导运算。但是对于处理
    image
    就需要开辟长度为1001的线性表,显然浪费空间。故可以将指数和系数分开存储。
    一般情况下,对于一元n次多项式可以写成
    image
    显然,可以用一个长度为m且每个元素包含俩个数据项(系数项和指数项)的线性表((p1,e1),(p2,e2),…,(pn,en))唯一确定多项式p(x)。
    线性表有两种存储结构,相应的采用线性表表示的一元多项式也有两种存储结构。如果只对多项式“求值”等不改变多项式的系数和指数的运算,则可以用顺序存储结构,否则应该采用链式存储结构。本次对一元多项式的操作是相加相减求导运算,故需要使用链式存储结构

    比如
    如下图所示,为一元多项式 A(x)=7+3x+9x8+5x17 和 B(x)=8x+22x7-9x8 的链表表示图:

    image

    一元多项式的存储结构定义描述如下:

    typedef struct
    {
        float coef;//系数
        int expn;//指数
        struct UNARY *next;//指针域
    } UNARY;
    
    

    3.算法设计思想

    如果两个多项式相加(减),根据两个多项式相加的规则:两个指数项相同的对应系数相加(减),如果系数和(差)不为零,则和(差)作为系数和指数一起构成“和(差)多项式”;如果两个系数不同,则分别复制“和(差)多项式”中去。

    当两个一元多项式相加时,需遵循如下的运算规则。假设指针 qa 和qb 分别指向多项式 A 和多项式 B 中当前进行比较的某个结点,则比较两个结点的指数项,有以下 3 种情况:

    • 指针 qa 所指结点的指数值小于指针 qb 所指结点的指数值,则应摘除 qa 所指结点插入到“和多项式”链表中去;
    • 指针 qa 所指结点的指数值大于指针 qb 所指结点的指数值,则应摘除 qb 所指结点插入到“和多项式”链表中去;
    • 指针 qa 所指结点的指数值等于指针 qb 所指结点的指数值,则将两个结点的系数相加:若和不为 0 ,则修改 qa 所指结点的系数值,- 同时释放qb所指结点;若和为 0,则应从多项式 A 的链表中删除相应结点,并释放指针 qa 和 qb 所指结点。

    如果对多项式进行求导,根据多项式的求导规则:系数与指数相乘,指数减1;如果指数为零,本项为零,不再复制到新的多项式中

    4.输入、输出设计

    输入设计
    首先对第一个链表进行输入
    输入格式(系数+指数)
    每次对是否继续输入该链表进行输入判断
    输入格式(1:继续 0:结束)

    输入选择
    输入格式(1:求导,2:加减运算)

    输入运算类型
    输入格式(+/-)

    输出设计
    依次输出链表中的系数和指数
    输出格式(系数+指数)

    四、主要代码

    /*
     *对一元多项式进行升幂排序
     *输入:一元多项式链表
     *输出:升幂排序的一元多项式链表
     *
    */
    UNARY* Increasing(UNARY *LA,UNARY *LB)
    {
         UNARY *head,*end,*pre,*cur,*next,*temp;
        head = LA;//以及LB
        end = NULL;
    
        //冒泡排序:将 最小/最大 的节点后移至当前的最后一位。
        while(head->next != end)
        {
            for(pre = head,cur = head->next,next = cur->next; next != end; pre = pre->next,cur = cur->next,next = next->next)
            {
                if(cur->expn > next->expn)
                {
                    cur->next = next->next;
                    pre->next = next;
                    next->next = cur;
                    temp = next;
                    next = cur;
                    cur = temp;
                }
    
            }
            end = cur;
        }
    }
    
    float  add_ab(float A,float B)
    {
    
        return A+B;
    }
    float subtract_ab(float A,float B)
    {
    
        return A - B;
    }
    
    //升幂的一元多项式的相加与相减
    UNARY* unaryAdd_Sub(UNARY *LA,UNARY *LB,char method)
    {
        //LA作为输出链
        UNARY *r,*s,*p,*q;
        int cmp;
        p = LA->next;//用于比较
        q = LB->next;//用于比较
        s = LA;//用于记录p的前置
        r = LB;//用于记录q的后置
    
        while(p!=NULL && q!=NULL)
        {
            if(p->expn<q->expn) cmp = -1;//当p指数小于q指数,p后移
            else if(p->expn>q->expn) cmp = 1;//当p指数大于q指数,q为p的前置,q后移
            else cmp = 0;//pq指数相同,进行加/减运算
            switch(cmp)
            {
            case -1:
            {
                s = p;
                p = p->next;
            };
            break;
    
    
            case 0:
            {
                float x;
                if(method == '+')
                {
                     x = add_ab(p->coef,q->coef);
    
                }
                else if(method == '-')
                {
                    x = subtract_ab(p->coef,q->coef);
                }
    
    
                if((int)x!=0)
                {
                    p->coef = x;
                    s = p;
                    p = p->next;
    
                    r->next =q->next;
                    free(q);
                    q = r->next;
    
                }
                else
                {
                    //删除LA节点
                    s->next = p->next;
                    free(p);
                    p = s->next;
                    //删除LB节点
                    r->next =q->next;
                    free(q);
                    q = r->next;
    
                }
            };
            break;
            case 1:
                {
                    r->next = q->next;
                    q->next = s->next;
                    s->next = q;
                    s = q;
                    q = r->next;
                };
                break;
    
    
    
            }
        }
        if(q!=NULL)
        {
            //因为 前面的结束条件 p = null 所以 p的前置s位于链表的尾部,s连接q
            s->next = q;
        }
        free(LB);
        return LA;
    
    
    
    
    }
    
    /*对一元多项式进行求导
     *输入:一元多项式链表
     *输出:求导后的一元多项式链表
     *所谓求导:系数与指数相乘,指数减1;如果指数为零,本项为零,不再复制到新的多项式中
    */
    
    UNARY* Derivation(UNARY *LA,UNARY *LB)
    {
    
        UNARY *headLA,*headLB;
        headLA = LA;
        headLB = LB;
    
    
        while(headLA->next!=NULL)
        {
            headLA = headLA->next;
            headLA->coef = headLA->coef*headLA->expn;
            if(headLA->expn!=0)
            {
                 headLA->expn -= 1;
            }
            else
            {
                headLA->expn = 0;
            }
    
    
        }
        while(headLB->next!=NULL)
        {
            headLB = headLB->next;
            headLB->coef = headLB->coef*headLB->expn;
            if(headLB->expn!=0)
            {
                 headLB->expn -= 1;
            }
            else
            {
                headLB->expn = 0;
            }
    
    
        }
    
    }
    

    五、程序运行结果截图

    image
    image

    六、遇到的问题和解决方法

    问题:刚开始考虑的一元多项式默认是升幂,对于乱序的一元多项式不知道如何解决
    解决方法:对乱序的一元多项式进行排序,首先考虑的是值传递 但是代码过于复杂,无论是时间复杂度,还是空间复杂度 都高于地址交换
    唯一的好处是逻辑简单;故本次采用地址交换的方式进行对乱序的一元二次多项式进行升幂排序,主要算法就是冒泡排序;需要6个节点并且是前后继的关系,每次后移加判断;
    问题:对于’零‘这个特殊项的处理
    解决方法:1.如果零系数出现在定义多项式阶段,直接不进行连接主链表,并且释放该空间
    2.如果零系数出现在加减运算阶段,进行删除两链表节处理,并且释放该空间
    3.如果零指数出现在求导运算阶段,删除节点,并释放空间

    七、完整代码

    点击查看代码
    #include <stdio.h>
    #include <stdlib.h>
    typedef struct
    {
        float coef;//系数
        int expn;//指数
        struct UNARY *next;
    } UNARY;
    
    float  add_ab(float A,float B)
    {
    
        return A+B;
    }
    float subtract_ab(float A,float B)
    {
    
        return A - B;
    }
    
    //升幂的一元多项式的相加与相减
    UNARY* unaryAdd_Sub(UNARY *LA,UNARY *LB,char method)
    {
        //LA作为输出链
        UNARY *r,*s,*p,*q;
        int cmp;
        p = LA->next;//用于比较
        q = LB->next;//用于比较
        s = LA;//用于记录p的前置
        r = LB;//用于记录q的后置
    
        while(p!=NULL && q!=NULL)
        {
            if(p->expn<q->expn) cmp = -1;//当p指数小于q指数,p后移
            else if(p->expn>q->expn) cmp = 1;//当p指数大于q指数,q为p的前置,q后移
            else cmp = 0;//pq指数相同,进行加/减运算
            switch(cmp)
            {
            case -1:
            {
                s = p;
                p = p->next;
            };
            break;
    
    
            case 0:
            {
                float x;
                if(method == '+')
                {
                     x = add_ab(p->coef,q->coef);
    
                }
                else if(method == '-')
                {
                    x = subtract_ab(p->coef,q->coef);
                }
    
    
                if((int)x!=0)
                {
                    p->coef = x;
                    s = p;
                    p = p->next;
    
                    r->next =q->next;
                    free(q);
                    q = r->next;
    
                }
                else
                {
                    //删除LA节点
                    s->next = p->next;
                    free(p);
                    p = s->next;
                    //删除LB节点
                    r->next =q->next;
                    free(q);
                    q = r->next;
    
                }
            };
            break;
            case 1:
                {
                    r->next = q->next;
                    q->next = s->next;
                    s->next = q;
                    s = q;
                    q = r->next;
                };
                break;
    
    
    
            }
        }
        if(q!=NULL)
        {
            //因为 前面的结束条件 p = null 所以 p的前置s位于链表的尾部,s连接q
            s->next = q;
        }
        free(LB);
        return LA;
    
    
    
    
    }
    UNARY* creatList(UNARY *LA,UNARY *LB)
    {
    
        LA->next = NULL;
    
        LB->next = NULL;
        UNARY *node;
        int choice;
    
       int i = 1;
        while(1)
        {
            printf("输入LA序列的第%d元素的系数+指数(格式:系数 指数)",i);
            node =  (UNARY*)malloc(sizeof(UNARY));
            if(node==NULL)
            {
                exit(0);
            }
    
            scanf("%f %d",&node->coef,&node->expn);
    
            //不合法分析:1、系数为零 (√)2、指数重复(未解决)
            if(node->coef==0)
            {
                continue;
            }
    
            node->next = LA->next;
            LA->next = node;
    
    
            i++;
    
    
            printf("继续?(1,0)");
            scanf("%d",&choice);
            if(choice==0)
            {
                break;
            }
    
        }
         while(1)
        {
            printf("输入LB序列的第%d元素的系数+指数(格式:系数 指数)",i);
            node =  (UNARY*)malloc(sizeof(UNARY));
    
            scanf("%f %d",&node->coef,&node->expn);
    
            node->next = LB->next;
            LB->next = node;
    
    
            i++;
    
    
            printf("继续?(1,0)");
            scanf("%d",&choice);
            if(choice==0)
            {
                break;
            }
    
        }
    
    
    
    }
    UNARY* printList(UNARY *LA,UNARY *LB)
    {
        UNARY *circleLA,*circleLB;
        circleLA = LA;
        circleLB = LB;
        printf("LA:\n");
        while(circleLA->next!=NULL)
        {
            circleLA = circleLA->next;
            printf("%.2f %d\n",circleLA->coef,circleLA->expn);
    
        }
        printf("LB:\n");
         while(circleLB->next!=NULL)
        {
            circleLB = circleLB->next;
            printf("%.2f %d\n",circleLB->coef,circleLB->expn);
    
        }
    }
    /*对一元多项式进行升幂排序
     *输入:一元多项式链表
     *输出:升幂排序的一元多项式链表
     *
    */
    UNARY* Increasing(UNARY *LA,UNARY *LB)
    {
         UNARY *head,*end,*pre,*cur,*next,*temp;
        head = LA;
        end = NULL;
    
        //冒泡排序:将 最小/最大 的节点后移至当前的最后一位。
        while(head->next != end)
        {
            for(pre = head,cur = head->next,next = cur->next; next != end; pre = pre->next,cur = cur->next,next = next->next)
            {
                if(cur->expn > next->expn)
                {
                    cur->next = next->next;
                    pre->next = next;
                    next->next = cur;
                    temp = next;
                    next = cur;
                    cur = temp;
                }
    
            }
            end = cur;
        }
         head = LB;
        end = NULL;
    
    
        while(head->next != end)
        {
            for(pre = head,cur = head->next,next = cur->next; next != end; pre = pre->next,cur = cur->next,next = next->next)
            {
                if(cur->expn > next->expn)
                {
                    cur->next = next->next;
                    pre->next = next;
                    next->next = cur;
                    temp = next;
                    next = cur;
                    cur = temp;
                }
    
            }
            end = cur;
        }
    
    
    
    
    
    }
    /*对一元多项式进行求导
     *输入:一元多项式链表
     *输出:求导后的一元多项式链表
     *所谓求导系数与指数相乘,指数减1;如果指数为零,本项为零,不再复制到新的多项式中
    */
    
    UNARY* Derivation(UNARY *LA,UNARY *LB)
    {
    
        UNARY *headLA,*headLB;
        headLA = LA;
        headLB = LB;
    
    
        while(headLA->next!=NULL)
        {
            headLA = headLA->next;
            headLA->coef = headLA->coef*headLA->expn;
            if(headLA->expn!=0)
            {
                 headLA->expn -= 1;
            }
            else
            {
                headLA->expn = 0;
            }
    
    
        }
        while(headLB->next!=NULL)
        {
            headLB = headLB->next;
            headLB->coef = headLB->coef*headLB->expn;
            if(headLB->expn!=0)
            {
                 headLB->expn -= 1;
            }
            else
            {
                headLB->expn = 0;
            }
    
    
        }
    
    }
    
    int main()
    {
        int choice;
        //创建链表
        UNARY *LA,*LB;
        LA = (UNARY*)malloc(sizeof(UNARY));
        LB = (UNARY*)malloc(sizeof(UNARY));
        creatList(LA,LB);
    
    
    
        //将链表变为升幂次序
        Increasing(LA,LB);
        printf("升幂后\n");
        printList(LA,LB);
        printf("输入选择(1:求导 2:运算):");
        scanf("%d",&choice);
    
    
    if(choice ==1)
    {
        //求导:将系数与指数相乘 然后指数减1
       Derivation(LA,LB);
         printf("求导后\n");
        printList(LA,LB);
    
    }
    else if(choice == 2)
    {
        //运算(加减运算)
        char x;
        printf("运算:");
        scanf("\n");
        scanf("%c",&x);
        unaryAdd_Sub(LA,LB,x);
        printf("运算后\n");
        printList(LA,NULL);
    
    }
    
    
    
    
    
    
    
    
    
    
    
    
    
    }
    
    
    
    

    文章主要摘自《深入浅出数据结构与算法》————清华出版社

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

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

    实验方案:

    分别采用了顺序表、链表的方式实现一元多项式完成多项式的加、减运算并求值
    1、实现功能描述:
    (1) 输入和输出:
    需要输入的信息有多项式的系数和指数,用来向系统动态申请内存;系数和指数用来构造每个结点,形成表。输入要求在程序运行过程中有提升,输出即对一元多项式进行遍历输出。

    (2) 一元多项式的相加和相减:
    多项式的加减要指数相同的同类项才能实现,所以需要在运行中对各种不同情况进行判断,最后得到的结果存到新的表中,形成一个新的多项式。

    (3)已知自变量求一元多项式的值:
    可以对输入的两个一元多项式及其经过加、减运算得到的新的一元多项式进行计算,只要给出x的值(可以为浮点数),即可求得三个多项式的结果。

    2、方案比较与选择
    (1) 从数据结构的逻辑结构与存储结构角度提供多种解决方案:
    ① 逻辑结构:
    由于一元多项式是线性结构,所以我选择线性表来实现。线性表分为顺序表和链表两种:若一元多项式的每一项均的系数均不为0且项数确定的情况下(不讨论具体的操作),选择顺序表是个更好的解决方案;若一元多项式的项数在不确定的情况下(不讨论具体的操作),选择链表是个更好的解决的方案。
    ② 存储结构:
    存储结构主要分为顺序存储方式、链式存储方式。若经常对一元多项式的某项进行操作且知道具体项数的情况,应选择顺序表;若不清楚对具体的哪一项进行操作的情况下,经常需要进行查找、插入、删除,则应选择链表。

    (2) 从时空效率角度分析决定最终采用方案的原因。
    ① 若输入的一元多项式是项数固定且指数依次递增的系数非0项,在不需要经常进行插入、删除某一项的情况下,选择顺序表。即是因为在上述情形下无论采用顺序还是链式的存储方式,需要的空间都是一样,但是使用顺序表可以在操作上有效降低时间的复杂度。
    ② 若输入的一元多项式的项数不固定,且指数不是依次递增的式子,需要经常进行插入、删除的情况下,选择链表。即是因为在上述情形下每个结点代表一个项,多项式的每一项可以用其系数和指数唯一的表示,方便进行插入、删除等操作,在操作上有效降低空间的复杂度。

    3、设计算法描述
    (1)用简单示例结合所设计算法采用的数据逻辑结构图、存储结构图说明算法思想。
    数据逻辑结构为:
    顺序表和链表的逻辑结构均相同,先对需要存储输入一元多项式的表进行初始化,再输入多项式的项数和多项式的系数、指数,重复两次,再选择是否进行加\减运算,然后输入x的值,最后得到需要求的多项式的值。
    在这里插入图片描述

    数据存储结构:
    顺序表的存储结构,是一个空间连续的表,通过下标来寻找数据元素,通过对数据的下标增加\减少来遍历整个表。
    链式的存储结构,是一个线性的但空间不连续的表,通过头结点来访问链表,每一个结点具有数据域和指针域,通过指针域来存储下一个元素的地址,然后一个个地进行遍历。
    在这里插入图片描述

    (2)进行模块划分,给出功能组成框图。
    功能主要分为初始化多项式、输入多项式、输出多项式、对多项式进行加\减、对多项式进行求值,通过主函数来调用各功能子函数来完成要求。

    在这里插入图片描述

    (3)用流程图描述关键算法。
    关键算法:多项式的加、减运算。
    顺序表中,先对两个多项式的第一项进行分析,若两项不相等,则先把小的一项放入新的表中,先放入一项的多项式下标加1用下一项和另一个多项式的第一项进行对比;若两项相等,则判断两项系数相加\减是否为0,若为0则两个多项式均自增到下一项进行比较;若不为0,则将得到的系数和表A的指数放入新的表中作为一项。如此循环对比,直到一个表到最后一项,然后再判断哪一个表不为空,将该表剩余的项均放入新的表中;若两个表刚刚好项数项数,则无需进行下一步。最后得到新的一元多项式。
    在这里插入图片描述

    链表中,先对两个多项式的第一项进行分析,若两项相等,则判断两项系数相加\减是否为0,若为0则两个多项式均自增到下一项进行比较;若不为0,则将得到的系数和表A的指数放入新的表中作为一项;若两项不相等,则先把小的一项放入新的表中,先放入一项的多项式下标加1用下一项和另一个多项式的第一项进行对比。如此循环对比,直到一个表到最后一项,然后再判断哪一个表不为空,将该表剩余的项均放入新的表中;若两个表刚刚好项数项数,则无需进行下一步。最后得到新的一元多项式。
    在这里插入图片描述
    4、算法实现(即完整源程序,带注解)
    (1)顺序表的完整源代码:

    #include<stdio.h>
    #include<stdlib.h>
    #include<malloc.h>
    #include<math.h>
    
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    
    typedef int Status;
    int num1, num2;
    
    typedef struct
    {
    	float coef; //系数
    	int	exp; //指数
    } Node;
    
    typedef struct
    {
    	Node *elem; //数据基地址
    	int length; //表的长度
    } LinkList;
    
    Status Initpolyn(LinkList *L, int n)    //多项式的初始化                            
    {
    	L->elem = (Node *)malloc(sizeof(Node) * n);
    	if (L->elem == NULL) //若空间申请失败,则返回0退出
    		return ERROR;
    	L->length = 0; //未输入前表的长度置为0
    	return OK;
    }
    
    void Inputpolyn(LinkList *La, int n) //输入系数和指数
    {
    	int y, i;
    	float x;
    
    	printf("依次输入系数和指数(例:2*x^3输入为2,3):\n");
    
    	for (i=0; i<n; i++)
    	{
    		scanf("%f,%d", &x, &y); //x为系数,y为指数
    
    		La->elem[i].coef = x;
    		La->elem[i].exp = y;
    		La->length++; //完整输入一项后,表长度加1
    	}
    
    }
    
    void Outputpolyn(LinkList *L) //遍历输出多项式的内容
    {	
    	int i = 0;
    
    	for (i = 0; i < L->length; i++)
    	{
    		printf("%.2f x^%d  | ", L->elem[i].coef, L->elem[i].exp);
    	}	
    }
    
    Status addpolyn(LinkList *La, LinkList *Lb, LinkList *Lc, int n) //多项式加减运算
    {
    	int i=0, j=0, k=0;
    	float coe;
    
    	Lc->elem = (Node *)malloc(sizeof(Node) * (La->length + Lb->length)); //建立新表
    	if (La->length == 0) //若表A为空,则新表等于表B
    	{
    		Lc = Lb;
    		return OK;
    	}
    	if (Lb->length == 0) //若表B为空,则新表等于表A
    	{
    		Lc = La;
    		return OK;
    	}
    
    	while (i<La->length && j<Lb->length) //用i,j分别来表示表A,B已经存入新表的项数
    	{
    		if (La->elem[i].exp < Lb->elem[i].exp) //若表A的项系数比表B的小,则插入新表
    		{
    			Lc->elem[k] = La->elem[i];
    			k++;
    			i++;
    		}
    		else if (La->elem[i].exp > Lb->elem[i].exp) //若表B的项系数比表A的小,则插入新表
    		{
    			Lc->elem[k] = Lb->elem[j];
    			k++;
    			j++;
    		}
    		else //若两表的系数相等,则判断加或减操作,再判断运算后的系数是否为0
    		{
    			if (n == 1)
    				coe = La->elem[i].coef + Lb->elem[j].coef;
    			else if (n == 0)
    				coe = La->elem[i].coef - Lb->elem[j].coef;
    
    			if (coe != 0) //若系数不为0,则将运算后得到的系数和表A的指数作为一项存入新表中
    			{
    				Lc->elem[k].exp = La->elem[i].exp;
    				Lc->elem[k].coef = coe;
    				k++;
    			}
    			i++;
    			j++;
    		}
    	}
    
    	if (i == La->length) //若表A已经遍历完且表B还没有,则将表B剩下的内容存入新表中
    	{
    		while (j < Lb->length)
    		{
    			Lc->elem[k].exp = Lb->elem[j].exp;
    			Lc->elem[k].coef = Lb->elem[j].coef;
    			j++;
    			k++;
    		}
    	}
    
    	if (j == Lb->length) //若表B已经遍历完且表A还没有,则将表B剩下的内容存入新表中
    	{
    		while (i < La->length)
    		{
    			Lc->elem[k].exp = La->elem[i].exp;
    			Lc->elem[k].coef = La->elem[i].coef;
    			j++;
    			k++;
    		}
    	}
    
    	Lc->length = k; //设置新表的长度
    	return OK;
    }
    
    double GetResult(LinkList *La, LinkList *Lb, LinkList *Lc) //对多项式进行计算
    {
    	LinkList *p;
    	int name, L_length, i;
    	double x, sum_polyn = 0;
    
    	scanf("%lf,%d", &x, &name);
    
    	switch (name) //判断选择哪一个多项式进行计算
    	{
    	case 1:
    		L_length = La->length;
    		p = La;
    		break;
    	case 2:
    		L_length = Lb->length;
    		p = Lb;
    		break;
    	case 3:
    		L_length = Lc->length;
    		p = Lc;
    		break;
    	default :
    		break;
    	}
    	
    	for (i=0; i<L_length; i++) //遍历的方式进行计算
    	{
    		sum_polyn += p->elem[i].coef * (pow(x,p->elem[i].exp));
    	}
    	return sum_polyn;
    
    }
    
    int main(void)
    {
    	LinkList La, Lb, Lc;
    	int change;
    	double result;
    
    	printf("输入第一个多项式的项数:");
    	scanf("%d", &num1);
    
    	Initpolyn(&La, num1);
    	Inputpolyn(&La, num1);
    	
    	printf("输入第二个多项式的项数:");
    	scanf("%d", &num2);
    
    	Initpolyn(&Lb, num2);
    	Inputpolyn(&Lb, num2);
    
    	printf("两个多项式分别为:\n");
    
    	Outputpolyn(&La);
    	printf("\n");
    
    	Outputpolyn(&Lb);
    
    	printf("\n令多项式相加输入1,相减输入0: \n");
    	scanf("%d", &change);
    
    	addpolyn(&La, &Lb, &Lc, change);
    
    	printf("相加减后的结果为: \n");
    
    	Outputpolyn(&Lc);
    
    	printf("\n请输入x的值及其需要计算的多项式[输入格式:2.1,1](前面为x的值,后面可以输入1,2,3分别对应多项式a,b,c):");
    
    	result = GetResult(&La, &Lb, &Lc);
    	printf("%.2lf\n", result);
    
    	return 0;
    }
    

    (2)链表的完整源代码:

    #include<stdio.h>
    #include<stdlib.h>
    #include<malloc.h>
    #include<string.h>
    #include<math.h>
    
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    
    typedef int Status;
    
    typedef struct polynmial
    {
    	float coef; //系数
    	int exp; //指数
    
    	struct polynmial *next; //指针
    } Node, *LinkList;
    
    Status Initpolyn(Node *L) //初始化链表
    {
    	L = (LinkList)malloc(sizeof(Node));
    	if (!L)              //若空间申请失败则返回0退出
    		return ERROR;
    	L->next = NULL;  //指针初始化
    	return OK;
    }
    
    Status Createpolyn(Node *L) //设置多项式
    {
    	int num, i;
    	LinkList p;
    
    	printf("\n请输入一元多项式的个数:\n");
    	scanf("%d", &num);
    
    	printf("\n请输入一元多项式的系数和指数(例:2*x^3输入为2,3):\n");
    
    	p = L;
    
    	for (i=0; i<num; i++) //输入一项则申请一个空间进行储存
    	{
    		p->next = (LinkList)malloc(sizeof(Node));
    		p = p->next;
    		scanf("%f,%d", &p->coef, &p->exp);
    	}
    	p->next = NULL; //尾项指针赋值为空
    	return OK;
    }
    
    void Display(Node *L) //输出多项式内容
    {
    	LinkList p;
    	p = L->next;
    
    	printf("\n该多项式为:\n");
    
    	while (p != NULL) //若该项地址不为空,则遍历输出该多项式的内容
    	{
    		printf("%.2f x^%d  | ", p->coef, p->exp);
    		p = p->next;
    	}
    }
    
    void Addpolyn(Node *La, Node *Lb, Node *Lc, int n) //对多项式进行加减操作
    {
    	float sum;
    	LinkList pa, pb, pc;
    	pc = (LinkList)malloc(sizeof(Node)); //对实表进行初始化
    	pc->next = NULL;
    
    	pc = Lc; //利用一个实参储存新表的首结点
    
    	pa = La->next;
    	pb = Lb->next;
    
    	while (pa && pb) //若两个表不为空,则循环对比
    	{
    		if (pa->exp == pb->exp) //若两项相等,则判断加或减运算,再对系数进行运算
    		{
    			if (n == 1)
    			{
    				sum = pa->coef + pb->coef;
    			}
    			else if (n == 0)
    			{
    				sum = pa->coef - pb->coef;
    			}
    			if (sum) //若系数不为0,则把运算后的系数和表A的指数存入新表中作为一项
    			{
    				pc->next = (LinkList)malloc(sizeof(Node));
    				pc = pc->next;
    				pc->coef = sum;
    				pc->exp = pa->exp;
    			}
    			pa = pa->next;
    			pb = pb->next;
    		}
    		else   //若两项不相等,则将系数小的一项存入新表中,然后遍历到下一项,循环判断直到一个表结束
    		{
    			pc->next = (LinkList)malloc(sizeof(Node));
    			pc = pc->next;
    			if (pa->exp < pb->exp)
    			{
    				pc->coef = pa->coef;
    				pc->exp = pa->exp;
    				pa = pa->next;
    			}
    			else if (pa->exp > pb->exp)
    			{
    				pc->coef = pb->coef;
    				pc->exp = pb->exp;
    				pb = pb->next;
    			}
    		}
    	}
    	
    	while (pa) //若表A未结束,则将剩下的项均存入新表中
    	{
    		pc->next = (LinkList)malloc(sizeof(Node));
    		pc = pc->next;
    		pc->coef = pa->coef;
    		pc->exp = pa->exp;
    		pa = pa->next;
    	}
    
    	while (pb) //若表B未结束,则将剩下的项均存入新表中
    	{
    		pc->next = (LinkList)malloc(sizeof(Node));
    		pc = pc->next;
    		pc->coef = pb->coef;
    		pc->exp = pb->exp;
    		pb = pb->next;
    	}
    
    	pc->next = NULL;
    }
    
    double GetRe(Node *La, Node *Lb, Node *Lc) //计算多项式的值
    {
    	LinkList p = NULL;
    	int name;
    	double x, sum_poly = 0;
    	
    	scanf("%lf,%d", &x, &name); 
    
    	switch (name) //判断对哪一个多项式进行计算
    	{
    	case 1:
    		p = La->next;
    		break;
    	case 2:
    		p = Lb->next;
    		break;
    	case 3:
    		p = Lc->next;
    		break;
    	default:
    		break;
    	}
    
    	while (p) //若该表地址非空,则遍历每一项进行运算
    	{
    		sum_poly += (double)p->coef * (double)(pow(x,p->exp));
    		p = p->next;
    	}
    
    	return sum_poly;
    }
    
    int main()
    {
    	Node La, Lb, Lc;
    	int change;
    	double result;
    
    	Initpolyn(&La); //创建表A,B
    	Initpolyn(&Lb);
    
    	Createpolyn(&La); //创建多项式A,B
    	Display(&La);
    
    	Createpolyn(&Lb);
    	Display(&Lb);
    
    	printf("\n若输入1则对多项式进行加操作,输入0则对多项式进行减操作:");
    	scanf("%d", &change);
    
    	Addpolyn(&La, &Lb, &Lc, change);
    	Display(&Lc);
    
    	printf("\n请输入x的值及需要计算的多项式(多项式可以选择输入1,2,3,对于着多项式a,b,c)[输入格式:2,1]: \n");
    
    	result = GetRe(&La, &Lb, &Lc);
    	printf("%.2lf\n", result);
    
    	return 0;
    }
    

    5、实验结果测试与分析
    (1)用各种可能数据测试程序,取截图。
    顺序表进行加运算:
    在这里插入图片描述
    顺序表进行减运算:
    在这里插入图片描述
    链表进行加运算:
    在这里插入图片描述
    链表进行减运算:
    在这里插入图片描述
    (2)对结果进行分析,说明算法的有效性。
    通过对顺序表、链表分别进行了加、减的运算,在输入的多项式的指数是递增的,均可以实现算法。

    6、分析
    线性表的顺序存储结构,在已知位置存、读取数据时,不管是哪个位置,时间复杂度都是O(1);而插入或删除时,时间复杂度都是O(n);
    线性表的链式存储结构,在已知位置插入、删除数据时,不管是哪个位置,时间复杂度都是O(1);而存、读取数据时,时间复杂度都是O(n);

    展开全文
  • 利用链式存储实现存储一元多项式,并计算两个一元多项式之和。一元多项式由系数和指数构成。 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;  //定义系数变量

    展开全文
  • 1、实现方式:可采用线性表的顺序存储结构,但是当多项式的每个项的指数差别很大时,会浪费很多存储空间。所以采用链式存储方式表示,每一项可以表示成一个结点,结点的结构由存放系数的coef域,存放指数的expn域和...
  • PAGE / NUMPAGES 实验链表的应用-求两个一元多项式之和 班级计科114...实验要求 用单链表存储一元多项式将两个存储一元多项式的单链表相加产生结果单链表 2.源程序如下 #include<stdio.h> #include<stdlib.h> typedef s
  • 数据结构一元多项式相加: 题目说明: 编写一元多项式加法运算程序。要求用线性链表存储一元多项式(参照课本)。该程序有以下几个功能: 多项式求和 输入:输入三个多项式,建立三个多项式链表Pa、Pb、Pc ...
  • 一元多项式计算器 数据结构

    千次阅读 2020-04-30 12:41:43
    直接上代码,代码几乎没加注释,不懂可直接问我(实现了判断是否是稀疏结构进行存储) #include <iostream> #include <stdio.h> #define MAXSIZE 10000 //表中元素的最大个数 #define OK 1 #define ...
  • printf("两个一元多项式相加的结果为:"); PrintPolyn(AddPolyn(P1, P2)); } void CreatePolyn(Link* p, int m)//*p是双重指针,用此意在改变指针 //创建多项式(带头结点),基础:动态链表的创建 { Link r, s;...
  • 数据结构(C++) 一元多项式求和

    千次阅读 2019-09-29 01:06:30
    今天做了做一元多项式求和的链表实现,其中主要的思想就是一个普通的尾插法链表,主要的区别也只是有coef和exp两个数据元素了,再有就是求和实质其实就是两个链表的相加操作。 主要的思想分别有: 首先确定一条主链...
  • 中南大学 数据结构与算法课程实验 实验报告 题目 实验一线性表的操作 学生姓名 谭淇蔚 学生学号 3901130721 专业班级 软件工程 1307班 完成日期 2014 年 3 月 31 日星期一 实验一线性表的操作一元多项式相加 1....
  • 一元多项式计算器 (c语言数据结构实验) 班级 : **** 学号 : 201907020633 姓名 : *** 实验机号: A3 实验日期 :2020.12.04 报告日期 :2020.12.07 实验题目:一元多项式计算器
  • 数据结构作业:一元多项式

    千次阅读 多人点赞 2020-12-25 10:52:28
    数据结构作业:一元多项式 电子科学与技术 刘智宇 1950083 刘岸奇 1951127 问题描述(问题描述、问题分析、输入、输出样例的简单叙述) ①问题描述 设有一元多项式A(x)和B(x),现要求其相加结果C(x)=A(x...
  • vc++6.0
  • 灵活运用顺序表和单链表的相关算法实现一元多项式的计算。 实验内容 设有一元多项式Am(x)和Bn(X),编程实现多项式Am(x)和Bn(x)的加法、减法和乘法运算。其中多项式描述为: Am(x)=A0+A1x1+A2x2+A3x3+….+Amxm; Bn...
  • 由于多项式的加减肯定会用到链表,所以本题运用链表来实现,其中会用到链表的插入,删除以及一些细节的地方,同时为了处理好一些其他的输入问题,或者是不是按照顺序的输入,加入了一些自己的理解,关于链表的知识点...
  • 线性表模块专题,一元多项式计算器的简单实现。简单回顾线性表章节相关内容,对实际问题(即一元多项式计算器的设计实现)综合运用相关知识进行问题分析和程序设计实现
  • #include <stdio.h> #include <stdlib.h>...//存储结构为:带头节点的单链表 struct PolyNode { int coef;//多项式系数 int expon;//多项式指数 Polynomial next;//指向下一个节点 }; t...
  • C语言数据结构一元多项式运算器

    千次阅读 2019-09-22 12:47:50
    首先,需要解决一元多项式在计算机中的存储问题。 对于一元多项式: P = p0 + p1x + …+pnx^n 在计算机中,可以用一个线性表来表示: P = (p0,p1,…,pn), 但是对于形如 S(x) = 1 + 5x^10 000 -12x^15 000 的多项式,...
  • 实现了一元多项式的加减乘的运算。我们使用计算机处理的对象之间通常存在着的是一种最简单的线性关系,这类数学模型可称为线性的数据结构。而数据存储结构有两种:顺序存储结构和链式存储结构。线性表是最常用且最...
  • 用单链表实现一元多项式的乘法。多项式的每一项含在一个单元中,并且这些单元以次数递减的顺序排序,将相乘结果保持到一个新的单链表中。其中比较困难的在于,当两个多项式相乘的时候所得到的多项式必须合并同类项。
  • 实验内容:使用链式存储实现一元多项式的加法、减法、乘法和求导。即: 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(x)和B(x),其中 输入时按照 指数的升序...
  • 数据结构课程设计一元多项式加法减法乘法运算的实现 1.一元多项式加法减法乘法运算的实现 1.1设计内容及要求 1)设计内容 1使用顺序存储结构实现多项式加减乘运算 例如 , 求和结果 2使用链式存储结构实现多项式加减乘...
  • 数据结构-一元多项式计算器 顺序cun'chu 要求结果中无重复阶项和无零系数项 输出升幂排序的运算结果 设计实现菜单方式的交互页面,界面友好,可重复操作</p>
  • 这个是自己编写的用顺序表实现一元稀疏多项式的基本操作
  • 数据结构(C语言)用单链表存储一元多项式,并实现两个多项式的相加运算 #include #include #include typedef int ElemType; /*单项链表的声明*/ typedef struct PolynNode{ int coef; // 系数 int expn; // 指数 ...
  • 函数功能说明:Void InitList(PolyNode &L) /初始化多项式单链表*/ Int GetLength(PolyNode*L) /求多项式单链表的长度/ PolyNode GetElem(PolyNode *L,int i) /返回多项式单链表中第i个结点的指针*/ PolyNode ...
  • 数据结构(12)线性表之C++实现一元多项式相加

    万次阅读 多人点赞 2016-03-17 11:24:57
    第二种代码的实现仅链表存储形式实现导言上篇文章,我们说明了一元多项式相加采取了什么形式和抽象定义数据类型定义以及实现一元多项式相加的方法,本节将用具体代码来实现一元多项式相加。一元多项式表现形式...

空空如也

空空如也

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

数据结构一元多项式顺序存储

数据结构 订阅