完整word版链表线性结构多项式的加减乘除.docx
《完整word版链表线性结构多项式的加减乘除.docx》由会员分享，可在线阅读，更多相关《完整word版链表线性结构多项式的加减乘除.docx（19页珍藏版）》请在冰点文库上搜索。
完整word版链表线性结构多项式的加减乘除
哈尔滨工业大学计算机科学与技术学院
实验报告
课程名称：
数据结构与算法
课程类型：
必修
实验项目：
线性结构及其应用
实验题目：
多项式的加减乘除和特定值带入
实验日期：
2017/11/5
班级：
1603001
学号：
**********
姓名：
***
设计成绩
报告成绩
指导老师
张岩
一、实验目的
设计线性表的链式存储结构，并实现一元多项式的代数运算。
二、实验要求及实验环境
（1）实验要求：
以链表存储一元多项式，在此基础上完成对多项式的代数操作。
1.能够输入多项式（可以按各项的任意输入顺序，建立按指数降幂排列的多项式）
和输出多项式（按指数降幂排列）,以文件形式输入和输出，并显示。
2.能够计算多项式在某一点x=x0的值，其中x0是一个浮点型常量，返回结果为
浮点数。
3.能够给出计算两个多项式加法、减法、乘法和除法运算的结果多项式，除法运
算的结果包括商多项式和余数多项式。
4.要求尽量减少乘法和除法运算中间结果的空间占用和结点频繁的分配与回收
操作。
（提示：
利用循环链表结构和可用空间表的思想，把循环链表表示的多项
式返还给可用空间表，从而解决上述问题）。
（2）实验环境：
windows下的CB;
三、设计思想（本程序中的用到的所有数据类型的定义，主程序的流程图及各程序模块之间的调用关系）
1．逻辑设计:
structpolynode
{
intcoef;
intexp;
structpolynode*link;
};//建立链表
typedefstructpolynodepoly;
poly*Attch（intc,inte,poly*d）;//多项式插入
poly*newPoly（）;//新链表
poly*padd（poly*p1,poly*p2）;//多项式加法
poly*pmul（poly*p1,poly*p2）;//乘法
poly*inputPoly（）;//输入多项式
poly*psub（poly*p1,poly*p2）;//减
poly*pdiv（poly*p1,poly*p2）;//除
poly*inputPoly1（）;
doublecaculate（doublex,poly*p）;//计算多项式
voidsortPoly（poly*p）;//多项式排序
voidoutputPoly（poly*p）;//输出多项式
voiddelPoly（poly*p）;//清空多项式
2．物理设计：
四、测试结果
五、经验体会与不足
不能连续输入多个多项式
函数设计不够简洁
算法过于直接简单
加注释后修改代码方便
六、附录：
源代码（带注释）
#include
#include
structpolynode
{
intcoef;
intexp;
structpolynode*link;
};//建立新链表
typedefstructpolynodepoly;
poly*Attch（intc,inte,poly*d）;//插入链表
poly*newPoly（）;//建立新链表
poly*padd（poly*p1,poly*p2）;//加法
poly*pmul（poly*p1,poly*p2）;//乘法
poly*inputPoly（）;//输入多项式
poly*psub（poly*p1,poly*p2）;//减法
poly*pdiv（poly*p1,poly*p2）;//除法
poly*inputPoly1（）;//输入
doublecaculate（doublex,poly*p）;//计算
voidsortPoly（poly*p）;//排序
voidoutputPoly（poly*p）;//输出多项式
voiddelPoly（poly*p）;//除法
voidInsert（poly*p,poly*h）{
if（p->coef==0）
free（p）;
else{
poly*q1,*q2;
q1=h;q2=h->link;
while（q2&&p->expexp）{
q1=q2;
q2=q2->link;
}/*判断两个指数是否相等*/
if（q2&&p->exp==q2->exp）{
q2->coef+=p->coef;
free（p）;
if（!
q2->coef）{
q1->link=q2->link;
free（q2）;
}
}/*相等就加系数*/
else{
p->link=q2;
q1->link=p;
}
}
/*不等就插在后面*/
}
intmain（）
{
poly*p1,*p2,*padd1,*psub1,*pmul1;
p1=newPoly（）;
printf（"第一个多项式\n"）;
p1->link=inputPoly（）;
outputPoly（p1）;
p2=newPoly（）;
printf（"第二个多项式\n"）;
p2->link=inputPoly1（）;
outputPoly（p2）;
padd1=newPoly（）;
pmul1=newPoly（）;
psub1=newPoly（）;
padd1->link=padd（p1,p2）;
printf（"padd\n"）;
outputPoly（padd1）;
psub1->link=psub（p1,p2）;
printf（"psub\n"）;
outputPoly（psub1）;
pmul1->link=pmul（p1,p2）;
printf（"pmul\n"）;
outputPoly（pmul1）;
printf（"输入x的值！
"）;
intx;
scanf（"%d",&x）;
x=caculate（x,p1）;
printf（"%d\n",x）;
pdiv（p1,p2）;
return0;
}
poly*newPoly（）
{
poly*x;
x=（poly*）malloc（sizeof（poly））;
x->link=NULL;
x->coef=0;
x->exp=0;
returnx;
}
poly*Attch（intc,inte,poly*d）
{
poly*x;
x=newPoly（）;
x->coef=c;
x->exp=e;
d->link=x;
returnx;
}
poly*padd（poly*p1,poly*p2）
{
poly*a,*b,*c,*d,*p;
c=newPoly（）;
d=c;
p=c;
a=p1->link;
b=p2->link;
while（a!
=NULL&&b!
=NULL）
{
if（a->exp>b->exp）//如果a的系数大于b把a先输入
{
c=Attch（a->coef,a->exp,c）;
a=a->link;
}
elseif（a->expexp）//小于相反
{
c=Attch（b->coef,b->exp,c）;
b=b->link;
}
else//相等
{
c=Attch（b->coef+a->coef,a->exp,c）;
a=a->link;
b=b->link;
}
}
/*ab比较完成开始遍历剩下的未插入的*/
while（a!
=NULL）
{
c=Attch（a->coef,a->exp,c）;
a=a->link;
}
while（b!
=NULL）
{
c=Attch（b->coef,b->exp,c）;
b=b->link;
}
c->link=NULL;
d=d->link;
p->link=NULL;
delPoly（p）;
returnd;
}
poly*psub（poly*p1,poly*p2）//加和减思路相同，b的系数得输入相反值
{
poly*a,*b,*c,*d,*p;
c=newPoly（）;
d=c;
p=c;
a=p1->link;
b=p2->link;
while（a!
=NULL&&b!
=NULL）
{
if（a->exp>b->exp）
{
c=Attch（a->coef,a->exp,c）;
a=a->link;
}
elseif（a->expexp）
{
c=Attch（b->coef*（-1）,b->exp,c）;
b=b->link;
}
else
{
if（（a->coef-b->coef）>0）{
c=Attch（a->coef-b->coef,a->exp,c）;
a=a->link;
b=b->link;
}
else{
a=a->link;
b=b->link;
}
}
}
while（a!
=NULL）
{
c=Attch（a->coef,a->exp,c）;
a=a->link;
}
while（b!
=NULL）
{
c=Attch（b->coef*（-1）,b->exp,c）;
b=b->link;
}
c->link=NULL;
d=d->link;
p->link=NULL;
delPoly（p）;
returnd;
}
/*
乘法，先用第一个链表的第一个数据乘以第二个链表里的所有值，储存在新的链表中，之后遍历一中所有的值，最后把这些多项式加在一起。
*/
poly*pmul（poly*p1,poly*p2）//乘法
{
poly*a,*b,*c,*d,*q,*sum;
intaex,aco;
a=p1->link;
b=p2->link;
sum=newPoly（）;
q=sum;
while（a!
=NULL）
{
c=newPoly（）;
d=c;
aco=a->coef;
aex=a->exp;
while（b!
=NULL）
{
c=Attch（aco*（b->coef）,aex+（b->exp）,c）;
b=b->link;
}
b=p2->link;
sum->link=padd（d,sum）;
a=a->link;
delPoly（d）;
}
sum=sum->link;
q->link=NULL;
delPoly（q）;
sortPoly（sum）;
returnsum;
}
/*
除法：
先用链表一第一个的系数除以第二个链表的第一个系数，得到的值乘以被除多项式，再用第一个多项式减。
最后得到一个最大系数比被除数小的多项式。
*/
poly*pdiv（poly*p1,poly*p2）{
poly*hf,*pf,*temp1,*temp2;
poly*q1;
q1=p1->link;
poly*q2;
q2=p2->link;
hf=newPoly（）;
hf->link=NULL;
pf=newPoly（）;
pf->link=NULL;
temp1=newPoly（）;
temp1->link=NULL;
temp2=newPoly（）;
temp2->link=NULL;
temp1=padd（temp1,p1）;;
while（q1->exp>=q2->exp）{
temp2->link=newPoly（）;
temp2->link->coef=（q1->coef）/（q2->coef）;
temp2->link->exp=（q1->exp）-（q2->exp）;
Insert（temp2->link,hf）;
p1=psub（p1,pmul（p2,temp2））;
q1=p1->link;
temp2->link=NULL;
}
pf=psub（temp1,pmul（hf,p2））;
p2=temp1;
printf（"商是"）;
outputPoly（hf）;
printf（"余数是"）;
outputPoly（pf）;
}
/*
输入：
多项式的系数和指数存在p1文件中，两个两个读，分别赋给多项式的系数和指数。
*/
poly*inputPoly（）
{
poly*q,*p;
p=newPoly（）;
q=p;
FILE*fp;
if（（fp=fopen（"c:
\\p1.txt","rt"））==NULL）
{
printf（"\nCannotopenfilestrikeanykeyexit!
"）;
getch（）;
exit
（1）;
}
inta,b;
while（fscanf（fp,"%d%d",&a,&b）!
=-1）
{
p->link=newPoly（）;
p=p->link;
p->coef=a;
p->exp=b;
}
p=q;
sortPoly（q）;
q=q->link;
p->link=NULL;
delPoly（p）;
fclose（fp）;
returnq;
}
poly*inputPoly1（）
{
poly*q,*p;
p=newPoly（）;
q=p;
FILE*fp;
if（（fp=fopen（"c:
\\p2.txt","rt"））==NULL）
{
printf（"\nCannotopenfilestrikeanykeyexit!
"）;
getch（）;
exit
（1）;
}
inta,b;
while（fscanf（fp,"%d%d",&a,&b）!
=-1）
{
p->link=newPoly（）;
p=p->link;
p->coef=a;
p->exp=b;
}
p=q;
sortPoly（q）;
q=q->link;
p->link=NULL;
delPoly（p）;
fclose（fp）;
returnq;
}
/*
输出：
读取系数和指数，按a*x^b的形式输出
*/
voidoutputPoly（poly*p）
{
poly*q;
q=p->link;
if（q!
=NULL）
{
printf（"%dx^%d",q->coef,q->exp）;
q=q->link;
}
else
printf（"0"）;
while（q!
=NULL）
{
if（q->coef<0）
printf（"-%dx^%d",-q->coef,q->exp）;
else
printf（"+%dx^%d",q->coef,q->exp）;
q=q->link;
}
printf（"\n"）;
}
/*删除多项式*/
voiddelPoly（poly*p）
{
if（p->link==NULL）
free（p）;
else
delPoly（p->link）;
}
/*冒泡排序*/
voidsortPoly（poly*p）
{
poly*a,*b;
inti;
a=p->link;
while（a!
=NULL）
{
b=a->link;
while（b!
=NULL）
{
if（（a->exp）<（b->exp））
{
i=a->coef;
a->coef=b->coef;
b->coef=i;
i=a->exp;
a->exp=b->exp;
b->exp=i;
}
b=b->link;
}
a=a->link;
}
}
/*计算：
调用函数pow（x，b）之后乘以系数*/
doublecaculate（doublex,poly*p）{
doublem=0;
if（p->link==NULL）{
return0;
}
else{
do{
m+=p->coef*pow（x,p->exp）;
p=p->link;
}
while（p!
=NULL）;
}
returnm;
}
升级会员 