4.3 字符串

??字符串(String)是由零個(gè)或多個(gè)字符(char)順序排列組成的有限序列，簡(jiǎn)稱為串。例如 “good morning”就是由12個(gè)字符構(gòu)成的一個(gè)字符串。一般把字符串記作：

$$S{=}^{\prime \prime }{a}_0{a}_1\dots a_{n?1}^{\prime \prime }$$

??其中S是串名，引號(hào)中的字符序列是串值。字符個(gè)數(shù)是串的長(zhǎng)度，長(zhǎng)度為0的串被稱為空串，因?yàn)樗话魏巫址Ｐ枰⒁獾氖?#xff0c;空格字符（" "）并不是空串，因?yàn)樗粋€(gè)字符——空格。
??若把某個(gè)串稱為主串，則主串中任意個(gè)連續(xù)的字符組成的子序列被稱為子串。子串在主串中第一次出現(xiàn)時(shí)，其首字符在主串中的序號(hào)被稱為該子串在主串中的位置。
??關(guān)于字符串的基礎(chǔ)知識(shí)亦可參考前文：
【重拾C語(yǔ)言】六、批量數(shù)據(jù)組織（三）數(shù)組初值；字符串、字符數(shù)組、字符串?dāng)?shù)組；類型定義 typedef
【重拾C語(yǔ)言】七、指針（三）指針與字符串（字符串與字符串?dāng)?shù)組；指針與字符串的遍歷、拷貝、比較；反轉(zhuǎn)字符串）

4.3.1 字符串的定義與存儲(chǔ)

??字符串在許多非數(shù)值計(jì)算問(wèn)題中扮演著重要的角色，并在模式匹配、程序編譯和數(shù)據(jù)處理等領(lǐng)域得到廣泛應(yīng)用。在高級(jí)程序設(shè)計(jì)語(yǔ)言中，字符串通常被定義為以特殊字符’\0’（稱為空字符或字符串結(jié)束符）結(jié)尾的字符序列。這個(gè)約定使得在處理字符串時(shí)可以方便地確定字符串的結(jié)束位置。關(guān)于字符串的存儲(chǔ)方式，主要有兩種常見(jiàn)的方式：

• 順序存儲(chǔ)：字符串的字符按照順序依次存儲(chǔ)在連續(xù)的內(nèi)存空間中。這種方式使得字符串的訪問(wèn)和操作效率較高，可以通過(guò)索引直接訪問(wèn)任意位置的字符。在順序存儲(chǔ)方式中，字符串的長(zhǎng)度可以通過(guò)計(jì)算字符個(gè)數(shù)或者遇到’\0’結(jié)束符來(lái)確定。

• 鏈?zhǔn)酱鎯?chǔ)：字符串的字符通過(guò)鏈表的方式進(jìn)行存儲(chǔ)。每個(gè)節(jié)點(diǎn)包含一個(gè)字符和指向下一個(gè)節(jié)點(diǎn)的指針。鏈?zhǔn)酱鎯?chǔ)方式可以動(dòng)態(tài)地分配內(nèi)存，適用于長(zhǎng)度可變的字符串。但是相比于順序存儲(chǔ)，鏈?zhǔn)酱鎯?chǔ)方式需要更多的內(nèi)存空間，并且訪問(wèn)字符需要遍歷鏈表。

??選擇何種存儲(chǔ)方式取決于具體的應(yīng)用場(chǎng)景和需求。順序存儲(chǔ)適合于需要頻繁訪問(wèn)和操作字符串的情況，而鏈?zhǔn)酱鎯?chǔ)適合于長(zhǎng)度可變的字符串或者對(duì)內(nèi)存空間要求較高的情況。具體C語(yǔ)言實(shí)現(xiàn)可參照前文：
??【數(shù)據(jù)結(jié)構(gòu)】數(shù)組和字符串（十一）：字符串的定義與存儲(chǔ)（順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)及其C語(yǔ)言實(shí)現(xiàn)）

4.3.2 字符串的基本操作（鏈?zhǔn)酱鎯?chǔ)）

• 串長(zhǎng)統(tǒng)計(jì)返回串s的長(zhǎng)度；
• 串定位返回字符或子串在母串s中首次出現(xiàn)的位置的指針；
• 串復(fù)制將一個(gè)串s2復(fù)制到另一個(gè)串s1中；
• 串插入在指定位置后面插入字符串；
• 串刪除是刪除一個(gè)子串；
• 串拼接將串s2拼接到串s1的尾部；
• ……

??【數(shù)據(jù)結(jié)構(gòu)】線性表（二）單鏈表及其基本操作（創(chuàng)建、插入、刪除、修改、遍歷打印）

1. 結(jié)構(gòu)體

typedef struct Node {char data;struct Node* next;
} Node;typedef struct {Node* head;Node* tail;
} LinkedList;

• Node：表示鏈表的節(jié)點(diǎn)，包含一個(gè)字符數(shù)據(jù)和一個(gè)指向下一個(gè)節(jié)點(diǎn)的指針。
• LinkedList：表示鏈表，包含鏈表的頭節(jié)點(diǎn)和尾節(jié)點(diǎn)。

2. 初始化

??initLinkedList函數(shù)：用于初始化鏈表，將頭節(jié)點(diǎn)和尾節(jié)點(diǎn)都設(shè)置為NULL。

void initLinkedList(LinkedList* list) {list->head = NULL;list->tail = NULL;
}

3. 判空

??isEmpty函數(shù)：判斷鏈表是否為空，即頭節(jié)點(diǎn)是否為NULL。

bool isEmpty(const LinkedList* list) {return list->head == NULL;
}

4. 串尾添加

?? append函數(shù)：向鏈表末尾添加一個(gè)字符節(jié)點(diǎn)。

void append(LinkedList* list, char data) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = data;newNode->next = NULL;if (isEmpty(list)) {list->head = newNode;list->tail = newNode;} else {list->tail->next = newNode;list->tail = newNode;}
}

• 如果鏈表為空，即頭節(jié)點(diǎn)為NULL，則將新節(jié)點(diǎn)設(shè)置為頭節(jié)點(diǎn)和尾節(jié)點(diǎn)。
• 如果鏈表不為空，即頭節(jié)點(diǎn)不為NULL，則將新節(jié)點(diǎn)鏈接到尾節(jié)點(diǎn)的后面，并將尾節(jié)點(diǎn)更新為新節(jié)點(diǎn)。

5. 打印

?? display函數(shù)：遍歷鏈表并打印出所有字符節(jié)點(diǎn)的數(shù)據(jù)。

void display(const LinkedList* list) {Node* current = list->head;while (current != NULL) {printf("%c", current->data);current = current->next;}printf("\n");
}

• 函數(shù)接受一個(gè)指向LinkedList結(jié)構(gòu)體的指針作為參數(shù)，然后從頭節(jié)點(diǎn)開(kāi)始遍歷鏈表，打印每個(gè)節(jié)點(diǎn)的數(shù)據(jù)。

6. 串長(zhǎng)統(tǒng)計(jì)

?? length函數(shù)：計(jì)算鏈表的長(zhǎng)度，即字符節(jié)點(diǎn)的個(gè)數(shù)。

int length(const LinkedList* list) {int count = 0;Node* current = list->head;while (current != NULL) {count++;current = current->next;}return count;
}

• 函數(shù)接受一個(gè)指向LinkedList結(jié)構(gòu)體的指針作為參數(shù)，然后從頭節(jié)點(diǎn)開(kāi)始遍歷鏈表，每遍歷一個(gè)節(jié)點(diǎn)，計(jì)數(shù)器加1，最后返回計(jì)數(shù)器的值。

7. 查找

?? search函數(shù)：在鏈表中搜索目標(biāo)字符串。

int search(const LinkedList* list, const char* target) {int targetLength = strlen(target);int listLength = length(list);if (targetLength > listLength) {printf("Error: Target string is longer than the source string.\n");return -1;}Node* current = list->head;int index = 0;while (current != NULL) {if (current->data == target[0]) {Node* temp = current;int i = 0;while (temp != NULL && temp->data == target[i]) {temp = temp->next;i++;if (i == targetLength) {return index;}}}current = current->next;index++;}printf("Error: Target string not found in the source string.\n");return -1;
}

• 首先比較目標(biāo)字符串的長(zhǎng)度和鏈表的長(zhǎng)度，如果目標(biāo)字符串比鏈表長(zhǎng)，說(shuō)明無(wú)法找到目標(biāo)字符串，函數(shù)返回錯(cuò)誤。
• 然后從頭節(jié)點(diǎn)開(kāi)始遍歷鏈表，找到第一個(gè)與目標(biāo)字符串首字符相同的節(jié)點(diǎn)，
  • 然后從該節(jié)點(diǎn)開(kāi)始逐個(gè)比較字符，直到找到完全匹配的目標(biāo)字符串或鏈表遍歷結(jié)束。
  • 如果找到目標(biāo)字符串，函數(shù)返回目標(biāo)字符串在鏈表中的起始位置的索引；
  • 如果未找到目標(biāo)字符串，函數(shù)返回錯(cuò)誤。

8. 復(fù)制

??copy函數(shù)：將源鏈表中的字符復(fù)制到目標(biāo)鏈表中。

bool copy(LinkedList* dest, const LinkedList* src) {Node* current = src->head;while (current != NULL) {append(dest, current->data);current = current->next;}return true;
}

• 函數(shù)接受兩個(gè)指向LinkedList結(jié)構(gòu)體的指針，分別表示源鏈表和目標(biāo)鏈表。
• 通過(guò)遍歷源鏈表的每個(gè)節(jié)點(diǎn)，創(chuàng)建一個(gè)新節(jié)點(diǎn)并將數(shù)據(jù)復(fù)制過(guò)去，然后將新節(jié)點(diǎn)添加到目標(biāo)鏈表的末尾。

9. 插入

?? insert函數(shù)：在鏈表的指定位置插入一個(gè)字符串。

bool insert(LinkedList* list, const char* insertStr, int pos) {int listLength = length(list);int insertStrLength = strlen(insertStr);if (pos < 0 || pos > listLength) {printf("Error: Invalid insertion position.\n");return false;}Node* current = list->head;int index = 0;while (current != NULL) {if (index == pos) {for (int i = 0; i < insertStrLength; i++) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = insertStr[i];newNode->next = current->next;current->next = newNode;current = newNode;}return true;}current = current->next;index++;}return false;
}

• 首先判斷插入位置是否合法，即索引是否在有效范圍內(nèi)。然后遍歷鏈表找到插入位置的節(jié)點(diǎn)，然后逐個(gè)創(chuàng)建新節(jié)點(diǎn)并插入到鏈表中。

10. 刪除

??delete函數(shù)：從鏈表中刪除指定位置和長(zhǎng)度的字符。

bool delete(LinkedList* list, int pos, int len) {int listLength = length(list);if (pos < 0 || pos >= listLength) {printf("Error: Invalid deletion position.\n");return false;}if (pos + len > listLength) {printf("Error: Deletion length exceeds the length of the string.\n");return false;}Node* current = list->head;int index = 0;while (current != NULL) {if (index == pos) {Node* prev = current;Node* temp = current;for (int i = 0; i < len; i++) {temp = temp->next;free(prev);prev = temp;}current->next = temp;return true;}current = current->next;index++;}return false;
}

• 首先判斷刪除位置是否合法，然后找到刪除位置的節(jié)點(diǎn)，逐個(gè)刪除指定長(zhǎng)度的節(jié)點(diǎn)。

11. 串拼接

??concat函數(shù)：將第二個(gè)鏈表中的字符追加到第一個(gè)鏈表的末尾。的末尾。

bool concat(LinkedList* list1, const LinkedList* list2) {Node* current = list2->head;while (current != NULL) {append(list1, current->data);current = current->next;}return true;
}

• 遍歷第二個(gè)鏈表的每個(gè)節(jié)點(diǎn)，將節(jié)點(diǎn)的數(shù)據(jù)追加到第一個(gè)鏈表。

12. 銷毀

??destroy函數(shù)：釋放鏈表占用的內(nèi)存。遍歷鏈表的每個(gè)節(jié)點(diǎn)，釋放節(jié)點(diǎn)的內(nèi)存，并將頭節(jié)點(diǎn)和尾節(jié)點(diǎn)設(shè)置為NULL。

void destroy(LinkedList* list) {Node* current = list->head;while (current != NULL) {Node* temp = current;current = current->next;free(temp);}list->head = NULL;list->tail = NULL;
}

• 函數(shù)遍歷鏈表的每個(gè)節(jié)點(diǎn)，釋放節(jié)點(diǎn)的內(nèi)存，并將頭節(jié)點(diǎn)和尾節(jié)點(diǎn)設(shè)置為NULL。

13. 主函數(shù)

int main() {LinkedList S;initLinkedList(&S);const char target[] = "H";LinkedList copyStr;initLinkedList(&copyStr);const char insertStr[] = "H";int pos = 3;append(&S, 'q');append(&S, 'o');append(&S, 'm');append(&S, 'o');append(&S, 'l');append(&S, 'a');append(&S, 'n');append(&S, 'g');append(&S, 'm');append(&S, 'a');display(&S);int searchIndex = search(&S, target);if (searchIndex != -1) {printf("Target string found at index: %d\n", searchIndex);}copy(&copyStr, &S);display(&copyStr);insert(&S, insertStr, pos);display(&S);delete(&S, pos, strlen(insertStr));display(&S);concat(&S, &copyStr);display(&S);destroy(&S);destroy(&copyStr);return 0;
}

14. 代碼整合

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>typedef struct Node {char data;struct Node* next;
} Node;typedef struct {Node* head;Node* tail;
} LinkedList;void initLinkedList(LinkedList* list) {list->head = NULL;list->tail = NULL;
}bool isEmpty(const LinkedList* list) {return list->head == NULL;
}void append(LinkedList* list, char data) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = data;newNode->next = NULL;if (isEmpty(list)) {list->head = newNode;list->tail = newNode;} else {list->tail->next = newNode;list->tail = newNode;}
}void display(const LinkedList* list) {Node* current = list->head;while (current != NULL) {printf("%c", current->data);current = current->next;}printf("\n");
}int length(const LinkedList* list) {int count = 0;Node* current = list->head;while (current != NULL) {count++;current = current->next;}return count;
}int search(const LinkedList* list, const char* target) {int targetLength = strlen(target);int listLength = length(list);if (targetLength > listLength) {printf("Error: Target string is longer than the source string.\n");return -1;}Node* current = list->head;int index = 0;while (current != NULL) {if (current->data == target[0]) {Node* temp = current;int i = 0;while (temp != NULL && temp->data == target[i]) {temp = temp->next;i++;if (i == targetLength) {return index;}}}current = current->next;index++;}printf("Error: Target string not found in the source string.\n");return -1;
}bool copy(LinkedList* dest, const LinkedList* src) {Node* current = src->head;while (current != NULL) {append(dest, current->data);current = current->next;}return true;
}bool insert(LinkedList* list, const char* insertStr, int pos) {int listLength = length(list);int insertStrLength = strlen(insertStr);if (pos < 0 || pos > listLength) {printf("Error: Invalid insertion position.\n");return false;}Node* current = list->head;int index = 0;while (current != NULL) {if (index == pos) {for (int i = 0; i < insertStrLength; i++) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = insertStr[i];newNode->next = current->next;current->next = newNode;current = newNode;}return true;}current = current->next;index++;}return false;
}bool delete(LinkedList* list, int pos, int len) {int listLength = length(list);if (pos < 0 || pos >= listLength) {printf("Error: Invalid deletion position.\n");return false;}if (pos + len > listLength) {printf("Error: Deletion length exceeds the length of the string.\n");return false;}Node* current = list->head;int index = 0;while (current != NULL) {if (index == pos) {Node* prev = current;Node* temp = current;for (int i = 0; i < len; i++) {temp = temp->next;free(prev);prev = temp;}current->next = temp;return true;}current = current->next;index++;}return false;
}bool concat(LinkedList* list1, const LinkedList* list2) {Node* current = list2->head;while (current != NULL) {append(list1, current->data);current = current->next;}return true;
}void destroy(LinkedList* list) {Node* current = list->head;while (current != NULL) {Node* temp = current;current = current->next;free(temp);}list->head = NULL;list->tail = NULL;
}int main() {LinkedList S;initLinkedList(&S);const char target[] = "H";LinkedList copyStr;initLinkedList(&copyStr);const char insertStr[] = "H";int pos = 3;append(&S, 'q');append(&S, 'o');append(&S, 'm');append(&S, 'o');append(&S, 'l');append(&S, 'a');append(&S, 'n');append(&S, 'g');append(&S, 'm');append(&S, 'a');display(&S);int searchIndex = search(&S, target);if (searchIndex != -1) {printf("Target string found at index: %d\n", searchIndex);}copy(&copyStr, &S);display(&copyStr);insert(&S, insertStr, pos);display(&S);delete(&S, pos, strlen(insertStr));display(&S);concat(&S, &copyStr);display(&S);destroy(&S);destroy(&copyStr);return 0;
}