数据结构学习（C++）——单链表应用（一元多项式【1】）
happycock（原作）
转自CSDN
总算到了这里，这时，你会很得意的说，辛辛苦苦学的单链表总算知道能干点什么了。但是很不幸，如果你和我一样看的是那本书，到这里，你可能比学双向链表时还要痛苦。如果你是按照书上的介绍一步一步做到这里，你能把书上的多项式加法函数调试出来，我对你致以十二分的敬意。<?xml:namespace prefix = o ns =
"urn:schemas-microsoft-com:office:office" />
说到这里，我想起来我发单链表的时候，有人给我建议说：最好把链表和链表位置这两个分开。没错，C++标准库是这么做的，而我也不是什么专家，也不能证明什么优劣；但是，对于初学者来说，一个类总比两个类好操作。我不清楚原书这部分的程序究竟调没调试，但这种语句我是绝对看不懂的：
ListNode<Term> *pa,
*pb, *pc, *p;
ListIterator<Term> Aiter(ah.poly);
ListIterator<Term>
Biter(ah.poly);
pa = pc = Aiter.First(); pb = p =
Biter.First();
………………………..
pa->coef = pa->coef + pb->coef;
p = pb; pb = Biter.Next(); delete p;
如果你没有原书，我来解释一下。pa,
pb, p 究竟指向什么？你说这很清楚，ListNode<Term>这样的节点呗。但按照原书的定义，ListIterator::First()等等函数返回是指向data域的指针，他们怎么能直接赋值？到了下面更乱了，pb指向的区域直接分解出了Term的数据成员，也就是说是指向Term结构的；然后让ListNode<Term>类型的指针p指向这个Term结构，最后，居然把这个结构delete了，天啊，ListNode<Term>这样的节点的data域被delete了！
如果从基本的节点操作入手，谁也不会弄的这么乱。但正因为又多了一个类，很多事就疏忽了。所以，我并不怀疑标准库的做法，只是对于初学者，同一时间最好只对一个类操作。我以我的定义为基础，重新完成了这段程序。我并不欣赏原位操作的多项式加法（＋），PolyA+PolyB，然后B就嗖的一下没了，A就多了一堆（也可能少了一堆）；你作intJ+intK的时候怎么没见J和K有什么变化。与其这样，重载“+”还不如写成PolyA.Add(PolyB)或者PolyAdd(PolyA,PolyB)。
#ifndef Polynomial_H
#define Polynomial_H
#include
"List.h"
class Term
{
public:
int
coef;
int exp;
Term() : coef(0), exp(0) {}
Term(int c, int e) :
coef(c), exp(e) {}
Term(int c) :
coef(c), exp(0) {}
};
class Polynomial : List<Term>
{
public:
void Input()
{
cout << endl << "输入多项式的各项系数和指数";
cout << endl << "注意：请按降序输入各项,输入系数0表示结束" <<
endl;
int
coef, exp;
for(int i = 1; ;
i++)
{
cout << "第" << i << "项的系数：";
cin >>
coef;
if
(coef)
{
cout << "指数：";
cin >> exp;
Term
term(coef, exp);
Insert(term);
}
else break;
}
}
void Print()
{
cout <<
endl;
First();
if
(!IsEmpty())
{
Term *p = Next();
cout << p->coef;
if (p->exp)
{
cout << "x";
if (p->exp != 1) cout << "^" << p->exp;
}
while (Next() != NULL)
{
p = Get();
if (p->coef > 0) cout << "+";
cout << p->coef;
if (p->exp)
{
cout << "x";
if (p->exp != 1) cout << "^" << p->exp;
}
}
}
cout <<
endl;
}
friend void PolyAdd (Polynomial &polyA, Polynomial &polyB)
{
Node<Term>
*pA, *pB;
polyA.First();polyB.First();
pA = polyA.pNext();pB =
polyB.pNext();
while
(pA != NULL && pB !=NULL)
{
if
(pA->data.exp == pB->data.exp)
{
pA->data.coef =
pA->data.coef + pB->data.coef;
polyB.Remove();
if
(!pA->data.coef) polyA.Remove();
else
polyA.pNext();
}
else
{
if
(pA->data.exp > pB->data.exp)
{
polyB.pRemove();
polyA.InsertBefore(pB);
}
else if
(pA->data.exp < pB->data.exp) polyA.pNext();
}
pA = polyA.pGet();pB =
polyB.pGet();
}
if
(pA == NULL)
{
polyA.pGetPrior()->link = pB;
polyB.pGetPrior()->link = NULL;
}
}
};
#endif
【说明】对于多项式，通常我们都是降序书写的，于是我就要求降序输入。但是对于做加法来说，确实升序的要方便一些，于是，实际上到了内部，就变成升序的了。对于输出格式（从C的时候我就不喜欢做这个），尽量照顾习惯，但是当非常数项系数为1的时候还是会输出系数的，我实在不想把一个实际应用中根本拿不出台的输出函数搞的很复杂。为我编起来方便，输出变成了升序的，请多包含。测试程序就不给了，很简单。在续篇中，我将完成一元多项式“＋”“－”“×”“＝”的重载——为什么没有“÷”，这种运算我拿笔算都不麻利，编起来就更闹心了，我还清楚的记得拿汇编写多字节除法程序时的痛苦。到了下一篇，你就可以这样写了a=b+c*d;a.Print();
数据结构学习（C++）——单链表应用（一元多项式【2】）
按照原书的安排，对多项式的讲解到上一篇就应该结束了，但我还想做一些延伸。比如说，你很清楚多项式的系数肯定不总是整数，但为什么用整型呢？我看到原书用的是整型，我也有这个疑问。但是，一旦动起手来，就会发现改成浮点不仅仅只是在定义Term时把int
coef;改成float
coef;很多的细节都要考虑到（给个提示，你知道浮点零是多少吗）。我试了一下，最后放弃了；理由是，写这些只是为了学习，没必要搞的那么复杂，能说明问题就可以了。<?xml:namespace prefix = o ns =
"urn:schemas-microsoft-com:office:office" />
在下面将会有些重载运算符的例子，我们的工作将是使多项式的运算看起来更符合书写习惯。完成这些是我觉得我擅自将原书的“＋”改成了PolyAdd()，总要给个交待吧。很快你就会看到原位运算的多项式加法在多项式运算中有多么重要，往下看之前，请确保弄懂了上一篇的内容。
下面将完成单链表的赋值运算的重载，请把这部分加到List类的public部分。的确，这部分也可以放在多项式类里实现；但是，复制一个多项式实际上就是复制一个单链表，与其单单做一个多项式赋值，还不如完成单链表的赋值，让派生类都能共享。
operator = (const List<Type> &l)
{
MakeEmpty();
for (Node<Type> *p =
l.first->link; p != NULL; p = p->link) LastInsert(p->data);
}
还记得List类的private里面的这个List(const List<Type> &l)吗？当初怕它惹祸，直接将它禁用了，既然现在=都能用了，为了这种语法List<Type> b = a;顺便也把它完成了吧。现在可以把它从private放到public了。
List(const List<Type> &l)
{
first = current = last = new Node<Type>; prior = NULL;
for (Node<Type> *p =
l.first->link; p != NULL; p = p->link) LastInsert(p->data);
}
friend Polynomial operator + (Polynomial &polyA, Polynomial &polyB)
{
Polynomial tempA = polyA;Polynomial tempB =
polyB;
PolyAdd(tempA,
tempB);
return tempA;
}
friend Polynomial operator * (Polynomial &polyA, Polynomial &polyB)
{
Node<Term>
*pA = polyA.pGetFirst()->link;
Node<Term>
*pB = polyB.pGetFirst()->link;
Polynomial
polyTempA, polyTempB;
int
coef, exp;
if
(pA == NULL || pB == NULL) return polyTempA;
for
(pA = polyA.pGetFirst()->link; pA != NULL; pA = pA->link)
{
for(pB =
polyB.pGetFirst()->link; pB != NULL; pB = pB->link)
{
coef =
pA->data.coef * pB->data.coef;
exp =
pA->data.exp + pB->data.exp;
Term
term(coef, exp);
polyTempB.LastInsert(term);
}
PolyAdd(polyTempA, polyTempB);
polyTempB.Initialize();
}
return polyTempA;
}
【后记】很显然，在“＋”的处理上我偷懒了，但这是最方便的。乘法部分只要参照手工运算，还是很简单的，我就不解释了。对于“－”，可以先完成（－a）这样的算法，然后就可以用加法完成了，而你要是象我一样懒很可能就会做这种事－a＝－1×a，真的不提倡，超低的效率。对于除法，如果你会用汇编写多字节除法（跟手工计算很像），依样画葫芦也能弄出来，但首先要完成“－”。如果要写又得好长，留给你完成吧。到这里你明白原位加法的重要了吧，这些运算实际上都是靠它实现的。