1286 - 算法2-23：一元多项式加法

提示

	提示：


	1、由于多项式元素的重要信息在系数和指数，所以可以定义结点类型为含两个整数的结构体，一个代表系数而另一个代表指数。 2、定义完数据类型后，主要的就是怎么读取数据了。由于每个多项式占一行，所以可以用gets来读取一行，并判断是否为空行：while(gets(strA) && strlen(strA))...然后就将字符串中的数据转换为多项式类型。此时使用到一个字符串处理函数char * strtok ( char * str, const char * delimiters )。这个函数的主要功能是将字符串str按delimiters中的字符分割。使用这个字符串处理函数时注意在处理某个字符串时首次使用时传递的参数是字符串指针而以后在使用时传递的参数是NULL。 3、下面的算法与有序序列有序合并算法类似。因为是多次循环，如果里面含有迭代变量（i，j之类的）注意下次循环时初值对不对。


	总结：


	多项式加法的算法与有序序列有序合并的算法类似，注意多项式元素类型的定义即可。

C语言解答

#include<stdio.h>
#include<string.h>
typedef struct
{
	int xishu;
	int zhishu;
}elemtype;
int main()
{
	elemtype a[100],b[100],c[200];
	int lena,lenb,lenc;
	char s1[101],s2[101],*t;
	int i,j;
	while(gets(s1) && strlen(s1))
	{
		gets(s2);
		lena=lenb=lenc=0;
		t=strtok(s1," \n\t");
		while(t)
		{
			sscanf(t,"%d",&a[lena].xishu);
			t=strtok(NULL," \n\t");
			sscanf(t,"%d",&a[lena].zhishu);
			t=strtok(NULL," \t\n");
			lena++;
		}
		t=strtok(s2," \n\t");
		while(t)
		{
			sscanf(t,"%d",&b[lenb].xishu);
			t=strtok(NULL," \n\t");
			sscanf(t,"%d",&b[lenb].zhishu);
			t=strtok(NULL," \t\n");
			lenb++;
		}
		i=j=0;
	while(i<lena && j<lenb)
	{
		if(a[i].zhishu>b[j].zhishu)
		{
			c[lenc].zhishu=a[i].zhishu;
			c[lenc].xishu=a[i].xishu;
			++i;++lenc;
		}
		else if(a[i].zhishu<b[j].zhishu)
		{
			c[lenc].zhishu=b[j].zhishu;
			c[lenc].xishu=b[j].xishu;
			++j;++lenc;
		}
		else if(a[i].zhishu==b[j].zhishu)
		{
			if(a[i].xishu+b[j].xishu)
			{
			c[lenc].zhishu=a[i].zhishu;
			c[lenc].xishu=a[i].xishu+b[j].xishu;
			++lenc;
			}
			++i;++j;
		}
	}
	while(i<lena)
	{
		c[lenc].xishu=a[i].xishu;
		c[lenc].zhishu=a[i].zhishu;
		++lenc;
		++i;
	}
	while(j<lenb)
	{
		c[lenc].xishu=b[j].xishu;
		c[lenc].zhishu=b[j].zhishu;
		++lenc;
		++j;
	}
	for(i=0;i<lenc;i++)
	    printf("%d %d ",c[i].xishu,c[i].zhishu);
	printf("\n");
	}
	return 0;
}

C++解答

#include <stdio.h>
#include <string.h>

struct ElemType{		// 定义多项式的每一项类型
	int coef;			// 系数
	int expn;			// 指数
};

int main(){

	ElemType a[110], b[110], r[220];	// 定义两个多项式以及他们的结果
	int lenA, lenB, lenR;				// 定义多项式 a,b,r 的项数
	char strA[1000], strB[1000], *tmp;	// 定义用来读取多项式的字符串，待会分解为整数
	int i, j;
	while(gets(strA) && strlen(strA)){	// 注意判断字符串 strA 的长度，防止有空行
		gets(strB);						// 读入字符串 strB
		lenA = lenB = lenR = 0;			// 首先令各多项式的项数为 0

		// 以下将字符串 a 放置到多项式 a 中
		tmp = strtok(strA, " \t\n");			// 注意这里传入的是字符串 strA
		while(tmp){
			sscanf(tmp, "%d", &a[lenA].coef);	// 从字符串中读取一个系数
			tmp = strtok(NULL, " \t\n");		// 注意这里传入的是 NULL
			sscanf(tmp, "%d", &a[lenA].expn);	// 从字符串中读取一个指数
			tmp = strtok(NULL, " \t\n");
			lenA++;								// 多项式项数加 1
		}

		// 以下将字符串 b 放置到多项式 b 中，操作类似上面的步骤
		tmp = strtok(strB, " \t\n");
		while(tmp){
			sscanf(tmp, "%d", &b[lenB].coef);
			tmp = strtok(NULL, " \t\n");
			sscanf(tmp, "%d", &b[lenB].expn);
			tmp = strtok(NULL, " \t\n");
			lenB++;
		}

		// 下面是进行多项式的加法，算法类同有序序列的有序合并
		i = j = 0;								// 注意这里每次循环时值要赋为0，否则下次循环就值就会有问题
		while(i<lenA && j<lenB){
			if(a[i].expn > b[j].expn){			// 如果 a 的某一项比 b 的某一项指数高，则结果应加入 a 这一项
				r[lenR].coef = a[i].coef;
				r[lenR].expn = a[i].expn;
				i++;
				lenR++;
			}else if(a[i].expn < b[j].expn){	// 如果 a 的某一项比 b 的某一项指数低，则结果应加入 b 这一项
				r[lenR].coef = b[j].coef;
				r[lenR].expn = b[j].expn;
				j++;
				lenR++;
			}else if(a[i].expn == b[j].expn){	// 如果 a 的某一项和 b 的某一项指数相等，
				if(a[i].coef + b[j].coef){		// 如果两项的系数和不为 0，则结果加上它们的和，否则就忽略
					r[lenR].coef = a[i].coef + b[j].coef;
					r[lenR].expn = a[i].expn;
					lenR++;
				}
				i++;
				j++;
			}
		}

		// 结果加入多项式 a 中剩下的部分
		while(i < lenA){
			r[lenR].coef = a[i].coef;
			r[lenR].expn = a[i].expn;
			i++;
			lenR++;
		}
		// 结果加入多项式 b 中剩下的部分
		while(j < lenB){
			r[lenR].coef = b[j].coef;
			r[lenR].expn = b[j].expn;
			j++;
			lenR++;
		}

		// 显示多项式的结果
		for(int i=0;i<lenR;i++){
			printf("%d %d ", r[i].coef, r[i].expn);
		}
		// 换行
		putchar('\n');
	}

	return 0;
}