多项式乘法是在多项式加法的基础上完成的。
1、多项式加法
1 #include<iostream>
2 using namespace std;
3 typedef struct lnode{
4 int coef;
5 int exp;
6 lnode *next;
7 }lnode;
8 class poly{
9 lnode *head;
10 public:
11 void create(int n);//创建n项的多项式
12 int comp(int a,int b);//比较函数
13 void addpoly(poly &ha,poly hb);
14 void print();
15 };
16 void poly::create(int n){
17 head=new lnode;
18 head->next=NULL;
19 lnode *p;
20 for(int i=0;i<n;i++){
21 p=new lnode;
22 cin>>p->coef>>p->exp;//升序输入,头插法
23 p->next=head->next;
24 head->next=p;
25 }
26 }
27 int poly::comp(int a,int b){
28 if(a>b)return -1;
29 else if(a==b)return 0;
30 else return 1;
31 }
//关键
32 void poly::addpoly(poly &ha,poly hb){
33 lnode *q=ha.head,*pa=ha.head->next, *pb=hb.head->next,*r;
34 while(pa&& pb)//pa，pb非空
35 switch(comp(pa->exp,pb->exp)){
36 case -1: q=pa; pa=pa->next;//pa>pb pa指数更大，链表中pa往右移
37 break;
38 case 0: pa->coef+=pb->coef;//pa = pb 先将指数相加
39 if(pa->coef==0) { //系数为0时
40 q->next=pa->next;
41 delete pa; //删除pa
42 pa=q; //后面有整体的pa=pa->next
43 }
44 else q=pa;
45 pa=pa->next;
46 pb=pb->next;//不为0时，pa，pb分别正常右移
47 break;
48 case 1: r=new lnode;//pa<pb，在表头插入pb
49 r->coef=pb->coef;
50 r->exp=pb->exp;
51 q->next=r;
52 r->next=pa;
53 q=r;
54 pb=pb->next;//勿忘pb右移
55 break;
56 }
57 while(pb!=NULL){//上述执行完pa后pb非空，将剩余pb项插入pa中，类似case 1操作
58 r=new lnode;
59 r->coef=pb->coef;
60 r->exp=pb->exp;
61 q->next=r;
62 r->next=pa;
63 q=r;
64 pb=pb->next;
65 }
66 }
67 void poly::print(){
68 lnode *p=head->next;
69 while(p){
70 cout<<p->coef<<' '<<p->exp<<' ';
71 p=p->next;
72 }
73 cout<<endl;
74 }
75 int main(void){
76 poly ha,hb;
77 ha.create(5);
78 hb.create(4);
79 ha.print();
80 hb.print();
81 ha.addpoly(ha,hb);
82 ha.print();
83
84 return 0;
85 }
2、多项式乘法
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef struct LNode {
4 int coef;
5 int exp;
6 LNode* next;//指针
7 };
8 class poly {
9 LNode* head;
10 public:
11 poly() { head = new LNode; head->next = NULL; }
12 void Create(int n);
13 int Comp(int a, int b);
14 void AddPoly(poly& ha, poly hb);//两项相加
15 void addpnode(poly& ha, LNode* x);//链表ha中添加x结点
16 void timespoly(poly& hc, poly ha, poly hb);//ha和hb相乘并将结果放入hc中
17 void Print();
18 };
19 void poly::Create(int n) {
20 head = new LNode;
21 head->next = NULL;//建立头结点
22 LNode* p;
23 for (int i = 0; i < n; i++) {
24 p = new LNode;
25 cin >> p->coef >> p->exp;//头插法输入
26 p->next = head->next;
27 head->next = p;
28
29 }
30
31 }
32
33 int poly::Comp(int a, int b) {
34 if (a > b)return -1;
35 else if (a == b)return 0;
36 else return 1;
37
38 }
39 void poly::AddPoly(poly& ha, poly hb) {
40 LNode* q = ha.head, * pa = ha.head->next, * pb = hb.head->next, * r;
41 while (pa && pb) {
42 switch (Comp(pa->exp, pb->exp)) {
43 case -1:q = pa;
44 pa = pa->next;
45 break;
46 //a>b
47 case 0://a=b
48 pa->coef += pb->coef;
49 if (pa->coef == 0) {
50 q->next = pa->next;
51 delete pa;
52 pa = q;
53 }
54 else q = pa;
55
56 pa = pa->next;
57 pb = pb->next;
58 break;
59
60 case 1://a<b,将pb插入到pa前面
61 r = new LNode;
62 r->coef = pb->coef;
63 r->exp = pb->exp;
64 r->next = pa;
65 q->next = r;
66 q = r;
67 pb = pb->next;
68 }
69 }
70 while (pb) {
71 //将hb剩余项复制到ha
72 r = new LNode;
73 r->coef = pb->coef;
74 r->exp = pb->exp;
75 q->next = r;
76 q = r;
77 pb = pb->next;
78 }
79 }
80 void poly::addpnode(poly& ha, LNode* x) {
81 cout<<"enter addpnode"<<endl;
82 LNode* q = ha.head, *pa = ha.head->next, * r;
83 if (pa == NULL) {
84 r = new LNode;
85 r->coef = x->coef;
86 r->exp = x->exp;
87 q->next = r;
88 r->next = pa;
89 q = r;
90 return;
91 }//pa为空，直接将x插入
92 while (pa) {
93 //cout<<"enter pa loop"<<endl;
94 switch (Comp(pa->exp, x->exp)) {
95 case -1:q = pa; pa=pa->next;//pa系数大于x，因为要找到指数小于等于x->exp的才能进行相加或插入操作，所以q和pa指针继续同步右移
96 if (pa == NULL) {
97 r = new LNode;
98 r->coef = x->coef;
99 r->exp = x->exp;
100 q->next = r;
101 r->next = pa;
102 q = r;
103 return;
104 //pa为空则直接在链表后面插入x
105
106 }break;
107 case 1://pa<x,在表头插入
108 r = new LNode;
109 r->coef = x->coef;
110 r->exp = x->exp;
111 q->next = r;
112 r->next = pa;
113 q = r;
114 pa=NULL;//这里一定要有pa=NULL否则pa还是指向之前用来比较的结点，循环不会结束，会一直插入r结点
115 break;
116
117 case 0://pa=x
118 pa->coef += x->coef;
119 if (pa->coef == 0) {
120 q->next = pa->next;
121 delete pa;
122 pa = q;
123 }//系数为0，删除pa
124 else q = pa;
125 pa = pa->next;//pa和q正常同步右移
126 break;
127
128 }
129
130 // cout<<"exit pa loop"<<endl;
131 }
132
133 //cout<<"exit addpnode"<<endl;
134
135
136 }
137 void poly::timespoly(poly& hc, poly ha, poly hb) {
138 //cout << "执行timespoly" << endl;
139 LNode* pa = ha.head->next, * pb = hb.head->next;
140 LNode* r;
141 while (pa) {
142 while (pb) {
143 r = new LNode;
144 r->coef = pa->coef * pb->coef;//系数相乘
145 r->exp = pa->exp + pb->exp;//指数相加
146 // cout<<"start addpnode"<<endl;
147 addpnode(hc, r);将r结点加入到hc链表中
148 // cout<<"end addpnode"<<endl;
149 pb = pb->next;
150
151 }
152 //cout<<"跳出pb"<<endl;
153 pb = hb.head->next;
154 pa = pa->next;
155 }
156 //cout<<"退出timspoly"<<endl;
157 }
158 void poly::Print() {
159 LNode* p = head->next;
160 while (p) {
161 cout << p->coef << " " << p->exp << " ";
162 p = p->next;
163
164 }
165 cout << endl;
166 }
167 int main() {
168 poly ha, hb, hc;
169 ha.Create(2);
170 hb.Create(2);
171 ha.Print();
172 hb.Print();
173 ha.timespoly(hc, ha, hb);
174 hc.Print();
175
176 return 0;
177 }
178
标签：pb,coef,多项式,poly,next,链表,pa,exp,乘法 From： https://www.cnblogs.com/Marcusss/p/17278912.html