数据结构:单链表结构字符串,python版
1 #!/urs/bin/env python 2 # -*- coding:utf-8 -*- 3 4 #异常类 5 class stringTypeError(TypeError): 6 pass 7 8 #节点类 9 class Node(object): 10 def __init__(self, elem, next_ = None): 11 self.elem = elem 12 self.next = next_ 13 #单链表类 14 class single_list(object): 15 def __init__(self): 16 self._head = None 17 self._num = 0 18 19 def __len__(self): 20 return self._num 21 22 def prepend(self,elem): 23 self._head = Node(elem, self._head) 24 self._num += 1 25 26 def append(self,elem): 27 if self._head is None: 28 self._head = Node(elem) 29 self._num += 1 30 return 31 p = self._head 32 while p.next: 33 p = p.next 34 p.next = Node(elem) 35 self._num += 1 36 37 def pop_last(self): 38 if self._head is None: 39 raise ValueError("in pop_last") 40 p = self._head 41 if p.next is None: 42 e = p.elem 43 self._head = None 44 self._num -= 1 45 return e 46 while p.next.next: 47 p = p.next 48 e = p.next.elem 49 p.next = None 50 self._num -= 1 51 return e 52 53 def delitem(self, key): 54 if key == len(self)-1: 55 self.pop_last() 56 elif 0<= key < len(self) - 1: 57 p = self._head 58 pre = None 59 num = -1 60 while p is not None: 61 num += 1 62 if key==num: 63 if not pre: 64 self._head = p.next 65 self._num -= 1 66 else: 67 pre.next = p.next 68 self._num -= 1 69 break 70 else: 71 pre = p 72 p = p.next 73 else: 74 raise IndexError 75 76 def insert(self, key, elem): 77 if key>=len(self)-1: 78 self.append(elem) 79 elif 0<=key<len(self)-1: 80 p = self._head 81 pre = None 82 num = -1 83 while p: 84 num += 1 85 if num==key: 86 if not pre: 87 self._head = Node(elem, self._head) 88 self._num += 1 89 else: 90 pre.next = Node(elem, pre.next) 91 self._num += 1 92 break 93 else: 94 pre = p 95 p = p.next 96 else: 97 raise IndexError 98 99 # 打印显示 100 def printall(self): 101 p = self._head 102 while p: 103 print(p.elem, end="") 104 if p.next: 105 print(", ", end="") 106 p = p.next 107 print("") 108 109 110 #单链表字符串类 111 class string(single_list): 112 def __init__(self, value): 113 self.value = str(value) 114 single_list.__init__(self) 115 for i in range(len(self.value)-1,-1,-1): 116 self.prepend(self.value[i]) 117 118 def length(self): 119 return self._num 120 121 def printall(self): 122 p = self._head 123 print("字符串结构:",end="") 124 while p: 125 print(p.elem, end="") 126 if p.next: 127 print("-->", end="") 128 p = p.next 129 print("") 130 131 #朴素的串匹配算法,返回匹配的起始位置 132 def naive_matching(self, p): #self为目标字符串,t为要查找的字符串 133 if not isinstance(self, string) and not isinstance(p, string): 134 raise stringTypeError 135 m, n = p.length(), self.length() 136 i, j = 0, 0 137 while i < m and j < n: 138 if p.value[i] == self.value[j]:#字符相同,考虑下一对字符 139 i, j = i+1, j+1 140 else: #字符不同,考虑t中下一个位置 141 i, j = 0, j-i+1 142 if i == m: #i==m说明找到匹配,返回其下标 143 return j-i 144 return -1 145 146 #kmp匹配算法,返回匹配的起始位置 147 def matching_KMP(self, p): 148 j, i = 0, 0 149 n, m = self.length(), p.length() 150 while j < n and i < m: 151 if i == -1 or self.value[j] == p.value[i]: 152 j, i = j + 1, i + 1 153 else: 154 i = string.gen_next(p)[i] 155 if i == m: 156 return j - i 157 return -1 158 159 # 生成pnext表 160 @staticmethod 161 def gen_next(p): 162 i, k, m = 0, -1, p.length() 163 pnext = [-1] * m 164 while i < m - 1: 165 if k == -1 or p.value[i] == p.value[k]: 166 i, k = i + 1, k + 1 167 pnext[i] = k 168 else: 169 k = pnext[k] 170 return pnext 171 172 #把old字符串出现的位置换成new字符串 173 def replace(self, old, new): 174 if not isinstance(self, string) and not isinstance(old, string) \ 175 and not isinstance(new, string): 176 raise stringTypeError 177 178 #删除匹配的旧字符串 179 start = self.matching_KMP(old) 180 for i in range(old.length()): 181 self.delitem(start) 182 #末尾情况下时append追加的,顺序为正;而前面的地方插入为前插;所以要分情况 183 if start<self.length(): 184 for i in range(new.length()-1, -1, -1): 185 self.insert(start,new.value[i]) 186 else: 187 for i in range(new.length()): 188 self.insert(start,new.value[i]) 189 190 191 if __name__=="__main__": 192 193 a = string("abcda") 194 print("字符串长度:",a.length()) 195 a.printall() 196 b = string("abcabaabcdabdabcda") 197 print("字符串长度:", b.length()) 198 b.printall() 199 print("朴素算法_匹配的起始位置:",b.naive_matching(a),end=" ") 200 print("KMP算法_匹配的起始位置:",b.matching_KMP(a)) 201 c = string("xu") 202 print("==") 203 b.replace(a,c) 204 print("替换后的字符串是:") 205 b.printall()
今天早上在继续实现replace时,发现一个严重的问题。在我初始化字符串string对象时,使用了self.value = str(value),而我在后面使用匹配算法时,无论是朴素匹配还是KMP匹配
都使用的对象的value值作为比较。所以对象实现replace方法后的start =b.mathcing_KMP(a)后依旧不变,会一直为6.原因在于我使用的是self.value在进行匹配。所以replace后的
链表字符串里的值并没有被利用到,从而发生严重的错误。
改进篇见下一篇博客