加载中

手写数据结构·线性表17:链式串

链式串(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() 返回的新串独立持有自己的结点。

跳转

下一个:无(本子专题完)

上一个:链式队列

本文作者:flowwalker之码艺Blog

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

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