main.cpp

设计一个一元稀疏多项式简单计算机器 1. 本演示程序中

#include<stdio.h>
#include<malloc.h>
#include<math.h>

typedef struct{
	float ceof;
	int expn;
}ElemType;

typedef struct LNode{
ElemType e;
struct LNode *next;
}*Link;

typedef struct{
Link head;
int len;
}LinkList;

typedef LinkList polynomail;


int cmp(ElemType &e,ElemType &e1){
if(e.expn>e1.expn)return 1;
else if(e.expn==e1.expn)return 0;
else return -1;
}//比较函数cmp


void InsFirst(Link &p,Link &s){
s->next=p->next;
p->next=s;
}//在p后插入结点函数InsFirst

int LocateElem(polynomail &P,ElemType &e,Link &q){
//若中存在与e满足判定函数cmp（）的取值为0的元素，则q指示P中的第一个值为
//e的结点的位置，并返回TRUE；否则，q指示第一个满足取值〈0的元素的前驱位
//置，并返回FALSE。
Link pre;
pre=P.head;q=pre->next;
do{
	if(cmp(e,q->e)==0){
		printf("error:can't input the same expn for second time!");
	return true;
	}
	else if(cmp(e,q->e)==-1){
		if(q->next==NULL){return false;
		break;}
		else{pre=q;q=q->next;}
	}
	else{q=pre;return false;}
}while(1);
}//LocateElem

int MakeNode(Link &s,ElemType &e){
s=(struct LNode *)malloc(sizeof(struct LNode));
if(s==NULL)return false;
(s->e).ceof=e.ceof;(s->e).expn=e.expn;
return true;
}//MakeNode

void CreatePolyn(polynomail &P,int &m){
//输入链表的共m项的系数与指数，建立指数降序排列的链表
Link h,s,q;//h指向结点
int i;
ElemType e;//e为ElemType型结点
h=P.head;
printf("Please input the coefficient and the exponent of items in order:\n");
scanf("%f%d",&e.ceof,&e.expn);
MakeNode(s,e);
InsFirst(h,s);
for(i=2;i<=m;i++){
scanf("%f%d",&e.ceof,&e.expn);
if(!LocateElem(P,e,q)){
if(MakeNode(s,e))InsFirst(q,s);
}
}//for
P.len=m;
}//CreatePolyn

void PrintPolyn(polynomail &P){
Link p;
p=P.head;
printf("%d ,",P.len);
if(p->next!=NULL){
do{
p=p->next;
printf("%f , %d ,",(p->e).ceof,(p->e).expn);
}while(p->next!=NULL);
}//if
printf("\n");
}//打印多项式函数PrintPolyn

void AddPolyn(polynomail &Pa,polynomail &Pb){
Link ha,hb,qa,qb;//ha作为qa的前驱
float sum;
ElemType *a,*b;
ha=Pa.head;hb=Pb.head;
qa=ha->next;qb=hb->next;
while(qa!=NULL&&qb!=NULL){
a=&(qa->e);b=&(qb->e);
switch(cmp(*a,*b)){
case 1:ha=qa;qa=qa->next;break;
case 0:sum=a->ceof+b->ceof;
	   if(fabs(sum)>=1e-6){
	   a->ceof=sum;ha=qa;
	   }
	   else{
	   ha->next=qa->next;free(qa);
	   Pa.len--;
	   }
	   hb->next=qb->next;free(qb);
	   qa=ha->next;qb=hb->next;
	   Pb.len--;
	   break;
case -1:hb->next=qb->next;InsFirst(ha,qb);
	    qb=hb->next;ha=ha->next;
		Pa.len++;
		Pb.len--;
		break;
}//switch
}//while
if(qb=NULL){
	qa->next=qb;
    Pa.len=Pa.len+Pb.len;
}//if
	free(qb);
}//AddPolyn

void SubPolyn(polynomail &Pa,polynomail &Pb){
Link qb;
int i;
qb=(Pb.head)->next;
for(i=1;i<=Pb.len;i++){
(qb->e).ceof=(qb->e).ceof*(-1);
qb=qb->next;
}//for
AddPolyn(Pa,Pb);
}//SubPolyn


void main(){
int i,j,n,m;
LinkList Pa,Pb;
Link ha,hb;
j=0;
ha=(struct LNode *) malloc(sizeof(struct LNode));
hb=(struct LNode *) malloc(sizeof(struct LNode));
Pa.head=ha;Pb.head=hb;
ha->next=NULL;
hb->next=NULL;

do{
printf("Menu:\n");
printf("1.createpolynomail\n2.printpolynomail\n3.addpolynomail\n4.subpolynomail\n5.quit\n");
printf("Please input1~5 and choose 1 the first time!\n");
scanf("%d",&i);
printf("\n");
if(i>5||i<1)printf("Error!\n");
if(i==1)j++;
if(j==0)printf("Error!Please choose 1 the first time!\n");
switch(i){
case 1:ha->next=NULL;
       hb->next=NULL;
	   printf("Please input the total number of item of the first polynomail:\n");
	   scanf("%d",&n);
	   CreatePolyn(Pa,n);
	   printf("Please input the total number of item of the second polynomail:\n");
	   scanf("%d",&m);
	   CreatePolyn(Pb,m);
	   break;
case 2:if(j>0){
	   printf("The first polynomail is:\n");
       PrintPolyn(Pa);
	   printf("The second polynomail is:\n");
	   PrintPolyn(Pb);
	   }//if
	   break;
case 3:if(ha->next!=NULL&&hb->next!=NULL)AddPolyn(Pa,Pb);
	   else printf("There are not enough polynomails.\nPlease choose 1 to recreate two polynomails.\n");
	   break;
case 4:if(ha->next!=NULL&&hb->next!=NULL)SubPolyn(Pa,Pb);
	   else printf("There are not enough polynomails.\nPlease choose 1 to recreate two polynomails.\n");
	   break;
}//switch
}while(i>=1&&i<=4);
}//main