RSS
トップページ – アルゴリズムとデータ構造編 – 【データ構造】第３章
問題① この章の最初のサンプルプログラムに、連結リストに含まれている要素の個数を返すコマンドを追加してください。
コード全体を掲載すると非常に長くなるので、関数本体だけ挙げておきます。
/*
要素数をカウントする。
戻り値：
リストに含まれる要素の個数。
*/
int count_list(void)
{
struct LinkedList_tag* p = gHead.next;
int count = 0;
while( p != NULL ){
count++;
p = p->next;
}
return count;
}これはそれほど難しくはないでしょう。ダミーの先頭要素だけ避けて、nextポインタをたどりながら、要素数を数えています。
問題② この章の最初のサンプルプログラムに、連結リストの要素を逆順に並べなおすコマンドを追加してください。
これは結構難しいでしょう。まず、実装例を挙げます。
/*
リストを逆順にする。
*/
void reverse_list(void)
{
struct LinkedList_tag* p = gHead.next;
struct LinkedList_tag* work = NULL;
while( p != NULL ){
// この後、p->next を書き換えるので退避しておく
struct LinkedList_tag* tmp = p->next;
// １つ前の要素を p->next に設定
// "１つ前の要素" とは先頭から末尾へ向かう流れの中でのことを言っており、
// 逆順になった後のことを考えると、"次の要素" のことを言っている。
// 初回は何もないので NULL になっている
p->next = work;
// 現在の注目要素を保存
// これは、次のループにおいては "１つ前の要素" になる
work = p;
// 最初に退避させておいた p->next を次の注目要素として復帰させる
p = tmp;
}
// 最終的な work は、逆順になった後の先頭要素であるから、
// ダミーの先頭要素の nextポインタとして設定する
gHead.next = work;
}詳しくコメントを入れておいたので、紙にでも図を書きながら処理を追いかけてみると良いと思います。
イメージとして重要なのは、Ａ→Ｂ→Ｃ のような矢印の流れを、Ａ←Ｂ←Ｃ のように逆方向に向ければいいということを意識することです。下手に要素が移動するイメージを持つと混乱します。素直に、矢印の向きが変わることを考えましょう。
そう考えると、nextポインタを１つ手前の要素を指すように書き換えればいいということが分かります。しかし、一方向にしか進めない単方向線形リストでは、「１つ手前の要素」はどこかに覚えておくしかありません。それが、work という名前の変数です。
最終的に、変数work は元のリスト（逆順でないリスト）の末尾に来ているので、これをダミーの先頭要素の nextポインタとしてセットすれば、見事に逆順のリストに置き換わります。
問題③ 連結リストの要素を、配列のように添字でアクセスするようにできるでしょうか？実装してみてください。この機能は、実用上どのような問題があるでしょうか。
実装は簡単です。
/*
リストの要素を添字アクセスする。
引数：
index: インデックス。
戻り値：
リストの先頭要素を 0番目として、index番目の要素のポインタ。
*/
struct LinkedList_tag* at_list(size_t index)
{
struct LinkedList_tag* p = gHead.next;
for( size_t i = 0; i < index; ++i ){
p = p->next;
}
return p;
}範囲外アクセスが起こることは当然の問題としてありますが、先頭要素から順番に辿らなければならないので非効率だという点に注意が必要です。便利だと感じることもあるかもしれませんが、配列のように錯覚して、性能の違いを忘れてしまわないようにしないと、データ構造の選択ミスになってしまいます。
また、リストは要素を挿入したり削除したりすることが容易です。ということは、挿入や削除を頻繁に行う場面で使われている可能性が高く、添字はどんどんずれていきますから、結果的に、思うほど便利でないことも多いといえます。
新規作成。
Programming Place Plus のトップページへ
| はてなブックマーク に保存 | Pocket に保存 | Facebook でシェア |
| X で ポスト／フォロー | LINE で送る | noteで書く |
|
RSS
|
管理者情報 | プライバシーポリシー |