單鏈表之一元多項式求和C++實現

單鏈表之一元多項式求和一元多項式求和單鏈表實現偽代碼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 插到結 ...

單鏈表之一元多項式求和

一元多項式求和單鏈表實現偽代碼

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 }

三、運行示例結果