C++

データ構造におけるリンクリスト（連結リスト）とは、データ要素を線形につなぎ合わせたコレクションのことです。リストの各要素（ノード）は「データ本体」と「次のノードへの参照（ポインタ）」という2つの情報で構成され、最後のノードは null を参照します。また、リストへの入り口となる先頭ノードは「ヘッド（head）」と呼ばれます。 単方向リンクリストでは、各ノードは自分の内容と次のノードへのポインタだけを持ちます。前のノードを指すポインタは保持しないため、リストの走査は基本的に先頭から一方向に行われます。 本記事で扱うのはソート済み循環単方向リンクリストです。これは、要素が常に昇順に並ぶよう管理され

リンクリスト（連結リスト）とはデータ構造におけるリンクリスト（連結リスト）は、データ要素を線形に並べた集合です。リストの各要素（ノード）は「データ」と「次のノードへの参照（ポインタ）」という2つの項目で構成され、最後のノードはnullへの参照を持ちます。リンクリストへの入口となる先頭ノードは「ヘッド（head）」と呼ばれます。双方向リンクリストとは双方向リンクリスト（ダブルリンクリスト）は、ノードと呼ばれるレコードが順次連結されたデータ構造です。各ノードは3つのフィールドを持ちます。1つはデータフィールド、残りの2つはリンクフィールドで、それぞれノード列における「前のノード」と「次のノード」へ

リンクリスト（連結リスト）とは データ構造におけるリンクリスト（連結リスト）とは、データ要素を線形につなげたコレクションです。リストの各要素（ノード）は、「データ本体」と「次のノードへの参照」という2つの項目で構成されており、末尾のノードはnullを参照します。また、リストへの入り口となる先頭ノードは「ヘッド（head）」と呼ばれます。 単方向リンクリストでは、各ノードは自分の内容と、リスト内の次のノードへのポインタ（参照）だけを保持します。前のノードを指すポインタは持たないため、逆方向へたどれない点が双方向リンクリストとの大きな違いです。 この記事では、ノードを挿入するたびに自動的に昇順へ

仮想関数とはC++の仮想関数（virtual function）を使用すると、基底クラスへのポインタのリストを作成し、派生クラスオブジェクトの実際の型を意識することなく、任意の派生クラスのメソッドを呼び出すことができます。仮想関数はコンパイル時ではなく、実行時（ランタイム）に遅延バインディングされるのが大きな特徴です。ランタイムポリモーフィズムの実現仮想関数の主な用途は、ランタイムポリモーフィズム（動的多態性）を実現することです。ランタイムポリモーフィズムは、基底クラス型のポインタ（または参照）を介してのみ実現できます。また、基底クラスのポインタは、基底クラス自身のオブジェクトだけでなく、派生

C++では、仮想関数とデフォルト引数を組み合わせた場合、一見すると直感に反する挙動が発生することがあります。本記事では、具体的なサンプルプログラムをもとに、その仕組みと理由をわかりやすく解説します。 サンプルコード #include<iostream> using namespace std; class B {    public:       virtual void s(int a = 0) {          cout<<" In Base \n&qu

C++の派生クラスにおける仮想関数とはC++における仮想関数（virtual function）は、基底クラスへのポインタのリストを作成し、派生クラスオブジェクトの実際の型を知らなくても、任意の派生クラスのメソッドを呼び出すために使用されます。仮想関数の呼び出しはコンパイル時ではなく、実行時に解決される「遅延バインディング（レイトバインディング）」という仕組みで処理されます。派生クラスではvirtualキーワードが不要基底クラスのメンバ関数を一度virtualキーワード付きで宣言すると、その基底クラスから派生したすべてのクラスにおいて、その関数は自動的に仮想関数となります。そのため、派生クラス

C++では、基底クラスへのポインタを使って派生クラスのオブジェクトを削除する場合、基底クラスに仮想デストラクタ（virtual destructor）を定義する必要があります。仮想デストラクタを定義していないと、deleteを実行したときに派生クラスのデストラクタが呼び出されず、メモリやリソースが正しく解放されない問題が発生します。これは、ポインタの静的な型（この場合は基底クラス）だけを見てデストラクタが選択されるためです。デストラクタをvirtualとして宣言すれば、実行時の実際のオブジェクト型に応じて適切なデストラクタが呼び出されるようになります。サンプルコード#include<io

C++における仮想関数の仕組み（仮想機構）は、基底クラスのポインタが派生クラスのオブジェクトを指している場合にのみ正しく機能します。 そしてC++では、コンストラクタを仮想関数（virtual）にすることはできません。その理由は、クラスのコンストラクタが実行される時点では、メモリ上にまだ仮想関数テーブル（vtable）が存在せず、仮想ポインタ（vptr）も定義されていないためです。仮想機構そのものが動作する前提となる情報がまだ用意されていない段階でコンストラクタは呼ばれるため、コンストラクタは常に非仮想（non-virtual）である必要があります。 一方で、デストラクタを仮想関数にすること（

式ツリー（Expression Tree）とは、数式を表現するために用いられる二分木のことです。式ツリーでは、内部ノード（親ノード）が演算子に対応し、各葉ノードがオペランド（被演算子）に対応します。本記事では、後置記法（ポーランド逆記法）の式を入力として受け取り、対応する式ツリーを構築し、それを中順走査（インオーダー走査）で出力するC++プログラムを紹介します。後置記法は括弧が不要なため、コンピュータによる式の解析に非常に適した記法です。アルゴリズムBegin function construct_expression_tree(): オペランドの場合 Flag = 1

FusionTree（フュージョンツリー）は、wビット整数をキーとして連想配列（辞書）操作を高速に実現するための木構造データ構造です。各ノードが複数のキーを持つ多分木構造を採用しており、B木に似た性質を持ちながら、ビット演算を活用することで従来の平衡木より高速な検索が可能になります。 本記事では、6ビット整数を格納するFusionTreeをC++で実装するサンプルプログラムを、アルゴリズムの手順・コード・実行結果とともにわかりやすく解説します。 FusionTreeの主な特徴 1つのノードが最大6個のキーと7個の子ポインタを持つ多分木構造 ノード内のキーは常にソートされた状態で管理される

区間木（インターバルツリー、Interval Tree）は、区間を格納するために設計された順序付き木構造のデータ構造です。最大の特徴は、任意の区間や点と重なるすべての区間を効率的に検索できる点にあります。本記事では、C++による区間木の実装方法を、アルゴリズムの解説とサンプルコード、実行結果とあわせて紹介します。アルゴリズム挿入操作（insert）開始 関数 insert() は新しいノードを木に挿入する： 木が空の場合、新しいノードが根となる。 根の区間の下限値（low）を取得する。 新しい区間の下限値が根の下限値より小さい場合、左部分

概要 このプログラムは、スプレーツリー（Splay Tree）をC++で実装したものです。スプレーツリーは、アクセスされたノードをルートに移動させる「スプレイ」操作を行う自己調整型の二分探索木です。これにより、頻繁にアクセスされる要素へのアクセスが高速化されます。 クラス構造と主要関数 ノード構造体 s struct s { int k; // キー値 s* lch; // 左の子へのポインタ s* rch; // 右の子へのポインタ }; クラス SplayTree のメンバ関数 RR_Rotate(s* k2):

seekg() は、C++ の iostream ライブラリに含まれる関数の一つで、ファイル内の任意の位置へ移動（シーク）するために使用されます。「seek get」の略であり、主に入力ストリームから次に読み込む文字の位置を指定する役割を担います。C++ のファイル処理では、ファイルの途中からデータを読み込みたい場合などに非常に便利な関数です。 seekg() の構文 istream& seekg(streamoff offset, ios_base::seekdir dir); istream& seekg(streampos position); パラメータの説明 pos

C++における例外処理（Exception Handling）とは、プログラムの実行時に発生するエラー（ランタイムエラー）を適切に扱うための仕組みです。例外とは、実行時に送出（スロー）されるイベントのことで、C++ではすべての標準例外が std::exception クラスから派生しています。もし例外を捕捉しなかった場合、例外メッセージが出力され、プログラムは強制終了してしまいます。 C++標準では、例外関連のクラスが <exception> ヘッダに定義されており、プログラムの中で自由に利用できます。親子関係によるクラス階層は次のようになっています。 C++の主な標準例外クラス

C++とJavaはどちらも広く使われているオブジェクト指向プログラミング言語ですが、例外処理（Exception Handling）の仕組みには重要な違いがいくつか存在します。本記事では、両言語の例外処理における主な相違点を表形式と解説でわかりやすくまとめました。 C++とJavaの例外処理の主な違い一覧 Javaの例外処理C++の例外処理 スローできるのはThrowableクラスのオブジェクトのみすべての型を例外としてスローできる 後始末処理のためのfinallyブロックが存在するfinallyブロックは存在しない メソッドが投げる例外の一覧には「throws」キーワードを使用関数が

これは、セット(集合)を使用してダイクストラ法(Dijkstras Algorithm)を実装するC++プログラムです。この手法では2つの集合を扱います。与えられた始点ノードを根として最短経路木を構築し、一方の集合には最短経路木に既に含まれた頂点を、もう一方の集合にはまだ含まれていない頂点を格納します。そして各ステップごとに、未確定の集合の中から始点からの距離が最小となる頂点を見つけ出します。 アルゴリズムの手順 開始     最短距離を求める関数 dijkstra():     1) 最短経路木に含まれる頂点を記

グラフ理論におけるグラフ彩色問題とは、辺で直接つながっている（隣接する）頂点同士が同じ色にならないように、すべての頂点へ色を割り当てる古典的な問題です。本記事では、その代表的な解法である貪欲法（グリーディ法）を使ってグラフ彩色を実行するC++プログラムを、アルゴリズムの手順・サンプルコード・実行結果とあわせてわかりやすく解説します。貪欲法による彩色の基本的な考え方貪欲法は、各頂点を順番に処理し、「その時点で隣接頂点がまだ使っていない色のうち、最も小さい番号の色」を割り当てていくシンプルな手法です。常に最小の色数になることを保証するものではありませんが、計算量が少なく実装も容易なため、実用的な場

この記事では、C++を使って、グラフ上の2つの頂点（始点と終点）の間に存在する辺素パスの最大数を求めるプログラムを紹介します。辺素パスとは、互いに同じ辺（エッジ）を1つも共有しない複数のパスのことであり、その最大本数は2頂点間の最大フロー（最大流）と一致するという重要な性質を持っています。 アルゴリズム 開始 　　関数 bfs()：残余グラフ上で始点 s から終点 t への経路が 　　存在する場合に true を返す。 　　（これはグラフにまだ流せるフローが残っていることを示す） 終了 開始 　　関数 findDisPath()：与えられたグラフの最大フローを返す。 　　A) フローを 0

二分探索木（Binary Search Tree：BST）は、データを効率的に管理できるように整理された二分木です。BSTのすべてのノードは、以下の性質を満たす必要があります。ノードの右部分木に含まれるキーは、必ずその親ノードのキーより大きい。ノードの左部分木に含まれるキーは、必ずその親ノードのキーより小さい。すべてのキー値は重複しない（一意である）。各ノードが持てる子の数は最大2つまで。これらの性質により、BSTでは平均的にO(log n)の時間で要素の検索・挿入・削除が可能になり、整列済みデータの取り扱いにも適しています。本記事では、C++を用いてBSTに対する基本的な操作（検索・挿入・削

これは、Ford-Fulkerson（フォード・ファルカーソン）アルゴリズムを用いてネットワークフロー問題を実装したC++プログラムの解説記事です。BFS（幅優先探索）による増加パスの探索を繰り返すことで、ソース（始点）からシンク（終点）へ流せる最大流量を求めます。 ネットワークフロー問題とは ネットワークフロー問題は、各辺に容量（キャパシティ）が設定された有向グラフにおいて、始点から終点へ送れる流量の最大値を求める古典的な最適化問題です。物流網・通信網・配水管網などの設計や解析など、幅広い分野で応用されています。 この問題を解く代表的な手法がFord-Fulkerson法です。「残余グラ