0001 #include <assert.h> 0002 #include "_share/util.h" 0003 #include "UniPrint/print.h" 0004 0005 typedef int Rank; //秩 0006 #define DEFAULT_CAPACITY 3 //默认的初始容量(实际应用中可设置为更大) 0007 0008 template <typename T> class CursorList { //游标式列表 0009 protected: 0010 Rank _size; int _capacity; //规模、容量 0011 Rank* _link; T* _elem; //游标指针、数据区 0012 Rank _data, _free; //数据链表和空闲链表的起点 0013 public: 0014 CursorList ( int c = DEFAULT_CAPACITY ) { //容量为c 0015 _link = new Rank[_capacity = c]; //游标指针向量 0016 _elem = new T[_capacity = c]; memset ( _elem, 0, c * sizeof ( T ) ); //数据向量 0017 _data = -1; _size = 0; //数据链表初始为空 0018 _free = 0; //空闲链表由所有单元依次串接而成 0019 for ( Rank i = 0; i < c - 1; i++ ) _link[i] = i + 1; 0020 _link[c - 1] = -1; 0021 } 0022 ~CursorList() { delete [] _link; delete [] _elem; } //释放内部空间 0023 Rank size() const { return _size; } //规模 0024 bool empty() const { return !_size; } //判空 0025 Rank find ( T const& e ) const { //查找 0026 Rank i = _data; //从数据链表起点出发 0027 while ( ( 0 <= i ) && ( e != _elem[i] ) ) i = _link[i]; //依次比对 0028 return i; 0029 } 0030 Rank insert ( T const& e ) { //插入元素 0031 assert ( 0 <= _free ); 0032 Rank k = _free; _free = _link[k]; _elem[k] = e; 0033 _link[k] = _data; _data = k; 0034 _size++; return k; 0035 } 0036 Rank remove ( Rank k ) { //删除秩为k的元素 0037 assert ( 0 <= k ); //此前经查找并确认k合法 0038 if ( _data == k ) //若[k]为首节点 0039 _data = _link[k]; 0040 else { //否则 0041 Rank i = _data; while ( k != _link[i] ) i = _link[i]; 0042 _link[i] = _link[k]; 0043 } 0044 _link[k] = _free; _free = k; _elem[k] = 0; 0045 _size--; return k; 0046 } 0047 void print() { 0048 printf ( "size = %d\t:\t", _size ); 0049 for ( Rank i = _data; 0 <= i; i = _link[i] ) 0050 UniPrint::p ( _elem[i] ); 0051 printf ( "\n" ); 0052 printf ( "\t" ); for ( Rank i = 0; i < _capacity; i++ ) UniPrint::p ( i ); printf ( "\n" ); 0053 printf ( "%d\t", _free ); for ( Rank i = 0; i < _capacity; i++ ) UniPrint::p ( _link[i] ); printf ( "\n" ); 0054 printf ( "%d\t", _data ); for ( Rank i = 0; i < _capacity; i++ ) UniPrint::p ( _elem[i] ); printf ( "\n" ); 0055 printf ( "\n\n" ); 0056 } 0057 };