python数据结构教程 Day4
本节重点：
- 队列
- 双端队列
- 有序表
- 无序表
一、队列
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、来应用双端队列：
用双端队列判断回文词：
- 先将需要判定的词从队尾加入deque
- 再从两端同时移除字符判定是否相同，直到 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
