1. 串的定義

串是由0個(gè)或多個(gè)字符組成的有限序列，也叫做字符串。串中 字符數(shù)目n稱為串的長(zhǎng)度。

子串：串中任意個(gè)數(shù)的連續(xù)字符組成的子序列稱為該字符串的子串，包含該子串的串稱為主串。子串中的位置就是該子串第一個(gè)字符在主串中的序號(hào)。

2. 串的比較

計(jì)算機(jī)的字符串標(biāo)準(zhǔn)包括：ASCII碼和Unicode碼。其中ASCII由8位二進(jìn)制組成，可以表達(dá)256個(gè)字符；Unicode由16位二進(jìn)制組成，可以表達(dá)65536個(gè)字符。當(dāng)然unicode前面256個(gè)字符與ASCII一致。

3. 串的抽象數(shù)據(jù)類型

串的邏輯結(jié)構(gòu)和線性表很相似，不同之處在于串針對(duì)的是字符。

4. 串的存儲(chǔ)結(jié)構(gòu)

串的存儲(chǔ)結(jié)構(gòu)與線性表相同，分為兩種：順序存儲(chǔ)結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

4.1 串的順序存儲(chǔ)結(jié)構(gòu)

串的順序存儲(chǔ)結(jié)構(gòu)使用數(shù)組來(lái)存儲(chǔ)，字符串的實(shí)際長(zhǎng)度通可以存在數(shù)組的第一個(gè)位置，最后一個(gè)位置等。順序存儲(chǔ)結(jié)構(gòu)的最大缺點(diǎn)在于字符串在進(jìn)行一個(gè)操作，比如字符串合并等可能會(huì)導(dǎo)致溢出，字符串的長(zhǎng)度超過(guò)數(shù)組長(zhǎng)度。

4.2 串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與鏈表類似，不同之處在于每個(gè)節(jié)點(diǎn)可能存儲(chǔ)多個(gè)字符。

5. 樸素的模式匹配算法

簡(jiǎn)單的講，字符串匹配最簡(jiǎn)單的目的就是找某個(gè)字符串中是否包含另外一個(gè)字符串，如果包含則返回位置。比如在Python中有這樣find函數(shù)來(lái)實(shí)現(xiàn)功能。

# -*- coding: utf-8 -*-str_m = "abaababaddecab" # 母串 str_s = "abad" # 子串pos = str_m.find(str_s)

6.KMP模式匹配算法

reference：

http://www.cnblogs.com/c-cloud/p/3224788.html

http://www.cnblogs.com/huangxincheng/archive/2012/12/01/2796993.html

總結(jié)

以上是生活随笔為你收集整理的大话数据结构 - 串的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。