search
LoginSignup
0

posted at

updated at

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

【出典】「新・明解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を使いこなす山場の一つでもある気がするので、しっかり押さえたいです。

以上です。ありがとうございました。

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
What you can do with signing up
0