加载中

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

顺序串(SeqString)

template<int MAXN>
class SeqString {
    char data[MAXN+1];
    int n;
public:
    SeqString(){ n=0; data[0]='\0'; }

    SeqString(const char* s){
        n=0;
        while(s[n]!='\0'){
            if(n==MAXN) throw length_error("SeqString too long");
            data[n]=s[n];
            n++;
        }
        data[n]='\0';
    }

    bool empty() const { return n==0; }
    int size() const { return n; }
    int length() const { return n; }
    int capacity() const { return MAXN; }
    const char* c_str() const { return data; }

    char& operator[](int i){ return data[i]; }
    const char& operator[](int i) const { return data[i]; }

    char& at(int i){
        if(i<0 || i>=n) throw out_of_range("SeqString::at");
        return data[i];
    }

    bool append(const SeqString& other){
        if(n+other.n>MAXN) return false;
        for(int i=0;i<other.n;i++) data[n+i]=other.data[i];
        n+=other.n;
        data[n]='\0';
        return true;
    }

    bool insert(int pos,const SeqString& other){
        if(pos<0 || pos>n || n+other.n>MAXN) return false;
        for(int i=n-1;i>=pos;i--) data[i+other.n]=data[i];
        for(int i=0;i<other.n;i++) data[pos+i]=other.data[i];
        n+=other.n;
        data[n]='\0';
        return true;
    }

    bool erase(int pos,int len){
        if(pos<0 || pos>n || len<0) return false;
        if(pos+len>n) len=n-pos;
        for(int i=pos;i+len<n;i++) data[i]=data[i+len];
        n-=len;
        data[n]='\0';
        return true;
    }

    SeqString substr(int pos,int len) const{
        if(pos<0 || pos>n || len<0) throw out_of_range("SeqString::substr");
        if(pos+len>n) len=n-pos;
        SeqString ans;
        for(int i=0;i<len;i++) ans.data[i]=data[pos+i];
        ans.n=len;
        ans.data[len]='\0';
        return ans;
    }

    int find(const SeqString& pat) const{
        if(pat.n==0) return 0;
        if(pat.n>n) return -1;

        for(int i=0;i+pat.n<=n;i++){
            int j=0;
            while(j<pat.n && data[i+j]==pat.data[j]) j++;
            if(j==pat.n) return i;
        }
        return -1;
    }

    bool operator==(const SeqString& other) const{
        if(n!=other.n) return false;
        for(int i=0;i<n;i++) if(data[i]!=other.data[i]) return false;
        return true;
    }

    void clear(){ n=0; data[0]='\0'; }
};

工程细节

  • data 有 MAXN + 1 个位置,额外位置留给 \0;n 不包含终止字符。修改长度后重新写入 data[n] = '\0'。
  • 插入先从后往前移动原字符。这版不能直接把自身作为插入来源,应先在外部复制一份,避免原串被移动后污染来源。
  • 插入和追加前检查两串长度之和是否超过容量;删除和截取会把过大的 len 截断到剩余长度。
  • find() 为朴素匹配,空模式返回 0,未找到返回 -1。下标访问不检查边界,不能改写终止字符;构造参数必须指向有效、以 \0 结尾的字符序列。

跳转

下一个:无头结点单链表

上一个:循环顺序队列

本文作者:flowwalker之码艺Blog

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

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