数据结构-多项式-实验报告(共8页)

1、北京邮电大学信息与通信工程学院数据结构实验报告实验名称： 实验一多项式的实现学生姓名： 班 级： 班内序号： 学 号： 日 期： 2011年10月29日1实验要求实验目的：1.熟悉C+语言的基本编程方法，掌握集成编译环境的调试方法2.学习指针、模板类、异常处理的使用3.掌握线性表的操作的实现方法4.学习使用线性表解决实际问题的能力实验内容： 利用线性表实现一个一元多项式Polynomialf(x) = a0 + a1x + a2x2 + a3x3 + + anxn 要求：1 能够实现一元多项式的输入和输出2 能够进行一元多项式相加3 能够进行一元多项式相减4 能够计算一元多项式在x处的值5 能

2、够计算一元多项式的导数（选作）6 能够进行一元多项式相乘（选作）7 编写测试main()函数测试线性表的正确性2. 程序分析由于多项式是线性结构，故选择线性表来实现，在这个程序中我采用的是单链表结构，每个结点代表一个项，多项式的每一项可以用其系数和指数唯一的表示。如果采用顺序存储，那么对于结点的插入和删除的操作会比较麻烦，而且顺序表的结点个数固定，对于可能发生的情况无法很好的处理，而采用链表就会简单许多，还能自由控制链表的长度。两个多项式要进行多次的计算，为了保护原始的数据，方便进行以后的计算，故选择把结果存储在一个新建的链表里。本程序完成的主要功能：1. 输入和输出：需要输入的信息有多项式的

3、项数，用来向系统动态申请内存；多项式各项的系数和指数，用来构造每个结点，形成链表。输出即是将多项式的内容向屏幕输出。2. 多项式相加与相减：多项式的加减要指数相同即是同类项才能实现，所以在运算时要注意判断指数出现的各种不同的情况，分别写出计算方法。将每项运算得到的结果都插入到新的链表中，形成结果多项式。3. 多项式的求导运算：多项式的求导根据数学知识，就是将每项的系数乘以指数，将指数减1即可，将每项得到的结果插入到结果多项式的链表中。4. 多项式在某点的值：由用户输入x的值，然后求出每项的值相加即可。 2.1 存储结构本程序采用的存储结构是单链表结构，其定义的结点包括三部分：系数、指数以及下一

4、个结点的地址。示意图如下：coef1 expn1 nextcoef1 expn1 nextcoef1 expn1 next next 2.2 关键算法分析1. 输入多项式·自然语言描述：1. 设置多项式的项数n；2. 按照多项式的项数申请动态数组coef和expn存储多项式的系数和指数；3. 按照指数递增的次序输入各项的系数以及指数，分别存入coef和expn；4. 再将输入的系数以及指数赋给每一个结点的coef和expn域； 5. 利用头插法将每个结点加入链表。·伪代码：1. 输入项数n；2. float* coef1=new floatn1;int* expn1=new

5、 intn1;3. 运用for循环，循环n次3.1 term* s=new term; 3.2 s->coef=coefi;3.3 s->expn=expni; 3.4 r->next=s; 3.5 r=s; 4. 运用头插法将结点插入链表。时间复杂度：空间复杂度：2. 输出多项式·自然语言描述：1. 获取头结点；2. 循环n-1次（n为多项式的项数）2.1将指针的指向后移；2.2依照多项式的各种情况，设置输出方式 2.2.1 系数为1且指数不为1和0，输出xexpn+； 2.2.2 系数不为0且指数为0，输出（coef）+； 2.2.3 系数不为0且指数为1，输出

6、（coef）x+； 2.2.4 系数不为0和1，指数不为0和1，输出(coef)x(expn)+； 3.将指针指向移到最后一个节点。重复2.2中判断，但不输出+号。·伪代码描述：1. term* m=front;2. for(int i=0;i<n-1;i+)2.1 m=m->next;2.2 if(m->coef=1&&(m->expn!=1&&m->expn!=0)cout<<"x"<<m->expn<<"+"2.3 else if(m-

7、>coef=1&&m->expn=0)cout<<m->coef<<"+"2.4 else if(m->coef!=1&&m->expn=0)cout<<m->coef<<"+"2.5 else if(m->coef!=0&&m->expn=1)cout<<m->coef<<"x"<<"+"2.6 else if(m->coe

8、f=1&&m->expn=1)cout<<"x"<<"+"2.7 else if(m->coef=0)cout<<""<<"+"2.8 elsecout<<m->coef<<"x"<<m->expn<<"+"3. m=m->next;3.1 if(m->coef=1&&(m->expn!=1&&

9、;m->expn!=0)cout<<"x"<<m->expn<<""3.2 else if(m->coef=1&&m->expn=0)cout<<m->coef;3.3 else if(m->coef!=1&&m->expn=0)cout<<m->coef;3.4 else if(m->coef!=1&&m->expn=1)cout<<m->coef<<&qu

10、ot;x"<<""3.5 else if(m->coef=1&&m->expn=1)cout<<"x"3.6 else if(m->coef=0)cout<<""3.7 elsecout<<m->coef<<"x"<<m->expn<<""时间复杂度：O(n)空间复杂度：S(1)3. 多项式的相加相减·自然语言描述：1. 指针p和q分别指向a和b两

11、个多项式的头结点的下一个节点；2. 将结果多项式的项数置为0；3. 只有p或q非空，进行以下循环：3.1 申请一个term* 型的指针d，将其next域赋为NULL；进行判断：3.3.1 如果p和q均非空3.3.3.1 如果p和q的指数相等将d的系数赋为p、q系数之和，指数不变，将p、q指向后移；3.3.3.2 如果p->expn>q->expn复制q到结果多项式（减法系数为q->coef的相反数）3.3.3.3 如果p->expn<q->expn复制p到结果多项式3.3.3.4 判断后将项数+，插入新节点d；3.3.2 如果q为空，p仍存在，逐项将p

12、复制到结果多项式。每进行一次，项数+，p后移。3.3.3 如果p为空，q仍存在，逐项将q复制到结果多项式（减法将系数变为原来的相反数）。每进行一次，项数+，q后移。3.2 返回结果多项式的项数 ·伪代码描述：1. 工作指针p、q初始化：term* p=front->next;term* q=b.front->next; 2. int nAdd=0;/加法 int nMinus=0;/减法 3. while(p|q) 3.1 term* d=new term;d->next=NULL; 3.3.1 if(p&&q) 3.3.3.1 if(p->e

13、xpn=q->expn) d->coef=p->coef+q->coef;d->expn=p->expn;p=p->next;q=q->next;/加法 d->coef=p->coef-q->coef;d->expn=p->expn;p=p->next;q=q->next;/减法 3.3.3.2 p->expn>q->expn d->coef=q->coef;d->expn=q->expn;q=q->next;/加法d->coef=-q->coe

14、f;d->expn=q->expn;q=q->next;/减法 3.3.3.3p->expn<q->expnd->coef=p->coef;d->expn=p->expn;p=p->next;/加法d->coef=p->coef;d->expn=p->expn;p=p->next;/减法 3.3.3.4 nAdd+;add.Insert(d);/加法 nMinus+;min.Insert(d);/减法 3.3.2 while(p)term* d=new term;d->coef=p->c

15、oef; d->expn=p->expn;d->next=NULL;nAdd+; add.Insert(d);p=p->next;/加法term* d=new term;d->coef=(p->coef); d->expn=p->expn;d->next=NULL; nMinus+;min.Insert(d);p=p->next;/减法 3.3.3 while(q) term* d=new term;d->coef=q->coef; d->expn=q->expn;d->next=NULL; nAdd+;

16、add.Insert(d);q=q->next;/加法term* d=new term;d->coef=0-(q->coef); d->expn=q->expn;d->next=NULL; nMinus+;min.Insert(d);q=q->next;/减法3.2 return nAdd; return nMinus;时间复杂度：O(n)空间复杂度：O(2)4. 求值·自然语言描述：1. 将工作指针指向多项式的第一项；2. 将结果result置为0；3. 指针不为空，即进行循环：3.1 result+=s->coef*(pow(x,s

17、->expn); 3.2 s=s->next; 4返回result；· 伪代码描述：1. term* s=front->next;2. float result=0;3. while(s)3.1 result+=s->coef*(pow(x,s->expn); 3.2 s=s->next; 4. return result;时间复杂度：O(n)空间复杂度：S(1)5. 求导数·自然语言描述：1. 将指针指到多项式的第一项的结点：term* p=a.front->next;2. 循环n次2.1 每项求导的系数为：p->coef*

18、p->expn;指数为：p->expn-1;2.2 将新结点插入新链表；2.3 指针p后移。 ·伪代码描述： 1. term* p=a.front->next; 2. for(int i=0;i<n;i+) 2.1 term* s=new term; 2.2 if(p->expn) 2.2.1 s->coef=(p->coef)*(p->expn); 2.2.2 s->expn=p->expn-1; 2.2.3p=p->next; 2.2.4 de.Insert(s); 2.3 else 2.3.1 s->coef=0;2.3.2 s->expn=0;2.3.3 p=p->next;2.3.4 de.Insert(s);时间复杂度：O(n)空间复杂度：S(1)3. 程序运行结果1. 测试主函数流程：1开始进行A-B的运算设置多项式A的项数按照A的项数动态申请coef1和expn1输出相减的结果minus进行对A求导数的运算输出A设置多项式B的项数输出求导的结果de按照B的项数动态申请coef2和expn2输入x的取值计算A在x处的取值并输出输出B结束进行A+B的运算输出相加的结果add1测试条件：问题规模n的数量级为