Python内置数据结构的分析和应用

摘要：分析了python内置数据结构，基于python内置数据结构构建了栈、队列、图等常用数据结构，并实现了图的深度优先遍历算法，python内置数据结构可组合实现高级数据结构，在数据处理相关算法中有着重要的应用。

关键词：python；数据结构；算法；图的遍历

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2013）33-7593-03

计算机信息处理依赖于有效算法的设计，信息处理时间是衡量算法有效性的重要测度，算法是基于特定的数据结构实现的，所以算法的设计与数据结构的选择会影响到算法的执行效率。算法程序的实现需要使用某种特定的语言，Python语言是一个混合体，丰富的工具集使它介于传统的脚本语言和系统语言之间，工具集中提供了Python内置数据结构作为语言的基本组成部分。

本文分析了python内置数据结构，基于python内置数据结构构建了栈、队列、图等数据结构，并实现了图的深度优先遍历算法，熟练应用python内置数据结构可以构建算法依赖的如树或图等较为复杂的数据结构，有助于大型开发项目数据信息的高效规范处理。

1 python内置数据结构

Python中有四种内置数据结构——列表、元组、字典和集合，它们用来存储一组相关数据，可以应用于简单的算法操作中。

1.1 列表

列表（list）是处理一组有序元素的数据结构，类似于java中的ArrayList，常作为函数的返回类型，列表中的元素应该包括在方括号中，每个元素之间用逗号分割。列表可以实现添加，删除，查找等操作，列表元素的值可以被修改。

列表的append方法将添加的元素排在列表的尾部，被添加的元素可以是元组、列表、字典等任何对象，remove方法删除指定元素，insert方法将给定元素添加到指定位置。列表支持分片、负索引操作和连接操作，所以列表是一种可变的数据类型。

列表的查找有两种方式，一种是使用index方法返回元素在列表中的位置，另一种方法是使用保留字in来判断元素是否在列表中。

列表分别用sort方法和reverse方法实现列表自身的排序和逆序。

1.2 元组

元组（tuple）相当于只读数组，由不同的元素组成，每个元素可以存储不同的元素，如字符串、数字甚至元组，元组中的元素应该包括在圆括号中，每个元素之间用逗号分割。

python中创建元组的过程成为打包，元组创建后其内部元素的值不能被修改，不能添加或删除任何元素，和字符串一样是不可变的。

元组中的元素可以通过索引方式即一对方括号指明某个元素的位置来访问，元组的下标可以为负数，即支持负索引、分片操作。

可以将元组的元素分别赋给各个变量，避免用循环去获取每个元素的值。可以用python内置函数range（）和len（）遍历元组，len（）计算出元组中元素的个数，range（）返回由一个数字组成的列表。

1.3 字典

字典（dictionary）是由键/值对组成的集合，值通过键来引用，键必须是唯一的且只能使用不可变的对象（比如字符串），值可以是不可变或可变的对象。

键/值之间用冒号分割，键/值对之间通过逗号隔开，并且被包含在一对花括号中，键/值对是没有顺序的。

通过一对方括号和索引可以访问字典。字典的添加、修改通过一条赋值语句如dict["x"]= value可以实现，如果x对应的值在字典中，则可以修改字典的内容，如果x对应的值不在字典中，则添加相应的字典元素。python内置函数del（）可以删除指定的字典元素。字典方法pop（）可以删除参数索引所指定的元素，方法clear（）可以清空整个字典。

通过字典方法items（）可以实现字典的遍历，items（）方法返回由若干元素组成的列表，items（）把字典中每对键/值组成了一个元组，并把这些元组放到列表中返回。

1.4 集合

集合（set）是没有顺序的简单对象的聚集。当在聚集中一个对象的存在比其顺序或者出现的次数重要时使用集合。使用集合，可以检查是否是成员，是否是另一个集合的子集，得到两个集合的交集。

2 python内置数据结构的应用

基于python的内置数据结构可以构建其它较复杂但更实用的数据结构，可供相关算法采用。下面主要实现了栈和队列的构建、图的表示和深度优先遍历算法的实现。

2.1 栈和队列的构建

栈是只允许在一端进行插入或删除的线性表，具有后进先出的操作特性。队列也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除，其操作特性是先进先出。栈和队列都可以基于python内置结构列表实现，进栈/队列用列表的append方法，出栈/队列用列表的pop方法，并且需要用python内置函数len检测列表的长度。栈和队列的实现类似，栈结构实现代码如下。

class Stack：

def __init__（self，size = 16）：

self.stack = []

self.size = size

self.top = -1

def setSize（self， size）：

self.size = size

def isStackEmpty（self）：

if self.top == -1：

return True

else：

return False

def isStackFull（self）：

if self.top +1 == self.size：

return True

else：

return False

def getTop（self）：

if self.isStackEmpty（）：

raise Exception（"StackIsEmpty"）

else：

return self.stack[self.top]

def push（self，obj）：

if self.isStackFull（）：

raise Exception（"StackOverFlow"）

else：

self.stack.append（obj）

self.top +=1

def pop（self）：

if self.isStackEmpty（）：

raise Exception（"StackIsEmpty"）

else：

self.top -= 1

return self.stack.pop（）

def show（self）：

print（self.stack）

2.2 图的表示和深度优先遍历算法实现

图G由顶点集V和边集E组成，如果点对是有序的，那么图就是有向图，无向图中顶点间的连接是没有方向的。若给定某有向图G1=（V，E），其中V={1，2，3，4，5，6}，E={（1，2），（1，4），（2，1），（2，3），（3，5），（4，3），（4，5）}，通过python内置列表和字典可实现图的表示，如graph={1：[2，4]， 2：[1，3]，3：[5]，4：[3，5]，5：[] }，graph是一个字典，每个键都是图的顶点，每个键的对应值是一个列表，列表包含与键所代表的顶点邻接的顶点。

图的深度优先遍历算法是指首先访问某个源顶点vi，然后由vi出发，访问与vi邻接且未被访问的任一顶点w1，再访问与w1邻接且未被访问的任一顶点w2，……，一次遍历能够访问图中的一个连通分量，访问的顶点和边存储在表示图结构的字典graph中，代码编写如下：

class Graph（）：

def __init__（self， graph）：

self.visited = []

self.visited = [0 for i in range（len（graph）+1）]

self.dict = graph

def DFSGraph（self， source）：

self.visited[source] = 1

print source，

if self.dict.get（source）：

for v in self.dict[source]：

if self.visited[v]==0：

self.DFSGraph（v）

图的深度优先遍历在有向无环图的拓扑排序或寻找图的关节点等算法中有重要的应用。

3 结束语

文中利用python内置数据结构构建了栈和图，实现了图的深度优先遍历算法，诸如二叉树、二叉排序树、散列表等程序中常用的数据结构，都可以在字典、列表等python内置结构基础上实现，多注重灵活运用内置数据结构将会提高解决程序实际问题的能力。

参考文献：

[1] David B.Python Cookbook[M].New York：O'Reilly Media，2013.

[2] Wesly M.Python for Data Analysis[M].New York：O'Reilly Media，2013.

[3] Robert S.Algorithms[M].New Jersey：Addison Wesley，2011.

[4] 石竑松，秦志光.对数空间可构造的无向图遍历序列[J].计算机工程与应用，2010，46（8）：11-15.

[5] Weiss D.Structures and Algorithm Analysis in Java[M].New Jersey：Addison Wesley，2012.