一元稀疏多项式简单计算器

数据结构课程设计系别计算机与通信工程学院专业计算机科学与技术班级学号姓名指导教师成绩2012年7月12日一、需求分析1、问题描述：（需求分析和背景意义）设计一个一元稀疏多项式简单计算器.2、基本要求：（设计阶段，概要设计和详细设计）一元稀疏多项式简单计算器的基本功能是:(1)输入并建立多项式;(2)输出多项式,输出形式为整数序列:n,c1,e1,c2,e2,…,cn,en,其中n是多项式的项数,ci和ei分别是第i项的系数和指数,序列按指数降序排列;(3)多项式a和b相加,建立多项式a+b;(4)多项式a和b相减,建立多项式a-b.3、测试数据：(2x+5x8-3.1x11)+(7-5x8+11x9)=(-3.1x11+11x9+2x+7)(6x-3-x+4.4x-2-1.2x9)-(-6x-3+5.4x2-x2+7.8x15)(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互换上述测试数据中的前后两个多项式4、实现提示：用带表头结点的单链表存储多项式5、选做内容：(1)计算多项式在x处的值.(2)求多项式a的导函数a′.(3)多项式a和b相乘,建立乘积多项式ab.(4)多项式的输出形式为类数学表达式.例如,多项式-3x8+6x3-18的输出形式为-3x∧8+6x∧3-18,x15+(-8)x7-14的输出形式为x∧15-8x∧7-14.注意,系数值为1的非零次项的输出形式中略去系数1,如项1x8的输出形式为x8,项-1x3的输出形式为-x3.(5)计算器的仿真界面.二、详细设计本程序采用VS2010编写，开始创建了一个工程，本程序的文件有：头文件：define.h用以定义全局变量function.h用以声明函数源文件：function.cpp用以定义函数main.cpp主函数下面罗列每个文件主要代码define.h#ifndefDEFINE_H#defineDEFINE_H#includeiostreamusingnamespacestd;#includestdlib.hstructlinklistmultinomial{floata;inte;structlinklistmultinomial*next;};typedefstructlinklistmultinomial*linklist,node;#endiffunction.h#ifndefFUNCTION_H#defineFUNCTION_H#includedefine.hvoidwelcome();voidgoodbye();linklistcreatelinklist(linklisthead,intn);voidinsert(linklistp,linklisthead);voidprintlinklist(linklisthead);voidaddlinklist(linklistpa,linklistpb);voidsublinklist(linklistpa,linklistpb);voiddlinklist(linklistpa);voidcalclinklista(linklistpd,intx);voidmenu();#endiffunction.cpp#includedefine.h//欢迎界面voidwelcome(){cout\n\n\n\n\n;cout*********************************************************************\n\nendl;cout一元稀疏多项式计算器\n\nendl;cout制作者：王雨辰学号：4100113\n\nendl;cout*********************************************************************\n\n\n\n\n\n\n;cout请输入请求\n\nendl;cout1.进入计算器0.退出\n\nendl;}//结束界面voidgoodbye(){system(cls);cout\n\n\n\n\nendl;cout*********************************************************************\n\nendl;cout谢谢使用，再见\n\nendl;cout*********************************************************************\n\n\n\n\n\n\n;}//创建链表后按照次方从大到小插入voidinsert(linklistp,linklisthead){if(p-a==0)free(p);else{linklistp1,p2;p1=head;p2=p1-next;while(p2&&p2-ep-e){p1=p2;p2=p2-next;}if(p2&&p2-e==p-e){p2-a=p2-a+p-a;free(p);if(p2-a==0){p1-next=p2-next;free(p2);}}else{p-next=p2;p1-next=p;}}}//创建链表linklistcreatelinklist(linklisthead,intn){linklistp;inti;p=head=(linklist)malloc(sizeof(node));head-next=NULL;for(i=1;i=n;i++){p=(linklist)malloc(sizeof(node));cout请输入第i项系数endl;cinp-a;cout请输入第i项指数endl;cinp-e;insert(p,head);}returnhead;}//输出函数voidprintlinklist(linklisthead)s{linklistp=head-next;if(!p)cout0;else//处理首项，若系数为正，省略+{if(p-a==1){if(p-e==0)cout1;elsecoutx^p-e;}elseif(p-a==0);elseif(p-a0){if(p-e==0)coutp-a;elsecoutp-ax^p-e;}else{if(p-e==0)coutp-a;elsecoutp-ax^p-e;}p=p-next;}while(p){if(p-a==1){if(p-e==0)cout+1;elsecout+x^p-e;}elseif(p-a==-1){if(p-e==0)cout-1;elsecout-x^p-e;}elseif(p-a==0);elseif(p-a0){if(p-e==0)coutp-a;elsecoutp-ax^p-e;}else{if(p-e==0)cout'+'p-a;elsecout'+'p-ax^p-e;}p=p-next;}coutendl;}//a+bvoidaddlinklist(linklistpa,linklistpb){linklistpc;linklistp1,p2,p3,p;p3=pc=(linklist)malloc(sizeof(node));p1=pa-next;p2=pb-next;if(!(p1||p2))p3-next=NULL;else{while(p1||p2){p=p3-next=(linklist)malloc(sizeof(node));if(p1==NULL){p-a=p2-a;p-e=p2-e;p2=p2-next;}elseif(p2==NULL){p-a=p1-a;p-e=p1-e;p1=p1-next;}else{if(p1-e==p2-e){p-a=p1-a+p2-a;p-e=p1-e;p1=p1-next;p2=p2-next;}elseif(p1-ep2-e){p-a=p1-a;p-e=p1-e;p1=p1-next;}elseif(p1-ep2-e){p-a=p2-a;p-e=p2-e;p2=p2-next;}}if(p-a==0)free(p);elsep3=p;}p3-next=NULL;}printlinklist(pc);}//a-bvoidsublinklist(linklistpa,linklistpb){linklistpc;linklistp1,p2,p3,p;p3=pc=(linklist)malloc(sizeof(node));p1=pa-next;p2=pb-next;if(!(p1||p2))p3-next=NULL;else{while(p1||p2){p=p3-next=(linklist)malloc(sizeof(node));if(p1==NULL){p-a=p2-a;p-e=p2-e;p2=p2-next;}elseif(p2==NULL){p-a=p1-a;p-e=p1-e;p1=p1-next;}else{if(p1-e==p2-e){p-a=p1-a-p2-a;p-e=p1-e;p1=p1-next;p2=p2-next;}elseif(p1-ep2-e){p-a=p1-a;p-e=p1-e;p1=p1-next;}elseif(p1-ep2-e){p-a=-p2-a;p-e=p2-e;p2=p2-next;}}if(p-a==0)free(p);elsep3=p;}p3-next=NULL;}if(pc-next-next==NULL&&pc-next-a==0)//若a-b=0，输出0cout0endl;elseprintlinklist(pc);}//对a求导voiddlinklist(linklistpa){linklistpd;linklistp1,p4;p1=pa-next;p4=pd=(linklist)malloc(sizeof(node));while(p1!=NULL){p4-next=(linklist)malloc(sizeof(node));p4=p4-next;if(p1-e==0){p4-a=0;p4-e=0;}elseif(p1-e==1){p4-a=p1-a;p4-e=0;}else{p4-e=p1-e-1;p4-a=p1-a*p1-e;}p1=p1-next;}p4-next=NULL;printlinklist(pd);}//计算多项式在x处的值voidcalclinklista(linklistpe,intx){intsum=0,t,i;linklistp5;for(p5=pe-next;p5;p5=p5-next){t=1;for(i=p5-e;i!=0;){if(i0){t/=x;i++;}//指数小于0，进行除法else{t*=x;i--;}//指数大于0，进行乘法}sum+=p5-a*t;}coutsumendl;}//菜单voidmenu(){intm,n,q=1,x;linklistpa=0,pb=0;cout请输入多项式a的项数endl;cinm;pa=c