堆積字串這個名字是我自己起的, 在 Google 上幾乎搜尋不到任何關於 Heap String 的信息. 但是書中有關於此的介紹.

顧名思義, 堆積字串就是字串以堆積 (Heap) 的方式進行存儲, 它的結構與靜態連結串列優點類似. 但是它擁有兩個表, 一個是記錄映射關係, 另外一個是用於存儲字串. 簡單的說就是從記錄表中拿出一個, 就能知道這個映射關係在字串中代表的子串

我們在開始的時候, 申請一個比較大的空間, 用於存儲字串. 同時申請一個陣列, 用於存儲映射關係. 不斷地對於映射關係表和字串陣列進行添加新的元素或者刪除元素, 這就是堆積字串的基本操作

形式上, 堆積字串與普通的定長字串有一定的區別, 不過在字串的抽象數據結構上, 其實是類似的

下面用一張 SVG 圖像表示堆積字串, 可能會加深理解

從圖像中可以看出, 這個存儲與讀取的方式有點類似於雜湊表

對於堆積字串的操作, 最麻煩的就是插入與刪除. 這可比普通的定長字串要麻煩多了

插入

插入分成兩種情況, 一種是從末位直接插入, 一種是從中間插入

在末位直接插入是比較簡單的, 在映射表中添加新的信息, 並且在字串最後連接要插入的新字串即可

在中間插入則比較麻煩, 這其中要考慮到插入是否為打破原來的映射. 拿 SVG 圖像中的例子直接說明, 例如是從 B 後面插入新的字串還是從 B 中間插入新的字串. 從 B 後面插入會比從中間插入簡單, 直接在映射表中添加新的信息, 並且重新對字串陣列進行連結即可. 從 B 中間插入則要麻煩的多, 首先要在映射表中插入新的字串的信息, 然後把打斷後的字串重新加入映射表中, 然後再對字串陣列進行重新連結

刪除

插入如果麻煩, 那麼刪除也是肯定麻煩. 刪除主要考慮一下兩點 :

  • 字串的刪除是否會導致直接從映射表中移除要刪除的字串. 拿 SVG 圖像中的例子說明, 即如果要刪除 "Please", 那麼映射表中的 A 就會從映射表中移除
  • 字串的刪除不會導致直接從映射表中移除, 這又分為兩種情況
    • 刪除是從 start 位置開始的
    • 刪除是從中間位置開始的

如果可以清楚分析上面幾點, 那麼寫堆積字串就不再麻煩


下面是本人寫的原始碼

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

HeapString.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 HeapString.cpp
 */

#ifndef HEAPSTRING_HEAPSTRING_HPP
#define HEAPSTRING_HEAPSTRING_HPP

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

namespace HeapString {
    using std::cin;
    using std::cout;
    using std::endl;
    using std::string;
    using std::vector;
    using std::uniform_int_distribution;
    using std::default_random_engine;
    class Map {
    protected :
        string name;
        int length;
        int start;
        Map();
    public :
        Map(string name, int length, int start);
        ~Map();
        void insertName(string name);
        void insertLength(int length);
        void insertStart(int start);
        string getName();
        int getLength();
        int getStart();
    };
    class String {
    private :
        char *copyString(int length);
    protected :
        vector<Map> strVector;
        char *str;
        int length;
    public :
        String();
        ~String();
        static int countChars(const char *str);
        int getLength();
        void insert(Map *strMap, const char *str);
        int locate(const char *str, int position = 0, bool systemCall = false);
        vector<int> locateAll(const char *str);
        void replace(const char *replaced, const char *replace);
        void replaceAll(const char *replaced, const char *replace);
        void clear();
        char *substring(int position, int length);
        void deleteString(const char *str);
        void deleteString(int start, int length);
        void show();
        void cleanVector();
        static void checkInputFirst(string &input);
    };
}


#endif //HEAPSTRING_HEAPSTRING_HPP

HeapString.cpp :

#include "HeapString.hpp"

#define LAST_POSITION (-1)

using namespace HeapString;

Map::Map() {

}
Map::Map(string name, int length, int start) {
    this->name = name;
    this->length = length;
    this->start = start;
}
Map::~Map() {

}
void Map::insertLength(int length) {
    this->length = length;
}
void Map::insertName(string name) {
    this->name = name;
}
void Map::insertStart(int start) {
    this->start = start;
}
int Map::getLength() {
    return this->length;
}
int Map::getStart() {
    return this->start;
}
string Map::getName() {
    return this->name;
}
String::String() {
    this->str = nullptr;
    this->length = 0;
}
String::~String() {
    delete []this->str;
}
int String::getLength() {
    return this->length;
}
int String::countChars(const char *str) {
    int count = 0;
    for(auto i = 0; str[i] != '\0'; i++) {
        count++;
    };
    return count;
}
char *String::copyString(int length) {
    auto *temp = new char[this->length + length];
    if(this->str) {
        for(auto i = 0; this->str[i] != '\0'; i++) {
            temp[i] = this->str[i];
        }
    }
    return temp;
}
void String::checkInputFirst(string &input) {
    if(input[0] == '\\' and input[1] == '4' and input[2] == '0') {
        auto length = input.size() - 2;
        for(auto i = 1; i < length; i++) {
            input[i] = input[i + 2];
        }
        input[0] = '\40';
        input[length] = input[length + 1] = 0;
    }
}
void String::insert(Map *strMap, const char *str) {
    auto start = strMap->getStart();
    if(start == 0 or start < -1 or start > this->length + 1) {
        cout << "Errant position!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    auto strLength = this->countChars(str);
    /* Insert from the last. */
    if(start == LAST_POSITION) {
        auto *temp = copyString(strLength);     //New string for String::str
        strMap->insertStart(this->length);      //Rechange the start position.
        /** Copy the str to String::str **/
        for(auto i = 0; i < strLength; i++) {
            temp[this->length] = str[i];
            this->length++;
        }
        strVector.push_back(*strMap);
        delete []this->str;
        this->str = temp;
        return;
    }
    /* Insert between the text */
    auto *temp = new char[this->length + strLength];      //New string for String::str
    start = strMap->getStart() - 1;
    strMap->insertStart(start);        //Rechange the start position, corresponding to the position of array.
    /** Copy character before start. **/
    for(auto i = 0; i < start; i++) {
        temp[i] = this->str[i];
    }
    /** Copy new string (const char *str) to the temp string. **/
    for(auto i = start, count = 0; count < strLength; i++, count++) {
        temp[i] = str[count];
    }
    /** Copy the left of String::str **/
    for(auto i = start + strLength, j = start; j < this->length; i++, j++) {
        temp[i] = this->str[j];
    }
    delete []this->str;
    this->str = temp;
    this->length += strLength;
    /** Inserting will not split the words. **/
    for(auto iterator = this->strVector.begin(); iterator < this->strVector.end(); iterator++) {
        /** Find the start from vector and change the old to a new start position. **/
        if(start == iterator->getStart()) {
            /*** Change the start number of String::strVector which the position is after start. ***/
            for(auto i = this->strVector.begin(); i < this->strVector.end(); i++) {
                auto s = i->getStart();
                if(s >= start) {
                    i->insertStart(s + strLength);
                }
            }
            strVector.push_back(*strMap);
            return;
        }
    }
    /** Inserting will split the words. **/
    string randomName = "abcde";        //Initialize it to avoid failing to create random numbers.
    uniform_int_distribution<unsigned> u(0, 127);
    default_random_engine e((unsigned)time(nullptr));       //Unsigned randomly number.
    /** Create string name randomly **/
    for(auto i = 0; i < 5; i++) {
        randomName[i] = (char)u(e);
    }
    /** Change the old string's start **/
    int length {-1};        //The length of words that is splitted
    int lengthLeft {-1};        //The length of words that is after being splitted.
    for(auto iterator = this->strVector.begin(); iterator < this->strVector.end(); iterator++) {
        length = iterator->getLength();
        if(iterator->getStart() < start and start < length + iterator->getStart()) {
            iterator->insertLength(start - iterator->getStart());
            lengthLeft = iterator->getStart() + length - start;
            break;
        }
    }
    strVector.push_back(*strMap);
    /*** Change the start number of String::strVector which the position is after start. ***/
    for(auto i = this->strVector.begin(); i < this->strVector.end(); i++) {
        if(i->getStart() > start) {
            i->insertStart(i->getStart() + strLength);
        }
    }
    auto *newVector = new Map(randomName, lengthLeft, start + strLength);       //The words that is splitted after start.
    this->strVector.push_back(*newVector);
}
int String::locate(const char *str, int position, bool systemCall) {
    /* If the function is called by users, the position will equal to 0 and systemCall will equal to false.
     * The position is used in where the locate starts.
     * The systemCall is used in whether the tips for users will print in the screen.
     */
    if(!systemCall and this->length == 0) {
        cout << "The heap string is empty!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return 0;
    }
    auto start {position};      //Location starts from the position.
    auto x {0}, y {0};      //x for the loop count of String::str, y for the loop count of str.
    auto strCount = this->countChars(str);      //The length of str.
    /* Brute-Force Algorithm */
    while(x < this->length and y < strCount) {
        if(this->str[x] == str[y]) {
            /** If the character is same, then x and y add 1. **/
            x++;
            y++;
        }else {
            /** If the character is different, the x backtrack to start + 1, the y backtrack to 0 **/
            start++;
            x = start;
            y = 0;
        }
    }
    /** If y <= strCount means the start is the position start of str. **/
    if(y >= strCount) {
        return start + 1;       //Return the right position of human cognition.
    }
    return 0;
}
vector<int> String::locateAll(const char *str) {
    vector<int> location;       //A vector to save the position of location.
    if(this->length == 0) {
        cout << "The heap string is empty!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return location;
    }
    auto start {0};     //The start position when starting to find position every time.
    auto strCount = this->countChars(str);      //The length of str.
    while(start < this->length) {
        auto stringLocation {locate(str, start, true)};     //Save the return data when call function String::locate()
        if(stringLocation) {
            /* If find the position : */
            location.push_back(stringLocation);
        }else {
            /* If cannot find the position : */
            break;
        }
        stringLocation--;       //Matching with the position of C++ array.
        start = stringLocation + strCount;      //Change the next location start.
    }
    return location;
}
void String::replace(const char *replaced, const char *replace) {
    auto locate {this->locate(replaced, 0, true)};
    if(!locate) {
        cout << "Cannot find the string you entered!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    auto replacedLength {this->countChars(replaced)};
    auto replaceLength {this->countChars(replace)};
    this->deleteString(locate - 1, replacedLength);
    string name {"abcde"};
    uniform_int_distribution<unsigned> u(0, 127);
    default_random_engine e((unsigned)time(nullptr));
    for(auto i = 0; i < 5; i++) {
        name[i] = (char)u(e);
    }
    auto *map = new Map(name, replaceLength, locate);
    this->insert(map, replace);
}
void String::replaceAll(const char *replaced, const char *replace) {
    auto locate {this->locate(replaced, 0, true)};
    if(!locate) {
        cout << "Cannot find the string you entered!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    auto start {0};
    while(locate) {
        auto replacedLength {this->countChars(replaced)};
        auto replaceLength {this->countChars(replace)};
        this->deleteString(locate, replacedLength);
        string name {"abcde"};
        uniform_int_distribution<unsigned> u(0, 127);
        default_random_engine e((unsigned)time(nullptr));
        for(auto i = 0; i < 5; i++) {
            name[i] = (char)u(e);
        }
        auto *map = new Map(name, replaceLength, locate);
        this->insert(map, replace);
        start = locate + replacedLength;
        locate = this->locate(replaced, start, true);
    }
}
void String::clear() {
    this->cleanVector();
    delete []this->str;
    this->length = 0;
    this->str = nullptr;
}
char *String::substring(int position, int length) {
    if(this->length == 0) {
        cout << "The string is empty!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return nullptr;
    }
    auto *substr = new char[length];
    position--;
    for(auto i = position, j = 0; i < length + position; i++, j++) {
        substr[j] = this->str[i];
    }
    return substr;
}
void String::deleteString(int start, int length) {
    if(start > this->length or start < 1) {
        cout << "Errant start position!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    if(length < 1 or length > this->length or start + length > this->length) {
        cout << "Errant length!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    start--;        //Make the start match with array index.
    /* Delete the characters from start before length. */
    auto *temp = new char[this->length - length];
    for(auto i = 0; i < start; i++) {
        temp[i] = this->str[i];
    }
    for(auto i = start + length, j = start; i < this->length; i++, j++) {
        temp[j] = this->str[i];
    }
    delete []this->str;
    this->str = temp;
    this->length -= length;
    auto count {0};     //To count the element index in String::strVector
    auto reduce {length};
    /* Delete the map which is all deleted. */
    for(auto i = this->strVector.begin(); i < this->strVector.end() and length > 0; i++) {
        /** The word that is all deleted. **/
        if((i->getStart() + i->getLength() > start and i->getStart() + i->getLength() < start + length) or (start == i->getStart() and length == i->getLength())) {
            length -= i->getLength();
            this->strVector.erase(this->strVector.begin() + count);
            i--;
            /*** If deleting from the word's start : ***/
            if(start == i->getStart()) {
                start += i->getLength();
            }
            continue;
        }
        /** Deleting the word that is deleted from head and deleting will split the word : **/
        if(i->getStart() >= start and i->getStart() < start + length and i->getStart() + i->getLength() > length + start) {
            auto insertNumber = i->getLength() - length + start - i->getStart();
            length -= length + start - i->getStart();
            i->insertLength(insertNumber);
            /*** If met start == i.start, means that deleting is done. **/
            if(start == i->getStart()) {
                break;
            }
        }
        /** Deleting the word that is deleted from middle and deleting will split the word : **/
        if(i->getStart() < start and length + start > i->getStart() and length + start <= i->getStart() + i->getLength()) {
            if(length + start == i->getStart() + i->getLength()) {
                length -= i->getStart() + i->getLength() - start;
                auto insertNumber {start - i->getStart()};
                i->insertLength(insertNumber);
                continue;
            }
            auto insertNumber {i->getLength() - length};
            i->insertLength(insertNumber);
            break;
        }
        count++;
    }
    /** Change the start position which start bigger than delete start position. **/
    for(auto &c : this->strVector) {
        if(c.getStart() > start) {
            auto insertNumber {c.getStart() - reduce};
            c.insertStart(insertNumber);
        }
    }
}
void String::deleteString(const char *str) {
    auto locate {this->locate(str, 0, true)};
    if(!locate) {
        cout << "Cannot find the string you entered!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        return;
    }
    auto start {0};
    auto strLength {this->countChars(str)};
    while(locate) {
        this->deleteString(locate, strLength);
        locate = this->locate(str, start, true);
    }
}
void String::cleanVector() {
    vector<Map> temp;
    this->strVector.swap(temp);
}
void String::show() {
    if(this->length == 0) {
        return;
    }
    //cout << this->str << endl;
    int start {0};
    /* Print one by one from String::strVector */
    cout << "String : " << endl;
    while(start < this->length) {
        /** Find next start. **/
        for(auto c : this->strVector) {
            if(c.getStart() == start) {
                int length {c.getLength()};     //Words' length.
                for(auto i = start; i < start + length; i++) {
                    cout << this->str[i];
                }
                start += length;
                break;
            }
        }
    }
    cout << endl;
}

main.cpp :

#include "HeapString.hpp"

using namespace HeapString;

void menu();

int main(int argc, char *argv[]) {
    auto *str = new String();
    string name;
    int start;
    string input, replace, replaced;
    int length;
    int choice;
    vector<int> location;
    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);
                cout << "Please enter the name of string you want to insert : ";
                cin >> name;
                String::checkInputFirst(input);
                cout << "Please enter the position you want to insert "
                        "(If you want to insert from the tail, please enter \"-1\") : ";
                cin >> start;
                if(true) {      //Variable cannot be declared in switch case.
                    auto map = new Map(name, String::countChars(input.c_str()), start);
                    str->insert(map, input.c_str());
                }
                break;
            case 3 :
                cout << "Please enter the string you want to locate : ";
                getchar();
                getline(cin, input);
                String::checkInputFirst(input);
                cout << "Location : \t" << str->locate(input.c_str()) << endl;
                cout << "Press any key to continue!" << endl;
                getchar();
                break;
            case 4 :
                cout << "Please enter the string you want to locate"
                        "(If you want to input space in the first, please enter \"\\40\" first) : ";
                getchar();
                getline(cin, input);
                String::checkInputFirst(input);
                location = str->locateAll(input.c_str());
                cout << "Location : \t";
                for(auto c : location) {
                    cout << c << "\t";
                }
                cout << endl << "Press any key to continue!" << endl;
                getchar();
                break;
            case 5 :
                cout << "Please enter the string that is going to be replaced "
                        "(If you want to input space in the first, please enter \"\\40\" first) : ";
                getline(cin, replaced);
                String::checkInputFirst(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::checkInputFirst(replace);
                str->replace(replaced.c_str(), replace.c_str());
                break;
            case 6 :
                cout << "Please enter the string that is going to be replaced "
                        "(If you want to input space in the first, please enter \"\\40\" first) : ";
                getline(cin, replaced);
                String::checkInputFirst(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::checkInputFirst(replace);
                str->replaceAll(replaced.c_str(), replace.c_str());
                break;
            case 7 :
                cout << "Please enter the start position : ";
                cin >> start;
                cout << "Please enter the length you want to cut : ";
                cin >> length;
                cout << "String : " << str->substring(start, length) << endl;
                cout << "Press any key to continue!" << endl;
                getchar();
                getchar();
                break;
            case 8 :
                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::checkInputFirst(input);
                str->deleteString(input.c_str());
                break;
            case 9 :
                cout << "Please enter the position you want to delete : ";
                cin >> start;
                cout << "Please enter the length you want to delete : ";
                cin >> length;
                str->deleteString(start, length);
                break;
            case 10 :
                str->clear();
                break;
            case 11 :
                str->cleanVector();
                exit(0);
            default :
                break;
        }
    }while(choice != 11);
}
void menu() {
    cout << "---------------------------------------------" << endl;
    cout << "1. Get the length of string." << endl;
    cout << "2. Insert." << endl;
    cout << "3. Locate." << endl;
    cout << "4. Locate all." << endl;
    cout << "5. Replace." << endl;
    cout << "6. Replace all." << endl;
    cout << "7. Substring." << endl;
    cout << "8. Delete by string." << endl;
    cout << "9. Delete by position." << endl;
    cout << "10. Clear." << endl;
    cout << "11. Exit." << endl;
    cout << "---------------------------------------------" << endl;
    cout << "Please enter your choice : ";
}