字串是一種特定的抽象數據結構, 組成字串的每一個元素都是字元, 其中包括了各種符號、數字以及字母 (全部都為數字的字串可以近似看作為順序表)
字串在所有的程式設計語言中都是一種重要的資料結構. 文本編輯中, 搜尋即為字串的子串定位; 很多驗證中, 需要進行字串的比對, 即字串的比較等等. 可以說, 字串的應用是非常多的
除去上述所提到的比較和定位之外, 字串還有拷貝、插入、刪除、串接、擷取和取代操作
其中插入與定位比其它的操作要困難一些, 我們主要講解這兩個操作
插入
在原來的字串中插入新的字串並不簡單, 因為其中涉及到插入後的總長度是否大於陣列可以容納的長度. 當插入後的總長度要大於陣列可容納的長度後, 又可以分為兩種情形
我們假設有一字串 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_HPPString.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 : ";
}自創文章, 原著 : Jonny, 如若需要轉發, 在已經授權的情況下請註明出處 :《資料結構 : 定長字串》https://jonny.vip/2018/03/08/%e8%b3%87%e6%96%99%e7%b5%90%e6%a7%8b-%e5%ae%9a%e9%95%b7%e5%ad%97%e4%b8%b2/
AliPay QR Code
WeChat QR Code
Leave a Reply