单链表之一元多项式求和C++实现

2018-06-17 19:53:41来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

单链表之一元多项式求和

一元多项式求和单链表实现伪代码

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 }

三、运行示例结果

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:postgresql遇到的性能问题

下一篇:PostgreSQL流复制记录