高中生学编程--Python学习
欢迎使用 入门客AI创业平台
当前位置： 入门客AI创业平台 > 学习手册 > 服务端语言 > python 》 高中生学编程--Python学习 》 十一、Python简单数据结构应用（之…

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

十、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 " comb-----"

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的语句就是检查是否匹配，这是本程序中唯一比较难的语句。

我的更多文章：

文章导航