Description
给定两个一元多项式A(x)与B(x)，利用链表表示A(x)与B(x)，实现A(x)与B(x)的加法、减法、 乘法和求导运算。
Input
输入多组数据，总计n*( a+b+2)+1行。其中，第一行整数n代表总计有n组数据，之后依次输入 n组数据。每组数据包括a+b+2行，其中第一行是两个整数a和b，分别代表A(x)与B(x)的项数。 之后紧跟a行，每行两个整数a1和a2，分别代表A(x)每项的系数和指数，再之后紧跟b行，每行 两个整数b1和b2，分别代表B(x)每项的系数和指数，每组数据最后一行为一个字符（+、-、* 、’），分别代表多项式的加法、减法、乘法和求导运算。所有数据的绝对值小于100，指数大 于等于0。
Output
对于每组数据输出一行，按照多项式次数从大到小排列，参考格式：5x17+22x7+11x^1+7。
Sample Input
Sample Output
参考程序（C语言实现）
#include <stdio.h>
#include <stdlib.h>
#define ROOM sizeof(struct ListNode)
struct ListNode
{
int ratio;
int exp;
struct ListNode *next;
};
struct ListNode* CreateList(int n)
{
struct ListNode *head,*p1,*p2;
head=(struct ListNode*)malloc(ROOM);
head->ratio=n;//head用于存储项数
head->next=NULL;
p2=head;
while(n--)
{
p1=(struct ListNode*)malloc(ROOM);
scanf("%d%d",&p1->ratio,&p1->exp);
p1->next=NULL;
p2->next=p1;
p2=p1;
}
return head;
}
struct ListNode* AddNode(int new_ratio,int new_exp,struct ListNode *head)
{
struct ListNode *p,*p0;
int flag=0;
p0=head->next;
while(p0)
{
//查找同类项
if(p0->exp==new_exp)
{
flag=1;
p0->ratio+=new_ratio;
break;
}
else
{
p0=p0->next;
}
}
if(!flag)
{
//不存在同类项，则需要新建一个结点，存入表达式链表
p=(struct ListNode*)malloc(ROOM);
p->ratio=new_ratio;
p->exp=new_exp;
p->next=head->next;
head->next=p;
head->ratio++;//为方便操作，采用头插法
}
return head;
}
struct ListNode* Plus(struct ListNode *head1,struct ListNode *head2)
{
struct ListNode *p1,*p2;
p2=head2->next;
while(p2)
{
head1=AddNode(p2->ratio,p2->exp,head1);
p2=p2->next;
}
return head1;
}
struct ListNode* Minus(struct ListNode *head1,struct ListNode *head2)
{
struct ListNode *p1,*p2;
p2=head2->next;
while(p2)
{
p2->ratio=-p2->ratio;
head1=AddNode(p2->ratio,p2->exp,head1);
p2=p2->next;
}
return head1;
}
struct ListNode* Derivative(struct ListNode *head)
{
struct ListNode *p;
p=head->next;
while(p)
{
p->ratio=p->ratio*p->exp;
--p->exp;
p=p->next;
}
return head;
}
struct ListNode* Multiply(struct ListNode *head1,struct ListNode *head2)
{
//乘法新建一个链表，将乘积结果逐项加入新链表
struct ListNode *p1,*p2,*new_head;
int new_ratio,new_exp;
new_head=(struct ListNode*)malloc(ROOM);
new_head->ratio=0;
new_head->next=NULL;
p1=head1->next;
while(p1)
{
p2=head2->next;
while(p2)
{
new_exp=p1->exp+p2->exp;
new_ratio=p1->ratio*p2->ratio;
new_head=AddNode(new_ratio,new_exp,new_head);
p2=p2->next;
}
p1=p1->next;
}
return new_head;
}
void SortList(struct ListNode *head)
{
struct ListNode *p1,*p2;
int i,temp;
for(i=0;i<head->ratio-1;i++)
{
p1=head->next;
while(p1->next)
{
if(p1->exp < p1->next->exp)
{
temp=p1->next->exp;
p1->next->exp=p1->exp;
p1->exp=temp;
temp=p1->next->ratio;
p1->next->ratio=p1->ratio;
p1->ratio=temp;
}
p1=p1->next;
}
}
}
void OutputList(struct ListNode *head)
{
struct ListNode *p;
int flag=0;
SortList(head);//对多项式先按照降幂排列
p=head->next;
while(p)
{
//寻找首个系数不为0的项
if(p->ratio!=0)
{
flag=1;
break;
}
else
{
p=p->next;
}
}
if(!flag)
{
//所有结点的系数均为0
printf("0");
}
else
{
//注：需要对第一项特别处理
printf("%d",p->ratio);
if(p->exp)
{
printf("x^%d",p->exp);
}
p=p->next;
while(p)
{
if(p->ratio==0)
{
p=p->next;
}
else
{
if(p->ratio>0)
{
printf("+");
}
printf("%d",p->ratio);
if(p->exp)
{
printf("x^%d",p->exp);
}
p=p->next;
}
}
}
printf("\n");
}
int main()
{
int n,a,b;
scanf("%d",&n);
while(n--)
{
scanf("%d%d",&a,&b);
struct ListNode *L1,*L2,*newhead;
char option;
L1=CreateList(a);
L2=CreateList(b);
getchar();
scanf("%c",&option);
switch(option)
{
case '+':
newhead=Plus(L1,L2);
OutputList(newhead);
break;
case '-':
newhead=Minus(L1,L2);
OutputList(newhead);
break;
case '*':
newhead=Multiply(L1,L2);
OutputList(newhead);
break;
}
if(option=='\'')
{
newhead=Derivative(L1);
OutputList(newhead);
newhead=Derivative(L2);
OutputList(newhead);
}
}
return 0;
//by jialChen
}
分析：
本题实现上思路比较简单，基本功还是在于单链表的建立、归并、排序。下面就几个难点进行说明。
运算方面：
①加法：实际上就是合并同类项（归并）；
②减法：将链表中每一项的系数取相反数，再转化为加法运算；
③乘法：两个链表，采用两层循环逐项进行乘法运算，系数相乘，指数幂相加，再归并；
④求导：按照幂函数的求导公式进行。
输出方面：
对于一个用链表表示的多项式，在输出时，需要
①先降幂排列（本题采用冒泡排序法，值交换法，也可采用结点交换，但涉及较多指针的赋值）；
本题中输出也是一个难点，综合考虑系数ratio和指数exp。
②然后需要找到系数非零的结点，因为某一项系数为0，则该项无需输出。若没找到，直接输出0；找到则进行下一步。
③对于表达式的第一项，系数无论正负直接输出；指数若为0则无需输出；指数非0则输出指数。
④对于表达式非首项，系数若为正数，需要加“+”号（两项的联结）；系数若为负数，正常输出即可。对于指数，输出法同③。
字符输入方面：
①注意到输入样例，输入数字后换行输入字符，则需要在这两部之间添加“getchar()”吸收一个换行；
②判断输入的字符是否是单引号，不可以使用’’’，应该在一对单引号里面，在字符单引号前面添加一个转义字符，如 ’ \ ’ '。
计算机小白，水平较低，如有更好的思路或建议，欢迎留言！
版权声明：本文不是「本站」原创文章，版权归原作者所有 | 原文地址: