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

1、一元稀疏多项式简单计算器 数据结构课程设计 系 别计算机与通信工程学院专 业计算机科学与技术班级学号姓 名 指导教师成 绩 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、测试数据：(2

2、x+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)

3、多项式的输出形式为类数学表达式.例如,多项式-3x8+6x3-18的输出形式为-3x8+6x3 -18,x15+(-8)x7-14的输出形式为x15-8x7-14.注意,系数值为1 的非零次项的输出形式中略去系数1,如项1x8的输出形式为x8,项-1x3的输出形式为-x3.(5) 计算器的仿真界面.二、详细设计本程序采用VS2010编写，开始创建了一个工程，本程序的文件有：头文件：define.h 用以定义全局变量 function.h 用以声明函数源文件：function.cpp 用以定义函数 main.cpp 主函数下面罗列每个文件主要代码define.h#ifndef DEFINE_H#

4、define DEFINE_H#includeusing namespace std;#includestruct linklistmultinomial float a; int e; struct linklistmultinomial *next;typedef struct linklistmultinomial *linklist,node; #endiffunction.h#ifndef FUNCTION_H#define FUNCTION_H#includedefine.hvoid welcome();void goodbye();linklist createlinklist(

5、linklist head,int n);void insert(linklist p,linklist head);void printlinklist(linklist head);void addlinklist(linklist pa,linklist pb);void sublinklist(linklist pa,linklist pb);void dlinklist(linklist pa);void calclinklista(linklist pd,int x);void menu();#endiffunction.cpp#includedefine.h/欢迎界面void w

6、elcome() coutnnnnn; cout *nnendl; cout 一元稀疏多项式计算器 nnendl; cout 制作者：王雨辰 学号：4100113 nnendl; cout *nnnnnnn; cout 请输入请求 nnendl; cout 1.进入计算器 0.退出 nnendl;/结束界面void goodbye() system(cls); coutnnnnnendl; cout *nnendl; cout 谢谢使用，再见 nnendl; couta=0) free(p); else linklist p1,p2; p1=head; p2=p1-next; while(p2

7、&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; /创建链表linklist createlinklist(linklist head,int n) linklist p; int i; p=head=(linklist)malloc(sizeof(node); head-next=NULL; for(i=1;i=n;i+) p=(linklist)malloc(sizeof(nod

8、e); cout请输入第i项系数p-a; cout请输入第i项指数p-e; insert(p,head); return head;/输出函数void printlinklist(linklist head)s linklist p=head-next; if(!p) couta=1) if(p-e=0) cout1; else coutxe; else if(p-a=0); else if(p-ae=0) couta; else coutaxe; else if(p-e=0) couta; else coutaxe; p=p-next; while(p) if(p-a=1) if(p-e=0

9、) cout+1; else cout+xe; else if(p-a=-1) if(p-e=0) cout-1; else cout-xe; else if(p-a=0); else if(p-ae=0) couta; else coutaxe; else if(p-e=0) cout+a; else cout+axe; p=p-next; coutnext; 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

10、;p-e=p2-e;p2=p2-next; else if(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; else if(p1-ep2-e) p-a=p1-a;p-e=p1-e;p1=p1-next; else if(p1-ee) p-a=p2-a;p-e=p2-e;p2=p2-next; if(p-a=0) free(p); else p3=p; p3-next=NULL; printlinklist(pc);/a-bvoid su

11、blinklist(linklist pa,linklist pb) linklist pc; linklist p1,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; else if(p2=NULL) p-a=p1-a;p-e=p1-e;p1=p1-ne

12、xt; else if(p1-e=p2-e) p-a=p1-a-p2-a;p-e=p1-e;p1=p1-next;p2=p2-next; else if(p1-ep2-e) p-a=p1-a;p-e=p1-e;p1=p1-next; else if(p1-ee) p-a=-p2-a;p-e=p2-e;p2=p2-next; if(p-a=0) free(p); else p3=p; p3-next=NULL; if(pc-next-next=NULL&pc-next-a=0) /若a-b=0，输出0 cout0next; p4=pd=(linklist)malloc(sizeof(node);

13、 while(p1!=NULL) p4-next=(linklist)malloc(sizeof(node); p4=p4-next; if(p1-e=0) p4-a=0;p4-e=0; else if(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处的值void calclinklista(linklist pe,int x) int sum=0,t,i; linklist p5; for(p5=pe-next;p5;

14、p5=p5-next) t=1; for(i=p5-e;i!=0;) if(ia*t; coutsumendl;/菜单void menu() int m,n,q=1,x; linklist pa=0,pb=0; cout请输入多项式a的项数m; pa=createlinklist(pa,m); cout请输入多项式b的项数n; pb=createlinklist(pb,n); cout *nnendl; cout 功能表 nn endl; cout 1.输出多项式a 2.输出多项式b endl; cout 3.输出a+b 4.输出a-b endl; cout 5.输出a的导数 6.计算多项式a

15、在x处的值 endl; cout 7.计算多项式b在x处的值 0.返回主菜单 nnendl; cout *nnnnnnn; while(q!=0) cout请输入命令q; switch(q) case 1:printlinklist(pa);break; case 2:printlinklist(pb);break; case 3:addlinklist(pa,pb);break; case 4:sublinklist(pa,pb);break; case 5:dlinklist(pa);break; case 6:cout输入xx;calclinklista(pa,x);break; cas

16、e 7:cout输入xx;calclinklista(pb,x);break; case 0:q=0;break; default:cout输入错误，请重新输入endl; 三、调试分析在这个程序写完后的调试过程中，出现了以下问题：1、printlinklist函数刚开是测试会出现首项系数为正，带加号的情况，加了个选择后解决此问题。2、addlinklist，sublinklist函数当做完后结果为0的情况出现不显示的情况，原因是没有及时释放节点，于是加上了free(p)。3、calclinklista要分清指数是正是负。通过本次课程设计我更加了解了单链表是怎样应用的，并学会将数据插入链表，删除链表中的数据等等四、用户手册开始界面然后根据提示输入多项式然后根据功能表来选择五、测试结果(2x+5x8-3.1x11)+(7-5x8+11x9)=(-3.1x11+11x9+2x+7)(1+x+x2+x3+x4+x5)+(-x3-x4)=(1+x+x2+x5)(x+x100)+(x100+x200)=(x+2x100+x200)(x+x2+x3)+0=x+x2+x3以上结果经过测试运行皆正确