随笔 - 8  文章 - 26  trackbacks - 0
<2024年11月>
日一二三四五六
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

常用链接

留言簿(4)

随笔档案

文章分类

文章档案

相册

C++语言

搜索

  •  

最新评论

阅读排行榜

评论排行榜

链表类---转载
#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
转载自：http://www.cppblog.com/mzty/archive/2005/10/28/870.html
posted on 2008-06-18 22:05 杨彬彬 阅读(333) 评论(0)  编辑 收藏 引用 所属分类: 数据结构

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Copyright ©2024 杨彬彬 Powered by: 博客园 模板提供：沪江博客