行业知识
python 数据结构篇
在众多���程语言里，数据结构与算法都可以说是至关重要的基础。但是对于python而言，因为其本身就是用C实现的，其速度和效率本身较低，因而pyhon没有像其他语言那样那么重视数据结构与算法（python最引以为傲的应该是其功能强大而丰富的各种库和模块）。对于很多像我一样的新手小白，时间复杂度似乎也不是硬要求，实现功能就行了。本节我们主要介绍用python实现数据结构。
对于数据结构，我们将采用以下的思路进行学习：
一、定义对象、节点
1.线性结构：
数组、链表、队列、栈
2.非线性结构：
树、堆、图
二、实现节点之间的互联
在节点属性中增加指针
三、对象由某一节点处开始的遍历
1.线性结构
1）单向遍历
2）双向遍历
2.非线性结构
1）DFS（深度优先搜索）
2）BFS（广度优先搜索）
四、基本操作方法
1.增加节点
2.返回节点数量
3.由遍历结果构建对象
目录
一、线性数据结构（一对一）
1.数组
1）构造一个数组对象
2）查找数组信息
3）删除操作
4）添加操作
5）转换操作
6）文件操作
7)排序
2.链表
1）单向链表
2）双向链表
3）双向循环链表
3.队列（queue模块）
队列方法：（适用于所有的队列）
1）FIFO先入先出队列--Queue
2）LIFO后入先出队列（栈）
3）优先级队列
4）双端队列
二、非线性数据结构
1.树（一对多）
1）二叉树
联动：二叉树与优先级队列--堆
2）树
3）森林
2.图（多对多）
1）图的分类
2）图的实现
邻接矩阵
邻接表
十字链表
邻接多重表
3）图的算法
遍历
最小生成树
最短路径
一、线性数据结构（一对一）
1.数组
数组
python使用其内置的模块array实现数组，python的数组就和C语言一样精简而高效。
1）构造一个数组对象
array.array(typecode[, initializer])# 例：构造一个空的int类型数组arr = array('i')arr = array('i', [0, 1, 2, 3, 4, 6, 7, 8, 9, 100]) 由于python没有对于变量声明的要求，所以在创建数组时需要一个类型代码字符标识该数组的数据类型，这样数组才能像C语言里的数组一样操作。
python中数组的类型代码字符2）查找数组信息
array.typecode用于创建数组的类型代码字符。array.typecodes包含所有可用类型代码的字符串。即'bBuhHiIlLqQfd'array.itemsize内部表示中一个数组项的字节长度。array.index(x)方法返回x 在数组中第一次出现的下标, 下标从零开始,如果没有找到该元素会报异常.array.buffer_info() 返回一个表示当前数组存储信息的元组(address, length)array.count(x)返回 x 在数组中出现的次数,没有该元素则返回0
3）删除操作
array.remove(element) element 是要删除的元素, 该方法会删除第一次出现的元素, 如果有多次出现, 不会删除。 如果删除的元素的不在 array 中, 则会抛异常 array.pop() 删除元素,默认删除下标-1 的元素, 也可以指定删除的位置,并返回被删除的元素
4）添加操作
array.insert (i,v) i 是索引位置, v 是插入的元素array.append(x) 默认从末尾追加元素, 在数组尾部添加元素xarray.extend(可迭代对象) 通过一个可迭代对象添加元素array.fromlist (list) 从一个列表中添加元素到数组
5）转换操作
array.tolist() 把array对象转换成list array.frombytes(s) 把bytes转换成array对象 array.tobytes() 把array对象转换成bytes
6）文件操作
array.fromfile(f, n) 从f中读取n个元素, 如果n> file中的个数,会报异常.array.tofile(f) 把array对象写到文件f中.
7)排序
array.sorted()排序数组，参数同可迭代对象里的sorted()array.reverse()反转数组
由以上的操作方法可知，python中的数组不仅可以像C语言中的数组一样进行操作，还支持像python中的可迭代对象一样的操作，以及一些其他的方法。
但是数组只能存储相同类型的数据，而列表可以存储不同类型的数据。而数组的存储效率和访问速度要快于列表。因此读者要根据实际情况适当选择。
2.链表
链表在python中使用类（相当于C中的结构）实现链表，实现方法也同C语言一样，但是python中没有指针的概念，于是就采用嵌套的方式，将一个实例赋给指针域，效果就同指针一样。但是同C一样，这样的做法，需要实例化对象起指针的作用，这样会降低数据的存储密度。
1）单向链表
单向链表
#定义结点：#数据域：item 存储节点上的信息#指针域：next 存储下一个节点的变量信息（可以理解为C里面的指针）class node(): def __init__(self,item): self.item=item self.next=None#定义单链表class SingleLinkedList(): def __init__(self): self.head=None #存储头结点（指向第一个节点） def add(self,item):#向链表头部中加入元素item t=node(item) t.next=self.head self.head=t def append(self,item):#向链表尾部中加入元素item t=node(item) if self.head==None: self.head=t else: m=self.head while m.next: m=m.next m.next=t def insert(self,index,item):#向链表索引为index处中加入元素item if index==0: self.add(item) elif index>=self.size(): self.append(item) else: t=node(item) c=self.head i=0 while iself.size(): self.append(item) else: i=0 while iself.size(): self.append(item) elif index==0: self.add(item) else: i=0 while i 0 不保证后续的 get() 不被阻塞，qsize()1)。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树，其中满二叉树的定义是所有叶节点都在最底层的完全二叉树; 二叉树1.数学性质：
1）在二叉树的第i层上至多有2^(i-1)个结点（i>0）
2）深度为k的二叉树至多有2^k - 1个结点（k>0）
3）对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1;
4）具有n个结点的完全二叉树的深度必为 log2(n+1)
5）对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲的编号必为i/2（i＝1 时为根,除外）
2.遍历方法
1）深度遍历：沿着树的深度遍历树的节点，尽可能深的搜索树的分支
深度遍历有三种方式：
（1）先序遍历的顺序为：根节点->左子树->右子树；
（2）中序遍历为：左子树->根节点->右子树；
（3）后序遍历是：左子树->右子树->根节点；
其中的序指的是根节点相对于左右节点的遍历位置。
2）广度遍历：从树的根层级开始一层一层的遍历，遍历完上一层再遍历下一层
3.由遍历构造二叉树（至少需要两组遍历）
后序遍历的第一个字符就是根，因此只需在中序遍历中找到它，就知道左右子树的中序 和后序遍历了。
4.实现（链式存储）
#定义树的结点class node(): def __init__(self,item,left=None,right=None): self.item=item#数据域 self.left=left#左子树 self.right=right#右子树#定义树class tree(): def __init__(self,root=None): self.root=root #每加满一个节点，在其左节点下继续加 def add(self,item): t=node(item) if self.root==None: self.root=t return q=[self.root] while q: c=q.pop() if c.left==None: c.left=t return elif c.right==None: c.right=t return else: q.append(c.right) q.append(c.left) #插入节点，order为插入位置，'L'为左子树，'R'为右子树 def insert(self,root,item=None,order='L'): if root==None: root=node(item) return if order=='L': if root.left: if root.left.item: return else: root.left.item=item else: root.left=node(item) elif order=='R': if root.right: if root.right.item: return else: root.right.item=item else: root.right=node(item) else: raise ValueError("insert:order error") #深度遍历（递归实现） def preorder(self,root):#先序遍历 if not root: print("",end="") else: print(root.item,end=" ") self.preorder(root.left) self.preorder(root.right) def inorder(self,root):#中序遍历 if not root: print("",end="") else: self.inorder(root.left) print(root.item,end=" ") self.inorder(root.right) def postorder(self,root): #后序遍历 if not root: print("",end="") else: self.postorder(root.left) self.postorder(root.right) print(root.item,end=" ") #广度遍历（队列实现） def broad(self,root): if not root: print("",end="") q=[root] while q: for i in range(len(q)): t=q.pop(0) print(t.item,end=" ") if t.left: q.append(t.left) if t.right: q.append(t.right) #根据中序遍历和后序遍历构造树，返回树根 def con(self,mid,post,root): if mid==[]: return None else: r=post[-1] root=node(r) n=mid.index(r) leftmid=mid[:n] rightmid=mid[n+1:] leftpost=find(leftmid,post) rightpost=find(rightmid,post) root.left=self.con(leftmid,leftpost,root.left) root.right=self.con(rightmid,rightpost,root.right) return root #返回由路径元组构成的列表 def path(self,root): def addpath(root,list1,s): if not root.left and not root.right: s+=(root.item,) list1.append(s) else: s+=(root.item,) if root.left: addpath(root.left,list1,s) if root.right: addpath(root.right,list1,s) list1=[] addpath(root,list1,()) return list1也可以采用嵌套列表的方式实现二叉树，但形式较为复杂（数据项很少很少时可以使用），不建议使用。
5.应用：
- 排序二叉树：用于二叉排序算法
- 最优二叉树（赫夫曼树）：用于解决编码问题
- 平衡二叉树：应用较广泛，此处不作介绍
联动：二叉树与优先级队列--堆
堆（heap）是一种优先队列。本质上讲，它是一个完全二叉树，实现的时候不需要建造一个树，改用一个数组即可。若一个节点的索引为i，那么，父节点的索引为（i-1）//2，左孩子节点编号为i*2+1，右孩子节点为i*2+2。
堆的特点：
最小堆 最大堆
- 内部数据是有序的
- 可以弹出堆顶的元素，大根堆就是弹出最大值，小根堆就是弹出最小值
- 每次加入新元素或者弹出堆顶元素后，调整堆使之重新有序，时间复杂度O(logn)
python实现堆时使用其内置的模块heapq
heapq模块
heappush(heap, x)：将x压入堆heap中 请注意，不能将它用于普通列表，而只能用于使用各种堆函数创建的列表， 原因是元素的顺序很重要，元素的排列顺序并不像看起来那么随意。 它们虽然不是严格排序的，但必须保证一点： 位置i处的元素总是大于位置i // 2处的元素（反过来说就是小于位置2 * i和2 * i + 1处的元素）。 这是底层堆算法的基础，称为堆特征（heap property）。heappop(heap)：从堆heap中弹出最小的元素 最小的元素总是位于索引0处，并确保剩余元素中最小的那个位于索引0处（保持堆特征）。heapify()：让列表heap具备堆特征 通过执行尽可能少的移位操作将列表变成合法的堆（即具备堆特征）。 如果你的堆并不是使用heappush创建的，应在使用heappush和heappop之前使用这个函数。heapreplace(heap, x)：弹出最小的元素，并将x压入堆中 相比于依次执行函数heappop和heappush，这个函数的效率更高。nlargest(n, iter)和nsmallest(n, iter)，:分别用于找出可迭代对象iter中最大和最小的n个元素。 这种任务也可通过先排序（如使用函数sorted）再切片来完成， 但堆算法的速度更快，使用的内存更少（而且使用起来也更容易）。对于最大堆，即双亲结点大于孩子节点的情况，该模块保留了一些方法：
_heappop_max(heap)：相当于最小堆的heappop方法_heapify_max(heap) ：相当于最小堆的heapify方法_heapreplace_max(heap, x)：相当于最小堆的heapreplace方法注意：对于最大堆的操作没有_heappush_max方法
当然，给数据加负号也可以实现最小堆到最大堆的转化
2）树
树
实现了二叉树之后，对于树的实现就很容易了。
实现方法1：孩子双亲表示法
class TreeNode(): def __init__(self, name, parent=None): self.name = name#数据域 self.parent = parent#双亲结点 self.child = []#用列表存储所有的子节点当然也可以使用单链表代替列表来存储子节点。
实现方法2：孩子兄弟表示法
class TreeNode(): def __init__(self, name, child,bro): self.name = name#数据域 self.child = child#第一个孩子结点 self.bro = bro#第一个兄弟结点由孩子兄弟表示法可以发现，树是以二叉树的形式实现的，接下来要说的森林也是一样的实现方法。
3）森林
森林：由m（m>=0）棵互不相交的树的集合称为森林
实现方法：孩子兄弟表示法
树的孩子兄弟表示法里，如果根节点为空，则树就是森林。
这里我们不能发现，二叉树、树、森林之间可以互相转换。
2.图（多对多）
在推广一下树的话，就到了多对多的图了。图可以更好地拟合实际问题，但是也最为复杂。
图的基本概念：
边（弧）：两个顶点之间
路径:：通过边连接的顶点序列
周期：第一个和最后一个顶点相同的路径
入度:：顶点的度数V是以V为端点的边数
出度： 顶点的出度v是以v为起点的边的数量
度：顶点的度数是其入度和出度的总和
1）图的分类
无向图 有向图
- 无向图：两个顶点之间可以沿着边互相访问，双向连通。
- 有向图：两个顶点之间只能以弧的箭头方向进行访问，单向连通。
图的连通性：
对于无向图，其连通子图（连通分量）称为连通图
对于有向图，其连通子图（强连通分量）称为强连通图
若任意节点之间均连通，称为完全图。
2）图的实现
图的实现有四种方法：
- 邻接矩阵
- 邻接表
- 十字链表
- 邻接多重表
邻接矩阵
用具体的数值表示节点之间的关系，可以使用邻接矩阵，假设这个矩阵是A,Aij就表示第i个节点和第j个节点是否相连，为1表示相连，0表示不相连。当然，该数值也可以是边或者弧的权值。
邻接矩阵class graph: def __init__(self,vertex,directed=False): vertex=list(set(vertex)) self.vertex=vertex #顶点列表 self.num_edge=0 #边的数量 self.directed=directed#是否有向图 self.matrix=[[0 for i in range(len(vertex))]for i in range(len(vertex))]#邻接矩阵 #以邻接矩阵遍历图 def draw(self): print(' ',self.vertex) for i in range(len(self.matrix)): print(self.vertex[i],self.matrix[i]) #加边（权值默认为1） def addedge(self,v,w,weight=1): if v in self.vertex and w in self.vertex: i=self.vertex.index(v) j=self.vertex.index(w) self.matrix[i][j]=weight if self.directed==False: self.matrix[j][i]=weight self.num_edge+=1 else: raise Exception("vertex not in the Graph") #为图加入节点 def addvertex(self,v): if v in self.vertex: return self.vertex.append(v) for i in self.matrix: i.append(0) self.matrix.append([0]*len(self.vertex))注意：应当先加入节点，再加入边。
缺点：浪费存储空间。
优点：便于访问与遍历。
适合表示稠密图。
邻接表
对于邻接表来说，一行只代表和他相连的节点。
邻接表class vertex(): def __init__(self,item): self.item=item self.connect={}class graph(): def __init__(self,v=[],directed=False): v=list(set(v)) self.vertex={} self.directed=directed for i in v: self.vertex[i]=vertex(i) #画图 def draw(self): for i in self.vertex.keys(): print(i,end=':') for j,k in self.vertex[i].connect.items(): print(j,'(',k,')',sep='',end=' ') print('') def addvertex(self,item): if not item in self.vertex: self.vertex[item]=vertex(item) def addedge(self,v,w,weight=1): if not v in self.vertex: self.addvertex(v) if not w in self.vertex: self.addvertex(w) self.vertex[v].connect[w]=weight if self.directed==False: self.vertex[w].connect[v]=weight #深度优先搜索 def DFS(self,v): l=[] def f(v,l): if v in l: return print(v,end=' ') l.append(v) p=self.vertex[v].connect.keys() for i in p: f(i,l) f(v,l) print('') #广度优先搜索 def BFS(self,v): q=[v] l=[v] while q!=[]: u=q.pop(0) print(u,end=' ') t=self.vertex[u].connect.keys() for i in t: if i in l: continue l.append(i) q.append(i)这里我们不妨与二叉树的遍历作对比，发现深度遍历都是采用递归的方法，广度遍历都是采用队列的方式。其实，由此可以看出图可以用树表示出来，我们习惯上将图的极小连通子图称为生成树。
十字链表
十字链表适用于有向图，操作时也较为方便，但是结构较为复杂，整体的时间复杂度和邻接表一样。
十字链表的结点描述：
顶点结点：
- 数据域
- 两个链域指示以该顶点为弧头、弧尾的第一个弧结点
弧结点：
- 数据域指示弧的信息
- 两个链域指向弧尾相同的下一条弧和弧头相同的下一条弧
- 尾域和头域指示弧头和弧尾这两个结点在图中的位置
#定义顶点class vertex(): def __inif__(self,data,firstin,firstout): self.data=data#数据域 self.firstin=firstin#以该顶点为弧尾的第一个弧结点 self.firstout=firstout#以该顶点为弧头的第一个弧结点#定义弧class edge(): def __inif__(self,info,tailvex,headvex,hlink,tlink): self.info=info#数据域，一般表示弧的权值 self.tailvex=tailvex#弧尾结点在图中（顶点链表）的位置 self.headvex=headvex#弧头结点在图中（顶点链表）的位置 self.hlink=hlink#弧头相同的下一条弧 self.tlink=tlink#弧尾相同的下一条弧#定义十字链表class crossinglink(): def __inif__(self): self.vertex=[]#顶点列表邻接多重表
邻接多重表适用于无向图，但其结构同十字链表一样，唯一的不同是其顶点结点的链域只有第一天依附于该节点的边（显然无向图没有弧头弧尾一说，故只需要一条边）。
由于与十字链表基本相同，这里不再赘述，读者可自行练习。
3）图的算法
我们之前有说，算法不是python的特色，这里只是简单介绍一下图里面的基本算法的思路，具体实现可以参考C语言的《数据结构与算法》。
遍历
1.深度优先搜索（DFS）--类似于树的先序遍历
2.广度优先搜索（BFS）
最小生成树
1.Prim算法
适用于求边稠密的图，时间复杂度O（n^2）
- 设置辅助数组记录并不断更新具有过程中到达不同顶点最小代价的边
- 从一个顶点开始，重复找代价最小的边，并不再考虑到达该边另一顶点，同时更新辅助数组
2.Kruskal算法
时间复杂度O(e·loge)
每个顶点先各成连通分量，再在所有边里选择代价最小的边，若该边的顶点落在不同的连通分量上，则选择该边
最短路径
1.Dijkstra算法（单源最短路径）
时间复杂度O(n^2)
- 建立一维辅助数组存储起点到各结点的最短路径的长度
- 先将起点到各点路径存入辅助数组，然后循环找到辅助数组中路径的最小值，确定起点到该点的最短路径已找到，同时更新辅助数组
2.Floyd算法（多源最短路径）
时间复杂度O(n^3)
- 建立二维辅助数组存储各结点到其他结点的最短路径的长度
- 先将各点之间路径存入辅助数组，再循环判断各个路径是否为最短路径：循环比较该路径与以其他结点为中间结点得到的路径大小，然后更新该路径值
感谢您的阅读！！！
