单链表——多项式相加

时间限制：1000ms

内存限制：256M

实验目的：

编写代码，使用两个单链表表示下面的多项式，完成两个多项式相加，并输出相加后的多项式结果。

实验要求：

1、单链表的类型定义如下：

typedef int datatype;//结点数据类型，假设为int
typedef struct node * pointer;//结点指针类型
struct node {       //结点结构
    datatype data;   //系数
    int exp;         //指数
    pointer next;
};
typedef pointer lklist;//单链表类型，即头指针类型

2、将A、B两个多项式相加，并输出相加后的多项式结果

实验运行示例：

Input

本实验无需input信息

Output

output：多项式A+B的结果，并以多项式方式输出

输出案例1

1x^0-1x^4-9x^10+7x^12+8x^14

#include<iostream>
using namespace std;
typedef int datatype;
typedef struct node * pointer;
struct node{
  datatype data;
  pointer next;
  int exp;
};
typedef pointer lklist;
lklist create1(){
	pointer head1,rear,s;
	int a[3]={1,-3,7};
	int b[3]={0,6,12};
	head1=new node;
	rear=head1;
	for(int i=0;i<3;i++){
		s=new node;
		s->data=a[i];
		s->exp=b[i];
		rear->next=s;
		rear=s;
	}
	rear->next=NULL;
	return head1;
}
lklist create2(){
	pointer head2,rear,s;
	int a[4]={-1,3,-9,8};
	int b[4]={4,6,10,14};
	head2=new node;
	rear=head2;
	for(int i=0;i<4;i++){
		s=new node;
		s->data=a[i];
		s->exp=b[i];
		rear->next=s;
		rear=s;
	}
	rear->next=NULL;
	return head2;
}
lklist add(lklist A,lklist B){
	pointer C,p,q,r;
	p=A->next;
	q=B->next;
	C=A;
	r=C;
	while(p!=NULL&&q!=NULL){
		if(p->exp<q->exp){
			r->next=p;
			r=p;
			p=p->next;
		}
		else if(p->exp==q->exp){
			p=p->next;
			q=q->next;
		}
		else{
			r->next=q;
			r=q;
			q=q->next;
		}
	}
	if(p!=NULL)
	r->next=p;
	else
	r->next=q;
	return C;
}
int main(){
	pointer head1,head2;
	pointer x1,x2;
	head1=create1();
	head2=create2();
	x1=add(head1,head2);
	x2=x1->next;
	while(x2!=NULL){
		if(x2->data>0&&x2!=x1->next)
		cout<<"+";
		cout<<x2->data<<"x^"<<x2->exp;
		x2=x2->next;
	}
}