Python-100days-16

Day16 - Python进阶之数据结构

大“O”表示法

当我们比较一个算法时，用一个T的函数表示赋值语句的数量，例如T(n)=1+n，n一般指问题的规模，也就是为了解决一个规模为n，对应的n+1的操作部署的问题，所需时间为T(n)。当问题规模n越大时，T(n)中的一部分会占据大头，这种起主导作用的部分，我们成为数量级函数，它表示规模n增加时，T(n)中增长最快的部分。我们称之为大“O”表示法，，也就是T(n)中主导部分的简化表示。

评价算法优劣

评价算法的好坏：渐近时间复杂度和渐近空间复杂度。

渐进时间复杂度大O表示

当n很小时

当n逐渐增大

从上面两幅图可以看出，当n很小时，函数之间不易区分，很难说谁占据主导作用。然而当n增大时，很明显可以看出谁起到主导作用，容易比较。
举个例子：

a = 5
b = 6
c = 10
for i in range(n):
    for j in range(n):
        x = i * i
y = j * j
z = i * j
for k in range(n):
    w = a * k + 45
    v = b * b
d = 33

上述代码不起任何作用。
从上述代码可以看出，任务操作总数分为四项。第一项是常数部分，总共三个常数赋值。第二项是嵌套迭代循环，其中还包含三个赋值，每一个赋值语句执行双重循环n^{2次。第三项是一个循环加两个赋值，一共2n次。最后一项是常数赋值，1次。所以总的T(n)=3+3n}2+2n+1=3n^{2+2n+4。很明显可以看出，指数型占据主导作用，当n增大时，其他项可以忽略，所以这段代码的数量级就是O(n}2)。

列表

列表操作中的大O效率

pop()表示在一个已知长度的列表中从列表的末端删除元素。pop(i)表示从列表开头删除元素。

字典

字典操作效率大O表示

基本数据结构

当添加一个项目时，它就被放在这样一个位置：在之前存在的项与后来要加入的项之间。像这样的数据集合常被称为线性数据结构。

栈

一个栈是一个项的有序集合，添加项和移除项都发生在同一端，通常被称为顶，另一端被称为底。堆栈遵循“后进先出”，越新的项越靠近顶，越老的靠近底。

栈的抽象数据类型

堆栈是结构化的，栈是一个有序的集，项添加和删除的一端称为顶，栈操作如下：

stack()创建一个新的空栈，不需要参数，返回一个空栈。
push(item)将新项目添加到堆栈的顶部，它不需要参数item，没有返回值。
pop()从栈顶删除项目，不需要参数，栈被修改。
peek()返回栈顶的项，不删除，不需要参数，堆栈不被修改。
isEmpty()测试栈是否为空，不需要参数，返回一个布尔值。
size()返回栈的项目数，不需要参数，返回一个整数。

简单的栈操作

队列

队列是一系列有顺序的元素的集合，新元素的加入在队列的一端，这一端叫“队尾”，已有元素的一处发生在队列的另一端“队首”。当一个元素被加入到队列之后，它就从队尾开始向队首前进，指导它成为下一个即将被移除队列的元素。遵循的原则是“先进先出”。

队列的抽象数据类型

队列的一些基本操作：

queue()创建一个空队列对象，五翻出，返回空的队列。
enqueue(item)将数据项添加到队尾，无返回值。
dequeue()从队首移除数据项，无参数，返回值为队首数据项。
isEmpty()测试是否为空队列，无需参数，返回布尔值。
size()返回队列中的数据项的个数，无需参数。

队列操作示例

双端队列

双端队列与队列类似，也是一系列元素的有序组合。其两端成为队首和队尾，元素再达到双端前始终位于双端队列之中。与队列不同的是，双端队列对元素添加和删除的限制不那么严格，元素可以从两端插入也可以从两端删除。

抽象数据类型

Deque抽象数据类型双端队列由以下一些结构和操作来定义。

Deque()创建一个空的双端队列，无参数，返回Deque对象。
addFront(item)在队首插入一个元素，参数为待插入元素，无返回值。
addRear(item)在队尾插入一个元素，参数为待插入元素，无返回值。
removeFront()队首移除元素，返回该元素，双端队列会改变。
removeRear()队尾移除元素，返回该元素，双端队列会改变。
isEmpty()判断双端队列中数据项是否为空，返回布尔值。
size()返回双端队列中数据项的个数，返回整数值。
例子：用双端队列判断回文序列。

from pythonds.basic.deque import Deque

def palchecker(aString):
    chardeque = Deque()
    for ch in aString:
        chardeque.addRear(ch)
    stillEqual = True
    while chardeque.size() > 1 and stillEqual:
        first = chardeque.removeFront()
        last = chardeque.removeRear()
    if first != last:
        stillEqual = False
    return stillEqual

if __name__ == '__main__':
    rText = palchecker("radar")
    print(rText)

列表

列表是一些元素的集合，每个元素拥有一个与其他元素不同的相对位置。

抽象数据类型无序列表

list()创建一个新的空列表，无参数，返回空列表。
add(item)列表中添加项，无返回值。
remove(item)从列表中删除元素，会修改列表内容。
search(item)搜索列表中的元素，无参数，返回布尔值。
isEmpty()判断列表是否为空，无参数，返回布尔值。
size()返回列表元素数。
append(item)在列表末端添加一个新的元素。
index(item)返回元素在列表中的位置。
insert(pos，item)在指定的位置添加一个新元素。
pop()从列表末端移除一个元素并返回它。
pop(pos)从指定位置移除列表元素并返回它。

链表实现无序列表

实现无序列表可以通过构建链表的方式。

节点node

链表的基本模块是节点。每个节点对象必须包含至少两条信息。必须包含列表元素本身（数据区），还需要由下一个节点的引用消息。
python实现节点：

class Node:
    def __init__(self, initdata):
        self.data = initdata
        self.next = None
    def getData(self):
        return self.data
    def getNext(self):
        return self.next
    def setData(self, newdata):
        self.data = newdata
    def setNext(self, newnext):
        self.next = newnext

无序列表

无序列表将由一个节点组合而成，每一个节点采用显式引用链接到下一个节点。只要知道第一个节点的位置，之后的元素都可以通过链接下一个节点。

class UnorderedList:
    def __init__(self):
        self.head = None

None说明我们建立的head头不指向任何东西，只是初始化一个空的列表。
功能示例代码：

class Node:
    def __init__(self, init_data):
        self.data = init_data
        self.next = None
    def get_data(self):
        return self.data
    def get_next(self):
        return self.next
    def set_data(self, new_data):
        self.data = new_data
    def set_next(self, new_next):
        self.next = new_next

class UnorderedList:
    def __init__(self):
        self.head = None
    def is_empty(self):
        return self.head is None
    def add(self, item):
        temp = Node(item)
        temp.set_next(self.head)
        self.head = temp
    def size(self):
        current = self.head
        count = 0
        while current is not None:
            count = count + 1
            current = current.get_next()
        return count
    def search(self, item):
        current = self.head
        found = False
        while current is not None and not found :
            if current.getData == item:
                found = True
            else:
                current = current.get_next()
        return found
    def remove(self, item):
        current = self.head
        previous = None
        found = False
        while not found:
            if current.get_data() == item:
                found = True
            else:
                previous = current
                current = current.get_next()
        if previous is None:
            # 移除列表第一个节点
            self.head = current.get_next()
        else:
            previous.set_next(current.get_next())

抽象数据类型有序列表

有序列表的结构是一个数据的集合体，在集合体中，每个元素相对其他元素有一个基于元素的某些基本性质的位置。

OrderedList() 创建空的有序列表。
add(item) 保持原有顺序的情况下向列表添加一个新的元素。
remover(item) 从列表中删除某个元素，会修改原列表。
search(item) 列表中搜索某个元素，返回布尔值。
size() 返回元素的数量，返回整型。
index(item) 返回元素在列表中的位置，返回索引值。
pop() 删除并返回列表中的最后一项。
pop(pos) 删除并返回索引pos指定项，返回该元素。

实现有序列表

许多实现方法与无序列表是一致的，有序列表无非就是对每个数据进行某个规则的排序。

class OrderedList:
    def __init__(self):
        self.head = None
    def search(self, item):
        current = self.head
        found = False
        stop = False
        while current is not None and not found and not stop:
            if current.get_data() == item:
                found = True
            else:
                if current.get_data() > item:
                    stop = True
                else:
                    current = current.get_next()
        return found
    def add(self, item):
        current = self.head
        previous = None
        stop = False
        while current is not None and not stop:
            if current.get_data() > item:
                stop = True
            else:
                previous = current
                current = current.get_next()
        temp = Node(item)
        # 首先要判断插入的位置，然后在新建节点，判断是插在头部，还是列表的某个部位。
        if previous is None:
            temp.set_next(self.head)
            self.head = temp
        else:
            temp.set_next(current)
            previous.set_next(temp)

链表实现算法分析

isEmpty 方法复杂度为O（1），只需要检查链表头是否为None。
size方法，需要n个步骤，复杂度为O（n）。
无序列表add方法复杂度为O（1），永远只需要在链表头部简单地添加一个新的节点。
search、remove和有序列表中的add方法，需要遍历，复杂度为O（n）。