本站消息
Python程序设计之数据结构
发布于2020-02-21 11:43 阅读(953) 评论(0) 点赞(25) 收藏(4)
1.堆
堆是一个二叉树，其中每个父亲节点的值都不大于其所有子节点的值。
使用数组或列表来实现堆时，对于所有的k（下标，从0开始）都满足heap[k]<=heap[2k+1]和heap[k]<=heap[2k+2],并且堆中最小的元素总是位于二叉树的根节点。 栈又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；
import heapq #引入堆模块
import random #引入random模块
data=random.shuffle(list(range(10))) #列表初始化为打乱的数字
heap=[] #建堆
for n in data:
heapq.heappush(heap,n) #堆初始化
heapq.heappush(heap,0.5) #新数据入堆
heapq.heappop(heap) #弹出最小的元素，堆会自动重建
list=[1,2,3] #初始化列表
heapq.heapify(list) #将列表转换为堆
heapq.heapreplace(list,6) #替换列表中的元素值，自动重建堆
heapq.nlargest(2,list) #返回堆中最大的两个元素
heapq.nsmallest(1,list) #返回堆中最小的元素
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
2.队列
队列的特点是先进先出（FIFO）和后进后出（LILO）。 队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
import queue #引入队列模块（Python3.x中使用queue,Python2.x使用Queue）
q=queue.Queue()
for i in range(3)
q.put(i) #元素入队
>>>q.queue
>>>dqueue([0,1,2])
q.get() #队列元素出队
q1=queue.LifoQueue(5) #后进先出队列（后进元素在队列get()操作时先出）
q2=queue.PriorityQueue(5) #优先级队列（默认出队时按从小到大）
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
自定义队列结构：
class myQueue:
def __init__(self, size=10):
self._content=[]
self._size=size
self._current=0
def Setsize(self,size):
if size<size._current: #如果缩小队列，应该删除后面的元素
for i in range(size,self._current)[::-1]:
del self._current[i]
self._current=size
self._size=size
def put(self,v): #进队
if self._current<self.size:
self._current.append(v)
self._current=self._current+1
else:
print('This queue is full !')
def get(self): #出队
if self_content:
self._current=self._current-1
return self._current.pop(0)
else:
print('This queue is empty !')
def show(self): #查看队列元素
if self._content:
print(self._content)
else:
print('This queue is empty !')
def empty(self): #空队列
self._current=[]
def isEmpty(self):
if not self._content:
return Ture
else:
return False
def isFull(self):
if self._current==self._size:
return True
else:
return False
if __name__=='__main__':
print('Please use me as a moudle.')
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
将上述代码保存为myQueue.py文件，模块创建参看：
https://blog.csdn.net/qxyloveyy/article/details/104345359
import myQueue #引入自定义模块
q=myQueue.myQueue() #队列初始化
>>>q.isFull()
>>>False #可以调用myQueue模块中的所有函数，不再赘述
- 1
- 2
- 3
- 4
3.栈
栈是一种先进后出（FILO）或后进先出（LIFO）的数据结构。 栈，又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。栈按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。
Python本身就可以实现栈的基本操作！
class myStack:
def __init__(self,size=10):
self._content=[]
self._current=0
self._size=size
def empty(self):
self._content=[]
self._current=0
def isEmpty(self):
if not self._content:
return Ture
else:
return False
def isFull(self):
if self._current==self._size:
return True
else:
return False
def setSize(self,size): #如果缩小栈空间，则删除指定大小之后的元素
if size<self._current:
for i in range(size,self._current)[::-1]:
def self._content[i]
self._current=size
self._size=size
def push(self,v):
if len(self._content)<self._size:
self._content.append(v)
self._current=self.self._current+1 #栈中·元素个数加1
else:
print('This stack is full !')
def pop(self):
if self._content:
self._current=self._current-1 #栈中元素个数减1
return self.content.pop()
else:
print('This stack is empty !')
def show(self):
print(self._content)
if __name__=='__main__':
print('Please use me as a Model !')
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
4.链表
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
可以使用Python列表来实现链表简易功能！
my_linkTable=[]
for i in range(3):
my_linkTable.append(i) #在尾部追加节点
my_linkTable.insert(1,4) #在链表中插入元素
my_linkTable.remove(my_linkTable[2]) #删除节点
- 1
- 2
- 3
- 4
- 5
5.二叉树
二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。 一棵深度为k，且有2^k-1个结点的二叉树，称为满二叉树。这种树的特点是每一层上的结点数都是最大结点数。而在一棵二叉树中，除最后一层外，若其余层都是满的，并且或者最后一层是满的，或者是在右边缺少连续若干结点，则此二叉树为完全二叉树。具有n个结点的完全二叉树的深度为floor(log2n)+1。深度为k的完全二叉树，至少有2k-1个叶子结点，至多有2k-1个结点。
自定义二叉树结构
class BinaryTree:
def __init__(self,value):
self._left=None
self._right=None
self.data=value
def insertLeftChild(self,value): #创建左子树
if self._left:
print('Left child tree already exists.')
else:
self._left=BinaryTree(value)
return self._left
def insertRightChild(right,value): #创建右子树
if self._left:
print('Right child tree already exists.')
else:
self._right=BinaryTree(value)
return self._right
def show(self):
print(self._data)
def preOrder(self): #前序遍历
print(self._data) #输出根节点的值
if self._left: #遍历左子树
self._left.preOrder()
if self._right: #遍历右子树
self._right.preOrder()
def postOrder(self): #后续遍历
if self._left: #遍历左子树
self._left.postOrder()
if self._right: #遍历右子树
self._right.postOrder()
print(self._data)
def inOrder(self): #中序遍历
if self._left: #遍历左子树
self._left.inOrder()
print(self._data)
if self._right: #遍历右子树
self._right.inOrder()
if __name__=='__main__':
print('Please use me as a model !')
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
6.有向图
一个有向图D是指一个有序三元组(V(D)，A(D)，ψD) ，其中ψD)为关联函数，它使A(D)中的每一个元素(称为有向边或弧)对应于V(D)中的一个有序元素(称为顶点或点)对．
自定义有向图结构！
def searchPath(graph,start,end):
results=[]
__generatePath(graph,[start],end,results)
reults.sort(key=lambda x:len(x)) #按所有路径的长度排序
return results
def __generatePath(graph,path,end,results):
current=path[-1]
if current==end:
results.append(path)
else:
for i in graph[current]:
if i not in path:
__generatePath(graph,path+[n],end,results)
def showPath(results):
print('The path from ',results[0][0], 'to' ,results[0][-1],' is: ')
for path in results:
print(path)
if __name__=='__main__':
graph={'A':['B','C','D']
'B':['C']
'C':['D']
'D':['E']}
r1=searchPath(graph,'A','D')
showPath(r1)
>>>The path is from A to D is:
>>>['A','D']
>>>['A','B','C','D']
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
其他参考文章：
Python开发环境搭建：
https://blog.csdn.net/qxyloveyy/article/details/104227923
Python序列参看文章：
https://blog.csdn.net/qxyloveyy/article/details/104391462
希望对您有所帮助！
所属网站分类: 技术文章 > 博客
作者：djjdf
链接：https://www.pythonheidong.com/blog/article/231867/be1b72e417a7a9b4cc61/
来源：python黑洞网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
25
0
收藏该文
昵称:
评论内容：(最多支持255个字符)
---无人问津也好，技不如人也罢，你都要试着安静下来，去做自己该做的事，而不是让内心的烦躁、焦虑，坏掉你本来就不多的热情和定力
站长公众号(new)
更多>
pdf(new)
更多>
问答(new)
更多>
游戏(new)
更多>