目錄

1 字符串與數組的關系

1.1 字符串與數組的聯系

1.2 字符串與數組的區別

2 實現字符串的鏈式存儲（Java）

3 子串查找的簡單實現

---

1 字符串與數組的關系

1.1 字符串與數組的聯系

在初學編程的時候（比如Java），我們都會接觸字符串(string)和數組(array)這兩種數據類型。雖然從字面上不難理解，字符串就是由字符(character)組成的一串線性序列；即使如此，我們仍然會把字符串類型的變量看作存儲單值的變量，把數組類型的變量理解為存儲多值的變量。

然后，我們會學習字符串對象的一些常用方法，此時很容易感受到它與數組之間千絲萬縷的聯系，因為從字符串中提取字符和從數組中提取元素的方法都是以索引為依據的，關于數組通過索引訪問數據的原理，在上一篇筆記“重識數組(Array)”中有所闡述，鏈接貼在下面：

重識數組：https://blog.csdn.net/weixin_45370422/article/details/117395751

我們在下面的Java代碼中定義了一個字符串和一個字符類型的數組，并進行了兩個操作：①取出單個字符或元素，②切片取出一組連續的字符或元素。

package com.notes.data_structure5;import java.util.Arrays;public class StringDemo {public static void main(String[] args) {String string = "abc";char[] array = {'a','b','c'};// 取出單個字符 或 元素char strFirst = string.charAt(0);char arrFirst = array[0];System.out.println(strFirst); // aSystem.out.println(arrFirst); // a// 切片取出一組連續的字符 或 元素String subStr = string.substring(0,2);char[] subArr = Arrays.copyOfRange(array,0,2);System.out.println(subStr); // abSystem.out.println(subArr); // ab} }

打印char數組和字符串打印出來的結果居然是一樣的。我們打開String的源碼，可以看到如下注釋內容，指出定義字符串"abc"和定義字符數組{'a','b','c}效果是一樣的。因此，在Java中，字符串的底層的實現就是數組。

繼續往下滑，會看到字符串的值被定義為一個byte類型的數組，而且被定義為常量，且加上了注解stable，表示“一個字段的所有組件變量最多更改一次值”(A field may be annotated as stable if all of its component variables changes value at most once.?)，這就是常說的字符串的不可變性。

@Stableprivate final byte[] value;

雖然在Java中字符串和數組都能是基于索引隨機訪問元素，但是方法的寫法還是不一樣的。相比而言，Python更狠。Python沒有內置對數組的支持，用與之相似的列表(list)為例，字符串和列表的隨機訪問、切片和拼接的寫法完全一樣：

# 定義一個 字符串 和 一個元組 my_str = "abc" my_list = ["a", "b", "c"]# 隨機訪問 str_first = my_str[0] list_first = my_list[0] print(str_first, list_first) # a a# 切片 str_sub = my_str[0:2] list_sub = my_list[0:2] print(str_sub, list_sub) # ab ['a', 'b']# 拼接 str_new = my_str + "xyz" list_new = my_list + ["x", "y", "z"] print(str_new, list_new) # abcxyz ['a', 'b', 'c', 'x', 'y', 'z']

?

1.2 字符串與數組的區別

字符串和數組的主要區別不在原理層面，而在應用層面，用索引隨機訪問單一字符其實沒有多少應用價值。我們把數組變量看作存儲多值、字符串看作存儲單值是符合應用需求的，否則Java和Python不會不約而同地將一種字符串轉換數組的方法命名為split，意為“分隔”。以下是Java代碼：

package com.notes.data_structure5;import java.util.Arrays;public class StringDemo {public static void main(String[] args) {String string = "Hello world";String[] array = string.split(" ");System.out.println(Arrays.toString(array)); // [Hello, world]} }

以下是Python代碼：

my_str = "Hello world" my_list = my_str.split(" ") print(my_list) # ['Hello', 'world']

對于字符串，我們關注的焦點不是字符與字符串的關系，而是子串與主串的關系。換言之，字符串始終被作為一個整體來看待。所謂“子串”，就是一個字符串中某一段連續字符組成的字符串，上面演示的split方法的作用就是根據指定的分隔符將一個字符串切片成若干子串。

另外，字符串的底層實現也不一定非要是數組，和線性表中的棧和隊列一樣，字符串也有基于數組的順序存儲和基于鏈表的鏈式存儲兩種方式。關于棧和隊列的兩種實現方式，可以參考“數據結構學習筆記”系列之前的文章，鏈接貼在下面：

棧：https://blog.csdn.net/weixin_45370422/article/details/116889212

隊列：https://blog.csdn.net/weixin_45370422/article/details/117376241

在下一章，我們不妨用Java實現一個鏈式存儲的字符串。

?

2 實現字符串的鏈式存儲（Java）

最簡單粗暴的思路無疑是一個字符一個結點，然后把結點用指針連起來，但是這樣做很浪費空間，意義也不大，正如上一節提到的，對于字符串我們關注的焦點其實不是字符與串的關系。因此，我們不妨在一個結點中放入一個或多個字符。

基于上面的想法，我們設計這樣一個字符串，一個結點放入一個英文單詞或一個標點，結尾都是一個空格。我們用這個結構實現Linux創始人Linus Torvalds的名言：Talk is cheap, show me the code.

至于代碼層面，我們可以直接參照“數據結構學習筆記”系列博文的第一篇“鏈表”中的代碼（文章鏈接貼在下面）。為了體現一個結點放入多個字符的思路，將結點中的數據類型設置為字符數組(char[])。先把鏈表那篇文章的鏈接貼在下面。

鏈表：https://blog.csdn.net/weixin_45370422/article/details/116573863

由于我們的這個用Java實現的鏈式字符串沒有任何實用價值，因此僅定義了增加結點(addNode)和打印字符串(printString)兩個公共方法：

package com.notes.data_structure5;public class MyLinkedString {private Node headNode; // 定義一個頭結點private Node currentNode; // 定義一個當前結點// 定義一個結點類private class Node {// 結點的兩個要素：數據和指針private char[] data;private Node next;// 構造方法：Node實例化時給data賦值public Node(char[] data) {this.data = data;}}// 創建頭結點private Node addHeadNode() {// 頭結點用來模擬頭指針，數據設為 空數組headNode = new Node(new char[] {});return headNode;}// 增加結點，相當于 拼接 的過程public void addNode(char[] data) {// 如果頭結點不存在，當前結點為頭結點，這樣就有了頭指針if (headNode==null) {// 當前結點是頭結點，調用創建頭結點的方法currentNode = addHeadNode();}// 創建一個新的結點Node node = new Node(data);// 當前結點的指針指向新結點currentNode.next = node;// 當前結點后移一位，新結點成為當前結點，正式加入鏈表currentNode = currentNode.next;} // 遍歷打印所有的節點，為顯示字符串效果，打印不換行public void printString() {// temp是一個移動的指針，以頭指針為起點Node temp = headNode; // 通過指針的移動遍歷數組，直到指針指向鏈尾的nullwhile(temp.next != null) {temp = temp.next;System.out.print(temp.data);}} }

為了節省篇幅，我們用這個鏈式字符串實現上面那句名言的前半句：talk is cheap

package com.notes.data_structure5;public class linkedStringDemo {public static void main(String[] args) {MyLinkedString myString = new MyLinkedString();myString.addNode(new char[] {'t','a','l','k',' '});myString.addNode(new char[] {'i','s',' '});myString.addNode(new char[] {'c','h','e','a','p',' '});myString.addNode(new char[] {'.',' '});myString.printString();}}

運行結果如下：

talk is cheap .

?

3 子串查找的簡單實現

子串查找又被稱為字符串匹配，在開發過程中，這是很常見的一種需求。子串查找的工作包括三個要素：主串、模式串、子串。所謂字符串匹配，就是從主串中找出與模式串等值的子串。

子串查找最簡單的實現方式就是暴力(brute force, 簡稱BF)查找，這種方法簡單粗暴。字符串匹配基于主串和模式串的字符間的比對，假設主串字符數為n，模式串字符數為m，目標是判斷模式串是否為主串的子串，我們可以這樣設計比對的步驟：

將模式串的索引為0的字符依次與主串中索引0到索引(n-m)的字符依次進行比對。如果在主串k索引處比對成功，模式串0索引之后的字符分別與主串k索引之后的字符比對，如果一直比對到模式串的最后的一個字符，返回true；如果中途發生不匹配的情況，模式串從0索引開始，繼續與主串索引(k+1)到索引(n-m)的字符依次比對，重復上述過程。

假設我們的匹配目標是判斷 Linus 那句名言的后半句“show me your code.”中是否包含字符串“our”，那么過程如下，圖示中橙色箭頭代表比對成功，灰色箭頭代表比對失敗，有三條連續的橙色箭頭才算匹配成功。

代碼實現如下：

package com.notes.data_structure5;public class Demo {public static void main(String[] args) {Boolean result = isContain("show me your code.","our");System.out.println(result); // trueBoolean result2 = isContain("show me your code.","oua");System.out.println(result2); // false}public static Boolean isContain(String mainString, String patternString) {int n = mainString.length(); // 主串的字符數int m = patternString.length(); // 模式串的字符數int k = 0; // 模式串 首元素 與匹配成功的 主串字符 的 索引int count = 0; // 比對中的連續字符數for(int i=0;i<(n-m+1);i++) {// 如果模式串的第0個字符與當前主串字符匹配if(mainString.charAt(i) == patternString.charAt(0)) {k = i; // 在主串索引k的位置匹配成功，繼續匹配后續字符count = 1; // 已經比對上一個字符for(int j=1;j<m;j++) {// 如果后續字符出現不匹配的情況，不再比對if(mainString.charAt(k+j) != patternString.charAt(j)) {break;}count++;}if(count==m) { // 字符全部比中，匹配成功return true;}}}// 匹配失敗return false;} }

?

總結

以上是生活随笔為你收集整理的数据结构学习笔记（五）：重识字符串（String）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。