#include<iostream>
using namespace std;
int a[100][2], b[100][2], sum[100][2];
int n, m;
int main()
{
cin >> n;//输入第一个多项式的项数
for (int i = 0; i < n; i++)
{
cin >> a[i][0] >> a[i][1];//分别输入系数和指数
}
cin >> m;//输入第二个多项式的项数
for (int i = 0; i < m; i++)
{
cin >> b[i][0] >> b[i][1];//分别输入系数和指数
}
int x = 0, y = 0, s = 0;//定位a,b,sum数组的下标指向
while (x < n && y < m)//当x,y在项数数量范围内,则比较两个多项式的大小
{
if (a[x][1] == b[y][1])//如果二者的指数相同
{
sum[s][0] = a[x][0] + b[y][0];//则系数相加
if (sum[s][0] != 0)//如果系数不等于0
{
sum[s][1] = a[x][1];//则指数落系下来
s++;//指针往后移动
}
x++, y++;//指针往后移动
}
else if (a[x][1] > b[y][1])//如果a多项式的指数比b的多项式的指数大
{
sum[s][0] = a[x][0];//则将a的系数和指数都落到sum中
sum[s][1] = a[x][1];
s++, x++;//a和sum的指针往后移动
}
else//如果b的多项式的指数比a的多项式的指数大
{
sum[s][0] = b[y][0];//则将b的系数和指数都落到sum中
sum[s][1] = b[y][1];
s++, y++;//b和sum的指针往后移动
}
}
if (x == n && y < m)//如果a没有项数可以比较
{
for (int i = y; i < m; i++)//则将b剩余的项的系数和指数都落下来
{
sum[s][0] = b[i][0];
sum[s][1] = b[i][1];
s++;
}
}
if (y == m && x < n)//如果b没有项数可以比较
{
for (int i = x; i < n; i++)//则将a剩余的项的系数和指数都落下来
{
sum[s][0] = a[i][0];
sum[s][1] = a[i][1];
s++;
}
}
for (int i = 0; i < s; i++)
{
if (i == 0)
{
cout << sum[i][0] << " " << sum[i][1];
}
else
{
cout << " " << sum[i][0] << " " << sum[i][1];
}
}
if (s == 0)
{
cout << 0 << " " << 0;
}
return 0;
}
#include<iostream>
#include<malloc.h>
using namespace std;
typedef struct node {
int coef;//系数
int exp;//指数
node* next;//在c++中支持node*这种写法
}list;
node* newNode(int c, int e)//创建一个新结点
{
node* temp = (node*)malloc(sizeof(node));
temp->coef = c;//系数
temp->exp = e;//指数
temp->next = NULL;
return temp;
}
list* createPoly(int n)//创建长度为n的链表
{
list* L = NULL;//创建一个指针表示链表
if (n == 0)//如果链表的长度为0,则直接返回
{
return L;
}
else
{
L = (list*)malloc(sizeof(node));//如果链表的长度不是0,则分配空间
}
int ac = 0;//初始化系数
int ae = 0;//初始化指数
node* lastp = L;//创建尾指针
node* temp = NULL;//创建一个指针用来接收新插入的结点
for (int i = 0; i < n; i++)
{
cin >> ac >> ae;//输入系数,指数
temp = newNode(ac,ae);//接收这个新的结点
lastp->next = temp;//尾插入新的结点
lastp = temp;//更新尾结点
}
return L;//返回这条链表
}
list* addPoly(list* A, list* B)//将两个多项式相加
{
if (!A->next)return B;
if (!B->next)return A;
node* pa = A->next;//pa指向A的第一项
node* pb = B->next;//pb指向B的第一项
list* sum = (list*)malloc(sizeof(node));//创建一个计算总和的链表
sum->next = NULL;//初始化
node* lastp = sum;//尾结点
node* temp = NULL;//创建一个临时结点
while (pa && pb)//如果满足二者的长度在多项式内
{
if (pa->exp == pb->exp)//并且这一项的指数相同
{
if (pa->coef + pb->coef != 0)//并且相加还不等于0
{
temp = newNode(pa->coef + pb->coef, pa->exp);//那么就得到这个系数相加后的结点
lastp->next = temp;//尾插入总和链表
lastp = temp;
}
pa = pa->next;//指针向后移动
pb = pb->next;
}
else if (pa->exp > pb->exp)//如果pa的指数比pb的指数大
{
temp = newNode(pa->coef, pa->exp);//将pa落下来
lastp->next = temp;//尾插
lastp = temp;
pa = pa->next;//移动
}
else//如果pa的指数比pb小,同理
{
temp = newNode(pb->coef, pb->exp);
lastp->next = temp;
lastp = temp;
pb = pb->next;
}
}
if (pa == NULL && pb != NULL)//如果pa指向空,将pb后面的全部落下来
{
lastp->next = pb;
}
if (pb == NULL && pa != NULL)//同理
{
lastp->next = pa;
}
return sum;
}
void printPoly(list*L)//打印链表
{
if (!L->next)//如果链表为空,则直接打印0 0
{
cout << "0 0";
}
else//如果链表不为空
{
node* p = L->next;//p指向第一个结点
int i = 0;
while (p)
{
if (i == 0)
{
cout << p->coef << " " << p->exp;
i++;
}
else
{
cout << " " << p->coef << " " << p->exp;
}
p = p->next;
}
}
}
int main()
{
int n, m;
cin >> n;
list* La = createPoly(n);//创建A链表
cin >> m;
list* Lb = createPoly(m);//创建B链表
list* result = addPoly(La, Lb);//计算
printPoly(result);//打印
return 0;
}