前提知识点
本文以准备以“链表类”为例，一步步深入了解学习“类”的各种功能实现。关于链表的概念定义略，详见上一篇文章的介绍： 链接地址点这里快速到达
一个最基础的节点类
就一个初始化方法 __init__()，定义一个节点类
三个属性： 其中，val和value是等价的，表示节点存储的数据； next 表示指针，指向下一节点。
class Node(): def __init__(self, value=None, Next=None): self.val = self.value = value self.next = Next ''' # 测试： >>> node = Node(1) >>> node.next = Node(2) >>> node.val 1 >>> node.value 1 >>> node.next.val 2 >>> >>> node = Node(1, Node(2)) >>> node.val 1 >>> node.next.value 2 >>> '''
进一步尝试其他操作：
>>> node = Node() >>> help(Node) Help on class Node in module __main__: class Node(builtins.object) | Node(value=None, Next=None) | | Methods defined here: | | __init__(self, value=None, Next=None) | Initialize self. See help(type(self)) for accurate signature. | | ---------------------------------------------------------------------- | Data descriptors defined here: | | __dict__ | dictionary for instance variables (if defined) | | __weakref__ | list of weak references to the object (if defined) >>> node <__main__.Node object at 0x00375B68> >>> node.__doc__ >>> node.__dict__ {'val': None, 'value': None, 'next': None} >>> node = Node(1,Node(2)) >>> node.__dict__ {'val': 1, 'value': 1, 'next': <__main__.Node object at 0x00375BB0>}
类的方法定义、数据描述符定义等就一两项，说明文档也为空。但就这么简单的类，已经可以用它解决实际问题了，来举个简单的例子：
将两个有序链表(升序)合并为一个新的有序链表并返回。
List1: 1->2>4->8 List2: 1->3->3->5->5
把可以反复利用的代码，新写两个函数拓展到这个类里：除了主要功能合并方法外，另写一个便于检查是否正确的遍历方法。
拓展一： 新增方法
>>> class Node(): def __init__(self, value=None, Next=None): self.val = self.value = value self.next = Next def merge(self, node): ret = cur = Node() while self is not None and node is not None: if self.val < node.val: cur.next = self self = self.next else: cur.next = node node = node.next cur = cur.next cur.next = self or node return ret.next def travel(self): ret,cur = [],self while cur is not None: ret.append(cur.val) cur = cur.next return ret
测试结果：
>>> NodeList1 = Node(1,Node(2,Node(4,Node(8)))) >>> NodeList2 = Node(1,Node(3,Node(3,Node(5,Node(5))))) >>> NodeList1.travel() [1, 2, 4, 8] >>> NodeList2.travel() [1, 3, 3, 5, 5] >>> NodeList = NodeList1.merge(NodeList2) >>> NodeList.travel() [1, 1, 2, 3, 3, 4, 5, 5, 8] >>>
经测试，完全正确！
拓展二：魔法方法
先看一下，自定义节点类与内置list列表类的对比结果：
>>> l = list([1,2,3]) >>> len(l) 3 >>> str(l) '[1, 2, 3]' >>> l [1, 2, 3] >>> type(l) <class 'list'> >>> type(l) is list True >>> >>> n = Node(1,Node(2,Node(3))) >>> len(n) Traceback (most recent call last): File "<pyshell#82>", line 1, in <module> len(n) TypeError: object of type 'Node' has no len() >>> str(n) '<__main__.Node object at 0x0000000002CD28B0>' >>> n '<__main__.Node object at 0x0000000002CD28B0>' >>> type(n) <class '__main__.Node'> >>> type(n) is Node True >>>
肯定败下阵来，看来需要请出__len__, __str__, __repr__等这些标准的类内置方法（命名两头均是双下划线，是类内置的内部方法，这种特殊方法也被称为“魔法方法”），来模拟一下内置类可以被len(), 被str()的功能。同时去掉merge方法，travel改名为values，重写原travel，最后新增全局变量__doc__，__version__，__all__等用于返回信息。
class Node(): '''class Node of Singlelinked List''' __version__ = '1.0.0' __all__ = ['size','travel','values','__version__'] def __init__(self, value=None, Next=None): self.val = self.value = value self.next = Next def __repr__(self): return f'Node({self.val}->{self.next})' def __str__(self): return f'{self.val}->{self.next}' def __len__(self): if self.val is None: return 0 size,cur = 0,self while cur is not None: size += 1 cur = cur.next return size def __add__(self, other): if self.val is None: self = other return self cur = self while cur.next is not None: cur = cur.next cur.next = other self.next = cur return self def values(self): ret,cur = [],self while cur is not None: ret.append(cur.val) cur = cur.next return ret def travel(self): ret = self.__str__() return ret[:-6] def size(self): return self.__len__()
测试结果：
>>> n = Node(1,Node(2,Node(3))) >>> n.__all__ ['size', 'travel', 'values', '__version__'] >>> n.__doc__ 'class Node of Singlelinked List' >>> n.__version__ '1.0.0' >>> n.__dict__ {'val': 1, 'value': 1, 'next': Node(2->3->None)} >>> n.size() 3 >>> len(n) 3 >>> n.__len__() # 就是用来被len()调用的，一般情况不会使用内部方法 3 >>> str(n) '1->2->3->None' >>> n.__str__() # 就是用来被str()调用的，一般情况不会使用内部方法 '1->2->3->None' >>> repr(n) 'Node(1->2->3->None)' >>> n.__repr__() # 就是用来被repr()调用的，一般情况不会使用内部方法 'Node(1->2->3->None)' >>> n # 变量本身也是repr的结果，但输出时没有引号 Node(1->2->3->None) >>> n.travel() '1->2->3' >>> n.values() [1, 2, 3] >>>
是不是很赞？ 魔法方法不仅仅只有这几个基本的，它共有八大类好几十种呢。它的本质就是用来实现重载对象的方法，可以用于重载算术运算、逻辑比较、类型转换、容器迭代等。
注：这个类里的__repr__、__str__是以递归实现的，与python允许的最大值递归深度有关，大概340个元素以上的会报错。但 .values .travel用遍历得来，不受影响。
拓展三：重载比较运算符
以比较运算（＞、＜、==）为例，先看一下未重载之前的效果：
>>> a,b=Node(1,Node(2,Node(3))),Node(1,Node(2,Node(3))) >>> a==b False >>> a>b Traceback (most recent call last): File "<pyshell#123>", line 1, in <module> a>b TypeError: '>' not supported between instances of 'Node' and 'Node' >>> a<b Traceback (most recent call last): File "<pyshell#124>", line 1, in <module> a<b TypeError: '<' not supported between instances of 'Node' and 'Node' >>>
结果：大于或小于没法用，等于么即便是两条节点链(多个节点相接而成)的所有节点都一一相等也返回False。
重载时比较运算（＞、＜、==）分别对应（__gt__、__lt__、__nq__），各是： greater than, less than, equal to 的意思。重载约定，两个节点链哪个节点数多就哪个大，节点数一样时每个节点值都相等为“==全等”，代码如下：
class Node(): '''class Node of Singlelinked List''' __version__ = '1.0.0' __all__ = ['size','travel','values','__version__'] def __init__(self, value=None, Next=None): self.val = self.value = value self.next = Next def __repr__(self): return f'Node({self.val}->{self.next})' def __str__(self): return f'{self.val}->{self.next}' def __len__(self): if self.val is None: return 0 size,cur = 0,self while cur is not None: size += 1 cur = cur.next return size def __gt__(self, other): if len(self)>len(other): return True else: return False def __lt__(self, other): if len(self)<len(other): return True else: return False def __eq__(self, other): cur1,cur2 = self,other if len(cur1)!=len(cur2): return False while cur1 is not None: if cur1.val!=cur2.val: return False cur1 = cur1.next cur2 = cur2.next else: return True def values(self): ret,cur = [],self while cur is not None: ret.append(cur.val) cur = cur.next return ret def travel(self): ret = self.__str__() return ret[:-6] def size(self): return self.__len__()
测试效果：
>>> a,b = Node(1,Node(2,Node(3))), Node(1,Node(2,Node(3))) >>> a == b True >>> a > b False >>> a < b False >>> >>> a,b = Node(1,Node(2,Node(3))), Node(3,Node(2)) >>> a > b True >>> a < b False >>> a == b False >>> b > a False >>> b < a True >>>
已完美达到预期效果！
拓展四：属性装饰器
用类属性装饰器@property标注类方法，能使类的方法变为只读属性。以下代码把values()方法和另一个与size()方法相同功能的length()方法转变成两个属性： values和length：
class Node(): '''class Node of Singlelinked List''' __version__ = '1.0.0' __all__ = ['length','value','values','cat','size','travel','__version__'] def __init__(self, value=None, Next=None): self.val = self.value = value self.next = Next def __repr__(self): return f'Node({self.val}->{self.next})' def __str__(self): return f'{self.val}->{self.next}' def __len__(self): if self.val is None: return 0 size,cur = 0,self while cur is not None: size += 1 cur = cur.next return size def __gt__(self, other): if len(self)>len(other): return True else: return False def __lt__(self, other): if len(self)<len(other): return True else: return False def __eq__(self, other): cur1,cur2 = self,other if len(cur1)!=len(cur2): return False while cur1 is not None: if cur1.val!=cur2.val: return False cur1 = cur1.next cur2 = cur2.next else: return True @property def values(self): ret,cur = [],self while cur is not None: ret.append(cur.val) cur = cur.next return ret def travel(self): ret = self.__str__() return ret[:-6] def size(self): return self.__len__() @property def length(self): return self.__len__()
测试结果：
>>> a,b = Node(1,Node(2,Node(3))),Node(4,Node(5)) >>> a.length 3 >>> a.values [1, 2, 3] >>> b.length 2 >>> b.values [4, 5] >> >>> b.next.next = a >>> b Node(4->5->1->2->3->None) >>> b.length 5 >>> b.values [4, 5, 1, 2, 3] >>>
一个节点类的代码基本成型了，此时类的帮助返回如下：
>>> help(Node) Help on class Node in module __main__: class Node(builtins.object) | Node(value=None, Next=None) | | class Node of Singlelinked List | | Methods defined here: | | __eq__(self, other) | Return self==value. | | __gt__(self, other) | Return self>value. | | __init__(self, value=None, Next=None) | Initialize self. See help(type(self)) for accurate signature. | | __len__(self) | | __lt__(self, other) | Return self<value. | | __repr__(self) | Return repr(self). | | __str__(self) | Return str(self). | | size(self) | | travel(self) | | ---------------------------------------------------------------------- | Readonly properties defined here: | | length | | values | | ---------------------------------------------------------------------- | Data descriptors defined here: | | __dict__ | dictionary for instance variables (if defined) | | __weakref__ | list of weak references to the object (if defined) | | ---------------------------------------------------------------------- | Data and other attributes defined here: | | __all__ = ['length', 'value', 'values', 'size', 'travel', '__version__... | | __hash__ = None >>> >>> Node.__all__ ['length', 'value', 'values', 'size', 'travel', '__version__'] >>> dir(Node) ['__add__', '__all__', '__class__', '__delattr__', '__dict__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__gt__', '__hash__', '__init__', '__init_subclass__', '__le__', '__len__', '__lt__', '__module__', '__ne__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__setattr__', '__sizeof__', '__str__', '__subclasshook__', '__version__', '__weakref__', 'cat', 'length', 'size', 'travel', 'values'] >>>
拓展五：创建节点链方法
增加新增、追加、创建等方法，方便节点的赋值，没有设置这些方法时赋值也要写代码，如：
>>> n = Node(1) >>> t = n >>> for i in range(2,10): t.next = Node(i) t = t.next print(n) 1->2->None 1->2->3->None 1->2->3->4->None 1->2->3->4->5->None 1->2->3->4->5->6->None 1->2->3->4->5->6->7->None 1->2->3->4->5->6->7->8->None 1->2->3->4->5->6->7->8->9->None >>> >>> >>> n = Node(9) >>> for i in reversed(range(1,9)): n = Node(i, n) print(n) 8->9->None 7->8->9->None 6->7->8->9->None 5->6->7->8->9->None 4->5->6->7->8->9->None 3->4->5->6->7->8->9->None 2->3->4->5->6->7->8->9->None 1->2->3->4->5->6->7->8->9->None
有了以上经验，添加push,append,cat三个方法和一个函数build()，代码如下：
class Node(): '''class Node of Singlelinked List''' __version__ = '1.0.1' __all__ = ['length','value','values', 'push','append','cat', 'build', 'size','travel','__version__'] def __init__(self, value=None, Next=None): self.val = self.value = value self.next = Next def __repr__(self): return f'Node({self.val}->{self.next})' def __str__(self): return f'{self.val}->{self.next}' def __len__(self): if self.val is None: return 0 size,cur = 0,self while cur is not None: size += 1 cur = cur.next return size def __gt__(self, other): if len(self)>len(other): return True else: return False def __lt__(self, other): if len(self)<len(other): return True else: return False def __eq__(self, other): cur1,cur2 = self,other if type(cur1) is not Node: return False if type(cur2) is not Node: return False if len(cur1)!=len(cur2): return False while cur1 is not None: if cur1.val!=cur2.val: return False cur1 = cur1.next cur2 = cur2.next else: return True @property def values(self): ret,cur = [],self while cur: ret.append(cur.val) cur = cur.next return ret def travel(self): ret = self.__str__() return ret[:-6] def size(self): return self.__len__() @property def length(self): return self.__len__() def append(self, value): '''在尾节点后追加数据或节点，数据允许为可迭代对象''' if self.val is None: self = Node.build(value) return self node = self while node.next: node = node.next if type(value) is Node: node.next = value else: tmp = Node.build(value) node.next = tmp return self def push(self, value): '''在头节点前插入数据或节点，数据允许为可迭代对象''' tmp = Node(self.val,self.next) if type(value) is Node: ret = Node(value.val,value.next) else: ret = Node.build(value) if tmp.val: ret.append(tmp) self.val,self.next = ret.val,ret.next return self def cat(self, other, flag=True): '''节点拼接，默认为追加，flag=Flase时插在头节点前''' tmp = Node.build(other) if flag: ret = Node.build(self.values+tmp.values) else: ret = Node.build(tmp.values+self.values) self.val,self.next = ret.val,ret.next return self def build(*data): '''多参数创建节点链，参数允许为可迭代对象''' values = [] for d in data: if hasattr(d,'__iter__'): for i in d: values.append(i) elif type(d) is Node: values.extend(d.values) else: values.append(d) cur = Node(values[-1]) for value in values[:-1][::-1]: cur = Node(value, cur) return cur
其中build()允许多参数输入；其它三个方法均允许可迭代对象作参数：
>>> node = Node.build(range(1,5),5,(6,7),[8]) >>> node Node(1->2->3->4->5->6->7->8->None) >>> a = Node.build(1,2,3) >>> b = Node.build(4,5) >>> a.cat(b) Node(1->2->3->4->5->None) >>> a.cat(b,flag=False) Node(4->5->1->2->3->4->5->None) >>> a = Node.build(1,2,3) >>> a.append(4) Node(1->2->3->4->None) >>> a.append(range(5,8)) Node(1->2->3->4->5->6->7->None) >>> a.append([8,9]) Node(1->2->3->4->5->6->7->8->9->None) >>> a = Node.build(1,2,3) >>> a.push(4) Node(4->1->2->3->None) >>> a.push(range(5,8)) Node(5->6->7->4->1->2->3->None) >>> a.push([8,9]) Node(8->9->5->6->7->4->1->2->3->None) >>>
有了拼接的方法，就可以尝试一下加法和乘法的重载——
拓展六：重载算术运算符
重载的约定：加法为两个节点的链的拼接；乘法为数乘，即一个节点链与一个正整数n相乘等价于反复n次相接，与0乘则为清空。乘法要注意分左乘和右乘，没有右乘方法整数在左边运算时会出错，代码如下放到拓展五中代码中即可：
def __add__(self, other): if type(other) is not Node: raise 'another Node typeError' ret = Node.build(self.values+other.values) return ret def __mul__(self, other): if type(other) is not int: raise 'Integer typeError' if other==0: return Node() elif other>0: tmp = Node(self.val,self.next) return Node.build(tmp.values * other) else: raise 'Integer rangeError' def __rmul__(self,other): return self.__mul__(other)
拓展七：添加其他方法
有增加必有减少，常见的操作除了创建、追加、插入，还有弹出、删除、查找、反序等等。有了以上的经验，给这个类添加这些方法不是难事，在以后的续篇中再来添加这些方法。
拓展八：增加单链表类
单链表是多个节点相接的线性列表，基本就是调用Node()方法来操作数据。省略的代码如下：
class Node(): def __init__(self, value=None, Next=None): self.value = value self.next = Next def __repr__(self): return f'Node({self.value})' #......略...... class List(): def __init__(self, node=None): if not hasattr(node,'__iter__'): self.data = Node(node) else: self.data = None for val in node: self.append(val) def __str__(self): return f'List({self.__items__()})' __repr__ = __str__ def __items__(self): if self.is_empty(): return None else: res,cur = [],self.data while cur is not None: res.append(cur.value) cur = cur.next return res def __getitem__(self, key): lst = self.values return lst[key] def __len__(self): if self.data is None: return 0 return len(self.__items__()) def is_empty(self): return self.data is None size = __len__ def push(self, val): node = Node(val) node.next = self.data self.data = node def append(self, val): if self.is_empty(): return self.push(val) node = self.data while node.next is not None: node = node.next node.next = Node(val) def pop(self): if self.is_empty(): return None if self.size()==1: self.next = None node = self.data while node.next is not None: node = node.next node.next = Node(val) return def clear(self): self.data = None def pprint(self): if self.data==None: print('None') return for i,v in enumerate(self.__items__()): t = f"'{v}'" if type(v) is str else v print(f'{t}->' if i<self.size()-1 else f'{t}->None',end='') #......略......
大致的结构如上，未完善全部功能。如果把代码存入一个文本文件，如 linkedlist.py；以后只要导入这个就能用这些方法来编程了：
import linkedlist node = linkedlist.Node.build(1,2,3,4) print(node) #...... 或者： from linkedlist import Node node = Node() node.add([1,2,3]) print(node)
本文完，以上所有代码只求实现效果，没有太多讲究算法优化。有空再来继续研究吧......
