链式串(LinkedString)
class LinkedString {
struct Node {
char ch;
Node* next;
Node(char c='\0'){ ch=c; next=nullptr; }
};
Node* head; // dummy head
Node* tail;
int n;
Node* prevAt(int pos) const{
Node* p=head;
while(pos--) p=p->next;
return p;
}
public:
LinkedString(){
head=new Node;
tail=head;
n=0;
}
LinkedString(const char* s){
head=new Node;
tail=head;
n=0;
while(*s!='\0'){
push_back(*s);
s++;
}
}
LinkedString(const LinkedString& other){
head=new Node;
tail=head;
n=0;
Node* p=other.head->next;
while(p!=nullptr){
push_back(p->ch);
p=p->next;
}
}
LinkedString& operator=(const LinkedString& other){
if(this==&other) return *this;
clear();
Node* p=other.head->next;
while(p!=nullptr){
push_back(p->ch);
p=p->next;
}
return *this;
}
~LinkedString(){
clear();
delete head;
}
bool empty() const { return n==0; }
int size() const { return n; }
int length() const { return n; }
void push_back(char c){
tail->next=new Node(c);
tail=tail->next;
n++;
}
bool insert(int pos,const LinkedString& other){
if(pos<0 || pos>n) return false;
// 支持 s.insert(..., s):先临时保存 other 的字符
char* tmp=new char[other.n];
Node* p=other.head->next;
for(int i=0;i<other.n;i++){
tmp[i]=p->ch;
p=p->next;
}
Node* prev=prevAt(pos);
Node* after=prev->next;
for(int i=0;i<other.n;i++){
prev->next=new Node(tmp[i]);
prev=prev->next;
}
prev->next=after;
if(after==nullptr) tail=prev;
n+=other.n;
delete[] tmp;
return true;
}
void append(const LinkedString& other){
insert(n,other);
}
bool erase(int pos,int len){
if(pos<0 || pos>n || len<0) return false;
if(pos+len>n) len=n-pos;
Node* prev=prevAt(pos);
while(len--){
Node* q=prev->next;
prev->next=q->next;
delete q;
n--;
}
if(prev->next==nullptr)
tail=prev;
return true;
}
LinkedString substr(int pos,int len) const{
if(pos<0 || pos>n || len<0)
throw out_of_range("LinkedString::substr");
if(pos+len>n) len=n-pos;
LinkedString ans;
Node* p=prevAt(pos)->next;
while(len--){
ans.push_back(p->ch);
p=p->next;
}
return ans;
}
int find(const LinkedString& pat) const{
if(pat.n==0) return 0;
if(pat.n>n) return -1;
Node* start=head->next;
for(int i=0;i+pat.n<=n;i++){
Node* a=start;
Node* b=pat.head->next;
while(b!=nullptr && a->ch==b->ch){
a=a->next;
b=b->next;
}
if(b==nullptr) return i;
start=start->next;
}
return -1;
}
char at(int pos) const{
if(pos<0 || pos>=n) throw out_of_range("LinkedString::at");
return prevAt(pos)->next->ch;
}
void clear(){
Node* p=head->next;
while(p!=nullptr){
Node* q=p;
p=p->next;
delete q;
}
head->next=nullptr;
tail=head;
n=0;
}
};
工程细节
- 采用 dummy 加尾指针;空串时
tail == head且head->next == nullptr。按位置访问仍为O(n),每字符一个结点,存储密度较低。 - 自插入前先把来源字符抄进临时数组,避免边遍历边增长自身;插入后用
delete[]释放临时数组。 - 在末尾插入后更新
tail,删除尾部后让tail指向最后保留的结点;删光后它应回到 dummy。 - 复制构造逐字符新建结点;赋值先检查自赋值,再清空并复制,不能直接复制头尾指针。
find()是朴素匹配,空模式返回0,找不到返回-1;substr()返回的新串独立持有自己的结点。
跳转
下一个:无(本子专题完)