一元多项式求和代码.doc

//#include "linklist.h"的定义

#include <iostream>
using namespace std;
struct elem
{
int coef;
int exp;
};

template <typename T> class linklist;

template <typename T>
class node
{
friend class linklist<T>;

template <typename T>
friend ostream & operator<<(ostream & os,linklist<T> & ll);

template <typename T>
friend void addd(linklist<T> * A,linklist<T> *B);

T date;
node<T> *next;
};

template <typename T>
class linklist
{
template <typename T>
friend ostream & operator<<(ostream & os,linklist<T> & ll);

template <typename T>
friend void addd(linklist<T> * A,linklist<T> * B);

private:
node<T> *first;
public:

linklist();
linklist(T a[],int n);//形成一元多项式链表

~linklist();

};
template <typename T>
ostream & operator<<(ostream & os,linklist<T> & kk)
{
node<T> *p;
p=kk.first->next;
while(p)
{
os<<p->date.coef<<"X"<<"("<<p->date.exp<<")"<<" ";
p=p->next;

}
os<<endl;
return os;

}
template <typename T>
void addd(linklist<T> * A,linklist<T> * B)
{

node<T> *p,*q,*pre,*qre,*v;
pre=A->first; p=pre->next; //工作指针p初始化，指针pre始终指向p的前驱结点
qre=B->first; q=qre->next; //工作指针q初始化，指针qre始终指向q的前驱结点
while(p && q)
{
if (p->date.exp<q->date.exp)
{ //第1种情况
pre=p;
p=p->next;
}
else if (p->date.exp>q->date.exp)
{ //第2种情况，将结点q插入到结点p之前,q指针后移
v=q->next;
q->next=p;
pre->next=q;

qre->next=v;
q=v;

}
else { //第3种情况
p->date.coef =p->date.coef+q->date.coef; //系数相加
if (p->date.coef ==0) { //系数为0，删除结点p和结点q
pre->next=p->next; //删除结点p
delete p;
p=pre->next;
}
else { //系数不为0，只删除结点q
pre=p;
p=p->next;
}
qre->next=q->next; //删除结点q
delete q;
q=qre->next;
}
}
if(q) pre->next=q; //将结点q链接在第一个单链表的后面
B->first->next=NULL;

}
template <typename T> linklist<T>::linklist()
{
first=new node<T>;
first->next=NULL;
}
template <typename T> linklist<T>::~linklist()
{
node<T> *p=first,*q;
while(p)
{
q=p;
p=p->next;
delete q;

}
}

//以下是尾接法
template <typename T> linklist<T>::linklist(T a[],int n)
{
node<T> *r; node<T> *p;
first=new node<T>;
first->next=NULL;
r=first;
for(int i=0;i<n;i++)
{
p=new node<T>;
p->date=a[i];
r->next=p;
r=p;}
r->next=NULL;

}

*/
//主函数
//主测试函数
#include <iostream>
using namespace std;
#include "linklist.h"
void main()
{
elem a[4],b[5];
linklist<elem> *P,*Q;
cout<<"输入第一个多项式的系数、指数"<<endl;
for(int i=0;i<4;i++)
cin>>a[i].coef>>a[i].exp;

linklist<elem> l1(a,4);
cout<<"输出第一个多项式为f(X):"<<endl;
cout<<l1<<endl;

cout<<"输入第二个多项式的系数、指数"<<endl;
for(int i=0;i<5;i++)
cin>>b[i].coef>>b[i].exp;

linklist<elem> l2(b,5);
cout<<"输出第二个多项式为g(X):"<<endl;
cout<<l2<<endl;

P=&l1;
Q=&l2;

addd(P,Q);
cout<<l1;

}