コンテンツにスキップ

Week 3 (2025/4/25)

今週の目的

データの順番を入れ替える。

今週のキーワード

  • モジュールのインポート
  • デフォルト値
  • 節（Nodeクラス）を用いた連結リストの作成
  • 連結リストの先頭への節の挿入
  • 連結リストの切り取り
  • 連結リストの繰り返し処理

データ構造の1つである連結リストを操作するプログラムを作成する。連結リストとは節（Node もしくは Vertex）と呼ばれるデータを一方向もしくは両方向に連結させたデータ構造である。今回は、この連結リストへのデータの挿入と切り取りを習得する。具体的には、前回作成したStopクラスのインスタンスを連結リストの節(Nodeクラス)に格納し、それらを表示するプログラムを作成する。

今回作成するNodeクラスの仕様は、以下の通りである。

Nodeクラス

class Node(data, next=None)
連結リストの節のクラス

パラメータ

  • data: 節に格納するデータ（Stopインスタンス）
  • next: 連結される次の節（Nodeインスタンス）

課題1：連結リストを作る

「立命館大学前」、「同志社前」、「京大正門前」、「京都産大前」、「龍谷大学前」からなる連結リストを作成する。（「データ構造とアルゴリズム」の教科書P.73の(1-d)参照）

なお、これまでに作成したStopクラスやStopインスタンスの定義をimportするために、それらをまとめたdef_stop.pyをダウンロードし、同一ディレクトリに保存して用いよ。

week3_1.py
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# 穴埋め用のプログラム
# StopクラスおよびStopインスタンスの定義をdef_stop.pyからインポート
from def_stop import Stop, ritsumeikan, doshisha, kyodai, kyosan, ryukoku


# Nodeクラスの定義
class Node:
    def __init__(self, data, next=None):
    # nextにデフォルト値（何も値が渡されなかった時に設定される値）を設定
        self.data = data  # データを格納するインスタンス変数
        self.next = next  # 連結される次の節を指すインスタンス変数


# 連結リストを末尾の「龍谷大学前」から順に作成する
top = Node(ryukoku)  # Nodeインスタンスを作成し、連結リストのリストヘッドtopに代入
p = Node([____])  # Nodeインスタンスを作成
[____] = top  # 作成したNodeインスタンス(p)の次に連結リストの先頭(top)を連結
top = p  # 作成したNodeインスタンス(p)が連結リストの先頭となるようにリストヘッドtopを更新
p = None  # 不要になった変数pをNoneに更新
top = Node([____], [____])  # 連結リストの先頭（top）の前にNodeインスタンスを挿入し、そのNodeインスタンスが連結リストの先頭となるようにリストヘッドtopを更新（上記5行分を簡潔に1行で記述）
top = Node([____], [____])  # 上と同様
top = Node([____], [____])  # 上と同様

message = '{}(ID:{})のバス停の緯度経度は({},{})です。'
p = top
print(message.format(p.data.name, p.data.id, p.data.lat, p.data.lng))
p = p.next
print(message.format(p.data.name, p.data.id, p.data.lat, p.data.lng))
p = p.next
print(message.format(p.data.name, p.data.id, p.data.lat, p.data.lng))
p = p.next
print(message.format(p.data.name, p.data.id, p.data.lat, p.data.lng))
p = p.next
print(message.format(p.data.name, p.data.id, p.data.lat, p.data.lng))

立命館大学前(ID:ED01_1914)のバス停の緯度経度は(35.03497163,135.72602961)です。
同志社前(ID:ED01_1922)のバス停の緯度経度は(35.02913136,135.76314762)です。
京大正門前(ID:ED01_1841)のバス停の緯度経度は(35.02548675,135.7786403)です。
京都産大前(ID:ED01_2244)のバス停の緯度経度は(35.07182049,135.75638731)です。
龍谷大学前(ID:ED01_2263)のバス停の緯度経度は(34.9631519,135.76834405)です。

課題2：連結リストを切り取る

課題１で作成した連結リストから「京大正門前」だけを切り取るようにプログラムを修正して、残った連結リストを表示し、実行例の通りに動くことを確認せよ。（「データ構造とアルゴリズム」の教科書P.77の(1-c)参照）

立命館大学前(ID:ED01_1914)のバス停の緯度経度は(35.03497163,135.72602961)です。
同志社前(ID:ED01_1922)のバス停の緯度経度は(35.02913136,135.76314762)です。
京都産大前(ID:ED01_2244)のバス停の緯度経度は(35.07182049,135.75638731)です。
龍谷大学前(ID:ED01_2263)のバス停の緯度経度は(34.9631519,135.76834405)です。

課題3：ファイルから連結リストを作る

前回と同じファイル（kyotocitybus_stop.dat）からデータを読み込み、読み込んだ順にStopインスタンスを生成して節に格納し、連結リストの先頭に順次挿入するプログラムを作成せよ。また、全てのデータを挿入し終わった後に、連結リストの先頭の節に格納されているStopインスタンスを表示するよう修正して、実行例の通りに動くことを確認せよ。

京都駅八条口(ID:ED01_4102)のバス停の緯度経度は(34.98401063,135.75866056)です。

発展課題4：連結リストを繰り返し処理する

課題３のプログラムに、連結リスト内のdataを「先頭」から順に表示するprint_linked_list関数を追加し、実行例の通りに動くことを確認せよ。なお、print_linked_list関数は、ループを回して連結リスト内の節がいくつであっても連結リストの節を全部出力できるように実装すること。

今回作成するprint_linked_list関数の仕様は、以下の通りである。

print_linked_list関数

print_linked_list(top)
連結リストの節に格納されたデータを先頭の節から終端の節まで順番に表示する関数

パラメータ

  • top: 連結リストの先頭の節（Nodeインスタンス）

ヒント

繰り返す回数が分からないため、ループはfor文ではなくwhile文を用いて、走査がNoneにたどり着くまで繰り返すとよい。つまり、走査する（節を一つずつ辿る）変数がNoneでない（is not None）限り、表示を繰り返すように実装しよう。

京都駅八条口(ID:ED01_4102)のバス停の緯度経度は(34.98401063,135.75866056)です。
京都駅前(ID:ED01_4089)のバス停の緯度経度は(34.98719397,135.75802795)です。
京都会館美術館前(ID:ED01_2307)のバス停の緯度経度は(35.01363868,135.78107416)です。
(途中省略)
大宮総門口町(ID:ED01_1639)のバス停の緯度経度は(35.05831804,135.74403767)です。
神光院前(ID:ED01_1638)のバス停の緯度経度は(35.06134071,135.74395031)です。
西賀茂車庫前(ID:ED01_1637)のバス停の緯度経度は(35.06385669,135.74499864)です。

発展課題5：連結リストから任意の節を切り取る

任意の長さの連結リストから、特定のバス停を格納した節のみを削除するremove_node関数を定義せよ。さらに、remove_node関数を使って課題３で作成した連結リストから「京都駅八条口」と「西賀茂車庫前」のバス停を切り取り、発展課題４で作成したprint_linked_list関数を使って、残りの連結リストを表示し、実行例の通りに動くことを確認せよ。

今回作成するremove_node関数の仕様は、以下の通りである。

remove_node関数

remove_node(top, names)
連結リストの節に格納されているデータを先頭の節から順番に確認し、namesリストに含まれるデータが見つかったときに、その節を連結リストから取り除く関数

パラメータ

  • top: 連結リストの先頭の節（Nodeインスタンス）
  • names: 削除するバス停名のリスト

返り値

  • 削除後の連結リストの先頭の節（Nodeインスタンス）

ヒント

節に格納されているバス停が削除対象のバス停かどうかチェックするために連結リストを走査する（節を一つずつ辿る）変数と、節の切り取り時に一つ前の節を覚えておくための変数の二つの変数を用いるとよい。また、繰り返し処理はprint_linked_list関数と同様に、while文を用いて走査がNoneにたどり着くまで繰り返すように実装しよう。

京都駅前(ID:ED01_4089)のバス停の緯度経度は(34.98719397,135.75802795)です。
京都会館美術館前(ID:ED01_2307)のバス停の緯度経度は(35.01363868,135.78107416)です。
京都市役所前(ID:ED01_2306)のバス停の緯度経度は(35.01092789,135.76803111)です。
(途中省略)
山ノ前町(ID:ED01_1640)のバス停の緯度経度は(35.05625634,135.74108489)です。
大宮総門口町(ID:ED01_1639)のバス停の緯度経度は(35.05831804,135.74403767)です。
神光院前(ID:ED01_1638)のバス停の緯度経度は(35.06134071,135.74395031)です。
Back to top