2.ADT和類（抽象數(shù)據(jù)類型和面向?qū)ο缶幊蹋?/h1>

發(fā)布時(shí)間：2020-07-12 04:14:28 來源：網(wǎng)絡(luò) 閱讀：1793 作者：聽丶飛鳥說 欄目：編程語言

ADT：Abstrack Datatype

在python里面一切都是對(duì)象

示例：

l = list()     #定義列表
l.append(3)    #調(diào)用append方法
l.remove(3)    #調(diào)用remove方法

上面示例中的列表就是一種抽象數(shù)據(jù)類型，通過組合一些現(xiàn)有的數(shù)據(jù)跟操作來形成一種新的數(shù)據(jù)結(jié)構(gòu)。

用python的class實(shí)現(xiàn)抽象數(shù)據(jù)類型（ADT）

---

            data (數(shù)據(jù))

class

            method(操作方法)

---

這里實(shí)現(xiàn)一個(gè)bag來做一個(gè)示例：

---

          data：要用容器去存儲(chǔ)

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:        #如果當(dāng)前長度大于最大定義容量
            raise Exception ('Bag is Full') #拋出異常
        self._items.append(item)            #否則添加到列表中

    def remove(self, item):                 #定義刪除操作
        self._items.remove(item)

    def __len__(self):                      #魔術(shù)方法
        return len(self._items)             #數(shù)據(jù)列表的長度

    def __iter__(self):                     #實(shí)現(xiàn)迭代器
        for item in self._items:
            yield item

#測(cè)試用例
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()      #調(diào)用測(cè)試函數(shù)

執(zhí)行腳本：

# python bag_adt.py

實(shí)現(xiàn)一個(gè)ADT要注意的幾個(gè)問題：

（1）數(shù)據(jù)成員，比如：items，應(yīng)該選用什么樣的數(shù)據(jù)結(jié)構(gòu)？

（2）選用數(shù)據(jù)結(jié)構(gòu)，能否滿足定義ADT的操作要求？

         比如add，remove這些操作能否滿足要求；

（3）選用數(shù)據(jù)結(jié)構(gòu)能支持高效的操作，它的效率如何？

        例如上例中容器選用list來作為他的底層存儲(chǔ)，實(shí)際上他的add和remove操作效率，

        不如選用set來作為容器效率更高，上例中的 remove 的操作來刪除中間的一個(gè)元素，

        它的時(shí)間復(fù)雜度就是O(n)。

        【O(n)可以簡單理解為刪除一個(gè)元素，需要執(zhí)行多少個(gè)步驟?！?/p>