一元稀疏多项式简单计算器
问题描述
设计一个一元稀疏多项式简单计算器
基本要求
一元稀疏多项式简单计算器的基本功能是:
(1)输入并建立多项式;
(2)输出多项式,输出形式为整数序列:n,c1,e1,c2,e2,……,cn,en,其中n是多项式的项数,ci和ei分别是第i项的系数和指数,序列按指数降序排列;
(3)多项式a和b相加,建立多项式a+b;
(4)多项式a和b相减,建立多项式a-b。
(5)计算多项式在X处的值。
(6)计算多项式a的导函数a’。
(7)多项式a和b相乘,建立乘积多项式ab。
(8)多项式的输出形式为类数学表达式。例如,多项式-3x8+6x3-18的输出形式为-3x8+6x3-18。注意,系数为1的非零次项的输出形式中略去系数1,如1x8的输出形式为x^8。
(9)计算器的仿真界面。
测试数据
(1)(2x+5x3-3.1x11)+(7-5x8+11x9)=(-3.1x11+11x9+2x+7)
(2)(6x-3-X+4.4X2-1.2X9)-(-6X-3+5.4X2-X2+7.8X15)=(-7.8X15-1.2X9+12X-3-X)
(3)(1+X+X2+X3+X4+X5)+(-X3-X4)=(1+X+X2+X5)
(4)(X+X3)+(-X-X3)=0
程序结果
A+B
A*B
C的倒数
C在x=2处的值
程序代码
#include "stdafx.h"
#include<stdio.h>
#include<stdlib.h>
#include <string.h>
#include <iostream.h>
#include <iomanip.h>
#include <conio.h>
#include <process.h>
#include <math.h>
#include <fstream.h>
#include <windows.h>
#define MAX 80
struct polynomial{ //多项式
double Coefficient; //系数
int index; //指数
int Rauk; //待定
polynomial *next; //链接
};
double Realization(char *str);
void push(polynomial *head,double Coefficient,int index) ;
double Realization(char *str);
void display(polynomial *head);//显示
void Build(polynomial *Aa,polynomial *Bb);
int xue(polynomial *head);
void del(polynomial *DLList1,double Coefficient,int index);
void sort(polynomial *DLList1);//排序
void Inverselist(polynomial *DLList1);//逆置
void algorithm(polynomial *Aa,polynomial *Bb,polynomial *Cc,int CD);
void Derivatives(polynomial *Dao,int e);
double ValueofX(polynomial *X,int e);
void Formattedoutput(polynomial *abc);//格式化输出
void goto_xy(int x,int y);
void quick(polynomial *Ac);
void ssss();
void ck(polynomial *Aa,polynomial *Bb,polynomial *Cc)
{
goto_xy(0,0); printf("┏━━━━━━━━━━━━━━━━━━━━━━━━┓\n");
goto_xy(0,1); printf("┃ ∞一元稀疏多项式简单计算器∞ ┃\n");
goto_xy(0,2); printf("┣━━━━━━━━━━━━━━━━━━━━━━━━┫");
goto_xy(0,3); printf("┃\n");goto_xy(50,3); printf("┃\n");
goto_xy(0,4); printf("┃\n");goto_xy(50,4); printf("┃\n");
goto_xy(0,5); printf("┃\n");goto_xy(50,5); printf("┃\n");
goto_xy(0,6); printf("┣━━━━━━━━━━━━━━━━━━━━━━━━┫");
goto_xy(0,7); printf("┃A :"); goto_xy(5,7); Formattedoutput(Aa); goto_xy(50,7); printf("┃");
goto_xy(0,8); printf("┣━━━━━━━━━━━━━━━━━━━━━━━━┫");
goto_xy(0,9); printf("┃B :");goto_xy(5,9);Formattedoutput(Bb); goto_xy(50,9); printf("┃");
goto_xy(0,10); printf("┣━━━━━━━━━━━━━━━━━━━━━━━━┫");
goto_xy(0,11); printf("┃C :");goto_xy(5,11);Formattedoutput(Cc);goto_xy(50,11); printf("┃");
goto_xy(0,12); printf("┣━━━━━━━┳━━━━━━━━┳━━━━━━━┫");
goto_xy(0,13); printf("┃ 7.A+B ┃ 8.A-B ┃ 9.A*B ┃\n");
goto_xy(0,14); printf("┣━━━━━━━╋━━━━━━━━╋━━━━━━━┫");
goto_xy(0,15); printf("┃ 4.A(x)' ┃ 5.B(x)' ┃ 6.C(x)' ┃");
goto_xy(0,16); printf("┣━━━━━━━╋━━━━━━━━╋━━━━━━━┫");
goto_xy(0,17); printf("┃ 1.A(x) ┃ 2.B(x) ┃ 3.C(x) ┃");
goto_xy(0,18); printf("┣━━━━━━━╋━━━━━━━━╋━━━━━━━┫");
goto_xy(0,19); printf("┃ Enter ┃ 0.输入 ┃ t.退出 ┃");
goto_xy(0,20); printf("┣━━━━━━━╋━━━━━━━━╋━━━━━━━┫");
goto_xy(0,21); printf("┃ a.清除A ┃ b.清除B ┃ c.清除C ┃");
goto_xy(0,22); printf("┗━━━━━━━┻━━━━━━━━┻━━━━━━━┛");
goto_xy(1,23); printf("【 s.简单计算器的操作说明】");
goto_xy(2,3);
}
void gotoxy(int x,int y)
{ CONSOLE_SCREEN_BUFFER_INFO csbiInfo;
HANDLE hConsoleOut;
hConsoleOut = GetStdHandle(STD_OUTPUT_HANDLE);
GetConsoleScreenBufferInfo(hConsoleOut,&csbiInfo);
csbiInfo.dwCursorPosition.X = x;
csbiInfo.dwCursorPosition.Y = y;
SetConsoleCursorPosition(hConsoleOut,csbiInfo.dwCursorPosition);
}
int main()
{
polynomial *Aa=new polynomial;Aa->next=NULL;
polynomial *Bb=new polynomial;Bb->next=NULL;
polynomial *Cc=new polynomial;Cc->next=NULL;
system("title my ");
system("mode con cols=52 lines=25");
system("color e0");
char ch,bh;
double sum=0;
while (1)
{
system("cls");
ck(Aa,Bb,Cc);
ch=getch();
// system("cls");
switch(ch)
{
case '0':
Build(Aa,Bb);
break;
case '1':
ValueofX(Aa,1);bh=getch();
break;
case '2':
ValueofX(Bb,2);bh=getch();
break;
case '3':
ValueofX(Cc,3);bh=getch();
break;
case '4':
Derivatives(Aa,1);bh=getch();
break;
case '5':
Derivatives(Bb,2);bh=getch();
break;
case '6':
Derivatives(Cc,3);bh=getch();
break;
case '7':
algorithm(Aa,Bb,Cc,1);
break;
case '8':
algorithm(Aa,Bb,Cc,2);
break;
case '9':
algorithm(Aa,Bb,Cc,3);
break;
case 's':
ssss();bh=getch();
break;
case 'a':
quick(Aa);
break;
case 'b':
quick(Bb);
break;
case 'c':
quick(Cc);
break;
case 't':
exit(0);
}
}
return 0;
}
void quick(polynomial *Ac)
{
polynomial *p,*q;
p=Ac;
while (p->next!=NULL)//初始化
{
q=p->next;
p->next=q->next;
free(q);
}
Ac->next=NULL;
}
void Build(polynomial *Aa,polynomial *Bb)
{
int i=0;
double Coefficient;
int index;
char strA[MAX],strB[MAX],str[MAX];
goto_xy(2,3);printf("polynomial A : "); gets(strA);
goto_xy(2,4);printf("polynomial B : "); gets(strB);
strcpy(str,strA);//printf("%s",str);system("pause");
while(*(str+i))
{
Coefficient=Realization(str+i);
if(*(str+i)!='x')i++;
while((*(str+i)>='0'&&*(str+i)<='9')||(*(str+i)=='.'))
i++;
if(*(str+i)=='+'||*(str+i)=='-'||*(str+i)=='\0')
index=0;
else
if(*(str+i)=='x')
{
i++;
if(*(str+i)=='+'||*(str+i)=='-'||*(str+i)=='\0')
index=1;
else
if(*(str+i)=='^')
{
i++;
index=(int) Realization(str+i);
while((*(str+i)>='0'&&*(str+i)<='9')||(*(str+i)=='.'))i++;
// i--;
}
}//system("pause");
// printf("double=%lf\n",Coefficient);
// printf("index=%d\n",index);
push(Aa,Coefficient,index);//system("pause");
xue(Aa);//Formattedoutput(c);
}
strcpy(str,strB);//printf("%s",str);system("pause");
i=0;
while(*(str+i))
{
Coefficient=Realization(str+i);
if(*(str+i)!='x')i++;
while((*(str+i)>='0'&&*(str+i)<='9')||(*(str+i)=='.'))
i++;
if(*(str+i)=='+'||*(str+i)=='-'||*(str+i)=='\0')
index=0;
else
if(*(str+i)=='x')
{
i++;
if(*(str+i)=='+'||*(str+i)=='-'||*(str+i)=='\0')
index=1;
else
if(*(str+i)=='^')
{
i++;
index=(int) Realization(str+i);
while((*(str+i)>='0'&&*(str+i)<='9')||(*(str+i)=='.'))i++;
// i--;
}
}//system("pause");
// printf("double=%lf\n",Coefficient);
// printf("index=%d\n",index);
push(Bb,Coefficient,index);//system("pause");
}xue(Bb);//Formattedoutput(c);
}
void Formattedoutput(polynomial *abc)//格式化输出
{
polynomial *p;
p=abc;
if(p->next==NULL){printf("0");/*system("pause");*/return ;}
if(p->next->Coefficient==0)
{
printf("0\t");
// system("pause");
return ;
}
printf(" (");
while(p->next)
{
p=p->next;
if(p->Coefficient==0){p=p->next;continue;}
if(p->Coefficient==1||p->Coefficient==-1)
{
if(p->index==0){printf("%g",p->Coefficient);continue;}
if(p->Coefficient==-1&&p->index!=0)printf("-");
}else
printf("%g",p->Coefficient);
if(p->index>0){
printf("x");
if(p->index>1){
printf("^");
printf("%d",p->index);
}
}
if(p->next!=NULL)
{
if(p->next->Coefficient>0)printf("+");
}
}printf(")\t\t");
}
double ValueofX(polynomial *X,int e)
{
double x,sum=0;
polynomial *a=X;
goto_xy(2,3);printf(" X = ");
scanf("%lf",&x);
while(a->next)
{
sum+=(a->next->Coefficient)*pow(x,a->next->index);
a=a->next;
}//printf("%g",sum);
goto_xy(2,4);
if(e==1)printf(" A ( %g ) = %g",x,sum);
if(e==2)printf(" B ( %g ) = %g",x,sum);
if(e==3)printf(" C ( %g ) = %g",x,sum);
return sum;
}
void Derivatives(polynomial *Dao,int e)
{
polynomial *dd=new polynomial;dd->next=NULL;
polynomial *a=Dao;
while(a->next)
{
if(a->next->index!=0)
push(dd,(a->next->Coefficient)*(a->next->index),a->next->index-1);
a=a->next;
}
goto_xy(2,4);
if(e==1)printf(" A(x)' = ");
if(e==2)printf(" B(x)' = ");
if(e==3)printf(" C(x)' = ");
Formattedoutput(dd);
}
void algorithm(polynomial *Aa,polynomial *Bb,polynomial *Cc,int CD)
{
polynomial *a=Aa;
polynomial *b=Bb;
polynomial *c=Cc;
quick(Cc);
if(CD==1)//+
{
while(a->next){push(c,a->next->Coefficient,a->next->index);a=a->next;}
while(b->next){push(c,b->next->Coefficient,b->next->index);b=b->next;}
xue(c);Formattedoutput(c);
}
if(CD==2)//-
{
while(a->next){push(c,a->next->Coefficient,a->next->index);a=a->next;}
while(b->next){push(c,-(b->next->Coefficient),b->next->index);b=b->next;}
xue(c);Formattedoutput(c);
}
if(CD==3)//*
{
while(a->next)
{
b=Bb;
while(b->next)
{
push(c,(a->next->Coefficient)*(b->next->Coefficient),(a->next->index)+(b->next->index));
b=b->next;
}
a=a->next;
}
xue(c);Formattedoutput(c);
}
}
void sort(polynomial *DLList1)//直接插入排序
{
polynomial *p,*q,*r;
polynomial heah; //头结点
p=&heah;
heah.next=NULL;//使头指针指向头结点*/
p=DLList1;
DLList1->index=0; //顺序表的直接插入排序
DLList1->Coefficient=0;
if(p->next==NULL||p->next->next==NULL) //空表或只有一个元素
return;
for(p=p->next->next;p!=NULL;p=p->next) //for(i=2;i<=n;i++){
{
DLList1->index=p->index; //r[0]=r[i];
DLList1->Coefficient=p->Coefficient;
q=DLList1;
while(q->next!=p)q=q->next; //j=i-1; //j从i-1到0,从后向前比较
while(DLList1->index<q->index) //while(r[0]<r[j]) //表明r[0]在r[j]前
{
q->next->index=q->index; // { r[j+1]=r[j]; //r[j]后移一个位置
q->next->Coefficient=q->Coefficient;
r=q; //
q=DLList1; //j--;
while(q->next!=r)q=q->next; //
} // } j=0时,循环条件必不成立
q->next->index=DLList1->index; //r[j+1]=r[0];
q->next->Coefficient=DLList1->Coefficient;
} // }
}
void del(polynomial *DLList1,double Coefficient,int index)
{
polynomial *p,*q;
p=DLList1;
while(p->next)
{
if(p->next->index==index&&p->next->Coefficient==Coefficient)break;
p=p->next;
}
if(p->next&&p->next->index==index&&p->next->Coefficient==Coefficient){//p->next可能是NULL
q=p->next;
if(q->next)
{
p->next=q->next;//p->next存在
}
else
{
p->next=NULL;//q->next是NULL
}
free(q);
}
}
void Inverselist(polynomial *DLList1)//逆置
{
polynomial *p,*q,*heah;
heah=DLList1;
if(heah->next==NULL||heah->next->next==NULL)//空表或只有一个元素
return;
p=heah->next->next; //p指向第二个元素
heah->next->next=NULL; //第一个元素构成单个元素的链表
while(p!=NULL)
{
q=p->next; //q指向下一个元素
p->next=heah->next; //把p插入第一个元素前
heah->next=p;
p=q;
}
}
int xue(polynomial *head)
{
polynomial *p,*q;
p=head;
while(p->next)
{
// display(p);
q=p->next;
while(q->next!=NULL)
{
if(p->next->index==q->next->index)
{
p->next->Coefficient=q->next->Coefficient+p->next->Coefficient;
del(head,q->next->Coefficient,q->next->index);
Formattedoutput(head);
}
else
q=q->next;
}
p=p->next;
}//printf("xus ok");
// display(head);
sort(head);
Inverselist(head);
return 0;
}
void push(polynomial *head,double Coefficient,int index)
{
polynomial *L = NULL;
polynomial *p = NULL;
L = head;
while (L->next != NULL)
{
L = L->next;//遍历找到尾节点
}
p = new polynomial;//开辟新的节点
p->Coefficient = Coefficient;//赋值
p->index=index;
p->next = NULL;//设置为尾节点
L->next = p;//挂在原来尾节点之后
return ;
}
double Realization(char *str)
{
double s=0.0;
double d=10.0;
int jishu=0;
bool falg=false;
while(*str==' ')
{
str++;
}
if(*str=='-')//记录数字正负
{
falg=true;
str++;
if(*str=='x')
return -1.0;
}
else
if((*str=='+'&&*(str+1)=='x')||(*str=='x'))
{
return 1.0;
}
if(*str=='+'&&(*(str+1)>='0'&&*(str+1)<='9'))str++;
if(!(*str>='0'&&*str<='9'))//如果一开始非数字则退出,返回0.0
return s;
while(*str>='0'&&*str<='9'&&*str!='.')//计算小数点前整数部分
{
s=s*10.0+*str-'0';
str++;
}
if(*str=='.')//以后为小树部分
str++;
while(*str>='0'&&*str<='9')//计算小数部分
{
s=s+(*str-'0')/d;
d*=10.0;
str++;
}
if(*str=='e'||*str=='E')//考虑科学计数法 其实不需要,,,
{
str++;
if(*str=='+')
{
str++;
while(*str>='0'&&*str<='9')
{
jishu=jishu*10+*str-'0';
str++;
}
while(jishu>0)
{
s*=10;
jishu--;
}
}
if(*str=='-')
{
str++;
while(*str>='0'&&*str<='9')
{
jishu=jishu*10+*str-'0';
str++;
}
while(jishu>0)
{
s/=10;
jishu--;
}
}
}
return s*(falg?-1.0:1.0);
}
void goto_xy(int x,int y)
{
HANDLE hOut;
hOut = GetStdHandle(STD_OUTPUT_HANDLE);
COORD pos={x,y};
SetConsoleCursorPosition(hOut,pos);
}
void ssss()
{
system("cls");
printf("\n\n\t\t没有!!!");
}