数据结构上机题1 一元稀疏多项式计算
2017-10-23
一元稀疏多项式计算
题目
参考习题集81页1.5题一元稀疏多项式计算
要求:
- 禁止使用STL库。自己练习链表操作并实现。必须用链表。打钩区分成绩。最多三个√，以半个√为一档表明该项完成程度。检查结束后需要提交源代码。源代码发送到qiweizhen1997@163.com。标注清楚姓名和学号。需不需要写实验报告看今年教务处要求。先别写。
基础要求：
- 最简单的输入输出:(一个√)
- 输入并创建多项式(升序or降序，系数浮点型，指数整型)
- 输出多项式，项数+每项系数指数(升序or降序)
- 多项式相加(结果要输出)
- 多项式相减(结果要输出)
- 最简单的输入输出:(一个√)
拓展：
- 多项式乘法(一个√)
- 计算多项式在x处的值
- 多项式整理，支持乱序输入(2，3项共一个√)
其他可选:
- 除法
- 友好的gui仿真界面
- 句法分析
其余扩展自选
- 由助教根据复杂度和完成度判断是否一个√
注意事项：
- 系数不允许出现0
- 基本要求可以用最简单的输入方法
- 检查过程中或者核对源代码时发现相似度非常高的代码，2人雷同分数除以2，3人除3
测试截图
代码
/*
Last Update time: 2017-10-08
Version：1.2
Author：LinXiang (PB16020923)
Description：
Polynome.
*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define OK 1
#define ERROR 0
typedef int Status;
typedef struct TermOfPolynome{
double c;//Coefficient
int e;//Exponent
struct TermOfPolynome *next;
}term;
typedef term *poly;
typedef struct PolynomeNode{
poly thepoly;
struct PolynomeNode* next;
}polynode;
int Menu_Selected=0,NumOfPoly=0;
polynode *list;//存放多个多项式的链表
char opt[5]={'\0','+','-','*','/'};
//==================system===================
void ShowMenu(){
system("cls");
//printf("0-退出\n1-添加多项式\n2-管理多项式\n3-计算\n4-求值\n");
system("color 0B");
printf("┏━━━━━━━━━━━━━━━━━━━━━━━┓\n");
printf("┃ 多项式运算器V1.1 ┃\n");
printf("┣━━━━━━━┳━━━━━━━┳━━━━━━━┫\n");
printf("┃ 0----退出 ┃ 1-添加多项式 ┃ 2-管理多项式 ┃\n");
printf("┣━━━━━━━╋━━━━━━━╋━━━━━━━┫\n");
printf("┃ 3----计算 ┃ 4----求值 ┃ 5----求导 ┃\n");
printf("┣━━━━━━━┻━━━━━━━┻━━━━━━━┫\n");
printf("┃ 6-关于 ┃\n");
printf("┗━━━━━━━━━━━━━━━━━━━━━━━┛\n");
}
void SendMessage(char *p){
system("cls");
int l=strlen(p),i;
if(l/2*2!=l) l++;//使l能被2整除
printf("┏━");
for(i=0;i<l/2;i++){if(i==l/4-1) printf("信"); else if(i==l/4) printf("息"); else printf("━");}
printf("━┓\n┃ ");
printf(p);
if(strlen(p)!=l) printf(" ");//不是2的倍数长度则补空格
printf(" ┃\n┗━");
for(i=0;i<l/2;i++) printf("━");
printf("━┛\n");
system("pause");
}
void PrintTitle(char *s){
printf("┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n");
printf("┃ %s ┃\n",s);
printf("┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");
}
void BackSpace(int n){//删除n个字符
int i;
for(i=0;i<n;i++) printf("\b");
for(i=0;i<n;i++) printf(" ");
for(i=0;i<n;i++) printf("\b");
}
int GetZeroNum(char *p){//计算浮点数末尾有几个0
char *q=p;
int count=0;
while(*q++!='.');
while(*q){
if(*q++=='0') count++;
else count=0;
}
return count;
}
void ShowPoly(poly pl){
if(pl->next==NULL) printf("0\n");
else{
term *q=pl->next;
while(q!=NULL){
char s[100];
sprintf(s,"%6lf",q->c);//临时打印出系数
int zn=GetZeroNum(s);
char text[10]="%s%.6lf";//格式文本
text[4]=6-zn+'0';//修改该显示的小数位数，删尾0
printf(text,q->c<0?"\b":"",q->c);//系数小于0,删'+'
if(q->e){//指数不为0
printf("%sX^%s%d%s",fabs(fabs(q->c)-1)<1e-6?"\b \b":""\
,q->e<0?"(":"",q->e,q->e<0?")":"");
}
if(q->e==1) BackSpace(2);//删除"^1"
printf("+");
q=q->next;
}
printf("\b \n");
}
}
void ShowAllPoly(polynode *list){
int i;
polynode *p=list->next;
printf("==================================多项式列表==================================\n");
for(i=0;i<NumOfPoly;i++,p=p->next){
printf("(%d) ",i+1);
ShowPoly(p->thepoly);
}
printf("====================================共%2d个====================================\n",NumOfPoly);
}
//======================term=====================
term *MakeTerm(double c,int e){//创建一个项
term *p=(term *)malloc(sizeof(term));
p->c=c;
p->e=e;
p->next=NULL;
return p;
}
Status DeleteTermFromPolyByExponent(poly pl,int e){
term *q=pl;
while(q->next!=NULL && q->next->e!=e){
q=q->next;
}
if(q->next==NULL) return ERROR;
else{
term *r=q->next;
q->next=q->next->next;
free(r);
}
return OK;
}
Status InsertTermToPolyInOrder(poly pl,term *t){//插入后该项将成为多项式的一部分或被销毁
term *q=pl;
while(q->next!=NULL && q->next->e>t->e){
q=q->next;
}
if(q->next==NULL){
q->next=t;
t->next=NULL;
}
else if(q->next->e==t->e){
q->next->c+=t->c;
free(t);
if(fabs(q->next->c)<1e-6) DeleteTermFromPolyByExponent(pl,q->next->e);
}
else{
t->next=q->next;
q->next=t;
}
return OK;
}
//======================poly=====================
Status InitPoly(poly *pl){//这里传进指针的指针，是为了修改pl的值
*pl=MakeTerm(0,0);
return OK;
}
Status DestoryPoly(poly *pl){
term *q=*pl,*s;
while(q!=NULL){
s=q->next;
free(q);
q=s;
}
*pl=NULL;
return OK;
}
Status AddPolyToList(polynode *list,poly pl){//把一个多项式加入到全局的列表里
polynode *p=list;
while(p->next!=NULL) p=p->next;
p->next=(polynode *)malloc(sizeof(polynode));
p=p->next;
p->thepoly=pl;
p->next=NULL;
NumOfPoly++;
}
Status DeletePolyFromListById(polynode *list,int id){
polynode *p=list;
int i=1;
while(p->next!=NULL && i++<id) p=p->next;//找到要删除的前一个
if(p->next==NULL) return ERROR;
polynode *q=p->next;
p->next=p->next->next;
DestoryPoly(&(q->thepoly));
free(q);
NumOfPoly--;
return OK;
}
poly LocatePolyById(polynode *list,int id){
polynode *p=list->next;
int i=1;
while(p!=NULL && i++<id) p=p->next;
return p->thepoly;
}
//======================calculate=====================
poly Add(poly pl1,poly pl2){
poly pl;
InitPoly(&pl);
term *q1=pl1->next,*q2=pl2->next,*q=pl;
while(q1!=NULL && q2!=NULL){
if(q1->e>q2->e){
q->next=MakeTerm(q1->c,q1->e);
q1=q1->next;
}
else if(q1->e<q2->e){
q->next=MakeTerm(q2->c,q2->e);
q2=q2->next;
}
else{
if(fabs(q1->c+q2->c)>1e-6) q->next=MakeTerm(q1->c+q2->c,q1->e);//不被抵消才加入
q1=q1->next;
q2=q2->next;
}
if(q->next!=NULL) q=q->next; //如果已经创建了下一项才后移
}
while(q1!=NULL){
q->next=MakeTerm(q1->c,q1->e);
q1=q1->next;
q=q->next;
}
while(q2!=NULL){
q->next=MakeTerm(q2->c,q2->e);
q2=q2->next;
q=q->next;
}
return pl;
}
poly Subtract(poly pl1,poly pl2){
poly pl;
InitPoly(&pl);
term *q1=pl1->next,*q2=pl2->next,*q=pl;
while(q1!=NULL){
term *tq1=MakeTerm(q1->c,q1->e);
InsertTermToPolyInOrder(pl,tq1);
q1=q1->next;
}
while(q2!=NULL){
term *tq2=MakeTerm(-q2->c,q2->e);
InsertTermToPolyInOrder(pl,tq2);
q2=q2->next;
}
return pl;
}
poly Multiply(poly pl1,poly pl2){
poly pl;
InitPoly(&pl);
term *q1=pl1->next,*q2=pl2->next,*q=pl;
while(q1!=NULL){
while(q2!=NULL){
term *tq=MakeTerm(q1->c*q2->c,q1->e+q2->e);
InsertTermToPolyInOrder(pl,tq);
q2=q2->next;
}
q1=q1->next;
q2=pl2->next;
}
return pl;
}
Status GetHighestE(poly pl,double *c,int *e){//取最高次的次数和系数
term *q=pl;
if(q->next==NULL){
*c=0;
*e=0;
return OK;
}
q=q->next;
*c=q->c;
*e=q->e;
return OK;
}
Status CopyPoly(poly *pl1,poly *pl2){//2to1
InitPoly(pl1);
term *q2=(*pl2)->next,*q1=*pl1;
while(q2!=NULL){
q1->next=MakeTerm(q2->c,q2->e);
q2=q2->next;
q1=q1->next;
}
return OK;
}
Status Divide(poly pl1,poly pl2,poly *res,poly *left){//res,left传递指向poly类型的指针
CopyPoly(left,&pl1);
poly xnpl;
InitPoly(&xnpl);
InitPoly(res);
int de,e1,e2;
double c1,c2;
GetHighestE(pl2,&c2,&e2);
GetHighestE(*left,&c1,&e1);
de=e1-e2;
while(de>=0 && (*left)->next!=NULL){//余数与除数最高次之差大于0 且余式不为0
term *xn=MakeTerm(c1/c2,de);
xnpl->next=xn;
poly tmp=Multiply(pl2,xnpl);
poly tmpleft=Subtract(*left,tmp);
DestoryPoly(left);
CopyPoly(left,&tmpleft);
DestoryPoly(&tmpleft);
InsertTermToPolyInOrder(*res,xn);
GetHighestE(*left,&c1,&e1);
de=e1-e2;
}
return OK;
}
poly Calculate(poly pl1,poly pl2,int op){
switch(op){
case 1: return Add(pl1,pl2);
case 2: return Subtract(pl1,pl2);
case 3: return Multiply(pl1,pl2);
}
}
double Value(poly pl,double x){//求值
term *q=pl->next;
double sum=0;
while(q!=NULL){
sum+=q->c*pow(x,q->e);
q=q->next;
}
return sum;
}
poly Dfx(poly pl1){ //求导
poly pl;
InitPoly(&pl);
term *q1=pl1->next,*q=pl;
while(q1!=NULL){
if(q1->e){//非常数项
q->next=MakeTerm(q1->c*q1->e,q1->e-1);
q=q->next;
}
q1=q1->next;
}
return pl;
}
//======================menu=====================
int Menu_Add(){
double c;int e;
system("cls");
PrintTitle("添加");
printf("依次输入每项的系数和指数，空格隔开，ctrl+z结束:\n");
poly pl;
InitPoly(&pl);
while(scanf("%lf",&c)!=EOF){
if(scanf("%d",&e)==EOF){
DestoryPoly(&pl);
return 1;
}
if(fabs(c)<1e-6) continue;
term *t=MakeTerm(c,e);
InsertTermToPolyInOrder(pl,t);
}
AddPolyToList(list,pl);
return 0;
}
int Menu_Delete(){
int s;
system("cls");
PrintTitle("管理");
if(NumOfPoly==0) return 1;
else ShowAllPoly(list);
printf("\n选择一个多项式删除。输入序号数字(输入0返回): ");
scanf("%d",&s);
if(s>0){
if(DeletePolyFromListById(list,s)==ERROR) return 2;
else return 0;
}
return -1;
}
int Menu_Calculate(){
int s1,s2,op;
system("cls");
PrintTitle("计算");
if(NumOfPoly==0) return 1;
else ShowAllPoly(list);
printf("\n选择两个多项式和一种运算符[ (1)+ (2)- (3)* (4)/ ]。\n依次输入多项式和运算符序号(空格隔开,回车结束,输入0返回): ");
scanf("%d",&s1);
if(s1==0) return 0;
scanf("%d",&s2);
if(s1<0 || s2<0 || s1>NumOfPoly || s2>NumOfPoly) return 2;
scanf("%d",&op);
if(op<=0 || op>4) return 2;
printf("\n===================================运算结果===================================\n");
poly pl1=LocatePolyById(list,s1);
poly pl2=LocatePolyById(list,s2);
poly pl;
poly left;
if(op==4){
if(pl2->next==NULL) return 3;
Divide(pl1,pl2,&pl,&left);
}
else{
pl=Calculate(pl1,pl2,op);
}
ShowPoly(pl1);
printf("%c\n",opt[op]);
ShowPoly(pl2);
printf("=\n");
ShowPoly(pl);
if(op==4){
printf("...\n");
ShowPoly(left);
}
DestoryPoly(&pl);
if(op==4) DestoryPoly(&left);
printf("==============================================================================\n");
system("pause") ;
return -1;
}
int Menu_Value(){
int s;
double x;
system("cls");
PrintTitle("求值");
if(NumOfPoly==0) return 1;
else ShowAllPoly(list);
printf("\n选择一个多项式求值。\n依次输入多项式序号和X值(空格隔开,回车结束,输入0返回): ");
scanf("%d",&s);
if(s==0) return 0;
if(s<0 || s>NumOfPoly) return 2;
scanf("%lf",&x);
printf("\n===================================运算结果===================================\n");
poly pl=LocatePolyById(list,s);
ShowPoly(pl);
printf("在 X = %lf 处的值为:\n%lf\n",x,Value(pl,x));
printf("==============================================================================\n");
system("pause") ;
return -1;
}
int Menu_Dfx(){
int s,n;
system("cls");
PrintTitle("求导");
if(NumOfPoly==0) return 1;
else ShowAllPoly(list);
printf("\n选择一个多项式求导。\n输入多项式序号和求导次数n(空格隔开,回车结束,输入0返回): ");
scanf("%d",&s);
if(s==0) return 0;
scanf("%d",&n);
if(n<1 ||s<0 || s>NumOfPoly) return 2;
printf("\n===================================运算结果===================================\n");
poly pl=LocatePolyById(list,s);
printf("F(X)=");
ShowPoly(pl);
int i;
poly tmp1,tmp2;
CopyPoly(&tmp2,&pl);
for(i=1;i<=n;i++){
printf("F(X)^(%d)=",i);
tmp1=Dfx(tmp2);
DestoryPoly(&tmp2);
CopyPoly(&tmp2,&tmp1);
DestoryPoly(&tmp1);
ShowPoly(tmp2);
}
DestoryPoly(&tmp2);
printf("==============================================================================\n");
system("pause") ;
return -1;
}
int About(){
system("cls");
printf("┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n");
printf("┃ About ┃\n");
printf("┣━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫\n");
printf("┃ PolynomeCalculator V1.1 ┃\n");
printf("┃ Made by LX 2017.10.06 ┃\n");
printf("┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");
system("pause");
return 0;
}
int main(){
list=(polynode *)malloc(sizeof(polynode));
list->next=NULL;
ShowMenu();
printf("请选择：");
//printf("abcdefg\b\b\b12");
scanf("%d",&Menu_Selected);
while(Menu_Selected){
int status;
switch(Menu_Selected){
case 1: if(Menu_Add()==1)
SendMessage("输入有误!系数个数与指数个数不匹配！");
else{
SendMessage("添加成功！");
}
break;
case 2: status=Menu_Delete();
if(status==1)
SendMessage("这里空空如也...");
else if(status==2){
SendMessage("输入的序号有误！");
}
else if(status==0){
SendMessage("删除成功");
}
break;
case 3: status=Menu_Calculate();
if(status==1){
SendMessage("你需要先添加多项式~");
}
else if(status==2){
SendMessage("输入的序号有误！");
}
else if(status==3){
SendMessage("0不能为除数！");
}
break;
case 4: status=Menu_Value();
if(status==1){
SendMessage("你需要先添加多项式~");
}
else if(status==2){
SendMessage("输入的序号和X值有误！");
}
break;
case 5: status=Menu_Dfx();
if(status==1){
SendMessage("你需要先添加多项式~");
}
else if(status==2){
SendMessage("输入的序号和n值有误！");
}
break;
case 6: About();
break;
}
ShowMenu();
printf("请选择：");
scanf("%d",&Menu_Selected);
}
return 0;
}