多项式计算器.cpp

用链表创建一元稀疏多项式,做加法和减法计算

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

typedef struct Ployn{//构造一个结构体,每个结点里存放多项式一项的系数,指数和next指针.
	float coef;//系数
	int expn;//指数
	struct Ployn *next;
}term,*LinkList;

LinkList CreatPloyn(int m){//逆位序输入m-1个元素的值,建立带头结点的单链线性表L,返回头指针.
	//输入按次幂的升序输入元素.
	int i;
    LinkList L,p;
	L=(LinkList)malloc(sizeof(term));
	L->next=NULL;//先建立一个头结点.
	L->expn=m-1; //用头结点的expn来存储链表中元素的个数,不包括头结点.
	for(i=m;i>1;i--){
		p=(LinkList)malloc(sizeof(term));
		printf("请输入系数和指数:");
		scanf("%f,%d",&p->coef,&p->expn); //输入多项式每项的系数和指数.
		p->next=L->next; //插到表头.
		L->next=p;
	}
	printf("\n");
	return L;
}
void printPloyn(LinkList L){//输出链表.
//首先输出项数,再逐次按降序输出多项式的每一项.
	LinkList p;
	printf("%d  ",L->expn);//输出多项式的项数
	p=L->next;
	while(p){
		printf("%.1f %d,",p->coef,p->expn);//输出每项的系数和指数
		p=p->next;
	}
	printf("\n");
	return;
}

LinkList AddPloyn(LinkList L1,LinkList L2){
//L1 L2中的元素是按指数非递减排列的.
//做加法:L1=L1+L2     加完后的L1也是按指数非递减排列的.最后返回L1的头指针.
	LinkList pa_cur,pa_pri,pb_cur,pb_pri;//pa_cur pb_cur表当前要做加法的元素的指针
	pa_pri=L1;pb_pri=L2;				//pa_pri pb_pri表当前指针的前一个指针
	pa_cur=L1->next;pb_cur=L2->next;	
	while(pa_cur && pb_cur){
		if(pa_cur->expn>pb_cur->expn){//pa_cur所指结点的指数大于pb_cur所指结点的指数
			pa_pri=pa_cur;				//L1中的相应指针往后指一个结点.L2中的不动.
			pa_cur=pa_cur->next;
		}
		else if(pa_cur->expn==pb_cur->expn){//pa_cur所指结点的指数等于pb_cur所指结点的指数
			pa_cur->coef+=pb_cur->coef;//指数相加
			if(!pa_cur->coef){//加完后,L1的当前结点的指数等于0,释放当前结点,并使L1的项数减一
				pa_pri->next=pa_cur->next;
				free(pa_cur);
				pa_cur=pa_pri->next;
				L1->expn--;
			}
			else{
				pa_pri=pa_cur;
				pa_cur=pa_cur->next;
			}
			pb_pri->next=pb_cur->next;
			free(pb_cur);//释放L2的当前结点
			pb_cur=pb_pri->next;
		}
		else{//pa_cur所指结点的指数小于pb_cur所指结点的指数,L2的当前结点插入到L1当前
			 //结点前一个结点,并使L1的项数加一.
			pa_pri->next=pb_cur;
			pb_cur=pb_cur->next;
			pb_pri->next->next=pa_cur;
			pb_pri->next=pb_cur;
			pa_pri=pa_pri->next;
			L1->expn++;
		}
	}
	if(!pa_cur){//L2的当前结点不为空,把L2包括当前结点之后的所有结点插到L1的最后一个结点之后.
		pa_pri->next=pb_cur;
		while(pb_cur){
			L1->expn++;
			pb_cur=pb_cur->next;
		}
	}
	return L1;
}

void Reverse(LinkList point){//把链表中的系数值全取反
	LinkList p;
	p=point->next;
	while(p){
		p->coef=-p->coef;
		p=p->next;
	}
	return;
}

void FreePloyn(LinkList L){//释放链表L的所有空间,包括头结点
	LinkList p1,p2;
	p1=p2=L;
	while(p1){
		p1=p1->next;
		free(p2);
		p2=p1;
	}
	return;
}

void UnionPloyn(LinkList L){//合并链表L中的同类项
	LinkList p_pri,p_cur;
	if(!L->next)	return;//L只有一个头结点,则不需合并
	else{
		p_pri=L->next;
		if(!p_pri->next)  return;//只有两个结点(包括头结点),不需要合并
		p_cur=p_pri->next;
		while(p_cur){
			if(p_cur->expn==p_pri->expn){//前后两项是同类项,而合并,并释放当前结点,L的项数减一
				p_pri->coef+=p_cur->coef;
				p_pri->next=p_cur->next;
				free(p_cur);
				p_cur=p_pri->next;
				L->expn--;
			}
			p_pri=p_cur;
			p_cur=p_cur->next;
		}
	}
	return;
}

void main(){	
	int n_a,n_b,i;
	LinkList La,Lb;
	printf("输入2表示做减法\n输入1表示做加法\n输入0表示退出\n");
	printf("请选择:");//选择做加法还是做减法,还是都不做
	scanf("%d",&i);
	while(i){
		if(i==0 | i==1 | i==2){//输入的i为0 1 2中一个
			printf("请输入多项式a的项数:");
			scanf("%d",&n_a);
			if(n_a<0){ printf("ERROR!Please input again!\n");continue;}
			La=CreatPloyn(n_a+1);
			UnionPloyn(La);
			printf("请输入多项式b的项数:");
			scanf("%d",&n_b);
			if(n_b<0){ printf("ERROR!Please input again!\n");continue;}
			Lb=CreatPloyn(n_b+1);
			UnionPloyn(Lb);
			printf("输出的多项式a为:");
			printPloyn(La);
			printf("输出的多项式b为:");
			printPloyn(Lb);
			switch(i){
				case 0:return;
				case 1:
						La=AddPloyn(La,Lb);
						printf("a+b的多项式为:");
						printPloyn(La);
						FreePloyn(La);
						break;
				case 2:
						Reverse(Lb);
						La=AddPloyn(La,Lb);
						printf("a-b的多项式为:");
						printPloyn(La);
						FreePloyn(La);
						break;
			}
		}
		else	printf("输入错误,请重新输入!\n");//i不为0 1 2中的任何一个
		printf("输入2表示做减法\n输入1表示做加法\n输入0表示退出\n");
		printf("请选择:");
		scanf("%d",&i);
	}
	return;
}