一元稀疏多项式的计算

任务：能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减，并将结果输出；
要求：以链式存储结构实现多项式。

#include<cstdio>
#include<iostream>
using namespace std;

typedef struct PNode {
	float coef;//系数
	int expn;//指数
	struct PNode *next; 
}PNode,*Polynomial;

/**多项式的创建(有序)*/
void CreatPolyn(Polynomial &P,int n) {//传入多项式长度
    printf(\"请输入各项的系数和指数:\\n\");
	P=new PNode;//建立一个带头结点的单链表
	P->next=NULL;
	for(int i=1;i<=n;i++){//依次输入n个非零项 
		Polynomial s=new PNode;//创建一个新的结点
		cin>>s->coef>>s->expn;//输入系数和指数
		Polynomial pre=P;//用于保存q点的前驱,初始值为头结点
		Polynomial q=P->next;//q的初始化,指向首元结点
		while(q&&s->expn<q->expn){//找到小于s的项,将s插在这一项之前 
			pre=q;
			q=q->next; 
		} 
		s->next=q;
		pre->next=s;
	}
}

/**打印某个多项式*/
void PrintPolyn(Polynomial &P){
	Polynomial p=P;
	while(p->next){
		printf(\"%.0fx%d \",p->next->coef,p->next->expn);
		p=p->next;
	}
	printf(\"\\n\"); 
} 

/**多项式加法Pa=Pa+Pb*/
void AddPolyn(Polynomial &Pa,Polynomial &Pb){
	//将两个链表合并成一个链表的过程(降序)
	Polynomial p1=Pa->next;Polynomial p2=Pb->next;//p1,p2初值分别指向Pa和Pb的首元结点
	Polynomial p3=Pa;//p3指向和多项式的当前结点,初值为Pa,Pa最后一个结点的前驱,合成的链中最后一个结点 
	while(p1&&p2){
		if(p1->expn==p2->expn){
			int sum=p1->coef+p2->coef;
			if(sum!=0){
				p1->coef=sum;//修改p1的系数
				p3->next=p1;p3=p1;
				p1=p1->next;
				PNode *r=p2;p2=p2->next;delete r;//删除Pb中的结点 
			}
			else{//系数和为零,Pa、Pb都删除 
				PNode *r=p1;p1=p1->next;delete r;
				r=p2;p2=p2->next;delete r; 
			}
		}
		else if(p1->expn<p2->expn){//Pa当前结点指数小,要将Pb放在p3之后,p3后移 
			p3->next=p2;p3=p2;p2=p2->next;//p2继续指向Pb的下一个结点继续比较 
		} 
		else{//Pb当前结点的指数小,直接将Pa当前结点放在p3之后,p3后移 
			p3->next=p1;p3=p1;p1=p1->next; 
		} 
	}
	//有一个链为空的时候
	p3->next=p1?p1:p2; 
	delete Pb;//释放Pb的头结点 
	printf(\"两个多项式相加的结果为:\\n\");
	PrintPolyn(Pa);
	printf(\">>Enter键返回主界面\\n\"); 
	system(\"pause\");
	system(\"cls\");
}

/**多项式减法*/
void SubPolyn(Polynomial &Pa,Polynomial &Pb){
	//将两个链表合并成一个链表的过程(降序)
	Polynomial p1=Pa->next;Polynomial p2=Pb->next;//p1,p2初值分别指向Pa和Pb的首元结点
	Polynomial p3=Pa;//p3指向和多项式的当前结点,初值为Pa,Pa最后一个结点的前驱,合成的链中最后一个结点 
	while(p1&&p2){
		if(p1->expn==p2->expn){
			int sum=p1->coef-p2->coef;
			if(sum!=0){
				p1->coef=sum;//修改p1的系数
				p3->next=p1;p3=p1;
				p1=p1->next;
				PNode *r=p2;p2=p2->next;delete r;//删除Pb中的结点 
			}
			else{//系数和为零,Pa、Pb都删除 
				PNode *r=p1;p1=p1->next;delete r;
				r=p2;p2=p2->next;delete r; 
			}
		}
		else if(p1->expn<p2->expn){//Pa当前结点指数小,要将Pb放在p3之后,p3后移 
			p3->next=p2;p3=p2;p2=p2->next;//p2继续指向Pb的下一个结点继续比较 
		} 
		else{//Pb当前结点的指数小,直接将Pa当前结点放在p3之后,p3后移 
			p3->next=p1;p3=p1;p1=p1->next; 
		} 
	}
	//有一个链为空的时候
	p3->next=p1?p1:p2;
	delete Pb;//释放Pb的头结点 
	printf(\"两个多项式相减的结果为:\\n\");
	PrintPolyn(Pa);
	printf(\">>Enter键返回主界面\\n\"); 
	system(\"pause\");
	system(\"cls\");
}

/**主界面*/
void Menu(){
	printf(\"*********一元稀疏多项式的计算*********\\n\");
	printf(\"**********1.一元多项式的加法**********\\n\");
	printf(\"**********2.一元多项式的减法**********\\n\");
	printf(\"****************3.退出****************\\n\");
	printf(\"**************************************\\n\");
	printf(\">>请输入您的选择(1-3):\");
	int chose;
	scanf(\"%d\",&chose);
	switch(chose){
		case 1:{
 			printf(\"请输入第一个多项式的项数:\");
			int len1,len2;
			scanf(\"%d\",&len1);
			Polynomial Pa; 
			CreatPolyn(Pa,len1);
			printf(\"请输入第二个多项式的项数:\");
			scanf(\"%d\",&len2);
			Polynomial Pb;
			CreatPolyn(Pb,len2);
			printf(\"第一个多项式为:\"); 
			PrintPolyn(Pa);
			printf(\"第二个多项式为:\"); 
			PrintPolyn(Pb);
			AddPolyn(Pa,Pb);
			Menu();
		}
		case 2: {
			printf(\"请输入第一个多项式的项数:\");
			int len1,len2;
			scanf(\"%d\",&len1);
			Polynomial Pa; 
			CreatPolyn(Pa,len1);
			printf(\"请输入第二个多项式的项数:\");
			scanf(\"%d\",&len2);
			Polynomial Pb;
			CreatPolyn(Pb,len2);
			printf(\"第一个多项式为:\"); 
			PrintPolyn(Pa);
			printf(\"第二个多项式为:\"); 
			PrintPolyn(Pb);
			SubPolyn(Pa,Pb); 
			Menu();
		}
		case 3: {
			exit(0);
		}
		default : {
			printf(\"请您输入正确的选择!\\n\");
			system(\"pause\");
			system(\"cls\");
			Menu();
		}
	} 
}

int main(){
	Menu(); 
	return 0;
}