加载中

手写数据结构·线性表01:顺序表

顺序表(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 需要能默认构造和复制赋值。

跳转

下一个:动长数组

上一个:前言与目录

本文作者:flowwalker之码艺Blog

本文链接:/coding-notes-blog/posts/44029136/

版权声明:本文采用 CC BY-NC-SA 4.0 许可协议