一元多项式的表示及相加.cpp

一元多项式的表示及相加 《数据结构》（清华大学出版社）P39课题的源代码

#include<stdio.h>
#include<math.h>
#include<malloc.h>
typedef struct{
	float coef;
	int expn;
}term,PElemType;
typedef struct plinknode{
	PElemType data;
	struct plinknode *next;
}PLinkNode;
typedef PLinkNode *PLinkList;
typedef PLinkList polynomial;

void CreatPolyn(PLinkList &P, int m) { 
  PLinkList h,q,s,t;
  PElemType e;
  int i;
  e.coef = 0.0;  e.expn = -1;
  P=(PLinkNode *)malloc(sizeof(PLinkNode));
  P->data=e;P->next=NULL;//建立头结点
  q=P;
  printf("请输入系数,指数：\n");
  for (i=1; i<=m; i++) {
    scanf ("%f,%d",&e.coef, &e.expn);
    if(e.coef!=0.0) {
		s=(PLinkNode *)malloc(sizeof(PLinkNode));
		s->data=e;s->next=NULL;
		if(s->data.expn>q->data.expn){
		    q->next=s;q=q->next;
		}//若s次数大,则直接加在链表之后，结束本次循环
		else{
		  h=P;t=h->next;
		  while(t){
			if(s->data.expn==t->data.expn){
				t->data.coef=t->data.coef+s->data.coef;//若s次数与某项相等,则合并同类项
				free(s);
				if(t->data.coef==0.0){
					h->next=t->next;
					free(t);//若合并后为0，则删去该项
					if(h->next==NULL) q=h;//若该项为最后一项，则将q前移一位
				}
				break;//结束比较
			}
			if(s->data.expn<t->data.expn){
				h->next=s;s->next=t;
				break;
			}//若s次数比某项小，则插入该项之前，结束比较
			h=t;t=t->next;
		  }
		}
	}
    else {
	    printf("系数不为0，请重新输入系数,指数：\n");
		i--;
	}
  }
}// CreatPolyn,同时按升幂排序,合并同类项

void PrintfPoly(PLinkList P) {
  int i=0;
  PLinkList q=P;
  while (q=q->next) {
	  if(i!=0){
		  if (q->data.coef>0.0) printf(" + ");
	  }
	  else i++;
	  printf("%.2f", q->data.coef);
	  if (q->data.expn>=1) printf("x");
	  if (q->data.expn>1) printf("^%d", q->data.expn);
  }
  if(i==0) printf("0");//如果只有头结点，则输出0
  printf("\n");
}// PrintfPoly

int Compare(PElemType a, PElemType b) {
  if (a.expn<b.expn) return -1;
  if (a.expn>b.expn) return 1;
  return 0;
}//比较a，b的次数

void AddPolyn(PLinkList &Pa, PLinkList &Pb) { 
  PLinkList ha,hb,qa,qb;
  PElemType a, b;
  float sum;
  ha = Pa;      
  hb = Pb;
  qa = Pa->next;   
  qb = Pb->next;
  while (qa && qb) {     
    a = qa->data; 
    b = qb->data;
    switch (Compare(a,b)) {
      case -1:  
          ha = qa;
          qa = qa->next;
          break;  
      case 0:   
          sum = a.coef + b.coef ;
          if (sum != 0.0) {  
            qa->data.coef=sum;
            ha = qa;
          } 
		  else {  
            ha->next=qa->next;
            free(qa);
          }
          hb->next=qb->next;
          free(qb);
          qb = hb->next;
          qa = ha->next;
          break;
      case 1:   
          hb->next=qb->next;
          ha->next=qb;qb->next=qa; ha=qb;
          qb = hb->next;
          break;
    } 
  }
  if (Pb->next!=NULL) ha->next=qb; 
  free(Pb); 
} // AddPolyn

void main(){
  PLinkList Pa,Pb;
  int m,n;
  printf("请输入多项式A,B的项数m,n：");
  scanf("%d,%d",&m,&n);
  CreatPolyn(Pa,m);PrintfPoly(Pa);
  CreatPolyn(Pb,n);PrintfPoly(Pb);
  AddPolyn(Pa,Pb);printf("A+B=\n");PrintfPoly(Pa);
}