- 1、本文档共6页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
数据结构实验报告实验题目元多项式
数据结构实验报告
实验名称: 实验一 题目3 一元多项式
学生姓名: 许虎
班 级: 信通20
班内序号: 10
学 号: 2011210578
日 期: 2012年11月2日
实验要求
实验目的:
利用线性表实现一个一元多项式Polynomial
f(x) = a0 + a1x + a2x2 + a3x3 + … + anxn
并实现相应功能。
实验内容:
使用一元多项式类存储多项式元素,通过定义并实现相关函数完成相应的功能,并通过设计的main函数测试了其正确性。用户可自行输入正确的多项式进行相关运算,得到相应结果。
相关函数实现的功能:1.能够实现一元多项式的输入和输出
2.能够进行一元多项式相加
3.能够进行一元多项式相减
4.能够计算一元多项式在x处的值
5.能够计算一元多项式的导数
6.能够进行两个一元多项式相乘
2. 程序分析
2.1 存储结构
存储结构:单链表(带头节点)
单链表示意图如下:
在本程序中使用结构类型element(赋给模版类型T)数组data储存数据成员,包含coef(系数)和exp(指数)两个成员,但仍为一维数组。在节点构造类型Node(运用了模版类)中定义了指针域next指向下一个结点,直到链表尾将next置空,front头指针为该链表类私有数据成员,如此得到多项式链表(单链表)。
2.2 关键算法分析
1、关键算法:
1)一元多项式类求和函数
(1)初始化工作指针p_prior(指向A链表头结点),p(p-next),q(指向B链表第一个结点)。
(2)若p和q都不为空,则循环下列操作:
(3)若p-data.expq-data.exp,则p_prior=p;p=p-next。
(4)否则,若p-data.expq-data.exp,则:
将q结点加入到A链表p结点之前,q指向B链表下移个结点。
(5)否则,p-data.coef=p-data.coef+q-data.coef;
(6)若p-data.coef==0,删除p结点,p指向下一个结点,删除q结点,q指向下一个结点。
(7)跳出循环,若p为空且q不为空,则将q结点及其后所有结点追加到A链表的最后。
(8)将B链表置空。
2)一元多项式相乘函数
(1)设置两个空链表分别为C、D,其中C为储存X每个元素链表与Y链表全部元素相乘结果的链表,D为最终两个多项式相乘结果的链表。
(2)初始化工作指针p1(X链表第一个结点),p2(Y链表第一个结点)。
(3)若p1不为空,则循环下列操作:
(4)初始化工作指针p3(指向C链表头结点),临时指针temp(p2)。
(5)当Y链表第一个结点存在,即temp非空时,则循环下列操作:
(6)定义新结点s,储存X链表中一个元素与Y链表中一个元素相乘结果,将此结点插入C链表中。
(7)如(6)操作,使用尾插法建立了C链表。
(8)跳出内循环,将C链表加到D链表中,C链表被置空,p1指针后移一个。
(9)跳出外循环,打印出最终的D链表。
2、代码详细分析:
1)一元多项式类求和函数
(1)情况1,X链元素指数小于Y链元素(p-data.exp q-data.exp)
①p_prior=p;
②p=p-next;
情况1示意图
(2)情况2,X链元素指数大于Y链元素
①p_prior-next=q;
②p_prior=q;
③q=q-next;
④p_prior-next=p;
情况2示意图
(3)情况3,指数相等可相加的情况
(Ⅰ)合并系数为零
p_prior-next = p-next;
delete p;
p = p_prior-next;
Nodeelement * temp = q;
q = q-next;
delete temp;
(Ⅰ)示意图
(Ⅱ)合并系数不为零
p_prior = p;
p=p_prior-next;
Nodeelement * temp = q;
q = q-next;
delete temp;
(Ⅱ)示意图
(4)情况4, q结点及其后所有结点追加到A链表的最后
① p_prior-next=q;
2)一元多项式相乘函数
(1)每次外循环用尾插法得到链表C
①s-data.coef=p1-data.coef*temp-data.coef;
s-data.exp=p1-data.exp+temp-data.exp;
②p3-n
文档评论(0)