1002. A+B for Polynomials

PS：这道题上周日就写好了，但是忘了发上来。

题解

题目是把两个多项式相加再按格式输出，我用的方法是用一个结构体数组储存指数和系数，其实就是一个顺序链表。

这道题因为之前在陈越姥姥的数据结构课做过类似的，所以做起来思路很清晰。不过还是卡了一会儿，甚至找了别人的代码看。最终发现自己的思路有以下缺陷：

1. 没有按格式输出。我想测试点里肯定有系数为整数的，一直没注意到，题目要求也没说得那么清楚，所以忽略了；
2. 没有考虑系数相加为0的情况。系数为0后这一项就消失了，这个之前应该有提过但是太不小心了。

附上自己的代码和测试情况：

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

struct Node{
	int Expon;
	double Coef;
};
typedef struct Node *Poly;

int cnt=0;		/* 用法不是很规范，但是懒得改了 */


Poly CreatePoly(int Num);
Poly BuildPoly(int Num);
Poly AddPoly(Poly p1, int k1, Poly p2, int k2);
void Print(Poly P);


int main()
{
	int k1, k2;
	Poly Pa, Pb, P;
	
	cin>>k1;
	Pa=BuildPoly(k1);
	cin>>k2;
	Pb=BuildPoly(k2);
	
	P=AddPoly(Pa, k1, Pb, k2);
	Print(P);
	
	return 0;
}

Poly CreatePoly(int Num)
{
	Poly P;
	P=(Poly)malloc(Num*sizeof(struct Node));
	return P;
}

Poly BuildPoly(int Num)
{
	int i;
	Poly P;
	
	P=CreatePoly(Num);
	
	for(i=0; i<Num; i++)
	{
		cin>>P[i].Expon>>P[i].Coef;
	}
	
	return P;
}

Poly AddPoly(Poly p1, int k1, Poly p2, int k2)
{
	int i, j, k;
	Poly P;
	
	P=CreatePoly(k1+k2);
	i=0, j=0, k=0;
	
	while(i<k1 && j<k2)
	{
		if(p1[i].Expon > p2[j].Expon)
		{
			P[k].Expon=p1[i].Expon;
			P[k].Coef=p1[i].Coef;
			k++;
			cnt++;
			i++;
		}
		else if(p1[i].Expon < p2[j].Expon)
		{
			P[k].Expon=p2[j].Expon;
			P[k].Coef=p2[j].Coef;
			k++;
			cnt++;
			j++;
		}
		else
		{
			if(p1[i].Coef+p2[j].Coef)
			{
				P[k].Expon=p1[i].Expon;
				P[k].Coef=p1[i].Coef+p2[j].Coef;
				k++;
				cnt++;
			}
			i++; j++;
		}
	}
	if(i==k1)
	{
		while(j<k2)
		{
			P[k].Expon=p2[j].Expon;
			P[k].Coef=p2[j].Coef;
			k++;
			cnt++;
			j++;	
		}
	}
	if(j==k2)
	{
		while(i<k1)
		{
			P[k].Expon=p1[i].Expon;
			P[k].Coef=p1[i].Coef;
			k++;
			cnt++;
			i++;
		}
	}
	
	if(cnt==0) return NULL;
	else       return P;
}
 
void Print(Poly P)
{
	int i;
	
	cout<<cnt;
	if(cnt!=0)
	{	
		for(i=0; i<cnt; i++)
		{
			printf(" %d %.1lf", P[i].Expon, P[i].Coef);			//  这个格式卡了8分 
		}
	}
}

情况基本这样，然后我再去看了别人的思路，也用的数组，但是没有用结构体，也没有分成几个函数做，初学者可能看不大懂。内存使用大家都差不多大，但是他的时间只有1ms。题目简单，就不分析他的题解了，附上链接。

http://blog.csdn.net/apie_czx/article/details/45309943