本系列文章

(1) 數據結構淺析(1)-什麼是數據結構？

(2) 數據結構淺析(2)-集合

(3) 數據結構淺析(3)-線性結構：數組

(4) 數據結構淺析(4)-線性結構：線性表

本文目標

試著理解什麼是線性數據結構中的串string。

在生物信息學中，用串來描述由氮基組成的DNA鏈。

什麼是串

引用自維基百科 String (computer science)

在計算機程序設計中，字元串 string 通常是字元序列，要麼是文字常量，要麼是某種變數。後者可能允許其元素髮生突變，長度改變，或者是固定的（在創建之後）。字元串通常被認為是一種數據類型，通常作為位元組（或字）的數組數據結構來實現，它存儲了一系列元素，通常是使用一些字元編碼的字元。字元串還可以用來表示更一般的數組或其他序列（或列表）數據類型和結構。

根據所使用的編程語言和精確的數據類型，聲明為字元串的變數可能會導致內存中的存儲被靜態地分配給預先確定的最大長度，或者可以使用動態分配來容納可變數量的元素。

當一個字元串在源代碼中出現時，它被稱為字元串文字或匿名字元串。

在數學邏輯和理論計算機科學中使用的正式語言中，string 是由一個叫做字母表的集合所選擇的有限的符號序列。

我自己的看法

串 sting，一般又可以被稱作字元串，是由0個或則多個字元組成的有限序列。一般我們用S = "a1 a2 a3....an" 來表示，其中S 是串的名字，雙引號或則單引號作為串的定界符用來表示串的內容即串值，ai (0<= i <= n) 則代表串中的單個元素，n表示穿的個數即串中有幾個字元，當n 為0時，該串被稱為空串（null string），用雙引號「」來表示，符號記為Ф。

注，空白串（blank string）和空串的區別，空白串是由一個或多個空格組成的串。

串的形式理論

子串

串中任意幾個連續的字元組成的子序列即為該串的子串

主串

相應地，包含該子串的串稱為主串

子串的位置

子串在主串中首次出現時，該子串的首字元對應在主串中的序號，即為子串在主串中的位置。

這裡有一個很經典的例子用來輔助說明。例如，設A和B分別為 A=『This is a string』 B=『is』 則B是A的子串，A為主串。B在A中出現了兩次，其中首次出現所對應的主串位置是3。因此，稱B在A中的位置為3。 特別地，空串是任意串的子串，任意串是其自身的子串。

引自數據結構-串

連接 concatenation

連接是一個重要的二進位操作。對於任意兩個主串中的子串s和t，它們的連接根據放置s和t 的前後順序來定符號序列。例如，子串s = love，t = hug，那麼st 就是lovehug，ts 就是huglove。

前綴和後綴 prefixes and suffixes

字元串s 可以說是t 的前綴，如果存在一個字元串u 滿足條件t =su。如果u 是非空的，那麼可以說s 是t 的一個合適的前綴；相應地，串s 可以說t 的後綴如果存在一個串u 滿足條件t=us。如果u 是非空的，s 可以說是t 的一個合適的後綴。前綴和後綴可以說是t 的子串。

旋轉

串s = uv 可以被說成t 的旋轉如果t = vu. 舉個例子，當u = 00110, v = 01的時候，串0011001 是0100110 的旋轉。

逆轉

串的逆轉就是具有相同符號單順序相反的字元串。例如，如果s=abc（a、b和c是字母表中符號），那麼s 的逆轉就是cba。一個與自身相反的字元串（例如，s=madam，逆轉還是madam）被稱為迴文 palindrome，它還包括空字元串和所有長度為1的字元串。

串的特徵

串中存在的序列，說明串的相鄰字元之間具有前驅和後繼的關係。

串的基本操作

  • 結構初始化 StrAssign (&T, chars) 初始條件：chars 是串常量。 操作結果：生成一個其值等於 chars的串T。 串的抽象數據類型定義 StrCopy (&T, S) 初始條件：串 S 存在。 操作結果：由串 S 複製得串 T。
  • 銷毀結構 DestroyString (&S) 初始條件：串 S 存在。 操作結果：串 S 被銷毀。
  • 引用型操作 StrEmpty (S) 初始條件：串 S 存在。 操作結果：若 S 為空串，則返回 TRUE，否則返回 FALSE。 StrCompare (S, T) 初始條件：串 S 和 T 存在。 操作結果：若S>T，則返回值>0；若S=T，則返回值=0； 若S0) { n = StrLength (S); m = StrLength (T); // 求得串長 i = pos; while ( i <= n-m+1) { SubString (sub, S, i, m); // 取得從第 i 個字元起長度為 m 的子串 if (StrCompare (sub,T) != 0) ++i ; else return i ; // 找到和 T 相等的子串 } // while } // if return 0; // S 中不存在滿足條件的子串 } // Index

引自數據結構-串

  • StrAssign(T,*chars): 生成一個其值等於字元常量chars的串T.
  • StrCopy(T,S): 　　　　串S存在,由S複製得到T.
  • ClearString(S): 　　 串S存在,將串清空.
  • StringEmpty(S): 　　 若串為空,返回true,否則返回false.
  • StrLentgth(S) : 　　 返回串S的元素個數,即串的長度.
  • StrCompare(S,L): 　　　比較S和T,若S>T,返回>0,S==T返回0, S<T返回<0
  • SubString(Sub, S, pos, len): 串S存在,1<=pos<=StrLentgth(S),且 0<=len<=StrLentgth(S)-pos+1,用Sub返回串S的第pos個起長度為len的子串.
  • Index(S,T,pos)
  • Replace(S,T,V)　　　　 串S,T,V存在,T是非空串,用V替換S中出現的所有與T相等的不重疊的子串.
  • StrInsert(S,T,pos): 在串S的第pos個字元之前插入串T.
  • StrDelete(S,pos,len): 從串S中刪除第pos個字元起的長度為len的子串.

引自數據結構之串(string)

串的存儲結構

串的順序存儲結構

串的順序存儲結構是用一組地址連續的存儲單元來存儲串中的字元序列的。按照預定義的大小，為每個定義的串變數分配一個固定長度的存儲區。一般是用定長數組來定義。

串的鏈式存儲結構

串的鏈式存儲結構，與線性表是相似的，但由於串結構的特殊性，結構中的每個元素數據是一個字元，如果也簡單的應用鏈表存儲串值，一個結點對應一個字元，就會存在很大的空間浪費。因此，一個結點可以存放一個字元，也可以考慮存放多個字元，最後一個結點若是未被佔滿時，可以用「#」或其他非串值字元補全。

引自數據結構之串

串的比較法

串之間的比較是通過組成串的字元之間的編碼來進行的，而字元的編碼指的是字元在對應字符集中的序號。

目前計算機常用的主流編碼方式為標準的ASCII 編碼，由7位二進位數表示一個字元，總共可以表示128個字元。後來由於一些特殊符號的出現，128個不夠用，於是擴展ASCII 碼由8位二進位數表示一個字元，總共則可以表示256個字元，足以滿足以英語為主的語言和特殊符號進行輸入、存儲、輸出等操作的字元需要了。

然而全世界有成百上千種語言與文字，顯然256個字元是不夠的，因此後來就有了Unicode 編碼，比較常用的是由16位的二進位數表示一個字元，這樣總共就可以表示個字元，約是6.5萬多個字元，足夠表示世界上所有語言的所有字元了。為了和ASCII碼兼容，Unicode的前256個字元與ASCII碼完全相同。

引自維基百科-字元串

串的實現

Java

在Java 中有兩種方法來創建串:

  • 字面上直接創建

String s = 「JavaString」;

  • 使用new 來創建新的串

String s = new String (「NewJavaString」);

Python

a = "Hello, World!"
print(a[1])

輸出結果為e，要想輸出H, 需要print(a[0]).

b = "Hello, World!"
print(b[2:5])

輸出結果為llo

a = "Hello, World! "
print(a.strip())

輸出結果為Hello, World!

在下一篇文章中，將著重講的是線性結構(3) -棧 stack

如果你覺得我的文章有用，順手點個贊，關注下我的專欄或則留下你的評論吧！

推薦閱讀：

相关文章