- Python算法详解
- 张玲玲
- 672字
- 2020-06-27 17:50:52
4.2.4 实践演练——单链表结构字符串
下面的实例文件zifuchuan.py演示了实现单链表结构字符串的过程。
源码路径：daima\第4章\zifuchuan.py
（1）定义单链表字符串类string，对应实现代码如下所示。
class string(single_list):
def __init__(self, value):
self.value = str(value)
single_list.__init__(self)
for i in range(len(self.value)-1,-1,-1):
self.prepend(self.value[i])
def length(self):
return self._num
def printall(self):
p = self._head
print("字符串结构：",end="")
while p:
print(p.elem, end="")
if p.next:
print("-->", end="")
p = p.next
print("")
（2）定义方法naive_matching()以实现匹配算法，返回匹配的起始位置，对应实现代码如下所示。
def naive_matching(self, p): #self为目标字符串，t为要查找的字符串
if not isinstance(self, string) and not isinstance(p, string):
raise stringTypeError
m, n = p.length(), self.length()
i, j = 0, 0
while i < m and j < n:
if p.value[i] == self.value[j]:#字符相同，考虑下一对字符
i, j = i+1, j+1
else: #字符不同，考虑t中下一个位置
i, j = 0, j-i+1
if i == m: #i==m，说明找到匹配，返回其下标
return j-i
return -1
（3）定义方法matching_KMP()以实现KMP匹配算法，返回匹配的起始位置，对应实现代码如下所示。
def matching_KMP(self, p):
j, i = 0, 0
n, m = self.length(), p.length()
while j < n and i < m:
if i == -1 or self.value[j] == p.value[i]:
j, i = j + 1, i + 1
else:
i = string.gen_next(p)[i]
if i == m:
return j - i
return -1
（4）定义方法gen_next()以生成pnext表，对应实现代码如下所示。
@staticmethod
def gen_next(p):
i, k, m = 0, -1, p.length()
pnext = [-1] * m
while i < m - 1:
if k == -1 or p.value[i] == p.value[k]:
i, k = i + 1, k + 1
pnext[i] = k
else:
k = pnext[k]
return pnext
（5）定义方法replace()，把old字符串出现的位置换成new字符串，对应实现代码如下所示。
def replace(self, old, new):
if not isinstance(self, string) and not isinstance(old, string) \
and not isinstance(new, string):
raise stringTypeError
#删除匹配的旧字符串
start = self.matching_KMP(old)
for i in range(old.length()):
self.delitem(start)
#末尾情况下是用append操作追加的，顺序为正；而在前面的地方插入为前插；所以要分情况对待
if start<self.length():
for i in range(new.length()-1, -1, -1):
self.insert(start,new.value[i])
else:
for i in range(new.length()):
self.insert(start,new.value[i])
if __name__=="__main__":
a = string("abcda")
print("字符串长度：",a.length())
a.printall()
b = string("abcabaabcdabdabcda")
print("字符串长度：", b.length())
b.printall()
print("朴素算法_匹配的起始位置：",b.naive_matching(a),end=" ")
print("KMP算法_匹配的起始位置：",b.matching_KMP(a))
c = string("xu")
print("==")
b.replace(a,c)
print("替换后的字符串是：")
b.printall()
上述解决方案有一个缺陷，在初始化字符串string对象时使用的是self.value=str(value)；而在后面使用匹配算法时，无论是朴素匹配还是KMP匹配，都使用对象的value值来做比较。所以对象在实现replace()方法后的start=b.mathcing_KMP(a)后依旧不会发生变化，会一直为6。原因在于使用self.value进行匹配，所以replace()方法后的链表字符串里的值并没有被用到，从而发生严重的错误。执行后会输出：
字符串长度： 5 字符串结构：a-->b-->c-->d-->a 字符串长度： 18 字符串结构：a-->b-->c-->a-->b-->a-->a-->b-->c-->d-->a-->b-->d-->a-->b-->c-->d-->a 朴素算法_匹配的起始位置：6 KMP算法_匹配的起始位置：6 == 替换后的字符串是： 字符串结构：a-->b-->c-->a-->b-->a-->x-->u-->b-->d-->a-->b-->c-->d-->a
在下面的实例文件gaijin.py中，基于上面的实例文件zifuchuan.py进行改进，通过replace()实现字符串类的多次匹配操作。文件gaijin.py的主要实现代码如下所示。
源码路径：daima\第4章\gaijin.py
class string(single_list):
def __init__(self, value):
self.value = str(value)
single_list.__init__(self)
for i in range(len(self.value)-1,-1,-1):
self.prepend(self.value[i])
def length(self):
return self._num
#获取字符串对象值的列表，方便下面使用
def get_value_list(self):
l = []
p = self._head
while p:
l.append(p.elem)
p = p.next
return l
def printall(self):
p = self._head
print("字符串结构：",end="")
while p:
print(p.elem, end="")
if p.next:
print("-->", end="")
p = p.next
print("")
#朴素的串匹配算法，返回匹配的起始位置
def naive_matching(self, p): #self为目标字符串，t为要查找的字符串
if not isinstance(self, string) and not isinstance(p, string):
raise stringTypeError
m, n = p.length(), self.length()
i, j = 0, 0
while i < m and j < n:
if p.get_value_list()[i] == self.get_value_list()[j]:#字符相同，考虑下一对字符
i, j = i+1, j+1
else: #字符不同，考虑t中下一个位置
i, j = 0, j-i+1
if i == m: #i==m，说明找到匹配，返回其下标
return j-i
return -1
#KMP匹配算法，返回匹配的起始位置
def matching_KMP(self, p):
j, i = 0, 0
n, m = self.length(), p.length()
while j < n and i < m:
if i == -1 or self.get_value_list()[j] == p.get_value_list()[i]:
j, i = j + 1, i + 1
else:
i = string.gen_next(p)[i]
if i == m:
return j - i
return -1
# 生成pnext表
@staticmethod
def gen_next(p):
i, k, m = 0, -1, p.length()
pnext = [-1] * m
while i < m - 1:
if k == -1 or p.get_value_list()[i] == p.get_value_list()[k]:
i, k = i + 1, k + 1
pnext[i] = k
else:
k = pnext[k]
return pnext
#把old字符串出现的位置换成new字符串
def replace(self, old, new):
if not isinstance(self, string) and not isinstance(old, string) \
and not isinstance(new, string):
raise stringTypeError
while self.matching_KMP(old) >= 0:
#删除匹配的旧字符串
start = self.matching_KMP(old)
print("依次发现的位置:",start)
for i in range(old.length()):
self.delitem(start)
#末尾情况下是用append操作追加的，顺序为正；而在前面的地方插入为前插；所以要分情况对待
if start<self.length():
for i in range(new.length()-1, -1, -1):
self.insert(start,new.value[i])
else:
for i in range(new.length()):
self.insert(start,new.value[i])
if __name__=="__main__":
a = string("abc")
print("字符串长度：",a.length())
a.printall()
b = string("abcbccdabc")
print("字符串长度：", b.length())
b.printall()
print("朴素算法_匹配的起始位置：",b.naive_matching(a),end=" ")
print("KMP算法_匹配的起始位置：",b.matching_KMP(a))
c = string("xu")
print("==")
b.replace(a,c)
print("替换后的字符串是：")
b.printall()
print(b.get_value_list())
其实上述方案依然有些缺陷，因为Python字符串对象是一个不变对象，所以replace()方法并不会修改原先的字符串，而只是返回修改后的字符串，而这个字符串对象是用单链表结构实现的，在实现replace()方法时改变了字符串对象本身的结构。执行后会输出：
字符串长度： 3 字符串结构：a-->b-->c 字符串长度： 10 字符串结构：a-->b-->c-->b-->c-->c-->d-->a-->b-->c 朴素算法_匹配的起始位置：0 KMP算法_匹配的起始位置：0 == 依次发现的位置: 0 依次发现的位置: 6 替换后的字符串是： 字符串结构：x-->u-->b-->c-->c-->d-->x-->u ['x', 'u', 'b', 'c', 'c', 'd', 'x', 'u']