【问题描述】
设计一个一元稀疏多项式简单计算器。
【基本要求】
一元稀疏多项式简单计算器的基本功能是：
- 输入并建立多项式；
- 输出多项式，输出形式为整数序列：n,c1,e1,c2,e2,…,cn,en,其中n是多项式的项数，ci,ei分别是第i项的系数和指数，序列按指数降序排列；
- 多项式a和b相加，建立多项式a b；
- 多项式a和b相减，建立多项式a-b。
【测试数据】
- (2x 5x8-3.1x11) (7-5x8 11x9)=(-3.1x11 11x9 2x 7)；
- (6x-3-x 4.4x2-1.2x9)-(-6x-3 5.4x2-x2 7.8x15)=(-7.8x15-1.2x9 12x-3-x)；
- (1 x x2 x3 x4 x5) (-x3-x4)=(1 x x2 x5)；
- (x x3) (-x-x3)=0
- (x x100) (x100 x200)=(x 2x100 x200)；
- (x x2 x3) 0=(x x2 x3)；
- 互换上述测试数据中的前后两个多项式。
解析：
看完题目和测试数据你或许会和我一样纳闷，题目要求的输出中 序列按指数降序排列，而测试数据中的示例输出却有升序的 有降序的 还有不是升序的也不是降序的。
没错，相信你的直觉，测试数据并不规范！
这里简单讲一下思路：用线性表的链式存储方式先读入输入数据到两个线性表L1 L2中，然后再初始化一个线性表L，比较L1、L2中结点的次数大小，将较大的先插入，相等的合并插入，剩余的连到线性表L的后面即可。具体在addition函数中。
Talk is cheap,show you the code.
代码语言：javascript复制#include<stdio.h>
#include<stdlib.h>
// Code by Titan 2020-03-09
//定义链表结构
typedef struct LNode *PtrToNode;
struct LNode {
double val; // 系数
int num; // 次数(幂)
PtrToNode next; // 指向下一个结点
};
typedef PtrToNode List;
//初始化链表
List initList(int n) {
//先初始化一个头结点
List Head = (List)malloc(sizeof(struct LNode));
List L = Head;
double a[n]; //用于存放输入数据，反向存储;
int b[n];
for(int i=0; i<n; i ) {
scanf("%lf %d",&a[i],&b[i]);
}
for(int i=1;i<n;i ){
if(b[i-1]==b[i]){
a[i-1] =a[i];
a[i]=0;
}
}
for(int i=n-1; i>=0; i--) {
//初始化一个结点
if(a[i]==0){
continue;
}
List Temp = (List)malloc(sizeof(struct LNode));
Temp->val=a[i];
Temp->num=b[i];
Temp->next=NULL;
L->next=Temp;
L=Temp;
}
//返回头结点
return Head;
}
// 多项式加法
List addition(List L1,List L2) {
//初始化一个链表
List L = (List)malloc(sizeof(struct LNode));
List P = L;
L1=L1->next;
L2=L2->next;
while(L1 && L2) {
List Temp=(List)malloc(sizeof(struct LNode));
if(L1->num == L2->num) {
Temp->val=L1->val L2->val;
Temp->num=L1->num;
L1=L1->next;
L2=L2->next;
} else if(L1->num > L2->num) {
Temp->val=L1->val;
Temp->num=L1->num;
L1=L1->next;
} else {
Temp->val=L2->val;
Temp->num=L2->num;
L2=L2->next;
}
P->next=Temp;
P=Temp;
}
// 把剩余部分接到后面;
if(L1) {
P->next=L1;
} else {
P->next=L2;
}
return L;
}
// 多项式减法 将第二个链表取负数即可
List subtraction(List L1,List L2) {
List NewL = L2->next;
while(NewL) {
NewL->val=-NewL->val;
NewL=NewL->next;
}
List L=addition(L1,L2);
return L;
}
void printList(List L) {
if(L->next) {
L=L->next;
if(L->val==1.0){
printf("X^%d",L->num);
}else if(L->val==-1.0){
printf("-X^%d",L->num);
}else if(L->val!=0){
printf("%gX^%d",L->val,L->num);
}else{
printf("0");
}
}
while(L->next) {
L=L->next;
if(L->val==1.0) {
if(L->num==1) {
printf(" X",L->num);
} else if(L->num==0) {
printf(" 1");
} else {
printf(" X^%d",L->num);
}
} else if(L->val==-1.0) {
if(L->num==1) {
printf("-X",L->num);
} else if(L->num==0) {
printf("-1");
} else {
printf("-X^%d",L->num);
}
} else if(L->val>1e-10) {
if(L->num==1) {
printf(" %gX",L->val,L->num);
} else if(L->num==0) {
printf(" %g",L->val);
} else {
printf(" %gX^%d",L->val,L->num);
}
} else if(L->val<-1e-10) {
if(L->num==1) {
printf("%gX",L->val,L->num);
} else if(L->num==0) {
printf("%g",L->val);
} else {
printf("%gX^%d",L->val,L->num);
}
}
}
printf("n");
}
int main(void) {
int n;
scanf("%d",&n);
List L1 =initList(n);
scanf("%d",&n);
List L2=initList(n);
printf("输入的第一个多项式是:");
printList(L1);
printf("输入的第二个多项式是:");
printList(L2);
List L=(List)malloc(sizeof(struct LNode));
printf("请输入运算符:");
char op;
getchar();
scanf("%c",&op);
if(op==' ') {
L=addition(L1,L2);
} else if(op=='-') {
L=subtraction(L1,L2);
} else {
printf("输入的运算符有误");
return -1;
}
printf("计算后的多项式结果为:");
printList(L);
free(L);
}
