Python常用算法学习（四）数据结构最全总结（原理+代码）

N.Wirth：“程序=数据结构+算法”

数据：数据是信息的载体。它是可以输入计算机并被计算机识别、存储和处理的符号的总称。

数据元素：数据元素是数据的基本单位，也称为记录。通常，数据元素由几种基本类型（或字段、域、属性）组成。

2，数据结构的分类

数据结构按其逻辑结构可分为线性结构、树形结构和图结构。

线性结构：数据结构中的元素具有一对一的关系。树结构：数据结构中的元素具有一对多的关系。图结构：数据结构中的元素具有多对多的关系。

3，存储结构

010- 1010 1. 计算机内存中数据逻辑结构的映像（或表示）。 2、存储结构是通过计算机程序实现的，所以取决于具体的计算机语言。

1，特点

1.顺序存储（Sequential Storage）：将数据结构中的元素按照逻辑顺序存储在内存中连续的存储空间中。 2. Linkend Storage：将数据结构中的每个元素分布到内存中未上电的部分，并通过记录下一个节点的位置来建立它们之间的连接。最终得到的存储结构就是链式存储结果。 3、索引存储：存储数据的同时，额外创建一个索引表，即索引存储结构=数据文件+索引表。

2，存储结构分类

常用的数据结构

列表（在其他语言中称为数组，但数组和Python 列表还是有区别）是一种基本数据类型。

列表，在Python中称为列表，用方括号括起来，内部元素用逗号分隔。内部元素可以是任何类型，包括null。

1，列表

1.数组元素类型必须相同，但Python列表不需要2.数组长度是固定的，但Python列表可以添加。 Python列表的操作方法请参考这篇博客：https://www.cnblogs.com/wj-1314/p/8433116。 html

1.1 数组和列表不同点

Tuple，Python中的类是tuple。使用括号括起来，内部元素用逗号分隔，可以是任意值。与列表的区别在于其内部元素不能修改，也不能删除或更新。

注意：当元组只有一个元素时，末尾必须加一个逗号。如果不添加逗号，Python解释器会将其解释为元素本身的类型，而不是元组类型。

例如：

a=(1,2,3)b=('1',[2,3])c=('1','2',(3,4))d=()e=(1,) :010 -1010 通过下标操作

通过下标获取元素值，使用方法与列表切片的处理相同。使用方法与列表相同。不能通过下标进行删除和更新操作，如下所示。进行修改和删除会报异常：

c[0]=1Traceback（最近一次调用最后）:File''，第1 行，inTypeError:'tuple'对象不支持项目分配del c[0]Traceback（最近一次调用最后）:File''，第1 行，inTypeError:'tuple ' 对象不支持项目删除

2，元组

元组本身是不可变的，但您可以使用+ 来形成新的元组。

a(1, 2, 3)b('1', [2, 3])a + b(1, 2, 3,'1', [2, 3]) 您可以使用内置的在函数len Length中，可以使用*元素来实现元素的重复

a=(1,2,3)len(a)3a*3(1, 2, 3, 1, 2, 3, 1, 2, 3) 元组还支持in 和not in 成员运算符。

2.1 元组的操作

集合用于包含一组无序的对象。与列表和元组不同，集合是无序的并且不能以数字方式索引。此外，集合中的元素不能重复。 set 和dict 一样，只是没有值，相当于dict 的键集合。由于dict的key不重复，且key是不可变的对象，所以set有以下特点：

1.无重复，（互性），也就是说集合本质上是去重的。 2. 元素是不可变的对象（确定性的，元素必须是可散列的）。 3.集合的元素没有顺序，（无序））Python的集合和数学中的集合是一样的。它们也有交集、并集和集合。

举例如下：

s1={1,2,3,4,5}s2={1,2,3}s3={4,5}s1s2 # 交集{1, 2, 3}s1|s2 # 并集{1, 2, 3 , 4, 5}s1 - s2 # 差分集{4, 5}s3.issubset(s1) # s3 是s1 的子集Trues1.issuperset(s2) # s1 是s2 的超集True more set 相关操作参考博客： https://www.cnblogs.com/wj-1314/p/8423273.html

2.2 运算符及内建函数操作

Stack是一个数据集合，可以理解为一个只能在某个section中插入或删除的列表。

栈的特点：LIFO（后进先出）

栈的概念是：栈顶、栈底

栈的基本操作：

压入栈（push）： 压出栈： pop 从栈顶获取： gettop 对栈的理解就像一摞书，只能从栈顶放入和取出。

3，集合

可以使用通用列表结构来实现堆栈：

入栈：li.append 出栈：li.pop 取栈顶：li[-1] 现在我们写一个类来实现：

classStack:def __init__(self):self.stack=[]def push(self, element):self.stack.append(element)def pop(self):# 从列表中移除一个元素（默认为last）并返回该元素的值returnself.stack.pop()def get_top(self):iflen(self.stack) 0:returnself.stack[-1]else:returnNonestack=Stack()stack.push(1)stack.push(2)print(stack.pop( )) #2

4，栈

我们可以通过堆栈来解决括号匹配的问题，也就是解决IDE实现括号不匹配成功报错的问题。

代码：

classStack:def __init__(self):self.stack=[]def push(self,element):returnself.stack.append(element)def pop(self):returnself.stack.pop()def get_top(self):iflen(self.stack) 0:returnself .stack[-1]else:returnNonedef is_empty(self):returnlen(self.stack)==0def braces_match(s):match={'}':'{',']':'[',')':'(' }stack=Stack()forchins:ifchin{'(','[','{'}:stack.push(ch)else:ifstack.is_empty():returnFalseelif stack.get_top()==match[ch]:stack.pop()else:returnFalseifstack. is_empty():returnTrueelse:returnFalseprint(brace_match('{[{()}]}'))

4.1 栈的实现

队列是一种数据集合，只允许在链表的一端插入，另一端删除，它是在链表的尾部。队列，插入动作称为入队或入队列，执行删除动作的一端称为前端，删除动作称为出队。

队列的性质：先进先出

队列可以并发调度多个线程来处理排列好的线程。每个需要处理的线程只需要将请求的数据放入队列容器的内存中即可。线程不需要等待。当安排完成，数据处理完毕后，线程就按时拿到数据了。请求数据的线程只与这个队列容器有关系。处理数据的线程的关闭不会影响请求数据的线程。队列会分配其他线程来处理数据，这就实现了解耦。提高效率。队列中将会有一个顺序容器。列表和此容器之间存在差异。虽然列表中的数据是排列好的，但是移除后数据仍会保留，而队列中这些容器的数据移除后不会保留。当信息必须在多个线程之间安全交换时，队列在线程编程中特别有用。

4.2 栈的应用——括号匹配问题

队列可以简单地用列表实现吗？为什么？

队列实际上是一个先进先出的线性列表。删除操作只能在队头进行，插入操作可以在队尾进行。队列用列表表示，使用append()方法在队列尾部插入元素，使用pop(0)方法。实现队列头部元素的删除。

观察上图，我们会发现链表的最左边（最上面）被视为队列头，最右边（最底下）被视为队列尾（左头、右尾、顶头、底尾） ，使用insert()或append()方法实现在队列尾部插入元素，pop()方法实现从队列尾部删除元素。

5，队列

环形队列：当队列尾指针front==MaxSize + 1时，前进一位自动到0。

队列头指针前进1：front=(front + 1) % MaxSize 队列尾指针前进1：rear=(rear + 1) % MaxSize 队列空条件：front==后队列满条件：(rear + 1) % MaxSize==frontclassQueue:def __init__(self, size):self.queue=[0for_inrange(size)]self.size=sizeself.rear=0 # 队列的尾指针就是进入队列的那个self.front=0 # 第一个指针是退出队列的指针def push (self, element):ifnot self.is_filled():rear=(self.rear + 1) % self.sizeself.queue[self.rear]=elementelse:raise IndexError( '队列已满')def pop(self):ifnot self.is_empty ():self.front=(self.front + 1) % self.sizereturnself.queue[self.front]else:raise IndexError('队列为空')#判断队列为空def is_empty(self):returnself.rear==self.front # 判断队列已满def is_filled(self):return(self.rear + 1) % self.size==self.frontq=Queue(5) foriinrange(4):q.push(i)print(q.pop())fromcollections import dequeq=deque()q.append(1) # 队列尾部进入队列print(q.popleft()) #队头退出# 用于双向队列q.appendleft(1) # 队头进入队列print(q. pop()) #在队列尾部使双向队列出队的完整用法：

# _*_coding:utf-8_*_# 创建双向队列fromcollections import dequed=deque()# 追加（在右侧添加一个元素） d.append(1)d.append(2)print(d) # deque ([1, 2])#appendleft(向左添加一个元素) d.appendleft(11)d.appendleft(22)print(d)#deque([22,11,1,2])#clear清除queue d.clear() print(d) # deque([])# 浅拷贝copyd.append(1)new_d=d.copy()print(new_d) # deque([1])# count (返回数量指定元素的出现次数) d.append (1)d.append(1)print(d) # deque([1, 1, 1])print(d.count(1)) # 3#extend (扩展元素队列右侧的列表) d.append (2)d.extend([3, 4, 5])print(d) # deque([1, 1, 1, 2, 3, 4, 5] )#extendleft(从队列左侧扩展列表的元素) d.extendleft([3,4,5])print(d)#deque([5,4,3,1,1,1,2 , 3, 4, 5])#index(查找某个元素位置的索引) d.clear()d.extend(['a','b','c','d','e']) print(d)print(d.index('e'))print( d.index('c', 0, 3)) #指定搜索间隔'''deque(['a','b',' c','d','e'])42'''# insert (在指定位置插入元素) d.insert(2,'z')print(d)# deque(['a', 'b' ', 'z', 'c', 'd', 'e']) # pop (获取最右边的元素并在队列中删除) x=d.pop()print(x)print(d)'' 'edeque(['a','b','z','c ','d'])'''# popleft(获取最左边的元素并在队列中删除) print(d)x=d. popleft()print(x)print(d)'''deque([ 'a','b','z','c','d'])adeque(['b','z',' c','d'])'''#remove(删除指定元素)print(d)d.remove('c')print(d)'''deque(['b','z',' c','d'])deque(['b','z' ,'d'])'''#反向(队列反向) print(d)d.reverse()print(d)'''deque (['b','z','d'])deque( ['d','z','b'])'''# 旋转(将右边的元素放到左边) d.extend([ 'a','b','c','d','e '])print(d)d.rotate(2) # 指定次数，默认为1 print(d)'''deque (['d','z','b','a','b','c','d','e'])deque(['d','e','d', 'z','b','a','b','c'])' ''

5.1 队列的实现

队列：先进先出的FIFO

LifoQueue：LIFO 是后进先出

PriorityQueue：优先级队列，级别越低，优先级越高

deque：双边队列

导入三个队列，包括

fromqueue 导入队列、LifoQueue、PriorityQueue

环形队列的实现方式

#基本FIFO队列先进先出FIFO就是先进先出，先进先出#maxsize设置队列中数据的上限。如果小于或等于0，则没有限制。如果容器中的数量大于这个数量，就会阻塞，直到队列中的数据消除q=Queue(maxsize=0)#写入队列数据q.put(0)q.put(1)q.put( 2)#输出当前队列的所有数据print(q.queue)#删除队列数据，并返回数据q.get()#丢失所有队列数据print(q.queue)#输出：# deque([0, 1, 2])# 双端队列([1, 2])

Python四种类型的队列

#LIFO 表示后进先出。与栈类似，使用起来也非常简单。 maxsize的用法同上lq=LifoQueue(maxsize=0)#将数据写入队列lq.put(0)lq.put(1)lq.put(2)#输出队列中所有数据print ( lq.queue)#删除队列末尾的数据并返回数据lq.get()#输出队列中的所有数据print(lq.queue)#输出：# [0, 1, 2]# [0 , 1] 010- 1010 # 存储数据时可以设置优先级的队列# 优先级设置数字越小，级别越高pq=PriorityQueue(maxsize=0)#写入队列并设置优先级pq.put((9 ,'a'))pq .put((7,'c'))pq.put((1,'d'))#输出队列的所有数据print(pq.queue)#获取队列数据。你可以看到它是按照优先级进行的。的。 pq.get()pq.get()print(pq.queue)#输出： [(9,'a')]

Queue：先进先出队列

#双边队列dq=deque(['a','b'])#增加数据到队列尾部dq.append('c')#向队列左侧添加数据dq.appendleft('d')#输出队列中所有数据print(dq)#移除队列尾部and return print(dq.pop() )#移除剩下的队伍并返回print(dq.popleft())#输出：deque(['d','a','b','c'])cd

LifoQueue：后进先出队列：

当我们存储一大波数据的时候，经常会用到数组，但是在进行插入操作的时候却非常麻烦。比如有一堆数据1、2、3、5、6、7，我们想把它插入到3、5和5之间插入4，如果用数组怎么办？当然，5后面的数据后移一位，然后插入4。这样很麻烦，但是如果用链表的话，直接在3和5之间插入4就可以了。

所以链表的节点结构如下：

data为自定义数据，next为下一个节点的地址。 head保存的是第一个节点的地址。

首先，你可以看一个小的链表并定义链表：

classNode:def __init__(self, item):self.item=itemself.next=Nonea=Node(1)b=Node(2)c=Node(3)# 通过next 连接a、b、c a.next=bb. next=c# 打印next的下一个结果是什么print(a.next.next.item) # 3 当然，我们不可能像这样用next来调用链表、使用循环等。我们继续学习吧。

链表总是有一个头节点，head

头插值和尾插值的代码如下：

classNode:def __init__(self, item):self.item=itemself.next=None# 头部插入方式# 这里使用li进行循环插入def create_linklist_head(li):head=Node(li[0])forelementinli[1:]:node=Node( element)node.next=head # 将头节点赋予新插入的节点head=node # 然后将插入的节点设置为头节点returnhead # 尾部插入方法def create_linklist_tail(li):head=Node(li[0]) tail=headforelementinli[1:]:node=Node(element)tail.next=nodetail=nodereturnheaddef print_linklist(lk):whilelk:print(lk.item, end=',')lk=lk.nextprint('******** * ')lk=create_linklist_head([1, 2, 3, 4])# print(lk.item) # 4print_linklist(lk) # 4,3,2,1,********lk=create_linklist_tail ([ 1, 2, 3, 4, 5])print_linklist(lk) # 1,2,3,4,5，插入如下，很简单，所以时间复杂度也低。

优先队列

双边队列

def isEmpty(self):return(self.length==0)

6，链表

defappend(self, dataOrNode):item=Noneifisinstance(dataOrNode, Node):item=dataOrNodeelse:item=Node(dataOrNode)if不是self.head:self .head=itemself.length +=1else:node=self.headwhilenode._next:node=node._nextnode._next=itemself.length +=1

6.1 关于链表的方法

# 删除节点后，记得将链表长度减少一个def delete (self, index) :ifself.isEmpty():print('此链表为空')returnifindex 0 or index=self.length:print('Error: out of index')return# 注意删除第一个节点。如果有空头节点，则不需要这样做ifindex==0:self.head=self.head._nextself.length -=1return# prev 是保存前导节点# node 是保存当前节点# 当j 为等于index，相当于找到要删除的节点j=0node=self.headprev=self.headwhilenode._next 并且j index:prev=nodenode=node._nextj +=1ifj==index:prev._next=node._nextself.length -=1

　　1，判断是否为空：isEmpty()

def update(self, index, data):ifself.isEmpty() 或index 0 或index=self.length:print'error: out of index'returnj=0node=self.headwhilenode._next 并且j index:node=node. _nextj +=1ifj==索引：n

　　5，查找一个节点：getItem()

　　6，查找一个节点的索引：getIndex()

　　7，插入一个节点：insert()

　　8，清空链表：clear()

6.2 双链表

6.3 链表复杂度分析

　 链表与顺序表

7，哈希表（Hash table）

直接寻址表

哈希

哈希表

7.1 哈希表的应用

　　1，集合与字典

　　2，md5算法

　　3，md5

　　 4，SHA2算法

　　5，SHA2算法应用举例

栈和队列的应用——迷宫问题

1，栈——深度优先搜索

2，队列——广度优先搜索