python数据结构教程 Day3
2020-07-17 本文已影响0人
XaviSong
本节重点：
- 线性结构介绍
- 栈结构介绍
- 栈结构ADT实现
- 栈在问题中的应用
一、线性结构
定义：
线性结构是一种有序数据项的集合，其中 每个数据项都有唯一的前驱和后继。除了第一个没有前驱，最后一个没有后继 新的数据项加入到数据集中时，只会加入到原有 某个数据项之前或之后。
称呼：
线性结构总有两端，在不同的情况下，两端的称呼也不同。栈中一般称为栈顶、栈底。队列中一般称为队列左端、队列右端。
特点：
不同线性结构的关键区别在于数据项增减的方式。有的结构只允许数据项从一端添加（栈），而有的结构则允许数据项从两端移除(双端队列)。
二、栈结构
定义：
一种有次序的数据项集合，属于线性结构。在栈中，数据 项的加入和移除都仅发生在同一端。
特征：
距离栈底越近的数据项，留在栈中的时间 就越长，而最新加入栈的数据项会被最先移除。这种次序通常称为“后进先出LIFO（Last in First out）”。
应用：
翻转访问的次序。如：浏览器的后退按钮、word中的ctrl+Z快捷键，都是对最近的操作进行再操作。
示例：入栈与出栈顺序改变
入栈出栈的顺序改变
三、python实现栈ADT
step1、定义其操作：
- Stack()：创建一个空栈，不包含任何数据项
- push(item)：将item加入栈顶，无返回值
- pop()：将栈顶数据项移除，并返回，栈被修改
- peek()：“窥视”栈顶数据项，返回栈顶的数 据项但不移除，栈不被修改
- isEmpty()：返回栈是否为空栈
- size()：返回栈中有多少个数据项
step2、实现操作：
- 将ADT Stack实现为Python的一个Class
- 将ADT Stack的操作实现为Class的方法
由于Stack是一个数据集，所以可以采用Python 的原生数据集来实现，我们选用最常用的数据集 List来实现。
step3、设计操作样例，测试并完善：
按照操作样例执行，检查ADT的各个操作是否返回预期结果。
设计测试样例
代码实践
class Stack:
'''
栈底在列表首端的版本，好处是上一篇讲过列表在尾部pop的时间比在其他位置pop的时间要少，所以 栈顶在列表尾部，可以让栈的常用操作pop、push复杂度为O(1)
'''
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[-1]
def size(self):
return len(self.items)
s = Stack()
print(s.isEmpty())
s.push(4)
s.push("dog")
print(s.peek())
s.push(True)
s.pop()
s.pop()
print(s.size())
'''
True
dog
1
'''
四、栈在问题中的应用
1、通用括号匹配
检查给定含有大括号、中括号、小括号串中括号是否合法
def parchecker(symbolString):
'''
所有左括号入栈，遇见右括号时，如果栈为空，则说明右括号多了，直接判定为不匹配；如果栈不空，弹栈，matches函数检查弹栈元素与当前待匹配左括号是否为同一类型。
'''
s = Stack()
balanced = True
index = 0
while index < len(symbolString) and balanced:
symbol = symbolString[index]
if symbol in "({[":
s.push(symbol)
else:
if s.isEmpty():
balanced = False
else:
top = s.pop()
if not matches(top, symbol):
balanced = False
index = index + 1
if balanced and s.isEmpty():
return True
else:
return False
def matches(open, close):
'''
精彩的设计，利用列表下标的对应关系
'''
opens = "({["
closers = ")}]"
return opens.index(open) == closers.index(close)
2、十进制转换为十六以下的任意进制
如：十进制10的八进制表示为12
def baseConverter(decNumber,base):
digits = "0123456789ABCDEF"
remstack = Stack()
while decNumber > 0:
rem = decNumber % base
remstack.push(rem)
decNumber = decNumber // base
newString = ""
while not remstack.isEmpty():
newString = newString + digits[remstack.pop()]
return newString
3、中缀表达式转换（复杂一点）
如果不清楚前缀、中缀、后缀，可以参考树的三种遍历顺序，它们是对应的。
首先：中缀表达式不同于前缀与后缀表达式，它可能对应不同的实际情况
如：中缀A+B*C可能对应两种情况：
列举中缀表达式的可能性
为此人们引入括号和优先级（* > +）来消除歧义，然而在中缀表达式里必须使用的括号，在前缀和后缀表达式中可以消失。也就是说，在前缀和后缀表达式中，操作符的次序完 全决定了运算的次序，不再有混淆。
中缀表达式向前缀、后缀表达式的转换：
- 将中缀表达式转换为全括号形式
- 将所有的操作符移动到子表达式所在的左括号（ 前缀）或者右括号（后缀）处，替代之，再删除所有的括号
中缀转前缀、后缀示例
另一种通用的中缀转后缀算法：
1、首先，创建空栈opstack用于暂存操作符 ，空表postfixList用于保存后缀表达式
2、将中缀表达式转换为一个一个的字符列表
3、从左到右扫描中缀表达式单词列表
如果单词是操作数，则直接添加到后缀表达式列表的 末尾
如果单词是左括号“(”，则压入opstack栈顶
如果单词是右括号“)”，则反复弹出opstack栈顶的操作符，加入到输出列表末尾，直到碰到左括号
如果单词是操作符“*/+-”，则压入opstack栈顶（但在压入之前，要比较其与栈顶操作符的优先级 如果栈顶的高于或等于它，就要反复弹出栈顶操作符 ，加入到输出列表末尾。直到栈顶的操作符优先级低于它）
4、中缀表达式单词列表扫描结束后，把opstack栈中的所有剩余操作符依次弹出，添加到输出列表末尾
5、把输出列表再用join方法合并成后缀表达式字符串，算法结束。
代码实现：
def infixToPostfix(infixexpr):
# 定义符号优先级
prec = {}
prec["*"] = 3
prec["/"] = 3
prec["+"] = 2
prec["-"] = 2
prec["("] = 1
opStack = Stack()
postfixexpr = []
tokenlist = infixexpr.split()
for token in tokenlist:
if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or "0123456789":
postfixexpr.append(token)
elif token == '(':
opStack.push(token)
elif token == ')':
top = opStack.pop()
while top!='(':
postfixexpr.append(top)
top = opStack.pop()
else:
while (not opStack.isEmpty) and (prec[opStack.peek() >= prec[token]]):
postfixexpr.append(opStack.pop())
opStack.push(token)
while not opStack.isEmpty():
postfixexpr.append(opStack.pop())
return " ".join(postfixexpr)
4、后缀表达式求值：
有了上一题的经验，这一题就稍微容易一些。
1、创建空栈operandStack用于暂存操作数
2、将后缀表达式用split方法解析为单词（token）的列表
3、从左到右扫描单词列表
1、如果单词是一个操作数，将单词转换为整数int，压入operandStack栈顶
2、如果单词是一个操作符（*/+-），就开始求值，从栈顶弹出2个操作数，先弹出的是右操作 数，后弹出的是左操作数，计算后将值重新压入栈顶。
4、单词列表扫描结束后，表达式的值就在栈顶
5、弹出栈顶的值，返回。
def postfixEval(postfixexpr):
operandStack = Stack()
tokenlist = postfixexpr.split()
for token in tokenlist:
if token in "0123456789":
operandStack.push(int(token))
else:
operand2 = operandStack.pop()
operand1 = operandStack.pop()
operandStack.push(doMath(token,operand1,operand2))
return operandStack.pop()
def doMath(op,operand1,operand2):
if op == "*":
return operand1 * operand2
if op == "/":
return operand1 / operand2
if op == "+":
return operand1 + operand2
if op == "-":
return operand1 - operand2
