一元稀疏多项式计算器实习报告[1].doc

。实习报告题目：设计一个一元稀疏多项式计算器班级: 姓名 学号_完成日期：_一、课程题目 一元稀疏多项式计算器二、 需求分析1、一元稀疏多项式简单计算器的功能是：1.1 输入并建立多项式；1.2 输出多项式，输出形式为整数序列：n，c1,e1,c2,e2,cn,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列； 1.3 求多项式a、b的导函数；1.4 计算多项式在x处的值；1.5多项式a和b相加，建立多项式a+b；1.6 多项式a和b相减，建立多项式a-b。2、设计思路:2.1 定义线性表的动态分配顺序存储结构；2.2 建立多项式存储结构，定义指针*next2.3利用链表实现队列的构造。每次输入一项的系数和指数，可以输出构造的一元多项式3、测试数据：（1）、(2x+5x8-3.1x11)+(7-5x8+11x9)=(-3.1x11+11x9+2x+7);（2）、(6x-3-x+4.4x2-1.2x9+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;（5）、(x+x100)+(x100+x200)=(x+2x100+x200);（6）、(x+x2+x3)+0=x+x2+x3.三、概要设计1. 有序表的抽象数据类型定义为：ADT List数据对象：D=ai| aiR,i=1,2,n,n0数据关系：R1=| ai-1,aiD, ai-1,ai, i=1,2,3,.n基本操作：InitList()操作结果：构造一个空的有序表L。DestroyList(L)初始条件：有序表L已存在。操作结果：销毁有序表L。ListLength(L)初始条件：有序表L已存在。操作结果：返回有序表L的长度。ClearList( L ) 初始条件：有序表L已存在。操作结果：清空链表内容。Ins_before ( N,N ) 初始条件：有序表L已存在。操作结果：插入节点到链表。 ADT OrderedList2.多项式的抽象数据类型定义为：ADT Poly 数据对象：D=ai |ai为实数，i=1，2，n 数据关系：R1= 基本操作：CreatePoly( L,N )初始条件：N为节点，L为有序表。操作结果：将N 插入多项式的适当位置。GetPoly( L )操作结果：将用户输入转换为节点。PrintPoly( L )初始条件：多项式L已存在。操作结果：显示多项式。AddPoly( L_1,L_2,L_add )初始条件：多项式L_1,L_2,L_add已存在。操作结果：生成L_1,L_2之和的多项式L_addDiffPoly( L ,L_diff) 初始条件：多项式L ,L_diff已存在。操作结果：生成L的导数多项式L_add。AlterPoly( L )初始条件：多项式L已存在。操作结果：将L多项式取相反数。ADT Poly、三、 详细设计1、Constant.h#ifndef _constant_#define _constant_#include#include#define TURE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;#endif2、Polynt.h#includeconstant.htypedef struct elemTypefloat coef;/系数int expn;/指数ElemType;typedef struct nodeElemType data; /指向结点元素的值struct node *next; /后继Node,*Polyn; /结点类型，指针类型typedef structNode *head;Node *tail;List;Status MakeNode(Polyn &p,ElemType e); /分配由p指向的数据元素为e、后继为“空”的结点Status InitList(List &L); /构造链表Status DestroyList(List &L); /销毁线性表void Insert(List &L,Polyn s); /将s指向的结点插入L的最后一个结点void Insbefore(Polyn p,Polyn q);Status CreatPolyn(List &polynomial,int m); /创建一个一元多项式polynomial，并输入m项的指数和系数void PrintPolyn(List L); /打印输出一元多项式void AlterPoly(List L); /减法void AddPolyn(List L1,List L2,List &L3); /多项式加法3、Polyn.cpp#includePolynt.hStatus MakeNode(Polyn &p,ElemType e)/分配由p指向的数据元素为e、后继为“空”的结点p=(Polyn)malloc(sizeof(Node);p-data.coef=e.coef;p-data.expn=e.expn;p-next=NULL;return OK;Status InitList(List &L)/初始化链表ElemType e;Polyn p;e.coef = ;e.expn = ;MakeNode(p,e);L.head = p;L.tail=p;return OK;Status DestroyList(List &L)/销毁链表Polyn p,q;if(L.head=L.tail) free(L.head);L.head=L.tail=NULL;return OK;p=L.head-next;while(!p)q=p-next;free(p);p=q;L.head=L.tail=NULL;return OK;void Insert(List &L,Polyn s)if(L.head-next =NULL)L.head-next =s;s-next =NULL;L.tail = s;elseif(L.head-next!=NULL & s-data.expnL.head-next-data.expn)s-next=L.head-next;L.head-next=s; return;if(L.tail-data.expns-data.expn)L.tail-next=s; L.tail=s;return;for (Polyn p = L.head-next; p!=NULL;p = p-next )if (s-data.expn= p-data.expn)p-data.coef+=s-data.coef;free(s);return;else if ( p-data.expns-data.expn & p-next-data.expndata.expn)s-next=p-next;p-next=s;return;Status CreatPolyn(List &polynomial,int m)/创建一个一元多项式polynomial，并输入m项的指数和系数ElemType e;Polyn p;for(int i=0;inext;while(p!=NULL)if(p=L.head-next)if(p-data.coef0) if(p-data.expn!=0) printf(%gx%d,p-data.coef,p-data.expn); elseprintf(%g,p-data.coef); else if(p-data.coefdata.expn!=0) printf(%gx%d,p-data.coef,p-data.expn); elseprintf(%g,p-data.coef); else printf( );p=p-next;else if(p!=L.head-next & p!=NULL)if(p-data.coef0) if(p-data.expn!=0) printf(+%gx%d,p-data.coef,p-data.expn); elseprintf(+%g,p-data.coef); else if(p-data.coefdata.expn!=0) printf(%gx%d,p-data.coef,p-data.expn); elseprintf(%g,p-data.coef); else printf( );p=p-next;elsereturn;void AlterPoly(List L)for(Polyn p=L.head-next;p!=NULL;p=p-next)p-data.coef*=-1;void AddPolyn(List L1,List L2,List &L3)Polyn p1,p2,p3;p1=L1.head-next;p2=L2.head-next;while(p1!=NULL & p2!=NULL)if(p1-data.expnp2-data.expn)MakeNode(p3,p1-data);Insert(L3,p3);p1=p1-next;else if(p1-data.expndata.expn)MakeNode(p3,p2-data);Insert(L3,p3);p2=p2-next;else if(p1-data.expn=p2-data.expn)MakeNode(p3,p2-data);p3-data.coef=p1-data.coef+p2-data.coef;p3-data.expn=p1-data.expn; Insert(L3,p3);p1=p1-next;p2=p2-next;if(p1=NULL & p2!=NULL)while(p2!=NULL)MakeNode(p3,p2-data);Insert(L3,p3);p2=p2-next;else if(p2=NULL & p1!=NULL)while(p1!=NULL)MakeNode(p3,p1-data);Insert(L3,p3);p1=p1-next;4、main.cpp#includePolynt.h#include#includevoid main()system(cls);printf(*n);printf( 欢迎使用一元稀疏多项式计算 n);printf(*n);printf(1、创建多项式A 2、创建多项式B 3、相加 4、相减 5、退出n);List polynomialA,polynomialB,polynomialC;InitList(polynomialA); InitList(polynomialB); InitList(polynomialC);char poly;int m;int n=1;for(;)printf(请输入指令:);poly=getchar();switch(poly)case1: /创建多项式Aprintf(请输入多项式A的项数：);scanf(%d,&m);printf(n请 输 入 多 项 式 A：);CreatPolyn(polynomialA,m);printf(n多项式A是：);PrintPolyn(polynomialA);printf(n);break; case2: /创建多项式Bprintf(请输入多项式B的项数：);scanf(%d,&m);printf(n请 输 入 多 项 式 B：);CreatPolyn(polynomialB,m);printf(n多项式B是：);PrintPolyn(polynomialB);printf(n);break;case3: /加法printf(结果是:);AddPolyn(polynomialA,polynomialB,polynomialC);PrintPolyn(polynomialC);printf(n);break;case4: /减法printf(结果是:);AlterPoly(polynomialB);DestroyList(polynomialC);InitList(polynomial