一元稀疏多项式计算器 c语言 数据结构OJ题

标题

一元稀疏多项式计算器

时间限制

2S

内存限制

10000 Kb

问题描述

见习题集P81

问题输入

每组数据有3行构成，第1行为3个正整数n，m，t， n表示第一个多项式的项数，m表示第二个多项式的项数，t表示运算类型，0为加法，1为减法，每组数据的第2行包含2n个整数，每两个整数分别表示第一个多项式每一项的系数和指数；第3行包含2m个整数，每两个整数分别表示第二个多项式每一项的系数和指数。

问题输出

在一行上以多项式形式输出结果，指数按从低到高的顺序

输入样例

6 3 0

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

-1 3 -2 4 1 5

输出样例

1+x-3x^2-x4+2x^5

基本思路

1.初始化链表，创建多项式线性表 polynomial->coefficient, polynomial->index存储 2.switch case/if else完成加减法选择 3.比较系数大小，指数大小将 4.L1,L2插入到L3里 #注意加减法 5.打印一元稀疏多项式

输出注意事项

输出结果时，写一个flag和cnt分别记录是否输出与是否为第一次输出

1.指数为0，直接打印系数，cnt++

2.系数为0，continue

3.系数为1时，指数不同的输出

4.指数为1时，系数不同的输出

5.最普通的情况，系数为负直接输出，系数为正带‘+’输出 #注意是否为第一次输出

6.当多项式相加减的结果为0时，输出为0 #用例942

代码最后Print函数写的比较繁琐…有基本思路就行了

#include<stdio.h> #include<stdlib.h> typedef struct{ int coef; int index; }Term; typedef struct polynomial{ Term term; polynomial* next; }polynomial,*LinkList;//创建单链表存储结构 void InitList(LinkList &L); //初始化链表 int cmp(Term a,Term b); //比较系数大小 void InsertNode(LinkList &L,Term e); //L1,L2插入到L3里 void CreatePolyn(LinkList &L,int m); //创建m项系数的一元多项式 void AddPolyn(LinkList &L,LinkList L1,LinkList L2); //L1+L2 void SubtractPolyn(LinkList &L,LinkList L1,LinkList L2); //L1-L2 void PrintPolyn(LinkList L); //Print List int main(){ int n,m,t; LinkList L1,L2; scanf("%d %d %d",&n,&m,&t); CreatePolyn(L1,n); CreatePolyn(L2,m); LinkList add,sub; if(t==0){ InitList(add); AddPolyn(add,L1,L2); PrintPolyn(add); }else{ InitList(sub); SubtractPolyn(sub,L1,L2); PrintPolyn(sub); } } void InitList(LinkList &L){ //创建头结点 L = (polynomial*)malloc(sizeof(polynomial)); L->term.coef = 0; L->term.index = -1; L->next = NULL; }//初始化链表 int cmp(Term a,Term b){ //compare if(a.index>b.index){ return -1; }else if(a.index==b.index){ return 0; }else{ return 1; } }//比较系数大小 void InsertNode(LinkList &L,Term e){ polynomial* q = L; while(q->next!=NULL){ if(cmp(q->next->term,e)==1){//q的下一个指数>要插入的指数 q = q->next; }else{ break; } }//找到要插入的前一位 if(q->next!=NULL && cmp(q->next->term,e)==0){ //指数相同 q->next->term.coef += e.coef; }else{ polynomial* node = (polynomial*)malloc(sizeof(polynomial)); node->term.coef = e.coef; node->term.index = e.index; if(q->next==NULL){ node->next = NULL;//若为尾结点，node最后加为NULL }else{ node->next = q->next; } q->next = node; } }//L1,L2插入到L3里 void CreatePolyn(LinkList &L,int m){ int i = 1; Term e; InitList(L); for(i=1;i<=m;i++){ scanf("%d %d",&e.coef,&e.index); InsertNode(L,e); } }//创建m项系数的一元多项式 void AddPolyn(LinkList &L,LinkList L1,LinkList L2){ polynomial* q; for(q=L1->next;q!=NULL;q=q->next){ InsertNode(L,q->term); }//L += L1 for(q=L2->next;q!=NULL;q=q->next){ InsertNode(L,q->term); }//L +=L2 }//L1+L2 void SubtractPolyn(LinkList &L,LinkList L1,LinkList L2){ polynomial* q; for(q=L1->next;q!=NULL;q=q->next){ InsertNode(L,q->term); }//L += L1 for(q=L2->next;q!=NULL;q=q->next){ q->term.coef = - (q->term.coef); InsertNode(L,q->term); }//L += -L2 }//L1-L2 void PrintPolyn(LinkList L){ //指数或系数为1时，省略1 polynomial* q = L; int flag; int cnt = 0; while(q->next!=NULL){ q = q->next; flag = 1; if(q->term.coef==0){continue;}//coef==0,pass if(q->term.index==0&&flag==1){ printf("%d",q->term.coef); cnt++; flag = 0; }//index==0,cnt++ if((q->term.coef==1||q->term.coef==-1)&&flag==1){ if(q->term.index==1){ if(q->term.coef==1){ if(cnt==0){ printf("x"); cnt++; }else{ printf("+x"); } }else{ if(cnt==0){ printf("-x"); cnt++; }else{ printf("-x"); } } }else{ if(q->term.coef==1){ if(cnt==0){ printf("x^%d",q->term.index); cnt++; }else{ printf("+x^%d",q->term.index); } }else{ if(cnt==0){ printf("-x^%d",q->term.index); cnt++; }else{ printf("-x^%d",q->term.index); } } } flag = 0; }//coef==1/-1 if(q->term.index==1&&flag==1){ if(q->term.coef>0){ if(cnt==0){ printf("%dx",q->term.coef); cnt++; }else{ printf("+%dx",q->term.coef); } }else{ if(cnt==0){ printf("%dx",q->term.coef); cnt++; }else{ printf("%dx",q->term.coef); } } flag = 0; }//index==1 if(flag==1){ if(cnt==0||q->term.coef<0){ if(cnt==0&&q->term.coef<0){ printf("%dx^%d",q->term.coef,q->term.index); cnt++; }else{ printf("%dx^%d",q->term.coef,q->term.index); } }else{ printf("+%dx^%d",q->term.coef,q->term.index); } }//common } if(cnt==0){ printf("0"); } }//Print List