Question

数据结构：用单链表实现两个多项式的加法

Answer 1

我也在学这个，这是我上学期学的。

//polynomial.cpp
#include"polynomial.h"
int sum(linklist<int>&list)
{
if(list.isempty()==1)return 0;
int item=list.reset(1)->data;
return item;
}
ostream&operator<<(ostream &output,polynomial&z)
{
node<term>*q;term data1;
q=z.poly.reset(1);

while(q->next!=NULL)
{
data1=q->data;output<<data1.coef<<"X^"<<data1.exp<<"+";q=q->next;}data1=q->data;
if(data1.exp==0) output<<data1.coef;
else output<<data1.coef<<"X^"<<data1.exp;
cout<<endl;
return output;
}
void main()
{
polynomial a,b;term c;
c.init(5,10);
a.poly.insertafter(c);
c.init(2,6);
a.poly.insertafter(c);
c.init(4,0);
a.poly.insertafter(c);
cout<<a<<endl;
c.init(3,10);
b.poly.insertafter(c);
c.init(7,4);
b.poly.insertafter(c);
c.init(6,1);
b.poly.insertafter(c);
cout<<b<<endl;
cout<<a+b<<endl;

// b.poly.~linklist();
// a.poly.~linklist();

}

//polynomial.h
//linklist
#include <iostream.h>
#include <stdlib.h>
#include <math.h>
#include<string.h>
template<class type>class linklist;
template<class type>class node
{
friend class linklist <type>;
private:
//node <type>* next;
public:
type data;
node <type>* next;
node (node<type>* pnext=NULL);
node(const type &item,node<type>* pnext=NULL);
void setnext(node<type>* p){next=p;}
void setdata(type x){data=x;}
~node(){};
};
template<class type>class linklist
{
private:
node<type>* head;
node<type>* pcurrent;
public:
linklist();
~linklist();
int length()const;
type getcurrent();
node<type>* locate(type &x);
void insertbefore(const type &x);
void insertafter(const type &x);
type deletecurrent();
int isempty()const;
void clear();
node <type>* reset(int i);
node <type>* Next();
int endoflist()const;
void freelist();
};
template<class type>
node <type>::node(node<type>* pnext){next=pnext;}
template<class type>
node<type>::node(const type &item,node<type>* pnext)
{
data=item;
next=pnext;
}
template <class type>
linklist<type>::linklist()
{
head=pcurrent=new node<type>();
head->next=NULL;
}
template <class type>
linklist<type>::~linklist(){}
template <class type>
void linklist<type>::freelist()
{
clear();
delete head;
}
template <class type>
int linklist<type>::length()const
{
node<type>*p=head->next;
int len=0;
while(p!=NULL)
{len++;p=p->next;}
return len;
}
template <class type>
type linklist <type>::getcurrent()
{if(pcurrent==head||pcurrent==NULL)
{cerr<<"未取到数值"<<endl;
exit(1);
}
return pcurrent->data;
}
template <class type>
node<type>* linklist<type>::locate(type&x)
{pcurrent=head->next;
while(pcurrent!=NULL)
if(pcurrent->data==x)break;
else pcurrent=pcurrent->next;
return pcurrent;
}
template <class type>
void linklist<type>::insertbefore(const type&x)
{
if(head->next==NULL)
{
node<type>* newnode=new node<type>*(x,NULL);
head->next=pcurrent=newnode;
}
else
{
node<type>*newnode=new node<type>(x,pcurrent);
node<type>* p=head;
while(p->next!pcurrent)p=p->next;
p->next=newnode;
pcurrent=newnode;
}
}
template <class type>
void linklist<type>::insertafter(const type &x)
{
if(head->next==NULL||pcurrent==NULL)
{node<type>*newnode=new node<type>(x,head->next);
head->next=pcurrent=newnode;
}
else
{
node<type>*newnode=new node<type>(x,pcurrent->next);
pcurrent->next=newnode;
pcurrent=newnode;
}
}
template <class type>
type linklist<type>::deletecurrent()
{
if(pcurrent==head||pcurrent==NULL)
{
cerr<<"不可删!"<<endl;
exit(1);
}
node<type>* p=head;
while(p->next!=pcurrent)p=p->next;
p->next=pcurrent->next;
type data1=pcurrent->data;
delete pcurrent;
pcurrent=p->next;
return data1;
}
template <class type>
int linklist<type>::isempty()const
{
if(head->next==NULL)return 1;
else return 0;
}
template <class type>
void linklist<type>::clear()
{
node<type>*p,*q;
p=head->next;
while(p!=NULL)
{q=p;p=p->next;delete q;}
pcurrent=head;
}
template <class type>
node<type>*linklist<type>::reset(int i)
{
if(head==NULL||i<0)return NULL;
if(i==0)
{pcurrent=head;return head;}
node<type>*p=head;
int k=0;
while(p!=NULL&&k<i)
{p=p->next;k++;}
pcurrent=p;
return p;
}
template <class type>
node<type>*linklist<type>::Next()
{
if(pcurrent!=NULL) pcurrent=pcurrent->next;
return pcurrent;
}
template <class type>
int linklist<type>::endoflist()const
{
if(pcurrent==NULL)return 1;
else return 0;
}
struct term{
int coef; int exp;
void init(int c,int e){coef=c;exp=e;};
};
class polynomial{
friend polynomial&operator +(polynomial &,polynomial &);
public:
linklist<term>poly;
};
polynomial&operator+(polynomial&a,polynomial&b){
node<term> *pa,*pb,*pc,*p, *c;
term at,bt;
pc=a.poly.reset(0);
c=pc;
p=b.poly.reset(0);
pa=a.poly.reset(1);
pb=b.poly.reset(1);
delete p;
while(!a.poly.endoflist()&&!b.poly.endoflist())
{
int i=0;
at=pa->data;
bt=pb->data;
if(at.exp==bt.exp) i=0;
if(at.exp>bt.exp) i=1;
else if(at.exp<bt.exp) i=2;
switch(i){
case 0:
at.coef=at.coef+bt.coef;
p=pb;
pb=b.poly.Next();
delete p;
if(abs(at.coef)<0.0001)
{p=pa;pa=a.poly.Next();delete p;}
else
{pa->setdata(at);
pc->setnext(pa);
pc=pa;pa=a.poly.Next();
}
break;
case 1:
pc->setnext(pa);
pc=pa;
pa=a.poly.Next();
break;
case 2:
pc->setnext(pb);
pc=pb;
pb=b.poly.Next();

}
}
if(!a.poly.endoflist()) pc->setnext(pa);
else pc->setnext(pb);
return a;
}