数据结构_多项式_实验报告北邮

《数据结构_多项式_实验报告北邮》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构实验报告实验名称：实验多项式的实现学生姓名：班级：班内序号：学FI1.号：期：2012年1108H实验要求实验目的：1.熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法2.学习指针、模板类、异常处理的使用3.掌握线性表的操作的实现方法4.学习使用线性表解决实际问题的能力实验内容：利用线性表实现一个一元多项式Polynomialf（x）=a（）+aX++a^x+・・・+aftxn要求：1.能够实现一元多项式的输入和输出2.能够进行一元多项式相加3.能够进行一元多项式相减4.能够计算一元多项式在x

2、处的值5.能够计算一元多项式的导数（选作）6.能够进行一元多项式相乘（选作）7.编写测试main（）

3、^

4、数测试线性表的正确性程序分析山于多项式是线性结构，故选择线性表來实现，在这个程序中我采用的是单链表结构，每个结点代表一个项，多项式的每一项可以用其系数和指数唯一的表示。如果采川顺序存储,那么对于结点的插入和删除的操作会比较麻烦，而且顺序表的结点个数固定，对于可能发生的情况无法很好的处理，而采用链表就会简单许多，还能自由控制链表的氏度，求和或者求差操作结束后，两个链表将合并在一起，。本程序完成的主要功能：1.

5、输入和输出：需要输入的信息有多项式的项数，川來向系统动态申请内存；多项式各项的系数和指数，用来构造每个结点，形成链表。输出即是将多项式的内容向屏幕输出。1.多项式相加与相减：多项式的加减要指数相同即是同类项才能实现，所以在运算时要注意判断指数出现的各种不同的情况，分別写出计算方法。并将B表按具体情况合并到A表中，形成结果多项式。2.多项式的求导运算：多项式的求导根据数学知识，就是将每项的系数乘以指数，将指数减1即可，将每项得到的结果插入到结果多项式的链表中。3.多项式在某点的值：由用户输入x的值，然后求出每项的

6、值相加即可。2.1存储结构本程序釆用的存储结构是单链表结构，其定义的结点包括三部分：系数、指数以及下一个结点的地址。示意图如下：2.2关键算法分析A.输入多项式1.设置多项式的项数m2.按照多项式的项数中请动态数组ea□和eb[]存储两个多项式的结点,cl[]、dl[]、c2[]、d2□分别存储两个多项式的系数和指数;3.再将输入的系数以及指数赋给每一个结点的coef和expn域；4.利用尾插法将每个结点加入链表。时间复杂度：空间复杂度：B.输出多项式②获取头结点,并将其赋给结点指针P；③当p不为零时循环2.1

7、如果p结点的系数为正数且p结点不为头结点，则在输出这一项前加”+”，即输出"+coef*x"exp”,p指针后移;2否则肓接输出p结点的”coef*x"exp”，p指针后移；时间复杂度：0(1)空间复杂度：S(l)C.多项式的和加1.若p->data.expdata.exp1.1q结点不变2.2p结点向下移2.1pprior二p;1.2.2p=p->next;示意图:a1.若p->data.exp>q->data.exp执行一下主要操作步骤1p_prior->next=q;p_prior=q;q二q->

8、next;p_prior->next=p;示意图：p->data.exp>q->data.exp的情况

9、♦若p->data.exp~q->data.exp执行以卜操作步骤：2.1若合并系数为零,则删除p结点，主要步骤:3・1・1p_prior->next=p->next;1.2deletep;3.1.3p=p_prior->next;②1.4Node*temp=q;3.1.5q=q->next;3.1.6deletetemp;示意图:合并系数为零卩3.2合并系数不为零，将其从新赋予p结点，主要

10、步骤:3.2.1p_prior=p;3.2.2p二p_prior-〉next;3.2.3Node*temp=q;3.2・4q=q->ncxt;3.2・5deletetemp;示意图：②若p为空fl.q不为空的情况p_prior->ncxt=q;示意图：ppriorPvA③将B链表置成空链表时间复杂度：O(n)空间复杂度：0(2)A.多项式的相减将B链表中所冇结点的coef置为相反数；再将新的B链表与A链表执行相加操作；B.多项式的求导1.将指针指到多项式的第一项的结点：Nodc

11、>*p=GctFirst()->ncxt;2.循环n次2.1每项求导的系数为：p->coef*p->expn;ffi数为：p->expn-l;2.2将新结点插入新链表；1.3指针p后移。时间复杂度：0(n)空间复杂度：S(l)C.求值1.将工作指针指向多项式的第一项；2.将结果result置为0；3.指针不为空，即进行循环：3.1result+=p->data.coef*((float