首页 > 代码库 > 模板实现C++队列（顺序存储）

模板实现C++队列（顺序存储）

2024-07-11 00:03:54   222人阅读

c++模板实现一个队列，包括查 插 删 改，求并集和交集，主要是想研究一下数据结构和算法，然后结合C++ template 实现一下，这个是第一个，这个分类里面的源代码没有追求尽善尽美，如果感觉有的借鉴就去去借鉴，如果感觉写的不好也别拍砖，谢谢……

模板头文件如下

  1 #ifndef  SEQUENCELIST_H  2 #define  SEQUENCELIST_H  3   4 //template of sequence list  5 //implicit interface of T , operator=() , operator<() , operator >() operator ==  6 #define SQU_LEN_INIT 100   7 #define  INSCREAMENT_SQU 10  8   9 #include <cstdlib> 10 #include <iostream> 11 using std::iostream ;  12 using std::endl ;  13 using std::cout ;  14  15 template<class T> class SquenceList 16 { 17  18 private: 19  20     size_t buf_len ;        //data buffer length 21     size_t squ_len ;        //element length in the squence 22     T * pdate ;                //the pointer to the squence head 23  24     int add_buf_length(void) ;  25 public: 26  27     ~SquenceList() ;  28     SquenceList( ) ; 29     SquenceList(T * start , T* end ) ;  30     SquenceList(const SquenceList<T> &squ_list) ;  31  32     size_t        get_buf_len( ) const ;  33     size_t        get_squ_len( ) const ;  34      35     T            get( size_t order ) const ; 36     int        insert( size_t _ins_pos , const T & _value ) ;  37     int        replace( size_t _rp_pos , const T& _value ) ;  38     int        replace( size_t _start , size_t end , T *buf ) ;  39     int        remove( size_t _rm_pos ) ;  40     int        find( const T &value ) const ; 41 //    int        find( const T &value ) const ;  42     T&        operator[ ] (int order) ;  43  44     int        push( const T & _value ) ;  45     int        pop( ) ; 46     T&        front( ) ;  47  48 // 49     int        merge( const SquenceList<T> & _squ ) ; 50     int        intersection(const SquenceList<T> & _squ ) ; 51  52 }; 53  54  55 template<class T> SquenceList<T> :: SquenceList( ) 56 { 57     pdate      =    new T[SQU_LEN_INIT] ; 58     buf_len  =    SQU_LEN_INIT ;  59     squ_len  =    0 ; 60 } 61 template<class T> SquenceList<T> :: SquenceList(T *start , T *end )              //default constructor 62 { 63     squ_len = end - start + 1 ;  64     if( squ_len < 0 ) 65     { 66         cout<<"the pointer is wrong!!"<<endl ;  67         system("pause") ;  exit(-1) ;  68     } 69      70     buf_len = ( squ_len < SQU_LEN_INIT ? SQU_LEN_INIT : squ_len ) ;  71     pdate = new T[ buf_len ] ; 72      73     //将数组中的元素拷贝到新建数组中  //可以优化 74     //for循环赋值 75     for( size_t i = 0 ; i < squ_len ;  i++ ) 76     { 77         *( pdate + i ) =  *( start + i ) ;                                                                            //operator = 78     } 79      80 } 81 template<class T> SquenceList<T> :: SquenceList(const SquenceList<T> & _squ_list)  //operator =  82 { 83     squ_len = _squ_list . get_buf_len() ;  84     buf_len = _squ_list . get_buf_len () ; 85     pdate = new T[ buf_len ] ; 86      87     for(size_t i = 0 ; i < squ_len ; i++ ) 88     { 89         pdate[ i ] = _squ_list.get( i ) ;  90     } 91 } 92  93  94 template<class T> size_t SquenceList<T>:: get_buf_len() const { return buf_len ; } 95 template<class T> size_t SquenceList<T>::get_squ_len()  const { return squ_len ; } 96  97 template< class T> int SquenceList<T> :: replace (size_t _rp_pos ,  const T &_value ) 98 { 99     if(_rp_pos >=squ_len || _rp_pos < 0 ) 100     {    101         cout<<"error replace() _rp_pos overflow!!!"<<endl ;     return -1 ; 102     }103     104     pdate[ _rp_pos ] = _value ;                                                                                                            //operator105     return 0 ; 106 }107 template< class T> int SquenceList<T> :: replace ( size_t _start , size_t _end , T *buf )108 {109     if(_start >= _end )110     {111         cout<<"ERROR:!! the the replace position error"<<endl ; 112         return -1 ; 113     }114 115     for(size_t i = _start ;  i <= _end ; i++)116     {117         if(replace( i , buf[ i - _start ]) == -1)118         {119             cout<<"the rang of the replace data error"<<endl ; 120             return -1; 121         }; 122     }123     124     return 0 ; 125 }126 127 128 template<class T> int SquenceList<T> :: remove( size_t _rm_pos )129 {130     if( _rm_pos <0 ||  _rm_pos >= squ_len ) 131     {132         cout<<"_rm_pos ERROR"<<endl  ; return -1; 133         return -1 ;134     }135     136     if(_rm_pos != squ_len - 1 ) 137     {138         for(size_t i = _rm_pos ; i < squ_len - 1 ; i++)139         {140             replace(i , pdate[i + 1 ] ) ; 141         }142     }143     144     squ_len = squ_len -1 ; 145     return 0 ; 146 147 }148 template<class T>  int SquenceList <T> :: find( const T &value ) const149 150 {151     152     for(size_t i = 0 ; i < buf_len ; i++)153     {154         if( pdate[ i ] == value )155             return i ; 156     }157     158     return -1 ; 159 160 }161 162 template< class T> T  SquenceList<T>:: get(size_t _pos) const                // copy constructor  and assigning constructor163 {164     if( _pos >= squ_len || _pos < 0 )165     {    cout<<"error _pos flow out"<<endl ;  exit(-1) ; }166 167     return pdate[ _pos ] ;168 }169 template< class T > int SquenceList<T> :: insert( size_t _ins_pos , const T & _value )170 {171     if(_ins_pos < 0 || _ins_pos > squ_len)172     {173         cout<<"the insert place ERROR"<<endl ; 174         return -1 ; 175     }176 177     if(squ_len == buf_len)178     {179         if(add_buf_length() != 0 ) 180         {181             cout<<"insert ERROR: add buffer error"<<endl ; 182             return -1; 183         }184     }185 186     for(size_t i = squ_len - 1 ; i >= _ins_pos ; i-- )187     {188         if(replace( i + 1 , pdate[ i ] ) != 0)189             cout<<"insert ERROR:"<<endl ; 190         //here if a error is detected the date need to be recovered 191     }192 193     pdate[ _ins_pos ] = _value ; 194     squ_len++ ; 195     return 0 ; 196 197 }198 template< class T > int SquenceList<T> :: pop()199 {200     if(remove(0) != 0)201     {202         cout<<"pop ERRROR"<<endl  ; 203         return -1 ; 204     }205     return 0 ; 206 }207 template< class T > int SquenceList<T> ::push(const T & _value)208 {209     210     if(insert(squ_len , _value) != 0)211     {212         cout<<"insert ERROR"<<endl ; 213         return -1;214     }215     216     return 0 ; 217 218 }219 220 template <class T> int SquenceList<T> :: merge(const SquenceList<T>& _squ)221 {222     for( size_t i = 0  ; i < _squ.get_squ_len()  ; i++ )223     {224         if( find( _squ.get( i )) == -1 )225             push(_squ.get(i)) ; 226     }227 228     return 0 ; 229 }230 231 template<class T > int SquenceList<T> :: intersection(const SquenceList< T>& _squ)232 {233     for( size_t i = 0 ; i < squ_len ; i++)234     {235         int dest = -1 ; 236 //如果确实不需要改变类或则模板中的元素，最好将定义成 const 原因这里就是；237 //非const 函数不能用 const 指针或者引用调用238         dest = _squ . find( get( i ) ) ;                239         if( dest == -1 ) { remove( i ) ; i-- ; }        //这里有一个小技巧“回移底标"240     }241 242     return 0 ; 243 }244 245 template < class T>  int SquenceList<T> :: add_buf_length(void)246 {247 248     int buf_len_temp = this -> get_buf_len() ; 249     T * pdate_temp = pdate ; 250     251     if( ( pdate= new T[ buf_len + INSCREAMENT_SQU]) == NULL )252         {253             cout<<"ERROR:memory allocate fail "<<endl ; 254             return -1;255         }256     257     for( size_t i = 0 ; i < squ_len ; i++ )        //copy date258     {259         pdate[ i ] = pdate_temp[ i ] ; 260     }261 262     buf_len = buf_len_temp + INSCREAMENT_SQU ; 263 264     return 0 ;265 266 }267 268 template < class T > SquenceList<T> :: ~SquenceList( )269 {270     if(buf_len != 0 )271         delete []pdate ; 272     pdate == NULL ; 273     274 }275 276 #endif

 

功能模块儿测试代码如下

  1 #include <iostream>  2 #include "SequenceList.h"  3   4 using std::cout ;  5 using std::cin ;   6 using std::endl ;   7   8 void test(SquenceList<int> &_squlist)  9 { 10     cout<<"buffer length:"<<_squlist.get_buf_len()<<endl ;  11     cout<<"squence length:"<<_squlist.get_squ_len()<<endl ;  12     for(size_t i = 0 ; i <_squlist.get_squ_len() ; i++ )  13     { 14         cout<<"squence["<<i<<"]="<<_squlist.get(i)<<endl ;  15     } 16 } 17  18 int main(int argc , char ** argv) 19 { 20     //template<class T> SquenceList<T> :: SquenceList() 21     SquenceList<int> squ_def_cons ; 22     test(squ_def_cons) ;  23      24  25     //template<class T> SquenceList<T> :: SquenceList(T *start , T *end )  26     cout<<"template<class T> SquenceList<T> :: SquenceList(T *start , T *end )"<<endl ;  27     int paa[100]; 28     for(int  i = 0 ; i <100 ;  i++) 29     { 30         paa[ i ] = i ;  31     } 32     SquenceList<int> squ_ptr_const(paa , paa+ 99) ;  33     test(squ_ptr_const) ;  34  35     cout<<"template<class T> SquenceList<T> :: SquenceList(const SquenceList<T> & _squ_list)"<<endl ;  36     SquenceList<int> squ_copy_const(squ_ptr_const) ;  37     test(squ_copy_const) ;  38  39  40     cout<<"template< class T> int SquenceList<T> :: replace (size_t _rp_pos ,  const T &_value )"<<endl ;  41     int rep = 100 ;  42     squ_ptr_const.replace(0 , rep) ;  43     squ_ptr_const.replace(100 , rep) ;  44     squ_ptr_const.replace(-1 , rep ) ; 45     test(squ_ptr_const) ;  46      47      48     cout<<"template< class T> int SquenceList<T> :: replace ( size_t _start , size_t _end , T *buf )"<<endl ;  49     int reparr[10] ;  50     for(int i = 0 ; i < 10 ; i++) 51     { 52         reparr[i] = i * 10 ;  53     } 54     SquenceList<int> squ_rep_test(paa , paa+ 99 ) ; 55     squ_rep_test.replace(0 , 9 , reparr ) ;  56     test(squ_rep_test) ;  57  58  59     cout<<"template< class T> int SquenceList<T> :: remove( size_t _rm_pos )"<<endl ;  60     SquenceList <int> squ_rm_test(paa, paa + 99 )  ;  61     squ_rm_test.remove(1) ;  62     test(squ_rm_test) ;  63  64  65     cout<<"template<class T> int SquenceList <T> :: find( const T &value )"<<endl ;  66     SquenceList<int> squ_find_test(paa , paa + 99 ) ; 67     cout<<"find result "<<squ_find_test.find(11)<<endl ;  68     test(squ_find_test) ;  69  70  71     cout<<"template<class T> int SquenceList<T> :: insert(int _ins_pos , T & _value)"<<endl ;  72     SquenceList<int> squ_insert_test(paa  ,  paa + 99) ;  73     int test_ins = 1000 ;  74     squ_insert_test.insert(100 , test_ins) ; 75     test(squ_insert_test) ;  76  77     cout<<"template<class T> SquenceList<T> :: pop()"<<endl ;  78     SquenceList< int > squ_pop_test(paa , paa + 99) ;  79     squ_pop_test.pop() ;  80     squ_pop_test.push(10000) ;  81     test(squ_pop_test) ;  82  83  84     cout<<"template<class T> SquenceList<T> :: merge(const SquenceList<T> _squ)"<<endl ; 85     int pmerg[10] = {95 , 96 , 97 , 98 , 99 , 100 , 101 , 102 , 103 , 104 } ;  86     SquenceList< int > squ_merge_test1(pmerg , pmerg + 9 ) ; 87     SquenceList< int > squ_merge_test2(paa , paa + 99 ) ; 88     squ_merge_test2.merge(squ_merge_test1) ;  89     test(squ_merge_test2) ;  90      91     cout<<"template<class T> SquenceList<T>::intersection(const SquenceList<T> _squ)"<<endl ; 92     int pintersec[10] = {95 , 96 , 97 , 98 , 99 , 100 , 101 , 102 , 103 , 104 } ;  93     SquenceList< int > squ_intersec_test1(pintersec , pintersec + 9 ) ; 94     SquenceList< int > squ_intersec_test2(paa , paa + 99 ) ; 95     squ_intersec_test2 .intersection(squ_intersec_test1) ;  96     test(squ_intersec_test2) ;  97  98     system("pause") ;  99     return 0 ;100     101 }

 


联系
我们