数据结构上机实验报告2
一．实验目的
设计一个一元稀疏多项式简单计算器
二．实验内容
（1）输入并建立多项式；
（2）输出多项式，输出形式为整数序列：n,c1,e1, c2,e2,,,,,,, cn,en,其中n是多项式的项数，ci,ei,分别是第i项的系数和指数，序列按指数降序排序；
（3）多项式a和b相加，建立多项式a+b；
（4）多项式a和b相减，建立多项式a-b；
（5）计算多项式在x处的值。
（6）计算器的仿真界面。
三．实验步骤（可选）
详细设计代码：#include<iostream.h>
#include <stdlib.h>
#include <math.h>
typedef struct Polynomial{
int coe; //系数
int exp;//指数
struct Polynomial *next;
}*Polyn,Polynomial;
Polyn ma,mb;
void Insert(Polyn p,Polyn h)
{
if(p->coe==0) delete p;
else{
Polyn q1,q2;
q1=h;q2=h->next;
while(q2&&p->exp<q2->exp)
{
q1=q2;
q2=q2->next;
}
if(q2&&p->exp==q2->exp)
{
q2->coe+=p->coe;
delete p;
if(!q2->coe)
{
q1->next=q2->next;
delete q2;}
}
else
{
p->next=q2;
q1->next=p;
}
}
}
Polyn CreatePolyn(Polyn head,int m)
{
int i;
Polyn p;
p=head=new Polynomial;
head->next=NULL;
for(i=0;i<m;i++){
p=new Polynomial;;
cout<<"请输入第"<<i+1<<"项的系数:";
cin>>p->coe;
cout<<" 指数:";
cin>>p->exp;
Insert(p,head);
}
return head;
}
void DestroyPolyn(Polyn p)
{
Polyn t;
while(p!=NULL)
{
t=p;
p=p->next;
delete t;
}
}
void PrintPolyn(Polyn Pm)
{
Polyn qa=Pm->next;
int flag=1;
if(!qa)
{
cout<<"0";
cout<<endl;
return;
}
while (qa)
{
if(qa->coe>0&&flag!=1) cout<<"+";
if(qa->coe!=1&&qa->coe!=-1)
{
cout<<qa->coe;
if(qa->exp==1) cout<<"X";
else if(qa->exp) cout<<"X^"<<qa->exp;
}
else
{
if(qa->coe==1)
{
if(!qa->exp) cout<<"1";
else if(qa->exp==1) cout<<"X";
else cout<<"X^"<<qa->exp;
}
if(qa->coe==-1)
{
if(!qa->exp) cout<<"-1";
else if(qa->exp==1) cout<<"-X";
else cout<<"-X^"<<qa->exp;
}
}
qa=qa->next;
flag++;
}
cout<<endl;
}
int compare(Polyn a,Polyn b)
{
if(a&&b)
{
if(!b||a->exp>b->exp) return 1;
else if(!a||a->exp<b->exp) return -1;
else return 0;
}
else if(!a&&b) return -1;
else return 1;
}
Polyn AddPolyn(Polyn pa,Polyn pb)
{
Polyn qa=pa->next;
Polyn qb=pb->next;
Polyn headc,hc,qc;
hc=new Polynomial;
hc->next=NULL;
headc=hc;
while(qa||qb)
{
qc=new Polynomial;
switch(compare(qa,qb))
{
case 1:
{
qc->coe=qa->coe;
qc->exp=qa->exp;
qa=qa->next;
break;
}
case 0:
{
qc->coe=qa->coe+qb->coe;
qc->exp=qa->exp;
qa=qa->next;
qb=qb->next;
break;
}
case -1:
{
qc->coe=qb->coe;
qc->exp=qb->exp;
qb=qb->next;
break;
}
}
if(qc->coe!=0)
{
qc->next=hc->next;
hc->next=qc;
hc=qc;
}
else delete qc;
}
return headc;
}
Polyn SubtractPolyn(Polyn pa,Polyn pb)
{
Polyn h=pb;
Polyn p=pb->next;
Polyn pd;
while(p)
{
p->coe*=-1;
p=p->next;
}
pd=AddPolyn(pa,h);
for(p=h->next;p;p=p->next)
p->coe*=-1;
return pd;
}
Polyn MultiplyPolyn(Polyn pa,Polyn pb)
{
Polyn hf,pf;//
Polyn qa=pa->next; //新建一个结点作为pa的后继结点
Polyn qb=pb->next; //新建一个结点作为pb的后继结点
hf=new Polynomial;
hf->next=NULL;
while(qa)//使用while循环，使得多项式的每项得以运算
{
qb=pb->next;
while(qb)
{
pf=new Polynomial;
pf->coe=qa->coe*qb->coe;
pf->exp=qa->exp+qb->exp;
Insert(pf,hf);//调用插入函数，将新的结点插入到新建链表中，并合并同类项
qb=qb->next;
}
qa=qa->next;
}
return hf;//返回所得链表的头指针
}
void DevicePolyn(Polyn pa,Polyn pb)
{
Polyn quotient,remainder,temp1,temp2;
Polyn qa=pa->next;
Polyn qb=pb->next;
quotient=new Polynomial; //建立头结点,存储商
quotient->next=NULL;
remainder=new Polynomial; //建立头结点，存储余数
remainder->next=NULL;
temp1=new Polynomial;
temp1->next=NULL;
temp2=new Polynomial;
temp2->next=NULL;
temp1=AddPolyn(temp1,pa);
while(qa!=NULL&&qa->exp>=qb->exp)
{
temp2->next=new Polynomial;
temp2->next->coe=(qa->coe)/(qb->coe);
temp2->next->exp=(qa->exp)-(qb->exp);
Insert(temp2->next,quotient);
pa=SubtractPolyn(pa,MultiplyPolyn(pb,temp2));
qa=pa->next;
temp2->next=NULL;
}
remainder=SubtractPolyn(temp1,MultiplyPolyn(quotient,pb));
pb=temp1;
cout<<endl<<"shang"<<endl;//printf("\t商：");
PrintPolyn(quotient);
cout<<"yushu"<<endl;//printf("\t余数：");
PrintPolyn(remainder);
}
float ValuePolyn(Polyn head,float x)
{
Polyn p;
p=head->next;
float result=0;
while(p!=NULL)
{
result+=(p->coe)*(float)pow(x,p->exp);
p=p->next;
}
return result;
}
void desktop()
{
system("cls");
cout<<endl<<endl<<endl<<" 一元稀疏多项式的计算"<<endl;
cout<<" ————————————————————————"<<endl;
cout<<" + 1output多项式a和b +"<<endl;
cout<<" + 2build多项式a+b +"<<endl;
cout<<" + 3build多项式a-b +"<<endl;
cout<<" + 4build多项式a*b +"<<endl;
cout<<" + 5build多项式a/b +"<<endl;
cout<<" + 6circulate多项式a的值 +"<<endl;
cout<<" + 7back to system +"<<endl;
cout<<" ———————————————————————— "<<endl<<endl;
cout<<" execute operation:";
}
void input(){
int m,n;
//Polyn pa,pb;
cout<<"please input多项式a的项数:";
cin>>m;
ma=CreatePolyn(ma,m);
cout<<endl;
cout<<"please input多项式b的项数:";
cin>>n;
mb=CreatePolyn(mb,n);}
void main()
{
//int m,n;
float x,result;
char key;
//Polyn pa,pb;
cout<<endl<<endl<<endl<<endl<<" Welcome to use！"<<endl;
cout<<" please wait a minute ..."<<endl;
_sleep(3*1000);
system("cls");
while(key)
{
desktop();
cin>>key;
switch (key)
{
case'1':input();
cout<<"多项式a：";
PrintPolyn(ma);
cout<<"多项式b：";
PrintPolyn(mb);
break;
case'2':input();
//pc=AddPolyn(pa,pb);
cout<<"多项式a：";
PrintPolyn(ma);
cout<<"多项式b：";
PrintPolyn(mb);
cout<<"多项式a+b：";
PrintPolyn(AddPolyn(ma,mb));
//DestroyPolyn(pc);
break;
case'3':input();
//pd=SubtractPolyn(pa,pb);
cout<<"多项式a：";
PrintPolyn(ma);
cout<<"多项式b：";
PrintPolyn(mb);
cout<<"多项式a-b：";
PrintPolyn(SubtractPolyn(ma,mb));
//DestroyPolyn(pd);
break;
case'4':input();
//pd=SubtractPolyn(pa,pb);
cout<<"多项式a：";
PrintPolyn(ma);
cout<<"多项式b：";
PrintPolyn(mb);
cout<<"多项式a*b：";
PrintPolyn(MultiplyPolyn(ma,mb));
//DestroyPolyn(pd);
break;
case'5':input();
//pd=SubtractPolyn(pa,pb);
cout<<"多项式a：";
PrintPolyn(ma);
cout<<"多项式b：";
PrintPolyn(mb);
cout<<"多项式a/b：";
DevicePolyn(ma,mb);
//DestroyPolyn(pd);
break;
case'6':input();
cout<<"多项式a：";
PrintPolyn(ma);
cout<<"输入x的值：x=";
cin>>x;
result=ValuePolyn(ma,x);
cout<<"多项式a的值:"<<result<<endl;
break;
case'7':
DestroyPolyn(ma);
DestroyPolyn(mb);
exit(0);
break;
default:
cout<<"Error!!!"<<endl;
}
cout<<endl<<endl;
system("pause");
}
}
四．实验的结果及分析。
实验输出值满足预期。
五．实验中出现的问题、解决方法和心得体会
实验中增添了计算多项式在x处的值，以及建立计算器的仿真界面。
-
数据结构上机实验报告
实验一线性表的基本操作实验目的学习掌握线性表的顺序存储结构链式存储结构的设计与操作对顺序表建立插入删除的基本操作对单链表建立插入删…
-
数据结构上机实验答案
数据结构实验指导书答案实验一1请编写函数intfunintaintb函数的功能是判断两个指针a和b所指存储单元的值的符号是否相同若…
-
数据结构上机实验报告
空间数据结构基础上机实验报告20xx姓名班级地信121学号07122857环境与测绘学院级实验报告1C面向对象程序设计范例1二维坐…
-
数据结构第一次上机实验报告
数据结构第一次上机实验报告线性表实验要求1实现顺序表结构的创建插入删除查找等操作2利用上述顺序表操作实现如下程序建立两个顺序表表示…
-
数据结构上机实验报告
计算机科学与技术学院数据结构教程实验报告20xx20xx学年第2学期学生姓名学生专业学生班级学生学号20xx65实验报告一设计人员…
-
数据结构上机实验报告7
一．实验目的文本编辑程序是利用计算机进行文字加工的基本软件工具，实现对文本文件的插入、删除等修改操作。二．实验内容被编译的文本文件…
- 《数据结构》上机实验报告—常用排序算法的实现
-
数据结构上机实验报告
实验一线性表的基本操作实验目的学习掌握线性表的顺序存储结构链式存储结构的设计与操作对顺序表建立插入删除的基本操作对单链表建立插入删…
-
数据结构实验报告34354
合肥师范学院实验报告册20xx20xx学年第2学期系别实验课程专业班级姓名学号指导教师计算机科学与技术系数据库原理计算机软件12级…
-
数据结构实验报告
数据结构实验报告实验序号3实验项目名称链式表的操作附源程序清单includequotstdiohquotincludequotst…
-
java上机实验心得体会报告
北京联合大学信息学院“面向对象程序设计”课程上机实验报告题目：JAVA上机实验心得体会姓名（学号）：专业：计算机科学与技术编制时间…