0. 目标
- To understand the abstract data types **stack, queue, deque, and list **.
- To be able to implement the ADT‘s stack, queue, and deque using Python lists.
- To understand the performance of the implementations of basic linear data structures.
- To understand prefix, infix, and postfix expression formats.
- To use stacks to evaluate postfix expressions.
- To use stacks to convert expressions from infix to postfix.
- To use queues for basic timing simulations.
- To be able to recognize problem properties where stacks, queues, and deques are appropriate data structures.
- To be able to implement the abstract data type list as a linked list using the node and reference pattern.
- To be able to compare the performance of our linked list implementation with Python’s list
implementation.
1. 课程笔记
1.1 线性数据结构——stack 堆
- stack特点1：LIFO last-in-fist-out， 最近的在Top，最老的在Base （例如一堆书）。常见例子：浏览过的URL存储在stack的数据结构，点击Back button可以退回到上一个。
- stack的实现
- stack( ): 空的stack
- push (item): 加入一个新数据在stack top，无返回
- pop ( ): 移除一个在stack top，返回item
- peek( ): 返回top item，但对stack 没有修改
- is_empty( ): 返回布尔值
- size( ): stack的大小，返回一个整数。
class Stack(): #最右边是top
def __init__(self):
self.stack = []
def is_empty(self):
if self.stack == []:
return True
else:
False
def push(self, item):
self.stack.append(item)
return self.stack
def pop(self):
m =self.stack.pop()
return m
def peek(self):
last_num = len(self.stack) - 1
return self.stack[last_num]
def size(self):
num = len(self.stack)
return num
from Stack_function import Stack ##从相同工程下的Stack_function.py取出Stack class的定义
s = Stack()
print(s.is_empty())
print(s.push(4))
print(s.push(5))
print(s.push('dog'))
print(s.pop())
print(s.peek())
print(s.size())
-
stack应用一：翻转字符串
a20a5b41-53cd-4435-94c5-0030a377c06a.png
def reverse(self):
new_list = []
i = len(self.stack) - 1
while i >= 0:
m = self.stack[i]
new_list.append(m)
i = i - 1
return new_list
- stack 应用二：检查括号是否成对出现：将符号放入stack中
from Stack_function import Stack
def cheek_balance(list):
mystack = Stack() # 初始化一个stack的空间
index = 0
num = len(list)
while index < num and index >= 0:
i = list[index] #从list中取出一个需要判断的符号
if i == '(': #push进stack
mystack.push(i)
if i == ')' and mystack.is_empty():
return 'sorry, it is not balance'
if i == ')':
mystack.pop()
index = index + 1
if mystack.is_empty() == True:
return 'perfect'
else:
return 'sorry'
- stack 应用三：十进制转化成二进制：将余数放入stack中
from Stack_function import Stack
def dicimal_to_binary(k):
mystack = Stack()
new_string = ''
if k == 1: #排除0、1的二进制
return 1
if k == 0:
return 0
else:
while k != 0:
remainder = k % 2 # 余数
mystack.push(remainder)
k = k // 2 #除数
while not mystack.is_empty():
index = str(mystack.pop())
new_string = new_string + index #字符串可以通过加号连接
return new_string
print(dicimal_to_binary(20))
1.2 线性结构——Queue 队列
- 特点： FIFO
- 实现queue的数据结构
class Queue():
def __init__(self):
self.queue = []
def enqueue(self, item):
self.queue.insert(0, item)
def dequeue(self):
return self.queue.pop()
def is_empty(self):
if len(self.queue) == 0:
return True
else:
return False
#return self.queue == []
def size(self):
return len(self.queue)
def print_queue(self):
return self.queue
- queue的应用一：烫手的山芋(hot potato): 约瑟夫环问题
from queue_structure import Queue
def hot_potato(List, num):
queue = Queue() # 初始化一个排队
for i in List:
queue.enqueue(i)
print(queue.print_queue()) #放入queue，已将考虑了bill在最前面
while queue.size() > 1: #最后只剩下一个人
for k in range(num): # k = 1,2,3,4,5,6,7
name = queue.dequeue()
queue.enqueue(name)
queue.dequeue() #达到7次后删除第一个
return queue.print_queue()
Namelist = ["Bill","David","Susan","Jane","Kent","Brad"]
print (hot_potato(Namelist, 7))
- queue的应用二：打印机任务建模
1.3 线性结构——Dequeue 双端队列
- 特点： 两端都可以插入和输入
- 实现dequeue
class Dequeue():
def __init__(self):
self.dequeue = []
def add_front(self, item):
self.dequeue.append(item)
def add_back(self, item):
self.dequeue.insert(0, item)
def delete_front(self):
return self.dequeue.pop()
def delet_back(self):
return self.dequeue.pop(0)
def is_empty(self):
if self.dequeue == []:
return True
else:
return False
def size(self):
return len(self.dequeue)
def print_dequeue(self):
print(self.dequeue)
- 双端队列的应用：回文检测
① 一个数据结构(list)， 不可能凭空变成另一种数据结构(dequeue)，只能通过一个一个添加的方法，将数据录入dequeue
②下面的dequeue的数据结构，没有dequeue[0]，因为没有定义
from dequeue_structure import Dequeue
def Palindrome_check(list):
dequeue = Dequeue()
n = len(list)
for i in range(n):
dequeue.add_back(list[i]) #倒叙输入到dequeue中
dequeue.print_dequeue()
while dequeue.size() > 1:
if dequeue.delete_back() == dequeue.delete_front():
continue
else:
return "False"
return "True"
1.4 无序队列(节点存储的数字大小是随机的)——链表(liked list)
- 为什么要使用链表？
list插入的时候耗时太长（需要向后移动） - 存储特点：
① 节点：一个具体存放的数值&下一个节点的地址
② head = none，既是代表了每个节点next node
③ 先add的当作old list，将最近添加的node连接到old list - 构造链表结构
class Node:
def __init__(self, initdata):
self.data = initdata
self.next = None
def get_data(self):
return self.data
def get_next(self): #type:Node
return self.next
def set_data(self, new_data):
self.data = new_data
def set_next_node(self, new_next):
self.next = new_next
- 实现链表
class UnorderList:
def __init__(self):
self.head = None #!! the end of structure / the entrance point
def is_empty(self):
return self.head == None #查看是否有head之后有node连接
def add(self, item):
temp = Node(item) #初始化一个节点
temp.set_next_node(self.head) #连接上end， 或者old list node
self.head = temp
def print_link_list(self):
current = self.head
list = []
while current != None:
item = current.get_data()
list.append(item)
current = current.get_next()
return list
def size(self):
current = self.head
sum_node = 1
while current.get_next() != None:
sum_node = sum_node + 1
current = current.get_next()
return sum_node
def search(self, item):
current = self.head # star at the head
while current.get_next() != None:
if current.get_data() == item:
return "Find" , item
else:
current = current.get_next()
return "Not find"
def remove(self, item):
current = self.head
pro_node = None
found = False
while not found:
if current.get_data() == item:
found = True
else:
pro_node = current
current = current.get_next()
if pro_node == None: #第一个节点删除
self.head = current.get_next()
else: #其他节点或者最后一个节点
pro_node.set_next_node(current.get_next())
mylist = UnorderList()
print(mylist.is_empty())
mylist.add(31)
mylist.add(30)
mylist.add(29)
print(mylist.size())
print(mylist.remove(30))
print(mylist.print_link_list())
True
3
None
[29, 31]
- 扩展其他的功能append, insert, index, and pop
## 在最后一个节点后面增加一个节点，记录消耗的时间
def append(self, item):
#search最后一个点
current = self.head #current is <class '__main__.Node'>
new_node = Node(item)
while current.get_next() != None:
current = current.get_next()
else:
current.set_next_node(Node)
return None
import time
mylist = UnorderList()
mylist.add(31)
mylist.add(30)
mylist.add(29)
tic = time.time()
mylist.append(10)
toc = time.time()
print('time is'+ str(1000*(toc-tic))+ 'ms')
---------------------------------------------------------------------------
AttributeError Traceback (most recent call last)
<ipython-input-21-29193cbe3960> in <module>()
5 mylist.add(29)
6 tic = time.time()
----> 7 mylist.append(10)
8 toc = time.time()
9 print('time is'+ str(1000*(toc-tic))+ 'ms')
AttributeError: UnorderList instance has no attribute 'append'
def insert(self, item, position):
# initialize a node
new_node = Node(item)
current = self.head
print(current.get_data())
pos = 0
pro_node = None
find = False
while not find:
if pos != position:
pro_node = current
current = current.get_next()
pos += 1
if position == 0: # Can I improve it?
self.head = new_node
new_node.set_next_node(current)
find = True
else:
pro_node.set_next_node(new_node)
new_node.set_next_node(current.get_next())
find = True
def index(self, num):
current = self.head
pos = 0
Find = False
while not Find:
if current.get_data() == num:
return pos
else:
current = current.get_next()
pos += 1
def pop(self):
current = self.head
Find = False
pro_node = None
while not Find:
if current.get_next() != None:
pro_node = current
current = current.get_next()
print(pro_node.get_data())
else:
pro_node.set_next_node(None)
Find = True
- 有序链表，例如从小到大排列
class OrderList():
def __init__(self):
self.head = None
def add(self, item):
node = Node(item)
node.set_next_node(self.head)
self.head = node
def print_list(self):
current = self.head
list = []
while current != None:
item = current.get_data()
list.append(item)
current = current.get_next()
return list
def search(self, item):
current = self.head
while current != None:
if current.get_data() == item:
return 'Find it'
if current.get_data() > item:
return 'Sorry, you dont find it'
else:
print('serch:', current.get_data())
current = current.get_next()
return 'Dont find it'
def add_new_node(self, item):
current = self.head
pro_node = None
print(type(pro_node))
Find = False
new_node = Node(item)
pos = 0
while not Find :
if current.get_data() >= item:
if pos == 0: # 在位置0加入
self.head = new_node
new_node.set_next_node(current)
Find = True
else: #在中间其他位置加入|
pro_node.set_next_node(new_node)
new_node.set_next_node(current)
Find = True
else:
pro_node = current
print ('through:', current.get_data())
current = current.get_next()
pos += 1
if current.get_next() == None: #最后一个节点加入
current.set_next_node(new_node)
Find = True
order_list = OrderList()
order_list.add(11)
order_list.add(9)
order_list.add(6)
print('1:', order_list.print_list())
# search
print('2:', order_list.search(8))
#add
order_list.add_new_node(12)
print('3:',order_list.print_list())
('1:', [6, 9, 11])
('serch:', 6)
('2:', 'Sorry, you dont find it')
<type 'NoneType'>
('through:', 6)
('through:', 9)
('3:', [6, 9, 11, 12])
