换手机号又忘记密码了，可怜了我的C币。只能从头来过

导言：C++抽象数据类型（Abstract Data Type 简称ADT）实现 多项式相加

实现效果类似下图

主函数

 模块化原则：尽量将重复代码抽象成功能函数    三个参数的PolyAddd(被加多项式，加多项式，多项式的和)      

考虑到多项式类的设计 多项式相加应该属于类外函数，设计成模板友元类更符合类的设计，但是耦合性就会变高，所谓有得有失嘛

PolyAdd后续还会介绍

读入多项式

类

1. Node类  

结点类（较简单）           蓝字注释不再赘述

2.多项式类

多项式类应该有的功能是 ：

1.创建一个空的多项式（Link()函数）

2.连接新的项           （Add()函数）

3.打印多项式           （Print()函数）

Add()需要考虑如果此时多项式为空如何解决    我更喜欢if(NULL==head)

当你汗流浃背找bug，  结果发现  if(head==NULL)写成if(head=NULL)你就懂我了。    NULL不是变量在编译时如果将==错写成= 编译器会报错而head==NULL错写成head=NULL就意味着   灾难。接下来两小时你的工作可能就是在找bug了。

最关键的多项式相加的函数

前面提到的PolyAdd             已经声明为ADT类Link的友元函数

其中82行

Compared函数具体实现

这样完整的多项式相加就是实现了

下期预告：  打开的度娘搜索框内的内容

输入C++为什么就不同于 天下第一帅  

这些就是字符串的模式识别需要解决的问题：将介绍朴素的模式匹配与KMP模式匹配算法

完整代码

#include<iostream>
using namespace std;
template<class T>
class Node                           //结点类    一个项的信息 
{
public:
T num;                      //系数 
int exp;                    //指数 
Node<T> *next;              //指向下一个节点的指针 

Node(T nu,int ex,Node<T> *ne=NULL)   //构造函数 
{
num=nu;
exp=ex;
next=ne;
}
};
template<class T>
class Link
{
template<T> friend void PolyAdd(const Link<T> a,const Link<T> b,Link<T> &tmp);       //完成多项式相加的友元函数 

public:                                                  
Node<T> *head;          //头节点指针 
Link()                  //构造函数 
{
head=NULL;
}
~Link()                 //析构函数 
{
Node<T> *tmp;
while(head)
{
tmp=head;
head=head->next;
delete tmp;
}
}
bool Add(T num,int exp)  //理解成Atach更合适，连接下一个项 
{
if(NULL==head)
{
head=new Node<T>(num,exp);
return true;
}
Node<T> *tmp;
tmp=head;
for(;tmp->next!=NULL;tmp=tmp->next);
tmp->next=new Node<T>(num,exp);
}
void print()                   //打印整个多项式 
{
Node<T> *t;
t=head;
while(t)
{
cout<<t->num<<"x^"<<t->exp;
if(t->next!=NULL)
cout<<"+";
t=t->next;
}
cout<<endl;
}

};
int Compared(int aExp,int bExp)
{
if(aExp>bExp)
return 1;
else if(aExp<bExp)
return -1;
else 
return 0;
}
template<class T>
void PolyAdd(const Link<T> &a,const Link<T> &b,Link<T> &tmp)
{
Node<T> *aTmp=a.head;
Node<T> *bTmp=b.head;
while(aTmp&&bTmp)
{
switch(Compared(aTmp->exp,bTmp->exp))
{
case 1:           //a的指数大于b的指数 
tmp.Add(aTmp->num,aTmp->exp); 
aTmp=aTmp->next;
break;
case 0:           //a与b指数相同 
//if(sum==0)    系数和为零是应舍去; 
tmp.Add(aTmp->num+bTmp->num,aTmp->exp);
aTmp=aTmp->next;
bTmp=bTmp->next;
break;
case -1:         //a的指数小于b的指数 
tmp.Add(bTmp->num,bTmp->exp);
bTmp=bTmp->next;
break;
}
}
 
for(;aTmp;bTmp=bTmp->next)        //多项式a中项都加入tmp多项式中了   ，解决b的剩余项 
tmp.Add(bTmp->num,bTmp->exp);
for(;bTmp;aTmp=aTmp->next)       //多项式b中项都加入tmp多项式中了   ，解决a的剩余项 
tmp.Add(aTmp->num,aTmp->exp);
}


template<class T>
void readPoly(Link<T> &item)       //参数为引用格式 
{
int a;                         //多项式个数     整形 
cin>>a;                        
T num;                         //抽象数据类型   系数 
int exp;                       //整形           指数 

for(int i=0;i<a;i++)           //读入多项式       * 
{  
cin>>num;              
cin>>exp;                 
item.Add(num,exp);         //加入到item链表中 
}
}


int main()
{
Link<int> fir;                // *********************** ***************************** 
Link<int> sen;                //    定义三个多项式  thr储存fir与sen的和              * 
Link<int> thr;                // *********************** ***************************** 

readPoly(fir);                //读入两个多项式 1 
readPoly(sen);                //               2 

PolyAdd(fir,sen,thr);         //多项式相加 

fir.print();                  //打印结果到显示器 1 
sen.print();                  //                 2 
thr.print();                  //                 3 
}