别人写的不错的双向列表
作者:18 year old C++ programmer. I like synth-music, poetry and roleplaying. smurf! #ifndef __list__
#define __list__
template<typename T> class list
{
class node;
friend class node;
public:
class iterator;
friend class iterator;
//Constructor
list():pHead(0),pTail(0) {};
//Destructor
~list() { PopAll(); };
//This method allocated new nodes.
//You have to clean out the list yourself before.
//Example: iterator i = GetHead(); while(*i) delete PopHead();
list &operator = (const list &m)
{
if(this == &m) return *this;
iterator i = m.GetHead();
while(*i) PushTail(*i++);
return *this;
};
//The iteration class.
class iterator
{
public:
friend iterator;
friend list<T>;
iterator(node *nNode = 0):pNode(nNode) {};
explicit iterator(iterator &i):pNode(i.pNode) {};
~iterator() {};
iterator &operator = (node *nNode) { pNode = nNode; return *this; };
iterator &operator ++ (void) { pNode = pNode->pNext; return *this; };
iterator operator ++ (int) { iterator i(*this); ++*this; return i; };
iterator &operator -- (void) { pNode = pNode->pPrev; return *this; };
iterator operator -- (int) { iterator i(*this); --*this; return i; };
T *operator * (void) { return (pNode) ? (&**pNode):0; };
T *operator -> () { return (**this); };
bool operator == (iterator &i) const { return (pNode == i.pNode); };
bool operator == (node *n) const { return (pNode == n); };
bool operator != (iterator &i) const { return (pNode != i.pNode); };
bool operator != (node *n) const { return (pNode != n); };
protected:
private:
node *pNode;
};
//Returns pointer to pHead
node *GetHead(void) const { return pHead; };
//Returns pointer to pTail
node *GetTail(void) const { return pTail; };
//Adds an item at head-position
node *PushHead(T *nData)
{
if(!nData) return 0;
node *n = new node(nData);
if (!pTail) pTail = n;
else pHead->pPrev = n;
n->pNext = pHead;
pHead = n;
return n;
};
//Adds an item at tail-position
node *PushTail(T *nData)
{
if(!nData) return 0;
node *n = new node(nData);
if (!pHead) pHead = n;
else pTail->pNext = n;
n->pPrev = pTail;
pTail = n;
return n;
};
//Detaches the first node and returns the item
T *PopHead(void) { return Detach(pHead); };
//Detaches the last node and returns the item
T *PopTail(void) { return Detach(pTail); };
//Detaches the node pointed on by i
T *Pop(iterator &i) { return Detach(i.pNode); };
//Detaches n and returns n's item
T *Pop(node *n) { return Detach(n); };
//Removes and deletes node, deletes item.
void Erase(iterator &i) { delete Detach(i.pNode); };
//Removes and deletes all nodes, deletes all items.
void EraseAll(void) { iterator i(GetHead()); while(*i) Erase(i++); };
//Removes all nodes, does not free memory for items, use with caution
void PopAll(void) { iterator i(GetHead()); while(*i) Pop(i++); };
//Returns pointer to the node pointing to nData, else returns 0
node *Find(T *nData)
{
iterator i = GetHead();
while(*i) { if(i.pNode->pData == nData) return i.pNode; ++i; }
return 0;
};
//Counts and returns number of items in list.
int GetCount(void) { int x = 0; for(iterator i = GetHead();*i;++i,++x); return x; };
protected:
private:
T *Detach(node *nNode)
{
if(!nNode) return 0;
if (!nNode->pPrev) pHead = nNode->pNext;
else nNode->pPrev->pNext = nNode->pNext;
if (!nNode->pNext) pTail = nNode->pPrev;
else nNode->pNext->pPrev = nNode->pPrev;
T *p = nNode->pData;
delete nNode;
return p;
};
class node
{
friend class list<T>;
friend class node;
friend class iterator;
public:
node(T *nData = 0):pData(nData),pPrev(0),pNext(0) {};
~node() {};
private:
T &operator * (void) { return *pData; };
node *pPrev;
node *pNext;
T *pData;
};
node *pHead;
node *pTail;
};
#endif
作者:18 year old C++ programmer. I like synth-music, poetry and roleplaying. smurf! #ifndef __list__
#define __list__
template<typename T> class list
{
class node;
friend class node;
public:
class iterator;
friend class iterator;
//Constructor
list():pHead(0),pTail(0) {};
//Destructor
~list() { PopAll(); };
//This method allocated new nodes.
//You have to clean out the list yourself before.
//Example: iterator i = GetHead(); while(*i) delete PopHead();
list &operator = (const list &m)
{
if(this == &m) return *this;
iterator i = m.GetHead();
while(*i) PushTail(*i++);
return *this;
};
//The iteration class.
class iterator
{
public:
friend iterator;
friend list<T>;
iterator(node *nNode = 0):pNode(nNode) {};
explicit iterator(iterator &i):pNode(i.pNode) {};
~iterator() {};
iterator &operator = (node *nNode) { pNode = nNode; return *this; };
iterator &operator ++ (void) { pNode = pNode->pNext; return *this; };
iterator operator ++ (int) { iterator i(*this); ++*this; return i; };
iterator &operator -- (void) { pNode = pNode->pPrev; return *this; };
iterator operator -- (int) { iterator i(*this); --*this; return i; };
T *operator * (void) { return (pNode) ? (&**pNode):0; };
T *operator -> () { return (**this); };
bool operator == (iterator &i) const { return (pNode == i.pNode); };
bool operator == (node *n) const { return (pNode == n); };
bool operator != (iterator &i) const { return (pNode != i.pNode); };
bool operator != (node *n) const { return (pNode != n); };
protected:
private:
node *pNode;
};
//Returns pointer to pHead
node *GetHead(void) const { return pHead; };
//Returns pointer to pTail
node *GetTail(void) const { return pTail; };
//Adds an item at head-position
node *PushHead(T *nData)
{
if(!nData) return 0;
node *n = new node(nData);
if (!pTail) pTail = n;
else pHead->pPrev = n;
n->pNext = pHead;
pHead = n;
return n;
};
//Adds an item at tail-position
node *PushTail(T *nData)
{
if(!nData) return 0;
node *n = new node(nData);
if (!pHead) pHead = n;
else pTail->pNext = n;
n->pPrev = pTail;
pTail = n;
return n;
};
//Detaches the first node and returns the item
T *PopHead(void) { return Detach(pHead); };
//Detaches the last node and returns the item
T *PopTail(void) { return Detach(pTail); };
//Detaches the node pointed on by i
T *Pop(iterator &i) { return Detach(i.pNode); };
//Detaches n and returns n's item
T *Pop(node *n) { return Detach(n); };
//Removes and deletes node, deletes item.
void Erase(iterator &i) { delete Detach(i.pNode); };
//Removes and deletes all nodes, deletes all items.
void EraseAll(void) { iterator i(GetHead()); while(*i) Erase(i++); };
//Removes all nodes, does not free memory for items, use with caution
void PopAll(void) { iterator i(GetHead()); while(*i) Pop(i++); };
//Returns pointer to the node pointing to nData, else returns 0
node *Find(T *nData)
{
iterator i = GetHead();
while(*i) { if(i.pNode->pData == nData) return i.pNode; ++i; }
return 0;
};
//Counts and returns number of items in list.
int GetCount(void) { int x = 0; for(iterator i = GetHead();*i;++i,++x); return x; };
protected:
private:
T *Detach(node *nNode)
{
if(!nNode) return 0;
if (!nNode->pPrev) pHead = nNode->pNext;
else nNode->pPrev->pNext = nNode->pNext;
if (!nNode->pNext) pTail = nNode->pPrev;
else nNode->pNext->pPrev = nNode->pPrev;
T *p = nNode->pData;
delete nNode;
return p;
};
class node
{
friend class list<T>;
friend class node;
friend class iterator;
public:
node(T *nData = 0):pData(nData),pPrev(0),pNext(0) {};
~node() {};
private:
T &operator * (void) { return *pData; };
node *pPrev;
node *pNext;
T *pData;
};
node *pHead;
node *pTail;
};
#endif
class ChainNode
{
friend Chain<T>;
private:
T data;
ChainNode<T>*link;
};template<class T>
class Chain
{
public:
Chain(){ first = 0; last = 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 Erase();
Chain<T>& Append( const T& x ); void Output( ostream& out ) const;
private:
ChainNode<T> *first;
ChainNode<T> *last;
};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 && current )
{
current = current->link;
index++;
}
if( current )
{
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 && current->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();
return *this;
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();
return *this;
p = q->link;
q->link = p->link; if( p == last )
last = q; }
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();
return *this;
ChainNode<T> *p = first;
for ( int index = 1; index < k && p; index++ )
p = p->link;
if ( k > 0 && !p )
// throw OutOfBounds();
return *this;
ChainNode<T> *y = new ChainNode<T>;
y->data = x;
if( k )
{
y->link = p->link;
p->link = y;
}
else
{
y->link = first;
first = y;
}
if( !y->link )
last = 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;
if( first )
{
last->link = y;
last = y;
}
else
first = last = y;
return *this;
}class Node {
friend ostream& operator<<(ostream&, const Node &);
friend void BinSort(Chain<Node>&, int);
friend void main(void);
public:
int operator !=(Node x) const
{return (score != x.score);}
private:
int score;
char *name;
};ostream& operator<<(ostream& out, const Node& x)
{out << x.score << ' '; return out;}