正常线性表-链式存储结构及其操作算法的实现-多项式的代数运算

一般线性表-----链式存储结构及其操作算法的实现-----多项式的代数运算

//file :list_link.h
#ifndef _LIST_LINK_H_HUMING_INCLUDE_
#define _LIST_LINK_H_HUMING_INCLUDE_
#include<cstdio>
template <class T>
class  node
{
public:
    T data;
    node<T>* next;
    node():next(NULL) {}; //No-arg constructor
    node(T p)//Constructor
    {
        this->data=p;//"this" means "class node"
        next=NULL;
    };
};
//node definatio
template <class T>
class link
{
public :
    link();
    void Insert(T x,node<T>* p);
    void Delete(node<T>* p);
    node<T>* Locate(T x);
    node<T>* First();
    T Retrieve(node<T>* p);
    node<T>* Previous(node<T>* p);
    node<T>* Next(node<T>* p);
    node<T>* End();
    void Swap(node<T>* p,node<T>*q);
private :
    node<T>* L;
};
//link defination
template <class T>
link<T>::link()
{
    L=new node<T>;
    L->next=NULL;
};
template <class T>
node<T>* link<T>::First()
{
  return L;
}
template <class T>
void link<T>::Insert(T x,node<T>* p)
{
    node<T>* q=new node<T>;
    q->data=x;
    q->next=p->next;
    p->next=q;
}
template <class T>
void link<T>::Delete(node<T>* p)//delete p next node<T>* data
{
    node<T>* q;
    if(p->next!=NULL)
        {
           q=p->next;
           p->next=p->next;
        }
        delete q;
}
template <class T>
node<T>* link<T>::Locate(T x)
{
   node<T>* p;
   p=L;
   while(p->next!=NULL)
    {
      if(p->next->data==x)  return p;
     else p=p->next;
    }
    return p;
}
template <class T>
T link<T>::Retrieve(node<T>* p)
{
  return (p->next->data);//show p node<T>* next element!,注意啊，不然实现的时候会抽的！
}
template <class T>
node<T>* link<T>::Previous(node<T>* p)
{
   node<T>* q;
   if(p=L->next)
       return NULL;
    else
        {
           q=L;
           while(q->next!=p) q=q->next;
           return q;//q->next==p
        }
}
template <class T>
node<T>* link<T>::Next(node<T>* p)
{
  if(p->next==NULL)  return NULL;
  else  return p->next;
}
template <class T>
node<T>*  link<T>::End()
{
  node<T>*  p;
  p=L;
  while(p->next!=NULL)p=p->next;
  return p;
}
template <class T>
void link<T>::Swap(node<T>* p,node<T>*q)
{
    T temp;
    temp=p->data;
    p->data=q->data;
    q->data=temp;
}
#endif

//多项式加法！
#include<iostream>
#include "list_link.h"
using namespace std;
struct polynode
{
    int coef;//系数
    int exp;//指数
};
link <polynode> a,b,c;
void PolyAdd(link<polynode>a,link<polynode>b,link<polynode>c);
void show(link<polynode>x);
int main()
{
    freopen("in.txt","r",stdin);
    int n;
    node<polynode>* m;
    polynode x;
//     printf("请输入第一个多项式\n");
    cin >> n >> x.coef >> x.exp;
    a.Insert(x,a.First());
    for(int i=1; i<=n-1; i++)
    {
        cin >> x.coef >> x.exp;
        m=a.First();
        while(m!=a.End())
        {
            if(a.Retrieve(m).exp>x.exp) m=a.Next(m);
            else break;
        }
        a.Insert(x,m);
    }
//    printf("请输入第二个多项式\n");
    cin >> n >> x.coef >> x.exp;
    b.Insert(x,b.First());
    for(int i=1; i<=n-1; i++)
    {
        cin >> x.coef >> x.exp;
        m=b.First();
        while(m!=a.End())
        {
            if(b.Retrieve(m).exp>x.exp) m=b.Next(m);
            else break;
        }
        b.Insert(x,m);
    }//插入的时候就按顺序插入，省的排序！
    PolyAdd(a,b,c);
    show(a);
    printf("+");
    show(b);
    printf("=");
    show(c);
    return 0;
}
void show(link<polynode>x)
{
    node<polynode>  *i;
    i=x.First();
    while(i->next!=x.End())
    {
        printf("%d*x^%d+",x.Retrieve(i).coef,x.Retrieve(i).exp);
        i=x.Next(i);
    }
    printf("%d*x^%d",x.Retrieve(i).coef,x.Retrieve(i).exp);
}
void PolyAdd(link<polynode> a,link<polynode> b,link<polynode> c)
{
    polynode temp;
    node<polynode>*p1=a.First(),*i,*p2=b.First();//指向节点类型的指针
    while(a.Next(p1)!=NULL&&b.Next(p2)!=NULL)
    {
        if(a.Retrieve(p1).exp>b.Retrieve(p2).exp)
        {
            c.Insert(a.Retrieve(p1),c.End());
            p1=a.Next(p1);
        }
        else if(a.Retrieve(p1).exp<b.Retrieve(p2).exp)
        {
            c.Insert(b.Retrieve(p2),c.End());
            p2=b.Next(p2);
        }
        else
        {
            temp.coef=a.Retrieve(p1).coef;
            temp.exp=a.Retrieve(p1).exp;
            temp.coef+=b.Retrieve(p2).coef;
            c.Insert(temp,c.End());
            p1=a.Next(p1);
            p2=b.Next(p2);
        }
    }
    if(p1!=a.End())
    {
        for(i=p1; i!=a.End(); i=a.Next(i))
            c.Insert(a.Retrieve(i),c.End());
    }
    if(p2!=b.End())
    {
        for(i=p2; i!=b.End(); i=b.Next(i))
            c.Insert(b.Retrieve(i),c.End());
    }
}