第1个回答 2013-06-30
大一上数据结构的时候写的：
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#include <conio.h>
typedef struct Item{
double coef;
int expn;
struct Item *next;
}Item,*Polyn;
#define CreateItem(p) p=(Item *)malloc(sizeof(Item));
#define DeleteItem(p) free((void *)p);
/************************************************************/
/*判断选择函数
*/
/************************************************************/
int Select(char *str)
{ char ch;
printf("%s\n",str);
printf("Input Y or N:");
do{ ch=getch();
}while(ch!='Y'&&ch!='y'&&ch!='N'&&ch!='n');
printf("\n");
if(ch=='Y'||ch=='y') return(1);
else return(0);
}
/************************************************************/
/*插入位置定位函数 */
/**************************************************************/
int InsertLocate(Polyn h,int expn,Item **p)
{ Item *pre,*q;
pre=h;
q=h->next;
while(q&&q->expn<expn)
{ pre=q;
q=q->next;
}
if(!q)
{ *p=pre;
return(1);
}
else if(q->expn==expn)
{ *p=q;
return(0);
}
else
{ *p=pre;
return(-1);
}
}
/************************************************************/
/*插入结点函数
*/
/************************************************************/
void insert(Item *pre,Item *p)
{
p->next=pre->next;
pre->next=p;
}
/************************************************************/
/*输入多项式 */
/************************************************************/
Polyn Input(void)
{
double coef;
int expn,flag;
Item *h,*p,*q,*pp;
CreateItem(h);//产生头结点
h->next=NULL;
printf("input coef and expn(if end ,expn=-1)\n");
while(1)
{
scanf("%lf%d",&coef,&expn); //输入多项式的系数和指数
if(expn==-1) break; //若指数为－1，表示输入结束
if(InsertLocate(h,expn,&pp))//返回值非 0表示插入新结点
{ CreateItem(p);
p->coef=coef;
p->expn=expn;
insert(pp,p);
}
else if(Select("has the same expn,Replace older value?"))
pp->coef=coef; //指数相同，替换系数
}
return h;
}
/************************************************************/
/*撤消多项式 */
/************************************************************/
void Destroy(Polyn h)
{
Item *p=h,*q;
while(p!=NULL)
{
q=p;
p=p->next;
DeleteItem(q);
}
}
/************************************************************/
/*输出多项式 */
/************************************************************/
void Output(Polyn h,char *title)
{
int flag=1;
Item *p=h->next;
printf("%s=",title);
while(p)
{ if(flag) //表示是否是多项式的第一项
{ flag=0;
if(p->expn==0) printf("%.2lf",p->coef);
else printf("%.2lfx^%d",p->coef,p->expn);
}
else
{ if(p->coef>0) printf("+");
if(p->expn==0) printf("%.2lf",p->coef);
else printf("%.2lfx^%d",p->coef,p->expn);
}
p=p->next;
}
printf("\n");
}
/************************************************************/
/*判断两个多项式项的关系 */
/************************************************************/
int ItemComp(Item x,Item y)
{ if(x.expn<y.expn)
return(-1);
else if(x.expn==y.expn)
return(0);
else return(1);
}
/************************************************************/
/*两多项式多项式相加
*/
/************************************************************/
Polyn AddPolyn(Polyn h1,Polyn h2)
{
Item *head,*last,*pa=h1->next,*pb=h2->next,*s,*s0;
double coef;
CreateItem(head);
last=head;
head->next=NULL;
while(pa && pb)
{
switch(ItemComp(*pa,*pb))
{
case -1:
CreateItem(s);
*s=*pa;
pa=pa->next;
s->next=NULL;
break;
case 0:
coef=pa->coef+pb->coef;
if(coef!=0.0)
{
CreateItem(s);
s->coef=coef;
s->expn=pa->expn;
s->next=NULL;
}
pa=pa->next;
pb=pb->next;
break;
case 1:
CreateItem(s);
*s=*pb;
pb=pb->next;
s->next=NULL;
break;
}
if(head->next==NULL)
{
insert(head,s);
last=s;
}
else
{
insert(last,s);
last=s;
}
}
// last->next=pa?pa:pb;
//实现两个多项式相加运算的代码
//（由学生独立完成）
last->next=NULL;
return head;
}
/************************************************************/
/*两多项式多项式相减
*/
/************************************************************/
Polyn SubtractPolyn(Polyn h1,Polyn h2)
{ int flag;
Item *head,*last,*pa=h1->next,*pb=h2->next,*s,*s0;
double coef;
int a,b;
CreateItem(head);
last=head;
while(pa&&pb)
{
a=pa->expn;
b=pb->expn;
switch(ItemComp(*pa,*pb))
{
case -1:
CreateItem(s);
*s=*pa;
/* //insert(s,s0);
* //s=s->next;
*/
pa=pa->next;
s->next=NULL;
break;
case 0:
coef=pa->coef-pb->coef;
if(coef!=0.0)
{
CreateItem(s);
s->coef=coef;
s->expn=pa->expn;
/* //insert(s,s0); */
s->next=NULL;
/* //s=s->next; */
}
pa=pa->next;
pb=pb->next;
break;
case 1:
CreateItem(s);
*s=*pb;
s->coef=-1*s->coef;
/* //insert(s,s0);
* //s=s->next;
*/
pb=pb->next;
s->next=NULL;
break;
}
if(head->next==NULL)
{
insert(head,s);
last=s;
}
else
{
insert(last,s);
last=s;
}
}
if(pa)
last->next=pa;
else
{
last->next=pb;
while(pb)
{
pb->coef*=-1;
pb=pb->next;
}
}
//实现两个多项式相减运算的代码
//（由学生独立完成）
last->next=NULL;
return head;
}
/************************************************************/
/*两多项式多项式相乘
*/
/************************************************************/
Polyn MultPolyn(Polyn h1,Polyn h2) //两个多项式相乘
{ int item,expn;
Item *head,*pa,*pb=h2->next,*s,*pp;
double coef;
CreateItem(head);
head->next=NULL;
CreateItem(pp);
pp->next=NULL;
for(;pb;pb=pb->next)
{
for(pa=h1->next;pa;pa=pa->next)
{
CreateItem(s);
pp->next=s;
s->coef=pa->coef*pb->coef;
s->expn=pa->expn+pb->expn;
s->next=NULL;
head=AddPolyn(pp,head);
}
}
//实现两个多项式相乘运算的代码
//（由学生独立完成）
return head;
}
/************************************************************/
/*菜单选择 */
/************************************************************/
int menu(void)
{ int num;
//clrscr();
printf("%20c1--create P(x)\n",' ');
printf("%20c2--create Q(x)\n",' ');
printf("%20c3--p(x)+Q(x)\n",' ');
printf("%20c4--P(x)-Q(x)\n",' ');
printf("%20c5--p(x)*Q(x)\n",' ');
printf("%20c6--print P(x)\n",' ');
printf("%20c7--print Q(x)\n",' ');
printf("%20c8--print P(x)+Q(x)\n",' ');
printf("%20c9--print P(x)-Q(x)\n",' ');
printf("%20c10--print P(x)*Q(x)\n",' ');
printf("%20c11--Quit\n",' ');
printf(" please select 1,2,3,4,5,6,7,8,9,10,11:");
do{
scanf("%d",&num);
}while(num<1 || num>11);
return(num);
}
/************************************************************/
/*判断多项式是否存在 */
/************************************************************/
int PolynNotEmpty(Polyn h,char *p)
{ if(h==NULL)
{ printf("%s is not exist!\n",p);
getchar();
return(0);
}
else return(1);
}
/************************************************************/
/*主函数 */
/************************************************************/
void main()
{ int num;
Polyn h1=NULL; //p(x)
Polyn h2=NULL; //Q(x)
Polyn h3=NULL; //P(x)+Q(x)
Polyn h4=NULL; //P(x)-Q(x)
Polyn h5=NULL; //P(x)*Q(x)
while(1)
{ num=menu();
getchar();
switch(num)
{
case 1: //输入第一个多项式，若多项式存在，首先撤消然后再输入
if(h1!=NULL)
{ if(Select("P(x) is not Empty,Create P(x) again?"))
{ Destroy(h1);
h1=Input();
}
}
else h1=Input();
break;
case 2: //输入第二个多项式，若多项式存在，首先撤消然后再输入
if(h2!=NULL)
{ if(Select("Q(x) is not Empty,Create Q(x) again?"))
{ Destroy(h2);
h2=Input();
}
}
else h2=Input();
break;
case 3: //两多项式相加
if(PolynNotEmpty(h1,"p(x)")&&PolynNotEmpty(h2,"Q(X)"))
{h3=AddPolyn(h1,h2);
Output(h3,"P(x)+Q(X)");
printf("P(x)+Q(x) has finished!\n");
getchar();
}
break;
case 4: //两多项式相减
if(PolynNotEmpty(h1,"p(x)")&&PolynNotEmpty(h2,"Q(X)"))
{ h4=SubtractPolyn(h1,h2);
Output(h4,"Px)-Q(x)");
printf("P(x)-Q(x) has finished!\n");
getchar();
}
break;
case 5: //两多项式相乘
if(PolynNotEmpty(h1,"p(x)")&&PolynNotEmpty(h2,"Q(X)"))
{ h5=MultPolyn(h1,h2);
Output(h5,"P(x)*Q(x)");
printf("P(x)*Q(x) has finished!\n");
getchar();
}
break;
case 6: //显示第一个多项式
if(PolynNotEmpty(h1,"p(x)"))
{ Output(h1,"P(x)");
getchar();
}
break;
case 7: //显示第二个多项式
if(PolynNotEmpty(h2,"Q(x)"))
{ Output(h2,"Q(x)");
getchar();
}
break;
case 8: //显示相加结果多项式
if(PolynNotEmpty(h3,"P(x)+Q(x)"))
{ Output(h3,"P(x)+Q(x)");
getchar();
}
break;
case 9: //显示相减结果多项式
if(PolynNotEmpty(h4,"P(x)-Q(x)"))
{ Output(h3,"P(x)-Q(x)");
getchar();
}
break;
case 10: //显示相乘结果多项式
if(PolynNotEmpty(h5,"P(x)*Q(x)"))
{ Output(h3,"P(x)*Q(x)");
getchar();
}
break;
case 11: //结束程序运行。结束前应先撤消已存在的多项式
if(h1!=NULL) Destroy(h1);
if(h2!=NULL) Destroy(h2);
if(h3!=NULL) Destroy(h3);
if(h4!=NULL) Destroy(h4);
if(h4!=NULL) Destroy(h4);
if(h4!=NULL) Destroy(h5);
}
if(num==11) break;
}
}