数据结构实验报告 实验一题目3 一元多项式

《数据结构实验报告 实验一题目3 一元多项式》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、北京邮电大学信息与通信工程学院数据结构实验报告实验名称：实验一题目3一元多项式学生姓名：许虎班级：信通20班内序号：10学号：2011210578日期：2012年11月2日1．实验要求实验目的：利用线性表实现一个一元多项式Polynomialf(x)=a0+a1x+a2x2+a3x3+…+anxn并实现相应功能。实验内容：使用一元多项式类存储多项式元素，通过定义并实现相关函数完成相应的功能，并通过设计的main函数测试了其正确性。用户可自行输入正确的多项式进行相关运算，得到相应结果。相关函数实现的

2、功能：1.能够实现一元多项式的输入和输出2.能够进行一元多项式相加3.能够进行一元多项式相减4.能够计算一元多项式在x处的值5.能够计算一元多项式的导数6.能够进行两个一元多项式相乘2.程序分析2.1存储结构存储结构：单链表（带头节点）单链表示意图如下：在本程序中使用结构类型element（赋给模版类型T）数组data储存数据成员，包含coef（系数）和exp（指数）两个成员，但仍为一维数组。在节点构造类型Node（运用了模版类）中定义了指针域next指向下一个结点，直到链表尾将next置空，fr

3、ont头指针为该链表类私有数据成员，如此得到多项式链表（单链表）。第6页北京邮电大学信息与通信工程学院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

4、指向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链表第一个结点

5、），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,

6、X链元素指数小于Y链元素（p->data.expdata.exp）①p_prior=p;②p=p->next;情况1示意图p②①p-prior第6页北京邮电大学信息与通信工程学院（2）情况2，X链元素指数大于Y链元素①p_prior->next=q;②p_prior=q;③q=q->next;④p_prior->next=p;情况2示意图pp-prior①①　②③q（3）情况3，指数相等可相加的情况（Ⅰ）合并系数为零①p_prior->next=p->next;②deletep;③p=p_

7、prior->next;④Node*temp=q;⑤q=q->next;⑥deletetemp;(Ⅰ)示意图②③p-priorp①④⑤⑥qtempq（Ⅱ）合并系数不为零①p_prior=p;②p=p_prior->next;③Node*temp=q;④q=q->next;⑤deletetemp;第6页北京邮电大学信息与通信工程学院①（Ⅱ）示意图②pp-prior③④⑤qtemp（4）情况4，q结点及其后所有结点追加到A链表的最后①p_prior->next=q;

8、2）一元多项式相乘函数(1)每次外循环用尾插法得到链表C①s->data.coef=p1->data.coef*temp->data.coef;s->data.exp=p1->data.exp+temp->data.exp;②p3->next=s;③p3=s;④p3->next=NULL;示意图q3③^②④^①s以上相应算法步骤说明参见关键算法部分，在此不再赘述。3、计算关键算法的时间、空间复杂度1）一元多项式类求和函数时间复杂度为O（n），空间复杂度为O（n）2）一元多项式相乘函