内容发布更新时间 : 2024/12/23 23:33:53星期一 下面是文章的全部内容请认真阅读。
北京邮电大学信息与通信工程学院
数据结构实验报告
实验名称: 实验一 题目3 一元多项式 学生姓名: 许虎 班 级: 信通20 班内序号: 10 学 号: 2011210578 日 期: 2012年11月2日
1. 实验要求
实验目的:
利用线性表实现一个一元多项式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头指针为该链表类私有数据成员,如此得到多项式链表(单链表)。
第1页
北京邮电大学信息与通信工程学院
2.2 关键算法分析
1、关键算法:
1)一元多项式类求和函数
(1)初始化工作指针p_prior(指向A链表头结点),p(p->next),q(指向B链表第一
个结点)。
(2)若p和q都不为空,则循环下列操作:
(3)若p->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示意图
① p p-prior ②
第2页
北京邮电大学信息与通信工程学院
(2)情况2,X链元素指数大于Y链元素 ①p_prior->next=q; ②p_prior=q; ③q=q->next;
④p_prior->next=p;
情况2示意图
p
p-prior ① ②
③
④ q
(3)情况3,指数相等可相加的情况 (Ⅰ)合并系数为零 ① p_prior->next = p->next; ② delete p; ③ p = p_prior->next; ④ Node
(Ⅰ)示意图
p p-prior ② ③
①
④
temp q ⑤ q ⑥
(Ⅱ)合并系数不为零 ① p_prior = p; ② p=p_prior->next; ③ Node
第3页