ADT：Abstrack Datatype


在python里面一切都是对象

示例：

l=list()#定义列表l.append(3)#调用append方法l.remove(3)#调用remove方法

上面示例中的列表就是一种抽象数据类型，通过组合一些现有的数据跟操作来形成一种新的数据结构。


用python的class实现抽象数据类型（ADT）

data (数据)

class

method(操作方法)



这里实现一个bag来做一个示例：

data：要用容器去存储

bag

method：add、remove、len、iter

代码如下：

#-*-condig:utf-8-*-classBag(object):def__init__(self,maxsize=10):#初始化，maxsize定义最大容量self.maxsize=maxsize#属性，表示最大容量self._items=list()#容器类型，这里用列表defadd(self,item):#定义add操作iflen(self)>self.maxsize:#如果当前长度大于最大定义容量raiseException('BagisFull')#抛出异常self._items.append(item)#否则添加到列表中defremove(self,item):#定义删除操作self._items.remove(item)def__len__(self):#魔术方法returnlen(self._items)#数据列表的长度def__iter__(self):#实现迭代器foriteminself._items:yielditem#测试用例deftest_bag():bag=Bag()bag.add(1)bag.add(2)bag.add(3)assertlen(bag)==3bag.remove(3)assertlen(bag)==2foriinbag:print(i)##test_bag()#调用测试函数

执行脚本：

# python bag_adt.py


实现一个ADT要注意的几个问题：

（1）数据成员，比如：items，应该选用什么样的数据结构？

（2）选用数据结构，能否满足定义ADT的操作要求？

比如add，remove这些操作能否满足要求；

（3）选用数据结构能支持高效的操作，它的效率如何？

例如上例中容器选用list来作为他的底层存储，实际上他的add和remove操作效率，

不如选用set来作为容器效率更高，上例中的 remove 的操作来删除中间的一个元素，

它的时间复杂度就是O(n)。

【O(n)可以简单理解为删除一个元素，需要执行多少个步骤。】