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 =http://www.mamicode.com/ 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     #获取字符串对象值的列表，方便下面使用
122     def get_value_list(self):
123         l = []
124         p = self._head
125         while p:
126             l.append(p.elem)
127             p = p.next
128         return l
129 
130     def printall(self):
131         p = self._head
132         print("字符串结构：",end="")
133         while p:
134             print(p.elem, end="")
135             if p.next:
136                 print("-->", end="")
137             p = p.next
138         print("")
139 
140     #朴素的串匹配算法，返回匹配的起始位置
141     def naive_matching(self, p):  #self为目标字符串，t为要查找的字符串
142         if not isinstance(self, string) and not isinstance(p, string):
143             raise stringTypeError
144         m, n = p.length(), self.length()
145         i, j = 0, 0
146         while i < m and j < n:
147             if p.get_value_list()[i] == self.get_value_list()[j]:#字符相同，考虑下一对字符
148                 i, j = i+1, j+1
149             else:               #字符不同，考虑t中下一个位置
150                 i, j = 0, j-i+1
151         if i == m:              #i==m说明找到匹配,返回其下标
152             return j-i
153         return -1
154 
155     #kmp匹配算法，返回匹配的起始位置
156     def matching_KMP(self, p):
157         j, i = 0, 0
158         n, m = self.length(), p.length()
159         while j < n and i < m:
160             if i == -1 or self.get_value_list()[j] == p.get_value_list()[i]:
161                 j, i = j + 1, i + 1
162             else:
163                 i = string.gen_next(p)[i]
164         if i == m:
165             return j - i
166         return -1
167 
168     # 生成pnext表
169     @staticmethod
170     def gen_next(p):
171         i, k, m = 0, -1, p.length()
172         pnext = [-1] * m
173         while i < m - 1:
174             if k == -1 or p.get_value_list()[i] == p.get_value_list()[k]:
175                 i, k = i + 1, k + 1
176                 pnext[i] = k
177             else:
178                 k = pnext[k]
179         return pnext
180 
181     #把old字符串出现的位置换成new字符串
182     def replace(self, old, new):
183         if not isinstance(self, string) and not isinstance(old, string) 184                 and not isinstance(new, string):
185             raise stringTypeError
186 
187         while self.matching_KMP(old) >= 0:
188             #删除匹配的旧字符串
189             start = self.matching_KMP(old)
190             print("依次发现的位置:",start)
191             for i in range(old.length()):
192                 self.delitem(start)
193             #末尾情况下时append追加的，顺序为正；而前面的地方插入为前插；所以要分情况
194             if start<self.length():
195                 for i in range(new.length()-1, -1, -1):
196                     self.insert(start,new.value[i])
197             else:
198                 for i in range(new.length()):
199                     self.insert(start,new.value[i])
200     
201     #self字符串里第一个属于字符串another的字符所在结点的位置
202     def find_in(self, another):
203         if not isinstance(self, string) and not isinstance(another, string):
204             raise  TypeError
205         for i in range(self.length()):
206             if self.get_value_list()[i] in another.get_value_list():
207                 return i
208         return -1  #没有发现
209 
210     # self字符串里第一个不属于字符串another的字符所在结点的位置
211     def find_not_in(self, another):
212         if not isinstance(self, string) and not isinstance(another, string):
213             raise  TypeError
214         for i in range(self.length()):
215             if self.get_value_list()[i] not in another.get_value_list():
216                 return i
217         return -1  #没有发现
218 
219     #从self里删除串another里的字符
220     def remove(self, another):
221         if not isinstance(self, string) and not isinstance(another, string):
222             raise  TypeError
223         while self.find_in(another)>=0:
224             self.delitem(self.find_in(another))
225 
226 if __name__=="__main__":
227 
228     a = string("aba")
229     print("字符串长度：",a.length())
230     a.printall()
231     b = string("abaaaabadaba")
232     print("字符串长度：", b.length())
233     b.printall()
234     print("朴素算法_匹配的起始位置：",b.naive_matching(a),end=" ")
235     print("KMP算法_匹配的起始位置：",b.matching_KMP(a))
236     c = string("xu")
237     print("==")
238     b.replace(a,c)
239     print("替换后的字符串是：")
240     b.printall()
241     print(b.get_value_list())
242     d = string("dfga")
243     print("第一个属于another字符的位置：",b.find_in(d))
244     e = string("ad")
245     print("第一个不属于another字符的位置：", b.find_not_in(e))
246     b.remove(e)
247     b.printall()