#include <iostream>
using namespace std;
class ilist_item
{
public:
ilist_item( int value, ilist_item *item_to_lind_to = 0);
int value()
{
return _value;
}
ilist_item * next()
{
return _next;
}
void next( ilist_item *link )
{
_next = link;
}
void value( int new_value )
{
_value = new_value;
}
private:
int _value;
ilist_item *_next;
};
inline ilist_item::ilist_item( int value, ilist_item *item ):_value( value )
{
if ( !item )
_next = 0;
else
{
_next = item->_next;
item->_next=this;
}
}
class ilist
{
public:
ilist()
{
_at_front = 0;
_at_end = 0;
_size = 0;
}
int size();
void bump_up_size();
void bump_down_size();
ilist_item* find( int value );
void insert( ilist_item *ptr, int value );
void insert_front( int value );
void insert_end( int value );
void display( ostream &os = cout);
int remove( int value );
void remove_front();
void remove_all();
void concat( const ilist &il );
void reverse();
void insert_all( const ilist &rhs );
inline ilist( const ilist &rhs );
inline ilist& operator= ( const ilist &rhs );
inline ilist_item* ilist::init_iter( ilist_item *it = 0 );
inline ilist_item* ilist::next_iter();
private:
ilist_item *_at_front;
ilist_item *_at_end;
int _size;
ilist_item *_current;
};
inline int ilist::size()
{
return _size;
}
inline void ilist::bump_up_size()
{
++_size;
}
inline void ilist::bump_down_size()
{
--_size;
}
inline void ilist::insert( ilist_item *ptr, int value )
{
if ( !ptr )
insert_front( value );
else
{
new ilist_item( value, ptr );
++_size;
}
}
inline void ilist::insert_front( int value )
{
ilist_item *ptr = new ilist_item( value );
if ( !_at_front )
_at_front = _at_end = ptr;
else
{
ptr->next( _at_front );
_at_front = ptr;
}
bump_up_size();
}
inline void ilist::insert_end( int value )
{
if ( !_at_end )
_at_end = _at_front = new ilist_item( value );
else
_at_end = new ilist_item ( value ,_at_end );
bump_up_size();
}
ilist_item *ilist::find( int value )
{
ilist_item *ptr = _at_front;
while ( ptr )
{
if ( ptr->value() == value )
break;
ptr = ptr->next();
}
return ptr;
}
void ilist::display( ostream &os )
{
os << "\n(" << _size << ")(";
ilist_item *ptr = _at_front;
while ( ptr )
{
os << ptr->value() << " ";
ptr = ptr->next();
}
os << ")\n";
}
inline void ilist::remove_front()
{
if ( _at_front )
{
ilist_item *ptr = _at_front;
_at_front = _at_front->next();
if ( _current == ptr )
_current = _at_front;
bump_down_size();
delete ptr;
}
}
void ilist::remove_all()
{
while ( _at_front )
{
remove_front();
}
_size = 0;
_at_front = _at_end = 0;
}
int ilist::remove( int value )
{
ilist_item *plist = _at_front;
int elem_cnt = 0;
while ( plist && plist->value() == value )
{
plist = plist->next();
remove_front();
++elem_cnt;
}
if ( ! plist )
return elem_cnt;
ilist_item *prev = plist;
plist = plist->next();
while ( plist )
{
if ( plist->value() == value )
{
prev->next( plist->next() );
if( _current == plist )
_current = prev->next();
delete plist;
++elem_cnt;
bump_down_size();
plist = prev->next();
if( ! plist )
{
_at_end = prev;
return elem_cnt;
}
}
else
{
prev = plist;
plist = plist->next();
}
}
return elem_cnt;
}
void ilist::concat( const ilist &il )
{
if ( ! _at_end )
_at_front = il._at_front;
else
_at_end->next( il._at_front );
_at_end = il._at_end;
}
void ilist::reverse()
{
ilist_item *ptr = _at_front;
ilist_item *prev = 0;
_at_front = _at_end;
_at_end = ptr;
while ( ptr != _at_front )
{
ilist_item *tmp = ptr->next();
ptr->next( prev );
prev = ptr;
ptr = tmp;
}
_at_front->next( prev );
}
void ilist::insert_all( const ilist &rhs )
{
ilist_item *pt = rhs._at_front;
while ( pt )
{
insert_end ( pt->value() );
pt = pt->next();
}
}
inline ilist::ilist( const ilist &rhs )
{
_at_front = 0;
_at_end = 0;
insert_all( rhs );
}
inline ilist& ilist::operator= ( const ilist &rhs )
{
if( this !=&rhs )
{
remove_all();
insert_all( rhs );
}
return *this;
}
inline ilist_item* ilist::init_iter( ilist_item *it )
{
return _current = it ? it : _at_front;
}
inline ilist_item* ilist::next_iter()
{
ilist_item *next = _current ? _current = _current->next() : _current;
return next;
}
int main()
{
ilist mylist;
for ( int ix = 0; ix< 10; ++ix )
{
mylist.insert_front( ix );
mylist.insert_end( ix );
}
cout << "Ok: after insert_front() and insert_end()(执行插入头数据和尾数据之后：)\n";
mylist.display();
ilist_item *it = mylist.find( 8 );
cout << "\n"<< " Searching for the value 8: found it<<"
<<( it ? " yes! \n" : "no!\n")<<"（找到了数据 8之后： ）\n";
mylist.insert( it, 1024 );
cout << "\n"<< " Inserting element 1024 following the value 8(在数据8之前插入1024之后：)\n";
mylist.display();
int elem_cnt = mylist.remove( 8 );
cout<< "\n"<< "Removed "<< elem_cnt << " of the value 8（移除数据8之后：）\n";
mylist.display();
cout<< "\n"<< "Removed front element（移除头数据之后：）\n";
mylist.remove_front();
mylist.display();
cout<< "\n" << "Removed all elements（移除所有元素之后：）\n";
mylist.remove_all();
mylist.display();
for ( ix = 0; ix< 10; ++ix )
{
mylist.insert_front( ix );
mylist.insert_end( ix );
}
ilist_item *iter;
cout << "\niterate across each list item(迭代整个链表输出):\n" ;
for( iter = mylist.init_iter(); iter; iter = mylist.next_iter() )
cout << iter->value() << " ";
cout<< "\n\nUse of copt constructor(使用拷贝构造函数后)\n";
ilist mylist2( mylist );
mylist.remove_all();
for( iter = mylist2.init_iter(); iter; iter = mylist2.next_iter() )
cout << iter->value() << " ";
cout<< "\n\nUse of copy assignment operator（使用重载运算符赋值）\n";
mylist = mylist2;
for ( iter = mylist.init_iter();iter;iter = mylist.next_iter() )
cout<< iter->value() << " ";
cout<<endl;
cout<<"\n\nThe following datas are new datas（后面为新的数据）:\n";
for (ix = 0; ix < 10; ++ix )
{
mylist.insert_front( ix );
}
cout<< "\n"<<"mylist_too（第一个链表为）:\n";
mylist.display();
cout << "\n"<<"reverse the list（翻转链表之后：）\n";
mylist.reverse();
mylist.display();
ilist mylist_too;
mylist_too.insert_end( 0 );
mylist_too.insert_end( 1 );
mylist_too.insert_end( 1 );
mylist_too.insert_end( 2 );
mylist_too.insert_end( 3 );
mylist_too.insert_end( 5 );
cout<< "\n"<<"mylist_too（第二个链表为）:\n";
mylist_too.display();
mylist.concat( mylist_too );
cout << "\n" << "mylist after concat with mylist_too（mylist_too链表的数据链接到mylist链表上之后）:\n";
mylist.display();
return 0;
}
- 1
- 2
前往页