python数据结构教程 Day4

本节重点：

1. 队列
2. 双端队列
3. 有序表
4. 无序表

一、队列

1、定义：

队列是一种有次序的数据集合，其特征是新数据项的添加总发生在一端（通常称为“尾 rear”端），而现存数据项的移除总发生在另一端（通常称为 “首front”端）。

当数据项加入队列，首先出现在队尾，随着队首数据项的移除，它逐渐接近队首。新加入的数据项必须在数据集末尾等待， 而等待时间最长的数据项则是队首。这种次序安排的原则称为（FIFO:First-in first-out）先进先出。

队列仅有一个入口和一个出口，不允许数据项直接插入队中，也不允许从中间移 除数据项。

实际应用：

一台打印机面向多个用户/程序提供服务、OS进程调度、键盘输入缓冲。

2、队列ADT的实现

step1、定义其操作

• Queue()：创建一个空队列对象，返回值为 Queue对象；
• enqueue(item)：将数据项item添加到队尾， 无返回值；
• dequeue()：从队首移除数据项，返回值为队首 数据项，队列被修改；
• isEmpty()：测试是否空队列，返回值为布尔值
• size()：返回队列中数据项的个数。

step2、实现操作

采用 List 来容纳 Queue的数据项，同栈一样，有两种实现的方式，这里选择将List首端作为队列尾端，List的末端作为队列首端。时间复杂度：

• enqueue()复杂度为 O(n)
• dequeue()复杂度为 O(1)

class Queue:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def enqueue(self):
        self.items.insert(0,item)

    def dequeue(self):
        return self.items.pop()

    def size(self):
        return len(self.items)

3、来应用队列

热土豆问题：

传说犹太人反叛罗马人，落到困境，约瑟夫和39人决定殉难，坐成一圈儿，报数1～7，报到7的人由旁边杀死，结果约瑟夫给自己安排了个位置，最后活了下来。用队列来实现热土豆问题的算法，参数为参加游戏的人名列表，以及传土豆次数num，算法返回最后剩下的人名。

算法思路：

模拟游戏开始，只需要将队首的人出队，随即再到队尾入队，算是土豆的一次传递传递了num次后，将队首的人移除，不再入队如此反复，直到队列中剩余1人。

代码：

def hotpotato(namelist, num):
    simqueue = Queue()
    for name in namelist:
        simqueue.enqueue(name)
    
    while simqueue.size() > 1:
        for i in range(num):
            simqueue.enqueue(simqueue.dequeue())
        simqueue.dequeue()
    return simqueue.dequeue()

二、双端队列

1、定义：

双端队列Deque是一种有次序的数据集， 跟队列相似，其两端可以称作“首”、“尾”端， 但deque中数据项既可以从队首加入，也可以从队尾加入；数据项也可以从两端移除。

某种意义上说，双端队列集成了栈和队列的能力。不过双端队列并不具有内在的LIFO或者 FIFO特性 如果用双端队列来模拟栈或队列，需要由使用者自行维护操作的一致性。

2、双端队列ADT实现：

step1、定义其操作：

• Deque()：创建一个空双端队列
• addFront(item)：将item加入队首
• addRear(item)：将item加入队尾
• removeFront()：从队首移除数据项，返回值为 移除的数据项
• removeRear()：从队尾移除数据项，返回值为 移除的数据项
• isEmpty()：返回deque是否为空
• size()：返回deque中包含数据项的个数

step2、实现其操作：

采用List实现，List下标0作为 deque的尾端，List下标-1作为 deque的首端。这种方案的操作复杂度为：

• addFront/removeFront O(1) 列表尾部操作
• addRear/removeRear O(n) 列表头部操作

class Deque:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def addFront(self, item):
        self.items.append(item)

    def addRear(self,item):
        self.items.insert(0, item)

    def removeFront(self):
        return self.items.pop()

    def removeRear(self):
        return self.items.pop(0)

    def size(self):
        return len(self.items)

3、来应用双端队列：

用双端队列判断回文词：

1. 先将需要判定的词从队尾加入deque
2. 再从两端同时移除字符判定是否相同，直到 deque中剩下0个或1个字符

def palchecker(aString):
    chardequeue = Deque()
    for ch in aString:
        chardequeue.addRear(ch)
    stillEqual = True

    while chardequeue.size > 1 and stillEqual:
        first = chardequeue.removeFront()
        last = chardequeue.removeRear()
        if first != last:
            stillEqual = False
            
    return stillEqual

三、无序表

1、从python原始的list谈起

在前面基本数据结构的讨论中，我们采用 Python List来实现了多种线性数据结构（栈、队列、双端队列）。列表List是一种简单强大的数据集结构， 提供了丰富的操作接口，但并不是所有的编程语言都提供了List数据类型 ，有时候需要程序员自己实现。

python中的列表是无序列表，一种数据项按照相对位置存放的数据集，其中数据项只按照存放位置来索引，如第1个、 第2个……、最后一个等。

2、自己动手实现一个ADT List

step1、定义其操作

• List()：创建一个空列表
• add(item)：添加一个数据项到列表中，假设 item原先不存在于列表中
• remove(item)：从列表中移除item，列表被修改，item原先应存在于表中
• search(item)：在列表中查找item，返回布尔类型值
• isEmpty()：返回列表是否为空
• size()：返回列表包含了多少数据项
• append(item)：添加一个数据项到表末尾，假设item原先不存在于列表中
• index(item)：返回数据项在表中的位置
• insert(pos, item)：将数据项插入到位置pos ，假设item原先不存在与列表中，同时原列表具 有足够多个数据项，能让item占据位置pos
• pop()：从列表末尾移除数据项，假设原列表至 少有1个数据项
• pop(pos)：移除位置为pos的数据项，假设原列 表存在位置pos

step2、实现其操作

为了实现无序表数据结构，可以采用链表的方案。虽然列表数据结构要求保持数据项的前后相对位置，但这种前后位置的保持，并不要求数据项依次存放在连续的存储空间。在数据项之间建立链接指向，就可以保持其前后相对位置。

链表的基本元素：Node

每个节点至少要包含2个信息：数据项本身，以 及指向下一个节点的引用信息。注意next为None的意义是没有下一个节点了， 这个很重要。

Node的实现：

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

现在用链表实现无序表list：

链表的第一个和最后一个节点最重要 如果想访问到链表中的所有节点，就必须从第一 个节点开始沿着链接遍历下去，所以无序表必须要有对第一个节点的引用信息。

随着数据项的加入，无序表的head始终指向链条中的第一个节点。

注意！无序表mylist对象本身并不包含数据项 （数据项在节点中） 其中包含的head只是对首个节点Node的引用

代码：

class UnorderedList:
    def __init__(self):
        self.head = None # 指向第一个结点，没有数据

    def isEmpty(self):
        return head == None
    
    def add(self, item):
        '''
        由于是无序表，出于对插入效率的优化，每次都选择在头部插入
        '''
        temp = Node(item)
        temp.setNext(self.head)
        self.head = temp

    def size(self):
        current = self.head
        count = 0
        while current != None:
            count = count + 1
            current = current.getNext()
        return count

    def search(self, item):
        current = self.head
        found = False
        while current != None and not found:
            if current.getData() == item:
                found = True
            else:
                current = current.getNext()
        return found

    def remove(self, item):
        current = self.head
        previous = None
        found = False
        while current != None and not found:
            if current.getData() == item:
                found = True
            else:
                previous = current
                current = current.getNext()

        if previous == None: # 要删除的节点是第一个数据项节点
            self.head = current.getNext()
        elif previous.getNext() == None: # 没找到待删除元素
            return found
        else:
            previous.setNext(current.getNext())
        return found

上一篇：python数据结构教程 Day3
下一篇：python数据结构教程 Day5