データ構造

はじめに ショコラブル♪🍫🔵 nikkieです。 スタッフ参加したみんなのPython勉強会のレポートです。 ご参加いただいた方、ありがとうございました！ 目次 はじめに 目次 みんなのPython勉強会#112 辻さん『Pythonの基本的なデータ構造とその便利な使い方』 たかのりさん『エラーはともだち こわくないよ』 私のLT「Pythonの組み込み例外の小話」 終わりに みんなのPython勉強会#112 startpython.connpass.com テーマは「エラーは友達」 #stapy スタッフのnikkieです。スタッフ特権で明日の登壇資料を見ました。全てをお話しますと言っても…

こんにちは。皆さんはデータ構造、お好きですか？今回は木構造の内容です。二分木、B木などが有名ですね。 今回は木構造の表現方法を紹介したいと思います。 木構造の定義 二分木 配列で管理する ポインタで管理する 多分木 二重連鎖木(連想配列) 入れ子の構造 操作の計算量の比較 idによるノード検索 ノードの追加 ノードの削除 ノードの並び替え まとめ おわりに 木構造の定義 まずは木構造の定義を確認しておきます。辞書を引いてみると、このようにあります。 データ構造の一種。一つの要素が複数の要素への分岐情報を持つ階層的な構造。要素の連結状態が枝分かれした木のように見えることからいう。木構造。(広辞苑…

前回の記事では方法 1 について記述しました。 今回はそれを発展させた方法 2 について記述します。 方針 方法 2 では、方法 1 の状態からさらに、子ノードが 1 個のノードを省略します。 下図は、クエリ (1) によりインデックス の値が更新されたときの例です。 根は となります。 保持するノードを省略することで、メモリ使用量を削減します。 方法 1 とは大きく異なるのが、クエリ (1) において二分木にノードを追加するときの処理です。 例として、クエリ (1) によりまず葉 が追加されており、その次に葉 が追加される場合を考えましょう。 葉 が追加される前の状態は下図のようになっていま…

概要 通常のセグメント木では、管理対象の列の項数 を固定して完全二分木を構築するため、初期化に時間計算量および空間計算量 を要し、1 回のクエリあたり時間計算量 を要する。 したがって、 として利用できる値には計算機資源上の制限があり、列のインデックス (セグメント木の定義域) としてより大きな値を利用するには、オフライン クエリ (入力値がすべて予め与えられる) を前提として座標圧縮をする必要があった。 そこで本稿では、セグメント木の定義域を拡張し、例えば や のような範囲を利用できる方法について記述する。 これにより、座標圧縮をせずにセグメント木のオンライン クエリ (入力値が逐次的に与え…

｜最も基本的なデータ構造（配列（Array）、配列の添え字） １．配列（Array） ２．添え字（Indexing） ｜静的配列と動的配列 １．静的配列（Static Array） ２．動的配列（Dynamic Array） ｜スタックとキューの操作 １．スタック（Stack） ２．キュー（Queue） ３．適切な使用例 ｜線形リスト：データの連なりを効率的に管理する １．線形リストの基本構造 ２．線形リストの特徴 ｜単方向リスト：データの順序付けと効率的な操作 １．単方向リストの基本構造 ２．単方向リストの特徴 ３．単方向リストの使用例 ｜両方向リスト：双方向のデータ操作 １．両方向リストの…

スタック(Stack)とキュー(Queue)は自分の知るがぎり簡単な部類のデータ構造ですが、どっちがどっちか間違いやすく意外と厄介です。この記事でっはその違いを簡単に紹介できればと思います。 スタック(Stack)とキュー(Queue)の違い 違いを一言で言うと、スタック(Stack)は筒で、キュー(Queue)は列です。 スタック(Stack)は筒で中に一度入れると取り出すのは筒の上にあるもの、すなわち最後に入れたものになります。 キュー(Queue)は列で最初に並んだ人が最初に呼ばれ(取り出され)ます。 スタック (Stack): スタックは、「最後に入ったものが最初に出る」(Last I…

データ構造のstackはLIFO（Last In First Out）方式のデータ構造の一種です。