python 数据结构篇

1）FIFO先入先出队列--Queue

这是最基本的队列，先输入的元素会先输出。

#创建队列对象q = Queue(maxsize=0)#maxsize设置队列中数据上限，小于或等于0则不限制，容器中大于这个数则阻塞，直到队列中的数据被消掉#写入队列数据for i in range(3):    q.put(i)#输出当前队列所有数据print(type(q.queue),q.queue) #队列弹出下一元素cur = q.get()

2）LIFO后入先出队列（栈）

后入先出队列，后输入的元素会先输出。

这里的后入先出队列，就是栈。（以下的后入先出队列就先用栈代表）

栈，添加移除新项总发生在同一端。这一端通常称为“顶部”。与顶部对应的端称为“底部”。

我们先给出栈的queue模块实现：

#创建后入先出队列对象lq = LifoQueue(maxsize=0)#队列写入数据for i in range(3):    lq.put(i)#输出队列所有数据print(type(lq.queue),lq.queue)   #队列弹出下一元素cur = lq.get() 

当然，栈也可以通过顺序存储或者链式存储实现，由于栈的重要性，我们这里把这两种也实现一下。

顺序存储（列表实现）：

class Stack:     def __init__(self):#列表实现栈         self.items = []     def isEmpty(self):#判断栈是否为空         return self.items == []     def push(self, item):#将item入栈         self.items.append(item)     def pop(self):#出栈一次         return self.items.pop()     def peek(self):#返回栈顶元素         return self.items[len(self.items)-1]     def size(self):#返回栈的大小         return len(self.items)

链式存储（链表实现）：

#定义节点class note():    def __init__(self,item):        self.item=item#数据域        self.next=None#指针域#定义栈class stack():    def __init__(self):        self.head=None#头结点    def isempty(self):#判断栈是否为空        return self.head==None    def push(self,item):#item入栈        m=note(item)        c=self.head        m.next=c        self.head=m    def pop(self):#出栈一次        c=self.head        data=c.item        self.head=c.next        del c        return data    def peek(self):#返回栈顶元素        return self.head.item    def size(self):#返回栈的大小        c=self.head        s=0        while c:            c=c.next            s+=1        return s    def printall(self):#遍历栈中元素        c=self.head        while c:            print(c.item,end=" ")#遍历操作：打印            c=c.next

3）优先级队列

优先级队列作为一种特殊的队列，会给各数据设置优先级（决定入栈和出栈的顺序）

#创建优先级队列对象pq = PriorityQueue(maxsize=0)#写入队列(优先级会按输入对象的第一个元素排序)pq.put((9,'a'))pq.put((7,'c'))pq.put((1,'d'))#输出队例全部数据print(pq.queue)    #[(1, 'd'), (9, 'a'), (7, 'c')]#队列弹出下一元素(按优先级)pq.get()

当然，通过堆（heapq库）也可以实现优先级队列，但是堆本质上还是一种完全二叉树。下面我们在树的部分会详细地解释堆。

4）双端队列

双端队列也是一种特殊的队列，其入队列和出队列可以在队列的两边同时进行，这样的队列更符合实际问题中一般的模型。

#创建双端队列对象dq = deque(['a','b'])dq.append('c')#增加数据到队尾 dq.appendleft('d')#增加数据到队左 dq.pop()#移除队尾dq.popleft()#移除队左

上述的线性数据结构都是一对一类型的结构。但实际生活中往往用到最多的是一对多或者多对多的非线性数据结构。当然，顺序存储显然是不适用于非线性数据结构，所以接下来我们将使用链式存储结构实现非线性数据结构。

1.树（一对多）

直观地看，树是数据元素（在树中称为结点）按分支关系组织起来的结构，很像自然界中的树那样。

树的一些基础概念：
节点的度：一个节点含有的子树的个数称为该节点的度；

树的度：一棵树中，最大的节点的度称为树的度；

叶节点或终端节点：度为零的节点；

节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；

树的高度或深度：树中节点的最大层次；

路径：对于一棵子树中的任意两个不同的结点，如果从一个结点出发，按层次自上而下沿着一个个树枝能到达另一结点，称它们之间存在着一条路径

在树里面有一种特殊的树--二叉树，即每个节点最多含有两个子树的树。在数据结构占据着非常重要的地位。有些说法认为二叉树不属于树，但是这里我们暂且放到这里介绍二叉树。因为二叉树的实现，是普通的树以及森林实现的重要基础。

1）二叉树

完全二叉树：对于一颗二叉树，假设其深度为d(d>1)。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树，其中满二叉树的定义是所有叶节点都在最底层的完全二叉树;

数学性质：
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.由遍历构造二叉树（至少需要两组遍历）
后序遍历的第一个字符就是根，因此只需在中序遍历中找到它，就知道左右子树的中序 和后序遍历了。

实现（链式存储）

#定义树的结点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        

也可以采用嵌套列表的方式实现二叉树，但形式较为复杂（数据项很少很少时可以使用），不建议使用。

应用：

1. 排序二叉树：用于二叉排序算法
2. 最优二叉树（赫夫曼树）：用于解决编码问题
3. 平衡二叉树：应用较广泛，此处不作介绍

联动：二叉树与优先级队列--堆

堆（heap）是一种优先队列。本质上讲，它是一个完全二叉树，实现的时候不需要建造一个树，改用一个数组即可。若一个节点的索引为i，那么，父节点的索引为（i-1）//2，左孩子节点编号为i*2+1，右孩子节点为i*2+2。

堆的特点：

1. 内部数据是有序的
2. 可以弹出堆顶的元素，大根堆就是弹出最大值，小根堆就是弹出最小值
3. 每次加入新元素或者弹出堆顶元素后，调整堆使之重新有序，时间复杂度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）图的分类

1. 无向图：两个顶点之间可以沿着边互相访问，双向连通。
2. 有向图：两个顶点之间只能以弧的箭头方向进行访问，单向连通。

图的连通性：

对于无向图，其连通子图（连通分量）称为连通图

对于有向图，其连通子图（强连通分量）称为强连通图

若任意节点之间均连通，称为完全图。

2）图的实现

 图的实现有四种方法：

1. 邻接矩阵
2. 邻接表
3. 十字链表
4. 邻接多重表

邻接矩阵

用具体的数值表示节点之间的关系，可以使用邻接矩阵，假设这个矩阵是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)

这里我们不妨与二叉树的遍历作对比，发现深度遍历都是采用递归的方法，广度遍历都是采用队列的方式。其实，由此可以看出图可以用树表示出来，我们习惯上将图的极小连通子图称为生成树。

十字链表

十字链表适用于有向图，操作时也较为方便，但是结构较为复杂，整体的时间复杂度和邻接表一样。

 十字链表的结点描述：

顶点结点：

1. 数据域
2. 两个链域指示以该顶点为弧头、弧尾的第一个弧结点

弧结点：

1. 数据域指示弧的信息
2. 两个链域指向弧尾相同的下一条弧和弧头相同的下一条弧
3. 尾域和头域指示弧头和弧尾这两个结点在图中的位置

#定义顶点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语言的《数据结构与算法》。

遍历

深度优先搜索（DFS）--类似于树的先序遍历

广度优先搜索（BFS）

最小生成树

Prim算法

适用于求边稠密的图，时间复杂度O（n^2）

1. 设置辅助数组记录并不断更新具有过程中到达不同顶点最小代价的边
2. 从一个顶点开始，重复找代价最小的边，并不再考虑到达该边另一顶点，同时更新辅助数组

Kruskal算法

时间复杂度O(e·loge)

每个顶点先各成连通分量，再在所有边里选择代价最小的边，若该边的顶点落在不同的连通分量上，则选择该边

最短路径

Dijkstra算法（单源最短路径）

时间复杂度O(n^2)

1. 建立一维辅助数组存储起点到各结点的最短路径的长度
2. 先将起点到各点路径存入辅助数组，然后循环找到辅助数组中路径的最小值，确定起点到该点的最短路径已找到，同时更新辅助数组

Floyd算法（多源最短路径）

时间复杂度O(n^3)

1. 建立二维辅助数组存储各结点到其他结点的最短路径的长度
2. 先将各点之间路径存入辅助数组，再循环判断各个路径是否为最短路径：循环比较该路径与以其他结点为中间结点得到的路径大小，然后更新该路径值

以上便是python中数据结构的实现，可能有某些方面讲的有些问题或者不够详细，欢迎私信或者评论区提出您的意见。

感谢您的阅读！！！

来源地址：https://blog.csdn.net/qq_62047219/article/details/125618390