189 8069 5689
ADT：Abstrack Datatype
创新互联是一家专注于成都网站设计、成都做网站与策划设计,历下网站建设哪家好?创新互联做网站,专注于网站建设十年,网设计领域的专业建站公司;建站业务涵盖:历下等地区。历下做网站价格咨询:028-86922220
在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 -*-
class Bag(object):
def __init__(self, maxsize=10): #初始化，maxsize定义最大容量
self.maxsize = maxsize #属性，表示最大容量
self._items = list() #容器类型，这里用列表
def add(self, item): #定义add操作
if len(self) > self.maxsize: #如果当前长度大于最大定义容量
raise Exception ('Bag is Full') #抛出异常
self._items.append(item) #否则添加到列表中
def remove(self, item): #定义删除操作
self._items.remove(item)
def __len__(self): #魔术方法
return len(self._items) #数据列表的长度
def __iter__(self): #实现迭代器
for item in self._items:
yield item
#测试用例
def test_bag():
bag = Bag()
bag.add(1)
bag.add(2)
bag.add(3)
assert len(bag) == 3
bag.remove(3)
assert len(bag) == 2
for i in bag:
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)可以简单理解为删除一个元素，需要执行多少个步骤。】