#include <iostream>
using namespace std;
template <class T>
class ChainIterator;
class NoMem
{
public:
NoMem(){}
};
void OutOfBounds()
{
throw NoMem();
}
template <class T>
class Chain;
template <class T>
class ChainNode
{
friend Chain<T>;
friend class ChainIterator<T>;
private:
T data;
ChainNode<T> *link;
};
template <class T>
class Chain
{
public:
Chain(){first=0;}
~Chain();
bool IsEmpty()const {return first==0;}
int Length()const;
bool Find(int k,T& x) const;
int Search(const T& x) const;
Chain<T>& Delete(int k,T& x);
Chain<T>& Insert(int k,const T& x);
void Output(ostream& out) const;
void Erase();
Chain<T>& Append(const T& x);
private:
ChainNode<T> *first;
friend class ChainIterator<T>;
};
template <class T>
Chain<T>::~Chain()
{
ChainNode<T> *next;
while(first)
{
next=first->link;
delete first;
first=next;
}
}
template <class T>
int Chain<T>::Length()const
{
ChainNode<T> *current=first;
int len=0;
while(current)
{
len++;
current=current->link;
}
return len;
}
template <class T>
bool Chain<T>::Find(int k,T& x)const
{
if(k<1) return false;
ChainNode<T> *current=first;
int index=1;
while(index<k&¤t)
{
current=current->link;
index++;
}
if(current)
{
if(x==current->data)
return true;
}
return false;
}
template <class T>
int Chain<T>::Search(const T& x) const
{
ChainNode<T> *current=first;
int index=1;
while(current&¤t->data!=x)
{
current=current->link;
index++;
}
if(current) return index;
return 0;
}
template <class T>
void Chain<T>::Output(ostream& out) const
{
ChainNode<T> *current;
for(current=first;current;current=current->link)
out<<current->data<<" ";
}
template <class T>
ostream& operator<<(ostream&out,const Chain<T>& x)
{
x.Output(out);
return out;
}
template <class T>
Chain<T>& Chain<T>::Delete(int k,T& x)
{
if(k<1||!first)
throw OutOfBounds();
ChainNode<T> *p=first;
if(k==1)
first=first->link;
else
{
ChainNode<T> *q=first;
for(int index=1;index<k-1&&q;index++)
q=q->link;
if(!q||!q->link)
throw OutOfBounds();
p=q->link;
q->link=p->link;
}
x=p->data;
delete p;
return *this;
}
template <class T>
Chain<T>& Chain<T>::Insert(int k, const T& x)
{
if(k<0) throw OutOfBounds();
ChainNode<T> *p=first;
for(int index=1;index<k&&p;index++)
p=p->link;
if(k>0&&!p) throw OutOfBounds();
ChainNode<T> *y=new ChainNode<T>;
y->data=x;
y->link=0;
if(k)
{
y->link=p->link;
p->link=y;
}
else
{
y->link=first;
first=y;
}
return *this;
}
template <class T>
void Chain<T>::Erase()
{
ChainNode<T> *next;
while(first)
{
next=first->link;
delete first;
first=next;
}
}
template <class T>
Chain<T>& Chain<T>::Append(const T&x)
{
ChainNode<T> *y;
y=new ChainNode<T>;
y->data=x;
y->link=0;
ChainNode<T> *c;
c=first;
while(c->link)
{
c=c->link;
}
c->link=y;
return *this;
}
template <class T>
class ChainIterator
{
public:
T* Initialize(const Chain<T>& c)
{
location=c.first;
if(location) return &location->data;
return 0;
}
T* Next()
{
if(!location) return 0;
location=location->link;
if(location) return &location->data;
return 0;
}
private:
ChainNode<T> *location;
};
int main()
{
Chain <int> a;
a.Insert(0,2).Insert(1,6).Insert(2,3).Insert(3,5).Insert(4,7);
cout<<a<<endl;
int i;
i=a.Length();
cout<<i<<endl;
int *x;
ChainIterator<int> c;
x=c.Initialize(a);
while(x)
{
cout<<*x<<" ";
x=c.Next();
}
cout<<endl;
i=6;
if(a.Find(2,i)) cout<<"find"<<endl;
int j;
j=a.Search(i);
cout<<"search:"<<j<<endl;
a.Delete(2,i);
cout<<a<<endl;
a.Append(i);
cout<<a<<endl;
a.Erase();
cout<<a<<endl;
return 0;
}