【9】數據結構的串篇章

目錄標題

- 串的定義
- 順序串的實現
- - - 初始化
    - 賦值
    - 打印串
    - 求串的長度
    - 復制串
    - 判斷兩個串長度是否相等
    - 連接兩個串
    - 比較兩個串內容是否相等
    - 插入操作
    - 刪除操作
    - 調試與代碼合集
- 串的模式匹配算法
- - 樸素的模式匹配算法
  - KMP算法實現模式匹配

串的定義

定義：由0個或多個字符組成的有限序列，由一對雙引號引起來。記為"S"

順序串的實現

初始化

    def __init__(self):"""串初始化"""self.str = list()self.length = ()

賦值

    def strAssign(self, string):"""賦值:param string: 待賦值的串:return:"""# 計算串的長度length = len(string)# 賦值self.str = list()for i in range(length):self.str.append(string[i])# 設置串的長度self.length = length

打印串

    def display(self):"""打印:return:"""print('當前串的長度：', end='')for i in range(self.length):print(self.str[i], end='')print()

求串的長度

    def getLength(self):"""求串的長度:return: 串的長度"""return self.length

復制串

    def strCopy(self, string):"""復制串:param string: 待復制的串:return:"""# 將當前串初始化self.str = list()# 循環復制for char in string.str:self.str.append(char)# 設置當前串的長度self.length = string.getLength()

判斷兩個串長度是否相等

    def strEquals(self, string):"""判斷兩個串是否相等:param string: 待判定是否相等的串:return: 是否相等 true or false"""if self.length == string.getLength():# 循環，逐一比較for i in range(self.length):if self.str[i] != string.str[i]:break# 判斷，如果i等于串的長度，則相等：否則不相等i += 1if i == self.length:return Trueelse:return Falseelse:return False

連接兩個串

    def strConnect(self, string2):"""連接兩個串:param string2: 串2:return:"""# 生成新串，并初始化newString = String()# 循環for i in range(self.length):newString.str.append(self.str[i])# 循環for i in range(string2.getLength()):newString.str.append(string2.str[i])# 設置串的長度newString.length = self.length + string2.getLength()return newString

比較兩個串內容是否相等

    def strCompete(self, string):"""兩個串比較大小:param string: 帶比較大小的串:return: 1為大于，0為等于，-1為小于"""# 循環，逐個比較兩個串相應位置的字符大小index = 0while index < self.length and index < string.getLength():if self.str[index] > string.str[index]:return 1elif self.str[index] < string.str[index]:return -1index += 1# 判斷兩個串是否還有字符，還存在字符的串大if index < self.length:return 1elif index < string.getLength():return -1else:return 0

插入操作

    def insert(self, offset, string):"""插入:param offset: 插入位置:param string::return:"""# 判斷位置是否正確if offset < 0 or offset > self.length:print("插入位置不合法！")return# 備份當前串temp = self.str# 初始化串self.str = list()for i in range(offset):self.str.append(temp[i])# 將待插入的串存入當前串for i in range(string.getLength()):self.str.append(string.str[i])# 將目標串剩余字符存入當前串for i in range(offset, self.length):self.str.append(temp[i])# 設置串的長度self.length = self.length + string.getLength()

刪除操作

    def delete(self, offset, len):"""刪除:param offset: 刪除開始位置:param len: 刪除長度:return:"""# 判斷位置與長度是否合法if offset < 0 or offset > self.length or len > self.length - offset:print('刪除位置不合法！')return# 備份當前串temp = self.str# 初始化串self.str = list()for i in range(offset):self.str.append(temp[i])# 將目標串剩余的字符存入當前串for i in range(offset + len, self.length):self.str.append(temp[i])# 設置串的長度self.length = self.length - len

調試與代碼合集

class String:"""串的定義"""def __init__(self):"""串初始化"""self.str = list()self.length = ()def strAssign(self, string):"""賦值:param string: 待賦值的串:return:"""# 計算串的長度length = len(string)# 賦值self.str = list()for i in range(length):self.str.append(string[i])# 設置串的長度self.length = lengthdef display(self):"""打印:return:"""print('當前串的長度：', end='')for i in range(self.length):print(self.str[i], end='')print()def getLength(self):"""求串的長度:return: 串的長度"""return self.lengthdef strCopy(self, string):"""復制串:param string: 待復制的串:return:"""# 將當前串初始化self.str = list()# 循環復制for char in string.str:self.str.append(char)# 設置當前串的長度self.length = string.getLength()def strEquals(self, string):"""判斷兩個串是否相等:param string: 待判定是否相等的串:return: 是否相等 true or false"""if self.length == string.getLength():# 循環，逐一比較for i in range(self.length):if self.str[i] != string.str[i]:break# 判斷，如果i等于串的長度，則相等：否則不相等i += 1if i == self.length:return Trueelse:return Falseelse:return Falsedef strConnect(self, string2):"""連接兩個串:param string2: 串2:return:"""# 生成新串，并初始化newString = String()# 循環for i in range(self.length):newString.str.append(self.str[i])# 循環for i in range(string2.getLength()):newString.str.append(string2.str[i])# 設置串的長度newString.length = self.length + string2.getLength()return newStringdef strCompete(self, string):"""兩個串比較大小:param string: 帶比較大小的串:return: 1為大于，0為等于，-1為小于"""# 循環，逐個比較兩個串相應位置的字符大小index = 0while index < self.length and index < string.getLength():if self.str[index] > string.str[index]:return 1elif self.str[index] < string.str[index]:return -1index += 1# 判斷兩個串是否還有字符，還存在字符的串大if index < self.length:return 1elif index < string.getLength():return -1else:return 0def insert(self, offset, string):"""插入:param offset: 插入位置:param string::return:"""# 判斷位置是否正確if offset < 0 or offset > self.length:print("插入位置不合法！")return# 備份當前串temp = self.str# 初始化串self.str = list()for i in range(offset):self.str.append(temp[i])# 將待插入的串存入當前串for i in range(string.getLength()):self.str.append(string.str[i])# 將目標串剩余字符存入當前串for i in range(offset, self.length):self.str.append(temp[i])# 設置串的長度self.length = self.length + string.getLength()def delete(self, offset, len):"""刪除:param offset: 刪除開始位置:param len: 刪除長度:return:"""# 判斷位置與長度是否合法if offset < 0 or offset > self.length or len > self.length - offset:print('刪除位置不合法！')return# 備份當前串temp = self.str# 初始化串self.str = list()for i in range(offset):self.str.append(temp[i])# 將目標串剩余的字符存入當前串for i in range(offset + len, self.length):self.str.append(temp[i])# 設置串的長度self.length = self.length - lenif __name__ == '__main__':# 16.串string1 = String()str = input('請輸入你的第1個串的內容：')string1.strAssign(str)string1.display()print(f"當前string1串的長度為:{string1.getLength()}")# 復制string2 = String()str = input('請輸入你的第2個串的內容：')string2.strAssign(str)string2.display()print(f"當前string2串的長度為:{string2.getLength()}")# string1.strCopy(string2)string1.display()print(f"當前string1串的長度為:{string1.getLength()}")# 判斷是否相等串result = string1.strEquals(string2)if result:print('兩個串相等')else:print('兩個串不相等')# 連接兩個串string3 = string1.strConnect(string2)string3.display()print(f"當前string3串的長度為:{string3.length}")# 兩個串比較大小result = string1.strCompete(string2)if result == 1:print('string1 大于 string2')elif result == -1:print("string1 小于 string2")else:print('string1 等于 string2')# 插入string1.insert(3, string2)string1.display()print(f"當前string1的長度為:{string1.length}")# 刪除string1.delete(3, 2)string1.display()print(f"當前string1的長度為:{string1.length}")

串的模式匹配算法

樸素的模式匹配算法

核心思路
- 也稱為暴力搜索算法。
- 從目標串S的第一個字符開始與模式串P的第一個字符進行匹配
- 如果匹配，繼續逐個匹配后續字符，
- 如果不匹配，模式串P返回到第一個字符，與目標串S的第二個字符進行匹配，
- 如果匹配，繼續逐個匹配后續字符，
- 如果不匹配，模式串P返回到第一個字符，與目標串S的第三個字符進行匹配，
- 以此類推…
最好情況：從第一個字符開始就匹配成功，模式串數量m，則時間復雜度為O(m)
最壞情況：沒有匹配成功，每次匹配比較m次，共匹配n-m+1次，時間復雜度為O(n×m).
代碼實現

def bruteForce(string1, string2):"""暴力模式匹配:param string2::return:"""i = 0j = 0while i < len(string1) and j < len(string2):if string1[i] == string2[j]:j += 1i += 1else:i = i-j+1j = 0# 如果找到返回索引if j == len(string2):index = i - len(string2)# 否則返回-1else:index = -1return indexif __name__ == '__main__':string1 = "ababdabcd"string2 = "abc"print(bruteForce(string1, string2) + 1)

KMP算法實現模式匹配

核心思路
- next列表的設計與生成。
- 使用前后綴列表的方式去解析next值的設定
- 其中：
  - 前綴列表表示除去最后一個字符后的前面所有子串組成的集合；
  - 后綴列表表示除去第一個字符后的后面所有子串組成的集合。
- 以“abcabd”為例，求的next列表
- 1.串‘a’的前綴和后綴均為空集，最長共有元素長度為0，
- 2.串“ab”的前綴為{“a”}，后綴集合為{‘b’}，沒有相同的前后綴的子串，最長共有元素長度為0，
- 3.串“abc”的前綴集合為{“a”，“ab”}，后綴為{“c”，“bc”}，沒有相同的前后綴的子串，最長共有元素長度為0，
- 4.串“abca”的前綴集合為{“a”，“ab”，“abc”}，后綴為{“a”，“ca”，“bca”}，相同的前后綴子串為“a”，最長共有元素長度為1，
- 5.串“abcab”的前綴集合為{“a”，“ab”，“abc”，“abca”}，后綴為{“b”，“ab”，“cab”，“bcab”}，相同的前后綴子串為“ab”，最長共有元素長度為2，
- 6.串“abcabd”的前綴集合為{“a”，“ab”，“abc”，“abca”，“abcab”}，后綴為{“d”，“bd”，“abd”，“cabd”，“bcabd”}，沒有相同的前后綴子串，最長共有元素長度為0，
- 7.最后得出字符串“abcabd”的next列表為[-1,0,0,0,1,2].
代碼實現

def createNext(pattern):length = len(pattern)# 定義next列表next = [0 for _ in range(len(pattern))]next[0] = -1next[1] = 0# 計算next列表k = -1j = 0while j < length-1:if pattern[k] == pattern[j] or k == -1:j += 1k += 1next[j] = kelse:k = next[k]print(next)return nextdef kmpSearch(text, pattern):# 得到next列表next = createNext(pattern)# 匹配字符串i = 0j = 0while i < len(text) and j < len(pattern):if text[i] == pattern[j] or j == -1:i += 1j += 1else:j = next[j]if j >= len(pattern):return Trueelse:return Falseif __name__ == '__main__':text = "ababdabcabcabd"pattern = "abcabd"print(kmpSearch(text, pattern))