双向链表
老师布置作业：求任意大整数的加减法。要求用双向链表，但是一脸蒙逼，一点思绪都没有，求助各位大神帮帮忙！
//很久没弄过双向链表了，用了那么长的代码才实现，真有点不好看
#include<iostream>
using std::endl;using std::cout;
using std::cin;
class Node
{
private:
short n;
Node*pre;
Node*next;
public:
short GetData(){return n;}
void SetPre(Node*n)
{
pre=n;
}
void SetNext(Node*n)
{
next=n;
}
Node*GetPre(){return pre;}
Node*GetNext(){return next;}
Node(short _n=0):n(_n)
{
pre=next=NULL;
}
Node(short _n,Node*pr,Node*nt):n(-n)
{
pre=pr;next=nt;
if(pr) pr->SetNext(this);
if(nt) nt->SetPre(this);
}
~Node(){delete pre;pre=0;delete next;next=0;}
void InsertAfter(Node*n)
{
if(!n) return;
pre=n;next=n->GetNext();
n->SetNext(this);next->SetPre(this);
}
void InsertBefore(Node*n)
{
if(!n) return;
next=n;pre=n->GetPre();
n->SetPre(this);pre->SetNext(this);
}
};
class Chain
{
private:
Node*head;//哨兵
Node*tail;//哨兵
int size;
public:
Chain()
{
head=new Node();
tail=new Node();
head->SetNext(tail);
tail->SetPre(head);
size=0;
}
Chain(char*str)
{
head=new Node();
tail=new Node();
head->SetNext(tail);
tail->SetPre(head);
size=0;
MassPush(str);
}
void MassPush(char*str)
{
for(short i=0;i<strlen(str);i++)
{
Push(str[i]-'0');
}
}
Node*First()
{
if(!size) return NULL;
else
return head->GetNext();
}
Node*Last()
{
if(!size) return NULL;
else
return tail->GetPre();
}
void Push(short n)
{
Node*nd=new Node(n);
nd->InsertBefore(tail);size++;
}
void InsertAsFirst(short n)
{
Node*nd=new Node(n);
nd->InsertAfter(head);size++;
}
void Display()
{
Node*i;
for(i=First();i!=tail;i=i->GetNext())
{
cout<<i->GetData();
}
}
int Size(){return size;}
friend Chain operator-(Chain a,Chain b);
};
bool operator>=(Chain a,Chain b)
{
return a.Size()>b.Size()||a.Size()==b.Size()&&a.First()->GetData()>=b.First()->GetData();
}
Chain operator+(Chain a,Chain b)
{
Chain result;
Node*a_digit,*b_digit;
short a_num,b_num;
short digit;//答案的数位
short tag=0;//tag是进位标记
for(a_digit=a.Last(),b_digit=b.Last();;)
{
a_num=a_digit?a_digit->GetData():0;
b_num=b_digit?b_digit->GetData():0;
digit=a_num+b_num+tag;
tag=digit>9;digit%=10;
result.InsertAsFirst(digit);
a_digit=(a_digit==a.First()||a_digit==NULL)?NULL:a_digit->GetPre();
b_digit=(b_digit==b.First()||b_digit==NULL)?NULL:b_digit->GetPre();
if(!(a_digit||b_digit)) break;
}
return result;
}
Chain operator-(Chain a,Chain b)
{
if(!(a>=b))
{
cout<<"本程序暂不支持负数运算。:P\n";exit(0);
}
Chain result;
Node*a_digit,*b_digit;
short a_num,b_num,digit;
short tag=0;//退位标记
for(a_digit=a.Last(),b_digit=b.Last();a_digit!=a.head;)
{
a_num=a_digit->GetData();
b_num=b_digit?b_digit->GetData():0;
digit=(10+a_num-tag-b_num)%10;
result.InsertAsFirst(digit);
tag=a_num-tag<b_num;
a_digit=a_digit->GetPre();
b_digit=(b_digit==b.First()||b_digit==NULL)?NULL:b_digit->GetPre();
}
return result;
}
int main()
{
Chain c("87843269087");
c.Display();cout<<endl;
Chain d("4444");
d.Display();cout<<endl;
Chain e;
e=c+d;
e.Display();cout<<endl;
e=c-d;
e.Display();cout<<endl;
return 0;
}