顺序串(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 结尾的字符序列。
跳转
下一个:无头结点单链表
上一个:循环顺序队列