「新・明解Pythonで学ぶアルゴリズムとデータ構造」で勉強日記#12

【出典】「新・明解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