#ifndef LIST_H
#define LIST_H
template<typename elemtype>class list_item
{
public:
list_item( elemtype, list_item<elemtype>* );
list_item( const list_item<elemtype>& );
const elemtype date () const;
const list_item<elemtype>* next() const;
void get_date ( const elemtype );
void get_next ( const list_item<elemtype>* );
void operator =( const list_item<elemtype>& );
private:
elemtype _date;
list_item<elemtype> *_next;
};//单链表数据项类
//数据项类代码实现
template<typename elemtype>
list_item<elemtype>::list_item( elemtype ia = 0,
list_item<elemtype> *p = 0 )
{
get_date( ia );
if( p == NULL )
get_next( NULL );
else
{
get_next( p->next() );
p->get_next( this );
}
}
template<typename elemtype>
const elemtype
list_item<elemtype>::date() const
{
return _date;
}
template<typename elemtype> const
list_item<elemtype>* list_item<elemtype>::
next() const
{
return _next;
}
template<typename elemtype>
void list_item<elemtype>::get_date( const elemtype de )
{
_date = de;
}
template<typename elemtype>
void list_item<elemtype>::
get_next( const list_item<elemtype> *pev )
{
_next = ( list_item<elemtype>* )pev;
}
template<typename elemtype> class list
{
public:
list();
list( const list<elemtype>& );
~list();
const int size() const;
const bool empty() const;
void insert( const elemtype, const elemtype );
void insert_front( const elemtype );
void insert_end( const elemtype );
void remove( const elemtype );
void remove_all();
void remove_front();
void print() const;
const list_item<elemtype>* find( const elemtype );
void operator =( const list<elemtype>& );
private:
//
void down_size();
void add_size();
//
list_item<elemtype> *at_front;
list_item<elemtype> *at_end;
list_item<elemtype> *at_move;
int _size;
};//链表类定义
//函数实现代码
//私有函数集合
template<typename elemtype>
void list<elemtype>::add_size()
{
++_size;
}
template<typename elemtype>
void list<elemtype>::down_size()
{
--_size;
}
//公有函数集合
template<typename elemtype>
list<elemtype>::list() {
at_front = NULL;
at_end = NULL;
_size = 0;
}
template<typename elemtype>
list<elemtype>::~list()
{
remove_all();
}
template<typename elemtype>
const bool list<elemtype>::empty() const
{
return size() == 0 ? false : true;
}
template<typename elemtype>
const int list<elemtype>::size() const
{
return _size;
}
template<typename elemtype>
void list<elemtype>::insert_front( const elemtype iva )
{
list_item<elemtype> *pv =
new list_item<elemtype>( iva, 0 );
if( !at_front )
{
at_front = at_end = pv;
}
else
{
pv->get_next( at_front );
at_front = pv;
}
add_size();
}
template<typename elemtype>
void list<elemtype>::insert_end( const elemtype iva )
{
if( at_end == NULL)
{
at_end = at_front =
new list_item<elemtype>( iva, 0 );
}
else
at_end = new list_item<elemtype>( iva, at_end );
add_size();
}
template<typename elemtype> void list<elemtype>::
insert( const elemtype ixa, const elemtype iva )
{
list_item<elemtype> *pev =
( list_item<elemtype>* )find( iva );
if( pev == NULL )
{
cerr << "err!" <<endl;
return;
}
if( pev == at_front )
insert_front( ixa );
else {
new list_item<elemtype>( ixa, pev );
add_size();
}
}
template<typename elemtype> const
list_item<elemtype>* list<elemtype>::
find( const elemtype iva )
{
list_item<elemtype> *at_move = at_front;
while( at_move != NULL )
{
if( at_move->date() == iva )
return at_move;
at_move = ( list_item<elemtype>* )at_move->next();
}
return NULL;
}
template<typename elemtype>
void list<elemtype>::remove_front()
{
if( at_front )
{
list_item<elemtype> *pev = at_front;
at_front = ( list_item<elemtype>* )at_front->next();
delete pev;
down_size();
}
}
template<typename elemtype>
void list<elemtype>::remove( elemtype iva )
{
list_item<elemtype> *pev = at_front;
while( pev && pev->date() == iva )
{
pev = ( list_item<elemtype>* )pev->next();
remove_front();
}
if( !pev )
return ;
list_item<elemtype> *prv = pev;
pev = ( list_item<elemtype>* )pev->next();
while( pev )
{
if( pev->date() == iva )
{
prv->get_next( pev->next() );
down_size();
delete pev;
pev = ( list_item<elemtype>* )prv->next();
if( pev != NULL )
{
at_end = prv;
return;
}
}
else
{
prv = pev;
pev = ( list_item<elemtype>* )pev->next();
}
}
}
template<typename elemtype>
void list<elemtype>::remove_all()
{
while( at_front )
remove_front();
_size = 0;
at_front = at_end = NULL;
}
template<typename elemtype>
void list<elemtype>::print() const
{
list_item<elemtype> *pev = at_front;
cout << '[' << size() << ']';
cout << '{';
for( int ix = 0; pev && ix < size(); ++ix )
{
cout << pev->date() << ' ';
pev = ( list_item<elemtype>* )pev->next();
}
cout << '}' << endl;
}
#endif