【出典】「新・明解Pythonで学ぶアルゴリズムとデータ構造」
前回の記事はこちら
3章を進めようとしたら、ハッシュ法の中に線形リストを使うものがあるみたいなので、先に8章を学ぶようにとのことでしたので急遽8章を学びます。
第8章 線形リスト
線形リストは、ノードと呼ばれる要素が連なってできています。
ノードはデータと後続のデータを示すポインタで構成できます。
とりあえず3章を進めるために今回、8章はさらっと流そうと思います。
さて、ここでは、線形リストに追加や削除などが行えるものを作ります。
list8-1,linked_list.py
#list8-1は消してください
#線形リスト
from __future__ import annotations #アノテーション機能が本書では未実装だったため、追加しているらしい。
from typing import Any, Type
class Node: #ノードクラス
"""線形リストノードクラス"""
def __init__(self, data: Any = None, next: Node = None):#pythonでは参照先を保持する機能があるため、初期化が必要になる(と捉えました。)
"""初期化"""
self.data = data #データ
self.next = next #後続ポインタ
class LinkedList:
"""線形リストクラス"""
def __init__(self) -> None:
"""初期化"""
self.no = 0
self.head = None
self.current = None
def __len__(self) -> int:#これによって線形リストをlen関数の引数として使うことができる
"""線形リスト上のノード数を返却する"""
return self.no#len関数の引数としたときノード数を返す
def search(self, data: Any) -> int:
"""dataと等価なノードを探索"""
cnt = 0 #カウント(何番目のノードか示す)
ptr = self.head #headを参照
while ptr is not None: #ptrが空でないとき
if ptr.data == data: #ptr.dataとdataが一致したとき
self.current = ptr #self.currentはptrを参照する
return cnt #cntを返す
cnt += 1 #cntに+1して参照
ptr = ptr.next #ptrはptr.nextを参照する(次のデータの値)
return -1 #空だった時-1を返す
def __contains__(self, data: Any) -> bool: #in演算子が適用できる
"""線形リストにdataは含まれているか"""
return self.search(data) >= 0
def add_first(self, data: Any) -> None:
"""先頭にノードを挿入"""
ptr = self.head
self.head = self.current = Node(data, ptr)
self.no += 1
def add_last(self, data: Any):
"""末尾にノードを挿入"""
if self.head is None:
self.add_first(data)
else:
ptr = self.head
while ptr.next is not None:
ptr = ptr.next
ptr.next = self.current = Node(data, None)
self.no += 1
def remove_first(self) -> None:
"""先頭ノードを削除"""
if self.head is not None:
self.head = self.current = self.head.next
self.no -= 1
def remove_last(self):
"""末尾ノードを削除"""
if self.head.next is None:
self.remove_first()
else:
ptr = self.head
pre = self.head
while ptr.next is not None:
pre = ptr
ptr = ptr.next
pre.next = None
self.current = pre
self.no -= 1
def remove(self, p: Node) -> None:
"""ノードpを削除"""
if self.head is not None:
if p is self.head:
self.remove_first()
else:
ptr = self.head
while ptr.next is not p:
ptr = ptr.next
if ptr is None:
return
ptr.next = p.next
self.current = ptr
self.no -= 1
def remove_current_node(self) -> None:
"""着目ノードを削除"""
self.remove(self.current)
def clear(self) -> None:
"""全ノードを削除"""
while self.head is not None:
self.remove_first()
self.current = None
self.no = 0
def next(self) -> bool:
"""着目ノードを一つ後方に進める"""
if self.current is None or self.current.next is None:
return False
self.current = self.current.next
return True
def print_current_node(self) ->None:
"""着目ノードを表示"""
if self.current is None:
print('着目ノードはありません。')
else:
print(self.current.data)
def print(self) -> None:
"""全ノードを表示"""
ptr = self.head
while ptr is not None:
print(ptr.data)
ptr = ptr.next
def __iter__(self) -> LinkedListIterator:
"""イテレータ―を返却"""
return LinkedListIterator(self.head)
class LinkedListIterator:
"""クラスLinkedListIteratorのイテレータ用クラス"""
def __init__(self, head: Node):
self.current = head
def __iter__(self) -> LinkedListIterator:
return self
def __next__(self) -> Any:
if self.current is None:
raise StopIteration
else:
data = self.current = self.current.next
return data
list8-2
#線形リストクラスLinkedListの利用例
from enum import Enum
from Linked_list import LinkedList
Menu = Enum('Menu', ['先頭に挿入', '末尾に挿入', '先頭を削除', '末尾を削除', '着目を表示', '着目を進める', '着目を削除', '全削除', '探索', '帰属性判定', '全ノードを表示', '走査', '終了'])
#列挙型は、一意の定数値に束縛された識別名 (メンバー) の集合です。列挙型の中でメンバーの同一性を比較でき、列挙型自身でイテレートが可能です。
def select_Menu() -> Menu:
"""メニュー選択"""
s = [f'({m.value}){m.name}' for m in Menu]
while True:
print(*s, sep=' ', end='')
n = int(input('：'))
if 1 <= n <= len(Menu):
return Menu(n)
lst = LinkedList()
while True:
menu = select_Menu()
if menu == Menu.先頭に挿入:
lst.add_first(int(input('値：')))
elif menu == Menu.末尾に挿入:
lst.add_last(int(input('値：')))
elif menu == Menu.先頭を削除:
lst.remove_first()
elif menu == Menu.末尾を削除:
lst.remove_last()
elif menu == Menu.着目を表示:
lst.print_current_node()
elif menu == Menu.着目を進める:
lst.next()
elif menu == Menu.着目を削除:
lst.remove_current_node()
elif menu == Menu.全削除:
lst.clear()
elif menu == Menu.探索:
pos = lst.search(int(input('値：')))
if pos >= 0:
print(f':その値のデータは{pos + 1}番目にあります。')
else:
print('該当するデータはありません。')
elif menu == Menu.帰属性判定:
print('その値のデータは含まれま' + ('す。'if int(input('値：'))in lst else 'せん。'))
elif menu == Menu.全ノードを表示:
lst.print()
elif menu == Menu.走査:
for e in lst:
print(e)
else:
break
私はジュピターノートブックを使っているので、一応貼り付けてすぐ使える版もおいておきます。
一括で動かす用
#線形リスト
from __future__ import annotations
from typing import Any, Type
class Node:
"""線形リストノードクラス"""
def __init__(self, data: Any = None, next: Node = None):
"""初期化"""
self.data = data #データ
self.next = next #後続ポインタ
class LinkedList:
"""線形リストクラス"""
def __init__(self) -> None:
"""初期化"""
self.no = 0
self.head = None
self.current = None
def __len__(self) -> int:
"""線形リスト上のノード数を返却する"""
return self.no
def search(self, data: Any) -> int:
"""dataと等価なノードを探索"""
cnt = 0
ptr = self.head
while ptr is not None:
if ptr.data == data:
self.current = ptr
return cnt
cnt += 1
ptr = ptr.next
return -1
def __contains__(self, data: Any) -> bool:
"""線形リストにdataは含まれているか"""
return self.search(data) >= 0
def add_first(self, data: Any) -> None:
"""先頭にノードを挿入"""
ptr = self.head
self.head = self.current = Node(data, ptr)
self.no += 1
def add_last(self, data: Any):
"""末尾にノードを挿入"""
if self.head is None:
self.add_first(data)
else:
ptr = self.head
while ptr.next is not None:
ptr = ptr.next
ptr.next = self.current = Node(data, None)
self.no += 1
def remove_first(self) -> None:
"""先頭ノードを削除"""
if self.head is not None:
self.head = self.current = self.head.next
self.no -= 1
def remove_last(self):
"""末尾ノードを削除"""
if self.head.next is None:
self.remove_first()
else:
ptr = self.head
pre = self.head
while ptr.next is not None:
pre = ptr
ptr = ptr.next
pre.next = None
self.current = pre
self.no -= 1
def remove(self, p: Node) -> None:
"""ノードpを削除"""
if self.head is not None:
if p is self.head:
self.remove_first()
else:
ptr = self.head
while ptr.next is not p:
ptr = ptr.next
if ptr is None:
return
ptr.next = p.next
self.current = ptr
self.no -= 1
def remove_current_node(self) -> None:
"""着目ノードを削除"""
self.remove(self.current)
def clear(self) -> None:
"""全ノードを削除"""
while self.head is not None:
self.remove_first()
self.current = None
self.no = 0
def next(self) -> bool:
"""着目ノードを一つ後方に進める"""
if self.current is None or self.current.next is None:
return False
self.current = self.current.next
return True
def print_current_node(self) ->None:
"""着目ノードを表示"""
if self.current is None:
print('着目ノードはありません。')
else:
print(self.current.data)
def print(self) -> None:
"""全ノードを表示"""
ptr = self.head
while ptr is not None:
print(ptr.data)
ptr = ptr.next
def __iter__(self) -> LinkedListIterator:
"""イテレータ―を返却"""
return LinkedListIterator(self.head)
class LinkedListIterator:
"""クラスLinkedListIteratorのイテレータ用クラス"""
def __init__(self, head: Node):
self.current = head
def __iter__(self) -> LinkedListIterator:
return self
def __next__(self) -> Any:
if self.current is None:
raise StopIteration
else:
data = self.current = self.current.next
return data
#線形リストクラスLinkedListの利用例
from enum import Enum
Menu = Enum('Menu', ['先頭に挿入', '末尾に挿入', '先頭を削除', '末尾を削除', '着目を表示', '着目を進める', '着目を削除', '全削除', '探索', '帰属性判定', '全ノードを表示', '走査', '終了'])
def select_Menu() -> Menu:
"""メニュー選択"""
s = [f'({m.value}){m.name}' for m in Menu]
while True:
print(*s, sep=' ', end='')
n = int(input('：'))
if 1 <= n <= len(Menu):
return Menu(n)
lst = LinkedList()
while True:
menu = select_Menu()
if menu == Menu.先頭に挿入:
lst.add_first(int(input('値：')))
elif menu == Menu.末尾に挿入:
lst.add_last(int(input('値：')))
elif menu == Menu.先頭を削除:
lst.remove_first()
elif menu == Menu.末尾を削除:
lst.remove_last()
elif menu == Menu.着目を表示:
lst.print_current_node()
elif menu == Menu.着目を進める:
lst.next()
elif menu == Menu.着目を削除:
lst.remove_current_node()
elif menu == Menu.全削除:
lst.clear()
elif menu == Menu.探索:
pos = lst.search(int(input('値：')))
if pos >= 0:
print(f':その値のデータは{pos + 1}番目にあります。')
else:
print('該当するデータはありません。')
elif menu == Menu.帰属性判定:
print('その値のデータは含まれま' + ('す。'if int(input('値：'))in lst else 'せん。'))
elif menu == Menu.全ノードを表示:
lst.print()
elif menu == Menu.走査:
for e in lst:
print(e)
else:
break
さて、なんだか、プログラミングやってるっぽいやつができてきましたね。
中身に関してはさっぱりな部分が多いので、追々解明していきたいと思います。
__init__←こういうやつとか、selfとかなかなかイメージがつかみづらいですね。
クラスに関しては、pythonを使いこなす山場の一つでもある気がするので、しっかり押さえたいです。
以上です。ありがとうございました。