C++ Programmer's Cookbook

{C++ 基础} {C++ 高级} {C#界面，C++核心算法} {设计模式} {C#基础}

c＋＋单向链表 （讨论应不应该在默认的构造里就分配空间）

//  IntLink.cpp : Defines the entry point for the console application.
 //
//
 /**/ //////////////////////////////////////////////////////////////////////// //
// 作者：梦在天涯
 // 单向链表类
/**/ //////////////////////////////////////////////////////////////////////// //
//
//
 #pragma once
#include  < stdio.h >
#include  < tchar.h >

#include  < iostream >
using   namespace  std;

 struct  NODE
 {
    int  data;
   NODE  *  next;
} ;
 class  CIntLink
 {
 private :
    NODE  *  head;
 public :
    CIntLink()
     {
        head = NULL;
    }
     ~ CIntLink()
     {
        delete head;
    }
   void  Add(  int  iValue );
   void   Remove(  int  iIndex);
   void    Insert( int  iIndex,  int  iValue );
   int   Find(  int  iValue );
   void  output();
   int  size();
} ;
 // 链表的标号是从0开始。且第一个节点有存有数据。
void   CIntLink::Add( int  ivalue)
 {
     if (head == NULL)
     {
       head = new  NODE;
       head -> data = ivalue;
       head -> next = NULL;
    }
     else
     {
   NODE  * temp = new  NODE;
   temp -> data = ivalue;
   temp -> next = NULL;
   NODE  * p = head;
    while (p -> next != NULL)
         p = p -> next;
   p -> next = temp;
    }
  
}
void  CIntLink::Remove( int  iIndex)     // iIndex 从0开始，即第一个值也即头指针为iIndex为0
{
     if (iIndex == 0 )
     {
        NODE  *  p = head;
       head = head -> next;
        delete p;
        p = NULL;
    }
     else   if (iIndex == 1 )
     {
        NODE  *  p2 = head -> next;
        head -> next = p2 -> next;
        delete p2;
        p2 = NULL;
    }
     else
     { 
        NODE  * pre = head -> next;
        NODE  * p = pre -> next;
      
        for ( int  i = 2 ;p != NULL;i ++ )   // p 为要删除的值的位置
        {      
         if  (iIndex == i)   break ;
        pre = p;p = p -> next;
       }
        if (iIndex == i && p != NULL)
        {
           pre -> next = p -> next;
          delete p;
          p = NULL;
      }
       else                          // p->NULL
       {
          cout << " remove fail:no fond iIndex " << endl;
      }
   }
}
  void  CIntLink::Insert( int  iIndex,  int  iValue)
 {
     if (iIndex == 0 )
     {
        NODE  *  p1 = new  NODE;
        p1 -> data = iValue;
        p1 -> next = head;
        head = p1;
    }
     else   if (iIndex == 1 )
     {
        NODE  *  p2 = new  NODE;
        p2 -> data = iValue;
        p2 -> next = head -> next;
        head -> next = p2;
    }
     else
     {
        NODE  * pre = head -> next;
        NODE  * pp = pre -> next;
        
         for ( int  i = 2 ;pp != NULL;i ++ )   // i为要插入的值的位置
         {
             if  (iIndex == i)   break ;
            pre = pp;pp = pp -> next;

        }
         if (iIndex == i && pp != NULL) 
         {
            NODE  * q = new  NODE;
            q -> data = iValue;
            q -> next = pp -> next;
            pre -> next = q;
            q -> next = pp;

        }
          else                 // (pp->next=NULL)
         {
            cout << " insert fail:iIndex is out of range  " << endl;
        }
    
    }
}
int   CIntLink::Find( int  iValue)
  {
      if (head == NULL)
      {
         cout << " find fail:no found ivalue ,and it retrun is -1 " << endl;
          return   - 1 ;
     }
     NODE  * pp =  head;
     for ( int  i = 0 ;pp -> next != NULL;i ++ )
       if (pp -> data == iValue)
       {
        return  i; // --i;
      }  
       else
       pp = pp -> next;

    cout << " find fail:no found ivalue,and it return is -1 " << endl; 
     return   - 1 ;
      
}
  void  CIntLink::output()
  {
     NODE  *  p = head;
     cout << " the link data is : " << endl;
      for (;p != NULL;p = p -> next)
         cout << p -> data << endl;
 }
  int  CIntLink::size()
  {
     NODE  *  p = head;
      int  i = 0 ;
      for ( ;p != NULL;p = p -> next,i ++ );
      return  i;
         
 }
int  _tmain( int  argc, _TCHAR *  argv[])
 {
    CIntLink link;
    link.Add( 10 );
    link.Add( 30 );
    link.Add( 40 );
    link.Add( 50 );
    link.Insert( 5 , 20 );
    link.Remove( 5 );
     int  num = link.size();
    cout << " the link data number is : " << num << endl;
    link.output();
     int  re = link.Find( 20 );
    cout << re << endl;
 
     return   0 ;
}
以上的析构函数,应该先判断为NULL,再delete.

别人写的：
#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

posted on 2005-10-28 08:42 梦在天涯 阅读(2442) 评论(6)  编辑 收藏 引用 所属分类: CPlusPlus 、Data Arithmetic

评论

# re: c＋＋单向链表 （讨论应不应该在默认的构造里就分配空间） 2005-11-02 08:12 怀沙

应该要有拷贝构造函数哦，否则在进行
CIntLink link2(link);
这样的操作时只会复制头结点的指针，而不是重新初始化一个链表哦  回复  更多评论   

# re: c＋＋单向链表 （讨论应不应该在默认的构造里就分配空间） 2005-11-02 17:28 magician

楼上说的还可以,如果为了使程序更加我完善,有健壮性,我还是喜欢用template<class T>
的方式来创建一个连表,  回复  更多评论   

# re: c＋＋单向链表 （讨论应不应该在默认的构造里就分配空间） 2005-11-03 16:19 梦在天涯

楼上的楼上说的拷贝构造函数是不是每个节点都的重新new，啊？  回复  更多评论   

# re: c＋＋单向链表 （讨论应不应该在默认的构造里就分配空间） 2005-11-15 16:35 yanfei

请问采用template<class T>的方式有什么好处呢?
  回复  更多评论   

# re: c＋＋单向链表 （讨论应不应该在默认的构造里就分配空间） 2005-12-10 00:10 寒曙

好处当然是不言自明咯，算法严谨，安全，可重用性高……
  回复  更多评论   

# re: c＋＋单向链表 （讨论应不应该在默认的构造里就分配空间） 2005-12-29 12:34 nanami

构造拷贝应该进行值拷贝。仅仅拷贝外部变量指针，在C++中极易造成内存泄漏，构成安全隐患。

除非你的程序对性能要求极高，或者你的链表长度极长（一般>100000项，相对于现在的计算机内存操作性能，才应算做极长，当然，实际情况也要综合考虑链表每一项的长度。），并且你保证外部变量在此类所生成的实例的生存周期内一直有效，那么仅仅传递指针是可以的。 不过这样一来，你DEBUG的时间会高出N倍，而且极易留下后患。尤其在对安全性和稳定性较高的领域，宁可牺牲些许性能，也要尽量保证安全。

顺便多句嘴，链表如果>100000项，尽量考虑RedBlackTree或者Map/HashMap，这样查找的性能比链表高的多得多得多得多得多，而插入最末项的性能也并会不比链表慢。尤其如果链表需要进行按顺序插入合适的位置，那么那个速度- -！我想你看到了，会以为死机了。

单项链表，N项，查找其中一个值最大时间O(N)。而对于红黑树或MAP，最大时间仅需O(log2(N))次操作，HASHMAP的查找时间恒定，只和HASH函数的速度相关。一般来说，对于极大数据结构操作HASHMAP是最理想的。  回复  更多评论   


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


公告

EMail：itech001#126.com

导航

统计

  • 随笔 - 461
  • 文章 - 4
  • 评论 - 746
  • 引用 - 0

常用链接

随笔分类

随笔档案

收藏夹

Blogs

c#(csharp)

C++(cpp)

Enlish

Forums(bbs)

My self

Often go

Useful Webs

Xml/Uml/html

搜索

  •  

积分与排名

  • 积分 - 1795783
  • 排名 - 5

最新评论

阅读排行榜