数据结构( Pyhon 语言描述 ) — — 第5章：接口、实现和多态
- 接口
- 接口是软件资源用户可用的一组操作
- 接口中的内容是函数头和方法头，以及它们的文档
- 设计良好的软件系统会将接口与其实现分隔开来
- 多态
- 多态是在两个或多个类的实现中使用相同的运算符号、函数名或方法。多态函数的示例是 str 和 len。多态运算符是 + 和 ==。多态方法的示例是 add 和 isEmpty。
- 将接口与实现隔开的好处
- 降低了用户的学习难度
- 允许用户以即插即用的方式，快速的将资源整合起来
- 让用户有机会在相同资源的不同实现中做出选择
- 允许用户对资源的实现做出修改，而不影响用户代码
- 开发接口
- 包的接口
- 包是一种无序的集合
- 定义包接口
- 在选择方法名和函数名的时候，应该尽量遵从通用、习惯的用法
- 包接口中的函数名、方法名和运算符如下：
- isEmpty
- len
- str
- for…
- in
- +
- ==
- clear
- add
- remove
- 指定参数和返回值
- 对包接口进行优化，是为接口中的操作添加参数，并用考虑它们返回什么值( 如果有返回值的话 )
- 迭代器依赖于 iter 方法
- 包操作及其方法
|
用户的包操作 |
Bag类中的方法 |
|
b = <class name>( optional collection> ) |
__init__( self, sourceCollection = none ） |
|
b.isEmpty() |
isEmpty( self ) |
|
len(b) |
__len__( self ) |
|
str( b ) |
__str__( self ) |
|
item in b |
__contains___( self, item ): 如果包含了__iter__，就不需要该方法 |
|
b1 + b2 |
__add__( self, other ) |
|
b == anyObject |
__eq__( self, other ) |
|
b.clear() |
clear( self ) |
|
b.add( item ) |
add( self, item ) |
|
b.remove( item ) |
remove( self, item ) |
- 构造方法和实现类
- 数组包
- 链表包
- 先验条件、后验条件、异常和文档
- 文档字符串
- 个引号括起来的字符串
- 个字符串
- 一个方法，如查没有什么可能的错误条件的话，文档字符串只用说明方法的参数是什么、返回值是什么、以及方法执行了什么样的操作
- 更加详细的文档形式
- 先验条件 ( Precondition )
- 是一条语句，只有该语句为真的时候，方法才能正常运行
- 后验条件( Postcondition )
- 当方法执行完毕后，什么条件会为真
- 异常
- 说明可能发生的异常，通常是无法满足方法的先验条件所致
- 示例
def remove( self, item ):
"""
Preconditon: item is in self.
Raise: KeyError if item is not in self.
Postcondition: item is removed from self.
"""
- 用 Python 编写接口
- 一些语言，如 Java 提供了编写接口的方法。Python 没有这样的方法，但是可以通过提供文档并指导类的开发，从而模拟类似的功能
- 为了创建接口，使用文档来列出每一个方法头，并且用一条单个的 pass 或 return 语句来结束每一个方法
- 示例
#!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author:Lijunjie
"""
File: baginterface.py
Author: Lijunjie
"""
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 ):
"""Return True if len( self ) == 0, or False otherwise."""
return True
def __len__( self ):
"""Returns the number of items in self."""
def __str__( self ):
"""Return the string representation of self."""
return ""
def __iter__( self ):
"""Supports iteration over a view of self."""
return None
def __add__( self, other ):
"""Return a new bag containing the contents of self and other"""
return None
def __eq__( self, other ):
"""Return True if self equals other, otherwise False."""
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.
Raise: KeyError if item is not in self.
Postcondition: item is removed form self.
"""
pass
- 开发一个基于数组的实现
- 集合类的设计确定接口后，类自身的设计和实现包含两个步骤
- 选择一个合适的数据结构来包含集合的项，并且确定可能需要表示集合状态的任何其他数据。将这些数据赋值给__init__方法中的实例变量
- 完成接口中相关方法的代码
- 选择并初始化数据结构
#!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author:Lijunjie
"""
File: arraybag.py
Author: Lijunjie
"""
from arrays import Array
class ArrayBag( object ):
"""An array-based bag implementation."""
#Class variable
#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_CAPACTIY )
if sourceCollection:
for item in sourceCollection:
self.add( item )
- 先完成容易完成的方法
- 应该尽可能的在 self 上调用方法或函数，而不是直接使用实例变量
- 代码示例
#Accessor methods
def isEmpty( self ):
"""Return True if len( self ) == 0, or False otherwise."""
def __len__( self ):
"""Returns the number of items in self."""
return self._size
#Mutator methods
def clear( self ):
"""Makes self become empty."""
self._items = Array( ArrayBag.DEFAULT_CAPACTIY )
def add( self, item ):
"""Adds item to self."""
#Check array memory here and increase it if necessary.
self._items[len( self )] = item
- 完成迭代器
- __str__，__add__和__eq__等方法，都需要借助 __iter__方法来正确运行
- __iter__通过 yield 语句，将每一项都发送给 for 循环调用
def __iter__( self ):
"""Supports iteration over a view of self."""
while cursor < len( self ):
yield self._items[cursor]
- 完成使用迭代器的方法
- __str__函数
def __str__( self ):
"""Return the string representation of self."""
return "{" + ", ".join( map( str, self ) ) + "}"
- __add__函数
def __add__( self, other ):
"""Return a new bag containing the contents of self and other"""
result = ArrayBag( self )
for item in other:
result.add( item )
return result
- __eq__函数
def __eq__( self, other ):
"""Return True if self equals other, otherwise False."""
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
- in 运算符和 __contains__ 方法
- in 运算符对应 __contains__ 方法
- 当类中不包含这个方法时，这个方法会在 self 上使用 for 循环，并进行一次顺序搜索
- 完成 remove 方法
def remove( self, item ):
"""
Precondition: item is in self.
Raise: KeyError if item is not in self.
Postcondition: item is removed form self.
"""
if not item in self:
raise KeyError( str(item) + " not in bag." )
#Search for index of target item.
for targetItem in self:
if targetItem == item:
break
#Shift items
for i in range( targetIndex, len( self ) - 1 ):
]
#Decrement logical size
#Check array memory here and decrease it if necessary
- 开发一个基于链表的实现
- 之前开发的 ArrayBag 类中的 __isEmpyt__，__len__，__add__，__eq__和__str__并没有直接访问数组变量，因此在 LinkedBag 类中，可以不进行修改。
- 初始化数据结构
"""
File: linkedbag.py
Author: Lijunjie
"""
from node import Node
class LinkedBag( object ):
"""An 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
if sourceCollection:
for item in sourceCollection:
self.add( item )
- 完成迭代器
def __iter__( self ):
"""Supports iteration over a view of self."""
cursor = self._items
while not cursor is None:
yield cursor.data
cursor = cursor.next
- 完成 clear 和 add 方法
- clear方法
def clear( self ):
"""Makes self become empty."""
self._items = None
- add 方法
def add( self, item ):
"""Adds item to self."""
self._items = Node( item, self._items )
- 完成 remove 方法
def remove( self, item ):
"""
Precondition: item is in self.
Raise: KeyError if item is not in self.
Postcondition: item is removed form self.
"""
if not item in self:
raise KeyError( str(item) + " not in bag." )
#Search for the node containing 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 the
#one thereafter
if probe == self._items:
self._items = self._items.next
else:
trailer.next = probe.next
#Decrement logical size
- 两个包实现的运行时性能
- in 和 remove 操作由于加入了顺序搜索，因此都是线性时间
- == 操作符默认的时间复杂度为
- 剩下的操作都是常数时间，除了 ArrayBag 需要调整数组长度的情况
- 当 ArrayBag 数组的装填因子超过 0.5 时，其内存占用要比相同逻辑大小的 LinkedBag 要小
- 测试两个包的实现
- 测试代码
##!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author:Lijunjie
"""
FIle: testbag.py
Author: Lijunjie
A test program for bag implementations.
"""
from arraybag import ArrayBag
from linkedbag import LinkedBag
def test( bagType ):
"""Expects a bag type as argument and runs some tests on objects
of that type. """
]
print( "The list of items added is:", lyst )
b1 = bagType( lyst )
print( "Expect 3:", len( b1 ) )
print( "Expect the bag's string:", b1 )
print( "Expect True:", 2018 in b1 )
print( "Expect False:", 2013 in b1 )
print( "Expect the items on spearate lines:" )
for item in b1:
print( item )
b1.clear()
print( "Expect {}:", b1 )
b1.add( 25 )
b1.remove( 25 )
print( "Expect {}:", b1 )
b1 = bagType( lyst )
b2 = bagType( b1 )
print( "Expect True:", b1 == b2 )
print( "Expect False:", b1 is b2 )
print( "Expect two of each items:", b1 + b2 )
for item in lyst:
b1.remove( item )
print( "Expect crash with keyError:" )
b2.remove( 99 )
if __name__ == "__main__":
#test( ArrayBag )
test( LinkedBag)
- 用 UML 图表示包资源
- 统一建模语言( Unified Modeling Language， UML )
- 带有一个接口和两个实现类的一个类图
- 聚合和组合关系
- 每个 LinkedBag 对象都聚合了 0 个或多个节点
- 每个 ArrayBag 对象都是单个 Array 对象的组合
- 组合是整体—部分关系，而聚合是一对多的关系
- 示意图
最新文章
- 原生JS事件绑定方法以及jQuery绑定事件方法bind、live、on、delegate的区别
- 【MongoDB】MongoDb的“not master and slaveok=false”错误及解决方法
- modbus协议讲义
- java.io.Serializable 序列化问题
- 在服务器上远程链接另一台服务器的数据库的方法how to connet the database from the other host
- Go channel同步
- vimrc for mac
- HDU 3555 Bomb （数位DP）
- Linux命令：cat命令详解
- 读书时间《JavaScript高级程序设计》七：表单
- Facebook兆级别图片存储及每秒百万级别图片查询原理
- ACCP8.0 HTML标签
- webpack2入门概念
- java标识符、修饰符和关键字
- CentOS7更改运行级别
- jdk1.8 HashMap的扩容resize()方法详解
- luogu P1052 过河
- 腾讯云外网IP直通后，遇到网络问题
- fork failed because of Out Of Memory
- 使用gdbserver远程调试