一元多项式运算器的分析与实现
 
 
首先，需要解决一元多项式在计算机中的存储问题。对于一元多项式： P = p0 + p1x + …+pnx^n ；在计算机中，可以用一个线性表来表示： P = (p0,p1,…,pn), 但是对于形如 S(x) = 1 + 5x^10 000 -12x^15 000 的多项式，上面的方法显然不合适，会有很多的项系数为0，造成存储空间的浪费，因此只需要存储非0系数项。
 
 
为了实现任意多项式的运算，考虑到运算时有较多的插入、删除操作，选择单链表作为存储结构比较方便，每个结点有三个域：系数、指数和指针。其数据结构如下所示：**
 
typedef struct DuoXiangShi{
	int xi_shu;  //系数
	int zhi_shu; //指数
	struct DuoXiangShi *next;  //指向下一个结点的指针
	 
}Polyn, *LinkPolyn;
 
 
一、建立多项式
 
 
通过键盘输入一组多项式的系数和指数，用尾插法建立一元多项式的链表。以输入系数0为结束标志，并约定建立一元多项式链表时，总是按指数从小到大的顺序排列。
 
/*用尾插法创建链表*/
LinkPolyn CreatePolyn(){
	LinkPolyn head,p,tail;
	 
	float x;      //存储输入的系数 
	int   e;      //存储输入的指数
	head = (LinkPolyn)malloc(sizeof(Polyn));     //生成头结点
	head->next = NULL;                   //生成空表
	tail = head;
	scanf("%d,%d",&x,&e);
	while(x!=0)                  //当x=0时，多项式输入结束 
	{
		p = (LinkPolyn)malloc(sizeof(Polyn));
		p->xi_shu = x;
		p->zhi_shu = e;
		tail->next = p;     //在表尾进行插入操作 
		tail = p;           //tail始终指向表尾 
		scanf("%f,%d",&x,&e);	
	}
	tail->next = NULL;          //将表中最后一个结点的next置为NULl 
	
	return head;
} 
 
 
二、输出多项式
 
 
从单链表第一个元素开始，逐项读出系数和指数，按多项式的形式进行输出即可。
 
/*打印多项式*/
void PrintPolyn(LinkPolyn LA)
{
	LinkPolyn p = LA->next;      //LA有头结点，让p指向LA的第一元素结点
	int flag = 1;
	
	if(!p)       //如果链表为空，没有项 
	{
		putchar('0');
		printf("\n");
		//return;
	}
	
	while(p)
	{
		if(p->xi_shu > 0 && flag != 1)  putchar('+');
		//if(p->xi_shu == 0) continue;
		if(p->xi_shu != 1 && p->xi_shu != -1 && p->xi_shu != 0)
		{
			printf("%d",p->xi_shu);
			if(p->zhi_shu == 1)
			{
				putchar('X');
			}
			else if(p->zhi_shu)
			{
				printf("X^%d",p->zhi_shu);
			}
			else               /*系数为1或系数为-1的情况*/
			{
				if(p->xi_shu == 1)
				{
					//如果指数为0
					if(!p->zhi_shu)   putchar('1');
					else if(p->zhi_shu == 1)  putchar('X');
					else        printf("X^%d",p->zhi_shu); 
				}
				if(p->xi_shu == -1) 
				{
					//如果指数为0
					if(!p->zhi_shu)   printf("-1");
					else if(p->zhi_shu == 1)  printf("-X");
					else        printf("-X^%d",p->zhi_shu);
				}
			}
			
			p = p->next;
			flag++;
		}
		else{
			p = p->next;
		}
	}
	printf("\n");
}
 
 
三、两个多项式相加
 
 
以单链表LA和LB分别表示两个一元多项式A和B，A+B的求和运算就等同于单链表的插入，设一个单链表LC来存放LA+LB的和。
 
/*两个多项式相加------返回的还是一个多项式*/
LinkPolyn AddPolyn(LinkPolyn LA,LinkPolyn LB)
{
	LinkPolyn pa = LA->next;      //指向LA的第一元素结点
	LinkPolyn pb = LB->next;      //指向LB的第一元素结点	
	
	LinkPolyn LC,pc,qc;     //LC存储LA+LB
	pc = (LinkPolyn)malloc(sizeof(struct DuoXiangShi));
	pc->next = NULL;
	LC = pc;        //保留原链的头指针 
	
	//当两个多项式均未扫描结束时 
	while(pa != NULL && pb != NULL) 
	{
		qc = (LinkPolyn)malloc(sizeof(struct DuoXiangShi));
		if(pa->zhi_shu < pb->zhi_shu)
		{
			qc->xi_shu = pa->xi_shu;
			qc->zhi_shu = pa->zhi_shu;
			pa = pa->next;
		}
		else if(pa->zhi_shu == pb->zhi_shu)
		{
			qc->xi_shu = pa->xi_shu + pb->xi_shu;
			qc->zhi_shu = pa->zhi_shu;
			pa = pa->next;
			pb = pb->next; 
		}
		else
		{
			qc->xi_shu = pb->xi_shu;
			qc->zhi_shu = pb->zhi_shu;
			pb = pb->next; 
		}
		if(qc->xi_shu != 0)
		{
			qc->next = pc->next;
			pc->next = qc;
			pc = qc;
		}
		else free(qc);
	} 
	/*如果LA中有余项，将剩余项插入LC*/
	while(pa != NULL)
	{
		qc = (LinkPolyn)malloc(sizeof(struct DuoXiangShi));
		qc->xi_shu = pa->xi_shu;
		qc->zhi_shu = pa->zhi_shu;
		pa = pa->next;
		qc->next = pc->next;
		pc->next = qc;
		pc = qc;
	} 
	/*如果LB中有余项，将剩余项插入LC*/
	while(pb!= NULL)
	{
		qc = (LinkPolyn)malloc(sizeof(struct DuoXiangShi));
		qc->xi_shu = pb->xi_shu;
		qc->zhi_shu = pb->zhi_shu;
		pb = pb->next;
		qc->next = pc->next;
		pc->next = qc;
		pc = qc;
	} 
	return LC;	
} 
 
 
四、两个多项式相减
 
 
将减数LB多项式的所有系数变为其相反数，然后使用两个多项式相加的思想进行处理。
 
/*两个多项式相减------返回的还是一个多项式*/
LinkPolyn SubstractPolyn(LinkPolyn LA,LinkPolyn LB)
{
	LinkPolyn b = LB;
	LinkPolyn p = LB->next;
	LinkPolyn LD;
	while(p)
	{
		p->xi_shu *= -1;
		p = p->next;
	}
	
	LD = AddPolyn(LA,b);
	
	for(p = b->next; p ;p = p->next)
	{
		p->xi_shu *= -1;
	}
	return LD;
} 

 
 
五、多项式乘法
 
 
多项式乘法类似于两个多项式相加，需要使用一个多项式的每一项和另一个多项式的每一项进行相乘，然后进行多项式相加操作
 
/*多项式相乘*/
LinkPolyn MultiplyPolyn(LinkPolyn LA,LinkPolyn LB)
{
	LinkPolyn pa = LA->next;
	LinkPolyn pb = LB->next;
	LinkPolyn LC,pc,qc;
	LinkPolyn LD; 
	LD = (LinkPolyn)malloc(sizeof(Polyn));
	LD->next = NULL;        //建立一个空表 
	
	while(pa != NULL)
	{
		
		pc = (LinkPolyn)malloc(sizeof(struct DuoXiangShi));
		pc->next = NULL;
		LC = pc; 
		while(pb != NULL)
		{
			qc = (LinkPolyn)malloc(sizeof(struct DuoXiangShi));
			qc->xi_shu = pa->xi_shu * pb->xi_shu;
			qc->zhi_shu = pa->zhi_shu + pb->zhi_shu;
			qc->next = pc->next;
			pc->next = qc;
			pc = qc; 
			pb = pb->next; 
		}
		LD = AddPolyn(LD,LC);
		pa = pa->next;
		pb = LB->next;
	}
	return LD;
} 
 
 
六、求多项式的值
 
 
需要输入变量x的值，然后进行求值运算
 
/*多项式求值*/
int EvaluatePolyn(LinkPolyn polyn,int x)
{
	LinkPolyn p = polyn->next;
	int sum = 0;
	while(p != 0)
	{
		sum += p->xi_shu*pow(x,p->zhi_shu);
		p = p->next;
	}
	return sum;
}
 
 
七、多项式的导数
 
 
需要根据导数公式对多项式的每一个结点求导，具体过程如下：多项式的当前结点指数为0，则其导数为0；当前结点指数不为0，则其导数的系数为当前结点指数乘以系数，指数为当前结点的指数减1。
 
/*多项式的导数，返回值仍然为一个多项式*/
LinkPolyn DaoPolyn(LinkPolyn polyn)
{
	LinkPolyn dao = polyn;
	LinkPolyn p = polyn->next;
	while(p!=NULL)
	{
		if(p->zhi_shu != 0)
		{
			p->xi_shu = p->zhi_shu * p->xi_shu;
			p->zhi_shu = p->zhi_shu - 1;
			p = p->next; 
		}
		else
		{
			p->xi_shu = 0;	
			p = p->next;
		}
		
	 
	}
	return dao;
} 
 

链表的生成
利用链表实现一元多项式的+、-、*运算，注意具体的思路是判断同类项，对其进行合并同类项，在乘法运算达到了O(n^3)，可以优化的地方是先对结果链表C进行预处理，先复制这个链表给C，然后表C的操作过程就将了一维，变成O(n^2)，并且每次可以利用链表的有序性这一点进行二分，但这是链表啊！怎么二分？还没想到，干脆把链表先导入数组中，然后在操作？这样就O(nlogn)了？....扯远了，就先O(n^3)吧。
要求：

实验五、线性表应用—一元多项式加减运算
1 实验目的
掌握用线性结构表示一元多项式的方法及实现一元多项式的加、减运算。
2 实验内容
两个一元多项式从键盘输入，每一项主要包括系数和指数两个数据，分别将两个一元多项式存到两个单链表中，然后对两个一元多项式进行加、减运算，最后输出结果。
3 实验过程
（1）：
（截图）
（2） ：
（截图）
（3） ：
（截图）
 
4 源代码
（附件）
具体代码如下：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

//******宏定义参数******
#define OK 1
#define NO 0
#define DATA_MAX_SIZE 20

//******定义数据类型别名******
typedef int Status;
typedef char Excelelem;
typedef int Numelem;
typedef double db;

//******声明数据结构******
typedef struct Node
{
	db xishu;
	db mi;
	struct Node *next;
}LNode,*LinkList;

typedef struct
{
	Excelelem name[100];
	Numelem length;
	LinkList next;
}HeadList,*HeadLinkList;

//******声明函数******
LinkList Init(Numelem *n); //初始化链表体
HeadLinkList HeadInit(char a[]); //初始化链表头
LinkList DATA_UPPER_FIND(LinkList Head,db ans); //查找链表中第一个系数大于ans的结点的前驱
void DATA_ADD(HeadLinkList A,HeadLinkList B,HeadLinkList C); //多项式加法 O(n)
void DATA_SUB(HeadLinkList A,HeadLinkList B,HeadLinkList C); //多项式减法 O(n)
void DATA_Free(HeadLinkList Head); //释放链表体内存
void DATA_cout(HeadLinkList Head); //将链表数据域以多项式形势输出
void DATA_MUL(HeadLinkList A,HeadLinkList B,HeadLinkList C); //多项式乘法 O(n^3)

int main()
{
	HeadLinkList A,B,C;
	Numelem n;
	printf("**********start!**********\n");
	A=HeadInit("A多项式");
	printf("请输入%s:\n",A->name);
	A->next=Init(&A->length);
	B=HeadInit("B多项式");
	printf("请输入%s:\n",B->name);
	B->next=Init(&B->length);
	C=HeadInit("C多项式");
	C->next=NULL;
	printf("请输出%s的内容:\n",A->name);
	DATA_cout(A);
	printf("请输出%s的内容\n",B->name);
	DATA_cout(B);
	printf("%s+%s:\n",A->name,B->name);
	DATA_ADD(A,B,C);
	DATA_cout(C);
	printf("%s-%s:\n",A->name,B->name);
	DATA_SUB(A,B,C);
	DATA_cout(C);
	printf("%s*%s:\n",A->name,B->name);
	DATA_MUL(A,B,C);
	DATA_cout(C);
	printf("操作结束，释放内存!\n");
	DATA_Free(A);DATA_Free(B);DATA_Free(C);
	free(A),free(B),free(C);
	printf("***********End!***********\n");
	return 0;
}

//******查找插入的位置******
LinkList DATA_UPPER_FIND(LinkList Head,db ans)
{
	if(Head->next == NULL || Head->next->mi > ans)
		return Head;
	return DATA_UPPER_FIND(Head->next,ans);
}

LinkList Init(Numelem *n)
{
	//以系数=0为输入结束标志,以下为输入的多项式默认为已合并同类项，否则在查找的时候多一项特判
	LinkList Head,p,q;
	Numelem i=0;
	db a,b;
	Head=NULL;
	while(~scanf("%lf",&a) && a!=0.0)
	{
		scanf("%lf",&b);
		q=(LinkList)malloc(sizeof(LNode));
		q->xishu=a;
		q->mi=b;
		if(*n==0 || Head->mi>b) q->next=Head,Head=q;
		else
		{
			p=DATA_UPPER_FIND(Head,b);
			//if p->mi==b ...  未合并同类项的情况
			q->next=p->next;
			p->next=q;
		}
		*n++;
	}
	return Head;
}

HeadLinkList HeadInit(char *a)
{
	HeadLinkList Head;
	Head=(HeadLinkList)malloc(sizeof(HeadList));
	strcpy(Head->name,a);
	Head->length=0;
	return Head;
}

void DATA_ADD(HeadLinkList A,HeadLinkList B,HeadLinkList C)
{
	LinkList qa=A->next,qb=B->next,p,q=NULL;
	DATA_Free(C);
	while(qa || qb)
	{
		p=(LinkList)malloc(sizeof(LNode));
		if(qb==NULL || qa && qa->mi<qb->mi)
		{
			*p=*qa;
			qa=qa->next;
		}
		else if(qa==NULL || qb && qa->mi>qb->mi)
		{
			*p=*qb;
			qb=qb->next;
		}
		else
		{
			p->xishu=qb->xishu+qa->xishu;
			p->mi=qb->mi;
			qa=qa->next;
			qb=qb->next;
		}
		if(q==NULL) p->next=q,C->next=q=p;
		else
			p->next=q->next,q->next=p,q=p;
		C->length++;
	}
}

void DATA_SUB(HeadLinkList A,HeadLinkList B,HeadLinkList C)
{
	LinkList qa=A->next,qb=B->next,p,q=NULL;
	DATA_Free(C);
	while(qa!=NULL || qb!=NULL)
	{
		p=(LinkList)malloc(sizeof(LNode));
		if(qb==NULL || qa && qa->mi<qb->mi)
		{
			*p=*qa;
			qa=qa->next;
		}
		else if(qa==NULL || qb && qa->mi>qb->mi)
		{
			*p=*qb;
			p->xishu*=-1;
			qb=qb->next;
		}
		else
		{
			*p=*qa;
			p->xishu-=qb->xishu;
			qa=qa->next;
			qb=qb->next;
			if(p->xishu==0)
			{
				free(p);
				continue;
			}
		}
		if(q==NULL) p->next=q,C->next=q=p;
		else
			q->next=p->next,q->next=p,q=p;
		C->length++;
	}
}

void DATA_MUL(HeadLinkList A,HeadLinkList B,HeadLinkList C)
{
	LinkList qa,qb,p,q;
	db a,b;
	DATA_Free(C);
	for(qa=A->next;qa;qa=qa->next)
	{
		for(qb=B->next;qb;qb=qb->next)
		{
			a=qa->xishu*qb->xishu;
			b=qa->mi+qb->mi;
			if(C->length)
			{
				p=DATA_UPPER_FIND(C->next,b);
				if(p->mi == b)
					p->xishu+=a;
				else
				{
					q=(LinkList)malloc(sizeof(LNode));
					q->xishu=a;
					q->mi=b;
					q->next=p->next;
					p->next=q;
					C->length++;
				}
			}
			else
			{
				p=(LinkList)malloc(sizeof(LNode));
				p->xishu=a;
				p->mi=b;
				p->next=C->next;
				C->next=p;
				C->length++;
			}
		}
	}
}

void DATA_Free(HeadLinkList Head)
{
	LinkList q=Head->next,p;
	while (q)
	{
		p=q;
		q=q->next;
		free(p);
	}
	Head->length=0;
	Head->next=NULL;
	return ;
}

void DATA_cout(HeadLinkList Head)
{
	LinkList q=Head->next;
	while(q)
	{
		if(q->xishu>0 && q!=Head->next)
			printf("+");
		printf("%.1lfx^(%.1lf)",q->xishu,q->mi);
		q=q->next;
	}
	printf("\n");
	return ;
}

总结：

 链表和顺序表的直接操作各有优点，在处理离散程度较大的数据时，链表可以节省空间，顺序表就会比较耗内存；在处理相对连续的数据时，用到顺序表就可以利用其逻辑结构和物理结构一直这一特点，降低算法的复杂度。

  一元多项式的加法，减法，乘法用到比较多的是插入，删除操作。所以一般选择单链表作为存储结构。每个结点分别有系数，指针作为数据域，以及指针域。
 
 算法实现：
 
 一.一元多项式加法：
 
 1.建立多项式：尾插法建立一元多项式的链表，通过键盘输入多项式的系数和指数，以输入系数0为结束标志，并约定建立一元多项式链表时，总是按指数从小到大的顺序排列。
 
 2.输出多项式：从单链表的第一项开始逐项读出系数和指数，按多项式的形式输出。
 
 3.多项式相加：设La和Lb分别表示两个多项式。Lc表示和多项式。p,q，r分别表示指向单链表的当前项比较指数大小。
 
 （1）若La->exp<Lb->exp,则结点p应是和多项式中的一项，将p复制到r，并使p后移。
 
 （2）若La->exp = Lb->exp,则将两个结点中的系数相加，当和不为0时，La的系数域加上Lb的系数域作为Lc的系数域；若和为0，则和多项式中没有这一项，p,q后移。
 
 （3）若La->exp > Lb->exp,则将结点q复制到Lc中，q后移。
 
 
 
 二.一元多项式减法
 
 算法：将减数多项式的所有系数先变为相反数，然后调用多项式相加的函数进行运算。
 
 
 
 三.一元多项式乘法
 
 两个多项式相乘，应该是第一个多项式中的每一项分别与第二个多项式相乘，将相乘得到的结果都存在第一个多项式中，再调用合并多项式的函数。我写的多项式相乘用到了两重循环，合并多项式也用到了两重循环。
 
 
 
 
 
 小结：在这次代码实现中，主要还是基础的一些线性表的操作的练习，还可以进一步改良的地方就是可以在合并多项式这部分与多项式相加写成一个函数，这样可以减少代码量，代码的通用性更高。
 
 
 
 附：源代码
 
 #include<stdio.h>
 
 #include<stdlib.h>
 
 
 
 
 
 typedef struct NODE{
 
 int coef; //系数
 
 int exp; //指数
 
 struct NODE *next;
 
 }polynode,*Polylist;
 
 
 
 int output_list(Polylist head);
 
 
 
 Polylist Creat_list(){ //创建链表
 
 Polylist head,rear,s;
 
 head = (Polylist)malloc(sizeof(polynode));
 
 rear = head;
 
 
 
 while(1){
 
 printf("input the coef,exp:\n");
 
 s = (Polylist)malloc(sizeof(polynode));
 
 scanf("%d", &s->coef);
 
 if(!s->coef){
 
 free(s);
 
 break;
 
 }
 
 scanf("%d", &s->exp);
 
 rear->next = s;
 
 rear = s;
 
 }
 
 rear->next = NULL;
 
 return (head);
 
 }
 
 
 
 
 
 Polylist add_list(Polylist head1,Polylist head2){ //多项式加法
 
 Polylist p, q, s, head, tail; 
 
 p = head1->next;
 
 q = head2->next;
 
 tail = head = (Polylist)malloc(sizeof(polynode));
 
 while(p && q){
 
 s = (Polylist)malloc(sizeof(polynode));
 
 if(p->exp < q->exp){ //当P的指数小于Q的指数时
 
 s->coef = p->coef;
 
 s->exp = p->exp;
 
 tail->next = s; 
 
 tail = s;
 
 tail ->next = NULL;
 
 p = p->next;
 
 
 
 }
 
 else if(p->exp == q->exp){ //当指数相等时
 
 s->coef = p->coef + q->coef;
 
 s->exp = p->exp;
 
 if (!s->coef){
 
 free(s);
 
 }
 
 else{
 
 tail->next = s; 
 
 tail = s;
 
 tail ->next = NULL;
 
 }
 
 p = p->next;
 
 q = q->next;
 
 }
 
 
 
 else{ 
 
 s->coef = q->coef;
 
 s->exp = q->exp;
 
 tail->next = s; 
 
 tail = s;
 
 tail ->next = NULL; 
 
 q = q->next;
 
 }
 
 }
 
 if(p)
 
 tail->next = p;
 
 else
 
 tail->next = q;
 
 return head;
 
 }
 
 
 
 
 
 Polylist sub_list(Polylist head1,Polylist head2){ //多项式减法
 
 Polylist p ,head;
 
 p = head2->next;
 
 do{ 
 
 p->coef = -p->coef;
 
 p = p->next;
 
 }while(p);
 
 head =add_list(head1,head2);
 
 return head; 
 
 }
 
 
 
 
 
 
 
 Polylist polyadd_list(Polylist head){ //合并多项式
 
 Polylist p,q,m;
 
 p = m = head->next;
 
 while(p ->next ){
 
 m = p;
 
 q = p->next;
 
 while(q){
 
 if(q->exp == p->exp){ 
 
 p->coef += q->coef;
 
 m->next = q->next;
 
 free(q);
 
 q = m->next;
 
 }
 
 else{
 
 m = q;
 
 q = q->next;
 
 }
 
 }
 
 p = p->next;
 
 }
 
 return head;
 
 }
 
 
 
 
 
 Polylist multi_list(Polylist head1,Polylist head2){ //多项式乘法
 
 Polylist head,p,q,r,m;
 
 head = r = (Polylist)malloc(sizeof(polynode));
 
 
 
 for(p = head1->next;p != NULL;p = p->next)
 
 {
 
 for(q = head2->next;q != NULL;q = q->next)
 
 {
 
 m = (Polylist)malloc(sizeof(polynode));
 
 m->coef = p->coef * q->coef;
 
 m->exp = p->exp + q->exp;
 
 r->next = m;
 
 r = m;
 
 }
 
 }
 
 r->next = NULL;
 
 output_list(head);
 
 polyadd_list(head);
 
 return head;
 
 }
 
 
 
 
 
 
 
 int output_list(Polylist head){ //输出多项式
 
 Polylist p;
 
 int n = 1;
 
 for(p = head->next;p !=NULL;p = p->next){
 
 printf("第%d项：%d   %d   \n", n++,p->coef,p->exp);
 
 }
 
 return 0;
 
 }
 
 
 
  
 
 int main(){
 
 Polylist head1,head2,head;
 
 head1 = Creat_list();
 
 head2 = Creat_list();
 
 
 
  
 
 printf("多项式加法：\n");
 
     head =add_list(head1,head2);
 
 output_list(head);
 
 
 
 printf("多项式减法：\n");
 
 head = sub_list(head1,head2); 
 
  output_list(head);
 
  
 
 
 
 printf("多项式乘法：\n");
 
 head = multi_list(head1,head2);
 
 output_list(head);
 
 
 
 
 
 return 0;
 
 } 

一、 需求分析
 
0.问题描述
 
在数学上，一个一元n次多项式 可按降序写成：
 
 它由n+1个系数唯一确定，因此，在计算机里他可以用一个线性表表示：
 
 
设Pn(x)和Qn(x)分别为两个一元多项式，请求出两个一元多项式的加法运算的结果，要求元素按照多项式的次数递减的次序排列。
 
1.问题分析
 
需求：实现两个一元多项式的加法运算。
 实现功能：①通过键盘接收输入的整数（浮点数）
 ②以系数和指数对应的形式，储存到计算机内存中
 ③实现一元多项式的加法运算
 ④通过屏幕输出一元多项式加法运算后的结果
 
2.输入数据
 
分别输入两组二元组数据，每一组二元组数据分别代表一个多项式，每个二元组包含两个整数（一个浮点数和一个整数），第一个整数（浮点数）代表多项式的项的系数，第二个整数代表该项的次数（指数），且在输入过程中，要求同一个多项式中不能出现两个项的指数相同。（使用模板设计，以下设计以系数为整数为例）
 
3.输出数据
 
输出两个一元二次多项式相加运算之后的结果，形式如 
 
4.测试样例设计
 
（1）样例输入1：
 
4
3 2
4 5
1 1
2 3
3
-3 2
-4 5
2 4
 
（1）样例输出1：
 
第一个多项式为:
4x^5+2x^3+3x^2+1x^1
第二个多项式为:
-4x^5+2x^4-3x^2
两个多项式的和为:
2x^4+2x^3+1x^1
 
目的：本例为了测试在两组多项式相加时，两个多项式中恰有相同指数项的系数互为相反数，即相加之后为0，能否实现正确计算。
 
（2）样例输入2：
 
2
0 1
2 3
3
2 6
3 9
4 3
 
（2）样例输出2：
 
第一个多项式为:
2x^3
第二个多项式为:
3x^9+2x^6+4x^3
两个多项式的和为:
3x^9+2x^6+6x^3
 
目的：本例为了检测若输入的项的系数是0，那么输出是否会出现错误，会不会把项 为0的也输出出来，能否实现正确运算。
 
（3）样例输入3：
 
1
2 3
1
3 3
 
（3）样例输出3：
 
第一个多项式为:
2x^3
第二个多项式为:
3x^3
两个多项式的和为:
5x^3
 
目的：本例为了测试在两组多项式只有一项的情况下，并且这项的幂相等，观察输出是否是一项。
 
（4）样例输入4：
 
2
0 5
0 4
5
6 5
3 8
-2 2
3 1
2 4
 
（4）样例输出4：
 
第一个多项式为:
（此处输出为空）
第二个多项式为:
3x^8+6x^5+2x^4-2x^2+3x^1
两个多项式的和为:
3x^8+6x^5+2x^4-2x^2+3x^1
 
目的：当某一个多项式所有项的系数均为0时，观察该多项式样式输出 及运算结果。
 
（5）样例输入5：
 
3
4 2
-2 2
-1 2
2
0 2
6 2
 
（5）样例输出5：
 
第一个多项式为:
4x^2-2x^2-1x^2
第二个多项式为:
6x^2
两个多项式的和为:
10x^2-2x^2-1x^2
 
目的：本例是反例，若不符合要求同一个多项式不能有相同的幂的项存在，观察该多项式输出及运算结果。
 
二、概要设计
 
1.抽象数据类型
 
问题的输入为多项式的，多项式由一个或者多个项构成，而每个项又是由一个指数和一个系数唯一确定，那么这个指数和这个系数就是一个具有关系的数对，我们可以用结构体进行存储，可以形象的定义为一个二元组（ai，bi），那么这些二元组按照多项式的次数递减的次序排列，则具有线性关系，则两个多项式可以分别用两个线性表表示，线性表中的数据元素即为多项式的项的二元组。
 
数据对象：
 
 
数据关系：
 
因为多项式按照多项式的次数递减的次序排列，相应的指数对应的系数也就排列好前后位置，因此具有线性结构，这些二元组之间都存在着有序的关系。即
 
 
基本操作：
 
①	link();                       // 构造线性表 
②	~link();                      // 摧毁线性表 
③	void init();                  // 初始化线性表 
④	void next();                  // 当前位置后移 
⑤	void movetostart();           // 移动当前位置到线性表表头 
⑥	arrary<E> getvalue();         // 获取当前位置存储单元内的数据元素
⑦	void insert(arrary<E> elem);   // 插入数据元素（实现线性表的有序性） 
⑧	int getsize();                // 返回线性表长度
⑨	void change(arrary<E> elem);  // 改变储存数据元素的值
 
2.算法的基本思想
 
存储：解决本问题首先要想到的就是怎么把一个乱序输入的二元组按照第二个数的从大到小的顺序排列下来，可以这么想，每次要添加一个二元组的时候都要把已经存在的二元组进行一次从头的搜索，查找到一个适当位置，使得二元组插入后，线性表数据元素满足以二元组第二个数依次递减的次序排列。把二元组的前后逻辑线性关系存储在链表中，通过修改插入函数实现上面存储中所提到的查找位置问题，然后把输入的二元组插入即可完成有序链表的构建。
 相加：把第二个多项式的线性表中的每一个数据元素二元组中第二个数依次与第一个多项式的线性表中的每一个数据元素二元组中第二个数比较，如果相同，通过修改第一个多项式的线性表中的每一个数据元素二元组中第一个数，实现相同指数项的相加，否则通过插入操作把该二元组插入到第一个多项式的线性表中。
 输出：完成相加后，计算结果储存在第一个多项式的线性表中，且由于插入时已完成了有序性的排列，按照线性表的线性顺序及多项式的写法规则输出完成相加后第一个多项式线性表中的数据元素。
 
3.程序的流程
 
① 第一个模块：输入模块。提示输入多项式的项数，之后提示输入多项式的每一项的系数和指数，调用insert（有序插入）等基本操作实现有序存储数据，将多项式分别储存到线性表中，然后根据多项式的写法规则调用基本操作进行打印多项式。
 ② 第二个模块：计算模块。根据第一个模块接受的数据，利用多重循环，对第二个多项式与第一个多项式进行遍历比较，并调用change、insert等基本操作完成两个多项式的相加，计算结果存储到第一个多项式的线性表中。
 ③ 第三个模块：输出模块。通过提示，按照多项式的写法规则打印出相加后的多项式的形式。
 
三、详细设计
 
1.物理数据类型
 
多项式的系数为整数（浮点数），指数为整数，所以物理数据类型可以为int等（采用模板）。
 多项式的项按照指数从大到小排列，相加运算时会改变项的个数。选用基于链表实现的线性表。
 ① 结点SNode的构造：结构体SNode在这个题中要存储的是一个多项式的项，其包含两个元素，多项式的系数和指数，所以我添加了一个结构体arrary作为一个二元组，包含系数（value），指数（element）将这个结构体类型的元素作为结点的数据元素
 伪代码：
 
struct arrary
 {
 	      E value;
 	      E element;
};
 struct SNode 
           {
                  arrary<E> elem;
                  SNode *next; 
};
 
② 基本操作：基于有序链表实现线性表ADT，要进行的基本操作有：
 Ⅰ构造线性表
 伪代码：
 
link()
{ init();}
 
Ⅱ摧毁线性表
 伪代码：
 
~link()
{removeall();}
 
流程：通过link类的一个私有函数removeall完成操作。
 
Ⅲ初始化线性表
 
伪代码：
 
void init()
    {
    	               curr=tail=head=new SNode<E>;
    	               linksize=0;
    }
 
Ⅳ把当前位置从前到后移动一个存储单元。
 伪代码：
 
void next()
{
			if(curr!=tail)
		    curr=curr->next;
}
 
流程：当前位置移动到下一个节点，只要把当前位置的指针curr的指向修改为他所指向的节点中的指针next的指向就可以做到，但是要注意表尾操作。
 Ⅴ移动当前位置到线性表表头。
 伪代码：
 
void moveToStart()
{curr=head;}
 
流程：把头节点的存储地址的值赋值给当前位置curr就可以实现当前位置头置。
 Ⅵ获取当前位置存储单元内的数据元素。
 伪代码：
 
arrary<E> getvalue()
{return curr->elem;}
 
流程：函数返回当前位置指向的节点中包含的数据元素。
 
Ⅶ向线性表插入一个数据元素（有序线性表的实现函数）。
 
伪代码：
 
void insert(arrary<E> elem)
    {
    	       for(curr=head;curr!=tail;curr=curr->next)
    	       {
    		        if(temp.element>curr->next->elem.element)break;
                }
    	       SNode<E>* tempnew =new SNode<E>;
    	       tempnew->elem.value=temp.value;
    	       tempnew->elem.element=temp.element;
    	       tempnew->next=curr->next;
                curr->next=tempnew;
    	       if(tail==curr)tail=curr->next;
    	       linksize++;
    }
 
流程：首先把当前位置设定在头指针的位置，之后开始用函数参数elem的element和当前位置的数据元素（也就是栅栏后面的节点的二元组中的第二个数）比较大小，如果找到了一个位置使得后面的节点中的指数小于要输入的节点的指数那么终止循环，如果没找到这样的位置，说明输入的项指数比已经有的所有项都要小，那么就会把这个位置定在表尾，之后让当前位置所指节点的next指针指向新的节点，也就是存储新项的地方，新节点的前两个参数就是函数的两个参数，指针肯定指向下一节点，若新节点是最后一个节点，也就是他存储的项的指数最小，那么要让表尾指针指向新节点 ，同时链表长度加一。
 
Ⅷ 获取线性表的长度。
 
伪代码：
 
int getsize()
    {return  linksize;}
 
流程：在每一次进行插入等操作时，都会有一个变量linksize发生变化，它记录了链表的节点数目，函数返回他就可以得到线性表长度。
 
Ⅸ修改当前存储单元的值。
 
伪代码：
 
void  change(arrary<E> temp)
    {
    	         curr->elem.value=temp.value;
    	         curr->elem.element=temp.element; 
    }
 
流程：为了实现两个多项式相加的操作同时又不影响链表的通用性，那么将需要修改的数据元素的值作为函数的参数，把原来的节点中的value系数和element指数全部修改为函数的参数。
 
2.输入和输出的格式
 
输入：
 ① 开始提示“请输入第一个一元多项式的项数:”，提示输入一个整数，之后提示"接下来 n行，分别输入每一项的系数和指数，如：3 2（其中3为系数，2为指数，中间以空格分隔）"。完成输入第一个多项式。
 ② 然后提示“请输入第二个一元多项式的项数:”，提示输入一个整数，之后提示"接下来 n行，分别输入每一项的系数和指数，如：3 2（其中3为系数，2为指数，中间以空格分隔）"。输入第二个多项式的输入。
 输出：
 ① 提示"第一个多项式为:"，之后打印第一个多项式多项式的排布，打印之后输出一行分隔符。
 ② 提示"第二个多项式为:"，之后打印第二个多项式多项式的排布，打印之后输出一行分隔符。
 ③ 提示"两个多项式的和为:"，之后打印两个多项式相加并存入第一个多项式线性表后的结果。
 
3.算法的具体步骤
 
（1）模块分析：
 
①第一个模块
 【1】第一个多项式的输入和输出：
 Ⅰ通过一个n代表第一个多项式的项数的输入进入第一个多项式的每一项系数和指数的输入，调用修改的插入函数实现数据的存入。
 
cin>>n;
cin>>temp.value>>temp.element;
a.insert(temp);
 
Ⅱ通过调用movetostart先把当前位置移动到表头，之后从头往后依次处理每个存储位置，特殊处理第一个输出还有系数为0的输出，调用getvalue和getelement实现输出。
 
a.movetostart();
a.getvalue();
 
【2】第二个多项式的输入和输出
 Ⅰ通过一个m代表第二个多项式的项数的输入进入第二个多项式的每一项系数和指数的输入，调用修改的插入函数实现数据的存入。
 
cin>>n;
cin>>temp.value>>temp.element;
b.insert(temp);
 
Ⅱ通过调用movetostart先把当前位置移动到表头，之后从头往后依次处理每个存储位置，特殊处理第一个输出还有系数为0的输出，调用getvalue和getelement实现输出。
 
b.movetostart();
b.getvalue();
 
②第二个模块（实现多项式的加法运算，并将结果保存到第一个多项式的线性表中）：首先对存储第二个多项式的线性表进行从头到尾的元素遍历，每一个第二个多项式中的元素都要再分别遍历第一个多项式中的元素，若查找到指数相同的项，那么调用change把第二个多项式中的系数加到第一个多项式中，如果没有找到，那就直接调用insert函数实现存入。
 b.movetoStart();
 a.movetoStart();
 如果查找到：
 
if(b.getvalue().element==a.getvalue().element)
{       arrary<int> temp2;
	 	   temp2.value=a.getvalue().value+b.getvalue().value;
	 	   temp2.element=a.getvalue().element;
a.change(temp2); 
}
 
如果没查找到那么：
 
arrary<int>temp;
temp.value=b.getvalue().value;
temp.element=b.getvalue().element;
a.insert(temp);
 
③第三个模块（输出两个多项式相加的结果）：和前文输出方法一致，通过调用movetoStart先把当前位置移动到表头，之后从头往后依次处理每个存储位置，特殊处理第一个输出还有系数为0的输出，调用getvalue和getelement实现输出。
 
a.movetoStart();
a.getvalue();
 
流程图：
 第一个模块：
 
 第二个模块：
 
 第三个模块：
 
 
4.算法的时空分析
 
第一个模块：对于第一个多项式的输入，首先要输入n个数对，存储时每个数对都要对已有的链表元素遍历一次，输入操作的时间代价根据化简规则略去低阶项和常数项，得到输入时间代价是Θ(n2)；输出是从头到尾依次输出，所以时间代价是Θ(n)，所以，输入并打印第一个多项式的时间代价是Θ(n2)；与第一个多项式相同输入第二个多项式，所以第二个多项式输入并打印的时间代价是Θ(m2)；综上，第一个模块的时间代价是Θ(max{ n2,m2 }）。
 第二个模块：在对应多项式A，多项式B的每一个值都去遍历一次，这个双重嵌套for循环的时间代价为Θ(nm),之后进入一个也在第一重for循环中的if解决是否要用到插入操作，那么这个语句的时间代价是Θ(n2)。
 所以总共的时间代价是Θ(max{nm,n2 }）。
 第三个模块:假设两个多项式相加之后的第一个多项式的长度为x，那么输出A的时间代价就是Θ(x)，第四个模块的时间代价就是Θ(x)。
 综上所述：整个算法的时间代价就是Θ(max{ nm,n2 }）
 
四、调试分析
 
1.调试方案设计
 
调试目的：用手工或编译程序等方法进行测试，修正语法错误和逻辑错误的过程。这是保证计算机信息系统正确性的必不可少的步骤。编完计算机程序，必须送入计算机中测试。根据测试时所发现的错误，进一步诊断，找出原因和具体的位置进行修正。对于本题目，根据调试过程及结果检测两个多项式加法运算相关函数过程及正确性。
 样例：（设计样例中的第一个样例）
 
（1）样例输入1：
 
4
3 2
4 5
1 1
2 3
3
-3 2
-4 5
2 4
 
（2）样例输出1：
 
第一个多项式为:
4x^5+2x^3+3x^2+1x^1
第二个多项式为:
-4x^5+2x^4-3x^2
两个多项式的和为:
2x^4+2x^3+1x^1
 
调试计划：该样例的设计中两个多项式存在系数互为相反数且指数相同的项，按照设计，当两个多项式进行相加运算时，第二个多项式的项会与第一个多项式中指数相同的项通过函数修改第一个项中对应的元素值，完成相加运算，同时第一个多项式的项数不会改变，及线性表长度不变，观察第一个多项式线性表的长度，验证设计过程的正确性。
 设置：在加法运算循环处设置断点，观察调试过程。
 
2.调试过程和结果，及分析
 
设置断点：
 
 开始调试：
 （1）当完成第一个模块输入之后，此时两个多项式线性表的长度均为项的个数，运行正常，结果如下图。
 
 （2）从设置断点进入for循环语句，开始进行两个多项式的相加操作，由于两个多项式的第一个项的指数相同，程序进入if语句，如下图。
 
 （3）和预测的结果相同，两个项的指数相同完成当前第一个项的相加操作之后，第一个多项式的线性表长度没有发生变化，如下图。
 
 （4）接下来对第二个多项式中的第二项即指数为4的项在第一个多项式中查找，与预测相同，当循环到最后一个时，此时j==3，没有发现相同的项，进入第二个if语句完成插入操作，第一个线性表的长度发生改变，变为5，如下图。
 
 （5）继续进行循环，第二个多项式中的第三项，根据预测与第一个多项式中的第四项相同，会同第一项完成相加时的操作相同，第一个多项式线性表长度不会改变，此时i=2，j=3,调试过程正确，如下图。
 
 （6）完成相加操作后，最后输出第一个多项式，得到两个多项式相加的结果，与预测结果相同，调试结果为正确，如下图。
 
 总结：调试结束，结果与预料一致，说明程序对这组数据的处理没有问题。
 
五、测试结果
 
（1） 测试样例1
 

 结论分析：两组多项式相加时，两个多项式中恰有相同指数项的系数互为相反数，即相加之后为0，能够实现正确计算。
 
（2） 测试样例2
 

 结论分析：输入的项的系数是0，输出未出现错误，不会把项为0的也输出出来，能够实现正确运算。
 
（3） 测试样例3
 

 结论分析：在两组多项式只有一项的情况下，并且这项的幂相等，输出为一项，程序计算结果正确。
 
（4） 测试样例4
 

 结论分析：当某个多项式所有项的系数均为零时，该多项式不会输出，满足系数为0的项不会输出的设计，最后的计算结果正确，程序运行正常。
 
（5） 测试样例5
 

 结论分析：本例是反例，若不符合要求同一个多项式不能有相同的幂的项存在，当储存一个多项式时会把指数相同的项当作多个项进行储存，运算时，也会把这些所有项的系数对第一个多项式中的第一个该指数的元素进行操作，完成相加，这也是符合当前该设计的计算过程的，即程序运行正常，由于不符合同一个多项式不能有相同的幂的项存在的要求，输出结果错误。
 
六、实验日志（选做）
 
实验时间
 2018.10.24-2018.10.30
 实验过程
 10.24
 19：30-21：40
 ① 完成需求分析模块。
 ② 完成概要设计模块。
 10.25
 12：20-15：50
 完成详细设计模块。
 21：00-22：44
 基本完成线性表ADT的设计和实现。
 10.26
 13：00-17：24
 ① 完成有序插入基本操作的设计与实现。
 ② 完成修改储存数据元素的值基本操作的设计与实现。
 ③ 完成源代码。
 10.27
 13：00-15：25
 完成调试分析模块
 10.30
 14：30-16：00
 针对预备报告进行了完善与修改。
 19：30-21：18
 ① 修改源代码。
 ② 调试修改后的源代码。
 ③ 完成最终报告。
 实验中遇到的问题及解决分析
 (1) 如何实现有序线性表？
 分析及解决：对于线性表的有序性，可以通过修改插入基本操作，在插入储存时实现有序储存，即实现了线性表的有序性。
 (2）使用模板 template 实现数据对象的多用性。出现报错报错(GCC): error: need ‘typename’ before ‘E::xxx’ because ‘E’ is a dependent scope
 分析及解决：通过查询，得知了这样两个概念——
 从属名称(dependent names): 模板(template)内出现的名称, 相依于某个模
 (template)参数, 如 E t;
 嵌套从属名称(nested dependent names):从属名称在 class 内呈嵌套装, 如
 E::const_iterator ci;
 如果不特定指出 typename, 嵌套从属名称, 有可能产生解析(parse)歧义.
 所以，任何时候在模板(template)中指涉一个嵌套从属类型名称, 需要在前一个
 位置, 添加关键字 typename;进行如下操作解决了问题
 (3）如何实现加法运算？
 分析及解决：我们实现这样一个算法过程——遍历操作，每一个第二个多项式中的元素都要再分别遍历第一个多项式中的元素，若查找到指数相同的项，那么调用change把第二个多项式中的系数加到第一个多项式中，如果没有找到，那就直接调用insert函数实现有序存入，完成加法运算。
 
实验心得
 实验设计比较完善，解决了基于有序链表实现多项式的输入输出和相加的功能，但是还是那个反例的问题怎么解决呢，我认为把两个多项式的项逐一存入另一个线性表中是一个好办法，这样的话，根据change函数，在每一次存入多项式的值的时候，新的线性表就构成了一个新的链表，那么就算多项式中有相同指数的项，到了存储进新的线性表中的时候，也会和前面已经存过的指数相同项进行一次系数的相加而不是增多一个节点，但是这个方法每次都要遍历前面已经存储过的节点时间代价有些大是它的缺点。
 
具体代码实现：
 数据结构——一元多项式的加法运算
 伪代码部分排版有点问题，请见谅！