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