7-6 多项式的加法 (50 分)
用链表表示多项式，并实现多项式的加法运算
输入格式:
输入在第一行给出第一个多项式POLYA的系数和指数，并以0,0 结束第一个多项式的输入；在第二行出第一个多项式POLYB的系数和指数，并以0,0 结束第一个多项式的输入。
输出格式:
对每一组输入，在一行中输出POLYA+POLYB和多项式的系数和指数。
第二个测试点一直过不去
```c
#include<stdio.h>
#include<stdlib.h>
#define maxSize 100
struct List{
int data_1;
int data_2;
struct List *next;
};
struct List *creat(){
struct List *head=NULL;
struct List *new;
struct List *end;
new=(struct List*)malloc(maxSize*sizeof(struct List*));
head=new;
for(int i=0;;i++){
scanf("%d",&new->data_1);
getchar();
scanf("%d",&new->data_2);
end=new;
if((new->data_1==0)&&(new->data_2==0)){
new->next=NULL;
return head;
}
new = (struct List*)malloc(maxSize*sizeof(struct List*));
end->next = new;
}
}
void plb(struct List *head)
{
struct List *temp;
temp = head;
while (temp->next!=NULL)
{
if(temp->data_1==0){
temp=temp->next;
continue;
}
printf("%d,%d", temp->data_1,temp->data_2);
if (temp->next!=NULL)
printf(" ");
temp = temp->next;
}
}
int main(){
struct List *head_1,*head_2;
head_1 = creat();
head_2 = creat();
struct List *temp_1,*temp_2;
temp_1 = head_1;
temp_2 = head_2;
struct List *Head=NULL;
struct List *New;
struct List *End;
New=(struct List*)malloc(maxSize*sizeof(struct List*));
Head=New;
int count = 0;
while(temp_2->next!=NULL&&temp_1->next!=NULL){
if(temp_1->data_2<temp_2->data_2){
New->data_1 = temp_1->data_1;
New->data_2 = temp_1->data_2;
End = New;
New = (struct List *) malloc(maxSize * sizeof(struct List *));
End->next = New;
temp_1=temp_1->next;
continue;
}
else if(temp_1->data_2==temp_2->data_2) {
New->data_1 = temp_1->data_1 + temp_2->data_1;
New->data_2 = temp_1->data_2;
End = New;
New = (struct List *) malloc(maxSize * sizeof(struct List *));
End->next = New;
temp_1=temp_1->next;
temp_2=temp_2->next;
continue;
}
else if(temp_1->data_2>temp_2->data_2){
New->data_1 = temp_2->data_1;
New->data_2 = temp_2->data_2;
End = New;
New = (struct List *) malloc(maxSize * sizeof(struct List *));
End->next = New;
temp_2=temp_2->next;
continue;
}
}
if(temp_1->next!=NULL&&temp_2->next==NULL){
while(temp_1->next!=NULL){
New->data_1 = temp_1->data_1;
New->data_2 = temp_1->data_2;
End = New;
New = (struct List *) malloc(maxSize * sizeof(struct List *));
End->next = New;
temp_1=temp_1->next;
}
}
else if(temp_1->next==NULL&&temp_2->next!=NULL){
while(temp_2->next!=NULL){
New->data_1 = temp_2->data_1;
New->data_2 = temp_2->data_2;
End = New;
New = (struct List *) malloc(maxSize * sizeof(struct List *));
End->next = New;
temp_2=temp_2->next;
}
}
New->next=NULL;
plb(Head);
return 0;
}
```
仅供参考：
//链表实现一元多项式的加法减法
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
float coef; //系数
int expn; //指数
struct node *next;
} PolyNode;
typedef PolyNode* Polynomial;
Polynomial createPolynomial() { //创建多项式
PolyNode *p, *q, *head = (PolyNode *)malloc(sizeof(PolyNode));
head->next = NULL;
float coef;
int expn;
printf("输入该多项式每一项的系数和指数，每项一行，输入0 0结束！\n");
while (1) {
scanf("%f %d", &coef, &expn);
if (0.0==coef && 0==expn) break;
if (head->next) {
p = head;
while (p->next && expn < p->next->expn) p = p->next;
if (p->next) {
if (expn == p->next->expn) { //有相同指数的直接把系数加到原多项式
p->next->coef += coef;
if (-0.00001f < p->next->coef && p->next->coef < 0.00001f) { //若是相加后系数为0，则舍弃该节点
q = p->next;
p->next = q->next;
free(q);
}
} else {
q = (PolyNode*)malloc(sizeof(PolyNode));
q->coef = coef;
q->expn = expn;
q->next = p->next;
p->next = q;
}
} else {
p->next = (PolyNode*)malloc(sizeof(PolyNode));
p = p->next;
p->coef = coef;
p->expn = expn;
p->next = NULL;
}
} else {
head->next = (PolyNode*)malloc(sizeof(PolyNode));
head->next->coef = coef;
head->next->expn = expn;
head->next->next = NULL;
}
}
return head;
}
Polynomial polyAdd(Polynomial poly1, Polynomial poly2) { //多项式相加 poly1+poly2形成一个新的多项式
Polynomial poly = (PolyNode*)malloc(sizeof(PolyNode)); //和多项式的头节点
poly->next = NULL;
PolyNode *p, *q, *r;
r = poly;
p = poly1->next;
q = poly2->next;
while (p&&q) {
if (p->expn > q->expn) {
r->next = (PolyNode*)malloc(sizeof(PolyNode));
r = r->next;
r->coef = p->coef;
r->expn = p->expn;
p = p->next;
} else if (p->expn < q->expn) {
r->next = (PolyNode*)malloc(sizeof(PolyNode));
r = r->next;
r->coef = q->coef;
r->expn = q->expn;
q = q->next;
} else {
float m = p->coef + q->coef;
if (!(-0.00001f <m && m < 0.00001f)) {
r->next = (PolyNode*)malloc(sizeof(PolyNode));
r = r->next;
r->coef = m;
r->expn = p->expn;
}
q = q->next;
p = p->next;
}
}
while (p) {
r->next = (PolyNode*)malloc(sizeof(PolyNode));
r = r->next;
r->coef = p->coef;
r->expn = p->expn;
p = p->next;
}
while (q) {
r->next = (PolyNode*)malloc(sizeof(PolyNode));
r = r->next;
r->coef = q->coef;
r->expn = q->expn;
q = q->next;
}
r->next = NULL;
return poly;
}
Polynomial polySubtract(Polynomial poly1, Polynomial poly2) { //多项式减法 poly1-poly2形成一个新的多项式
//把poly2的系数取相反数，形成一个新的多项式
Polynomial poly = (PolyNode*)malloc(sizeof(PolyNode)); //构造头节点
PolyNode *p, *q;
p = poly;
q = poly2->next;
while (q) {
p->next = (PolyNode*)malloc(sizeof(PolyNode));
p = p->next;
p->coef = -(q->coef); //系数取反
p->expn = q->expn;
q = q->next;
}
p->next = NULL;
Polynomial poly3 = polyAdd(poly1, poly); //利用加法
return poly3;
}
void printPoly(Polynomial poly) { //打印多项式
if (poly && poly->next) {
PolyNode *p = poly->next; //p指向第一个节点
while (p->next) {
if (1!=p->expn) printf("%g X^%d", p->coef, p->expn);
else printf("%g X" , p->coef );
p = p->next;
if (p) {
if (p->coef > 0) printf(" +");
else printf(" ");
}
}
if (p->expn == 0)
printf("%g", p->coef); //打印常数项
else {
if (1!=p->expn) printf("%g X^%d", p->coef, p->expn);
else printf("%g X" , p->coef );
}
printf("\n");
} else {
printf("0\n");
}
}
void freePoly(Polynomial poly) { //释放内存
if (poly && poly->next) {
PolyNode *p, *q;
p = poly;
while (p) {
q = p->next;
free(p);
p = q;
}
}
poly = NULL;
}
int main() {
printf("用链表实现多项式的加减法\n");
Polynomial poly1, poly2, poly3;
printf("创建多项式一\n");
poly1 = createPolynomial();
printf("创建多项式二\n");
poly2 = createPolynomial();
printf(" 多项式一：");printPoly(poly1);
printf(" 多项式二：");printPoly(poly2);
poly3 = polyAdd(poly1, poly2);
printf("两多项式相加，和为：");printPoly(poly3);
freePoly(poly3);
poly3 = polySubtract(poly1, poly2);
printf("两多项式相减，差为：");printPoly(poly3);
freePoly(poly3);
freePoly(poly2);
freePoly(poly1);
system("pause");
return 0;
}
//用链表实现多项式的加减法
//创建多项式一
//输入该多项式每一项的系数和指数，每项一行，输入0 0结束！
//4 9
//3 6
//2 5
//0 0
//创建多项式二
//输入该多项式每一项的系数和指数，每项一行，输入0 0结束！
//4 9
//3 6
//2 5
//0 0
// 多项式一：4 X^9 +3 X^6 +2 X^5
// 多项式二：4 X^9 +3 X^6 +2 X^5
//两多项式相加，和为：8 X^9 +6 X^6 +4 X^5
//两多项式相减，差为：0
//请按任意键继续. . .