数据结构实验一完成多项式的相加相乘运算.docx
《数据结构实验一完成多项式的相加相乘运算.docx》由会员分享，可在线阅读，更多相关《数据结构实验一完成多项式的相加相乘运算.docx（22页珍藏版）》请在冰点文库上搜索。
数据结构实验一完成多项式的相加相乘运算
福建农林大学金山学院本科实验报告标准〔暂行〕
程序设计类
一、每个实验工程一份实验报告。
二、实验报告内容一般包括以下几个内容：
1、实验工程名称：
2、实验目的和要求：
3、实验内容和原理：
4、实验环境：
本次上机实验所使用的软硬件平台。
5、算法描述及实验步骤：
用算法、流程图或者源代码的形式表达算法设计思想与算法实现步骤。
6、调试过程：
详细记录程序在调试过程中出现的问题及解决方法。
7、实验结果：
记录测试数据及程序执行的结果。
8、总结：
对上机实验结果进行分析、上机的心得体会及改良意见。
9、附录〔调试正确的源程序清单〕
说明：
1、2、3、4、5属于实验预习报告的内容，每次实验需经指导教师检查签字后才能进行实验。
三、实验报告格式见附件二〔可打印〕。
四、每学期将拟存档的学生实验报告按课程、学生装订成册，即每个学生每门课程所有实验报告装订成一本。
装订线在左侧，第一页加订实验报告封皮。
五、福建农林大学计算机与信息学院实验报告封皮范本见附件一。
六、福建农林大学计算机与信息学院实验报告范本见附件二。
附件一：
福建农林大学金山学院
〔程序设计类课程〕
实验报告
课程名称：
线性表及其应用
姓名：
系：
专业：
计算机科学与技术
年级：
08级
学号：
指导教师：
林敏
职称：
讲师
2010年4月18日
实验工程列表
序号
实验工程名称
成绩
指导教师
1
线性表及其应用
2
哈夫曼树及哈夫曼编码译码的实现
3
Prim最小生成树
4
实现Fibonacci检索算法
5
快速、堆、基数排序算法的设计
6
7
8
9
10
11
12
福建农林大学金山学院实验报告
系〔教研室〕：
专业：
计算机科学与技术年级：
08实验课程：
姓名：
学号：
实验室号：
______计算机号：
实验时间：
指导教师签字：
成绩：
实验一：
完成多项式的相加运算〔验证性、4学时〕
一、实验目的和要求
完成多项式的相加、相乘运算。
〔1〕掌握线性表的插入、删除、查找等根本操作设计与实现
〔2〕学习利用线性表提供的接口去求解实际问题
〔3〕熟悉线性表的的存储方法
二、实验内容和原理
设计一个一元多项式的简单计算程序，其根本功能有：
〔1〕输入并建立多项式；〔2〕输出多项式；〔3〕多项式的相加运算。
利用单链表实现。
使用单链表实现一元多项式的存储，并实现两个一元多项式的加法运算。
三、实验环境
硬件：
〔1〕学生用微机〔2〕多媒体教室或远程教学〔3〕局域网环境
软件：
〔1〕WindowsXP中文操作系统〔2〕
四、算法描述及实验步骤
1、描述：
加法：
输入建立一元多项式,进行简单加法运算,输出结果；通过建立单链表A和B分别存放多项式的a和b的各项系数及指数；并且利用A使得不产生新的节点而在A中存放数据运算结果；该过程通过定义指针变量p和q使它们分别指向两个多项式的第一个节点，之后依次比拟它们所指向的项的指数，即一种情况指数相等时系数相加且和不为零，修改当前p所指项的系数〔和〕，同时删除q所指项，假设和为零那么同时删除p和q各自所指；情况二，p当前项指数大于q当前项，将q所指插入p所指之前作为结果项之一；情况三，p当前项指数小于q当前项，p所指作为多项式和的一项，移动p指向下一项，进行比拟，在移动p，q至其中以个链空，把另一个链余下节点插在p所指之后；
乘法：
定义指针p,q指向所操作节点，通过A链表的每一项与B链表各项相乘，指数相加，系数相乘，将值赋给新节点各自域，构成一新的链表，最后返回头结点。
可这样有一个问题，即新生成的链表，即最终结果混乱，没有对数据进行过滤，相同指数项应在执行加法运算，所以可以这样实现，通过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!
=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->next=q;
free（B）;
returnA;}
2〕乘法算法
polynomial*polyand（polynomial*A,polynomial*B）/*核心算法实现两链表的乘法运算*/
{polynomial*p,*q,*n,*head,*r,*temp,*m;//定义当前指针p，q风别指向两链表和头指针，尾指针，及新生成节点n
intexp;//定义整型指数
floatcoef;//定义浮点型系数
head=（polynomial*）malloc（sizeof（polynomial））;//创头节点为新生链表准备
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->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->next;//后移指针，为下一节点做准备
q=q->next;//控制B链表下一项
//printf（"%f%d",coef,exp）;//调试用
}
p=p->next;//控制A链表下一项
m->next=NULL;//链表尾置空
//head=head->next;
polyadd（head,temp）;//
}
returnhead;
}
2、1〕加法算法流程图
2〕乘法算法流程图
3、代码（注释）
仅作参考--redbatzero
#include"stdio.h"
#include"malloc.h"
typedefstructlinknode/*定义节点*/
{
floatcoef;
intexp;
structlinknode*next;
}polynomial;
polynomial*creatlist（）/*创立单链表*/
{
floatx;/*节点中存放项系数和指数*/
intz;
polynomial*head,*r,*n;/*下指针,分别是头指针、尾指针和新建立节点的指针*/
head=（polynomial*）malloc（sizeof（polynomial））;/*malloc分配内存单元给头指针申请空间*/
head->next=NULL;/*头指针next指向空位空链表状态*/
r=head;
printf（"建立一元多项式:
（以系数0结束）\n"）;/*打印文字提醒用户输入*/
while（x!
=0）/*建立单链表*/
{
n=（polynomial*）malloc（sizeof（polynomial））;/*建立新节点,将用户输入的数据分别作为项（各节点）的系数和指数*/
n->coef=x;
n->exp=z;
r->next=n;/*为指针指向下一新建节点*/
r=r->next;/*后移尾指针*/
//r=n;
printf（"请按升幂输入系数和指数:
"）;
scanf（"%f%d",&x,&z）;
}
r->next=NULL;
head=head->next;/*链接节点使之勾成链表*/
return（head）;/*还回head指针（链表头标志或是说地址）给函数调用者*/
}
voidprint（polynomial*head）/*打印输出函数*/
{
polynomial*p;/*为传入的链表设立当前指针*/
p=head->next;/*将指针后移指向包含实际数据的节点*/
while（p!
=NULL）/*判断需要打印的链表是否为空*/
{
printf（"%.2fX（%d）",p->coef,p->exp）;/*打印当前指针所指项的数据*/
p=p->next;/*后移指针指向下一节点*/
}
printf（"\n"）;
}
polynomial*polyadd（polynomial*A,polynomial*B）/*核心算法实现两链表的加法运算并将结果保存在A中*/
{polynomial*p,*q,*s,*r;/*为链表设立指针分别指向链表A和链表B（多项式A和B），s为临时存放为后续移动指针做地址保存*/
floatx;
p=A->next;
q=B->next;
s=A;/**//*s作为p的前驱*/
while（（p!
=NULL）&&（q!
=NULL））/*判断所比拟链表是否为空不同时为空时反复执行以下函数*/
if（（p->exp）>（q->exp））/*将q插入p之前*/
{
r=q->next;/*保存当前q的下一结点地址为r后移作准备*/
q->next=p;/*将p接到到q之后*/
s->next=q;/*将q彻底的插入到A链表中p之前作为结果项之一*/
s=q;/*修改当前指针为下一节点作比拟准备*/
q=r;
}
elseif（（p->exp）<（q->exp））/*将p作为结果项之一，后移p进行下一结点比拟*/
{
s=p;/*后移s*/
p=p->next;/*后移当前指针p指向下一节点*/
}
else/*当前链表中节点的指数相等进行系数加法运算*/
{
x=（p->coef）+（q->coef）;/*实现系数相加赋给x，节点中的系数单元*/
if（x!
=0）/*判断系数和是否为零,不为零执行系数替换原有数据*/
{
p->coef=x;
s=p;/*p的前驱指针后移*/
}
else/*系数和为零*/
{
s->next=p->next;/*为释放p准备*/
free（p）;
}
p=s->next;/*p指针指向下一节点*/
r=q;/*为释放q作准备*/
q=q->next;/*q指向下一节点*/
free（r）;
}
if（q!
=NULL）/*循环结束将q中剩余节点直接插入p的为节点之后作为结果项*/
s->next=q;
free（B）;/*运算结束释放B链锁占空间*/
returnA;/*还回A链给函数调用者*/
}
polynomial*polyand（polynomial*A,polynomial*B）/*核心算法实现两链表的乘法运算*/
{polynomial*p,*q,*n,*head,*r,*temp,*m;//定义当前指针p，q风别指向两链表和头指针，尾指针，及新生成节点n
intexp;//定义整型指数
floatcoef;//定义浮点型系数
head=（polynomial*）malloc（sizeof（polynomial））;//创头节点为新生链表准备
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->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->next;//后移指针，为下一节点做准备
q=q->next;//控制B链表下一项
//printf（"%f%d",coef,exp）;//调试用
}
p=p->next;//控制A链表下一项
m->next=NULL;//链表尾置空
//head=head->next;
polyadd（head,temp）;//
}
returnhead;
}
voidselet（polynomial*A,polynomial*B）
{
intp;
polynomial*C;
printf（"1、实现相加运算\n2、实现相乘运算\n"）;
printf（"请选择运算:
"）;
scanf（"%d",&p）;
while（p!
=1&&p!
=2）
{
printf（"输入错误,请重新选择:
\n"）;
scanf（"%d",&p）;
}
if（p==1）
C=polyadd（A,B）;
elseif（p==2）
C=polyand（A,B）;
printf（"Theresultis:
\n"）;
print（C）;/*调用输出打印函数，打印运算结果*/
}
intmain（）/*主函数*/
{
polynomial*A,*B;/*设立指针分别指向多项式链表A和链表B以及C作为结果*/
A=creatlist（）;/*建立打印多项式A*/
print（A）;
B=creatlist（）;/*建立打印多项式B*/
print（B）;
selet（A,B）;
return0;/*还回系统调用0，结束整个程序*/
}
4、调试过程
1打印输出调试：
输入〔3,4〕〔-2,5〕〔2.6,7〕即3x^4-2x^5+2.6x^6
xxx（6）如图：
输出正常；
2加法运算调试
输入数据ａ：
〔2,3〕〔3,4〕〔4,5〕和〔1,2〕〔3,4〕〔-5,5〕即2x^3+3x^4+4x^5和x^2+3x^4-5x^5并没有项预期的一样实现加法运算，而是在打印出各项数据后程序终止。
如图：
输入数据ｂ：
〔2,3〕〔3,4〕〔4,5〕和〔1,3〕〔3,4〕〔-5,5〕即2x^3+3x^4+4x^5和x^3+3x^4-5x^5结果和项预期的一样实现了加法运算，如图：
比照得知数据ａ和ｂ唯一不同的是Ａ的第一项的的指数大于Ｂ的第一项指数因此应该想到程序在执行比拟第一项之后并不能进行该有的操作即而之后的第二项第三项却可以执行有暗示着实现（（p->exp）>（q->exp））并没内部错误：
因此矛头指向了
polynomial*p,*q,*s,*r;
floatx;
p=A->next;
q=B->next;
s=p;/*出错原因*/
而其中ｓ＝ｐ正是出错所在了，ｓ是作为ｐ的前驱而不是p->next的前驱，故而该是s=A；
修改后正常的实现了改算法；
但由于程序以实现该算法的核心思想为主因此并没有过多注意的在用户界面上实现和排序问题和出错等处理。
因此对用户输入的要求严格。
3乘法运算调试
通过以上改正后进行测试
测试数据〔3,4〕〔4,5〕〔5,6〕和〔2，4〕〔3，6〕〔6,7〕
未能得到预期结果；分析：
可知第一项6.00x（8）并没能出现
可能有两个原因，一是执行运算时跳过了B链表第一项；二是运算了单没能打印出；
有后面的数据8.00x（9）可知,是第二种可能；
因此在执行运算后用printf（"%f%d",coef,exp）;得
结果如图：
可以确定错误出处了，
经检查知运算后多了head=head->next;将其删除即可。
六、实验结果
测试数据〔1〕：
2,33,45,6和1,22,33,45,7即2x^3+3x^4+5x^6和1x^22x^3+3x^4+5x^7
实验结果〔1〕：
加法1.00x
（2）4.00x（3）6.00x（4）5.00x（5）5.00x（7）
即1.00x^2+4.00x^3+6.00x^4+5.00x^5+5.00x^7
乘法9.00x（8）12.00x（9）15.00x（10）38x（11）30x（13）即9x^2+12x^3+15x^4+38x^5+30x（13）
实验截图〔1〕：
加法
乘法
测试数据〔2〕：
加法
1,22,33,5和-3,22,34,40.4,5即1x^2+2x^3+3x^5和-3x^2+2x^3+4x^4+0.4x^5
乘法：
3,45,60.5,7和5,6-3,7-0.8,8即3x^4+5x^6+0.5x7和5x^6-3x^7-0.8x^8
实验结果〔2〕：
加法-2.00x
（2）4.00x（3）4.00x（4）3.4x（5）即-2.00x^2+4.00x^3+4.00x^4+3.4x^5
乘法
15.00x（10）-9.00x（11）22.60x（12）-12.50x（13）-5.50x（14）-0.40x（15）
即5.00x^10-9.00x^11+22.60x^12-12.50x^13-5.50x^14-0.40x^15
实验截图〔2〕：
加法
乘法
七、总结
在设计该算法时，由于过于依赖书本上的例子，导致很多不必要的麻烦，例如在建立链表时头指针的设立导致了之后运用到相关的指针时没能很好的移动指针出现了数据重复输出或是输出系统缺省值，不能实现算法。
实现加法时该链表并没有向通常那样通过建立第三个链表来存放运算结果，而是再度利用了链表之一来进行节点的比拟插入删除等操作。
大大压缩了程序代码，节省了程序空间使用，但不能防止的是必须要求输入数据时按升幂排序的缺乏当然可在数据的输入后先做一个节点的排序函数，通过对链表排序后再进行之后加法或乘法运算也是可以的。
但它也给后续乘法的实现提供了便利，当前我们的重点是实现单链表的加法乘法运算，故而，我选择了这个算法，并真正的实现了它。
设计中让我更深的体会到了动手能力的重要性，在实现乘法时虽然花了我很多时间去研究书上虽然错误的算法，但那提高了我的洞察能力，并让我单独思考，最终虽然很局限〔数据输入上〕的实现了一元多项式的加乘法运算，可是我学到了远远不止这些。
附录：
升级会员 