链表应用之多项式相加

116 阅读 0 评论 77 点赞

我是靠谱客的博主小巧秀发，这篇文章主要介绍链表应用之多项式相加，现在分享给大家，希望可以做个参考。

题目来源:Wejudge#3988

题目

首先输入2个整数m和n（0<m, n<=1000000000）分别代表2个多项式的项数。

然后，输入m+n行数据，前m行表示第一个多项式，后n行表示第二个多项式

每行1个整数c和一个非负整数e（e>=0），分别表示多项式每一项的系数和指数（指数按升序排列）。

样例

输入

3 4
1 1
2 3
3 5
1 0
-6 1
1 2
-3 5

输出

x+2x^3+3x5
1-6x+x^2-3x5
1-5x+x^2+2x3

代码

复制代码

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode{
int
coef,index;
//数据域
struct LNode
*next;
//指针域
}LNode,*LinkList;
void create(LinkList &ll,int n);
void add(LinkList l1,LinkList l2,LinkList &L);
void print(LinkList L);
int main(){
int n,m;
while(~scanf("%d %d", &n , &m)){
LinkList l1,l2,l3;
create(l1, n);
create(l2, m);
add(l1,l2,l3);
print(l1);
print(l2);
print(l3);
}
return 0;
}
void create(LinkList &ll,int n)
{
ll=new LNode;
LNode *l=ll;
int a,b;
while(n--)
{
scanf("%d %d",&a,&b);
if(a==0)continue;
l->next=new LNode;
l=l->next;
l->coef=a,l->index=b;
l->next=NULL;
}
}
void add(LinkList l1,LinkList l2,LinkList &L)
{
int cc=0;
L=new LNode;
LNode *p=L;
l1=l1->next,l2=l2->next;
while(l1&&l2){
p->next=new LNode;
if(l1->index<l2->index){//指数比较,小的先进行 ,l1小 
p->next->coef=l1->coef;
p->next->index=l1->index;
l1=l1->next;
} else if(l1->index==l2->index){//指数相同的相加 
int u=l1->coef+l2->coef;
if(u==0){//为0 
p->next->coef=0;
p->next->index=0;
}else{//不为0 
p->next->coef=u;
p->next->index=l1->index;
}
l1=l1->next;
l2=l2->next;
}else{//l2小 
p->next->coef=l2->coef;
p->next->index=l2->index;
l2=l2->next;
}
p=p->next;
}
while(l1){
p->coef=l1->coef;
p->index=l1->index;
l1=l1->next;
p->next=new LNode;
p=p->next;
}
while(l2){
p->coef=l2->coef;
p->index=l2->index;
l2=l2->next;
p->next=new LNode;
p=p->next;
}
p->next=NULL;
}
void print(LinkList L)
{
int kk=0;
while(L->next!=NULL){
kk++;
L=L->next;
if(kk==1){//第一个数 
if(L->coef==0){//a=0
continue;
}else if(L->coef==1){//a=1
剩下都有b是0
1
其他的情况 
if(L->index==0){
printf("%d",L->coef);//就是1 
}else if(L->index==1){
printf("x");
}else{
printf("x^%d",L->index);
}
}else{//a是其他情况 
if(L->index==0){
printf("%d",L->coef);
}else if(L->index==1){
printf("%dx",L->coef);
}else{
printf("%dx^%d",L->coef,L->index);
}
}
} else{//不是第一个 
if(L->coef>=0){//正数和0 
if(L->coef==0){//a=0
continue;
}else if(L->coef==1){//a=1
剩下都有b是0
1
其他的情况 
if(L->index==0){
printf("+%d",L->coef);//就是1 
}else if(L->index==1){
printf("+x");
}else{
printf("+x^%d",L->index);
}
}else{//a是其他情况 
if(L->index==0){
printf("+%d",L->coef);
}else if(L->index==1){
printf("+%dx",L->coef);
}else{
printf("+%dx^%d",L->coef,L->index);
}
}
}else{
{
if(L->index==0){
printf("%d",L->coef);
}else if(L->index==1){
printf("%dx",L->coef);
}else{
printf("%dx^%d",L->coef,L->index);
}
}
}
}
}
printf("n");
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include<stdio.h>
#include<stdlib.h>
typedef struct LNode{
int
coef,index;
//数据域
struct LNode
*next;
//指针域
}LNode,*LinkList;
void create(LinkList &ll,int n);
void add(LinkList l1,LinkList l2,LinkList &L);
void print(LinkList L);
int main(){
int n,m;
while(~scanf("%d %d", &n , &m)){
LinkList l1,l2,l3;
create(l1, n);
create(l2, m);
add(l1,l2,l3);
print(l1);
print(l2);
print(l3);
}
return 0;
}
void create(LinkList &ll,int n)
{
ll=new LNode;
LNode *l=ll;
int a,b;
while(n--)
{
scanf("%d %d",&a,&b);
if(a==0)continue;
l->next=new LNode;
l=l->next;
l->coef=a,l->index=b;
l->next=NULL;
}
}
void add(LinkList l1,LinkList l2,LinkList &L)
{
int cc=0;
L=new LNode;
LNode *p=L;
l1=l1->next,l2=l2->next;
while(l1&&l2){
p->next=new LNode;
if(l1->index<l2->index){//指数比较,小的先进行 ,l1小 
p->next->coef=l1->coef;
p->next->index=l1->index;
l1=l1->next;
} else if(l1->index==l2->index){//指数相同的相加 
int u=l1->coef+l2->coef;
if(u==0){//为0 
p->next->coef=0;
p->next->index=0;
}else{//不为0 
p->next->coef=u;
p->next->index=l1->index;
}
l1=l1->next;
l2=l2->next;
}else{//l2小 
p->next->coef=l2->coef;
p->next->index=l2->index;
l2=l2->next;
}
p=p->next;
}
while(l1){
p->coef=l1->coef;
p->index=l1->index;
l1=l1->next;
p->next=new LNode;
p=p->next;
}
while(l2){
p->coef=l2->coef;
p->index=l2->index;
l2=l2->next;
p->next=new LNode;
p=p->next;
}
p->next=NULL;
}
void print(LinkList L)
{
int kk=0;
while(L->next!=NULL){
kk++;
L=L->next;
if(kk==1){//第一个数 
if(L->coef==0){//a=0
continue;
}else if(L->coef==1){//a=1
剩下都有b是0
1
其他的情况 
if(L->index==0){
printf("%d",L->coef);//就是1 
}else if(L->index==1){
printf("x");
}else{
printf("x^%d",L->index);
}
}else{//a是其他情况 
if(L->index==0){
printf("%d",L->coef);
}else if(L->index==1){
printf("%dx",L->coef);
}else{
printf("%dx^%d",L->coef,L->index);
}
}
} else{//不是第一个 
if(L->coef>=0){//正数和0 
if(L->coef==0){//a=0
continue;
}else if(L->coef==1){//a=1
剩下都有b是0
1
其他的情况 
if(L->index==0){
printf("+%d",L->coef);//就是1 
}else if(L->index==1){
printf("+x");
}else{
printf("+x^%d",L->index);
}
}else{//a是其他情况 
if(L->index==0){
printf("+%d",L->coef);
}else if(L->index==1){
printf("+%dx",L->coef);
}else{
printf("+%dx^%d",L->coef,L->index);
}
}
}else{
{
if(L->index==0){
printf("%d",L->coef);
}else if(L->index==1){
printf("%dx",L->coef);
}else{
printf("%dx^%d",L->coef,L->index);
}
}
}
}
}
printf("n");
}