當這篇文章發布之後, 《資料結構》這一專欄的文章將會暫時停止更新一段時間. 因為在字串後面就是陣列了. 陣列的實作不可能僅靠 int 型別去完成, 所以涉及到樣板. 本人對於樣板的了解非常少, 所以之後要不斷地進修. 那麼在學習樣板之後, 這一專欄會繼續保持更新. 當然可能不是完全停止更新, 如果期間了解到新的演算法, 也會在這一專欄發表

區塊連結字串在 Google 上同樣在前幾頁搜尋不到任何信息, 名字也是我自己起的

其實區塊連結字串就是擴充了的鏈結串列. 我們通過一張關於區塊連結字串的 SVG 圖像就知道我為什麼這麼說了

本質上, 是一個非迴圈式的雙向鏈結串列, 但是其中的元素由 int 型別變為 char * 型別. 每一個 Node 構成一個區塊, 所以稱作為區塊連結字串

在我設定的區塊連結字串中, 是帶有頭部結點的, 也就是一個元素為空的 Node, 用一個叫做 head 的指標去指向它

書上對於每一個 Node 的大小是固定的, 而我通過向記憶體申請空間, 將每一個 Node 的大小改為動態可變的大小

對於這個字串來說, 最複雜的也是插入與刪除

插入

在程式碼中, 我將插入分為了三種情況

  • 在最後插入
  • 在最前面插入
  • 在中間插入 (這又分為兩種情況)
    • 插入不從每個結點所對應的字串中間插入, 也就是插入不會將原結點中的字串一分為二
    • 插入會將原結點中的字串一分為二

最複雜的屬於會將原結點中的字串一分為二的插入 : 我們首先要將原結點拆開分為兩個結點, 然後在兩個結點中間插入一個新的 Node. 別看思想非常簡單, 但是實際上在實作的時候, 需要進行長時間的除錯

刪除

和堆積字串類似, 在區塊連結字串中刪除也分為同樣的三種情況

  • 字串的刪除會導致整個 Node 被刪除
  • 字串的刪除不會導致整個 Node 被刪除, 這又分為兩種情況
    • 刪除是從 start 位置開始的
    • 刪除是從中間位置開始的

下面是本人寫的原始碼

本次的程式碼並未經過嚴格測試, 如若有錯誤存在, 可以聯絡我或者直接添加評論. 關於原始碼的註解, 已經給的比較全面, 還有不明白的可以直接評論, 對於註解的建議也可以提出. 直接讀原始碼的函式名稱或者變數名稱可以直接了解作用

 

BlockingLinkedString.hpp :

/* The programme only passed a rough test, if you want to use it, you should test it again and seriously
 * If you want to include it in an another programme, you should delete all tips in BlockingLinkedString.cpp
 */

#ifndef BLOCKINGLINKEDSTRING_BLOCKINGLINKEDSTRING_HPP
#define BLOCKINGLINKEDSTRING_BLOCKINGLINKEDSTRING_HPP

#include <iostream>
#include <cstdlib>
#include <vector>

namespace BlockingLinkedString {
    using std::cin;
    using std::cout;
    using std::endl;
    using std::vector;
    using std::string;
    class Node {
    protected :
        char *str;
        Node *next;
        Node *previous;
        unsigned length;
    public :
        Node();
        explicit Node(unsigned length);
        explicit Node(char *str);
        ~Node();
        void insertString(char *str);
        void insertNext(Node *next);
        void insertLength(unsigned length);
        void insertPrevious(Node *previous);
        unsigned getLength();
        Node *getNext();
        Node *getPrevious();
        char *getString();
    };
    class String {
    private :
        char *copyString();
        void checkEmptyNode();      //Check whether every node's string is empty. If the node's string is empty, then delete the node.
    protected :
        Node *head;
        unsigned length;
    public :
        String();
        ~String();
        static unsigned countChar(const char *str);
        static void checkInput(string &input);
        unsigned getLength();
        void insert(const char *str, int position);
        void deleteString(const char *str);
        void deleteString(unsigned start, unsigned length);
        unsigned locate(const char *str, unsigned start = 0, bool systemCall = false);
        vector<int> locateAll(const char *str);
        char *substring(unsigned start, unsigned length);
        void replace(const char *replaced, const char *replace);
        void replaceAll(const char *replaced, const char *replace);
        void clear();
        void show();
    };
}

#endif //BLOCKINGLINKEDSTRING_BLOCKINGLINKEDSTRING_HPP

BlockingLinkedString.cpp :

#include "BlockingLinkedString.hpp"
#define LAST_POSITION (-1)

using namespace BlockingLinkedString;

Node::Node() {
    this->str = nullptr;
    this->next = nullptr;
    this->previous = nullptr;
    this->length = 0;
}
Node::Node(unsigned length) {
    this->str = new char[length];
    memset(this->str, 0, sizeof *this->str * length);
    this->length = length;
    this->next = nullptr;
    this->previous = nullptr;
}
Node::Node(char *str) {
    this->str = str;
    this->length = String::countChar(str);
    this->next = nullptr;
    this->previous = nullptr;
}
Node::~Node() {
    this->next = nullptr;
    this->previous = nullptr;
    delete []this->str;
}
void Node::insertNext(Node *next) {
    this->next = next;
}
void Node::insertLength(unsigned length) {
    this->length = length;
}
void Node::insertString(char *str) {
    this->str = str;
}
void Node::insertPrevious(Node *previous) {
    this->previous = previous;
}
Node *Node::getPrevious() {
    return this->previous;
}
Node *Node::getNext() {
    return this->next;
}
unsigned Node::getLength() {
    return this->length;
}
char *Node::getString() {
    return this->str;
}
String::String() {
    this->head = new Node;
    this->length = 0;
}
String::~String() {
    auto node {this->head->getNext()};       //iterator
    /* Delete all node. */
    while(node->getNext()) {
        auto *temp {node};      //Node that is going to be deleted.
        node = node->getNext();
        delete temp;
        temp = nullptr;
    }
    delete node;        //Delete the last node.
    node = nullptr;
    delete this->head;
    this->head = nullptr;
}
char *String::copyString() {
    if(!this->length) {
        return nullptr;
    }
    auto node {this->head};
    auto temp {new char[this->length]};
    memset(temp, 0, sizeof *temp * this->length);
    auto count {0};     //The index of temp string.
    while(node->getNext()) {
        node = node->getNext();
        auto nodeString {node->getString()};
        auto nodeLength {node->getLength()};
        for(auto i {0}; i < nodeLength; i++, count++) {
            temp[count] = nodeString[i];
        }
    }
    return temp;
}
void String::checkEmptyNode() {
    auto node {this->head};
    while((node = node->getNext())) {
        if(!strncmp(node->getString(), "", node->getLength())) {
            auto nodePrevious {node->getPrevious()};
            nodePrevious->insertNext(node->getNext());
            if(node->getNext()) {
                node->getNext()->insertPrevious(nodePrevious);
            }
            delete node;
            node = nodePrevious;
        }
    }
}
unsigned String::countChar(const char *str) {
    unsigned count {0};
    for(auto i {0}; str[i] != '\0'; i++) {
        count++;
    }
    return count;
}
void String::checkInput(string &input) {
    if(input[0] == '\\' and input[1] == '4' and input[2] == '0') {
        input[0] = '\40';
        auto size {input.size() - 2};
        for(auto i {1}; i < size; i++) {
            input[i] = input[i + 2];
        }
    }
}
unsigned String::getLength() {
    return this->length;
}
void String::insert(const char *str, int position) {
    if(position > static_cast<int>(this->length) + 1) {
        cout << "Errant position!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    this->checkEmptyNode();
    /* Convert const char * to char * */
    auto length {String::countChar(str)};
    auto strCopy {new char[length]};
    memset(strCopy, 0, sizeof *strCopy * this->length);
    for(auto i = 0; i < length; i++) {
        strCopy[i] = str[i];
    }
    /* Insert from last. */
    if(position == LAST_POSITION) {
        auto node {new Node(strCopy)};
        this->length += length;
        auto string {this->head};
        while(string->getNext()) {
            string = string->getNext();
        }
        node->insertPrevious(string);
        string->insertNext(node);
        string = nullptr;
        return;
    }
    if(position == 1) {
        auto node {new Node(strCopy)};
        this->length += length;
        node->insertNext(this->head->getNext());
        node->insertPrevious(this->head);
        if(node->getNext()) {
            node->getNext()->insertPrevious(node);
        }
        this->head->insertNext(node);
        return;
    }
    auto start {1};     //Every node's start position in the string.
    auto count {0};     //Count how many characters have been traversed.
    auto node {this->head->getNext()};
    auto startFlag {false};      //flag == false means start from start position, or means start from mid position.
    /* Check where the position is starting. */
    if(node) {
        auto flag {false};
        while (node->getNext() and count < position) {
            flag = false;
            auto temp{node->getString()};
            for (auto i {0}; temp[i] != '\0'; i++) {
                count++;
                if (count == position) {
                    startFlag = true;
                    break;
                }
            }
            if(startFlag) {
                break;
            }
            start += node->getLength();
            node = node->getNext();
            flag = true;
        }
        if(flag) {
            node = node->getPrevious();
        }
        if(!node->getNext() and position <= this->length and count + 1 != start) {
            startFlag = true;
        }
        /* The situation is going to be devided to two :
         * Insert from start position
         * Insert from mid position
         */
        if (startFlag) {
            auto insertNode {new Node};     //Node that is going to be inserted. Node's string is cut from old string.
            auto loopLength {start + node->getLength() - position};     //The string of new node's length.
            auto temp {new char[loopLength]};       //The string of new node.
            memset(temp, 0, sizeof *temp * loopLength);
            auto nodeString {node->getString()};        //Old node string.
            /** Set new node's string. **/
            for (int i {position - start}, j {0}; i <= loopLength; i++, j++) {
                temp[j] = nodeString[i];
            }
            insertNode->insertString(temp);
            insertNode->insertLength(loopLength);
            auto newNode{new Node(strCopy)};       //The string that is input by users.
            newNode->insertPrevious(node);
            newNode->insertNext(insertNode);
            insertNode->insertNext(node->getNext());
            insertNode->insertPrevious(newNode);
            if(node->getNext()) {
                node->getNext()->insertPrevious(insertNode);
            }
            node->insertNext(newNode);
            auto oldNodeString {new char[position - start]};        //The node's new string that is going to be inserted.
            memset(oldNodeString, 0, sizeof *oldNodeString * (position - start));
            /** Cut the node's string. **/
            for(auto i {0}; i < position - start; i++) {
                oldNodeString[i] = nodeString[i];
            }
            node->insertString(oldNodeString);
            node->insertLength((unsigned)position - start);
            insertNode = nullptr;
            newNode = nullptr;
            delete nodeString;
            nodeString = nullptr;
        } else {
            auto newNode {new Node(strCopy)};
            newNode->insertNext(node->getNext());
            newNode->insertPrevious(node);
            if(node->getNext()) {
                node->getNext()->insertPrevious(newNode);
            }
            node->insertNext(newNode);
        }
    }
    node = nullptr;
    strCopy = nullptr;
    this->length += length;
}
void String::deleteString(const char *str) {
    if(!this->length) {
        cout << "The string is empty!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    auto location {locate(str, 0, true)};
    if(!location) {
        cout << "Cannot find the string you entered!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    auto start {location};      //Set start to prevent double-deleting (Example : str = "abc", this->str = "ababcc").
    auto strLength = String::countChar(str);
    while(location) {
        this->deleteString(location, strLength);
        start = location - 1;
        location = locate(str, start, true);
    }
}
void String::deleteString(unsigned start, unsigned length) {
    if(!this->length) {
        cout << "The string is empty!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    if(start > this->length) {
        cout << "Errant start!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    if(start + length - 1 > this->length) {
        cout << "Errant length!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    this->checkEmptyNode();
    auto nodeStart {1};
    auto node {this->head->getNext()};
    this->length -= length;
    /* Search the node that is going to be deleted or cut. */
    while(node and length > 0) {
        /** Node that is going to be deleted **/
        if(nodeStart >= start and nodeStart + node->getLength() <= start + length) {
            /*** Set the correct next and previous. ***/
            auto nodePrevious {node->getPrevious()};
            if(node->getNext()) {
                nodePrevious->insertNext(node->getNext());
                node->getNext()->insertPrevious(nodePrevious);
            }else {
                nodePrevious->insertNext(nullptr);
            }
            nodePrevious = nullptr;
            /*** Set tempNode to node and delete tempNode. ***/
            auto tempNode {node};
            auto nodeLength {node->getLength()};
            if(nodeStart == start) {
                start += nodeLength;
            }
            length -= nodeLength;
            node = node->getNext();
            delete tempNode;
            tempNode = nullptr;
            nodeStart += nodeLength;
            continue;
        }
        /** Deleting is not from start and deleting will not delete the node. **/
        if(nodeStart < start and nodeStart + node->getLength() <= start + length and nodeStart + node->getLength() > start) {
            auto insertStringLength {start - nodeStart};
            auto insertString {new char[insertStringLength]};
            memset(insertString, 0, sizeof *insertString * insertStringLength);
            auto oldString {node->getString()};
            for(auto i {0}; i < insertStringLength; i++) {
                insertString[i] = oldString[i];
            }
            delete oldString;
            oldString = nullptr;
            node->insertString(insertString);
            auto oldStringLength {node->getLength()};
            node->insertLength(insertStringLength);
            if(nodeStart + oldStringLength == start + length) {
                break;
            }
            length -= oldStringLength - insertStringLength;
        }
        /** Deleting is from start and deleting will not delete the node. **/
        if(start == nodeStart and nodeStart + node->getLength() > start + length) {
            auto insertStringLength {node->getLength() - start - length + nodeStart};
            auto insertString {new char[insertStringLength]};
            memset(insertString, 0, sizeof *insertString * insertStringLength);
            auto oldString {node->getString()};
            for(auto i {start + length - nodeStart}, j {static_cast<unsigned>(0)}; i < node->getLength(); i++, j++) {
                insertString[j] = oldString[i];
            }
            node->insertString(insertString);
            node->insertLength(insertStringLength);
            delete oldString;
            oldString = nullptr;
            break;
        }
        nodeStart += node->getLength();
        node = node->getNext();
    }
    node = nullptr;
}
unsigned String::locate(const char *str, unsigned start, bool systemCall) {
    if(!this->length and !systemCall) {
        cout << "The string is empty!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return 0;
    }
    if(!systemCall and start > this->length) {
        cout << "Errant start!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return 0;
    }
    auto temp {this->copyString()};
    auto strLength {String::countChar(str)};
    auto strLocation {0};
    auto tempLocation {start};
    while(strLocation < this->length and strLocation < strLength and start < this->length) {
        if(temp[tempLocation] == str[strLocation]) {
            strLocation++;
            tempLocation++;
        }else {
            start++;
            tempLocation = start;
            strLocation = 0;
        }
    }
    delete temp;
    temp = nullptr;
    if(strLocation == strLength) {
        return start + 1;
    }
    return 0;
}
vector<int> String::locateAll(const char *str) {
    vector<int> location;
    if(!this->length) {
        cout << "The string is empty!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return location;
    }
    auto strLocation {this->locate(str, 0, true)};
    if(!strLocation) {
        cout << "Cannot find the string you entered!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return location;
    }
    unsigned start {0};
    auto strLength {String::countChar(str)};
    while(strLocation) {
        location.push_back(strLocation);
        start = strLocation - 1;
        start += strLength;     //Indexing starts from the next.
        strLocation = this->locate(str, start, true);
    }
    return location;
}
char *String::substring(unsigned start, unsigned length) {
    if(!this->length or start + length > this->length or start > length) {
        return nullptr;
    }
    start--;        //Make the start match with the index of array.
    auto temp {this->copyString()};
    auto substr {new char[length]};
    memset(substr, 0, sizeof *substr * length);
    for(auto i {start}, j {(unsigned)0}; i < length; i++, j++) {
        substr[j] = temp[i];
    }
    delete temp;
    temp = nullptr;
    return substr;
}
void String::replaceAll(const char *replaced, const char *replace) {
    if(!this->length) {
        cout << "The string is empty!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    auto location {this->locate(replaced, 0, true)};
    if(!location) {
        cout << "Cannot find the string you entered!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    auto replacedLength {String::countChar(replaced)};
    auto replaceLength {String::countChar(replace)};
    auto start {location + replaceLength};
    while(location) {
        this->deleteString(location, replacedLength);
        this->insert(replace, location);
        location = this->locate(replaced, start, true);
        start = location + replaceLength - 1;       //Indexing starts from the next.
    }
}
void String::replace(const char *replaced, const char *replace) {
    if(!this->length) {
        cout << "The string is empty!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    auto location {this->locate(replaced, 0, true)};
    if(!location) {
        cout << "Cannot find the string you entered!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    auto replacedLength {String::countChar(replaced)};
    this->deleteString(location, replacedLength);
    this->insert(replace, location);
}
void String::clear() {
    auto node {this->head->getNext()};
    while(node) {
        auto tempNode {node};
        node = node->getNext();
        delete tempNode;
        tempNode = nullptr;
    }
    delete node;
    this->head->insertNext(nullptr);
    this->length = 0;
}
void String::show() {
    if(!this->length) {
        return;
    }
    this->checkEmptyNode();
    /* Print for testing. */
    auto node {this->head};
    while(node->getNext()) {
        node = node->getNext();
        cout << node->getString();
        if(node->getNext()) {
            cout << "->";
        }
    }
    cout << endl;
    node = nullptr;
    /* Print for users. */
    auto string {this->copyString()};
    cout << string << endl;
    delete []string;
    string = nullptr;
}

main.cpp :

#include "BlockingLinkedString.hpp"

using namespace BlockingLinkedString;

void menu();

int main(int argc, char *argv[]) {
    unsigned choice;
    string input, replace, replaced;
    unsigned start, length;
    int position;
    auto str {new String};
    vector<int> location;
    char *substring;
    do {
        system("clear");
        str->show();
        menu();
        cin >> choice;
        switch(choice) {
            case 1 :
                cout << "The length of string : " << str->getLength() << endl;
                cout << "Press any key to continue!" << endl;
                getchar();
                getchar();
                break;
            case 2 :
                cout << "Please enter string you want to insert "
                        "(If you want to input space in the first, please enter \"\\40\" first) : ";
                cin.ignore();
                getline(cin, input);
                String::checkInput(input);
                cout << "Please enter the position you want to insert : ";
                cin >> position;
                str->insert(input.c_str(), position);
                break;
            case 3 :
                cout << "Please enter the string you want to delete "
                        "(If you want to input space in the first, please enter \"\\40\" first) : ";
                cin.ignore();
                getline(cin, input);
                String::checkInput(input);
                str->deleteString(input.c_str());
                break;
            case 4 :
                cout << "Please enter the position you want to delete : ";
                cin >> start;
                cout << "Please enter the length : ";
                cin >> length;
                str->deleteString(start, length);
                break;
            case 5 :
                cout << "Please enter the string you want to locate"
                        "(If you want to input space in the first, please enter \"\\40\" first) : ";
                cin.ignore();
                getline(cin, input);
                String::checkInput(input);
                {
                    auto pos {str->locate(input.c_str())};
                    if (pos) {
                        cout << "Location : \t" << pos << endl;
                    } else {
                        cout << "Cannot find the string you entered!" << endl;
                    }
                }
                cout << "Press any key to continue!" << endl;
                getchar();
                break;
            case 6 :
                cout << "Please enter the string you want to locate"
                        "(If you want to input space in the first, please enter \"\\40\" first) : ";
                cin.ignore();
                getline(cin, input);
                String::checkInput(input);
                location = str->locateAll(input.c_str());
                if(location.empty()) {
                    break;
                }
                cout << "Location : \t";
                for(auto c : location) {
                    cout << c << "\t";
                }
                cout << endl;
                cout << "Press any key to continue!" << endl;
                getchar();
                break;
            case 7 :
                cout << "Please enter the start : ";
                cin >> start;
                cout << "Please enter the length : ";
                cin >> length;
                substring = str->substring(start, length);
                if(substring) {
                    cout << "Substring : " << substring << endl;
                    delete substring;
                    substring = nullptr;
                }else {
                    cout << "Errant input!" << endl;
                }
                cout << "Press any key to continue!" << endl;
                getchar();
                getchar();
                break;
            case 8 :
                cout << "Please enter the string that is going to be replaced "
                        "(If you want to input space in the first, please enter \"\\40\" first) : ";
                cin.ignore();
                getline(cin, replaced);
                String::checkInput(replaced);
                cout << "Please enter the string that is going to replace : "
                        "(If you want to input space in the first, please enter \"\\40\" first) : ";
                getline(cin, replace);
                String::checkInput(replace);
                if(replace == replaced) {
                    break;
                }
                str->replace(replaced.c_str(), replace.c_str());
                break;
            case 9 :
                cout << "Please enter the string that is going to be replaced "
                        "(If you want to input space in the first, please enter \"\\40\" first) : ";
                cin.ignore();
                getline(cin, replaced);
                String::checkInput(replaced);
                cout << "Please enter the string that is going to replace : "
                        "(If you want to input space in the first, please enter \"\\40\" first) : ";
                getline(cin, replace);
                String::checkInput(replace);
                if(replace == replaced) {
                    break;
                }
                str->replaceAll(replaced.c_str(), replace.c_str());
                break;
            case 10 :
                str->clear();
                break;
            case 11 :
                /* Clean vector. */
                {
                    vector<int> temp;
                    location.swap(temp);
                }
                delete str;
                delete substring;
                str = nullptr;
                substring = nullptr;
                exit(0);
            default :
                break;
        }
    }while(choice != 11);
}
void menu() {
    cout << "--------------------------------------------------" << endl;
    cout << "1. Get the string's length." << endl;
    cout << "2. Insert." << endl;
    cout << "3. Delete by string." << endl;
    cout << "4. Delete by position" << endl;
    cout << "5. Locate." << endl;
    cout << "6. Locate All." << endl;
    cout << "7. Substring." << endl;
    cout << "8. Replace." << endl;
    cout << "9. Replace All." << endl;
    cout << "10. Clear." << endl;
    cout << "11. Exit." << endl;
    cout << "--------------------------------------------------" << endl;
    cout << "Please enter your choice : ";
}