01 链表的应用--求两个一元多项式之和.cpp

链表的应用

#include <stdio.h>
#include <stdlib.h>


typedef struct{//多项式的数据元素
	int coef;//系数
	int expn;//指数
}term;
typedef struct lnode{//链表元素
	term data;
	struct lnode * next;
}lnode,* linklist;


void creatpolyn(linklist &p,int m){//建立一元多项式
//p为链表的头结点，m为一元多项式的长度
	linklist h,node1,node2,nodenew;
	int i,key;
	term e;
	h=p=(linklist)malloc(sizeof(lnode));//建立头结点
	h->data.coef=0;
	h->data.expn=-1;
	h->next=0;
	for(i=1;i<=m;i++){//插入数据项
		printf("输入系数、指数\n");
		scanf("%d%d",&e.coef,&e.expn);
		for(node1=h->next,key=0;node1;node1=node1->next)
			if(node1->data.expn==e.expn){//若此项已经存在，则修改系数值
				key=1;
				node1->data=e;
				m++;
				break;
			}//if
		if(key==0){//若此项不存在，则新增结点，并插入到合适的位置
			for(node2=h,node1=node2->next;node1&&e.expn>node1->data.expn;node2=node1,node1=node1->next);
			nodenew=(linklist)malloc(sizeof(lnode));
			nodenew->data=e;
			node2->next=nodenew;
			nodenew->next=node1;
		}//if
	}//for
}//creatpolyn

void addpolyn(linklist &pa,linklist &pb){//合并一元多项式
//pa、pb一元多项式分别为需要合并的两个一元多项式（链表）的头结点
	linklist nodea1=pa->next,nodea2=pa,nodeb1=pb->next,nodeb2;
	int a,b,sum;
	if(pa->next&&pb->next){
		while(nodea1&&nodeb1){
			a=nodea1->data.expn;
			b=nodeb1->data.expn;
			switch(a==b?0:(a>b?1:-1)){
				case -1://多项式pa中当前结点的指数值较小
					nodea2=nodea1;
					nodea1=nodea1->next;
					break;
				case 0://两者指数值相等
					sum=nodea1->data.coef+nodeb1->data.coef;
					if(sum!=0){//修改多项式pa中当前结点的指数值
						nodea1->data.coef=sum;
						nodea2=nodea1;
						nodea1=nodea1->next;
					}//if
					else{//删除多项式pa中当前结点
						nodea1=nodea1->next;
						free(nodea2->next);
						nodea2->next=nodea1;
					}//else
					nodeb2=nodeb1->next;
					free(nodeb1);
					nodeb1=nodeb2;
					break;
				case 1://多项式pb中当前结点的指数值较小
					nodeb2=nodeb1->next;
					nodeb1->next=nodea1;
					nodeb1=nodeb2;
					nodea2->next=nodeb1;
					nodea2=nodea1;
					nodea1=nodea1->next;
					break;
			}//switch
		}//while
		if(!nodea1)nodea2->next=nodeb1;
		free(pb);
	}//if
	else
		if(!pa->next){
			pa->next=pb->next;
			free(pb);
		}//if

}//addpolyn

void printpolyn(linklist &p){//输出表达式
	linklist node1=p->next;
	if(node1){
		for(;node1->next;node1=node1->next)
			printf("%dX^%d+",node1->data.coef,node1->data.expn);
		printf("%dX^%d\n",node1->data.coef,node1->data.expn);
	}//if
	else
		printf("0");
}//printpolyn

void main(){//一元多项式按升幂排列
	linklist a,b;
	int m;
	printf("输入表达式1的长度\n");
	scanf("%d",&m);//建立多项式1
	creatpolyn(a,m);
	printf("\n\nf1(x)=");//打印多项式
	printpolyn(a);
	printf("\n输入表达式2的长度\n");//建立多项式2
	scanf("%d",&m);
	creatpolyn(b,m);
	printf("\nf2(x)=");
	printpolyn(b);
	addpolyn(a,b);//合并多项式
	printf("\nf1(x)+f2(x)=");
	printpolyn(a);
}//main