上QQ阅读APP看书，第一时间看更新
4.2.2 实践演练——实现完整链表操作
下面的实例文件wanlian.py演示了完整实现链表并进行操作测试的过程。文件wanlian.py的主要实现代码如下所示。
源码路径：daima\第4章\wanlian.py
#清除单链表
def clear(self):
LList.__init__(self)
#判断单链表是否为空
def is_empty(self):
return self._head is None
#计算单链表元素的个数，有两种方式：遍历列表或返回_num
def count(self):
return self._num
"""
p = self._head
num = 0
while p:
num += 1
p = p.next
return num
"""
def __len__(self):
p = self._head
num = 0
while p:
num += 1
p = p.next
return num
#在表首端插入元素
def prepend(self, elem):
self._head = LNode(elem, self._head)
self._num += 1
#删除表首端元素
def pop(self):
if self._head is None:
raise LinkedListUnderflow("in pop")
e = self._head.elem
self._head = self._head.next
self._num -= 1
return e
#在表末端插入元素
def append(self, elem):
if self._head is None:
self._head = LNode(elem)
self._num += 1
return
p = self._head
while p.next:
p = p.next
p.next = LNode(elem)
self._num += 1
#删除表末端元素
def pop_last(self):
if self._head is None:
raise LinkedListUnderflow("in pop_last")
p = self._head
#表中只有一个元素
if p.next is None:
e = p.elem
self._head = None
self._num -= 1
return e
while p.next.next:
p = p.next
e = p.next.elem
p.next = None
self._num -= 1
return e
#发现满足条件的第一个表元素
def find(self, pred):
p = self._head
while p:
if pred(p.elem):
return p.elem
p = p.next
#发现满足条件的所有元素
def filter(self, pred):
p = self._head
while p:
if pred(p.elem):
yield p.elem
p = p.next
#显示
def printall(self):
p = self._head
while p:
print(p.elem, end="")
if p.next:
print(", ",end="")
p = p.next
print("")
#查找某个值，列表有的话，返回True，没有的话返回False
def search(self, elem):
p = self._head
foundelem = False
while p and not foundelem:
if p.elem == elem:
foundelem = True
else:
p = p.next
return foundelem
#找出元素第一次出现时的位置
def index(self, elem):
p = self._head
num = -1
found = False
while p and not found:
num += 1
if p.elem == elem:
found = True
else:
p = p.next
if found:
return num
else:
raise ValueError("%d is not in the list!" % elem)
#删除第一个出现的elem
def remove(self, elem):
p = self._head
pre = None
while p:
if p.elem == elem:
if not pre:
self._head = p.next
else:
pre.next = p.next
break
else:
pre = p
p = p.next
self._num -= 1
#在指定位置插入值
def insert(self, pos, elem):
#当值大于count时默认在尾端插入
if pos >= self.count():
self.append(elem)
#其他情况
elif 0<=pos<self.count():
p = self._head
pre = None
num = -1
while p:
num += 1
if pos == num:
if not pre:
self._head = LNode(elem, self._head)
self._num += 1
else:
pre.next = LNode(elem,pre.next)
self._num += 1
break
else:
pre = p
p = p.next
else:
raise IndexError
#删除表中的第i个元素
def __delitem__(self, key):
if key == len(self) - 1:
#pop_lasy num自减
self.pop_last()
elif 0<=key<len(self)-1:
p = self._head
pre = None
num = -1
while p:
num += 1
if num == key:
if not pre:
self._head = pre.next
self._num -= 1
else:
pre.next = p.next
self._num -=1
break
else:
pre = p
p = p.next
else:
raise IndexError
#根据索引获得该位置的元素
def __getitem__(self, key):
if not isinstance(key, int):
raise TypeError
if 0<=key<len(self):
p = self._head
num = -1
while p:
num += 1
if key == num:
return p.elem
else:
p = p.next
else:
raise IndexError
# ==
def __eq__(self, other):
#两个都为空列表，则相等
if len(self)==0 and len(other)==0:
return True
#两个列表的元素个数相等，在每个元素都相等的情况下，两个列表相等
elif len(self) == len(other):
for i in range(len(self)):
if self[i] == other[i]:
pass
else:
return False
#全部遍历完后，两个列表相等
return True
#两个列表的元素个数不相等，返回Fasle
else:
return False
# !=
def __ne__(self, other):
if self.__eq__(other):
return False
else:
return True
# >
def __gt__(self, other):
l1 = len(self)
l2 = len(other)
if not isinstance(other, LList):
raise TypeError
# 1.len(self) = len(other)
if l1 == l2:
for i in range(l1):
if self[i] == other[i]:
continue
elif self[i] < other[i]:
return False
else:
return True
#遍历完都相等的话，说明两个列表相等，所以返回False
return False
# 2.len(self) > len(other)
if l1 > l2:
for i in range(l2):
if self[i] == other[i]:
continue
elif self[i] < other[i]:
return False
else:
return True
#遍历完毕，前面的元素全部相等，则列表中元素个数多的一方大
#if self[l2-1] == other[l2-1]:
return True
# 3.len(self) < len(other)
if l1 < l2:
for i in range(l1):
if self[i] == other[i]:
continue
elif self[i] < other[i]:
return False
else:
return True
#遍历完毕，前面的元素全部相等，则列表中元素个数多的一方大
#if self[l2-1] == other[l2-1]:
return False
# <
def __lt__(self, other):
#列表相等情况下，>会返回False，<在这里的判断会返回True，有错误。所以要考虑在相等的情况下也为False
if self.__gt__(other) or self.__eq__(other):
return False
else:
return True
# >=
def __ge__(self, other):
"""
if self.__eq__(other) or self.__gt__(other):
return True
else:
return False
"""
#大于或等于和小于是完全相反的，所以可以依靠小于实现
if self.__lt__(other):
return False
else:
return True
# <=
def __le__(self, other):
"""
if self.__eq__(other) or self.__lt__(other):
return True
else:
return False
"""
##小于或等于和大于是完全相反的，所以可以依靠大于实现
if self.__gt__(other):
return False
else:
return True
#example，大于5返回True的函数
def greater_5(n):
if n>5:
return True
if __name__=="__main__":
mlist1 = LList()
mlist2 = LList()
mlist1.append(1)
mlist2.append(1)
mlist1.append(2)
mlist2.append(2)
#mlist1.append(2)
mlist2.append(6)
mlist2.append(11)
mlist2.append(12)
mlist2.append(14)
mlist1.printall()
mlist2.printall()
#print(mlist1 == mlist2)
#print(mlist1 != mlist2)
print(mlist1 <= mlist2)
mlist2.__delitem__(2)
mlist2.printall()
执行后会输出：
1, 2 1, 2, 6, 11, 12, 14 True 1, 2, 11, 12, 14