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> *= 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 
<< '{';
  
forint 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)  编辑 收藏 引用 所属分类: CPlusPlusData 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

搜索

  •  

积分与排名

  • 积分 - 1795889
  • 排名 - 5

最新评论

阅读排行榜