Pythonでさまざまなデータ構造（１）
こんにちは。これまで１０回以上にわたり、さまざまなデータ構造を取り上げてきました。そこで使ったプログラミング言語はJavaでした。競技プログラミングを目指すならば、絶対にCまたはC++に進むべきですが、あえてPythonで書いてみることにしました。
今回は片方向につながるノードを基にしたデータ構造のプログラム、次回は木構造のプログラムに分けて紹介します。念のため、それぞれのデータ構造の考え方がわかるページへのリンクも貼っておくことにします。
MyNodeクラス
連結リストの基になる片方向につながるノードを定義するクラスです。説明は次のページにあります。
https://joho-ka.mints.ne.jp/node01それではプログラムです。
class MyNode:
def __init__( self, element = None ):
self.__element = element
self.__next_node = None
def get_element( self ):
return self.__element
def set_element( self, element ):
self.__element = element
def get_next( self ):
return self.__next_node
def set_next( self, next_node ):
self.__next_node = next_node
def to_string( self ):
result = '[' + str( self.__element ) + ']'
if self.__next_node != None:
result += '→'
return result
MyLinkedListクラス
連結リストを定義するクラスです。説明は次のページにあります。
それではプログラムです。
import mynode
class MyLinkedList:
def __init__( self ):
self.__head = None
def size( self ):
size = 0
tmp = self.__head
while tmp != None:
size += 1
tmp = tmp.get_next()
return size
def add( self, element, index = None ):
if index == None:
index = self.size()
n = mynode.MyNode( element )
if index == 0:
n.set_next( self.__head )
self.__head = n
return
tmp = self.__get_n_node( index - 1 )
n.set_next( tmp.get_next() )
tmp.set_next( n )
def set( self, element, index ):
self.__get_n_node( index ).set_element( element )
def get( self, index ):
return self.__get_n_node( index ).get_element()
def remove( self, index):
if index == 0:
self.__head = self.__head.get_next()
return
tmp = self.__get_n_node( index - 1 )
tmp.set_next( tmp.get_next().get_next() )
def __get_n_node( self, index ):
result = self.__head
for i in range( index ):
result = result.get_next()
return result
def to_string( self ):
result = ''
tmp = self.__head
while tmp!=None:
result += tmp.to_string()
tmp = tmp.get_next()
return result
if __name__ == '__main__':
li = MyLinkedList()
print( str( li.size() ) + ' : ' + li.to_string())
li.add( '青森県' )
print( str( li.size() ) + ' : ' + li.to_string())
li.add( 'みやぎ県' )
print( str( li.size() ) + ' : ' + li.to_string())
li.add( '北海道', 0 )
print( str( li.size() ) + ' : ' + li.to_string())
li.add( '岩手県', 2 )
print( str( li.size() ) + ' : ' + li.to_string())
li.add( '秋田県' )
print( str( li.size() ) + ' : ' + li.to_string())
li.set( '宮城県', 3 )
print( str( li.size() ) + ' : ' + li.to_string())
print( li.get(1) )
li.remove( 1 )
print( str( li.size() ) + ' : ' + li.to_string())
li.remove( 0 )
print( str( li.size() ) + ' : ' + li.to_string())
動作確認用のプログラムの実行結果は次になります。
0 :
1 : [青森県]
2 : [青森県]→[みやぎ県]
3 : [北海道]→[青森県]→[みやぎ県]
4 : [北海道]→[青森県]→[岩手県]→[みやぎ県]
5 : [北海道]→[青森県]→[岩手県]→[みやぎ県]→[秋田県]
5 : [北海道]→[青森県]→[岩手県]→[宮城県]→[秋田県]
青森県
4 : [北海道]→[岩手県]→[宮城県]→[秋田県]
3 : [岩手県]→[宮城県]→[秋田県]
MyStackクラス
スタックを定義するクラスです。説明は次のページにあります。
それではプログラムです。
import mylinkedlist
class MyStack:
def __init__( self ):
self.__my_list = mylinkedlist.MyLinkedList()
def empty( self ):
return self.__my_list.size() == 0
def peek( self ):
return self.__my_list.get(0)
def pop( self ):
result = self.peek()
self.__my_list.remove(0)
return result
def push( self, element ):
self.__my_list.add( element )
def to_string( self ):
return self.__my_list.to_string()
if __name__ == '__main__':
stack = MyStack()
print(stack.empty())
stack.push(8)
print( stack.to_string() )
stack.push(5)
print( stack.to_string() )
stack.push(2)
print( stack.to_string() )
print( stack.pop() )
print( stack.to_string() )
print( stack.peek() )
print( stack.to_string() )
動作確認用のプログラムの実行結果は次になります。
True
[8]
[8]→[5]
[8]→[5]→[2]
8
[5]→[2]
5
[5]→[2]
MyQueueクラス
キューを定義するクラスです。説明は次のページにあります。
それではプログラムです。
import mylinkedlist
class MyQueue:
def __init__( self ):
self.__my_list = mylinkedlist.MyLinkedList()
def offer( self, element ):
self.__my_list.add( element, 0)
def peek( self ):
return self.__my_list.get( self.__my_list.size() - 1 )
def poll( self ):
result = self.peek()
self.__my_list.remove( self.__my_list.size() - 1 )
return result
def is_empty( self ):
return self.__my_list.size() == 0
def to_string( self ):
return self.__my_list.to_string()
if __name__ == '__main__':
queue = MyQueue()
print( queue.is_empty() )
queue.offer( '睦月' )
print( queue.to_string() )
print( queue.is_empty() )
queue.offer( '如月' )
print( queue.to_string() )
queue.offer( '弥生' )
print( queue.to_string() )
queue.offer( '卯月' )
print( queue.to_string() )
print( queue.peek() )
print( queue.to_string() )
print( queue.poll() )
print( queue.to_string() )
print( queue.peek() )
動作確認用のプログラムの実行結果は次になります。
True
[睦月]
False
[如月]→[睦月]
[弥生]→[如月]→[睦月]
[卯月]→[弥生]→[如月]→[睦月]
睦月
[卯月]→[弥生]→[如月]→[睦月]
睦月
[卯月]→[弥生]→[如月]
如月
片方向につながるノードを基にしたデータ構造は以上のものを取り上げていました。今回はこれでおしまいにします。それではまた。