當這篇文章發布之後, 《資料結構》這一專欄的文章將會暫時停止更新一段時間. 因為在字串後面就是陣列了. 陣列的實作不可能僅靠 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_HPPBlockingLinkedString.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 : ";
}自創文章, 原著 : Jonny, 如若需要轉發, 在已經授權的情況下請註明出處 :《資料結構 : 區塊連結字串》https://jonny.vip/2018/03/15/%e8%b3%87%e6%96%99%e7%b5%90%e6%a7%8b-%e5%8d%80%e5%a1%8a%e9%80%a3%e7%b5%90%e5%ad%97%e4%b8%b2/
AliPay QR Code
WeChat QR Code
Leave a Reply