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