顺序表(SeqList)
template<class T, int MAXN>
class SeqList {
T data[MAXN];
int n;
public:
SeqList(): n(0) {}
bool empty() const { return n==0; }
bool full() const { return n==MAXN; }
int size() const { return n; }
int capacity() const { return MAXN; }
T& operator[](int i){ return data[i]; }
const T& operator[](int i) const { return data[i]; }
T& at(int i){
if(i<0 || i>=n) throw out_of_range("SeqList::at");
return data[i];
}
int find(const T& x) const {
for(int i=0;i<n;i++) if(data[i]==x) return i;
return -1;
}
bool insert(int pos,const T& x){
if(full() || pos<0 || pos>n) return false;
for(int i=n;i>pos;i--) data[i]=data[i-1];
data[pos]=x; n++;
return true;
}
bool erase(int pos){
if(pos<0 || pos>=n) return false;
for(int i=pos;i<n-1;i++) data[i]=data[i+1];
n--;
return true;
}
bool push_back(const T& x){ return insert(n,x); }
bool pop_back(){ if(empty()) return false; n--; return true; }
void clear(){ n=0; }
};
工程细节
- 有效元素始终位于
[0, n)。插入允许 pos == n,删除要求 pos < n。
- 插入从后向前搬,删除从前向后填坑。待插入值如果来自表内被搬动的元素,应先在外部保存副本,避免搬移时覆盖它。
clear()、pop_back() 和 erase() 只调整逻辑长度,不清零,也不立即析构数组槽位中的对象。
- 模板容量
MAXN 必须大于零;本实现直接声明数组,因此 T 需要能默认构造和复制赋值。
跳转
下一个:动长数组
上一个:前言与目录