`

多项式加法

阅读更多
题目的链接为http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1005
题目如下:
多项式加法
时间限制(普通/Java):1000MS/3000MS          运行内存限制:65536KByte
总提交:964            测试通过:100

描述


线性表是一种最简单、最基本,也是最常用的数据结构,其用途十分广泛,例如,用带表头结点的单链表求解一元整系数多项式加法和乘法运算。

现给两个一元整系数多项式,请求解两者之和。


输入


两组数据,每一组代表一个一元整系数多项式,有多行组成,其中每一行给出多项式每一项的系数和指数,这些行按指数递减次序排序,每一组结束行为

0 -1


输出


三组数据,前两组为一元整系数多项式,最后一组为两个多项式的和。

一元整系数多项式输出形式如下:

(1)多项式项4x输出为4X

(2)多项式项4x2输出为4X^2

(3)第一项系数为正数时,加号不要输出

(4)除常系数项外,项系数为1不显式输出,-1输出为-

例如,4x3- x2+x-1正确输出形式为4X^3-X^2+X-1,错误输出形式为 +4X^3-1X^2+1X-1

样例输入

3 14
-8 8
6 2
2 0
0 -1
2 10
4 8
-6 2
0 -1

样例输出

3X^14-8X^8+6X^2+2
2X^10+4X^8-6X^2
3X^14+2X^10-4X^8+2


提示


该题属于南京邮电大学《数据结构A》实验一中的内容,验证的是课本代码,请慎重解答。


题目来源

CHENZ
说是多项式的加法,其实考察的是对于链表的操作。
我们设一个结构体,包括3个部分:
xs:多形式某项的系数
zs:多项式某项的指数
next:指向下个项的指针
typedef struct node{
      
      int xs;
      int zs;
      struct node *next;  
}Node;

对于一个多项式的输入,由于是按指数递减输入的,故我们只需按照输入顺序进行存储即可。
对待一个输入,算法如下:
1.如果当前多项式为空,那么将此项放入第一项
2.如果当前多项式不为空
2.1如果有指数相同的项,那么将此项与指数相同的项合并,如果系数变为0,则将此项删除。
2.2如果没有指数相同的项(那么此项的指数一定比当前所有项的指数都小),那么将此项放入多项式末尾。
这样就可以得到输入的两个多项式,并输出。
对于最后一步,多项式加法,即将多项式指数相同的项分别相加,而将指数不同的项保留输出即是加法结果。
代码如下,思路不难,重在细心:
PS:我是第100个AC的,好彩头!
#include<iostream>
using namespace std;
typedef struct node{
      
      int xs;
      int zs;
      struct node *next;  
}Node;
int xs,zs;
bool tag=true;
void print(Node *root)
{
    Node *p=root->next;
    while(p!=NULL)
    {
         if(p==root->next)
         {
              if(p->xs!=1)
              {
                 if(p->xs==-1)
                 {
                     cout<<"-"; 
                 }    
                 else
                 {
                     cout<<p->xs; 
                 }
              } 
         } 
         else
         {
              if(p->xs>0)
              {
                   cout<<"+";
                   if(p->xs!=1)
                   {
                       cout<<p->xs; 
                   }
              } 
              else
              {
                    if(p->xs!=-1)
                    {
                       cout<<p->xs;
                    } 
                    else
                    {
                       cout<<"-"; 
                    }
              }
         }
         if(p->zs!=0)
         {
               cout<<"X";
         }
         else
         {
               if(p->xs==1||p->xs==-1)
               {
                  cout<<"1"; 
               }
               
               p=p->next;
               continue; 
         }
         if(p->zs!=1)
         {
               cout<<"^"<<p->zs; 
         }
         
         p=p->next;
    }
    cout<<endl;
}
int main(){

    Node *root[2],*root1,*t,*u,*k;
    for(int i=0;i<2;i++){
        root[i]=NULL; 
    } 
    root1=new Node();
    for(int i=0;i<2;i++){
        while(cin>>xs>>zs&&(xs!=0||zs!=-1)){
         
            if(xs==0)
            {
               continue;
            }
            if(root[i]==NULL)
            {
                  Node *temp=new Node();
                  temp->xs=xs;
                  temp->zs=zs;
                  temp->next=NULL;
                  
                  root[i]=new Node();
                  root[i]->next=temp;
            }
            else
            {
                  Node *p,*q;
                  p=root[i]->next;
                  q=root[i];
                  while(p!=NULL&&p->zs!=zs)
                  {
                       q=p;
                       p=p->next; 
                  }
                  if(p==NULL)
                  {
                       Node *temp=new Node();
                       temp->xs=xs;
                       temp->zs=zs;
                       temp->next=NULL;
                  
                       q->next=temp;
                  }
                  else
                  {
                       p->xs+=xs;
                       if(p->xs==0)
                       {
                           q->next=p->next; 
                       }
                  }
            }
        }
        print(root[i]);  
    }
    t=root[0]->next;
    u=root[1]->next;
    k=root1;
    while(t!=NULL&&u!=NULL)
    {
             Node *tempNode=new Node();
             if(t->zs>u->zs)
             {
                  tempNode->xs=t->xs;
                  tempNode->zs=t->zs;
                  t=t->next;
                  tag=false;
             } 
             else if(t->zs<u->zs)
             {
                  tempNode->xs=u->xs;
                  tempNode->zs=u->zs;
                  u=u->next;   
                  tag=false;
             }
             else
             {
                  if(t->xs+u->xs==0)
                  {
                      t=t->next;
                      u=u->next;
                      continue; 
                  } 
                  tempNode->xs=u->xs+t->xs;
                  tempNode->zs=u->zs;
                  u=u->next; 
                  t=t->next;
                  tag=false;
             }
             k->next=tempNode;
             k=tempNode;
    }
    while(t!=NULL)
    {
           Node *tempNode=new Node();
           tempNode->xs=t->xs;
           tempNode->zs=t->zs;
           
           k->next=tempNode;
           k=tempNode;
           t=t->next;
           tag=false;
    }
    while(u!=NULL)
    {
           Node *tempNode=new Node();
           tempNode->xs=u->xs;
           tempNode->zs=u->zs;
           
           k->next=tempNode;
           k=tempNode;
           u=u->next;
           tag=false;
    }
    if(!tag)
    {
      print(root1);
    }
    else
    {
      cout<<"0"<<endl; 
    } 
    
    for(int i=0;i<2;i++)
    {
        t=root[i];
        u=t;
        while(t!=NULL)
        {
              u=t->next;
              delete t;
              t=u;
        } 
    }
    t=root1;
    u=t;
    while(t!=NULL)
    {
              u=t->next;
              delete t;
              t=u;
    } 
    system("pause");
    return 0;
}
分享到:
评论

相关推荐

    数据结构实验 多项式加法

    在这个实验中,我们将探讨如何使用循环链表来实现多项式加法,这是一种常见的数据结构应用。 首先,理解多项式可以被视为一系列系数与指数的配对,每一对代表一个项。例如,多项式`3x^2 + 2x + 1`可以表示为三个项...

    多项式加法C语言实现编程序

    在数据结构的学习中,多项式加法是一个经典的问题,它涉及到序列表示法和算法设计。在C语言中,我们可以利用数组或链表来表示多项式,并编写程序来实现加法操作。下面将详细讲解如何使用C语言实现多项式加法。 首先...

    c++封装的多项式加法器

    ### C++封装的多项式加法器:实现与关键技术点 #### 一、概述 本文将详细介绍一个基于C++封装的多项式加法器的设计与实现。该加法器不仅支持基本的多项式运算(包括加法、减法、乘法、求值、求导、求积分),还...

    多项式加法和乘法C代码

    ### 多项式加法和乘法C代码解析 #### 概述 本文将深入解析一个用C语言编写的多项式加法与乘法程序。该程序主要利用链表结构来表示多项式,并通过栈的方式来处理多项式的运算。程序不仅实现了多项式的加法运算,还...

    一元多项式加法器

    ### 一元多项式加法器的关键知识点 #### 数据结构的重要性 数据结构是计算机科学的基础,连接基础课程如计算机基础、程序设计语言、离散数学等与专业课程如操作系统、编译原理、数据库原理等之间的桥梁。通过学习...

    多项式加法的C++链表实现

    本文将深入探讨如何使用C++通过链表数据结构实现多项式加法。链表是一种非连续、非顺序的存储结构,每个节点包含数据元素以及指向下一个节点的指针。在这种情况下,我们将创建一个链表节点来表示多项式的项,其中...

    C++实现多项式加法

    在计算机科学中,多项式加法是一个常见的数学运算,它涉及到表示多项式并进行相应的加法操作。在C++编程语言中,我们可以采用多种方法来实现这个功能。本篇文章将探讨几种不同的C++实现方式,重点介绍一种简洁而高效...

    数据结构-多项式加法运算

    ### 数据结构-多项式加法运算 #### 一、引言 多项式是数学和计算机科学中的一个重要概念,在科学计算、工程设计等领域有着广泛的应用。本文档将详细介绍如何使用链表这种数据结构来实现多项式的加法运算。通过具体...

    数据结构/C++/多项式加法

    数据结构的作业/多项式加法用来C++来实现

    设计一个一元多项式加法器

    1)输入并建立多项式;(2)两个多项式相加; (3)输出多项式:n, c1, e1, c2, e2, …cn , en, 其中,n是多项式项数,ci和ei分别是第 i 项的系数和指数,序列按指数降序排列。

    数据结构——一元多项式加法.zip

    一元多项式加法是数学中的基本运算,而在编程和算法设计中,这种运算可以通过利用数据结构,尤其是线性表来实现。这篇内容将深入探讨如何使用线性表来实现一元多项式加法。 首先,理解一元多项式。一元多项式是由...

    MATLAB——多项式加法函数示例

    在MATLAB中,多项式加法是通过内置的函数实现的,这使得处理多项式运算变得非常方便。本文将深入探讨如何使用MATLAB进行多项式加法,以及相关的函数和概念。 首先,MATLAB中的多项式通常表示为向量形式,其中向量的...

    双向链表实现多项式加法和乘法.cpp

    双向链表实现多项式加法和乘法

    数据结构——一元多项式加法、减法、乘法运算的实现

    ### 数据结构——一元多项式加法、减法、乘法运算的实现 #### 设计内容及要求 本节详细介绍了如何使用不同的数据结构来实现一元多项式的加法、减法以及乘法运算。 ##### 1.1 设计内容 1. **使用顺序存储结构实现...

    多项式加法器

    编写一个“一元稀疏多项式加法器”,输入两个一元稀疏多项式,然后对它们进行加法操作。在具体实现上,要求用线性链表的形式来存储一个多项式,每个链表结点包括两个成员变量,即int类型的系数coef和int类型的指数...

    C语言多项式加法.pdf

    C语言多项式加法 多项式加法是 C 语言编程中的一种基本操作,它涉及到多项式的表示、存储和计算。在本篇文章中,我们将探讨如何使用 C 语言实现多项式加法,包括程序的设计、实现和优化。 一、多项式的表示 在 C ...

    多项式加法参考答案.cpp

    一个多项式可以表达为x的各次幂与系数乘积的和,比如: 2x6+3x5+12x3+6x+20 现在,你的程序要读入两个多项式,然后输出这两个多项式的和,也就是把对应的幂上的系数相加然后输出。 程序要处理的幂最大为100。

    数据结构课件,课后答案,单链表,多项式加法,二叉树,湖大小判断等代码

    这个压缩包包含了一系列与数据结构相关的课件、答案和代码示例,涵盖了单链表、多项式加法、二叉树以及湖泊大小判断等主题。 首先,单链表是一种线性数据结构,由节点构成,每个节点包含数据和指向下一个节点的指针...

    顺序链式一元多项式加法、减法、乘法运算的实现 (2).docx

    "顺序链式一元多项式加法、减法、乘法运算的实现" 本文档主要介绍了顺序链式一元多项式加法、减法、乘法运算的实现,涉及到多项式的存储结构、算法设计和实现等方面的知识点。 1. 顺序存储结构实现多项式加、减、...

Global site tag (gtag.js) - Google Analytics