单链表之一元多项式求和
一元多项式求和单链表实现伪代码
1、工作指针 pre、p、qre、q 初始化
2、while(p 存在且 q 存在)执行下列三种情况之一:
2.1、若 p->exp < q->exp:指针 p 后移;
2.2、若 p->exp > q->exp,则
2.2.1、将结点 q 插到结点 p 之前
2.2.2、指针 p 指向他原指结点的下一个结点;
2.3、若 p->exp == q->exp,则
2.3.1、p->coef = p->coef + q->coef
2.3.2、若 p->coef == 0,则执行下列操作,否则指针 p 后移,
2.3.2.1、删除结点 p
2.3.2.2、使指针 p 指向它原指结点的下一个结点
2.3.3、删除结点 q
2.3.4、使指针 q 指向它原指结点的下一个结点
3、如果 q 不为空,将结点 q 链接在第一个单链表的后面。
一、一元多项式求和单链表实现头文件:PolynomialOfOneIndeterminateAdd.h
1 //一元多项式求和头文件
2 #include<iostream>
3 using namespace std;
4 template<class DataType>
5 //定义单链表结点
6 struct Node
7 {
8 //数据域:非零项的系数和指数
9 DataType coef, exp;
10 //指针域
11 Node<DataType> *next;
12 };
13 //定义存放一元多项式的类
14 template<class DataType>
15 class Linklist
16 {
17 private:
18 Node<DataType> *first;
19 //一元多项式的项数
20 int size;
21 public:
22 //构造函数
23 Linklist();
24 //初始化一元多项式
25 void Init();
26 //输出一元多项式
27 void Print();
28 //定义一元多项式的的加法操作
29 Linklist<DataType> operator+(Linklist &p2);
30 };
31
32
33
34 //构造函数
35 template<class DataType>
36 Linklist<DataType>::Linklist()
37 {
38 first = new Node<DataType>;
39 first = NULL;
40 size = 0;
41 }
42
43
44
45 //实现一元多项式单链表的初始化
46 template<class DataType>
47 void Linklist<DataType>::Init()
48 {
49 cout << "多项式的元素个数为:";
50 cin >> size;
51 DataType x, y;
52 cout << "请输入第1项的系数:";
53 cin >> x;
54 cout << "请输入第1项的指数:";
55 cin >> y;
56 Node<DataType> *m;
57 m = new Node<DataType>;
58 m->coef = x;
59 m->exp = y;
60 m->next = NULL;
61 first = m;
62 for (int i = 2; i <= size; i++)
63 {
64 cout << "请输入第" << i << "项的系数:";
65 cin >> x;
66 cout << "请输入第" << i << "项的指数:";
67 cin >> y;
68 Node<DataType> *n;
69 n = new Node<DataType>;
70 n->coef = x;
71 n->exp = y;
72 n->next = NULL;
73 m->next = n;
74 m = n;
75 }
76 }
77
78
79
80 //实现一元多项式单链表实的输出
81 template<class DataType>
82 void Linklist<DataType>::Print()
83 {
84 Node<DataType> *m = first;
85 while (m != NULL)
86 {
87 if (m == first)
88 {
89 if (m->coef != 0 && m->exp != 0)
90 {
91 cout << m->coef << "x^" << m->exp;
92 }
93 else if (m->coef != 0 && m->exp == 0)
94 {
95 cout << m->coef;
96 }
97 }
98 else
99 {
100 if (m->coef > 0 && m->exp != 0){
101 cout << "+" << m->coef << "x^" << m->exp;
102 }
103 else if (m->coef<0 && m->exp != 0)
104 {
105 cout << m->coef << "x^" << m->exp;
106 }
107 else if (m->coef>0 && m->exp == 0)
108 {
109 cout << "+" << m->coef;
110 }
111 else if (m->coef < 0 && m->exp == 0)
112 {
113 cout << m->coef;
114 }
115 }
116 m = m->next;
117 }
118 cout << endl;
119 }
120
121
122
123 //实现一元多项式单链表的相加
124 template<class DataType>
125 Linklist<DataType> Linklist<DataType>::operator+(Linklist &p2)
126 {
127 //声明工作指针
128 Node<DataType> *pre, *p, *qre, *q;
129 //初始化工作指针
130 pre = this->first;
131 p = pre->next;
132 qre = p2.first;
133 q = qre->next;
134 while (p != NULL&&q != NULL)
135 {
136 //p->exp < q->exp:指针 p 后移
137 if (p->exp < q->exp)
138 {
139 pre = p;
140 p = p->next;
141 }
142 //p->exp > q->exp:将结点 q 插到结点 p 之前,指针 p 指向他原指结点的下一个结点
143 if (p->exp > q->exp)
144 {
145 Node<DataType> *s;
146 s = q->next;
147 pre->next = q;
148 q->next = p;
149 q = s;
150 }
151 //p->exp == q->exp:
152 if (p->exp == q->exp)
153 {
154 //p->coef = p->coef + q->coef
155 p->coef = p->coef + q->coef;
156 if (p->coef == 0)
157 {
158 //使指针 p 指向它原指结点的下一个结点
159 pre->next = p->next;
160 //删除结点 p
161 delete p;
162 p = p->next;
163 }
164 else
165 {
166 pre = p;
167 p = pre->next;
168 }
169 //使指针 q 指向它原指结点的下一个结点
170 qre->next = q->next;
171 //删除结点 q
172 delete q;
173 q = qre->next;
174 }
175 }
176 //如果 q 不为空,将结点 q 链接在第一个单链表的后面。
177 if (q != NULL)
178 {
179 pre->next = q;
180 delete p2.first;
181 }
182 return *this;
183 }
二、测试一元多项式单链表实现的源程序:TestPolynomialOfOneIndeterminateAdd.cpp
1 #include<iostream>
2 //引入一元多项式之单链表实现的头文件
3 #include "PolynomialOfOneIndeterminateAdd.h"
4 using namespace std;
5
6 int main()
7 {
8 //声明一元多项式单链表
9 Linklist<int> p1, p2, p3;
10 cout << "请按指数由小到大的顺序定义多项式A(x):" << endl;
11 p1.Init();
12 cout << "输入的多项式A(x)为:";
13 p1.Print();
14 cout << "n请按指数由小到大的顺序定义多项式B(x):" << endl;
15 p2.Init();
16 cout << "输入的多项式B(x)为:";
17 p2.Print();
18 //一元多项式相加
19 p3 = p1 + p2;
20 cout << "n多项式A(x)和多项式B(x)的和为:" << endl;
21 p3.Print();
22 return 0;
23 }
三、运行示例结果
原文链接: https://www.cnblogs.com/zfc-java/p/6661458.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/251935
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!