«
»

一个链表类的实现（C++ PRIMER学习笔记）

Posted by 机器人 on 14th 四月 2007 in c/c++

链表是一个数据项序列每个数据项都包含一个某种类型的值和链表下一项的地址地址可以为空null 链表也可以为空即链表中可以没有数据项链表不可能为满但是当程序的空闲存储区被耗尽时试图创建一个新链表项会失败链表类必须支持的操作是什么用户必须能够插入insert 或删除remove 以及查找find 一个项用户必须能够查询链表的长度size 显示display 链表以及比较两个链表是否相等equality 另外还要支持翻转reverse 链表以及连接concatenate
两个链表:
接口部分
list.h

///list.h
using namespace std;
class ilist_item {
    public:
        ilist_item( int value, ilist_item *item_to_link_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;
};
 
class ilist {
    public:
        ilist() : _at_front( 0 ),_at_end( 0 ), _size( 0 ) {}
        int size();
        void insert( ilist_item *ptr, int value );
        void bump_up_size();
        void bump_down_size();
        void insert_front( int value );
        void insert_end( int value );
        ilist_item* find( int value );
        void display( ostream &os = cout );
        void remove_front();
        void remove_all();
        int remove( int value );
        //连接两个链表
        void concat( const ilist &il );
        //翻转一个链表
        void reverse();
        void insert_all( const ilist &rhs );
        ilist( const ilist& );
        ilist& operator=( const ilist& );
    private:
        //禁止用一个链表对象初始化或赋值给另一个
        // ilist( const ilist& );
        //ilist& operator=( const ilist& );
        ilist_item *_at_front;
        ilist_item *_at_end;
        int _size;
        int _value;
        ilist_item *_next;
};

实现部分
list.cpp

//list.cpp
#include < iostream >
#include "list.h"
using namespace std;
 
inline ilist_item::ilist_item( int value, ilist_item *item ) : _value( value ) {
    if ( !item ) {
        _next = 0;
    } else {
        //这两步要多加注意
        _next = item->_next;
        item->_next = this;
    }
}
 
inline  void ilist::insert( ilist_item *ptr, int value ) {
    if ( !ptr ) {
        insert_front( value );
    } else {
        bump_up_size();
        new ilist_item(value, ptr );
    }
}
 
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;
}
 
 
//拷贝构造函数
ilist::ilist( const ilist &rhs ): _at_front( 0 ), _at_end( 0 ) {
    insert_all( rhs );
}
 
void ilist::insert_all( const ilist &rhs ) {
    ilist_item *pt = rhs._at_front;
    while ( pt ) {
        insert_end( pt->value() );
        pt = pt->next();
    }
}
 
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();
        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() );
            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 ) {
    ilist_item *ptr = il._at_front;
    while ( ptr ) {
        insert_end( ptr->value() );
        ptr = ptr->next();
    }
}
 
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 );
}
 
inline void ilist::bump_up_size() { ++_size; }
inline void ilist::bump_down_size() { --_size; }

类测试代码

//下面类的测试代码
#include < iostream >
#include "list.h"
using namespace std;
 
int main()
{
    ilist mylist;
    /* cout < <"#####################测试一####################"<<endl;
       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" );
       mylist.insert( it, 1024 );
       cout << "\n"
       << "Inserting element 1024 following the value 8\n";
       mylist.display();
       int elem_cnt = mylist.remove( 8 );
       cout << "\n"
       << "Removed " << elem_cnt << " of the value 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();
       cout <<"#####################测试一结束################"<<endl;
       */
    /*cout <<"#####################测试二####################"<<endl;
      cout << "\n———————————————–\n"
      << "test #1: items at end\n"
      << "————————————————\n";
      mylist.insert_front( 1 );
      mylist.insert_front( 1 );
      mylist.insert_front( 1 );
      mylist.insert_front( 2 );
      mylist.insert_front( 3 );
      mylist.insert_front( 4 );
      mylist.display();
      int elem_cnt = mylist.remove( 1 );
      cout << "\n" << "Removed " << elem_cnt << " of the value 1\n";
      mylist.display();
      mylist.remove_all();
      cout << "\n———————————————–\n"
      << "test #2: items at front \n"
      << "————————————————-\n";
      mylist.insert_front( 1 ); mylist.insert_front( 1 );
      mylist.insert_front( 1 );
      mylist.display();
      elem_cnt = mylist.remove( 1 );
      cout << "\n" << "Removed " << elem_cnt << " of the value 1\n";
      mylist.display();
      mylist.remove_all();
      cout << "\n———————————————–\n"
      mylist.insert_front( 0 );
      mylist.insert_front( 2 );
      mylist.insert_front( 4 );
      mylist.display();
      elem_cnt = mylist.remove( 1 );
      cout << "\n" << "Removed " << elem_cnt << " of the value 1\n";
      mylist.display();
      mylist.remove_all();
      cout << "\n———————————————-\n"
      << "test #4: items at front and end\n"
      << "———————————————–\n";
      mylist.insert_front( 1 );
      mylist.insert_front( 1 );
      mylist.insert_front( 1 );
      mylist.insert_front( 0 );
      mylist.insert_front( 2 );
      mylist.insert_front( 4 );
      mylist.insert_front( 1 );
      mylist.insert_front( 1 );
      mylist.insert_front( 1 );
      mylist.display();
      elem_cnt = mylist.remove( 1 );
      cout << "\n" << "Removed " << elem_cnt << " of the value 1\n";
      mylist.display();
      cout << "#################测试二结束###################" << endl;*/
    cout <<"#####################测试三##################"<<endl;
    for ( int ix = 0; ix< 10; ++ix ) {
//        mylist.insert_front( ix );
        mylist.insert_front(ix);
    }
    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:\n";
    mylist.display();
    cout <<"#####################测试三结束###########"<<endl;
    return 0;
}

机器人 2007年04月14日 17:44 于 北京

分享到： 新浪微博

Leave a Reply