实验一 一元多项式运算
实验一 一元多项式的运算
班级:计算机1405 组别:4 姓名:刘诚阳 学号:20143712
1. 问题定义及需求分析
1.1课题目的和任务
问题描述:设计一个一元多项式简单计算器。
实验要求:
1)采用顺序表或链表等数据结构。
2)输入并建立多项式。
3)输出运算结果的多项式。
1.2数据形式
输入数据形式:通过键盘输入。
输入值的范围:多项式的项数和指数的输入数据为int型,输入值范围为-32768至32767;多项式系数的输入值范围为float型,范围为
1.2e-38至3.4e+38。
输出数据形式:输出到显示器。
1.3程序功能
实现两个一元多项式之间的加法、减法和乘法运算。
1.4测试数据
4//第一个多项式的项数
1 4 //第一项的系数和指数
3 3 //第二项的系数和指数
-2 2 //第三项的系数和指数
6 0 //第四项的系数和指数
5 //第二个多项式的项数
-3 5 //第一项的系数和指数
2 2 //第二项的系数和指数
-6 0 //第三项的系数和指数
-1 -1 //第四项的系数和指数
1.2 -2 //第五项的系数和指数
2. 概要设计
2.1抽象数据类型
需要定义一个多项式类型的数据类型,里面包含一个int型的指数和一个float型的系数,再定义一个多项式节点,里面包含一个多项式类型的数
据,和一个指向下一个节点的指针。通过对多项式节点的操作,实现对输入
2.2
3. 详细设计
3.1存储结构实现
多项式结构体:
typedef struct{
float coef;
int expn;
}Poly;
typedef struct LNode{
Poly data;
struct LNode* next;
}LNode,*LinkList;
多项式类型的定义:
typedef LinkList polynomial;
3.2负责模块的伪码算法
(1)int MultiplyPolyn(polynomial& a,polynomial& b){//多项式相乘 if(a,b中均没有项){return 0;}
c=(polynomial)malloc(sizeof(LNode));//开辟一个c储存相乘结果 c->next=NULL;
ha=a->next;//ha为a中的项
hb=b->next;//hb为b中的项
for(;hb不空;下一项){//将a中第一项与b中所有项相乘 ha的系数*hb的系数;
ha的指数*hb的指数;
开辟一个新节点E,将数据存入,并把E连到c后
}
Sort(c);//对c中多项式排序
ha=ha->next;//ha指向下一个项
while(ha!=NULL){//将a中第二项与b中所有项相乘,存入d,然后将c和d相加得到新的c,再以此对a中其余各项做相同操作,最终得到乘法运算后的c
hb=b->next;//hb为b的第一项
d=(polynomial)malloc(sizeof(LNode));//开辟一个d储存相乘结果
d->next=NULL;
for(;hb不空;下一项){//将a中第一项与b中所有项相乘 ha的系数*hb的系数;
ha的指数*hb的指数;
开辟一个新节点E,将数据存入,并把E连到d后;
}
Sort(d);//对d中多项式排序
ha=ha->next;//ha指向下一项
AddPolyn(c,d);//将c,d相加得到新的c
}
t=a;
a=c;//a指向运算结果
DestroyPolyn(b);//销毁初始的两个多项式
DestroyPolyn(t);
}
(2)void DestroyPolyn(polynomial& L){//销毁多项式
while(L!=NULL){
p=L;
L=L->next;//指向后一项
free(p);
}
}
(3)void Sort(polynomial& L){//对多项式的指数进行冒泡排序 for(多项式长度){
for(j=L;j->next->next!=NULL;j=j->next){
if(j->next指数next->next指数){//将大的冒到前面 p=j->next;
q=j->next->next;
p->next=q->next;
q->next=p;
j->next=q;
}
}
}
}
4. 调试分析
4.1问题分析与解决方法
(1)多项式相乘
对于多项式相乘,考虑到两个一元多项式的相乘,可以利用两个一元多项式相加的算法来实现,因为乘法运算可以分解为一系列的加法运算,所以只需循环执行加法运算,就可以完成多项式的相乘。例如A(x)和B(x)为一元多项式,则有:
MxAxBx
ene1e1Axbxbxbx2n1
n
biAxxei
i1
其中,每一项都是一个一元多项式。
(2)销毁多项式
销毁多项式只需要判断多项式中的项是否为空,不为空就将指针后移,然后释放刚才的储存空间,当为空时结束循环。
(3)对多项式各项进行排序
通过冒泡排序实现多现实各项的指数的排序,冒泡排序的实现过程为:多项式中有多少项就进行多少次的排序,第一次排序遍历一遍所有项,进行比较大小,将最大的项调整到链表最前端,然后依次遍历,排完所有项。
4.2算法的时空分析
(1)多项式相乘
假设多项式a长度为m,多项式b长度为n,因为需要对两个表中的所有元素进行操作,所以时间复杂度为Omn,需要建立两个临时表c,d来存储运算数据,因此空间复杂度为On。
(2)销毁多项式
时间复杂度为On,空间复杂度为O1。
(3)冒泡排序
时间复杂度为On2,空间复杂度为O1。
4.3算法的改进设想
对于多项式中项的排序,可以采用更高效的排序算法来实现,因为输入多项式中不含有指数相同的项(指数相同的项在运算中会被合并),因此可以采用时间性能更好的快速排序来实现。
4.4经验和体会
在算法设计中,有很多问题是可以相互转化的,例如对于乘法运算的算法设计,因为乘法源自于加法,所以可以将求乘法的问题转化为求一系列加法的问题,从而使问题得到简化,更有利于解决。因此,在编程过程中,应当多注意事物之间的内在联系,从而抽丝剥茧,简化问题,有利于问题的求解。
5. 使用说明
按照屏幕提示,通过键盘输入数据,数据与数据之间用空格隔开,一组数据输入完毕后,回车结束。
6. 测试结果(截屏)
(1) 多项式相乘
(2)销毁多项式
销毁多项式只需要判断多项式中的项是否为空,不为空就将指针后移,然后释放刚才的储存空间,当为空时结束循环。
(3)对多项式各项进行排序
通过冒泡排序实现多现实各项的指数的排序,冒泡排序的实现过程为:多项式中有多少项就进行多少次的排序,第一次排序遍历一遍所有项,进行比较大小,将最大的项调整到链表最前端,然后依次遍历,排完所有项。
4.2算法的时空分析
(1)多项式相乘
假设多项式a长度为m,多项式b长度为n,因为需要对两个表中的所有元素进行操作,所以时间复杂度为Omn,需要建立两个临时表c,d来存储运算数据,因此空间复杂度为On。
(2)销毁多项式
时间复杂度为On,空间复杂度为O1。
(3)冒泡排序
时间复杂度为On2,空间复杂度为O1。
4.3算法的改进设想
对于多项式中项的排序,可以采用更高效的排序算法来实现,因为输入多项式中不含有指数相同的项(指数相同的项在运算中会被合并),因此可以采用时间性能更好的快速排序来实现。
4.4经验和体会
在算法设计中,有很多问题是可以相互转化的,例如对于乘法运算的算法设计,因为乘法源自于加法,所以可以将求乘法的问题转化为求一系列加法的问题,从而使问题得到简化,更有利于解决。因此,在编程过程中,应当多注意事物之间的内在联系,从而抽丝剥茧,简化问题,有利于问题的求解。
5. 使用说明
按照屏幕提示,通过键盘输入数据,数据与数据之间用空格隔开,一组数据输入完毕后,回车结束。
6. 测试结果(截屏)
(1) 多项式相乘
(2) 多项式排序(冒泡排序)
7. 附录
7.1个人负责模块的程序代码
int MultiplyPolyn(polynomial& a,polynomial& b){//多项式相乘
//将a的每项分别和b所有项相乘,再将它们相加
void Sort(polynomial& L);//函数声明
void DestroyPolyn(polynomial& );
polynomial ha=NULL,hb=NULL,c=NULL;
Poly e;
if(a->next==NULL||b->next==NULL){return 0;}//若多项式中无项,则返回 c=(polynomial)malloc(sizeof(LNode));//开辟c,存储第一次运算结果
c->next=NULL;
ha=a->next;
hb=b->next;
for(;hb!=NULL;hb=hb->next){//将b中每项都与a的第一项相乘
e.coef=(ha->data.coef)*(hb->data.coef);
e.expn=(ha->data.expn)+(hb->data.expn);
polynomial E=NULL;
E=(polynomial)malloc(sizeof(LNode));
E->data.coef=e.coef;
E->data.expn=e.expn;
E->next=c->next;
c->next=E;//将每项结果保存在c中
}
Sort(c);//对c中项的指数进行排序处理
ha=ha->next;//指向下一项
while(ha!=NULL){//将a中其余各项分别与b中各项相乘
hb=b->next;
polynomial d;
d=(polynomial)malloc(sizeof(LNode));
d->next=NULL;
for(;hb!=NULL;hb=hb->next){//用d储存a中后一项和b中所有项的乘积 e.coef=(ha->data.coef)*(hb->data.coef);
e.expn=(ha->data.expn)+(hb->data.expn);
polynomial E=NULL;
E=(polynomial)malloc(sizeof(LNode));
E->data.coef=e.coef;
E->data.expn=e.expn;
E->next=d->next;
d->next=E;
}
Sort(d);
ha=ha->next;
AddPolyn(c,d);//将c,d两项相加,得到合并后的c
}
polynomial t=a;
a=c;
DestroyPolyn(b);//销毁临时存储空间
DestroyPolyn(t);
return 1;
}
void DestroyPolyn(polynomial& L){//销毁线性表
while(L!=NULL){
polynomial p;
p=L;
L=L->next;
free(p);
}
}
void Sort(polynomial& L){//冒泡排序
polynomial i,j;
for(i=L;i->next!=NULL;i=i->next){//总次数
for(j=L;j->next->next!=NULL;j=j->next){//第一趟
if(j->next->data.expnnext->next->data.expn){
//比较大小,将大的冒到前面
polynomial p,q;
p=j->next;
q=j->next->next;
p->next=q->next;
q->next=p;
j->next=q;
}
}
}
}
7.2程序全部代码
#include
#include
#include
#define TRUE 1;
#define FALSE 0;
using namespace std;
typedef struct{
float coef;
int expn;
}Poly;
typedef struct LNode{
Poly data;
struct LNode* next;
}LNode,*LinkList;
typedef LinkList polynomial;
int main(){//主函数
//函数声明
void CreatPolyn(polynomial& ,int );
void DestroyPolyn(polynomial& );
void const PrintPolyn(polynomial );
int AddPloyn(polynomial& ,polynomial& );
int SubtractPloyn(polynomial& ,polynomial& );
int MultiplyPloyn(polynomial& ,polynomial& );
void Menu(polynomial& ,polynomial& );
//定义
int n=1;
while(n>=0){
polynomial a;
polynomial b;
system("cls");
printf("请输入第一个多项式的项数(输入负数退出):"); scanf("%d",&n);
if(n
CreatPolyn(a,n);
PrintPolyn(a);
printf("请输入第二个多项式的项数(输入负数退出):"); scanf("%d",&n);
if(n
CreatPolyn(b,n);
PrintPolyn(b);
//菜单
Menu(a,b);
//销毁线性表
DestroyPolyn(a);
}
return 0;
}
void Menu(polynomial& a,polynomial& b){//菜单
int AddPolyn(polynomial& ,polynomial& );
int SubtractPolyn(polynomial& ,polynomial& );
int MultiplyPolyn(polynomial& ,polynomial& );
void const PrintPolyn(polynomial );
int n=0;
printf("1.多项式相加\n2.多项式相减\n3.多项式相乘\n"); scanf("%d",&n);
switch(n){
case 1:AddPolyn(a,b);
printf("Answer= ");
PrintPolyn(a);
system("pause");
break;
case 2:SubtractPolyn(a,b);
printf("Answer= ");
PrintPolyn(a);
system("pause");
break;
case 3:if(MultiplyPolyn(a,b)){
printf("Answer= ");
PrintPolyn(a);
}
else printf("Answer= 0\n");
system("pause");
break;
default:break;
}
}
void CreatPolyn(polynomial& L,int n){//创建多项式
void Sort(polynomial& L);
L=(polynomial)malloc(sizeof(LNode));
L->next=NULL;
Poly e;
int i=1;
for(;n>0;n--,i++){
printf("请输入第%d",i);
printf("项的系数和指数:");
scanf("%f%d",&e.coef,&e.expn);
polynomial E=NULL;
E=(polynomial)malloc(sizeof(LNode));
E->data.coef=e.coef;
E->data.expn=e.expn;
E->next=L->next;
L->next=E;
}
Sort(L);
}
int SubtractPolyn(polynomial &Pa,polynomial &Pb){//多项式减法:Pa=Pa-Pb polynomial ha=NULL,hb=NULL,p=NULL;
ha=Pa;
hb=Pb;
if(ha->next==NULL){
Pa=Pb;
free(ha);
return 0;
}
else{
while(hb->next!=NULL)
{
if(ha->next->data.expnnext->data.expn){
polynomial p,q;
p=hb->next;
q=p->next;
p->data.coef=0-p->data.coef;
p->next=ha->next;
ha->next=p;
hb->next=q;
ha=ha->next;
}
else if(ha->next->data.expn==hb->next->data.expn){
ha->next->data.coef=ha->next->data.coef-hb->next->data.coef; p=hb->next;
hb->next=hb->next->next;
free(p);
}
else{
ha=ha->next;
if(ha->next==NULL){
hb->next->data.coef=0-hb->next->data.coef; ha->next=hb->next;
hb->next=NULL;
free(hb);
}
}
}
}
return 0;
}
void const PrintPolyn(polynomial P)
//输出多项式
{
polynomial a;
a=P->next;
//开始输出
while(a->next)
{
printf("%gx^%d +",a->data.coef,a->data.expn);
a=a->next;
}
//输出最后一个
printf("%gx^%d\n",a->data.coef,a->data.expn);
}
int AddPolyn(polynomial &Pa,polynomial &Pb)
//多项式加法:Pa=Pa+Pb
{
polynomial ha=NULL,hb=NULL,p=NULL;
ha=Pa;
hb=Pb;
if(ha->next==NULL){
Pa=Pb;
free(ha);
return 0;
}
else{
while(hb->next!=NULL)
{
if(ha->next->data.expnnext->data.expn){
polynomial p,q;
p=hb->next;
q=p->next;
p->next=ha->next;
ha->next=p;
hb->next=q;
ha=ha->next;
}
else if(ha->next->data.expn==hb->next->data.expn){
ha->next->data.coef=ha->next->data.coef+hb->next->data.coef; p=hb->next;
hb->next=hb->next->next;
free(p);
}
else{
ha=ha->next;
if(ha->next==NULL){
ha->next=hb->next;
hb->next=NULL;
free(hb);
}
}
}
}
} return 0;
int MultiplyPolyn(polynomial& a,polynomial& b){//多项式相乘 void Sort(polynomial& L);
void DestroyPolyn(polynomial& );
polynomial ha=NULL,hb=NULL,c=NULL;
Poly e;
if(a->next==NULL||b->next==NULL){return 0;}
c=(polynomial)malloc(sizeof(LNode));
c->next=NULL;
ha=a->next;
hb=b->next;
for(;hb!=NULL;hb=hb->next){
e.coef=(ha->data.coef)*(hb->data.coef);
e.expn=(ha->data.expn)+(hb->data.expn); polynomial E=NULL;
E=(polynomial)malloc(sizeof(LNode));
E->data.coef=e.coef;
E->data.expn=e.expn;
E->next=c->next;
c->next=E;
}
Sort(c);
ha=ha->next;
while(ha!=NULL){
hb=b->next;
polynomial d;
d=(polynomial)malloc(sizeof(LNode)); d->next=NULL;
for(;hb!=NULL;hb=hb->next){
e.coef=(ha->data.coef)*(hb->data.coef); e.expn=(ha->data.expn)+(hb->data.expn); polynomial E=NULL;
E=(polynomial)malloc(sizeof(LNode)); E->data.coef=e.coef;
E->data.expn=e.expn;
E->next=d->next;
d->next=E;
}
Sort(d);
ha=ha->next;
AddPolyn(c,d);
}
polynomial t=a;
a=c;
DestroyPolyn(b);
DestroyPolyn(t);
return 1;
}
void DestroyPolyn(polynomial& L){//销毁线性表
while(L!=NULL){
polynomial p;
p=L;
L=L->next;
free(p);
}
}
void Sort(polynomial& L){//冒泡排序
polynomial i,j;
for(i=L;i->next!=NULL;i=i->next){
for(j=L;j->next->next!=NULL;j=j->next){
if(j->next->data.expnnext->next->data.expn){ polynomial p,q;
p=j->next;
q=j->next->next;
p->next=q->next;
q->next=p;
j->next=q;
}
}
}
}