一元稀疏多项式计算器实现完整实现详细源码

1、1.5一元稀疏多项式计算器实习报告一、 需求分析 1输入并建立多项式；2输出多项式，输出形式为整数序列：n，c1，e1，c2，e2，cn，en，其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列；3多项式a和b相加，建立多项式ab；4多项式a和b相减，建立多项式ab；5多项式a和b相乘，建立多项式a×b；6计算多项式在x处的值；7求多项式P的导函数P'；8.多项式的输出形式为类数学表达式；9.做出计算器的仿真界面；10. 测试数据：（1） (2x+5x8-3.1x11)+(7-5x8+11x9)=(-3.1x11+11x9+2x+7)（2） (6x-

2、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（7）互换上述测试数据中的前后两个多项式二、 概要设计1. 链表的抽象数据类型定义为：ADT LinkList 数据对象：D ai | aiElemSet, i=1,2,.,n, n0 数据关系：R1 <ai

3、-1, ai>|ai-1, aiD, i=2,.,n 基本操作： InitList(&L) 操作结果：构造一个空的线性表L。 DestroyList(&L) 初始条件：线性表L已存在。 操作结果：销毁线性表L。ClearList(*L) 初始条件：线性表L已存在。 操作结果：将线性表L重置为空表。 LocateElem(L, e, cmp() 初始条件：线性表L已存在，compare()是元素判定函数。 操作结果：返回L中第1个与e满足关系cmp()的元素的位序。 若这样的元素不存在，则返回值为0。 SetCurElem(&p, e) 初始条件：线性表L已存在，且

4、非空。操作结果：用元数e更新p所指结点中元数的值。GetCurElem(p)初始条件：线性表L已存在，且非空。操作结果：返回p所指结点中数据元数的值。InsFirst (&L, h, s) 初始条件：线性表L已存在，h结点在L中。 操作结果：在L的s所指结点插入在h结点之后，L的长度加1。 DelFirst (&L, h, q) 初始条件：线性表L已存在且非空，q结点在L中且不是尾结点 操作结果：删除链表L中的h结点之后的结点q，L的长度减1。 MakeNode(&p, e)操作结果：创建了一个结点p，其data部分为e。FreeNode(&p)初始条件：结点p

5、存在且非空。操作结果：释放结点p空间。Append(LinkList &L,Link s)初始条件：线性表L已存在。操作结果：s及s以后的结点链接到了原L之后，L的长度增加链上的结点数。ListEmpty(L)初始条件：线性表L已存在。操作结果：若线性链表L为空表，则返回TRUE,否则返回FALSE。GetHead(L)初始条件：线性表L已存在。操作结果：返回线性链表L中头结点的位置。NextPos(L, p)初始条件：线性表L已存在。操作结果：返回p所指结点的直接后继的位置，若没后继，则返回NULL。int cmp(a, b)初始条件：存在两个元数。操作结果：比较a，b的数值，分别返

6、回-1，0，1。 ADT LinkList2.一元多项式的抽象数据类型定义为：ADT Polynomial数据对象：D ai | aiTermSet, i=1,2,.,m, m0 TermSet中的每个元素包含一个表示系数的实数和表示指数的整数数据关系：R1 <ai-1, ai>|ai-1, aiD, 且ai-1中的指数值<ai中的指数值，i=2，n基本操作：CreatPolyn（&P，m）操作结果：输入m项的系数和指数，建立一元多项式P。DestroyPolyn（&P）初始条件：一元多项式P已存在。操作结果：销毁一元多项式P。AddPolyn（&Pa

7、，&Pb）初始条件：一元多项式Pa和Pb已存在。操作结果：完成多项式相加运算，即：Pa=Pa+Pb，并销毁一元多项式Pb。SubtractPolyn(&Pa,&Pb)初始条件：一元多项式Pa和Pb已存在。操作结果：完成多项式相减运算，即：Pa=Pa-Pb，并销毁一元多项式Pb。MultiplyPolyn(&Pa,&Pb)初始条件：一元多项式Pa和Pb已存在。操作结果：完成多项式相乘运算，即：Pa=Pa×Pb，并销毁一元多项式Pb。DerivPolyn(&Pa)初始条件：一元多项式Pa已存在。操作结果：多项式求导。CalPolyn(Pa

8、, x)初始条件：一元多项式Pa已存在。操作结果：求多项式在x处的值。PrintPolyn(p, m) 初始条件：一元多项式p已存在，且已知多项式项数。 操作结果：打印输出一元多项式p的项数、系数和指数。Expression(p, m)初始条件：一元多项式p已存在，且已知多项式项数。 操作结果：打印输出一元多项式的类数学表达式。SortPolyn(&p)初始条件：一元多项式p已存在。 操作结果：对多项式p进行排序ADT Polynomial3.本程序包含4个模块：(1)主程序模块：int main() 初始化； 接受命令； while（命令！=推出） 处理命令； 接受命令；return

9、 0;(2)一元多项式单元模块实现一元多项式的抽象数据类型；（3）链表单元模块实现链表的抽象数据类型；(4)结点结构单元模块定义链表的节点结构。各模块之间的调用关系如下：主程序模块 一元多项式单元模块 链表单元模块结点结构单元模块三、 详细设计1.设计好的数据类型：typedef struct /项的表示，多项式的项作为Linklist的数据元素float coef; /系数int expn;/指数 term, ElemType;/两个类名：term用于本ADT，ElemType为Linklist的数据对象名typedef struct LNode /结点类型 ElemType data; s

10、truct LNode *next; *Link, *Position;typedef struct/链表类型Link head,tail;/分别指向线性链表中的头结点和最后一个结点 int len;/指示线性链表中数据个数 LinkList;typedef LinkList polynomial;/基于带头结点的线性链表定义的多项式数据类型2.基于链表、结点的操作(部分伪码如下)/ 分配由p指向值为e的结点,并返回OK,若分配失败,则返回ERROR。Status MakeNode(Link &p, ElemType e);/释放p所指结点void FreeNode(Link &

11、;p);/构造一个空的线性链表LStatus InitList(LinkList &L); L.head=L.tail=(Link)malloc(sizeof(LNode); L.len=0; L.head->next=L.tail->next=NULL; return OK;/ 返回线性表L中头结点的位置。Position GetHead(LinkList &L);/已知p指向线性链表L中的一个结点，返回p所指结点的直接后驱的位置/若无后继，返回NULLPosition Nextpos(LinkList &L,Link p);/已知p指向线性表L中的一个结

12、点,返回p所指结点中数据元素的值。ElemType GetCurElem(Link p);/已知p指向线性链表L中的一个结点,用e更新p所指结点中数据元素的值。Status SetCurElem(Link &p,float e); /已知h指向线性链表的某个结点,将q所指的结点插入在h之后。Status InsFirst(Link h,Link q); s->next=h->next; h->next=s; L.len+; if(!s->next) L.tail=s; return OK;/已知h指向线性链表的头结点,删除线性链表第一个指结点并以q返回Statu

13、s DelFirst(Link h,Link &q);/若线性链表L为空,则返回TRUE,否则返回FALSE。Status ListEmpty(LinkList L); if(L.head=L.tail=NULL) return TRUE; else return FALSE;/将指针s所指的一连串结点连接在线性表L的最后一个结点之后,并改变链表L的尾指针指向新的尾结点。Status Append(polynomial &L,Link s); i=0; q=s; while(s) /找到新的tail，计数s长度 p=s; s=s->next; i+; L.tail->

14、;next=q; L.tail=p; L.len+=i; return OK;/判断已知链表中，是否存在相同的元素e，若存在返回TURE，且q指示L中第一个与e相同的结点元素；/否则返回FALSE,并q指示L中第一个稍大于e的元素的直接前驱的位置Status LocateElem(LinkList L,ElemType e,Position &q); p=L.head; while(p->next) s=p; p=p->next; m=p->data; if(cmp(e,m )=0) q=p; return TRUE; q=p; return FALSE;/整表删除v

15、oid ClearList(LinkList &L); if(L.head!=L.tail) p=q=L.head->next; L.head->next=NULL; while(p!=L.tail) p=q->next; free(q); q=p; free(q); L.tail=L.head; L.len=0; return OK;/依a的指数值<（或=）(或>）b的指数数值，分别返回-1，0，+1int cmp(term a, term b) ; if(a.expn<b.expn) return -1; if(a.expn=b.expn) re

16、turn 0; if(a.expn>b.expn) return 1;3.基于多项式的操作（部分伪码如下）/输入m项的系数和指数，建立表示一元多项式的有序链表Pvoid CreatPolyn(polynomial &p,int m);InitList(p);h=GetHead(p);e.coef=0.0;e.expn=-1;SetCurElem(h,e);for(int i=1;i<=m;i+) cout<<"请输入第"<<i<<"项的系数和指数（按指数降序）：" cin>>e.coef

17、>>e.expn; cout<<endl; if(!LocateElem(p,e,q)/当前链表中不存在该指数项 if(MakeNode(s,e) InsFirst(p,q,s);/生成节点并插入链表 else return; else q->data.coef+=e.coef; +c; m=m-c;/销毁一元多项式Pvoid DestroyPolyn(polynomial &p); while(p.head ->next!=NULL) k=p.head; p.head =p.head ->next; free(k); free(&p)

18、;/打印输出一元多项式Pvoid PrintPolyn(polynomial p);ha=GetHead(p);cout<<m<<', ' for(int i=1;i<=m;i+) qa=NextPos(p,ha); e=GetCurElem(qa); cout<<e.coef<<','<<e.expn<<', ' ha=qa; cout<<endl;/打印输出一元多项式的类数学表达式void Expression(polynomial p,int m);/

19、完成多项式的相加运算，即：Pa=Pa+Pb，并销毁一元多项式Pbvoid AddPolyn(polynomial &Pa ,polynomial &Pb); ha = GetHead(Pa);hb = GetHead(Pb);/ha和hb分别指向pa和pb的头节点qa = NextPos(Pa, ha);qb = NextPos(Pb, hb);while (qa&&qb) /qa，qb均非空a = GetCurElem(qa);b = GetCurElem(qb);switch (cmp(a, b)/a和b为两表比较元数case -1: /a的指数小于b的指数

20、DelFirst(Pb, hb, qb);InsFirst(Pa, ha, qb);qb = NextPos(Pb, hb);ha = NextPos(Pa, ha);break;case 0: /a的指数等于b的指数a.coef = a.coef + b.coef;if (a.coef != 0.0) /修改多项式Pa中当前结点的系数SetCurElem(qa, a);ha = qa;else /删除多项式Pa中当前结点DelFirst(Pa, ha, qa);FreeNode(qa);DelFirst(Pb, hb, qb);FreeNode(qb);qb=NextPos(Pb,hb);q

21、a=NextPos(Pa,ha);break;case 1: /a的指数大于b的指数ha = qa;qa = NextPos(Pa, qa);break;if (!ListEmpty(Pb) Append(Pa, qb);/链接Pb中剩余结点FreeNode(hb);/释放Pb的结点/完成多项式的相减运算，即：Pa=Pa-Pb，并销毁一元多项式Pbvoid SubtractPolyn(polynomial &Pa ,polynomial &Pb);/完成多项式的相减运算，即：Pa=Pa×Pb，并销毁一元多项式Pbvoid MultiplyPolyn(polynomia

22、l &Pa ,polynomial &Pb); InitList(Pc); qa=GetHead(Pa); qa=qa->next; hc=GetHead(Pc); while(qa) a=GetCurElem(qa); qb=GetHead(Pb); qb=qb->next; while(qb) b=GetCurElem(qb); c.coef=a.coef*b.coef; c.expn=a.expn+b.expn; MakeNode(qc,c); InsFirst(Pc,hc,qc); hc=NextPos(Pc,hc); qc=NextPos(Pc,qc);

23、qb=qb->next; qa=qa->next; DestroyPolyn(Pb); ClearList(Pa); Pa.head=Pc.head; Pa.tail=Pc.tail; Pa.len=Pc.len;/计算多项式在x处的值double Evaluation(double x, polynomial p);/计算多项式P的导函数P'void Derivative( polynomial &p ); InitList(Pb); qa=GetHead(Pa); qa=qa->next; hb=GetHead(Pb); while(qa) a=GetCu

24、rElem(qa); b.coef=a.coef*a.expn; b.expn=a.expn-1; MakeNode(qb,b); InsFirst(Pb,hb,qb); hb=NextPos(Pb,hb); qb=NextPos(Pb,qb); qa=qa->next; qb=NULL; ClearList(Pa); Pa.head=Pb.head; Pa.tail=Pb.tail; Pa.len=Pb.len;4.主函数和其他函数的伪码算法int main() Initialization();ReadCommand(cmd);while (cmd != 'q' &a

25、mp;& cmd != 'Q')Interpret(cmd);display();ReadCommand(cmd); return 0;void Initialization()pre_cmd = ' 'cmd = ' 'InitList(La);InitList(Lb);void display()system("cls"); /清屏在屏幕上方显示操作命令清单：CreatePolynomial_a ->1 CreatePolynomial_b ->2 a+b ->' a-b >'

26、;' a*b ->* Derivation of a ->d Calculate a in x ->c Quit ->q 在屏幕下方显示操作命令提示框：Enter a operation code(1,2,+,_,*,c,d OR q): "void ReadCommand(char &cmd)/读入操作命令符 显示检入操作命令符的提示信息；dodisplay();cin >> cmd; while (!strchr(cmdsets, cmd);void Interpret(char cmd) /解释执行操作命令cmdswitch

27、(cmd)case '1':ClearList(La);cout << "请输入第一个一元多项式的项数"cin >> n; cout << endl;CreatPolyn(La, n);/输入多项式SortPolyn(La);break;case '2':ClearList(Lb);cout << endl << "请输入第二个一元多项式的项数"cin >> m; cout << endl;CreatPolyn(Lb, m);/输入多项式S

28、ortPolyn(Lb);break;case '+':cout << endl << "两多项式相加的结果："AddPolyn(La, Lb);PrintPolyn(La, La.len);Expression(La,La.len);getchar();getchar();break;case '-':cout << endl << "两多项式相减的结果："SubtractPolyn(La, Lb);PrintPolyn(La, La.len);Expression(La,

29、La.len);getchar();getchar();break;case '*':cout << endl << "两多项式相乘的结果："MultiplyPolyn(La, Lb);PrintPolyn(La, La.len);Expression(La,La.len);getchar();getchar();break;case 'c':case 'C':cout << "请输入x的值" << endl;cin >> x;cout <&

30、lt; "多项式a在" << x << "处的值为" << CalPolyn(La, x);getchar();getchar();break;case 'd':case 'D':DerivPolyn(La);cout << "求导结果为"PrintPolyn(La, La.len);Expression(La,La.len);getchar();getchar();default:cout << "输入错误" << endl; 5.函数的调用关系图反映了演示程序的层次结构四、 调试分析1. 一开始写求导部分代码时没有