字串是一種特定的抽象數據結構, 組成字串的每一個元素都是字元, 其中包括了各種符號、數字以及字母 (全部都為數字的字串可以近似看作為順序表)

字串在所有的程式設計語言中都是一種重要的資料結構. 文本編輯中, 搜尋即為字串的子串定位; 很多驗證中, 需要進行字串的比對, 即字串的比較等等. 可以說, 字串的應用是非常多的

除去上述所提到的比較和定位之外, 字串還有拷貝、插入、刪除、串接、擷取和取代操作

其中插入與定位比其它的操作要困難一些, 我們主要講解這兩個操作

插入

在原來的字串中插入新的字串並不簡單, 因為其中涉及到插入後的總長度是否大於陣列可以容納的長度. 當插入後的總長度要大於陣列可容納的長度後, 又可以分為兩種情形

我們假設有一字串 string 和即將被執行插入操作的字串 chars, 並且假設 NAME.length 為字串的長度, length 為陣列最大長度, 插入位置為 position

string.length + chars.length <= length 時, 陣列的長度不但可以容納 string, 還可以容納 chars, 那麼此時就是簡單的串接

string.length + chars.length > length 時, 分為兩種情況

  • 字串 chars 插入後, 字串 string 必然要捨棄一部分字串, 但是 chars 可以完整插入. 也就是 position + chars.length <= length. 舉個例子 : 陣列長度為 10, string 為 "abcdef". 現在要在第三個位置插入 "abcde", 插入後 string 為 "ababcdecde". 可以看到, 橙色部分並沒有被完全捨棄
  • 字串 chars 插入後, 字串 string 不但要捨棄一部分, chars 的末尾也要捨棄一部分. 也就是 position + chars.length > length. 舉個例子 : 陣列長度為 10, string 為 "abcdefgh". 現在要在第六個位置插入 "ijklmno", 插入後 string 為 "abcdeijklm".可以發現, 兩個字串都捨棄了一部分的數據

定位

字串的搜尋目前使用的比較暴力的 Brute-Force 演算法, 還有其它演算法這裡暫時不作介紹, 後續會有獨立的介紹

假設現在有目標串 string, 定位串 pattern (pattern.length > string.length). 即在 string 中搜尋是否存在子串 pattern

一開始, 我們從 string 的第 1 個位置開始, 比較 string 的第一個位置的字元和 pattern 的第一個位置的字元. 如果相同, 那麼比較 string 的第 2 個字元和 pattern 的第二個字元. 以此類推, 當 pattern 走完的時候, 就說明從 string 的第一個位置開始, 到 string 的第 pattern.length 為止, 都和 pattern 相同, 即 string 中存在 pattern. 例如 string 為 "abcde", pattern 為 "abc". 但是, 當遇到不同的字符的時候, 那麼就從 string 的第二個位置開始重新比較. 即 string 的第二個字元開始重新和 pattern 的第一個字元開始比較. 如果中間有字元不一樣, 那麼從 string 的第三個字元開始與 pattern 的第一個字元開始比較... 以此類推, 當 string 走到某個位置, 剩下的字串長度小於 pattern, 那麼就說明 string 中不存在 pattern. 將這個演算法描述總結 :

從 string 的第 position 個位置開始 (position 從 0 開始), 和 pattern 的第一個字元比較, 如果一樣, 則繼續比較下一個字符; 如果不一樣, 那麼 string 從 position + 1 個位置開始, pattern 回溯到第一個字元繼續比較. 直到 string 中某個位置開始與 pattern 全部相等, 則 string 中存在 pattern; 否則,  string 中不存在 pattern. 若且唯若 string 中存在 pattern, 那麼 position 即為 pattern 在 string 中的位置

比較

假設現在有目標串 string, 比較串 pattern

從 string 的第一個字元開始與 pattern 的第一個字元開始比較, 如果相同, 則繼續比較; 如果不相同, 那麼返回 string 的比較字元 - pattern 的比較字元 (並非字元做減法, 而是字元對應的 ASCII 碼做減法). 如果其中一個串走完了, 那麼直接返回 string.length - pattern.length

若且唯若 string.length = pattern.length 並且 string[i] = pattern[i] (i = 0, 1, 2, ..., length - 1), 稱 string 與 pattern 相等 (字串相等)


下面是本人寫的原始碼

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

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

#ifndef STRING_STRING_HPP
#define STRING_STRING_HPP

#include <iostream>
#include <cstdlib>

namespace SequentialString {
    using std::cin;
    using std::cout;
    using std::endl;
    using std::string;      //used in user inputting
    class String {
    private :
        bool isEmpty();
        bool isFull();
        int locateCharacter(char ch);
    protected :
        char *str;
        int length;
        String();       //default constructor. It is protected in order to avoid anyone who is fucking stupid calling this constructor.
    public :
        String(int length);
        ~String();
        void assign(const char *chars);
        void insert(int position, const char *chars);
        void deleteByPosition(int position);
        void deleteByString(char ch);
        void deleteByString(const char *chars);
        void copy(const char *chars);
        int compare(const char *chars);
        int count();        //Get the length of String::str
        void clear();
        void concatenate(const char *chars);
        char *substring(int position, int length);
        void replace(const char *chars, int position);
        void replace(const char *replaced, const char *replace);
        int index(const char *chars);
        void show();
    };
}


#endif //STRING_STRING_HPP

String.cpp :

#include "String.hpp"

using namespace SequentialString;

String::String() {

}
String::String(int length) {
    this->length = length;
    this->str = new char;
}
String::~String() {
    delete []this->str;
}
bool String::isEmpty() {
    if(this->str[0] == '\0') {      //If first character is '\0\ meaning that the string is empty.
        return true;
    }
    return false;
}
bool String::isFull() {
    int count = this->count();
    if(count == this->length) {
        return true;
    }
    return false;
}
/* This function is to count the strings who isn't String::str */
int countChar(const char *chars) {
    int count = 0;
    for(int i = 0; chars[i] != '\0'; i++) {
        count++;
    }
    return count;
}
void String::assign(const char *chars) {
    this->clear();
    int chars_count = countChar(chars);
    if(chars_count > this->length) {        //If the length of chars is longer than String::str, then only copy String::str'length.
        for(int i = 0; i < this->length; i++) {
            this->str[i] = chars[i];
        }
    }else {
        for(int i = 0; chars[i] != '\0'; i++) {
            this->str[i] = chars[i];
        }
    }
}
void String::insert(int position, const char *chars) {
    if(position > this->length || position < 1) {
        cout << "Errant position!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    auto chars_count = countChar(chars);
    position--;
    auto str_count = this->count();
    /*
     * Insert Module.
     * The situation is devided to three
     */
    if(chars_count + str_count <= this->length) {       //The String::str will all insert.
        auto *concatenateString = new char;
        for(auto i = position, count = 0; i < str_count; i++, count++) {
            concatenateString[count] = this->str[i];
        }
        for(auto i = position, count = 0;  i < str_count + position && count < chars_count; i++, count++) {
            this->str[i] = chars[count];
        }
        this->concatenate(concatenateString);
    }else if(chars_count + str_count > this->length && position + chars_count <= this->length) {      //After inserting, the String::str needs to give up some characters from itself.
        for(auto i = this->length - 1; i >= position + chars_count; i--) {
            this->str[i] = this->str[i - chars_count];
        }
        for(auto i = position, count = 0; i < str_count + position && count < chars_count; i++, count++) {
            this->str[i] = chars[count];
        }
    }else {     //The String::str needs to give up all characters after position, and will only insert some characters of chars.
        for(auto i = position, count = 0; i < this->length && count < chars_count; i++, count++) {
            this->str[i] = chars[count];
        }
    }
    /* To avoid abnormal, count < chars_count is needed. */
}
void String::deleteByPosition(int position) {
    if(this->isEmpty()) {
        cout << "The string is empty!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    if(position > this->count() || position < 1) {
        cout << "Errant position!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    position--;     //Make position match with C++ array
    auto str_count = this->count();
    for(int i = position; str[i + 1] != '\0'; i++) {
        this->str[i] = this->str[i + 1];
    }
    this->str[str_count - 1] = 0;
}
int String::locateCharacter(char ch) {
    for(int i = 0; this->str[i] != '\0'; i++) {
        if(this->str[i] == ch) {
            return i + 1;
        }
    }
    return 0;
}
void String::deleteByString(char ch) {
    if(this->isEmpty()) {
        cout << "The string is empty!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    auto position = this->locateCharacter(ch);
    if(!position) {
        cout << "Cannot find the character you entered!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    /* Delete Module */
    while(position) {
        this->deleteByPosition(position);
        position = this->locateCharacter(ch);
    }
}
void String::deleteByString(const char *chars) {
    if(isEmpty()) {
        cout << "The string is empty!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    auto position = index(chars);
    if(position == -1) {
        cout << "Cannot find the string you entered!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    int chars_count = countChar(chars);
    /* Delete Module */
    for(int i = 1; i <= chars_count; i++) {
        deleteByPosition(position + 1);
    }
}
void String::copy(const char *chars) {
    //The feature of copy() is same to function assign()
}
int String::compare(const char *chars) {
    auto count = this->count();
    auto charsCount = countChar(chars);
    for(int i = 0; i < count and i < charsCount; i++) {
        if(this->str[i] != chars[i]) {
            return this->str[i] - chars[i];
        }
    }
    return count - charsCount;       //Returning '0' means no difference
}
int String::count() {
    int count = 0;
    for(int i = 0; this->str[i] != '\0'; i++) {
        count++;
    }
    return count;
}
void String::clear() {
    while(this->str[0] != '\0') {
        deleteByPosition(1);
    }
}
void String::concatenate(const char *chars) {
    if(isFull()) {
        cout << "The string is full!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    auto left = this->length - this->count();
    /* Concatenate Module */
    for(int i = 1; i <= left; i++) {
        this->str[this->count()] = chars[i - 1];
    }
}
char *String::substring(int position, int length) {
    if(position > this->count() || position < 1) {
        return nullptr;
    }
    auto *returnChars = new char[length];
    position--;     //Make position match with C++ array
    int returnCount = 0;
    /* Substring Module */
    for(int i = position; i <= length + position && this->str[i] != '\0'; i++) {
        returnChars[returnCount] = this->str[i];
        returnCount++;
    }
    return returnChars;
}
void String::replace(const char *chars, int position) {
    if(position > this->count() || position < 1) {
        cout << "Errant position!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
        return;
    }
    position--;     //Make position match with C++ array
    auto chars_count = countChar(chars);
    int charsCount = 0;
    /* Replace Module */
    for(int i = position; i < chars_count + position; i++) {
        this->str[i] = chars[charsCount];
        if(this->str[i + 1] == '\0') {      //Break the loop when str[i + 1] == '\0'
            break;
        }
        charsCount++;
    }
}
void String::replace(const char *replaced, const char *replace) {
    if(countChar(replace) > this->count()) {
        cout << "The replacing string is too long!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
    }
    auto position = this->index(replaced);
    if(position == -1) {
        cout << "Cannot find the string that you want to replace!" << endl;
        cout << "Press any key to continue!" << endl;
        getchar();
        getchar();
    }
    auto count = countChar(replaced);       //length of string replaced
    auto positionBackup = position + 1;     //backup the start number of position
    /*
     * Replace Module
     * If find the position, after deleting then insert.
     */
    while(position != -1) {
        for(int i = 1; i <= count; i++) {
            this->deleteByPosition(position + 1);
        }
        this->insert(positionBackup, replace);
        position = this->index(replaced);
    }
}
int String::index(const char *chars) {
    auto count = this->count();
    auto chars_count = countChar(chars);
    if(chars_count > count) {
        return -1;
    }
    int index = -1;
    int loopCount = 0;
    /* Brute-Force algorithm */
    while(index == -1 && loopCount != count) {
        bool flag = true;       //When flag == true meaning it has indexed the chars in String::str. In the first, it will be initialize by true.
        for(int i = 0; chars[i] != '\0'; i++) {
            if(chars[i] != this->str[loopCount + i]) {
                flag = false;
                break;
            }
        }
        if(flag) {
            index = loopCount;
        }
        loopCount++;
        if(this->length - loopCount < chars_count) {        //When left string's length is shorter than chars'
            break;
        }
    }
    return index;
}
void String::show() {
    if(isEmpty()) {
        return;
    }
    auto length = count();
    cout << "Index : \t";
    for(int i = 1; i <= length; i++) {
        cout << i << "\t";
    }
    cout << endl << "Character : \t";
    for(int i = 0; this->str[i] != '\0'; i++) {
        cout << this->str[i] << "\t";
    }
    cout << endl << "String : " << this->str << endl;
}

main.cpp :

#include "String.hpp"

using namespace SequentialString;

void menu();

int main(int argc, char *argv[]) {
    int choice;     //The choice of user inputting.
    String *str;
    cout << "Please enter the max length of string : ";
    cin >> choice;
    str = new String(choice);
    string input, replace;       //The string is going to be a param when calling a function that needs it.
    char *substring;        //String::substring()'s return.
    char ch;        //It is going to be a param when calling a function that needs a character.
    int length;     //The length of String::str.
    int compare;        //The result of String::compare().
    int index;      //The result of String::index().
    int position;       //It is going to be a param when calling a function that needs position.
    do {
        system("clear");
        str->show();
        menu();
        cin >> choice;
        switch(choice) {
            case 1 :
                cout << "Please enter a string : ";
                cin >> input;
                str->assign(input.c_str());
                break;
            case 2 :
                cout << "Please enter a string you want to insert : ";
                cin >> input;
                cout << "Please enter the position : ";
                cin >> position;
                str->insert(position, input.c_str());
                break;
            case 3 :
                cout << "Please enter the position : ";
                cin >> position;
                str->deleteByPosition(position);
                break;
            case 4 :
                cout << "Please enter a character : ";
                cin >> ch;
                fflush(stdin);
                str->deleteByString(ch);
                break;
            case 5 :
                cout << "Please enter a string : ";
                cin >> input;
                str->deleteByString(input.c_str());
                break;
            case 6 :
                cout << "Please enter a string : ";
                cin >> input;
                compare = str->compare(input.c_str());
                cout << "Compare result : ";
                if(!compare) {
                    cout << "Same" << endl;
                }else {
                    cout << compare << endl;
                }
                cout << "Press any key to continue!" << endl;
                getchar();
                getchar();
                break;
            case 7 :
                length = str->count();
                cout << "The string's length : " << length << endl;
                cout << "Press any key to continue!" << endl;
                getchar();
                getchar();
                break;
            case 8 :
                cout << "Please enter a string : ";
                cin >> input;
                str->concatenate(input.c_str());
                break;
            case 9 :
                if(true) {      //Variables cannot be declared in switch case.
                    cout << "Please enter the position : ";
                    cin >> position;
                    cout << "Please enter the length you want to cut : ";
                    cin >> length;
                    substring = str->substring(position, length);
                    cout << "The substring : " << substring << endl;
                    cout << "Press any key to continue!" << endl;
                    char *deleteSubstring;
                    deleteSubstring = substring;
                    substring = nullptr;
                    delete deleteSubstring;
                }
                getchar();
                getchar();
                break;
            case 10 :
                cout << "Please enter a string you want to index : ";
                cin >> input;
                position = str->index(input.c_str());
                if(position == -1) {
                    cout << "The position : " << position + 1 << endl;
                }else {
                    cout << "Cannot find the string you entered!" << endl;
                }
                cout << "Press any key to continue!" << endl;
                getchar();
                getchar();
                break;
            case 11 :
                cout << "Please enter a string :";
                cin >> input;
                cout << "Please enter the position that is going to be replaced : ";
                cin >> position;
                str->replace(input.c_str(), position);
                break;
            case 12 :
                cout << "Please enter a string that is going to be replaced : ";
                cin >> input;
                cout << "Please enter a string that is going to replace : ";
                cin >> replace;
                if(input == replace) {
                    cout << "The string is going to be replaced is same to the string is going to replace!" << endl;
                    cout << "Press any key to continue!" << endl;
                    getchar();
                    getchar();
                    break;
                }
                str->replace(input.c_str(), replace.c_str());
                break;
            case 13 :
                str->clear();
                break;
            case 14 :
                delete str;
                exit(0);
            default :
                break;
        }
    }while(choice != 14);
}
void menu() {
    cout << "-----------------------------------------" << endl;
    cout << "1. Assign (Copy)." << endl;
    cout << "2. Insert." << endl;
    cout << "3. Delete by position." << endl;
    cout << "4. Delete by a character." << endl;
    cout << "5. Delete by a string." << endl;
    cout << "6. Compare." << endl;
    cout << "7. Get length." << endl;
    cout << "8. Concatenate a string." << endl;
    cout << "9. Get a substring." << endl;
    cout << "10. Index a string." << endl;
    cout << "11. Replace by position." << endl;
    cout << "12. Replace by string." << endl;
    cout << "13. Clear." << endl;
    cout << "14. Exit." << endl;
    cout << "-----------------------------------------" << endl;
    cout << "Please enter your choice : ";
}