串是一种常见的数据结构，这里使用Python定义类来实现相应的方法。先看代码，再对相关知识进行讲解。
# coding=utf-8
__all__=['ADTString']
class ADTString(object):
'''
此类用于描述串，包含以下方法
'''
def __init__(self, d=''):
'''
data用于存储串
'''
self.data = d
def StrCopy(self):
'''
复制函数，返回主串data
'''
return self.data
def ClearString(self):
'''
清空主串
'''
self.data = ''
def StringEmpty(self):
'''
判断主串是否为空，返回True或False
'''
return False if len(self.data) else True
def StrLength(self):
'''
返回主串的长度
'''
return len(self.data)
def StrCompare(self, T):
'''
主串和串T进行比较，大于串T返回1，等于串T返回0，小于串T返回-1
'''
len_S = self.StrLength()
len_T = T.StrLength()
len_min = min(len_S, len_T)
len_max = max(len_S, len_T)
i=j=0
while(True):
if (i>=len_min):
if len_min==len_max:
return 0
elif (j >=len_min):
return 1 if len_S > len_T else -1
if(self.data[i]==T.data[j]):
i=i+1
j=j+1
elif self.data[i]<T.data[j]:
return -1
elif self.data[i]>T.data[j]:
return 1
def Concat(self, S2):
'''
拼接主串和串S2
'''
return self.data+S2.data
def SubString(self, pos, len_):
'''
返回主串中，第pos个字符后len_长的子串
pos为负数，则逆序
'''
if pos >= 0:
if len(self.data) < pos:
return -1
return self.data[pos:pos+len_]
else:
if len_==0 or pos==-1:
return ''
elif pos+len_==0 or abs(pos)<len_:
return self.data[pos:-1]+self.data[-1]
else:
return self.data[pos:pos+len_]
def Index(self, T, pos):
'''
若主串S中存在和串T值相同的子串，则返回它在主串中第pos个字符之后第一次出现的位置，否则返回-1
'''
len_T = T.StrLength()
len_S = self.StrLength()
if len_S < len_T + pos:
return -1
p1 = pos
p2 = pos + len_T
while(p2<=len_S):
if self.SubString(p1, len_T) == T.data:
return p1
else:
p1=p1+1
p2=p2+1
if p2 > len_S:
return -1
def IndexBruteforce(self, T, pos):
'''
朴素匹配算法，若主串S中存在和串T值相同的子串，则返回它在主串中第pos个字符之后第一次出现的位置，否则返回-1；不使用串定义的方法来实现
'''
len_T = T.StrLength()
len_S = self.StrLength()
i=pos
j=0
while(True):
if i >= len_S or j >= len_T:
break
if(self.data[i]==T.data[j]):
i=i+1
j=j+1
else:
i=i-j+1
j=0
return i-j if j>=len_T else -1
def GetNext(self):
'''
返回KMP匹配算法所需的next数组
'''
len_S=self.StrLength()
next=[0]
i=1
while(True):
if i>=len_S:
break
k = next[i-1]
while(self.data[k]!=self.data[i] and k!=0):
k=next[k-1]
if self.data[k]==self.data[i]:
next.append(k+1)
else:
next.append(0)
i=i+1
return next
def IndexKMP(self, T, pos):
'''
KMP匹配算法，若主串S中存在和串T值相同的子串，则返回它在主串中第pos个字符之后第一次出现的位置，否则返回-1；不使用串定义的方法来实现
'''
next=self.GetNext()
len_T = T.StrLength()
len_S = self.StrLength()
i=pos
j=0
while(True):
if i >= len_S or j >= len_T:
break
if(self.data[i]==T.data[j]):
i=i+1
j=j+1
else:
i=i+next[i]+1
j=0
return i-j if j>=len_T else -1
def Replace(self, T, V):
'''
用串V替换主串S中，出现的所有与串T相等的不重叠的子串
'''
string = ''
len_S = len(self.data)
len_T = len(T.data)
p1=p2=0
while(True):
pos = self.Index(T, p2)
if pos == -1:
string+=self.data[p2:]
break
else:
p1=pos
string+=self.data[p2:p1]
string+= V.data
p2=p1+len_T
if string == '':
return self.data
else:
return string
def StrInsert(self, pos, T):
'''
在主串的第pos个字符后，插入串T;pos为负，则逆序插入
'''
len_S = len(self.data)
if len_S < pos or len_S <abs(pos):
return -1
return self.data[:pos]+T.data+self.data[pos:]
def StrDelete(self, pos, len_):
'''
在主串的第pos个字符后，删除len_长度的字符
pos小于0则逆序删除
'''
len_S = len(self.data)
if pos >= 0:
if len_S < pos:
return -1
return self.data[:pos]+self.data[pos+len_:]
else:
if len_S < abs(pos) :
return -1
return self.data[:pos-len_]+self.data[pos:]
if __name__ == '__main__':
from ADTString import ADTString
# 打印该类的readme文档
print help(ADTString)
第3行：__all__中定义的内容，是使用from <module> import * 时，会导出的内容。
第15~218行：串的一些基本方法，其中，第86~105行的Index，是使用到串SubString方法来实现的；第107~125行，是使用朴素匹配算法实现的；第149~167行，是使用KMP匹配算法来实现的。
第223行：是打印根据代码和注释，自动生成的参考文档。
下面对这个类进行单元测试，使用unittest模块，代码的最后两行，是执行单元测试的意思。
# conding=utf-8
from ADTString import ADTString
import unittest
class TestADTStringMethods(unittest.TestCase):
def setUp(self):
self.obj = ADTString()
def tearDown(self):
pass
def test_StrCopy(self):
self.obj.data=''
self.assertEqual(self.obj.StrCopy(), '')
self.obj.data='goodgoogle'
self.assertEqual(self.obj.StrCopy(), 'goodgoogle')
self.obj.data='!'
self.assertEqual(self.obj.StrCopy(), '!')
def test_ClearString(self):
self.obj.data='goodgoogle'
self.obj.ClearString()
self.assertEqual(self.obj.data, '')
def test_StringEmpty(self):
self.obj.data=''
self.assertEqual(self.obj.data, '')
def test_StrLength(self):
self.obj.data='
self.assertEqual(self.obj.StrLength(), 3)
self.obj.data=''
self.assertEqual(self.obj.StrLength(), 0)
def test_StrCompare(self):
obj_T=ADTString('goodgoogle')
self.obj.data='goodgoogle'
self.assertEqual(self.obj.StrCompare(obj_T),0)
self.obj.data='goodgoogl'
self.assertEqual(self.obj.StrCompare(obj_T),-1)
self.obj.data='goodgooglea'
self.assertEqual(self.obj.StrCompare(obj_T),1)
def test_Concat(self):
self.obj.data='good'
obj_S2=ADTString('google')
self.assertEqual(self.obj.Concat(obj_S2),'goodgoogle')
self.obj.data=''
self.assertEqual(self.obj.Concat(obj_S2),'google')
def test_SubString(self):
self.obj.data='goodgoogle'
self.assertEqual(self.obj.SubString(0,0),'')
self.assertEqual(self.obj.SubString(0,1),'g')
self.assertEqual(self.obj.SubString(0,4),'good')
self.assertEqual(self.obj.SubString(0,100),'goodgoogle')
self.assertEqual(self.obj.SubString(100,1),-1)
self.assertEqual(self.obj.SubString(-50,0),'')
self.assertEqual(self.obj.SubString(-5,0),'')
self.assertEqual(self.obj.SubString(-1,0),'')
self.assertEqual(self.obj.SubString(-1,1),'')
self.assertEqual(self.obj.SubString(-1,2),'')
self.assertEqual(self.obj.SubString(-6,1),'g')
self.assertEqual(self.obj.SubString(-6,6),'google')
self.assertEqual(self.obj.SubString(-6,100),'google')
self.assertEqual(self.obj.SubString(-6,10),'google')
def test_Index(self):
self.obj.data='goodgoogle'
obj_T=ADTString('good')
self.assertEqual(self.obj.Index(obj_T, 0),0)
self.assertEqual(self.obj.Index(obj_T, 1),-1)
self.obj.data='googlegood'
self.assertEqual(self.obj.Index(obj_T, 0),6)
self.assertEqual(self.obj.Index(obj_T, 7),-1)
self.obj.data=''
self.assertEqual(self.obj.Index(obj_T, 0),-1)
def test_IndexBruteforce(self):
self.obj.data='goodgoogle'
obj_T=ADTString('good')
self.assertEqual(self.obj.Index(obj_T, 0),0)
self.assertEqual(self.obj.Index(obj_T, 1),-1)
self.obj.data='googlegood'
self.assertEqual(self.obj.Index(obj_T, 0),6)
self.assertEqual(self.obj.Index(obj_T, 7),-1)
self.obj.data=''
self.assertEqual(self.obj.Index(obj_T, 0),-1)
def test_IndexKMP(self):
self.obj.data='goodgoogle'
obj_T=ADTString('good')
self.assertEqual(self.obj.Index(obj_T, 0),0)
self.assertEqual(self.obj.Index(obj_T, 1),-1)
self.obj.data='googlegood'
self.assertEqual(self.obj.Index(obj_T, 0),6)
self.assertEqual(self.obj.Index(obj_T, 7),-1)
self.obj.data=''
self.assertEqual(self.obj.Index(obj_T, 0),-1)
def test_Replace(self):
self.obj.data='good'
obj_T=ADTString('good')
obj_V=ADTString('replace')
self.assertEqual(self.obj.Replace(obj_T, obj_V),'replace')
self.obj.data='googlegood'
self.assertEqual(self.obj.Replace(obj_T, obj_V),'googlereplace')
self.obj.data='goodgooglegood'
self.assertEqual(self.obj.Replace(obj_T, obj_V),'replacegooglereplace')
self.obj.data=''
self.assertEqual(self.obj.Replace(obj_T, obj_V),'')
self.obj.data='aaa'
self.assertEqual(self.obj.Replace(obj_T, obj_V),'aaa')
def test_StrInsert(self):
self.obj.data='goodgoogle'
obj_T=ADTString('insert')
self.assertEqual(self.obj.StrInsert(0,obj_T),'insertgoodgoogle')
self.assertEqual(self.obj.StrInsert(100,obj_T),-1)
self.assertEqual(self.obj.StrInsert(len(self.obj.data),obj_T),'goodgoogleinsert')
self.assertEqual(self.obj.StrInsert(4,obj_T),'goodinsertgoogle')
self.assertEqual(self.obj.StrInsert(-1,obj_T),'goodgooglinserte')
self.assertEqual(self.obj.StrInsert(-100,obj_T),-1)
def test_StrDelete(self):
self.obj.data='goodgoogle'
self.assertEqual(self.obj.StrDelete(0,4),'google')
self.assertEqual(self.obj.StrDelete(0,100),'')
self.assertEqual(self.obj.StrDelete(-1,1),'goodgooge')
self.assertEqual(self.obj.StrDelete(-2,3),'goodgle')
self.assertEqual(self.obj.StrDelete(-2,100),'le')
self.assertEqual(self.obj.StrDelete(-100,1),-1)
suite = unittest.TestLoader().loadTestsFromTestCase(TestADTStringMethods)
unittest.TextTestRunner(verbosity=2).run(suite)
执行的结果如下：
test_ClearString (__main__.TestADTStringMethods) ... ok test_Concat (__main__.TestADTStringMethods) ... ok test_Index (__main__.TestADTStringMethods) ... ok test_IndexBruteforce (__main__.TestADTStringMethods) ... ok test_IndexKMP (__main__.TestADTStringMethods) ... ok test_Replace (__main__.TestADTStringMethods) ... ok test_StrCompare (__main__.TestADTStringMethods) ... ok test_StrCopy (__main__.TestADTStringMethods) ... ok test_StrDelete (__main__.TestADTStringMethods) ... ok test_StrInsert (__main__.TestADTStringMethods) ... ok test_StrLength (__main__.TestADTStringMethods) ... ok test_StringEmpty (__main__.TestADTStringMethods) ... ok test_SubString (__main__.TestADTStringMethods) ... ok ---------------------------------------------------------------------- Ran 13 tests in 0.001s OK [Finished in 0.1s]