十一、Python简单数据结构应用（之…

最后更新于：2022-04-01 21:47:39

## 十、Python语言中简单数据结构的应用（之一） ----From a high schoolstudent's view to learn Python 关键字： python 列表 堆栈数据结构 递归调用 函数 组合问题 后缀表达式 前缀表达式 逆波兰表达式 运算符 优先级   本篇我们将简单介绍一下数据结构中的堆栈(stack)，以及在Python中利用堆栈所实现的一些应用。 一、堆栈介绍 堆栈是一个后进先出(LIFO)的数据结构，其工作方式就像往弹夹里面填子弹，在填好子弹之后，如果你要取出一颗子弹，那么你去除的这颗子弹一定是你最后填进去的，如果将子弹全部取出，那最后取出的那颗子弹一定是你最先填进去的那颗。把子弹当成我们程序中操作的元素，那么弹夹就是一个堆栈的模型了。 在栈上"push"元素是个常用术语，意思是把一个对象添加到堆栈中；反之，要删除一个元素,你可以把它"pop"出堆栈。此外，还有”empty”来判断堆栈是否为空状态。 很明显，使用Python中的List非常容易实现堆栈的模型，我们先复习一下List中有哪些内置的方法，在terminal窗口输入： dir(list) ['__add__', '__class__','__contains__', '__delattr__', '__delitem__', '__delslice__','__doc__', '__eq__', '__format__', '__ge__', '__getattribute__','__getitem__', '__getslice__', '__gt__', '__hash__', '__iadd__','__imul__', '__init__', '__iter__', '__le__', '__len__', '__lt__','__mul__', '__ne__', '__new__', '__reduce__', '__reduce_ex__','__repr__', '__reversed__', '__rmul__', '__setattr__','__setitem__', '__setslice__', '__sizeof__', '__str__','__subclasshook__', 'append', 'count', 'extend', 'index', 'insert','pop', 'remove', 'reverse', 'sort'] 内容很多，介绍一些常用的： s[i] = x item i of s is replaced byx s[i:j] = t slice of s from i to j isreplaced by the contents of the iterable t del s[i:j] same as s[i:j] = [] s[i:j:k] = t the elements of s[i:j:k] arereplaced by those of t del s[i:j:k] removes the elements ofs[i:j:k] from the list s.append(x) same as s[len(s):len(s)] =[x] s.extend(x) same as s[len(s):len(s)] =x s.count(x) return number of i‘s for whichs[i] == x s.index(x[, i[, j]]) return smallest k such thats[k] == x and i <= k < j s.insert(i, x) same as s[i:i] = [x] s.pop([i]) same as x = s[i]; del s[i];return x s.remove(x) same as dels[s.index(x)] s.reverse() reverses the items of s inplace s.sort([cmp[, key[,reverse]]]) sort the items of s inplace 我们使用List的append()来实现堆栈的push，使用pop()不带参数的情况来实现堆栈的pop，使用len(list)==0来实现empty。 举例： stack=[] len(stack)==0 True stack.append('1') stack.append('2') for a in '3456789': stack.append(a) ...  stack ['1', '2', '3', '4', '5', '6','7', '8', '9'] stack.pop() '9' stack ['1', '2', '3', '4', '5', '6','7', '8'] len(stack)==0 False 二、如何使用堆栈来模拟递归函数调用 看下面的程序，还是一个组合问题的程序：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

def comb(iterable, r,order=1):

   pool = tuple(iterable)

   if order != 1:

       pool =list(pool)

      pool.reverse()

       pool =tuple(pool)


   comb=[]

   n = len(pool)

   if r > n:

       returncomb

   indices = range(r)


   def subcomb(N, m, n, B):

      i=1

       whileTrue:

          if i == m-n+2:

             break

          indices[N-n] = i+B

          ifn-1>0:

             subcomb(N, m-i, n-1, B+i)

          else:

             comb.append(tuple(pool[k-1] for k inindices))

          i += 1

   

   subcomb(r,n,r,0)

   return comb


print "\ncomb-----"

comb1=comb(tuple('123456'),4)

for e in comb1: printe

print len(comb1)


这个程序就不像之前一句一句的详细介绍了，因为使用的方法和之前的没有根本的变化，简单说明如下： - 函数和之前相比，增加了一个参数，并且使用1作为缺省参数值，当该参数不为1时，我们将按照列表中元素的倒序来列出组合 - 递归函数为subcomb()，请注意，这个函数的定义和调用都在函数comb()中，这也是一种合法的方式 - 递归函数subcomb(N, m, n,B)实现的方式和前一篇介绍的稍有不同，前一篇是从后往前开始列出组合结果的，而这个是从前往后来列的，所以在参数中还额外的加了一个B用来表示递归子序列的起始位置；参数N表示最终组合中元素的个数，m、n分别表示当前所求的元素个数和组合中元素个数，递归调用时，m、n、B会变化 程序的运行结果： comb----- ('1', '2', '3', '4') ('1', '2', '3', '5') ('1', '2', '3', '6') ('1', '2', '4', '5') ('1', '2', '4', '6') ('1', '2', '5', '6') ('1', '3', '4', '5') ('1', '3', '4', '6') ('1', '3', '5', '6') ('1', '4', '5', '6') ('2', '3', '4', '5') ('2', '3', '4', '6') ('2', '3', '5', '6') ('2', '4', '5', '6') ('3', '4', '5', '6') 15 介绍这个程序不是主要目的，主要的目的是想说明，递归是可以通过使用堆栈来模拟的，而且最终运行的结果也一模一样。先看程序：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36


def combusestack(iterable, r,order=1):

   pool = tuple(iterable)

   if order != 1:

       pool =list(pool)

      pool.reverse()

       pool =tuple(pool)


   comb=[]

   nc = len(pool)

   if r > nc:

       returncomb

   indices = range(r)


   stack=[]

   res=[-1,-1,-1,-1]

   m, n, B, i = nc, r, 0,1 

   while True:

       while i ==m-n+2:

          if len(stack) ==0: 

             return comb

         (m,n,B,i)=stack.pop()

          i+=1

      indices[r-n] = i+B

       ifn-1>0:

          res=[m, n, B, i]

          stack.append(res)

          m, n, B, i = m-i, n-1, B+i,1

          continue

      else:

          comb.append(tuple(pool[k-1]for k in indices))

       i +=1


print "comb usestack-----"

comb1=combusestack(tuple('123456'),4)

for e in comb1: printe

print len(comb1)

运行结果： comb use stack----- ('1', '2', '3', '4') ('1', '2', '3', '5') ('1', '2', '3', '6') ('1', '2', '4', '5') ('1', '2', '4', '6') ('1', '2', '5', '6') ('1', '3', '4', '5') ('1', '3', '4', '6') ('1', '3', '5', '6') ('1', '4', '5', '6') ('2', '3', '4', '5') ('2', '3', '4', '6') ('2', '3', '5', '6') ('2', '4', '5', '6') ('3', '4', '5', '6') 15 这个程序使用一个List来模拟堆栈，进入堆栈中的元素，也是一个List，我们在原来递归函数进行递归调用的地方，将函数的其中3个参数(N除外，因为在过程中不会改变)以及循环变量i，push到堆栈中，在原来函数结束的地方，在堆栈中pop一个List出来，直到堆栈空为止。 在程序中也出现了一些比较奇特的语句，如line21、line27。 这个程序的目的只是为了验证，递归调用可以通过堆栈来模拟函数调用，变换为非递归的函数；其实这个程序可读性不是很高，而且在line21由于堆栈的弹出，会改变循环变量i的值，在调试程序和理解程序方面会带来困惑。 三、堆栈的简单应用举例 介绍两个例子，一是利用堆栈的特性，反转字符串，另一是利用堆栈，检查表达式中的（）是否匹配。 堆栈所具有的这种后进先出(LIFO)协议的特性，它可以作为一个通用的办法用于反转数据序列。例如，如果按照1，2，3的顺序把值压入一个堆栈，那么从堆栈中将它们弹出时的顺序为3，2，1。 看下面字符窜反转的例子：

1

2

3

4

5

6

7

8

9

10

11

12


defrev(s):

    stack =[]

    n =len(s)

    if n==0: returnNone

    for c in s:stack.append(c)

    revstr =''

    whilelen(stack)>0 :

       revstr += stack.pop()

    returnrevstr


printrev('123456789')

printrev('')


运行结果如下： 987654321 None 下面是关于检查括号是否匹配的例子 文字说明的部分摘录于<> In the following application, we considerarithmetic expressions that may contain various pairs of groupingsymbols, such as • Parentheses: “(” and “)” • Braces: “{”and “}” • Brackets: “[” and “]” Each opening symbol must match itscorresponding closing symbol. For example, a left bracket, “[,”must match a corresponding right bracket, “],” as in the expression[(5+x)-(y+z)]. The following examples further illustrate thisconcept: • Correct: ()(()){([()])} • Correct: ((()(()){([()])})) • Incorrect:)(()){([()])} • Incorrect: ({[])} - Incorrect: ( 程序如下：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20


defis_matched(expr):

   """Return True if all delimiters are properlymatch; 

   False otherwise."""

   lefty = '({['

   righty = ')}]'

   S = [] 

   for c in expr:

       if c inlefty: 

          S.append(c)

       elif c inrighty:

          if len(S) ==0: 

             return False

          if righty.index(c) !=lefty.index(S.pop()):

             return False

   return len(S) == 0

   

printis_matched('[(5+x)-(y+z)]')

printis_matched('{(5+x)-(y+z)]')

printis_matched('[(5+x)-(y+z))')


运行结果分别显示为：True False False 做一些说明： 我们仍然使用List来模拟堆栈，所以push和empty的形式和真正的堆栈有差异。 程序的流程大致是这样： for循环扫描表达式，如果遇到的字符是’({[‘中的任一个，则将该字符压入堆栈；否则如果字符是’)}]’中的任一个，程序先判断当前堆栈是否为空，为空则返回错误，然后判断符号是否匹配，line13的语句就是检查是否匹配，这是本程序中唯一比较难的语句。 我的更多文章： - [Python程序调试的一些体会](http://blog.sina.com.cn/s/blog_d6cca93e0101ewc9.html)(2013-10-06 22:57:35) - [十四、Python编程计算24点（之二）](http://blog.sina.com.cn/s/blog_d6cca93e0101euxx.html)(2013-10-03 22:18:28) - [十三、Python编程计算24点（之一）](http://blog.sina.com.cn/s/blog_d6cca93e0101eukc.html)![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2015-10-30_5632e1cc04fc3.gif "此博文包含图片") (2013-10-02 22:15:46) - [十二、Python简单数据结构应用（之二）](http://blog.sina.com.cn/s/blog_d6cca93e0101euk8.html)(2013-10-02 22:10:41) - [十、Python编程解决组合问题（之二）](http://blog.sina.com.cn/s/blog_d6cca93e0101entc.html)![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2015-10-30_5632e1cc04fc3.gif "此博文包含图片") (2013-09-21 23:37:27) - [九、Python编程解决组合问题（之一）](http://blog.sina.com.cn/s/blog_d6cca93e0101ent7.html)(2013-09-21 23:32:54) - [八、Python的函数编程（之二）](http://blog.sina.com.cn/s/blog_d6cca93e0101ekwj.html)![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2015-10-30_5632e1cc04fc3.gif "此博文包含视频") (2013-09-20 23:09:39) - [七、Python的函数编程（之一）](http://blog.sina.com.cn/s/blog_d6cca93e0101ekwg.html)![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2015-10-30_5632e1cc04fc3.gif "此博文包含视频") (2013-09-20 23:09:10) - [一、Python语言的入门](http://blog.sina.com.cn/s/blog_d6cca93e0101ebw4.html)(2013-09-08 09:16:19) - [高中生如何学编程](http://blog.sina.com.cn/s/blog_d6cca93e0101e8fn.html)(2013-09-02 19:26:01)
';