Pythonプログラム設計のデータ構造

1.ヒープは、各親ノードの値がすべてのサブノードの値を超えない二叉木です.配列またはリストを使用してスタックを実装する場合、すべてのk(下付き、0から)はheap[k]<=heap[2 k+1]およびheap[k]<=heap[2 k+2]を満たし、スタック内の最小要素は常に二叉木のルートノードに位置する.スタックはスタックとも呼ばれ、演算が制限された線形テーブルです.この制限は、テーブルの一端でのみ挿入および削除演算を許可することです.この一端をスタックトップと呼び、反対に他端をスタックベースと呼ぶ.1つのスタックに新しい要素を挿入することは、スタック、スタック、またはスタックと呼ばれ、新しい要素をスタックの上部要素の上に配置し、新しいスタックの上部要素にすることである.

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)		#         

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)	#     （          ）

カスタムキュー構造:

class myQueue:
	def __init__(self, size=10):
		self._content=[]
		self._size=size
		self._current=0
		
	def Setsize(self,size):
		if size

上記のコードをmyQueueとして保存する.pyファイル、モジュール作成参照:https://blog.csdn.net/qxyloveyy/article/details/104345359

import myQueue	#       
q=myQueue.myQueue()	#     
>>>q.isFull()
>>>False		#    myQueue        ，    

3.スタックは、先行後出(FILO)または後進先出(LIFO)のデータ構造である.スタック、スタックとも呼ばれ、演算が制限された線形テーブルです.この制限は、テーブルの一端でのみ挿入および削除演算を許可することです.この一端をスタックトップと呼び、反対に他端をスタックベースと呼ぶ.1つのスタックに新しい要素を挿入することは、スタック、スタック、またはスタックと呼ばれ、新しい要素をスタックの上部要素の上に配置し、新しいスタックの上部要素にすることである.スタックから要素を削除することは、スタックまたはバックスタックとも呼ばれ、スタックトップ要素を削除し、隣接する要素を新しいスタックトップ要素にします.スタックは先進的な後出の原則に従ってデータを格納し、先に入ったデータはスタックの底に押し込まれ、最後のデータはスタックの上にあり、データを読む必要があるときにスタックの上からデータがポップアップされる(最後のデータは最初に読み出される).スタックは記憶作用があり、スタックの挿入と削除操作では、スタックベースポインタを変更する必要はありません.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

4.チェーンテーブルチェーンテーブルは物理記憶ユニット上の非連続、非順序の記憶構造であり、データ要素の論理順序はチェーンテーブル中のポインタリンク順序によって実現される.チェーンテーブルは、実行時に動的に生成できる一連のノード(チェーンテーブルの各要素をノードと呼ぶ)から構成されます.各ノードには、データ要素を格納するデータドメインと、次のノードアドレスを格納するポインタドメインの2つのセクションがあります.線形テーブルの順序構造に比べて、操作が複雑です.順番に格納する必要がないため、チェーンテーブルは挿入時にO(1)の複雑さに達し、別の線形テーブルの順序テーブルよりもずっと速いが、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])	#    

5.ツリーツリーツリーツリーは、ノードごとに最大2つのサブツリーを持つツリー構造です.通常、サブツリーは「左サブツリー」(left subtree)と「右サブツリー」(right subtree)と呼ばれます.二叉木は、二叉ルックアップツリーと二叉スタックを実現するためによく用いられる.深さkで2^k-1の接点を持つ二叉樹で、満二叉樹と呼ばれています.この木の特徴は,各層のノード数が最大ノード数であることである.一方、1本の二叉木では、最後の層を除いて、残りの層がいっぱいで、最後の層がいっぱいであるか、右側に連続するいくつかの接点が欠けている場合、この二叉木は完全な二叉木である.n個のノードを有する完全二叉木の深さはfloor(log 2 n)+1であった.深さkの完全な二叉木は、少なくとも2 k−1個の葉の結点があり、せいぜい2 k−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 !')

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']		     							

その他参考記事:Python開発環境構築:https://blog.csdn.net/qxyloveyy/article/details/104227923Pythonシーケンスは記事を参照してください.https://blog.csdn.net/qxyloveyy/article/details/104391462
あなたに役に立つことを望みます!