转载须注明出处：https://www.jianshu.com/u/5e6f798c903a
参考：《数据结构（Python 语言描述）》 - 第5章 接口、实现和多态
目录.jpg
在 C# 等静态语言中，我们会将"接口类型"简称为接口。但本文中提及的"接口"并非特指接口类型，而是以软件资源用户的视角，将软件资源为用户提供的各种操作视为接口。由于用户只关心如何使用方法，但并不关心其具体实现(这是类编写者的工作)，所以接口仅含方法名、参数以及文档注释。就 Python 而言，接口可理解为"类为用户提供的一组方法签名及其文档注释"。
使用 help 函数获取模块、数据类型、类、方法或函数的相关信息时，便会访问与该软件资源的接口相关的文档。比如通过 help() 获取 data types (或 classes) 的帮助文档时，可以看到一个 "Methods defined" 列表，其中包含了相关的接口。
class Cls:
"""测试类"""
def func_1(self, argm: object) -> object:
"""方法 1"""
return True
def func_2(self, argm):
"""方法 2"""
pass
help(Cls)
输出：
class Cls(builtins.object)
| 测试类
|
| Methods defined here:
|
| func_1(self, argm:object) -> object
| 方法 1
|
| func_2(self, argm)
| 方法 2
|
| ----------------------------------------------------------------------
| Data descriptors defined here:
|
| __dict__
| dictionary for instance variables (if defined)
|
| __weakref__
| list of weak references to the object (if defined)
一个设计良好的软件资源，其特征之一便是可以清晰的区分接口和实现。当用户使用一个软件资源时，只需要关心其接口。理想情况下，这些软件资源如何实现的细节，也就是底层的算法代码和数据结构，都隐藏或封装在一个抽象的边界中。这个边界将接口和实现隔开，从而：
- 允许用户即插即用的方式，快速地将软件资源整合起来；
- 让用户有机会在相同软件资源的不同实现中做出选；
- 并允许具体实现者对软件资源的实现做出修改，而不影响其用户的代码。
多态(polymorphism)是指一个软件资源的多种实现，但这些实现都遵从相同的接口或方法。比如在两个不同的实现中都使用了相同的运算符符号或方法名，这便是多态。多态方法的示例是 str 和 len ；多态运算符的示例是 + 和 == 。
1. 接口类型
一些编程语言会提供接口(interface)类型，例如 C#。在接口类型中，我们会指定一组函数成员，但不会实现它们。因此，接口本身不会执行任何操作，它作用是为实现接口的类提供一套有关函数成员的蓝图。在创建类的过程中，必须依照接口提供的蓝图，逐一实现接口中的函数成员。
Tips：本小结中提及的"接口"表示接口类型，如 IIfc1 接口。
# 本例展示了在C#中声明和使用接口的过程
interface IIfc1{ // 声明接口
void PrintOut(string s); // 不必实现函数体
}
class MyClass : IIfc1{ // 声明类，该类需要实现IIfc1接口
public void PrintOut(string s){ // 实现接口
Console.WriteLine("Calling through: {0}", s);
}
}
class Program{
static void Main(){
MyClass mc = new MyClass(); // 创建类实例
mc.PrintOut("object"); // 调用方法
}
}
2. 伪接口类
Python 中并没有接口类型，如果我们需要事先为类提供一个蓝图，以说明类中所包含的操作，可创建一个伪接口类。伪接口类不会出现在继承链中，作用仅在于为类提供蓝图，用于说明类中所包含的操作，并确保操作和实现之间的一致性。
伪接口类通常以 "Interface" 为后缀，其中包含一组未实现的方法，所有方法都以 pass 或 return 结尾并包含文档字符串。pass 语句用于没有返回值的修改器方法；return 语句用于访问器方法，并返回一个简单的默认值，如 False 、0 或 None 。最后，还需要为所有方法添加文档字符串，以说明该方法所做的事情。
由于在之后的内容中，我们会为一种为名"包(bag)"的无需集合(collection)类型开发接口。所以，此处以包集合为例，创建一个伪接口类：
"""
File: baginterface.py
Author: Ken Lambert
"""
class BagInterface(object):
"""Interface for all bag types."""
# Constructor 构造器
def __init__(self, sourceCollection = None):
"""Sets the initial state of self, which includes the
contents of sourceCollection, if it's present."""
pass
# Accessor methods 访问器方法
def isEmpty(self):
"""Returns True if len(self) == 0, or False otherwise."""
return True
def __len__(self):
"""Returns the number of items in self."""
return 0
def __str__(self):
"""Returns the string representation of self."""
return ""
def __iter__(self):
"""Supports iteration over a view of self."""
return None
def __add__(self, other):
"""Returns a new bag containing the contents
of self and other."""
return None
def __eq__(self, other):
"""Returns True if self equals other,
or False otherwise."""
return False
# Mutator methods
def clear(self):
"""Makes self become empty."""
pass
def add(self, item):
"""Adds item to self."""
pass
def remove(self, item):
"""Precondition: item is in self.
Raises: KeyError if item in not in self.
Postcondition: item is removed from self."""
pass
在设计一个软件资源的伪接口类时，首先考虑要完成哪些操作，并依次给出文档字符串；然后，依据文档字符串的描述来给出恰当的函数签名。
3. 开发基于 BagInterface 的实现
下面来为包集合开发两种基于 BagInterface 的实现。
在集合类的设计者获知了集合的伪接口类之后，类自身的设计和实现包含两个步骤：
- 选择一个恰当的数据结构来包含集合中的项，并确定用于表示集合状态的其它数据，将这些数据赋给
__init__方法中的实例变量(也有可能使用类变量)。 - 完成接口中指定方法的代码
注意：伪接口类的作用仅是为实现提供蓝图，不必也不需要继承伪接口类。
3.1 基于数组的实现
本节将基于 BagInterface 开发一个基于数组的实现，这里使用名为 Array 的数组类，代码如下：
"""
File: arrays.py
An Array is a restricted list whose clients can use
only [], len, iter, and str.
To instantiate, use
<variable> = array(<capacity>, <optional fill value>)
The fill value is None by default.
"""
class Array(object):
"""Represents an array."""
def __init__(self, capacity, fillValue = None):
"""Capacity is the static size of the array.
fillValue is placed at each position."""
self._items = list()
for count in range(capacity):
self._items.append(fillValue)
def __len__(self):
"""-> The capacity of the array."""
return len(self._items)
def __str__(self):
"""-> The string representation of the array."""
return str(self._items)
def __iter__(self):
"""Supports iteration over a view of an array."""
return iter(self._items)
def __getitem__(self, index):
"""Subscript operator for access at index."""
return self._items[index]
def __setitem__(self, index, newItem):
"""Subscript operator for replacement at index."""
self._items[index] = newItem
a. 构造器方法
from arrays import Array
class ArrayBag(object):# 不必继承BagInterface
"""An array-based bag implementation."""
# Class variable
DEFAULT_CAPACITY = 10
# Constructor
def __init__(self, sourceCollection = None):
"""Sets the initial state of self, which includes the
contents of sourceCollection, if it's present."""
self._items = Array(ArrayBag.DEFAULT_CAPACITY)
self._size = 0 # _size表示逻辑尺寸，len(Array)表示物理尺寸
if sourceCollection:
for item in sourceCollection:
self.add(item)
# --snip--
b. 无需使用数组变量的方法
当需要访问(或修改)实例变量时，应尽可能通过相应的方法来完成操作，将对变量的引用保持最小化。比如当我们需要查看包实例的逻辑尺寸时，应该运行 len()，而不是直接使用实例变量 _size。
这样做的优点是，例如某个方法没有使用数组变量，那么即使将数组变为其它数据结构，也无需对该方法做出修改，可继续使用。
class ArrayBag(object):
# --snip--
# Accessor methods
def isEmpty(self):
"""Returns True if len(self) == 0, or False otherwise."""
return len(self) == 0
def __len__(self):
"""Returns the number of items in self."""
return self._size
def __str__(self):
"""Returns the string representation of self."""
return "{" + ", ".join(map(str, self)) + "}"
def __eq__(self, other):
"""Returns True if self equals other,
or False otherwise."""
if self is other: return True
if type(self) != type(other) or \
len(self) != len(other):
return False
for item in self:
if not item in other:
return False
return True
# --snip--
c. 需要使用数组变量的方法
如果将数组变为其它数据结构，则会影响到使用数组变量的方法。因为，数据结构的改变可能会导致操作方式的变化。
class ArrayBag(object):
# --snip--
# Accessor methods
def __iter__(self):
"""Supports iteration over a view of self."""
cursor = 0
while cursor < len(self):
yield self._items[cursor] # 使用数组变量
cursor += 1
def __add__(self, other):
"""Returns a new bag containing the contents
of self and other."""
result = ArrayBag(self) # 使用数组变量，不一定是类变量
for item in other:
result.add(item)
return result
# Mutator methods
def clear(self):
"""Makes self become empty."""
self._items = Array(ArrayBag.DEFAULT_CAPACITY) # 使用数组变量
self._size = 0
def add(self, item):
"""Adds item to self."""
# Check array memory here and increase it if necessary
# 附加练习：如果数组已满，需要编写额外的代码以调整数组大小
self._items[len(self)] = item # 使用数组变量
self._size += 1
def remove(self, item):
"""Precondition: item is in self.
Raises: KeyError if item in not in self.
Postcondition: item is removed from self."""
# Check precondition and raise if necessary
if not item in self:
raise KeyError(str(item) + " not in bag")
# Search for the index of the target item
targetIndex = 0
for targetItem in self:
if targetItem == item:
break
targetIndex += 1
# Shift items to the left of target up by one position
for i in range(targetIndex, len(self) - 1):
self._items[i] = self._items[i + 1] # 使用数组变量
# Decrement logical size
self._size -= 1
# Check array memory here and decrease it if necessary
# 附加练习：如果删除了多个项，可能会造成内存的浪费。
# 编写代码，当数组的装载因子达到某个阈值时，自动调整数组的大小
3.2 基于链表的实现
本节将基于 BagInterface 开发一个基于链表的实现，这里使用名为 Node 的链表类，代码如下：
"""
File: node.py
Author: Ken Lambert
"""
class Node(object):
"""Represents a singly linked node."""
def __init__(self, data, next = None):
self.data = data
self.next = next
a. 构造器方法
"""
File: linkedbag.py
Author: Ken Lambert
"""
from node import Node
class LinkedBag(object):
"""A link-based bag implementation."""
# Constructor
def __init__(self, sourceCollection = None):
"""Sets the initial state of self, which includes the
contents of sourceCollection, if it's present."""
self._items = None # 外部头链接，初始值None表明链表为空
self._size = 0 # 逻辑尺寸
if sourceCollection:
for item in sourceCollection:
self.add(item)
# --snip--
b. 可拷贝的方法
如果某个方法没有访问数组变量，它也就不必访问链表变量。所以那些 ArrayBag 类中没有访问数组变量的方法，可直接拷贝到 LinkedBag 中。这是之前的策略——当需要访问(或修改)实例变量时，应尽可能通过相应的方法来完成操作，将对变量的引用保持最小化——带来的回报。也是编写方法的重要一环：尽可能尝试着将数据结构隐藏到对象的方法调用之中，以使得通过调用相应的方法便可完成对数据结构的操作(always try to hide the implementing data structures behind a wall of method calls on the object being implemented.)。
以下方法没有访问数组变量，可直接拷贝到 LinkedBag 中：
class LinkedBag(object):
# --snip--
# Accessor methods
def isEmpty(self):
"""Returns True if len(self) == 0, or False otherwise."""
return len(self) == 0
def __len__(self):
"""Returns the number of items in self."""
return self._size
def __str__(self):
"""Returns the string representation of self."""
return "{" + ", ".join(map(str, self)) + "}"
def __eq__(self, other):
"""Returns True if self equals other,
or False otherwise."""
if self is other: return True
if type(self) != type(other) or \
len(self) != len(other):
return False
for item in self:
if not item in other:
return False
return True
# --snip--
c. 需要使用链表变量的方法
class LinkedBag(object):
# --snip--
# Accessor methods
def __iter__(self):
"""Supports iteration over a view of self."""
cursor = self._items
while not cursor is None:
yield cursor.data
cursor = cursor.next
def __add__(self, other):
"""Returns a new bag containing the contents
of self and other."""
result = LinkedBag(self) # 改动
for item in other:
result.add(item)
return result
# Mutator methods
def clear(self):
"""Makes self become empty."""
# Exercise
self._items = None # 外部头链接，初始值None表明链表为空
self._size = 0 # 逻辑尺寸
def add(self, item):
"""Adds item to self's head."""
# 在列表头部添加新项，从而利用了常数访问时间的优点
self._items = Node(item, self._items)
self._size += 1
def remove(self, item):
"""Precondition: item is in self.
Raises: KeyError if item in not in self.
Postcondition: item is removed from self."""
# Check precondition and raise if necessary
if not item in self:
raise KeyError(str(item) + " not in bag")
# Search for the node containing the target item
# probe will point to the target node, and trailer
# will point to the one before it, if it exists
probe = self._items
trailer = None
for targetItem in self:
if targetItem == item:
break
trailer = probe
probe = probe.next
# Unhook the node to be deleted, either the first one or one
# thereafter
if probe == self._items:
self._items = self._items.next
else:
trailer.next = probe.next
# Decrement logical size
self._size -= 1
# --snip--
