实验1 线性表应用-多项式计算.doc

浙江大学城市学院实验报告
课程名称 数据结构与算法
实验项目名称 实验一 线性表应用---多项式计算
学生姓名 蓝礼巍 专业班级 学号
实验成绩 指导老师（签名 ） 日期

一. 实验目的和要求
1．进一步掌握线性表的的基本操作。
2．掌握线性表的典型应用----多项式表示与计算。

二. 实验内容
1． 设用线性表 ( (a1, e1), (a2, e2), ……, (am, em) ) 表示多项式P(x) = a1*xe1 + a2*xe2 +…+ am*xem ，其中：a1～am为非零系数，0≤e1＜e2＜…..＜em，请编写用链式存储结构（带表头附加结点的单链表）存储该多项式时，多项式基本操作的实现函数。多项式基本操作应包括初始化多项式、清除多项式、输出多项式、插入一项、删除一项、多项式求值、多项式相加等。要求：把多项式线性表的结构定义及多项式基本操作实现函数存放在头文件Linkpoly.h中，主函数存放在主文件test6_1.cpp中，在主函数中通过调用Linkpoly.h中的函数进行测试。
2． 选做： 编写用顺序存储结构存储多项式时，多项式基本操作的实现函数。要求：把多项式线性表的结构定义及多项式基本操作实现函数存放在文件Seqpoly.h中，在主文件test6_1.cpp中增加测试语句对Seqpoly.h中的函数进行测试。
3． 填写实验报告，实验报告文件取名为report1.doc。
4． 上传实验报告文件report1.doc与源程序文件test6_1.cpp及Linkpoly.h、Seqpoly.h（若有）到Ftp服务器上自己的文件夹下。

三. 函数的功能说明及算法思路
包括每个函数的功能说明，及一些重要函数的算法实现思路
void InitPoly(LNode *&HL)初始化
void TraversePoly(LNode *HL)输出多项式
void ClearPoly(LNode *HL) 删除多项式
void InsertPoly(LNode *HL,double a,double e)插入一项
bool DeletePoly(LNode *&HL,double &a,double &e,int pos)删除一项
double PoluSum(LNode *HL,double x)求值
LNode *PolyAdd2(LNode *p1,LNode *p2)加和

四. 实验结果与分析
包括运行结果截图等

五. 心得体会
记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。
写的时候不仔细，改错就要很久了

【附录----源程序】

Cpp

#include<stdio.h>
#include<stdlib.h>
#include<iostream.h>
#include<math.h>
#include"Linkpoly.h"

void main(){
LNode *head;
InitPoly(head);
double a,e;
while(1){
cout<<"若插入一项,请选1."<<endl;
cout<<"若删除一项,请选2."<<endl;
cout<<"若输出多项式,请选3."<<endl;
cout<<"若清除多项式,请选4."<<endl;
cout<<"若多项式求值,请选5."<<endl;
cout<<"若多项式相加,请选6."<<endl;
cout<<"退出,请选0."<<endl;
cout<<"请输入0-6"<<endl;
int i;
cin>>i;
if(i==1){
cout<<"输入要插入的值"<<endl;
cout<<"系数a=：";
cin>>a;
cout<<"指数e=：";
cin>>e;
InsertPoly(head,a,e);

}
else if(i==2){
int pos;
cout<<"请输入要删除的位置"<<endl;
cin>>pos;
DeletePoly(head,a,e,pos);
cout<<"已删除的值是："<<a<<","<<e<<endl;

}
else if(i==3)
TraversePoly(head);
else if(i==4)
ClearPoly(head);
else if(i==5){
double x;
cout<<"请输入 X：";
cin>>x;
if(head->next!=NULL)
cout<<"多项式之和是"<<PoluSum(head,x)<<endl;
else
cout<<"无多项式"<<endl;

}
else if(i==6){
LNode *b,*c;
InitPoly(b);
InitPoly(c);
int h1,h2,j,z;
double k;
double ra[50][2],rb[50][2];
cout<<"请输入b的项数,h1=: "<<endl;
cin>>h1;

for(z=0;z<h1;z++)
for(j=0;j<=1;j++){
cout<<"输入a或e";
cin>>k;
ra[z][j]=k;
}
cout<<"请输入c的项数,h2=: "<<endl;
cin>>h2;
for(z=0;z<h2;z++)
for(j=0;j<=1;j++){
cout<<"输入a或e";
cin>>k;
rb[z][j]=k;
}
int h3;
for(h3=0;h3<h1;h3++)
InsertPoly(b,ra[h3][0],ra[h3][1]);
for(h3=0;h3<h2;h3++)
InsertPoly(c,rb[h3][0],rb[h3][1]);
cout<<"线性表b：";
TraversePoly(b);
cout<<"线性表c：";
TraversePoly(c);
LNode *d=PolyAdd2(b,c);
cout<<"线性表d：";
TraversePoly(d);
ClearPoly(b);
ClearPoly(c);
ClearPoly(d);

}
else if(i==0)
exit(1);
else
cout<<"输入有误，请输入0-6"<<endl;

}

}
H：
struct term
{
double a;
double e;
};
typedef term ElemType;
struct LNode
{
ElemType data;
LNode *next;
};
void InitPoly(LNode *&HL)
{
LNode *newpter;
newpter=new LNode;
newpter->next=NULL;
HL=newpter;

}
void TraversePoly(LNode *HL)
{
if(HL->next==NULL)
cout<<"无多项式！"<<endl;
else
{
HL=HL->next;
while(HL->next!=NULL)
{
cout<<HL->data.a;
cout<<"X^";
cout<<HL->data.e;
cout<<"+";
HL=HL->next;
}
cout<<HL->data.a<<"X^"<<HL->data.e<<endl;

}
}
void ClearPoly(LNode *HL)
{
LNode *cp;
LNode *np;
cp=HL->next;
while(cp!=NULL)
{
np=cp->next;
delete cp;
cp=np;
}
HL->next=NULL;
cout<<"清除成功！"<<endl;

}
void InsertPoly(LNode *HL,double a,double e)
{
LNode *ap;
LNode *cp;
cp=HL;
ap=NULL;
LNode *newpter;
newpter=new LNode;
newpter->data.a=a;
newpter->data.e=e;
while(cp!=NULL)
{
if(e<cp->data.e)
break;
else
{
ap=cp;
cp=cp->next;
}
}
newpter->next=cp;
ap->next=newpter;

}
bool DeletePoly(LNode *&HL,double &a,double &e,int pos)
{
if(HL->next==NULL)
{
cout<<"无多项式！"<<endl;
return false;
}
if(pos<-1)
{
cerr<<"pos 值有错退出运行"<<endl;
return false;
}
LNode *cp=HL->next;
LNode *ap=HL;
if(pos==-1)
while(cp->next!=NULL)
{
ap=cp;
cp=cp->next;
}
else
{
int i=0;
while(cp!=NULL)
{
i++;
if(i==pos)
{
break;
}
else
{
ap=cp;
cp=cp->next;
}
}
if(cp==NULL)
{
cout<<"pos值无效！"<<endl;
return false;
}
}
a=cp->data.a;
e=cp->data.e;
ap->next=cp->next;
delete cp;
return true;

}
double PoluSum(LNode *HL,double x)
{
double sum;
sum=0;
while(HL->next!=NULL)
{
sum=sum+HL->data.a*pow(x,HL->data.e);
HL=HL->next;
}
sum=sum+HL->data.a*pow(x,HL->data.e);
return sum;
}
LNode *PolyAdd2(LNode *p1,LNode *p2)
{
LNode *p3;
p3=new LNode;
LNode *t1,*t2,*t3;
t1=p1;
t2=p2;
t3=p3;

while(t1&&t2)
{
if(t1->data.e<t2->data.e)
{
t3=t3->next=new LNode;
t3->data=t1->data;
t1=t1->next;
}
else if(t1->data.e> t2->data.e)
{
t3=t3->next=new LNode;
t3->data=t2->data;
t2=t2->next;

}
else
{
double a1=t1->data.a+t2->data.a;
if(a1!=0)
{
t3=t3->next=new LNode;
t3->data.a=a1;
t3->data.e=t1->data.e;
}
t1=t1->next;
t2=t2->next;
}
}
while(t1)
{
t3=t3->next=new LNode;
t3->data=t1->data;
t1=t1->next;
}
while(t2)
{
t3=t3->next=new LNode;
t3->data=t2->data;
t2=t2->next;
}
t3->next=NULL;
t3=p3;
p3=t3->next;
delete t3;
return p3;
}