数据结构实验报告完成多项式的运算

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

1、简单介绍：本次作业力在学会链表表示线性表的插入、删除、查找等基本操作设计与实现，学习利用链表提供的接口去求解实际问题，同时熟悉链表的的存储方法。再基于线性链表的基础设计完成多项式的相加运算程序。一、实验目的和要求完成多项式的相加、相乘运算。（1）掌握线性表的插入、删除、查找等基本操作设计与实现（2）学习利用线性表提供的接口去求解实际问题（3）熟悉线性表的的存储方法二、实验内容和原理1.实验内容设计一个一元多项式的简单计算程序，其基本功能有：（1）输入并建立多项式；（2）输出多项式；（3）多项式的相加运

2、算。利用单链表实现。2.实验原理使用单链表实现一元多项式的存储，并实现两个一元多项式的加法运算。三、实验环境硬件：（1）学生用微机（2）多媒体教室或远程教学（3）局域网环境软件：（1）WindowsXP中文操作系统（2）VC6.0四、算法描述及实验步骤1、描述：加法：输入建立一元多项式,进行简单加法运算,输出结果；通过建立单链表A和B分别存放多项式的a和b的各项系数及指数；并且利用A使得不产生新的节点而在A中存放数据运算结果；该过程通过定义指针变量p和q使它们分别指向两个多项式的第一个节点，之后依次比

3、较它们所指向的项的指数，即一种情况指数相等时系数相加且和不为零，修改当前p所指项的系数（和），同时删除q所指项，若和为零则同时删除p和q各自所指；情况二，p当前项指数大于q当前项，将q所指插入p所指之前作为结果项之一；情况三，p当前项指数小于q当前项，p所指作为多项式和的一项，移动p指向下一项，进行比较，在移动p，q至其中以个链空，把另一个链余下节点插在p所指之后；乘法：定义指针p,q指向所操作节点，通过A链表的每一项与B链表各项相乘，指数相加，系数相乘，将值赋给新节点各自域，构成一新的链表，最后返回

4、头结点。可这样有一个问题，即新生成的链表，即最终结果混乱，没有对数据进行过滤，相同指数项应在执行加法运算，所以可以这样实现，通过A链表的每一项与B链表各项相乘的新生成节点单独构成一链表，并将第一个链表加入另一新链表，循环此操作将后生成的链表加之先前的链表，即可实现排序问题。1）加法算法如下：polynomial*polyadd(polynomial*A,polynomial*B){polynomial*p,*q,*s,*r;floatx;p=A->next;q=B->next;s=p;while((p

5、!=NULL)&&(q!=NULL))if((p->exp)>(q->exp)){r=q->next;q->next=p;s->next=q;s=q;q=r;}elseif((p->exp)<(q->exp)){s=p;p=p->next;}else{x=(p->coef)+(q->coef);/*if(x!=0){p->coef=x;s=p;}else{s->next=p->next;free(p);}*/p=s->next;r=q;q=q->next;free(r);}if(q!=NULL)s->

6、next=q;free(B);returnA;}2）乘法算法polynomial*polyand(polynomial*A,polynomial*B)/*核心算法实现两链表的乘法运算*/{polynomial*p,*q,*n,*head,*r,*temp,*m;//定义当前指针p，q风别指向两链表和头指针，尾指针，及新生成节点nintexp;//定义整型指数floatcoef;//定义浮点型系数head=(polynomial*)malloc(sizeof(polynomial));//创头节点为新生

7、链表准备head->next=NULL;//置空链表r=head;//临时变量，为后移指针做准备p=A->next;//当前指针跳过A链表头指向实际运算数while(p!=NULL)//控制操作，循环A链表与内部while所控制B链表进行项之间的运算{temp=(polynomial*)malloc(sizeof(polynomial));//在内部创头节点为新生链表准备即A中每一项与B中各项相乘构成一新链表temp->next=NULL;//置空链表m=temp;//临时变量，为后移指针做准备q=B

8、->next;//当前指针跳过B链表头指向实际运算数while(q!=NULL){n=(polynomial*)malloc(sizeof(polynomial));//建立新节点exp=p->exp+q->exp;//进行系数相加操作coef=p->coef*q->coef;////进行指数相乘操作n->coef=coef;//赋值新节点的系数域n->exp=exp;//赋值新节点的指数域m->next=n;//链接节点至头结点，构成链表m=m->ne