Pythonでさまざまなデータ構造（１）

データ構造

こんにちは。これまで１０回以上にわたり、さまざまなデータ構造を取り上げてきました。そこで使ったプログラミング言語はJavaでした。競技プログラミングを目指すならば、絶対にCまたはC++に進むべきですが、あえてPythonで書いてみることにしました。

今回は片方向につながるノードを基にしたデータ構造のプログラム、次回は木構造のプログラムに分けて紹介します。念のため、それぞれのデータ構造の考え方がわかるページへのリンクも貼っておくことにします。

MyNodeクラス

連結リストの基になる片方向につながるノードを定義するクラスです。説明は次のページにあります。

それではプログラムです。

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
Python

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())
Python

動作確認用のプログラムの実行結果は次になります。

0 : 
1 : [青森県]
2 : [青森県]→[みやぎ県]
3 : [北海道]→[青森県]→[みやぎ県]
4 : [北海道]→[青森県]→[岩手県]→[みやぎ県]
5 : [北海道]→[青森県]→[岩手県]→[みやぎ県]→[秋田県]
5 : [北海道]→[青森県]→[岩手県]→[宮城県]→[秋田県]
青森県
4 : [北海道]→[岩手県]→[宮城県]→[秋田県]
3 : [岩手県]→[宮城県]→[秋田県]
None

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() )
Python

動作確認用のプログラムの実行結果は次になります。

True
[8]
[8]→[5]
[8]→[5]→[2]
8
[5]→[2]
5
[5]→[2]
None

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() )
Python

動作確認用のプログラムの実行結果は次になります。

True
[睦月]
False
[如月]→[睦月]
[弥生]→[如月]→[睦月]
[卯月]→[弥生]→[如月]→[睦月]
睦月
[卯月]→[弥生]→[如月]→[睦月]
睦月
[卯月]→[弥生]→[如月]
如月
None

片方向につながるノードを基にしたデータ構造は以上のものを取り上げていました。今回はこれでおしまいにします。それではまた。

Posted by 春日井 優