2.ADT和类（抽象数据类型和面向对象编程）

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 -*-
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)可以简单理解为删除一个元素，需要执行多少个步骤。】