数据结构课程设计__多项式运算
#include
#include
#include"malloc.h"
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define NULL 0
typedef int Status;
typedef struct ElemType{
float coef; //多项式系数
int exp; //多项式指数
}ElemType;//数据类型
typedef struct Polynomial{
ElemType data;
struct Polynomial *next;
}*Polyn,Polynomial;//多项式结构体
void Insert(Polyn p,Polyn head)
{ /*将新的结点插入链表, 如果系数为零，则释放该结点；
如果指数为新时将结点直接插入；否则查找插入位置， 方法：比较该结点指数与首元结点及其他结点的指数， 直到该结点指数大于等于链表内某结点的指数，相等则合并这两项；大于则插入到其前驱*/
if(p->data.coef==0) {free(p);p=NULL;} //如果插入项的系数为零时，释放其结点将其删除
else
{
Polyn q1,q2;
q1=head;
q2=head->next;
while(q2&& p->data.exp data.exp)
排列
q1=q2;
q2=q2->next;
} { //查找多项式某项的插入位置，使多项式按指数降幂
if(q2&& p->data.exp == q2->data.exp)
{ //将多项式指数相同相进行合并
q2->data.coef += p->data.coef;
free(p);
if(!q2->data.coef)
{ //如果多项式的系数为零的话，将其删除即释放期结点
q1->next=q2->next;
free(q2);
} }
else
{ //如果是新建的多项式，指数为新时将结点插入 p->next=q2;
q1->next=p;
} } }
Status CreatePolyn(Polyn &L,int m)
{ /*建立一个头指针为L, 项数为m 的一元多项式;
先建立一个头指针，再建立新结点来接收数据， 然后再调用Insert 函数插入结点*/
int i;
Polyn p;
L=(Polyn)malloc(sizeof(Polynomial));
if(!L)exit(OVERFLOW);
L->next=NULL;
for(i=1;i
{
p=(Polyn)malloc(sizeof(Polynomial)); //建立新结点以接收数据
if(!p)exit(OVERFLOW);
p->next=NULL; printf("请输入第%d项的系数与指数:",i); scanf("%f %d",&p->data.coef,&p->data.exp);
getchar();
Insert(p,L); //调用Insert 函数插入新建的结点
}
return OK;
}
void DestroyPolyn(Polyn p){ //销毁多项式p
Polyn q;
while(q=p->next)
{
p->next=q->next;
free(q);q=NULL;
}
free(p);p=NULL;
}
void PrintPolyn(Polyn P)// 输出多项式
{
Polyn q=P->next;
int flag=1; //项数计数器，用来判别第一项
if(!q)
{ //如果多项式为空链表，输出零
putchar('0');
printf("\n");
return;
}
while(q)
{
if(q->data.coef>0&& flag!=1) putchar('+'); //多项式系数大于0且不是第一项 if(q->data.coef!=1&&q->data.coef!=-1)
{ //多项式系数不是+1和-1的普通情况 printf("%g",q->data.coef);
if(q->data.exp==1) putchar('X'); //多项式系数不是1且指数为1时，输出X
else if(q->data.exp) printf("X^%d",q->data.exp); //多项式系数不是1且指数不为1，输出X 的指数次幂
}
else
{
if(q->data.coef==1) //多项式系数为1时
{
if(!q->data.exp) putchar('1'); //多项式指数为零时，直接输出1 else if(q->data.exp==1) putchar('X'); //多项式指数为1时，输出X else printf("X^%d",q->data.exp);
}
if(q->data.coef==-1) //多项式系数为-1时
{
if(!q->data.exp) printf("-1"); //多项式指数为零时，直接输出-1 else if(q->data.exp==1) printf("-X"); //多项式指数为1时，输出X else printf("-X^%d",q->data.exp);
} }
q=q->next;
flag++;
}
printf("\n");
}
Status AddPolyn(Polyn &pc,Polyn pa,Polyn pb){ //求解并建立多项式a+b，并用pc 带回多项式的和
Polyn qa=pa->next;
Polyn qb=pb->next;
Polyn hc,qc;
int j;
pc=(Polyn)malloc(sizeof(Polynomial)); //建立头结点
if(!pc)exit(OVERFLOW);
pc->next=NULL;
hc=pc;
while(qa||qb)//(while（qa&&qb）退出循环可以用hc=qa?qa:qb;),使用时对后面的减法造成影响
{
if(qa&&qb)
{
if(qa->data.exp>qb->data.exp) j=1; //a多项式某项指数大于b 多项式某项指数
else if(qa->data.expdata.exp) j=-1; //b多项式某项指数大于a 多项式某项指数
else j=0; //a多项式某项指数等于b 多项式某项指数 }
else if(!qa&&qb) j=-1; //a多项式已空，但b 多项式非空 else j=1; //b多项式已空，但a 多项式非空
qc=(Polyn)malloc(sizeof(Polynomial)); //建立新结点来存放两多项式相加和的某一项
if(!qc)exit(OVERFLOW); qc->next=NULL;
switch(j){
case 1: //a多项式某项指数大于b 多项式指数，则把其存入qc 内
{
qc->data.coef=qa->data.coef;
qc->data.exp=qa->data.exp;
qa=qa->next;
break;
}
case 0://两多项式两项指数相等，则把其和存入qc 内
{
qc->data.coef=qa->data.coef+qb->data.coef;
qc->data.exp=qa->data.exp;
qa=qa->next;
qb=qb->next;
break;
}
case -1: //b多项式某项指数大于a 多项式指数，则把其存入qc 内
{
qc->data.coef=qb->data.coef;
qc->data.exp=qb->data.exp;
qb=qb->next;
break;
} }
if(qc->data.coef!=0)// 产生的和项式插入链表pc 内
{
hc->next=qc;
hc=qc;
}
else free(qc); //当相加系数为零时，释放该结点
到hc
}
Status SubtractPolyn(Polyn &pd,Polyn pa,Polyn pb){ //求解并建立多项式a-b ，用pd 带回多项式的差
Polyn h=pb;
Polyn p=pb->next; return OK; } //hc->next=qa?qa:qb; //如果qa 或qb 空时，把另一个多项式剩余的项连接
while(p)
{ //将pb 的系数取反，调用加法的函数实现减法
p->data.coef*=-1;
p=p->next;
} AddPolyn(pd,pa,h); for(p=h->next;p;p=p->next) //为保证原多项式不变，恢复pb 的系数 p->data.coef*=-1;
return OK;
}
float ValuePolyn(Polyn p,float x){ //输入x 值，计算并返回多项式的值
Polyn q=p->next; //指针q 用来遍历p
int i;
float t; float sum=0;
while(q)
{
t=1;
i=q->data.exp;
while(i) //来计算X^i的值 {
if(i
else{t*=x;i--;} //如果指数大于0，则进行乘法
}
sum+=q->data.coef*t;
} q=q->next;
return sum;
}
Status DerivativePolyn(Polyn &hd,Polyn p){ //求解多项式的导函数，并用hd 带回求导后的结果
Polyn q=p->next,p1,p2;
hd=p1=(Polyn)malloc(sizeof(Polynomial));//建立头结点
if(!hd)exit(OVERFLOW);
hd->next=NULL;
while(q)
{
if(q->data.exp!=0)
{ //如果多项式该项不是常数项时，常数的话就不用参与下面的计算
p2=(Polyn)malloc(sizeof(Polynomial)); //开辟新的结点用来存放求导后的该项
if(!p2)exit(OVERFLOW); p2->next=NULL;
p2->data.coef=q->data.coef*q->data.exp; //求导后该项的系数=原项系数*原项指数
p2->data.exp=q->data.exp-1; //求导后该项的指数=原项指数-1
p1->next=p2;//将求导后的该项插入新链表
p1=p2;
}
q=q->next;
}
return OK;
}
Status MultiplyPolyn(Polyn &hf,Polyn pa,Polyn pb){ //求解多项式a*b，并用hf 带回乘积结果
Polyn pf;
Polyn qa=pa->next; //qa和qb 用来遍历多项式pa 和pb
Polyn qb=pb->next;
hf=(Polyn)malloc(sizeof(Polynomial));//建立头结点
if(!hf)exit(OVERFLOW);
hf->next=NULL;
while(qa) //利用两个循环让多项式pa 和pb 的任意两项相乘
{
for(qb=pb->next;qb;qb=qb->next)
{
pf=(Polyn)malloc(sizeof(Polynomial));
if(!pf)exit(OVERFLOW);
pf->next=NULL;
pf->data.coef=qa->data.coef*qb->data.coef; //系数相乘
pf->data.exp=qa->data.exp+qb->data.exp; //指数相乘
Insert(pf,hf); //调用Insert 函数以合并指数相同的项，并按降幂排序
} } qa=qa->next;
return OK;
}
Status Indefinite_integralPolyn(Polyn &hd, Polyn p){ //求解多项式的不定积分，并用hd 带回求导后的结果
Polyn q=p->next,p1,p2;
hd=p1=(Polyn)malloc(sizeof(Polynomial));//建立头结点
if(!hd)exit(OVERFLOW);
hd->next=NULL;
while(q)
{ if(q->data.exp==-1)//如果含有-1次方的多项式，积分会涉及到ln(x)，不好运算及存储，则直接默认积分结果为零
{ printf("\n本程序不能对含有-1次方的多项式积分！\n若还有-1次方，则积分结果默认为零！\n");
DestroyPolyn(hd);
hd=(Polyn)malloc(sizeof(Polynomial));//重新建立头结点，方便输出 if(!hd)exit(OVERFLOW);
hd->next=NULL;
} break;
p2=(Polyn)malloc(sizeof(Polynomial)); //建立新的结点来存放积分后某项的结果
if(!p2)exit(OVERFLOW); p2->next=NULL;
p2->data.coef=q->data.coef/(q->data.exp+1);//积分后该项的系数=原项的系数:(原项的指数+1)
p2->data.exp=q->data.exp+1; //积分后该项的指数=原项指数+1 p1->next=p2; //积分后该项的结果插入链表
p1=p2;
q=q->next;
}
} return OK;
double Definite_integralPolyn(Polyn p,float a,float b){ //求解多项式p 的定积分，并用e 带回求定积分的结果
double e=0;
Polyn q;
if(!p)exit(OVERFLOW);
if(!p->next) return 0; Indefinite_integralPolyn(q,p); //调用不定积分函数Indefinite_integralPolyn（），先计算多项式的不定积分
e=ValuePolyn(q,b)-ValuePolyn(q,a);//调用求值函数ValuePolyn ，计算定积分的值 return e;
}
void main()
{
int m,n,c=1;
float x,a,b; int temp;
double result_a=0,result_b=0;
Polyn pa=0,pb=0,pc;
printf(" ***************************************************\n"); printf(" * *\n");
printf(" * 数据结构课程设计 *\n");
printf(" * *\n");
printf(" ***************************************************\n");
printf(" * 姓名：XX *\n");
printf(" * 班级：2010级2班 *\n");
printf(" * 学号：XXXXXXX *\n");
printf(" * 专业：电子信息科学与技术 *\n");
printf(" * 题目：一元多项式运算器 *\n");
printf(" ***************************************************\n");
printf("首先创建两个一元多项式, 即多项式a 和b:\n"); printf("请输入a 的项数:");
scanf("%d",&m);
//getchar();
CreatePolyn(pa,m); //建立多项式a
printf("\n 多项式a=");
PrintPolyn(pa);
printf("\n");
printf("请输入b 的项数:");
scanf("%d",&n);
//getchar();
CreatePolyn(pb,n); //建立多项式b
printf("\n 多项式b="); PrintPolyn(pb);
printf("\n");
//输出菜单
printf(" **************************************************\n"); printf(" * 多项式操作菜单 *\n");
printf(" * *\n");
printf(" * 1:显示两个一元多项式 *\n"); printf(" * 2:求两个多项式的和即（a+b） *\n"); printf(" * 3:求两个多项式的差即（a-b ） *\n"); printf(" * 4:求两个多项式的积即（a*b） *\n"); printf(" * 5:带入X 求多项式的值 *\n");
printf(" * 6:对多项式求导计算 *\n"); printf(" * 7:对多项式不定定积分计算 *\n"); printf(" * 8:对多项式定积分计算 *\n"); printf(" * 9:销毁所创建的一元多项式 *\n");
printf(" * 10:重新创建两个一元多项式 *\n");
printf(" * 11:退出程序（并且销毁了多项式） *\n");
printf(" **************************************************\n");
while(c) {
printf("\n请选择操作：");
scanf(" %d",&temp);
getchar(); switch(temp) { case 1: { printf("\n 多项式a="); PrintPolyn(pa); printf("\n 多项式b="); PrintPolyn(pb); break; }
case 2:
{ AddPolyn(pc,pa,pb);
printf("\n a+b=");
PrintPolyn(pc);
}
case 3:
{ SubtractPolyn(pc,pa,pb);
printf("\n a-b=");
PrintPolyn(pc); break; }
case 4:
{ MultiplyPolyn(pc,pa,pb);
printf("\n a*b=");
PrintPolyn(pc); break; } case 5: { printf("对于多项式a, 输入x 求多项式的值!\n"); printf("输入x 的值：x="); scanf("%f",&x);
printf("\n x=%.3f时，
a=%.3f\n",x,ValuePolyn(pa,x));
printf("对于多项式b, 输入x 求多项式的值!\n"); printf("输入x 的值：x="); scanf("%f",&x);
printf("\n x=%.3f时，
b=%.3f\n",x,ValuePolyn(pb,x));
break;
case 6: { DerivativePolyn(pc,pa); printf("\n 多项式a 的导函数为：a'="); PrintPolyn(pc); DerivativePolyn(pc,pb); printf("\n 多项式b 的导函数为：b'="); PrintPolyn(pc); break; } case 7: {
Indefinite_integralPolyn(pc,pa); printf("\n 多项式a 的不定积分为：∫a="); PrintPolyn(pc); Indefinite_integralPolyn(pc,pb); printf("\n 多项式b 的不定积分为：∫b="); PrintPolyn(pc); break; } case 8: {
printf("请输入定积分的上下限：\n");
printf("请输入定积分的下限a=:");
scanf("%f",&a);
printf("请输入定积分的上限b=:");
scanf("%f",&b);
printf("定积分的区间为:[a,b]=[%f,%f]\n",a,b);
result_a=Definite_integralPolyn(pa,a,b); printf("\n 多项式a 的定积分结果为：result_∫a=");
result_b=Definite_integralPolyn(pb,a,b); printf("%f",result_a); b="); printf("\n 多项式b 的定积分结果为：result_∫printf("%f",result_b); break; } case 9: { printf("多项式a 和b 已被销毁！\n"); DestroyPolyn(pa);pa=NULL; DestroyPolyn(pb);pb=NULL; break; } case 10: { if(pa||pb) { printf("\n请先选择“9”销毁多项式a 和
b \n再选择“10”重新创建新的多项式\n");
break; } //DestroyPolyn(pa);
//DestroyPolyn(pb); printf("重新创建两个一元多项式, 即多项式a 和
b:\n");
printf("请输入a 的项数:");
scanf("%d",&m);
//getchar();
CreatePolyn(pa,m); //建立多项式a printf("请输入b 的项数:");
scanf("%d",&n);
//getchar();
CreatePolyn(pb,n); //建立多项式b
} break; case 11: { printf("\n 感谢使用多项式运算器！\n"); DestroyPolyn(pa); DestroyPolyn(pb); DestroyPolyn(pc);
c=0; } break;
default:
}
} } printf("\n 选择错误，请重新选择！\n");