XDOJ-一元稀疏多项式计算器
标题：

一元稀疏多项式计算器
类别：

综合
时间限制

2S
内存限制

1000Kb
问题描述

一元 n 次多项式𝑝0𝑋𝑒0 + 𝑝1𝑋𝑒1 + ⋯ + 𝑝𝑖𝑋𝑒𝑖 + ⋯ + 𝑝𝑛𝑋𝑒𝑛 项数较少时成为一元稀疏多项式，例如：3 + 6𝑋3 − 2𝑋8 + 12𝑋20是一个一元稀疏多项式。设计一个一元稀疏多项式计算器程 序完成两个一元稀疏多项式的加减法，输出结果多项式的各项系数和指数。
输入说明

输入数据第 1 行为 3 个正整数 n，m，t。其中 n 表示第一个多项式的项数，m 表示第二个

多项式的项数，t 表示运算类型，0 为加法，1 为减法。数据的第 2 行包含 2n 个整数，每两

个整数分别表示第一个多项式每一项的系数和指数；第 3 行包含 2m 个整数，每两个整数分

别表示第二个多项式每一项的系数和指数。两个多项式的每项是按照指数递增的形式给出的，

例如对于多项式3 + 6𝑋3 − 2𝑋8 + 12𝑋20，对应的输入为 3 0 6 3 -2 8 12 20
输出说明

运算结果按指数从低到高的顺序在以多项式形式（见输出样例）输出结果，注意系数为负数

时输出减号，系数为 0 时不输出该项，指数为 1 时不输出指数。
输入样例

6 2 0

1 0 1 1 1 2 1 3 1 4 1 5

-1 3 -1 4
输出样例

1+x+x^2+x ^5

(编辑原因,此处x^5之间没有那个空格)
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>//该库中含有下文用到的swap函数,不用自己手写swap了
using namespace std;
struct num//想了想还是用结构体吧
{
	int x, y;
};
int main()
{
	num sj1[200], sj2[100];//2个结构体数组,sj意为数据
	bool result = false;
	int n, m, t,i,j,a;//n,m,t如题所示,i,j控制循环
	cin >> n >> m >> t;
	a = n;
	for (i = 0; i < n; i++)
	{
		cin >> sj1[i].x >> sj1[i].y;
	}
	for (i = 0; i < m; i++)
	{
		cin >> sj2[i].x >> sj2[i].y;
	}
	for (i = 0; i < n; i++)
		{
			for (j = 0; j < m; j++)
			{
				if (sj1[i].y == sj2[j].y)思路是将指数相同的项系数相加放入sj1结构体中
				{
					if (t == 0)//加法运算
					{
						sj1[i].x += sj2[j].x;
					}
					else
					{
						sj1[i].x -= sj2[j].x;//减法运算
					}
					sj2[j].x = 0;//将对应的sj2中x置零
					break;//减少不必要的循环次数
				}
				
			}
		}
		for (i = 0; i < m; i++)
		{
			if (sj2[i].x != 0)//经历上面的循环过后,指数相同的项已经处理完毕,这些项的系数已经置零,下面来寻找系数不为零的项,将其加入到sj1的后面
			{
				if (t == 0)
				{
					sj1[a].x = sj2[i].x;//将sj2系数不为零的项加入到sj1的后面,此处也要注意t值
				}
				else 
				{
					sj1[a].x = -sj2[i].x;
				}
				sj1[a].y = sj2[i].y;
				a++;
			}
		}
		for (i = 0; i < a - 1; i++)//sj1目前已经包含所有项,但添加后面那一部分时,指数可能比sj1前面的值小,此处用冒泡排序,从小到大排下sj1,排完后即按照升幂顺序
		{
			for (j = 0; j < a - 1 - i; j++)
			{
				if (sj1[j].y > sj1[j + 1].y)
				{
					swap(sj1[j], sj1[j + 1]);
				}
			}
		}
		for (i = 0; i < a; i++)//后面写的太乱了,不忍直视,目的是处理指数为0和指数为1,系数为0,系数为1和系数为-1,以及系数大于1时输出+,还要注意输出第一项如果系数为正,+号不用输出,总之很烦
		{
			if (sj1[i].x == 0)
			{
				continue;
			}
			else if(sj1[i].y==0)
			{
				cout << sj1[i].x;
				result = true;
			}
			else
			{
				if (sj1[i].y == 1)
				{
					if (result)
					{
						if (sj1[i].x > 1)
						{
							cout << "+" << sj1[i].x << "x";
						}
						else if (sj1[i].x == 1)
						{
							cout << "+x";
						}
						else if (sj1[i].x == -1)
						{
							cout << "-x";
						}
						else
						{
							cout << sj1[i].x << "x";
						}
					}
					else
					{
						if (sj1[i].x > 1)
						{
							cout << sj1[i].x << "x";
						}
						else if (sj1[i].x == 1)
						{
							cout << "x";
						}
						else if (sj1[i].x == -1)
						{
							cout << "-x";
						}
						else
						{
							cout << sj1[i].x << "x";
						}
						result = true;
					}
				}
				else
				{
					if (sj1[i].x > 1)
					{
						if (result)
						{
							cout << "+" << sj1[i].x << "x^" << sj1[i].y;
						}
						else
						{
							cout << sj1[i].x << "x^" << sj1[i].y;
							result = true;
						}
					}
					else if (sj1[i].x == 1)
					{
						if (result)
						{
							cout << "+x^" << sj1[i].y;
						}
						else
						{
							cout << "x^" << sj1[i].y;
							result = true;
						}
					}
					else if (sj1[i].x == -1)
					{
						if (result)
						{
							cout << "-x^" << sj1[i].y;
						}
						else
						{
							cout << "-x^" << sj1[i].y;
							result = true;
						}
					}
					else
					{
						cout << sj1[i].x << "x^" << sj1[i].y;
					}
				}
				
			}

		}
	return 0;
}

应该有180行代码,感觉有点繁琐,如果有简单的,欢迎讨论交流

思路都在代码中注释了,下方不再赘述

ps:如有错误敬请指正,欢迎评论区讨论或私信

邮箱:1654407501@qq.com如果对你有用的话,请点赞并关注,近期不定时更新新内容

一元稀疏多项式计算器

[问题描述]：

设计一个一元稀疏多项式简单计算器。

[基本要求]：

一元稀疏多项式简单计算器的基本功能是：

 

(1)输出并建立多项式；

(2)输出多项式，输出形式为整数序列：n,c1,e1,c2,e2,...,cn,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列；

(3)多项式a和b相加，建立多项式a+b;

(4)多项式a和b相减，建立多项式a-b;

[测试数据]

(1)(2x+5x^8-3.1x^11)+(7-5x^8+11x^9)=(-3.1x^11+11x^9+2x+7);

(2)(6x^(-3)-x+4.4x^2-1.2x^9)-(-6x^(-3)+5.4x^2-x^2+7.8x^15)=(-7.8x^15-1.2x^9+12x^(-3)-x);

(3)(x+x^3)+(-x-x^3)=0;

(4)(x+x^2+x^3)+0=x+x^2+x^3;

(由于篇幅原因，只选取了具有代表性的4组测试数据)

[实现提示]

用带表头节点的单链表存储多项式。

 

 

一：程序设计流程：

1.建立两个带头节点的单链表A、B。

2.将A、B两个链表连接成一个新链表 C；

3.用冒泡法对C中链表进行排序。

4.把C链表中指数项相同节点合并。

二：程序源代码：

 

#include<stdlib.h>

#include<string.h>  

#include<stdio.h>

typedef struct PolyNode  

{     

    float coef;            //系数  

    int exp;               //指数  

    struct PolyNode *next;  

}PolyNode;  //用PolyNode定义PolyNode的结构体变量。

typedef PolyNode *Polynomial;  //是将*Polynomial定义为struct PolyNode类型，即Polynomial被定义为一个类型名。这样就可以用Polynomial来定义说明新的变量了

Polynomial CreateList()

{  

    float co;  

    int ex;  

    Polynomial head,p,l;  

    head=(Polynomial)malloc(sizeof(PolyNode));      

    p=head;  

    scanf("%f%d",&p->coef,&p->exp);           //设置头结点，并且设置第一个节点，为了保证表不为空  

    if(head->coef==0&&head->exp==0)

{        //如果头结点数据元素均为0，则为单节点链表  

    head->next=NULL;  

    }

else

{  

    p->next=(Polynomial)malloc(sizeof(PolyNode));  

    p=p->next;  

    while(1)

{  

    scanf("%f%d",&co,&ex);  

    if(co==0&&ex==0) 

break;         // 系数=0并且指数=0 代表结束输出 

{ 

        p->coef=co;  

        p->exp =ex;  

        l=p;  

        p->next =(Polynomial)malloc(sizeof(PolyNode));  

        p=p->next; 

}

    }   

    l->next = NULL;  

    }  

    return head;  

}  

void Sortlist(Polynomial L) // 用冒泡法对链表L中的节点按指数降序排列。

{ 

    Polynomial a,b;  

    float temp_co;        //设置中间变量来交换链表元素的值；  

    int temp_ex;  

    b =L;  

    a =L;  

    for(a;a!=NULL;a=a->next)

{  

        b= L ;  

        for(b;b->next!=NULL;b=b->next)

{  

            if(b->exp<b->next->exp)

{  

            temp_co=b->coef;  

            temp_ex=b->exp;  

            b->coef=b->next->coef;  

            b->exp =b->next->exp;  

            b->next->coef =temp_co;  

            b->next->exp  =temp_ex;  

            }  

        }  

    }     

    return;  

}  

void Display(Polynomial p)

{  

    Polynomial Pointer;  

    Pointer =p;  

    do

{  

    printf("%.2fx^%d  ",Pointer->coef,Pointer->exp);  

    Pointer=Pointer->next;  

    }

while(Pointer!=NULL);  

}  

Polynomial LinkList(Polynomial A,Polynomial B,int n)  //链接链表A B，在这里设定B的头指针为连接后的头指针 n=1表示加法，n=2表示减法；  

{  

    Polynomial tail_b,C,op_pointer;  // op_pointer 用来取反链表B cof 的数值。  

    tail_b =B;  

    op_pointer =B;  

    for(op_pointer;op_pointer!=NULL;op_pointer=op_pointer->next)

{  

        if(n==2)

{  

        op_pointer->coef = -op_pointer->coef;  

        //printf("%.2f  %d\n",op_pointer->coef,op_pointer->exp);  

        }  

    };  

    for(tail_b;tail_b->next!=NULL;tail_b=tail_b->next);  // 连接 B A 链表，以B链表头为合并后的表头  

    tail_b->next=A;  

    C=B;  

    Sortlist(C);  

    return C;  

}  

void MergeList(Polynomial C)

{      // 合并C中exp数值相同的节点.  

    Polynomial C1,C2;  

    C1=C;  

    C2=C1->next;  

    while(C2!=NULL)

{  

        if(C1->exp==C1->next->exp)

{  

        C1->coef=C1->next->coef+C1->coef;  

        C1->next=C1->next->next;  

        free(C2);  

        C2=C1->next;  

        }

else

{  

        C1=C1->next;  

        C2=C2->next;  

        }  

    }  

}

int main()

{  

    Polynomial A,B,Com;  

    int s;  

    printf("\n请输入链表A的数据为：X的系数，X的指数。两个数据以空格分开。\n：输入0 0表示输入结束。\n");  

    A=CreateList();  

    Display(A);  

    printf("\n\n\n请输入链表B的数据为: X的系数，X的指数。两个数据以空格分开。\n：输入0 0表示输入结束。\n");  

    B=CreateList();  

    Display(B);  

    printf("请选择加法还是减法\n");  

    printf("输入1代表加法\n");  

    printf("输入2代表减法\n");  

    scanf("%d",&s);  

    if(s==1||s==2){  

        Com=LinkList(A,B,s);    

        MergeList(Com);  

        Display(Com);  

    }

else

{  

        printf("输入了非法字符\n");  

    }  

  



}

 

 

 

三、测试数据

1.(2x+5x^8-3.1x^11)+(7-5x^8+11x^9)=(-3.1x^11+11x^9+2x+7);

 

2.(6x^(-3)-x+4.4x^2-1.2x^9)-(-6x^(-3)+5.4x^2-x^2+7.8x^15)=(-7.8x^15-1.2x^9+12x^(-3)-x);

 

3.(x+x^3)+(-x-x^3)=0;

 

4.(x+x^2+x^3)+0=x+x^2+x^3;