Python常用数据结构

常用的数据结构有表、栈、队列、树等,本文介绍它们在Python中的定义和使用情况。

 


表是最基本的数据结构,python中的元组、列表等就是表的应用,它们都是一种线性的结构。

常用的实现表结构的方式有 单向链表双向链表

单向链表只提供了一个方向的链接方式,即只能从头到尾或从尾到头的去访问链接中的数据。

双向链表提供了双向的链接方式。

所以双向链表能带来更大的性能提升,如当需要在链表前的某个位置或链表后的某个位置插入新数据时,都可以快速地定位到相应位置,而单向链表只能在前后位置中的某一侧快速操作。

 


栈又称为堆栈,可以看做是特殊的表。

栈的特点是后进先出(LIFO),就像是一个容器,即往栈里插入数据时(压栈),最先进入的数据位于栈底,而后插入的数据在它的上面,取数据时取栈顶的数据(出栈),栈不允许在中间位置做插入或删除操作。

比如我们买一盒羽毛球,厂家装盒的时候是逐个把羽毛球放入到盒中,但我们取出来时,就要从最上面逐个取出,也就是先放入的后被取出。

我们借助列表实现一个简单的自定义栈对象,示例代码如下:

#!/usr/bin/python3
# -*- coding: utf8 -*-

'''
用列表实现一个自定义的栈对象
'''

class TestStack:
    def __init__(self):
        self.stack = []

    # 压栈
    def push(self, data):
        self.stack.append(data)

    # 出栈
    def pop(self):
        data = self.stack[-1]
        del self.stack[-1]
        return data


stack = TestStack()
for i in range(1, 5):
    stack.push(i)
    print(i, ': 出栈')

for i in range(1, 6):
    print(stack.pop(), ': 出栈')


'''
$ python3 09.py
1 : 出栈
2 : 出栈
3 : 出栈
4 : 出栈
4 : 出栈
3 : 出栈
2 : 出栈
1 : 出栈
Traceback (most recent call last):
  File "09.py", line 28, in <module>
    print(stack.pop(), ': 出栈')
  File "09.py", line 18, in pop
    data = self.stack[-1]
IndexError: list index out of range
'''

定义了类 TestStack 为一个栈对象,列表 stack 用于存储栈中的数据。

push() 方法用于压栈,使用列表的 append() 方法把新加入的数据添加到列表的末尾。

pip() 方法用于出栈,使用 self.stack[-1] 取得列表中的最末尾的数据,并使用 del 删除。

测试时使用 for 循环压入和取出了 4个数据,从结果可以看出,进出栈的顺序是后进先出。

最后出现异常是因为程序并不完善,取数据时多取了一个,列表的索引位置发生异常。

这段代码只是用于演示栈的基本结构,在实际使用中可以对栈压入的数据的最大数量、栈是否为空、异常等情况作出处理。

 

队列


队列也是一种特殊的表结构,它的特点是先进先出(FIFO),先进入队列的数据会先被取出。

我们也可以使用列表自定义队列结构,示例代码如下:

#!/usr/bin/python3
# -*- coding: utf8 -*-

'''
用列表实现一个自定义的队列结构
'''

class TestQueue:
    def __init__(self):
        self.queue = []

    # 入列
    def inQueue(self, data):
        self.queue.append(data)

    # 出列
    def outQueue(self):
        data = self.queue[0]
        del self.queue[0]
        return data


queue = TestQueue()
for i in range(1, 5):
    queue.inQueue(i)
    print(i, ': 入列')

for i in range(1, 6):
    print(queue.outQueue(), ': 出列')


'''
$  python3 10.py 
1 : 入列
2 : 入列
3 : 入列
4 : 入列
1 : 出列
2 : 出列
3 : 出列
4 : 出列
Traceback (most recent call last):
  File "10.py", line 29, in <module>
    print(queue.outQueue(), ': 出列')
  File "10.py", line 18, in outQueue
    data = self.queue[0]
IndexError: list index out of range
'''

本示例与栈非常相似,使用 append() 把数据加入到列表的末尾,但取数据时使用 queue[0] 取列表中的第一条数据,最后的执行结果是先入列的先被出列。

同样,在实际使用中要做更多的处理才能完善代码。

 


树是非线性的,由多个节点组成,节点之间是父子关系。

树必须有一个根节点作为起点,然后下面有多个子节点,子节点下面再有子节点。

同一级的节点如 A、B、C称为兄弟节点,根节点称为它们的父节点,它们也可以称为根节点的子节点。

节点下面没有子节点,如D、E、F称为叶子节点。

当数据较多时使用线性结构较慢,但树要比表、栈、队列的结构复杂,创建有一定难度,树在Python中可以直接使用列表创建。

最多有两个子节点的树称为二叉树,它是会经常使用的一种特殊的树结构。

下面我们自定义二叉树实现,示例代码如下:

#!/usr/bin/python3
# -*- coding: utf8 -*-

class Tree:
    def __init__(self, data):
        self.leftNode = None        # 左边子节点
        self.data = data            # 数据
        self.rightNode = None       # 右边子节点

    # 加入左边子节点
    def addLeft(self, data):
        self.leftNode = Tree(data)
        return self.leftNode

    # 加入右边子节点
    def addRight(self, data):
        self.rightNode = Tree(data)
        return self.rightNode

    def show(self):
        print(self.data)


root = Tree('根')
A = root.addLeft('A')
C = A.addLeft("C")
B = root.addRight('B')
D = B.addRight("D")
E = D.addLeft("E")
F = E.addRight("F")


root.show()
A.show()
B.show()
C.show()
D.show()
E.show()
F.show()


'''
$ python3 11.py
根
A
B
C
D
E
F
'''

因为二叉树最多只能有两个子节点,所以用 leftNode和rightNode表示。

可以看到二叉树的构建并不复杂,但是遍历树的方式并不简单,共有三种方式:先序遍历中序遍历后序遍历

先序遍历是先访问根,然后访问左子树,最后访问右子树。

中序遍历是先访问左子树,然后访问根,最后是右子树。

后序遍历是先访问左子树,然后访问右子树,最后访问根。

下面我们采用三种方式遍历上面创建的二叉树,示例代码如下:

# 先序遍历
def method1(node):
    if node.data:
        node.show()
        if node.leftNode:
            method1(node.leftNode)
        if node.rightNode:
            method1(node.rightNode)


# 中序遍历
def method2(node):
    if node.data:
        if node.leftNode:
            method2(node.leftNode)
        node.show()
        if node.rightNode:
            method2(node.rightNode)


# 后序遍历
def method3(node):
    if node.data:
        if node.leftNode:
            method3(node.leftNode)
        if node.rightNode:
            method3(node.rightNode)
        node.show()


print('先序遍历')
method1(root)

print('中序遍历')
method2(root)

print('后序遍历')
method3(root)


'''
先序遍历
根
A
C
B
D
E
F
中序遍历
C
A
根
B
E
F
D
后序遍历
C
A
F
E
D
B
根
'''

 

数据结构应用


对数据进行排序时我们在编程中经常要做的事情,常用的方法又冒泡排序、快速排序等,利用二叉树进行排序也是一种非常好的选择,而且便于操作。

下面我们对一组数字 "55, 12, 23, 6, 9, 60, 70, 8" 使用二叉树从小到大排序,示例代码如下:

#!/usr/bin/python
# -*- coding:utf-8 -*-

def add(node, value):
    # 如果值大于当前节点的数据
    if value > node.data:
        # 如果右边节点存在
        if node.rightNode:
            # 加入到当前节点的右节点
            add(node.rightNode, value)
        else:
            # 右节点不存在,把值赋给右节点
            node.addRight(value)
    else:
        # 如果左节点存在
        if node.leftNode:
            # 加入到当前节点的左节点
            add(node.leftNode, value)
        else:
            # 左节点不存在,把值赋给左节点
            node.addLeft(value)


datas = [55, 12, 23, 6, 9, 60, 70, 8]
root = Tree(datas[0])

for i in range(1, len(datas)):
    add(root, datas[i])

在对二叉树进行中序遍历,就可以得到从小到大的排序结果,示例代码如下:

print('中序遍历')
method2(root)

'''
中序遍历
6
8
9
12
23
55
60
70
'''

 

总结


表、栈、队列是线性结构,可以借助 Python 的列表实现。

二叉树可以很便利的实现排序功能。

评论