数据结构实验报告实验题目元多项式.doc
文本预览下载声明
数据结构实验报告
实验名称： 实验一 题目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
显示全部