作成 July 13, 2022
あるフォルダにあるすべてのサブフォルダとすべてのファイルを列挙したい場合、 「あるフォルダに対して直下のサブフォルダとファイルを列挙」を行い、 見つかったサブフォルダに対してまた同じ処理を行う必要があります。 これは「リカーシブ・コール」とか 「リカージョン」 と呼ばれているようです。
C/C++ でこれを実装するのは多少面倒で、時にはメモリの管理に危険を伴いますが、 wiki では 「連結リスト」 として紹介されている、Linked List や線形リストと呼ばれている方法で、 簡単に実装できることがわかりました。
すでに
このように、これから紹介するクラスは線形リストの実装目的で作成したのではなく、 自分で便利に使うために実装したものですので、 コードとしては理想的なものではないかもしれません。 この点については、事前にご了承いただいたうえで、先にお進みください。
開発環境は Windows + Visual C++ 2015 ですが、
なるべくそれに依存しないように書いています。
なお、線形リストをテストするプログラムは、Microsoft の
線形リストについての説明はここではしませんが、 簡単に言えば、1 つ 1 つのデータサイズが異なり、またいくつのデータがあるかを事前に定義しない配列で、 あるデータ（ノード）から次のデータ（ノード）に進むこともでき、 また逆にあるデータ（ノード）から前のデータ（ノード）にさかのぼることもできるデータ構造です。 あらかじめデータの最大数を決める必要もなく、それぞれのデータサイズの最大サイズを決める必要もないので便利です。
線形リスト自体はさまざまな用途に利用可能ですが、ここではフォルダとファイルの検索を目的としています。
なお、本サイトのご利用に際しては、必ずプライバシーポリシー（免責事項等）をご参照ください。
投稿 July 11, 2022
コードに入る前に、どのような形で実装できるのか、ダイアログアプリを作成して動作を確認できるようにしておきます。
まずは Visual C++ で MFC ダイアログアプリを作成し、このような画面を用意します。 線形リストそのものとは関係ありませんので、ダイアログアプリでなくても構いませんし、 テスト・確認用のアプリを作成しないでコードだけ確認していただいても構いません。
コードを簡単にするため、ダイアログはサイズ変更不可で、適当なサイズで作成しています。 ダイアログに検索対象フォルダのドロップを行いたいので、 ダイアログの Accept Files プロパティを True に変更しています。
ダイアログの上部はリストボックス IDC_LIST で、自動で
説明テキストを挟んでダイアログの下部もリストボックスで、IDC_FILE_LIST と ID を設定し、 こちらも自動で並べ替えが行われるように、Sort プロパティを True に設定しています。
なお、以降の Visual Studio でも仕様に変更がなければ、リストボックス作成時の Sort プロパティはデフォルトで True になっています。
投稿 July 11, 2022
ひとまず、サブフォルダやファイルを検索する対象とするフォルダの指定ができるようにします。
一般には「参照...」ボタンが用意されていて、 それをクリックするとフォルダを選択するダイアログが表示され、指定可能とするわけですが、 その指定方法が面倒くさく感じますので、 ここではフォルダまたはファイルのドロップのみでの指定とします。 本来は、両方実装されることが望ましいでしょう。
ここでは CDirByLinkedListDlg と名づけられたメインダイアログに、 ドロップを受け付ける関数 OnDropFiles を追加します。
改めて記載しておきますが、この関数が呼び出されるのはダイアログで Accept Files プロパティが True に設定されている場合のみで、 True に変更していない場合にはいくらこの関数を実装しても呼び出されることはありませんので、ご注意ください。
OnDropFiles 関数を追加するには、 コードの編集画面で Ctrl + Shift + X キーを同時に押して 「クラスウィザード」を起動し、 「メッセージ」のタブにある WM_DROPFILES メッセージを選び、「ハンドラーの追加」をクリックします。
「ハンドラーの追加」をする前に、念のため画面上部の「クラス名」の欄をしっかり確認しましょう。 メインダイアログではなく CDirByLinkedListApp のようなアプリケーションクラスが表示されている場合があり、 このまま追加してしまうと、ダイアログではなくアプリケーションクラスにハンドラ（関数）ができてしまいます。 うっかり違うファイルに追加してしまった場合には、その関数を選択し「ハンドラーの削除」で削除できますが、 コードはコメントアウトされますので、本当に不要ならコメントアウトされたコードを削除します。
今回のプログラムは単機能ですので、基本の呼び出し CDialogEx::OnDropFiles(hDropInfo); は、行いません。
フォルダのドロップならそのフォルダにあるファイルと、サブフォルダにあるフォルダやファイルを検索しますが、 ファイルがドロップされた場合には、そのファイルがあるフォルダを対象とするようにしようと思います。
void CDirByLinkedListDlg::OnDropFiles(HDROP hDropInfo)
{
//CDialogEx::OnDropFiles(hDropInfo);
TCHAR szBuf[MAX_PATH];
CFileFind ff;
CString strFile; // ドロップされたファイル名
CString strFolder; // ドロップされたフォルダ名
CString strMsg;
strFile.Empty();
strFolder.Empty();
CFileFind クラスは、 ファイルの検索を容易にする MFC クラスです。
CString クラスは、 文字列の操作を簡単にする、非常に高機能な MFC クラスです。
C/C++ による文字列操作 CString を代用
MFC の CString クラスの一部の機能を、C/C++ で実装することにトライしています。
必要な機能のみを拡張するのは、それほど難しくありません。
準備ができたら、 DragQueryFile 関数で、 第 2 引数に 0xFFFFFFFF を指定して、ドロップされたファイルの数を取得します。 ここでいう「ファイル」には「フォルダ」の意味も含まれます。
// ドロップされたファイル数を検査します。 UINT unDropped = DragQueryFile(hDropInfo, 0xFFFFFFFF, NULL, 0); if (unDropped < 1) { // 安全のため、ドロップファイルなしを除外します return; // 続きの処理は行いません } // ２つ以上のファイルがドロップされた場合は警告を表示します。 if (unDropped >= 2) { strMsg.Format(_T("２つ以上のフォルダ/ファイルがドロップされました。\n\n一度に検査できるのは１フォルダ/ファイルのみです。")); MessageBox(strMsg, _T("フォルダ/ファイルのドロップ"), MB_ICONEXCLAMATION | MB_OK); return; }
今回は 1 フォルダまたは 1 ファイルだけを扱いたいので、ドロップ数が 2 以上のときにはメッセージを表示し、続行しません。 念のため、その直前では、ドロップ数が 0 で呼び出された場合には何もしないよう、判定を入れています。 そういうケースがあるかないかはわかりませんが、もしあるとこのあとのコードに問題が出てきてしまいますので。
// ドロップされたフォルダまたはファイルを処理します。 // ここでは、unDropped は必ず 1 です。 for (UINT i = 0; i < unDropped; i++) { // ファイルを順次検査 // ドロップされたファイル名またはフォルダ名を取得します。 DragQueryFile(hDropInfo, i, szBuf, MAX_PATH); // ドロップされたものがフォルダなのかファイルなのかを判定します。 if (ff.FindFile(szBuf)) { ff.FindNextFile(); // フォルダの場合、そのまま strFolder に設定します。 if (ff.IsDirectory()) { strFolder = ff.GetFilePath(); } // ファイルの場合、そのファイルがあるフォルダ名を strFolder に設定します。 else { strFile = ff.GetFilePath(); strFolder = strFile.Left(strFile.GetLength() - ff.GetFileName().GetLength() - 1); } ff.Close(); } }
まず、ドロップされたファイルの数 unDropped だけループするようにしていますが、 本当は今回は 1 でしかここに来ませんので、ループは不要です。 一般化する目的のためだけに、ループの形になっています。
再び DragQueryFile 関数を呼び出し、 文字 TCHAR の配列 szBuf に、ドロップされたファイルのフルパスを取得します。
ドロップされたものがファイルなのかフォルダなのかを判断するため、 CFileFind クラスを利用し、 今ドロップされたファイルを検索しています。 ff.FindNextFile() 呼び出しは、最初に行う決まり事です（最初はファイルを指していませんので、「次のファイル」を指すようにします）。
ff.IsDirectory() 関数で、それがフォルダであるかどうかを判断しています。 TRUE が返ればフォルダですから、CString 変数 strFolder に、ff.GetFilePath() 関数で取得できる、 フォルダのフルパスを設定しています。
フォルダでない場合はファイルですから、いったん CString 変数 strFile にフルパスを取得し、 ff.GetFileName() 関数で得られるファイル名の長さと、区切りの￥サインの長さを引いた、 文字列の左側部分を CString 変数 strFolder に設定しています。
基本的にはドロップされたファイルが見つからないことはありませんから、 strFolder に対象フォルダ名が設定されたことになります。
// 正しく判断できなかった場合は、何もしません。
if (strFolder.IsEmpty()) {
strMsg.Format(_T("ドロップされたファイルまたはフォルダを検出できませんでした。\n[%s]"), szBuf);
MessageBox(strMsg, _T("フォルダ/ファイルのドロップ"), MB_ICONEXCLAMATION | MB_OK);
return;
}
対象フォルダ名が設定される strFolder は通常必ず設定されますが、 万が一、ドロップ直後に削除されるなどした場合に備え、 この関数のはじめでクリアしていますので、ちゃんと設定されたことを確認しています。
// ドロップされた（ファイルの）フォルダをサーチします。
SearchForFile(strFolder);
}
最後に、これから実装する SearchForFile 関数を呼び出して、 ダイアログに検索されたファイルを表示できるよう、列挙処理を行います。
投稿 July 11, 2022
まずはメインダイアログのヘッダーファイルにあるクラス定義で、関数の定義を行います。 もちろん関数名や引数名は、何でも構いません。
protected: bool SearchForFile(LPCTSTR pszPath); bool AddSubFolders(CsaLinkedList& lnk, LPCTSTR pszBaseFolder);
AddSubFolders 関数は、SearchForFile 関数が呼び出す補助関数です。 LPCTSTR 型は、書き換え不可の文字列ポインタです。
そして CsaLinkedList クラスがリンクリストの実装クラスで、別途独立して定義しますので、 この関数定義の前で、saLinkedList.h を include しておきます。
もちろんこのクラス名もファイル名も、これから実装を行う形ですから、自由な名前にしていただいて構いません。
メインダイアログの cpp に実装するコードです。
bool CDirByLinkedListDlg::SearchForFile(LPCTSTR pszPath)
{
CWaitCursor csr;
CsaLinkedList lnk;
CFileFind ff;
BOOL bLoop;
CString str;
CString strFind;
int nFolders;
CWaitCursor クラス については、気にする必要はありません。 これがスコープにいるうち（デストラクトされるまで）は、マウスポインタが砂時計などウェイトになるものです。
続く CsaLinkedList クラスが、今回のメインとなるリンクリストクラスです。
CFileFind クラスは ファイルを簡単に検索できる MFC クラスで、 BOOL は実体が int の TRUE または FALSE をとる型です。
CString クラスは、 文字列の操作を簡単にする MFC クラスです。
// 検索結果を出力するリストボックスを用意します。
CListBox* pList = (CListBox*)GetDlgItem(IDC_LIST);
pList->ResetContent();
作成したメインダイアログの上の部分を占めるリストボックス、IDC_LIST という名前を付けていますので、 それを pList に取得し、内容をクリアしています。
// フォルダ情報を格納する線形リストを用意します。 lnk.DeleteAll(); // クリアを保証 AddSubFolders(lnk, pszPath); // まずはそのフォルダにあるサブフォルダを取得
リンクリストのデータがクリアされていることを保証し、 AddSubFolders 関数を呼び出して、リンクリストに（直下の）サブフォルダを取得しています。 pszPath は、この関数の引数で受け取った文字列ですから、 ダイアログにドロップされたフォルダ名です。
この処理により、リンクリスト lnk には、ドロップされたフォルダの直下にあるサブフォルダが列挙されることになります。 サブフォルダの中にある、さらなるサブフォルダは設定されません。
// サブフォルダ内を検索していきます。 nFolders = lnk.GetNumNodes(); // 確認されたサブフォルダ数 for (int i = 0; i < nFolders; i++) { strFind.Format(_T("%s\\*.*"), lnk.GetNode(i)); // サブフォルダを探します if (ff.FindFile(strFind)) { do { bLoop = ff.FindNextFile(); // フォルダの場合のみ、リストに追加します。 if (ff.IsDirectory() && !ff.IsDots()) { lnk.AddString(ff.GetFilePath()); nFolders = lnk.GetNumNodes(); // 確認されたサブフォルダ数を更新 } } while (bLoop); ff.Close(); } }
lnk.GetNumNodes() は、リンクリストにある要素（ノード）数を返してくれます。 つまりドロップされたフォルダにあるサブフォルダ数が入っていますので、ひとまずその数だけをループし、さらなるフォルダの検索を行います。
CString クラスの strFind に、サブフォルダの 1 つを取り出し、ワイルドカード *.* で検索できるよう、準備をしています。
ff.FindFile 関数でワイルドカードでサブフォルダを検索します。 自分のフォルダを表す . と、親フォルダを表す .. は、最低限みつかるはずですが、念のため判定をしています。
続く do ループと bLoop の設定は、この CFileFind クラスを使うときの定番です。 結構忘れがちですから、意外と重要です。
ff.IsDirectory() は、見つかったものがディレクトリ（フォルダ）である場合は TRUE を返します。 と同時に、ff.IsDots() で、自分自身を表す . と親フォルダを表す .. であるかを調べ、 そうでない場合、つまり普通のフォルダである場合のみ、if の中を処理します。
サブフォルダが見つかった場合はリンクリスト lnk に、 lnk.AddString(ff.GetFilePath()); のようにフルパスを追加し、このループで検査するフォルダ数 nFolders を更新しています。 基本的には 1 つ追加しただけですので、nFolders は 1 をプラスするだけでも同じ結果になりますが、安全な処理を心がけています。
// 指定フォルダ自身が記録されていないので、追加します。 lnk.AddString(pszPath); // みつかったフォルダ・サブフォルダをリストに出力します。 nFolders = lnk.GetNumNodes(); // リストに設定されたデータ数 for (int i = 0; i < nFolders; i++) { str.Format(_T("[%s]"), lnk.GetNode(i)); pList->SetCurSel(pList->AddString(str)); // リストに追加してそれを選択 } return false; }
最後に、ドロップされた指定のフォルダがまだリンクリスト lnk に追加されていませんので、追加しておきます。
これでリンクリスト lnk に、ドロップされたフォルダを含めたサブフォルダすべてが設定されましたので、 lnk.GetNode(i) で順番に取り出して、 メインダイアログ上部のリストボックスに追加し、この関数は終了します。 このようなインデックスによる呼び出し方のほかに、リンクリストらしく、先頭のノードから順に次をたどり、最終項目までを繰り返す方法でも OK です。
なお、SearchForFile 関数から 1 回だけ呼び出される補助関数、AddSubFolders は、 引数で指定された、ドロップされたフォルダにあるサブフォルダをリンクリスト lnk に入れるだけのものですので、 細かいところは省略します。 コードは こちらにテキスト形式で提示しておきます。
投稿 July 11, 2022
メインダイアログの上の部分に列挙されたフォルダ名の 1 つをダブルクリックすると、 そこにあるファイルが列挙されるようにしました。
ユーザーの手を介さなければ、上の SearchForFile 関数が終了したら、IDC_LIST リストボックス、 あるいはリンクリスト lnk に設定されたフォルダのそれぞれについて、同じことを行えば全ファイルを列挙できることになります。
「コマンド」タブの IDC_LIST のような、 リストボックスの ID を選択し、右側に表示されるリストボックス・メッセージから LBN_DBLCLK のハンドラを追加します。
void CDirByLinkedListDlg::OnDblclkList()
{
CWaitCursor csr;
CFileFind ff;
CString strPath;
CString strFind;
BOOL bLoop;
// 検索結果を出力するリストボックスを用意します。
CListBox* pFileList = (CListBox*)GetDlgItem(IDC_FILE_LIST);
pFileList->ResetContent();
SetDlgItemText(IDC_PATH, _T(""));
そのフォルダにあるファイル一覧を出力するリストボックスは画面下部の IDC_FILE_LIST です。 IDC_PATH は、リストボックスの間にある説明の部分で、ここに検索したパス名を表示するため、ここではクリアしています。
それ以外は、ここまでの関数と同じです。
// ファイルを検索するフォルダ名を取得します。 CListBox* pList = (CListBox*)GetDlgItem(IDC_LIST); int nSel = pList->GetCurSel(); if (nSel < 0) { pFileList->AddString(_T("フォルダが選択されていません。")); return; } pList->GetText(nSel, strPath); strPath = strPath.Mid(1, strPath.GetLength() - 2); // 両端のカッコを外す SetDlgItemText(IDC_PATH, strPath);
リストボックスでダブルクリックされた項目のインデックス nSel を取得し、 その文字列を strPath に設定しています。
このとき、リストボックスへの出力でカッコで囲んでいましたので、 両端のカッコをはずしたものを strPath に再設定し、検索した（する）パス名を画面に表示します。
// strPath にあるファイルを IDC_FILE_LIST に列挙します。
strFind.Format(_T("%s\\*.*"), strPath);
if (!ff.FindFile(strFind)) {
pFileList->AddString(_T("検索に失敗しました。"));
return;
}
strPath に設定されたパスに *.* を追加してワイルドカード検索できるよう文字列 strFind を作成し、検索します。 少なくとも自身と親フォルダがヒットするはずですので失敗することはないのですが、 安全のため、何も見つからないケースを除外しておきます。
do {
bLoop = ff.FindNextFile();
// ファイルの場合のみ、リストに追加します。
if (!ff.IsDirectory()) {
pFileList->AddString(ff.GetFileName());
}
} while (bLoop);
ff.Close();
CFileFind クラスの定番の書き方により、「ファイル」と認識されるもののファイル名のみを、 メインダイアログ下部のリストボックスに追加していきます。
// ファイルが 1 つもなかった場合は、それを表示します。
if (pFileList->GetCount() < 1) {
pFileList->AddString(_T("ファイルはありません。"));
}
}
もしファイルが何もなかった場合には、わかりやすいよう「ファイルはありません。」と出力します。
投稿 July 11, 2022
まずはヘッダです。 ここまでで用いているファイル名なら、saLinkedList.h です。
typedef struct tag_saLinkedList { BYTE* pData; // 確保したデータ領域を指すポインタ int nSize; // データサイズ struct tag_saLinkedList* pPrev; // 前のノード struct tag_saLinkedList* pNext; // 次のノード } SsaLinkedList, *PSsaLinkedList;
1 つのノードが持つ情報の構造体定義です。
BYTE* は、unsigned char、つまり 1 バイトの符号なしデータ型へのポインタです。 このノードに設定されたデータを保持するメモリへのポインタを保持します。
int 型の nSize は、データサイズです。 文字列データの場合は、末尾の終了コード NULL を含めた、確保したメモリのサイズとしています。
戻って、この構造体は struct tag_saLinkedList という名前にしています。 このノードの前のノードを指すためにこの構造体を指すポインタの pPrev を、 このノードの次のノードを指すためにこの構造体を指すポインタの pNext を定義しています。 自身と同じ構造体を指す必要がありますので、このような定義になっています。 void* で定義しておいて使うときにキャストしてもいいと思いますが、毎回キャストが面倒になりそうです。
また戻って、struct 定義の前に typedef と書いていますので、 この構造体に別名を付けるとしています。
構造体本体は SsaLinkedList に、そしてこの構造体へのポインタは PSsaLinkedList となるように、指定しています。 何だか変な書き方に見えなくもありませんが、こう書くようです。
ここから、双方向リンクリスト管理クラスの定義です。
/** * 双方向リンクリスト管理クラス CsaLinkedList */ class CsaLinkedList { public: /** * constructor */ CsaLinkedList(); /** * destructor */ ~CsaLinkedList();
クラス名は CsaLinkedList としていますが、自由で構いません。
実装内容についてはあとに記載していますが、上記文字の部分からリンクさせていますので、今すぐ参照することもできます。 以下、同じようにリンクを作成してあります。
/**
* リストの末尾に新しいノードを追加します。
*/
bool Add(BYTE* pNode, int nSize);
リストの末尾に新しいデータを追加する Add 関数です。
引数 pNode でそのノードが保持するデータを、nSize でそのサイズを指定します。 データはコピーされ保持されますので、この関数を実行後は元のデータが削除されても問題ありません。
/**
* リストの途中に新しいノードを追加します。
* nIndex の位置にノードが追加されます。
* nIndex = 0 なら、リストの先頭にノードが追加されます。
*/
bool Insert(int nIndex, BYTE* pNode, int nSize);
リストの途中に新しいノードを追加する Insert 関数です。
これが比較的簡単にできることが、線形リストの特徴と言っていいでしょう。 もし配列で管理されているなら、途中にデータを追加したら、それ以降のデータをうしろにずらす必要がでてきます。
/**
* 保持しているノード数を返します。
*/
int GetNumNodes(void) {
return m_nCount;
}
保持しているノード数を返す GetNumNodes 関数です。
保持しているノード数は int 変数 m_nCount に記録することにしてありますので、 この関数で保持しているノード数を知ることができます。 処理が短いので、ここに関数本体も記述しています。
/** * カレントノードをリストの先頭に移動します。 */ bool SeekToBegin(void); /** * カレントノードをリストの末尾に移動します。 */ bool SeekToEnd(void);
「現在の」ノードの位置をリストの先頭に移動させる SeekToBegin 関数と SeekToEnd 関数です。
現在指しているノード（カレントノード）のデータは、このあとに定義している GetCurNode 関数で取得可能としています。 このすぐあとに定義している 3 関数とあわせて、リストのデータに連続的にアクセスできる方法を提供しています。
/** * カレントノードを指定のインデックスに移動します。 * 先頭のノードのインデックスは 0 です。 */ bool MoveTo(int nIndex); /** * カレントノードを１つ進めます。 */ bool Next(void); /** * カレントノードを１つ戻します。 */ bool Prev(void);
カレントノードを好きな位置にダイレクトに移動させる MoveTo 関数と、 ノードを次、あるいは前へとたどるときに使う Next 関数、 Prev 関数です。
MoveTo 関数は使う機会がないかもしれませんが、 Next 関数と Prev 関数は、リストのデータに連続的にアクセスするときに使用できます。
/**
* カレントノードのデータを返します。
* bMoveCur に true を指定すると、カレントノードは１つ先に進みます。
* pnSize に int ポインタを指定すると、そのデータのサイズを返します。
* 例）while (pData = GetCurNode(true)){ do something with pData; };
*/
BYTE* GetCurNode(bool bMoveCur = false, int* pnSize = NULL);
カレントノードのデータを返す GetCurNode 関数です。
第 1 引数 bMoveCur に true を設定して呼び出すと、カレントノードが 1 つ先に進みます。 つまり、連続呼び出しで、リストの最後まで連続的に取得できるということになります。 引数省略時には false ですので、カレントノードは移動しません。 お好みにより、引数省略時の値を true にしてもいいかもしれません。
第 2 引数に int 型のポインタを指定すると、そこにデータサイズを設定します。 サイズが必要なければ、引数を省略、あるいは NULL を指定します。
/**
* 指定のノードのデータを返します。
* 先頭のノードのインデックスは 0 です。
* bMoveCur に true を指定すると、カレントノードは１つ先に進みます。
* pnSize に int ポインタを指定すると、そのデータのサイズを返します。
*/
BYTE* GetNode(int nIndex, bool bMoveCur = false, int* pnSize = NULL);
指定のインデックスを持つノードのデータを返す GetNode 関数です。
カレントノードを移動してから GetCurNode 関数を呼び出すのと同じ機能です。 インデックス指定を便利に扱えるよう、直接インデックスを指定してデータを取り出せるようにしています。 第 2、第 3 引数は、直前のカレントノードからのデータ取得と同じです。
カレントノードは、指定したインデックスのノード、あるいは bMoveCur に true を指定した場合はその次のノードに移動されます。
/**
* すべてのノードを削除し、確保したメモリを解放します。
*/
void DeleteAll(void);
保持しているノードをすべて削除し、確保したメモリを解放する DeleteAll 関数です。
それぞれのノードを追加したときにはメモリが確保され、ずっと保持されていますので、 利用が終了したときには、それらのメモリが解放されなくてはいけません。
/**
* 指定のノードを削除します。
* 先頭のノードのインデックスは 0 です。
* インデックスを省略した場合は、カレントノードを削除します。
*/
bool Delete(int nIndex = -1);
指定したインデックスのノードだけを削除する Delete 関数です。
リンク構造ですので、このようなことを比較的簡単に行うことができます。 もし配列での管理なら、リストの途中のデータを削除したら、それ以降のデータを 1 つ前に詰める必要があるでしょう。
/**
* 【ユーティリティ】テキストを（末尾に）追加します。
* NULL-terminated 文字列の場合は、nSize を指定しなくても自動的に決定されます。
* 文字列無しは追加できません（AddString("") はノードを追加しません）。
*/
bool AddString(LPCTSTR pszText, int nSize = -1);
実装関数の最後は、文字列を扱うためのユーティリティ AddString 関数です。
簡単に文字列を扱えるよう、別関数としています。 NULL 終わりの文字列を渡す場合は、サイズは自動計算されますので、ただ文字列を渡すだけでノードを増やせます。
protected: /** * 先頭のダミーデータ（シード） * このノードはデータを持ちません。 */ SsaLinkedList m_seed; /** * カレントノードを指すポインタ */ PSsaLinkedList m_pCurrent; /** * 保持しているノード数 */ int m_nCount; };
データを定義したら、ヘッダは終わりです。
投稿 July 11, 2022
あらかじめヘッダファイル、ここでは saLinkedList.h を #include しておきます。
コンストラクタです。
/** * constructor */ CsaLinkedList::CsaLinkedList() { m_seed.pData = NULL; // シードはデータを持ちません m_seed.nSize = 0; // 確保したデータサイズ m_seed.pPrev = NULL; // １つ前のノード m_seed.pNext = NULL; // 次のノードはまだありません m_pCurrent = NULL; // 現在指しているノードはありません m_nCount = 0; // 保持しているノード数は 0 です }
m_seed は SsaLinkedList 構造体で、 先頭のノードとして特別に定義されるもので、データは持ちません。 先頭のノードですので前のノード pPrev はなく、 初期状態ですので次のノード pNext もありません。
続けてカレントノード m_pCurrent を「なし」とし、 現在保持しているノード数 m_nCount も 0 に設定しています。
デストラクタです。
/** * destructor */ CsaLinkedList::~CsaLinkedList() { DeleteAll(); // 確保したメモリを解放します }
確保したメモリが確実に解放されるよう、すべてのノードの削除関数 DeleteAll を呼び出しています。
新しいノードをリストの末尾に追加する Add 関数です。
/** * リストの末尾に新しいノードを追加します。 */ bool CsaLinkedList::Add(BYTE* pNode, int nSize) { // 新しいノードを作成します。 PSsaLinkedList pList = new struct tag_saLinkedList; if (!pList) { // メモリを確保できなかった場合 return false; // 追加できません }
PSsaLinkedList は、struct tag_saLinkedList 構造体を指すポインタです。 new で新しいノードのメモリを確保し、いったん pList に設定しています。 もし NULL が返された場合はノードを作成できていませんので、false を返して処理を終わります。
// 必要なメモリを確保します。 BYTE* pData = new BYTE[nSize]; // nSize バイトのメモリを確保 if (!pData) { // メモリを確保できなかった場合 delete pList; // 作成したノードを削除 return false; // 追加できません } memcpy((void*)pData, pNode, nSize); // データをコピー
新しいノードのメモリを確保できましたので、次にデータをコピーして保持するためのメモリを確保しています。
ここでは nSize で必要サイズを受け取っていますので、unsigned char、符号なし 1 バイトデータの BYTE を用意しています。 メモリを確保できなかった場合は、先に確保した新しいノード用のメモリも解放して、false を返します。
データ用のメモリを確保できた場合には、引数で受け取ったデータ pNode をコピーします。
// 新しいノードに情報を設定します。 pList->pData = pData; // データ領域を指すポインタ pList->nSize = nSize; // データサイズ pList->pPrev = NULL; // 仮に、前のノードなし pList->pNext = NULL; // 次のノードはありません
pList は SsaLinkedList 構造体を指しますので、 データ pData には確保したメモリにデータをコピーしたポインタを、 サイズ nSize には確保したメモリのサイズを設定しています。 いったん、前のノード pPrev と次のノード pNext に NULL を設定していますが、前のノードについては、このあと正しく設定される必要があります。
// 最初のノードならシードがポイントします。 if (!m_seed.pNext) { // シードが指すノードがない場合 m_seed.pNext = pList; // 新しいノードを設定します pList->pPrev = &m_seed; // 新しいノードの直前はシードです m_pCurrent = pList; // 追加したノードを現在のノードとします }
新しいノードが追加された場合は、前のノードが新しいノードを指し、 新しいノードは前のノードを指す必要があります。
先頭の管理用ノード m_seed の次のノードが設定されていない場合、 追加されるノードは最初のデータノードとなりますので、そこに設定します。 同時にカレントノードを、追加した新しいノードに設定しています。
// 最初のノードではない場合は、リンクに追加します。 else { PSsaLinkedList pLast = m_seed.pNext; // 先頭のノード while (pLast->pNext) { // 次のノードがあるうちは先に進めます pLast = pLast->pNext; } // 最後のノードの情報を設定します。 pLast->pNext = pList; // 新しいノードを設定します pList->pPrev = pLast; // 直前のノードを設定します }
先頭の管理用ノード m_seed の次のノードが設定されている場合は、 すでにリストがあるということですので、最後のノードに追加する形を取らなくてはなりません。
pLast にデータノードの先頭を設定し、次のノード pNext が設定されているうちは次へとたどり、 次のノードがなくなったところで pLast が最後のノードを指して、while ループを脱出します。
最後のノードを指している pLast の次のノードを今作成した新しいノードを指すようにし、 今作成した新しいノードの前のノードとして、これまでの最後のノード pLast を設定します（pLast と pList が似た名前になってしまい、見にくいですね）。
// ノードの数をカウントします。
m_nCount++;
return true;
}
ノードを 1 つ追加しましたので、ノード数をカウントしている m_nCount に 1 を加えておきます。
m_nCount を管理しなくても m_seed から数えればいつでもノード数はわかりますが、リストが大きくなってデータ数を欲しくなるたびに追いかけるのは非効率的と考えました。
新しいノードをリストの途中に追加する Insert 関数です。
ノードの途中に新しいノードを挿入するのは、リスト構造を持っているため、簡単になります。
/** * リストの途中に新しいノードを追加します。 * nIndex の次にノードが追加されます。 * nIndex = 0 なら、リストの先頭にノードが追加されます。 */ bool CsaLinkedList::Insert(int nIndex, BYTE* pNode, int nSize) { // インデックス指定を検証します。 if (nIndex < 0 || nIndex >= m_nCount) { // 0 未満または末尾以上は不正 if (nIndex == m_nCount) { // 末尾を意味するなら return Add(pNode, nSize); // 末尾に追加します } return false; }
引数 nIndex で指定されたノードの次に、新しいノードを追加します。
// 新しいノードを作成します。 PSsaLinkedList pList = new struct tag_saLinkedList; if (!pList) { // メモリを確保できなかった場合 return false; // 追加できません } // 必要なメモリを確保します。 BYTE* pData = new BYTE[nSize]; // nSize バイトのメモリを確保 if (!pData) { // メモリを確保できなかった場合 delete pList; // 作成したノードを削除 return false; // 追加できません } memcpy((void*)pData, pNode, nSize); // データをコピー
Add 関数と同じように、pList に新しいノードのためのメモリを確保し、 pData にデータをコピーするためのメモリを確保して、データをコピーしています。
// 新しいノードに情報を設定します。 pList->pData = pData; // データ領域を指すポインタ pList->nSize = nSize; // データサイズ pList->pPrev = NULL; // 仮に、前のノードなし pList->pNext = NULL; // 次のノードはありません
追加する新しいノードのデータを設定しています。 前のノード pPrev、 次のノード pNext とも、正しく設定される必要がありますが、いったん NULL を割り当てています。
// 挿入する直前のノードを探します。 PSsaLinkedList pPos = m_seed.pNext; // 先頭のノードを指します for (int i = 0; i < nIndex; i++) { // 指定のインデックス（の次）まで進めます pPos = pPos->pNext; }
どの位置に挿入するかが引数の nIndex で指定されていますので、リストを先頭からたどり、 pPos の前に新しいノードが挿入される位置を見つけます。
// リンクを修正します。 pList->pNext = pPos; // 新しいノードはこのノードを指します pPos->pPrev->pNext = pList; // このノードの１つ前の次を新しいノードにします pList->pPrev = pPos->pPrev; // 前のノードを設定します pPos->pPrev = pList; // このノードの１つ前を新しいノードにします m_pCurrent = pList; // 現在のノードを今追加したノードにします // ノードの数をカウントします。 m_nCount++; return true; }
新しいノードの次 pNext が今見つけた pPos を指すようにし、 pPos の前のノードの次、pPos->pPrev->pNext が新しいノードを指すようにします。 これで、リストの前方から後方の向きで、新しいノードが間に挟まった形になりました。
リストの後方から前方への逆向きも設定が必要です。 新しいノードの前のノードは、次のノード pPos の前のノードを指すようにし、 次のノードの pPos の前のノードは、新しいノードを指すようにします。 そしてカレントノードを、今追加したノードに設定しています。
このリンクの設定の順序は、注意深く行わないとリストが壊れてしまいます（線形にならなくなります）。
とりあえず実装してはありますが、多用するのであれば、 「カレントノードの次の挿入」や、 「カレントノードのインデックスを返す」関数があると良さそうですね。
カレントノードをリスト先頭に移動する SeekToBegin 関数です。
リストの先頭から順にノードを次へ、次へとたどって最後まで到達したい場合に有用です。
/** * カレントノードをリストの先頭に移動します。 */ bool CsaLinkedList::SeekToBegin(void) { m_pCurrent = m_seed.pNext; return m_pCurrent ? true : false; // データがなければ false を返します }
データを持つ先頭のノードは、管理用のノード m_seed が指す次のノードです。 カレントノードを指すポインタ m_pCurrent に設定しますが、 データを持つノードがない場合、m_pCurrent が NULL になってしまいますので、その場合は false を返しています。
カレントノードをリストの末尾に移動する SeekToEnd 関数です。
使うとすれば、リストのデータを逆順に取得する、というところでしょうか。
/** * カレントノードをリストの末尾に移動します。 */ bool CsaLinkedList::SeekToEnd(void) { if (!(m_pCurrent = m_seed.pNext)) { // 先頭のノードを指します return false; // データがありません } while (m_pCurrent->pNext) { m_pCurrent = m_pCurrent->pNext; // 次のリンクを辿ります } return m_pCurrent ? true : false; }
カレントノード m_pCurrent を最初のデータのあるノードに設定しますが、 リストにデータが 1 つもない場合は NULL になりますので、その場合は false を返して終了とします。
データがあれば次を指すポインタ pNext でリストをたどり、 次のデータがなくなったところが最後ですので、while ループを脱出します。 念のため、m_pCurrent の値を検査し、基本的にはここでは true しか返しません。
カレントノードを指定のインデックスに移動する MoveTo 関数です。
リストの途中に、インデックスを指定してダイレクトに移動したいケースは、ほとんどないかもしれません。
/** * カレントノードを指定のインデックスに移動します。 * 先頭のノードのインデックスは 0 です。 */ bool CsaLinkedList::MoveTo(int nIndex) { if (!(m_pCurrent = m_seed.pNext)) { // 先頭のノードを指します return false; // データがありません }
まずは SeekToEnd 関数と同じように、 カレントノード m_pCurrent に先頭のデータのあるノードを設定しています。
for (int i = 0; i < nIndex; i++) { // 指定のインデックスまで
if (m_pCurrent->pNext) { // 次のリンクを辿ります
m_pCurrent = m_pCurrent->pNext;
}
else { // リストの最後まで到達
return false; // 移動できません（末尾をポイント）
}
}
return m_pCurrent ? true : false;
}
引数 nIndex で指定されたインデックスまで進めます。 nIndex が 0 のときは、for ループは 1 回も実行されませんので、m_pCurrent は先頭のノードを指したままとなります。
指定された nIndex が大きすぎてリストの末尾に到達してしまった場合には、false を返して失敗となりますが、 カレントノードはリストの末尾に移動されていますので、ご注意ください。
まとめると、ここに渡す nIndex は、0 が先頭のノードであり、末尾は m_nCount - 1 ということになります。 これはこのあとの GetNode 関数でも同じになります。
カレントノードを 1 つ先に進める Next 関数です。
/** * カレントノードを１つ進めます。 */ bool CsaLinkedList::Next(void) { // カレントノードが有効な場合 if (m_pCurrent) { if (m_pCurrent->pNext) { // 次のノードがある場合 m_pCurrent = m_pCurrent->pNext; // それを指します return true; } }
カレントノード m_pCurrent が有効な場合は、単純に次のノードがあればそこに移動とします。 次のノードがない場合（末尾の場合）、カレントノードはそのままで false を返します。
// カレントノードが無効な場合 else { if (m_seed.pNext) { // 先頭のノードがあれば m_pCurrent = m_seed.pNext; // 先頭のノードを指します return true; } } // 次のノードがない場合、またはデータが１つもない場合、false を返します。 return false; }
そもそもカレントノードが無効な場合、通常はデータのあるノードが 1 つもない場合のみですが、 念のため最初のデータのあるノードを検査し、あればそこに移動して、true を返します。 なければ false を返します。
カレントノードを 1 つ戻す Prev 関数です。
/** * カレントノードを１つ戻します。 */ bool CsaLinkedList::Prev(void) { // カレントノードが有効な場合 if (m_pCurrent) { if (m_pCurrent->pPrev != &m_seed) { // 前のノードがシード以外の場合 m_pCurrent = m_pCurrent->pPrev; // それを指します return true; } } // カレントノードが無効、または今が先頭のノードなら、false を返します。 return false; }
カレントノードが有効な場合は、前のノード pPrev がどこを指しているかを確認し、 データのあるノードを指している場合はそこに移動します。
カレントノードがないか、前のノードがデータのない管理用ノード m_seed を指している場合は、 前に移動することはできませんので、false を返します。
カレントノードのデータを返す GetCurNode 関数です。
/** * カレントノードのデータを返します。 * bAuto に true を指定すると、カレントノードは１つ先に進みます。 * pnSize に int ポインタを指定すると、そのデータのサイズを返します。 * 例）while (pData = GetCurNode(true)){ do something with pData; }; */ BYTE* CsaLinkedList::GetCurNode(bool bMoveCur /*= false*/, int* pnSize /*= NULL*/) { BYTE* pRet = NULL; // 返すデータ領域へのポインタ // カレントノードが設定されていない場合 if (!m_pCurrent) { if (m_seed.pNext) { // 先頭のノードがあれば m_pCurrent = m_seed.pNext; // それを設定します } else { // 先頭のノードがなければ if (pnSize) { *pnSize = 0; // サイズを 0 とします } return NULL; // NULL を返します } }
まず、カレントノード m_pCurrent が設定されていない場合の例外的な処理を書いていますが、 通常はここに入ることを想定しません。
// カレントノードのデータ領域を確認します。 pRet = m_pCurrent->pData; if (pnSize) { *pnSize = m_pCurrent->nSize; // データサイズを設定 }
ここに来るときにはカレントノード m_pCurrent は有効です。
BYTE* の pRet にデータ領域を指すポインタをコピーし、引数で pnSize が指定されていれば、そのサイズを設定します。
// 自動で進める場合は Next() を呼び出します。
if (bMoveCur) {
Next();
}
return pRet;
}
引数でカレントノードを先に進めるよう、bMoveCur に true が指定されている場合は、 Next 関数を呼び出して、1 つ先に進めています。
そういう使い方はしていませんが、 ここで返しているのは確保したメモリへのポインタ直接ですので、 呼び出し側が取得したポインタを用いてノードの内容を書き換えることが可能です。
考えようによっては便利ですが、考えようによっては大変危険ですので、 自分だけで使うのでなければ const BYTE* みたいに書き換え不可にするほうがいいかもしれません （検証していませんので、これだとポインタの値を書き換えられないだけでその内容を書き換えられてしまう可能性もあります）。
指定したインデックスのノードのデータを返す GetNode 関数です。
GetCurNode 関数は、あらかじめカレントノードをデータが欲しいノードに移動させておく必要がありますが、 この関数ではインデックス指定を可能としています。 つまり、MoveTo 関数と GetCurNode 関数を組み合わせたもの、と言えます。
/** * 指定のノードのデータを返します。 * 先頭のノードのインデックスは 0 です。 * bMoveCur に true を指定すると、カレントノードは１つ先に進みます。 * pnSize に int ポインタを指定すると、そのデータのサイズを返します。 */ BYTE* CsaLinkedList::GetNode(int nIndex, bool bMoveCur /*= false*/, int* pnSize /*= NULL*/) { PSsaLinkedList pCur = m_pCurrent; // カレントノード BYTE* pRet = NULL; // 指定のノードをカレントにします。 if (!MoveTo(nIndex)) { // 移動できなかった場合 if (pnSize) { *pnSize = 0; // サイズを 0 とします } m_pCurrent = pCur; return NULL; // NULL を返します }
MoveTo 関数呼び出しで、指定されたインデックス nIndex にカレントノードを移動させています。
カレントノードを移動させる前に、引数 bMoveCur で「カレントノードを移動しない」が指定されている場合に備え、pCur にコピーしています。
// 指定インデックスのノードに移動できた場合 pRet = GetCurNode(false, pnSize); // カレントノードのデータを取得 if (!bMoveCur) { // 自動的に進めない場合 m_pCurrent = pCur; // 元の値に戻します } return pRet; }
カレントノードのデータへのポインタを pRet に取得しています。 そしてカレントノードを移動させない指定の場合は、バックアップしておいた元のカレントノードに戻しています。
すべてのノードを削除し、確保したメモリを解放する DeleteAll 関数です。
/** * すべてのノードを削除し、確保したメモリを解放します。 */ void CsaLinkedList::DeleteAll(void) { PSsaLinkedList pList = m_seed.pNext; // データのあるノードの先頭 PSsaLinkedList pCur; // 先頭からノードを辿りながら確保したメモリを解放します。 while (pList) { // ノードがあるうちはループ if (pList->pData) { delete[] pList->pData; // 確保したメモリを解放します } if (!pList->pNext) { // 次のノードがない場合 delete pList; // 自身を削除して終わります break; } // 次のノードがある場合 pCur = pList; // いったん pCur にコピーします pList = pList->pNext; // pList は次のノードを指します delete pCur; // データを解放したノードを削除します }
SsaLinkedList 構造体 pList に先頭のノードを設定し、 while ループで最後のノードまでたどっていきます。
確保したメモリがあることを確認し、確保したメモリを解放します。
次のノードがない、つまりはこれが最後のノードである場合は、自分を削除して while ループから脱出します。
次のノードがある場合は、今指しているノードを pCur が指すようにポインタをコピーし、 検査するノード pList を 1 つ先に進めます。 その後、コピーしたポインタ、現在の pList から見れば 1 つ前のノードとなった pCur のメモリを解放しています。
いったん pCur に設定しなくても、pList を 1 つ進めて、1 つ先を指す pList の pPrev を削除しても同じかもしれません。
// シードを初期化します。
m_seed.pData = NULL;
m_seed.nSize = 0;
m_seed.pPrev = NULL;
m_seed.pNext = NULL;
m_pCurrent = NULL;
m_nCount = 0;
}
これですべてのノードが削除されましたので、管理用ノード等を初期化して完了です。
指定のノードだけを削除する Delete 関数です。
/** * 指定のノードを削除します。 * 先頭のノードのインデックスは 0 です。 * インデックスを省略した場合は、カレントノードを削除します。 */ bool CsaLinkedList::Delete(int nIndex /*= -1*/) { PSsaLinkedList pToDel; int i; // インデックス指定が不正の場合 if (nIndex >= m_nCount) { // 末尾のデータより大きいとき return false; // 削除できません }
まずは指定されたインデックス nIndex が有効であるかを確認します。 インデックスは 0 から始まり、データ数 m_nCount - 1 までが有効となりますので、そうでない場合は false を返し、削除を行いません。
// 引数省略または負の値を指定の場合 if (nIndex < 0) { pToDel = m_pCurrent; // カレントノードを指します } // 削除するノードのインデックスが指定されている場合 else { pToDel = m_seed.pNext; // 先頭のノードを指す for (i = 0; i < nIndex; i++) { // 指定のノードまでリンクを辿ります if (!(pToDel = pToDel->pNext)) {// 途中で終端に到達 return false; // 削除できません } } }
特例として、削除するインデックスに負の値を指定した場合、カレントノードを削除することとしています。
正常な範囲でのインデックス指定の場合は、先頭からリストをたどり、削除対象のノードを pToDel に設定します。 ただし途中で終端に到達してしまった場合、つまり m_nCount と実体が合わなくなっていた場合には、削除は行いません。
// リンクを修正します。 pToDel->pPrev->pNext = pToDel->pNext; // １つ前のノードの次が、次のノードになるように if (pToDel->pNext) { // 次のノードがある場合 pToDel->pNext->pPrev = pToDel->pPrev; // その前のノードが１つ前のノードになるように }
pToDel で指定されたノードを削除します。
削除する前に、1 つ前が指すノードの「次のノード」を、削除されるノードの「次のノード」に書き換えて、自分をスキップしてもらいます。 自分が最後のノードでない場合には、次のノードの「前のノード」が、削除されるノードの「前のノード」になるように、書き換えます。 ちなみに「前のノード」は、例え先頭でも m_seed を指しますから、NULL の可能性はありません。
// リンクから外したノードを削除します。 delete[] pToDel->pData; // 確保したメモリを解放します delete pToDel; // 確保したノードを解放します m_nCount--; // カウントを減算します return true; }
削除されるノードが線形リストから外れましたので、確保したメモリを解放し、そして自分を解放します。 保持されているノード数 m_nCount をマイナスしたら完了です。
テキスト（文字列）をリストの末尾に追加するユーティリティ、 AddString 関数です。
/** * 【ユーティリティ】テキストを（末尾に）追加します。 * NULL-terminated 文字列の場合は、nSize を指定しなくても自動的に決定されます。 * 文字列無しは追加できません（AddString("") はノードを追加しません）。 */ bool CsaLinkedList::AddString(LPCTSTR pszText, int nSize /*= -1*/) { TCHAR* pData; int i; bool bRet; // 引数を検証します。 if (!pszText || nSize > 0xFFFF) { // テキスト指定がないか大きすぎる場合 return false; // 追加できません }
引数を確認しています。 追加する文字列が NULL の場合や、指定サイズが 65535 文字を超える場合は拒否しています。
サイズが省略されている場合は -1 ですので拒否されず、このあと自動計算します。
// サイズ指定がない場合は、自動的に計算します。 if (nSize < 0) { nSize = lstrlen(pszText); // lstrlen は UNICODE でも正しい値を返します } if (nSize < 1) { // 0 文字となった場合 return false; // 追加できません }
サイズ指定がないか、負の値が指定された場合は、文字列のサイズで自動計算します。 自動計算して nSize が確定したあと、それでも 0 以下の値になってしまった場合には、追加できません。
// 追加するデータを用意します。 if (!(pData = new TCHAR[nSize + 1])) { // UNICODE 対応のため TCHAR を追加します return false; // メモリを確保できません } ZeroMemory(pData, sizeof(TCHAR) * (nSize + 1)); // 全体をゼロクリア for (i = 0; i < nSize; i++) { pData[i] = (TCHAR)pszText[i]; // １文字づつコピー }
追加するデータを用意します。 データサイズは、このクラスを利用するプロジェクトがマルチバイトか UNICODE かにより 1 文字のバイト数が異なりますので、 BYTE や char ではなく、TCHAR マクロを使う必要があります。
念のため確保したメモリをゼロクリアし、文字列データをコピーします。 ここでもマルチバイトか UNICODE かを意識しています。
// 文字列を追加します。 bRet = Add((BYTE*)pData, sizeof(TCHAR) * (nSize + 1)); // 一時的に確保したデータ領域を解放します。 delete[] pData; return bRet; }
Add 関数にデータを渡して、リストの末尾に追加してもらいます。
Add 関数はデータを新しく確保したメモリにコピーして保持しますので、 ここで作成したデータ領域 pData は解放する必要があります。
以上で実装が完了です。
使いたい状況に応じて AddInt 関数や Sort 関数を実装するともっと便利かもしれません。
Enjoy !!
Visual Studio Community 2019 を共存インストールする（デスクトップ）