1 #!/usr/bin/env python
2 # -*- coding:utf-8 -*-
3 # Author: Minion Xu
4
5 class LinkedListUnderflow(ValueError):
6 pass
7
8 class LNode(object):
9 def __init__(self, elem, next_=None):
10 self.elem = elem
11 self.next = next_
12
13 class LList(object):
14 def __init__(self):
15 self._head = None
16 self._num = 0
17
18 #清楚单链表
19 def clear(self):
20 LList.__init__(self)
21
22 #判断单链表是否为空
23 def is_empty(self):
24 return self._head is None
25
26 #计算单链表元素的个数 两种方式：遍历列表 或 返回 _num
27 def count(self):
28 return self._num
29 """
30 p = self._head
31 num = 0
32 while p:
33 num += 1
34 p = p.next
35 return num
36 """
37 def __len__(self):
38 p = self._head
39 num = 0
40 while p:
41 num += 1
42 p = p.next
43 return num
44
45 #表首端插入元素
46 def prepend(self, elem):
47 self._head = LNode(elem, self._head)
48 self._num += 1
49
50 #删除表首端元素
51 def pop(self):
52 if self._head is None:
53 raise LinkedListUnderflow("in pop")
54 e = self._head.elem
55 self._head = self._head.next
56 self._num -= 1
57 return e
58
59 #表末端插入元素
60 def append(self, elem):
61 if self._head is None:
62 self._head = LNode(elem)
63 self._num += 1
64 return
65 p = self._head
66 while p.next:
67 p = p.next
68 p.next = LNode(elem)
69 self._num += 1
70
71 #删除表末端元素
72 def pop_last(self):
73 if self._head is None:
74 raise LinkedListUnderflow("in pop_last")
75 p = self._head
76 #表中只有一个元素
77 if p.next is None:
78 e = p.elem
79 self._head = None
80 self._num -= 1
81 return e
82 while p.next.next:
83 p = p.next
84 e = p.next.elem
85 p.next = None
86 self._num -= 1
87 return e
88
89 #发现满足条件的第一个表元素
90 def find(self, pred):
91 p = self._head
92 while p:
93 if pred(p.elem):
94 return p.elem
95 p = p.next
96
97 #发现满足条件的所有元素
98 def filter(self, pred):
99 p = self._head
100 while p:
101 if pred(p.elem):
102 yield p.elem
103 p = p.next
104
105 #打印显示
106 def printall(self):
107 p = self._head
108 while p:
109 print(p.elem, end="")
110 if p.next:
111 print(", ",end="")
112 p = p.next
113 print("")
114
115 #查找某个值，列表有的话返回为True，没有的话返回False
116 def search(self, elem):
117 p = self._head
118 foundelem = False
119 while p and not foundelem:
120 if p.elem == elem:
121 foundelem = True
122 else:
123 p = p.next
124 return foundelem
125
126 #找出元素第一次出现时的位置
127 def index(self, elem):
128 p = self._head
129 num = -1
130 found = False
131 while p and not found:
132 num += 1
133 if p.elem == elem:
134 found = True
135 else:
136 p = p.next
137 if found:
138 return num
139 else:
140 raise ValueError("%d is not in the list!" % elem)
141
142 #删除第一个出现的elem
143 def remove(self, elem):
144 p = self._head
145 pre = None
146 while p:
147 if p.elem == elem:
148 if not pre:
149 self._head = p.next
150 else:
151 pre.next = p.next
152 break
153 else:
154 pre = p
155 p = p.next
156 self._num -= 1
157
158 #在指定位置插入值
159 def insert(self, pos, elem):
160 #当值大于count时就默认尾端插入
161 if pos >= self.count():
162 self.append(elem)
163 #其他情况
164 elif 0<=pos<self.count():
165 p = self._head
166 pre = None
167 num = -1
168 while p:
169 num += 1
170 if pos == num:
171 if not pre:
172 self._head = LNode(elem, self._head)
173 self._num += 1
174 else:
175 pre.next = LNode(elem,pre.next)
176 self._num += 1
177 break
178 else:
179 pre = p
180 p = p.next
181 else:
182 raise IndexError
183
184 #删除表中第i个元素
185 def __delitem__(self, key):
186 if key == len(self) - 1:
187 #pop_lasy num自减
188 self.pop_last()
189 elif 0<=key<len(self)-1:
190 p = self._head
191 pre = None
192 num = -1
193 while p:
194 num += 1
195 if num == key:
196 if not pre:
197 self._head = pre.next
198 self._num -= 1
199 else:
200 pre.next = p.next
201 self._num -=1
202 break
203 else:
204 pre = p
205 p = p.next
206 else:
207 raise IndexError
208
209 #根据索引获得该位置的元素
210 def __getitem__(self, key):
211 if not isinstance(key, int):
212 raise TypeError
213 if 0<=key<len(self):
214 p = self._head
215 num = -1
216 while p:
217 num += 1
218 if key == num:
219 return p.elem
220 else:
221 p = p.next
222 else:
223 raise IndexError
224
225 # ==
226 def __eq__(self, other):
227 #两个都为空列表 则相等
228 if len(self)==0 and len(other)==0:
229 return True
230 #两个列表元素个数相等 当每个元素都相等的情况下 两个列表相等
231 elif len(self) == len(other):
232 for i in range(len(self)):
233 if self[i] == other[i]:
234 pass
235 else:
236 return False
237 #全部遍历完后则两个列表相等
238 return True
239 #两个列表元素个数不相等 返回Fasle
240 else:
241 return False
242 # !=
243 def __ne__(self, other):
244 if self.__eq__(other):
245 return False
246 else:
247 return True
248 # >
249 def __gt__(self, other):
250 l1 = len(self)
251 l2 = len(other)
252 if not isinstance(other, LList):
253 raise TypeError
254 # 1.len(self) = len(other)
255 if l1 == l2:
256 for i in range(l1):
257 if self[i] == other[i]:
258 continue
259 elif self[i] < other[i]:
260 return False
261 else:
262 return True
263 #遍历完都相等的话说明两个列表相等 所以返回False
264 return False
265 # 2.len(self) > len(other)
266 if l1 > l2:
267 for i in range(l2):
268 if self[i] == other[i]:
269 continue
270 elif self[i] < other[i]:
271 return False
272 else:
273 return True
274 #遍历完后前面的元素全部相等 则列表个数多的一方大
275 #if self[l2-1] == other[l2-1]:
276 return True
277 # 3.len(self) < len(other)
278 if l1 < l2:
279 for i in range(l1):
280 if self[i] == other[i]:
281 continue
282 elif self[i] < other[i]:
283 return False
284 else:
285 return True
286 #遍历完后前面的元素全部相等 则列表个数多的一方大
287 #if self[l2-1] == other[l2-1]:
288 return False
289 # <
290 def __lt__(self, other):
291 #列表相等情况下>会返回False,则<这里判断会返回True,有错误.所以要考虑在==的情况下也为False
292 if self.__gt__(other) or self.__eq__(other):
293 return False
294 else:
295 return True
296 # >=
297 def __ge__(self, other):
298 """
299 if self.__eq__(other) or self.__gt__(other):
300 return True
301 else:
302 return False
303 """
304 #大于等于和小于是完全相反的，所以可以依靠小于实现
305 if self.__lt__(other):
306 return False
307 else:
308 return True
309 # <=
310 def __le__(self, other):
311 """
312 if self.__eq__(other) or self.__lt__(other):
313 return True
314 else:
315 return False
316 """
317 ##小于等于和大于是完全相反的，所以可以依靠大于实现
318 if self.__gt__(other):
319 return False
320 else:
321 return True
322
323
324 #example 大于5返回True的函数
325 def greater_5(n):
326 if n>5:
327 return True
328
329 if __name__=="__main__":
330 mlist1 = LList()
331 mlist2 = LList()
332 mlist1.append(1)
333 mlist2.append(1)
334 mlist1.append(2)
335 mlist2.append(2)
336 #mlist1.append(2)
337 mlist2.append(6)
338 mlist2.append(11)
339 mlist2.append(12)
340 mlist2.append(14)
341 mlist1.printall()
342 mlist2.printall()
343 #print(mlist1 == mlist2)
344 #print(mlist1 != mlist2)
345 print(mlist1 <= mlist2)
346
347 mlist2.del_if(greater_5)
348 mlist2.printall()
349
350 """
351 llist1 = LNode(1)
352 p = llist1
353 for i in range(2,11):
354 p.next = LNode(i)
355 p = p.next
356
357 p = llist1
358 while p is not None:
359 print(p.elem, end=" ")
360 p = p.next
361 print("\n=====")
362
363 mlist1 = LList()
364 for i in range(10):
365 mlist1.prepend(i)
366 for i in range(11,20):
367 mlist1.append(i)
368 mlist1.printall()
369
370
371
372 mlist1.pop()
373 mlist1.printall()
374
375 mlist1.pop_last()
376 mlist1.printall()
377
378 print("===")
379 print(mlist1.search(18))
380
381 print(mlist1.index(18))
382
383 mlist1.remove(0)
384 mlist1.printall()
385
386 mlist1.insert(1,20)
387 mlist1.printall()
388
389 del(mlist1[2])
390 mlist1.printall()
391
392 print(mlist1.count())
393
394 print(mlist1.count()) -
395 print(len(mlist1))
396 print(mlist1.find(greater_5))
397 for i in mlist1.filter(greater_5):
398 print(i, end=",")
399 """