【出典】「新・明解Pythonで学ぶアルゴリズムとデータ構造」
前回の記事はこちら
8-3カーソルによる線形リスト
前回で学習した線形リストは「ノードの挿入や削除を、データの移動を伴わずに行える」という特徴があったようで…。(学習不足感)
挿入や削除のたびにノード用インスタンスの生成とは気が内部的に行われるため、記憶域の確保・解放に要するコストは決して小さくないのだとか…。(記憶域の確保とか解放とかいまいちわからないですが…。)
今回学ぶカーソルによる線形リストは、後続ポインタ(ノード内のnextに当たるところ)を後続ノードが格納されている要素の添字とします。ここでは、添字によってあらわすポインタのことをカーソルと呼びます。
ポインタ式(前回)の線形リストでは、追加削除を行う際には、データを詰めるような動作がありましたが、カーソル式ではフリーリスト(削除した部分のリスト)を生成して対応します。
詳しく理解はできていないのですが、ポインタ式で詰めたりする作業があったのに対して、カーソル式ではリストを生成する(別で記録する？)ため、詰める分の計算量が減るといったところでしょうか。
さて、今回も前回と同じようなシステムのプログラムを組むようです。
list8-3,array_list.py
#線形リスト(配列カーソル版)
from __future__ import annotations
from typing import Any, Type
Null = -1
class Node:
"""線形リスト用ノードクラス(配当カーソル版)"""
def __init__(self, data = Null, next = Null, dnext = Null):
"""初期化"""
self.data = data #データ
self.next = next #リストの後続ポインタ
self.dnext = dnext #フリーリストの後続ポインタ
class ArrayLinkedList:
"""線形リストクラス(配列クラス)"""
def __init__(self, capacity: int):
"""初期化"""
self.head = Null #先頭ノード
self.current = Null #着目ノード
self.max = Null #利用中の末尾レコード
self.deleted = Null #フリーリストの先頭ノード
self.capacity = capacity #リストの容量
self.n = [Node()] * self.capacity #リスト本体
self.no = 0
def __len__(self) -> int:
"""線形リスト上のノード数を返却する"""
return self.no
def get_insert_index(self):
"""次に挿入するレコードの添字を求める"""
if self.deleted == Null:
if self.max < self.capacity:
self.max += 1
return self.max
else:
return Null
else:
rec = self.deleted
self.deleted = self.n[rec].dnext
return rec
def delete_index(self, idx: int) -> None:
"""レコードidxをフリーリストに登録"""
if self.deleted == Null:
self.deleted = idx
self.n[idx].dnext = Null
else:
rec = self.deleted
self.deleted = idx
self.n[rec].dnext = rec
def search(self, data: Any) -> int:
"""dataと等価なノードを探索"""
cnt = 0
ptr = self.head
while ptr != Null:
if self.n[ptr].data ==data:
self.current = ptr
return cnt
cnt += 1
ptr = self.n[ptr].next
return Null
def __contains__(self, data: Any) -> bool:
"""線形リストにデータは含まれているか"""
return selff.search(data) >= 0
def add_first(self, data: Any):
"""先頭にノードを挿入"""
ptr = self.head
rec = self.get_insert_index()
if rec != Null:
self.head = self.current = rec
self.n[self.head] = Node(data, ptr)
self.no += 1
def add_last(self, data: Any) -> None:
"""末尾にノードを挿入"""
if self.head == Null:
self.add_first(data)
else:
ptr = self.head
while self.n[ptr].next != Null:
ptr = self.n[ptr].next
rec = self.get_insert_index()
if rec != Null:
self.n[ptr].next = self.current = rec
self.n[rec] = Node(data)
self.no += 1
def remove_first(self) -> None:
"""先頭ノードを削除"""
if self.head != Null:
ptr = self.n[self.head].next
self.delete_index(self.head)
self.head = self.current = ptr
self.no -= 1
def remove_last(self) -> None:
"""末尾ノードを削除"""
if self.head != Null:
if self.n[self.head].next == Null:
self.remove_first()
else:
ptr = self.head
pre = self.head
while self.n[ptr].next != Null:
pre = ptr
ptr = self.n[ptr].next
self.n[pre].next = Null
self.delete_index(pre)
self.current = pre
self.no -= 1
def remove(self, p: int) -> None:
"""レコードpを削除"""
if self.head != Null:
if p == self.head:
self.remove_first()
else:
ptr = self.head
while self.n[ptr].next != p:
ptr = self.n[ptr].next
if ptr == Null:
return
self.n[ptr].next = Null
self.delete_index(ptr)
self.n[ptr].next = self.n[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 != Null:
self.remove_first()
self.current = Null
def next(self) -> bool:
"""着目ノードを一つ後方に進める"""
if self.current == Null or self.n[self.current].next == Null:
return False
self.current = self.n[self.current].next
return True
def print_current_node(self) -> None:
"""着目ノードを表示"""
if self.current == Null:
print("""着目ノードはありません""")
else:
print(self.n[self.current].data)
def print(self) -> None:
"""全ノードを表示"""
ptr = self.head
while ptr != Null:
print(self.n[ptr].data)
ptr = self.n[ptr].next
def dump(self) -> None:
"""配列をダンプ"""
for i in self.n:
print(f'[{i}]{i.data}{i.next}{i.dnext}')
def __iter__(self) -> ArrayLinkedListIterator:
"""イテレータを返却"""
return ArrayLinkedListIterator(self.n, self.head)
class ArrayLinkedListIterator:
"""クラスArrayLinkedListIteratorのイテレータ用クラス"""
def __init__(self, n: int, head: int):
self.n = n
self.current = head
def __iter__(self) -> ArrayLinkedListIterator:
return self
def __next__(self) -> Any:
if self.current == Null:
raise StopIteration
else:
data = self.n[self.current].data
self.current = self.n[self.current].next
return data
list8-4,array_list_test.py
#配列版線形リストクラスArrayLinkedListの利用例
from enum import Enum
from array_list import ArrayLinkedList
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 = ArrayLinkedList(100)
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
| コラム8-2 論理演算子 |
|---|
今まで、andなどの演算子について深く考えて使ったことはなかったのですが、どうやら、真偽判定が行われているようですね。
（そもそも演算子だったことを意識していませんでした。）
確かに、プログラムなので何かしらの真偽判定が行われているんですよね…。(逆を言えば真偽の作り方をマスターするといろいろ考えれる幅が増えそうですね。)
ちなみに優先順位があるようで not>and>or の順らしいです。
さて、and,or,notについて次のようにまとめられていたのでご参考までに
and演算子
| x | y | x and y |
|---|---|---|
| 真 | 真 | y（真） |
| 真 | 偽 | y（偽） |
| 偽 | 真 | x（偽） |
| 偽 | 偽 | x（偽） |
or演算子
| x | y | x or y |
|---|---|---|
| 真 | 真 | x（真） |
| 真 | 偽 | x（真） |
| 偽 | 真 | y（真） |
| 偽 | 偽 | y（偽） |
こちらも偽が連続したときは
not演算子
| x | not x |
|---|---|
| 真 | False |
| 偽 | True |
#おまけ
8-3,8-4を統合したものです。
#線形リスト(配列カーソル版)
from __future__ import annotations
from typing import Any, Type
Null = -1
class Node:
"""線形リスト用ノードクラス(配当カーソル版)"""
def __init__(self, data = Null, next = Null, dnext = Null):
"""初期化"""
self.data = data #データ
self.next = next #リストの後続ポインタ
self.dnext = dnext #フリーリストの後続ポインタ
class ArrayLinkedList:
"""線形リストクラス(配列クラス)"""
def __init__(self, capacity: int):
"""初期化"""
self.head = Null #先頭ノード
self.current = Null #着目ノード
self.max = Null #利用中の末尾レコード
self.deleted = Null #フリーリストの先頭ノード
self.capacity = capacity #リストの容量
self.n = [Node()] * self.capacity #リスト本体
self.no = 0
def __len__(self) -> int:
"""線形リスト上のノード数を返却する"""
return self.no
def get_insert_index(self):
"""次に挿入するレコードの添字を求める"""
if self.deleted == Null:
if self.max < self.capacity:
self.max += 1
return self.max
else:
return Null
else:
rec = self.deleted
self.deleted = self.n[rec].dnext
return rec
def delete_index(self, idx: int) -> None:
"""レコードidxをフリーリストに登録"""
if self.deleted == Null:
self.deleted = idx
self.n[idx].dnext = Null
else:
rec = self.deleted
self.deleted = idx
self.n[rec].dnext = rec
def search(self, data: Any) -> int:
"""dataと等価なノードを探索"""
cnt = 0
ptr = self.head
while ptr != Null:
if self.n[ptr].data ==data:
self.current = ptr
return cnt
cnt += 1
ptr = self.n[ptr].next
return Null
def __contains__(self, data: Any) -> bool:
"""線形リストにデータは含まれているか"""
return selff.search(data) >= 0
def add_first(self, data: Any):
"""先頭にノードを挿入"""
ptr = self.head
rec = self.get_insert_index()
if rec != Null:
self.head = self.current = rec
self.n[self.head] = Node(data, ptr)
self.no += 1
def add_last(self, data: Any) -> None:
"""末尾にノードを挿入"""
if self.head == Null:
self.add_first(data)
else:
ptr = self.head
while self.n[ptr].next != Null:
ptr = self.n[ptr].next
rec = self.get_insert_index()
if rec != Null:
self.n[ptr].next = self.current = rec
self.n[rec] = Node(data)
self.no += 1
def remove_first(self) -> None:
"""先頭ノードを削除"""
if self.head != Null:
ptr = self.n[self.head].next
self.delete_index(self.head)
self.head = self.current = ptr
self.no -= 1
def remove_last(self) -> None:
"""末尾ノードを削除"""
if self.head != Null:
if self.n[self.head].next == Null:
self.remove_first()
else:
ptr = self.head
pre = self.head
while self.n[ptr].next != Null:
pre = ptr
ptr = self.n[ptr].next
self.n[pre].next = Null
self.delete_index(pre)
self.current = pre
self.no -= 1
def remove(self, p: int) -> None:
"""レコードpを削除"""
if self.head != Null:
if p == self.head:
self.remove_first()
else:
ptr = self.head
while self.n[ptr].next != p:
ptr = self.n[ptr].next
if ptr == Null:
return
self.n[ptr].next = Null
self.delete_index(ptr)
self.n[ptr].next = self.n[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 != Null:
self.remove_first()
self.current = Null
def next(self) -> bool:
"""着目ノードを一つ後方に進める"""
if self.current == Null or self.n[self.current].next == Null:
return False
self.current = self.n[self.current].next
return True
def print_current_node(self) -> None:
"""着目ノードを表示"""
if self.current == Null:
print("""着目ノードはありません""")
else:
print(self.n[self.current].data)
def print(self) -> None:
"""全ノードを表示"""
ptr = self.head
while ptr != Null:
print(self.n[ptr].data)
ptr = self.n[ptr].next
def dump(self) -> None:
"""配列をダンプ"""
for i in self.n:
print(f'[{i}]{i.data}{i.next}{i.dnext}')
def __iter__(self) -> ArrayLinkedListIterator:
"""イテレータを返却"""
return ArrayLinkedListIterator(self.n, self.head)
class ArrayLinkedListIterator:
"""クラスArrayLinkedListIteratorのイテレータ用クラス"""
def __init__(self, n: int, head: int):
self.n = n
self.current = head
def __iter__(self) -> ArrayLinkedListIterator:
return self
def __next__(self) -> Any:
if self.current == Null:
raise StopIteration
else:
data = self.n[self.current].data
self.current = self.n[self.current].next
return data
#配列版線形リストクラスArrayLinkedListの利用例
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 = ArrayLinkedList(100)
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