内容发布更新时间 : 2024/11/5 20:41:45星期一 下面是文章的全部内容请认真阅读。

北京邮电大学信息与通信工程学院

数据结构实验报告

实验名称： 实验一 题目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.expdata.exp，则p_prior=p;p=p->next。 （4）否则，若p->data.exp>q->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 * temp = q; ⑤ q = q->next; ⑥ delete temp;

(Ⅰ)示意图

p p-prior ② ③

①

④

temp q ⑤ q ⑥

（Ⅱ）合并系数不为零 ① p_prior = p; ② p=p_prior->next; ③ Node * temp = q; ④ q = q->next; ⑤ delete temp;

第3页