串是一种常见的数据结构,这里使用Python定义类来实现相应的方法。先看代码,再对相关知识进行讲解。
1 # coding=utf-8 2 3 __all__=['ADTString'] 4 5 class ADTString(object): 6 ''' 7 此类用于描述串,包含以下方法 8 ''' 9 def __init__(self, d=''): 10 ''' 11 data用于存储串 12 ''' 13 self.data = d 14 15 def StrCopy(self): 16 ''' 17 复制函数,返回主串data 18 ''' 19 return self.data 20 21 def ClearString(self): 22 ''' 23 清空主串 24 ''' 25 self.data = '' 26 27 def StringEmpty(self): 28 ''' 29 判断主串是否为空,返回True或False 30 ''' 31 return False if len(self.data) else True 32 33 def StrLength(self): 34 ''' 35 返回主串的长度 36 ''' 37 return len(self.data) 38 39 def StrCompare(self, T): 40 ''' 41 主串和串T进行比较,大于串T返回1,等于串T返回0,小于串T返回-1 42 ''' 43 len_S = self.StrLength() 44 len_T = T.StrLength() 45 len_min = min(len_S, len_T) 46 len_max = max(len_S, len_T) 47 i=j=0 48 while(True): 49 if (i>=len_min): 50 if len_min==len_max: 51 return 0 52 elif (j >=len_min): 53 return 1 if len_S > len_T else -1 54 55 if(self.data[i]==T.data[j]): 56 i=i+1 57 j=j+1 58 elif self.data[i]<T.data[j]: 59 return -1 60 elif self.data[i]>T.data[j]: 61 return 1 62 63 def Concat(self, S2): 64 ''' 65 拼接主串和串S2 66 ''' 67 return self.data+S2.data 68 69 def SubString(self, pos, len_): 70 ''' 71 返回主串中,第pos个字符后len_长的子串 72 pos为负数,则逆序 73 ''' 74 if pos >= 0: 75 if len(self.data) < pos: 76 return -1 77 return self.data[pos:pos+len_] 78 else: 79 if len_==0 or pos==-1: 80 return '' 81 elif pos+len_==0 or abs(pos)<len_: 82 return self.data[pos:-1]+self.data[-1] 83 else: 84 return self.data[pos:pos+len_] 85 86 def Index(self, T, pos): 87 ''' 88 若主串S中存在和串T值相同的子串,则返回它在主串中第pos个字符之后第一次出现的位置,否则返回-1 89 ''' 90 len_T = T.StrLength() 91 len_S = self.StrLength() 92 if len_S < len_T + pos: 93 return -1 94 95 p1 = pos 96 p2 = pos + len_T 97 while(p2<=len_S): 98 if self.SubString(p1, len_T) == T.data: 99 return p1 100 else: 101 p1=p1+1 102 p2=p2+1 103 104 if p2 > len_S: 105 return -1 106 107 def IndexBruteforce(self, T, pos): 108 ''' 109 朴素匹配算法,若主串S中存在和串T值相同的子串,则返回它在主串中第pos个字符之后第一次出现的位置,否则返回-1;不使用串定义的方法来实现 110 ''' 111 len_T = T.StrLength() 112 len_S = self.StrLength() 113 i=pos 114 j=0 115 while(True): 116 if i >= len_S or j >= len_T: 117 break 118 if(self.data[i]==T.data[j]): 119 i=i+1 120 j=j+1 121 else: 122 i=i-j+1 123 j=0 124 125 return i-j if j>=len_T else -1 126 127 def GetNext(self): 128 ''' 129 返回KMP匹配算法所需的next数组 130 ''' 131 len_S=self.StrLength() 132 next=[0] 133 i=1 134 while(True): 135 if i>=len_S: 136 break 137 138 k = next[i-1] 139 while(self.data[k]!=self.data[i] and k!=0): 140 k=next[k-1] 141 if self.data[k]==self.data[i]: 142 next.append(k+1) 143 else: 144 next.append(0) 145 146 i=i+1 147 return next 148 149 def IndexKMP(self, T, pos): 150 ''' 151 KMP匹配算法,若主串S中存在和串T值相同的子串,则返回它在主串中第pos个字符之后第一次出现的位置,否则返回-1;不使用串定义的方法来实现 152 ''' 153 next=self.GetNext() 154 len_T = T.StrLength() 155 len_S = self.StrLength() 156 i=pos 157 j=0 158 while(True): 159 if i >= len_S or j >= len_T: 160 break 161 if(self.data[i]==T.data[j]): 162 i=i+1 163 j=j+1 164 else: 165 i=i+next[i]+1 166 j=0 167 return i-j if j>=len_T else -1 168 169 170 171 def Replace(self, T, V): 172 ''' 173 用串V替换主串S中,出现的所有与串T相等的不重叠的子串 174 ''' 175 string = '' 176 len_S = len(self.data) 177 len_T = len(T.data) 178 p1=p2=0 179 while(True): 180 pos = self.Index(T, p2) 181 if pos == -1: 182 string+=self.data[p2:] 183 break 184 else: 185 p1=pos 186 string+=self.data[p2:p1] 187 string+= V.data 188 p2=p1+len_T 189 190 if string == '': 191 return self.data 192 else: 193 return string 194 195 def StrInsert(self, pos, T): 196 ''' 197 在主串的第pos个字符后,插入串T;pos为负,则逆序插入 198 ''' 199 len_S = len(self.data) 200 if len_S < pos or len_S <abs(pos): 201 return -1 202 203 return self.data[:pos]+T.data+self.data[pos:] 204 205 def StrDelete(self, pos, len_): 206 ''' 207 在主串的第pos个字符后,删除len_长度的字符 208 pos小于0则逆序删除 209 ''' 210 len_S = len(self.data) 211 if pos >= 0: 212 if len_S < pos: 213 return -1 214 return self.data[:pos]+self.data[pos+len_:] 215 else: 216 if len_S < abs(pos) : 217 return -1 218 return self.data[:pos-len_]+self.data[pos:] 219 220 if __name__ == '__main__': 221 from ADTString import ADTString 222 # 打印该类的readme文档 223 print help(ADTString) |
第3行:__all__中定义的内容,是使用from <module> import * 时,会导出的内容。
第15~218行:串的一些基本方法,其中,第86~105行的Index,是使用到串SubString方法来实现的;第107~125行,是使用朴素匹配算法实现的;第149~167行,是使用KMP匹配算法来实现的。
第223行:是打印根据代码和注释,自动生成的参考文档。
下面对这个类进行单元测试,使用unittest模块,代码的最后两行,是执行单元测试的意思。
1 # conding=utf-8 2 3 from ADTString import ADTString 4 import unittest 5 6 class TestADTStringMethods(unittest.TestCase): 7 def setUp(self): 8 self.obj = ADTString() 9 10 def tearDown(self): 11 pass 12 13 def test_StrCopy(self): 14 self.obj.data='' 15 self.assertEqual(self.obj.StrCopy(), '') 16 self.obj.data='goodgoogle' 17 self.assertEqual(self.obj.StrCopy(), 'goodgoogle') 18 self.obj.data='!' 19 self.assertEqual(self.obj.StrCopy(), '!') 20 21 def test_ClearString(self): 22 self.obj.data='goodgoogle' 23 self.obj.ClearString() 24 self.assertEqual(self.obj.data, '') 25 26 def test_StringEmpty(self): 27 self.obj.data='' 28 self.assertEqual(self.obj.data, '') 29 30 def test_StrLength(self): 31 self.obj.data='123' 32 self.assertEqual(self.obj.StrLength(), 3) 33 self.obj.data='' 34 self.assertEqual(self.obj.StrLength(), 0) 35 36 def test_StrCompare(self): 37 obj_T=ADTString('goodgoogle') 38 self.obj.data='goodgoogle' 39 self.assertEqual(self.obj.StrCompare(obj_T),0) 40 self.obj.data='goodgoogl' 41 self.assertEqual(self.obj.StrCompare(obj_T),-1) 42 self.obj.data='goodgooglea' 43 self.assertEqual(self.obj.StrCompare(obj_T),1) 44 45 def test_Concat(self): 46 self.obj.data='good' 47 obj_S2=ADTString('google') 48 self.assertEqual(self.obj.Concat(obj_S2),'goodgoogle') 49 self.obj.data='' 50 self.assertEqual(self.obj.Concat(obj_S2),'google') 51 52 def test_SubString(self): 53 self.obj.data='goodgoogle' 54 self.assertEqual(self.obj.SubString(0,0),'') 55 self.assertEqual(self.obj.SubString(0,1),'g') 56 self.assertEqual(self.obj.SubString(0,4),'good') 57 self.assertEqual(self.obj.SubString(0,100),'goodgoogle') 58 self.assertEqual(self.obj.SubString(100,1),-1) 59 self.assertEqual(self.obj.SubString(-50,0),'') 60 self.assertEqual(self.obj.SubString(-5,0),'') 61 self.assertEqual(self.obj.SubString(-1,0),'') 62 self.assertEqual(self.obj.SubString(-1,1),'') 63 self.assertEqual(self.obj.SubString(-1,2),'') 64 self.assertEqual(self.obj.SubString(-6,1),'g') 65 self.assertEqual(self.obj.SubString(-6,6),'google') 66 self.assertEqual(self.obj.SubString(-6,100),'google') 67 self.assertEqual(self.obj.SubString(-6,10),'google') 68 69 def test_Index(self): 70 self.obj.data='goodgoogle' 71 obj_T=ADTString('good') 72 self.assertEqual(self.obj.Index(obj_T, 0),0) 73 self.assertEqual(self.obj.Index(obj_T, 1),-1) 74 self.obj.data='googlegood' 75 self.assertEqual(self.obj.Index(obj_T, 0),6) 76 self.assertEqual(self.obj.Index(obj_T, 7),-1) 77 self.obj.data='' 78 self.assertEqual(self.obj.Index(obj_T, 0),-1) 79 80 def test_IndexBruteforce(self): 81 self.obj.data='goodgoogle' 82 obj_T=ADTString('good') 83 self.assertEqual(self.obj.Index(obj_T, 0),0) 84 self.assertEqual(self.obj.Index(obj_T, 1),-1) 85 self.obj.data='googlegood' 86 self.assertEqual(self.obj.Index(obj_T, 0),6) 87 self.assertEqual(self.obj.Index(obj_T, 7),-1) 88 self.obj.data='' 89 self.assertEqual(self.obj.Index(obj_T, 0),-1) 90 91 def test_IndexKMP(self): 92 self.obj.data='goodgoogle' 93 obj_T=ADTString('good') 94 self.assertEqual(self.obj.Index(obj_T, 0),0) 95 self.assertEqual(self.obj.Index(obj_T, 1),-1) 96 self.obj.data='googlegood' 97 self.assertEqual(self.obj.Index(obj_T, 0),6) 98 self.assertEqual(self.obj.Index(obj_T, 7),-1) 99 self.obj.data='' 100 self.assertEqual(self.obj.Index(obj_T, 0),-1) 101 102 def test_Replace(self): 103 self.obj.data='good' 104 obj_T=ADTString('good') 105 obj_V=ADTString('replace') 106 self.assertEqual(self.obj.Replace(obj_T, obj_V),'replace') 107 self.obj.data='googlegood' 108 self.assertEqual(self.obj.Replace(obj_T, obj_V),'googlereplace') 109 self.obj.data='goodgooglegood' 110 self.assertEqual(self.obj.Replace(obj_T, obj_V),'replacegooglereplace') 111 self.obj.data='' 112 self.assertEqual(self.obj.Replace(obj_T, obj_V),'') 113 self.obj.data='aaa' 114 self.assertEqual(self.obj.Replace(obj_T, obj_V),'aaa') 115 116 def test_StrInsert(self): 117 self.obj.data='goodgoogle' 118 obj_T=ADTString('insert') 119 self.assertEqual(self.obj.StrInsert(0,obj_T),'insertgoodgoogle') 120 self.assertEqual(self.obj.StrInsert(100,obj_T),-1) 121 self.assertEqual(self.obj.StrInsert(len(self.obj.data),obj_T),'goodgoogleinsert') 122 self.assertEqual(self.obj.StrInsert(4,obj_T),'goodinsertgoogle') 123 self.assertEqual(self.obj.StrInsert(-1,obj_T),'goodgooglinserte') 124 self.assertEqual(self.obj.StrInsert(-100,obj_T),-1) 125 126 def test_StrDelete(self): 127 self.obj.data='goodgoogle' 128 self.assertEqual(self.obj.StrDelete(0,4),'google') 129 self.assertEqual(self.obj.StrDelete(0,100),'') 130 self.assertEqual(self.obj.StrDelete(-1,1),'goodgooge') 131 self.assertEqual(self.obj.StrDelete(-2,3),'goodgle') 132 self.assertEqual(self.obj.StrDelete(-2,100),'le') 133 self.assertEqual(self.obj.StrDelete(-100,1),-1) 134 135 136 suite = unittest.TestLoader().loadTestsFromTestCase(TestADTStringMethods) 137 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] |