【问题描述】
设计一个一元稀疏多项式简单计算器。
【基本要求】
一元稀疏多项式简单计算器的基本功能是:
- 输入并建立多项式;
- 输出多项式,输出形式为整数序列: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.
#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); }
文章评论