第5回 ポインタによるリスト、 循環・重連結リスト

Presentation on theme: "第5回 ポインタによるリスト、 循環・重連結リスト"— Presentation transcript:

1 第5回 ポインタによるリスト、 循環・重連結リスト
アルゴリズムと データ構造 第5回 ポインタによるリスト、 循環・重連結リスト 時間になりましたので、授業を始めたいと思います。

2 前回の復習 多次元配列 構造体 配列によるリスト 2次元配列 3次元配列 応用例：年内の経過日数 typedef宣言 構造体のメンバーの参照
構造体の配列 配列によるリスト スタックとキュー リストの実現に使用できるデータ構造 リストを操作する代表的な関数８つ 配列による線形リストの実現 それでは、先週の授業の復習です。 先週は、多次元配列と構造体と、配列によるリストについて勉強しました。 まず、多次元配列とは、配列を要素に持つ配列のことです。 2次元以上の配列をこう呼びます。 2次元配列は、要素が縦横に並んで、行と列で構成される表のイメージでとらえられます。 そのため、n行m列の2次元配列と呼ばれます。 二次元配列の要素には、添字を用いて直接アクセスすることができます。 3次元配列は先ほどのn行m列の2次元配列を集めて配列化したものです。 3次元配列のデータにアクセスする際も、添え字を用いることでアクセスできます。 この多次元配列を用いた応用例を、年内の経過日数の計算で行いました。 次に、構造体です。 構造体は、任意のデータ型を自由に組み合わせて作ることのできるデータ構造です。 バラバラのデータをグループ化でき、任意の型を組み合わせて作成することが可能です。 構造体は、struct＋タグ名の２つで宣言することができます。 タグ名だけでは、形名とはならず、必ずｓｔｒｕｃｔという前置きが必要です。 これは長いので、ｔｙｐｅｄｅｆ宣言によって、短い形名で表すのがほとんどです。 構造体のメンバーはアクセスすることで自由に値を変えたり、参照したりできます。 構造体オブジェクト内のメンバーは、ドット演算子を用いてアクセスします。 また、構造体をポインタで扱う場合は、アロー演算子を使ってアクセスします。 構造体は、配列で扱うことができました。 これは、配列の各要素に、構造体を入れることが可能ということです。 そして、構造体の配列も普通の配列と同じで、動的生成ができます。 最後に、配列によるリストです。 リストとは、要素の並び、または列のことを言います。 リストの特殊なケースとして、スタックとキューがあります。 スタックは後入れ先出し、キューは先入れ先出しの構造をしています。 リストの実現に使用できるデータ構造は2つあります。 配列と連結リストです。 リストを操作する代表的な関数はよく使うものには、関数ＩＮＳＥＲＴ、DELETE、LOCATE、RETRIEVE、FIND、TOP、LAST、NEXT、PREVIOUS、CREATEの８つがあります。 配列による線形リスト実現するには、2つのポイントがります。 １つ目は、用意した配列の先頭からデータを順次格納することです。 2つ目は、後続ノードへの着目は添え字をインクリメントすることです。 しかし、配列による線形リスト実現には、2つの問題点があります。 1つ目は、データを挿入・削除する際、配列内の要素ブロックを移動する必要あることです。 2つ目の問題点は、あらかじめ用意した配列の要素数以上のデータは格納できないということです。 そして、最後に、最も重要な2つの関数ｉｎｓｅｒｔとｄｅｌｅｔｅを例にして、配列によるリストの動きを説明しました。

3 演習問題の答え #include <stdio.h> #include <stdlib.h> #define NUM 5 typedef struct { // 構造体の定義 float shincho; // 身長 float taiju; // 体重 } shintai; void hyouji(shintai p[],int n) // n個分のデータを表示する { int i; for(i=0;i<n;i++) printf("No.%2d 身長: %4.1f 体重: %4.1f \n",i,p[i].shincho,p[i].taiju); } それでは、前回の演習問題の答えを一緒に見てみましょう。 まず、ここまでは同じです。 まず、関数の宣言とhyouji関数の中は変える必要はありません。 普通の配列と同じように使えます。

4 演習問題の答え // メイン処理 int main() { int i; int num; shintai *p; printf(“データ数：”); scanf(“%d”, &num); p=(shintai *)calloc(num, sizeof(shintai)); if (p==NULL) { printf(”メモリの確保はできなかった\n”); exit(1); } shintai p[NUM] この赤字のところが違います。 メイン関数の３行目、shintai *pを見てください。 ここはもともと配列の普通の宣言をしていました。（クリック）確認 そして次の行で、ユーザからデータ数を入力してもらいます。 データ数はnumに格納します。 その次の行で、callocを用いて動的メモリの確保を行います。 この時の引数は、numとsizeof(shintai)です。 これは、shintai型の大きさのメモリをnum個用意するという意味です。 自分で作った型（例えば　struct構造体）の大きさもsizeofで知ることができます。 そして、その下４行は、メモリの確保に失敗したらプログラムを終了するという条件文です。 これで確保に失敗しても、大丈夫です。

5 演習問題の答え for(i=0; i<num; i++){ printf("No.%d\n",i); printf("\t身長 : "); scanf("%f",&p[i].shincho); printf("\t体重 : "); scanf("%f",&p[i].taiju); } hyouji(p, num); free(p); return 0; } 次のfor文で名前と身長と体重をユーザに入力してもらうところと、hyouji関数に送るところは同じです。 これで、配列pに格納したデータは使わないので、最後に動的メモリを開放して終了します。 以上が先週の課題の答えです。 いかがでしたか？ 少し期限は短かったかもしれませんが、だいたいの人が解けたのではないかと思います。

6 補足: キャストとsizeof演算子 キャスト演算子 データ型を変換する操作 float x; int y; y=(int) x;
引数の型のサイズをbyte数で返す sizeof(int) = 4 sizeof(char) = 1 書式：　（型）式 「式」で示すデータが「型」に変換される 型が違うものを代入するときなどに使用 ここで少し、先ほど出てきたキャストとsizeof演算子について補足します。 キャスト演算子とは、データ型を変換する操作のことです。 下のプログラムを見てください。 このプログラムは、Float型の変数ｘを、ｉｎｔ型の変数ｙに代入しています。 たいてい、型が異なると代入はできません。 しかしこのように、代入する変数の前に型の指定を行って型を変換することで、異なる型の変数にも代入することができます。 キャスト演算子の書式は、（型）式です。 「式」のデータがカッコで指定した「型」に変換されます。 この例のように、型が違うものを代用するときなどに使われます。 次に、sizeof演算子についてです。 これは、引数の型のサイズをbyte数で返す演算子です。 たとえば下のプログラムを見てください。 Sizeof(int)とした場合は、この値は4になります。 これは、ｉｎｔ型の大きさが４だからです。 また、sizeof（ｃｈａｒ）とした場合は、この値は１になります。 これは、char型の大きさが１だからです。 ちなみに、コンピュータによってはｉｎｔ型が4ないものもあります。 したがって、sizeof（ｉｎｔ）で帰ってくる値が4ではない場合もあります。 これは、使用する言語や処理系などによって変わります。

7 ポインタによる線形リスト init a0 a1 a2 an-1
ポインタによってリストのデータ構造を表現したものを連結リスト（リンクトリスト，linked list）と呼ぶ 「要素」と「次のセルを指すポインタ」で構成される連結リストは，特に，単方向リスト，一方向リストなどと呼ばれる 実現方法 本来のデータと、次のノードを示すポインタを用意 自分自身と同じ構造体型を指すポインタを含む構造体：自己参照構造体 データが追加される時点で動的にデータ格納用構造体を確保 確保した構造体を、次のノードを示すポインタで指す init ここではポインタのみになっているが、実装を簡単にするため、ヘッダも完全なセルにすることもある． それでは第五回目の講義を始めます。 今回学習するのはポインタによる線形リストです。 リストの実現には配列と連結リストの２つのデータ構造があるということを前回の講義で説明したと思います。 リストとはデータが順序付けされて並んでいるデータ構造でしたね。 今回学習するのは、リストの中でもポインタによる線形リストについてです。 前回も説明しましたが、復習もかねてリストについて詳しく説明します。 連結リストや循環・重連結リストなどがあります。 非常に一般的な構造の一種です。 下の図は連結リストの一例です。 リスト上のデータはノード、あるいは要素と呼ばれます。 黄色い部分と緑色の部分を合わせて一つのノードになります。 しかし、各ノードはデータだけではなく、後ろに続くノードを指すためにポインタを持ちます。 緑色の部分がポインタになります。 このように連結リストとはリストに含まれる各要素をポインタによってつなぎ合わせたデータです。 また、連結リストの先頭と末尾に位置するノードはそれぞれ先頭ノードと末尾ノードと呼ばれます。 その他にも個々のノードにとってひとつ先頭側のノードを先行ノード、ひとつ末尾のノードを後続ノードと呼びます。 たとえばノードa1にとっての先頭ノードはノードa0、後続ノードはノードa2を指します。（クリック） 今回挙げたこの図ですが、あくまで連結ノードの一例です。 今回は先頭ノードがポインタのみになっていますが、先頭ノードも完全なセルにすることができます。 つまり、データとポインタで構成されることもあるということです。 a0 a1 a2 an-1

8 ポインタによる線形リスト init 自己参照構造体によるノード typedef struct _node {
Menber data; /* データを格納する構造体 */ struct _node *next; /* 後続ノードへのポインタ */ } Node; ・ 後続ノードがない場合、nextはNULL init 単純な配列による線形リストには、問題があります。 まず、一つ目として蓄えるデータ数の上限が既知でなければならないということ。 二つ目としてデータの挿入、削除に伴ってデータの移動が生じるため効率が良くないといった問題です。 しかし、線形リストにデータを挿入する際にノード用オブジェクトを生成し、削除する際にノード用オブジェクトを破棄すると、このような問題を解決できます。 それを実現するためのノードの構造を示したのが、構造体Nodeです。 この構造体は、二つのメンバdataとnextとから構成されます。 dataはデータを格納するメンバです。 nextは自分自身と同じ構造体型のstruct_node型オブジェクトを指すポインタです。 このように、自分自身と同じ型のオブジェクトを指すデータを持つデータ構造は、自己参照型と呼ばれます。 自己参照型といっても自分自身を指すポインタと勘違いする必要はなく、自分と同じオブジェクトを指すポインタをたまたまメンバとして持っているものと理解してください。 つまり、nextが自分自身を指してもいいのですが、自分自身と同じ型である別のオブジェクトを指してもいいわけです。 メンバnextに格納するのは、そのノードの後続ノードへのポインタです。 ただし、後続ノードを持たない末尾ノードのnextの値は、空ポインタNULLとします。 struct _node型 要素（data）と 次のセルを指すポインタからなる a0 a1 a2 an-1

9 ポインタによる線形リスト List型構造体 typedef struct { Node *head; /*先頭ノードへのポインタ */
Node *crnt; /* 現在着目中のノードへのポインタ */ } List; 線形リストを管理するための構造体として、プログラムのヘッダ部にはNodeとは別にListという構造体が宣言されています。 二つのメンバで構成されており、いずれもNodeへのポインタ型です。 メンバの一つ目はheadです。 headは線形リストの先頭ノードへのポインタです。 もうひとつはcrntです。 crntは現在着目しているノードへのポインタです。 探索したノードに着目した直後にそれを削除するといった用途で利用します。 Headは必須で、データがない場合はNULLとなります。 Crntは便宜上用意するものであり、なくても問題はないです。 ・ headは必須、データがない場合NULL ・ crntは便宜上用意、なくてもよい

10 ポインタによる線形リスト ノードの探索 線形探索でデータを探索 先頭ノードから目的値を持つノードを探索
探索すべき値と等しい要素を持つノードを見つけたら探索成功 探索すべき値が見つからず末尾までいったら探索失敗 C G を探索： 失敗 成功 H ・ ノードの探索について説明します。 探索アルゴリズムは線形探索であり、目的とするノードに出会うまで先頭ノードから順に走査します。 返却値は、見つけたノードへのポインタです。 探索失敗時は空ポインタNULLを返却します。 ノードの走査は探索条件を満たすノードを見つけた場合とノードが見つからず末尾ノードを通り越しそうになった場合の一方が成立したときに終了します。 例えばノードCを探す場合です。（クリック） headからノードＡへ移ります。（クリック） ノードＡは目的ノードではなく末尾ノードではないのでノードＢへ移ります。（クリック） ノードＢも目的ノードではなく末尾ノードではないのでノードＣへ移ります。（クリック） ここで探索条件を満たすノードが見つかったので終了です。（クリック） 他のノードも探索してみましょう。（クリック） 次は、ノードＧを探してみます。（クリック） 先ほどと同じようにheadからノードＡに移ります。（クリック） ノードＢは目的ノードではなく末尾ノードではないのでノードＣへ移ります。（クリック） ノードＣは目的ノードではなく末尾ノードではないのでノードＤへ移ります。（クリック） ノードＤは目的ノードではなく末尾ノードではないのでノードＥへ移ります。（クリック） ノードＥは目的ノードではなく末尾ノードであるためここで終了します。（クリック） 探索失敗となります。 以上がノード探索になります。 A B C D E N ・ N ・ N ・ N ・ N ・

11 ポインタによる線形リスト：ノードの探索 これがノード探索のプログラムになります。 Listが探索の対象となる線形リストです。
Xは探索するキーを格納したデータへのポインタです。 Compareは第2引数xが指すオブジェクトと、線形リスト上の個々のノード内データとを比較するための比較関数へのポインタです。 この比較関数が返却する値が0であれば、探索条件が成立しているとみなします。 まず①の部分は走査中のノードを指すための変数ptrをlist->headで初期化します。 Ptrのさす先はlist->headが指している先頭ノードとなります。 ②の部分では探索条件のノードが末尾ノードを通り越しそうになる場合の終了条件の判定を行います。 Ptrの値がnullでなければループ本体である③と④を実行します。 Ptrの値がnullであれば、走査すべきノードが存在しないということです。 While文の実行を終了して⑤に進みます。 ③では探索条件を満たすノードを見つけた場合の終了条件の判定を行います。 行うためには走査中のノードのデータと、xが指すデータとを比較関数compareによって比較します。 関数compareが返す値が0であれば探索成功であり、終了②が成立します。 List->crntにptrを代入するとともに、見つけたノードへのポインタであるptrを返却します。 ④ではptrにptr-.nextを代入することによって、走査を次のノードへと進みます。 プログラムの流れが⑤に到達するのは、探索に失敗したときです。探索失敗であることを示すnullを返します。

12 ポインタによる線形リスト 先頭へのノードの挿入 新規ノードを生成後、ポインタの付け替え 現先頭ノードのポインタを保存
新規ノードを先頭ノードへ 新規ノードの後続ノードを、保存してあったポインタで置き換え G H ・ N ・ P ・ 次に先頭へのノード挿入です。 図を用いて説明していこうと思います。 ここに連結リストの一例があります。 ここにノードＧという新規ノードを挿入したいと思います。（クリック） まずは、ひとまずノードＰというノードに先頭ノードのポインタを保存します。（クリック） その後、ノードＧを生成します。（クリック） その後、先頭ノードのポインタを今回挿入するノードＧへ参照するように変更します。（クリック） そして最後に、ノードＧの後続へのノードが指す場所をノードＰに保存してあったポインタで更新します。（クリック） このように、先頭へのノードの挿入は、現先頭ノードのポインタを保存する、先頭ノードが生成した新規ノード指すように更新する、新規ノードの後続ノードを保存してあったポインタに更新するといった手順になります。 A B C D E N ・ N ・ N ・ N ・ N ・

13 ポインタによる線形リスト 末尾へのノードの挿入 新規ノードを生成後、ポインタの付け替え headがNULL（データなし）なら先頭にノード挿入
headから、後続ノード（next）がない（NULL）ノードまで探索 新規ノードを生成し、探索したノードの後続ノードに接続 G H ・ P ・ N ・ 次に末尾へのノード挿入です。 リストが空であるかどうかで異なる処理をします。 リストが空のとき先頭ノード挿入と同じ処理を行います。 リストが空ではない時の場合を図を用いて説明します。 まず、ノードＰを生成します。（クリック） 末尾ノードを探すために、ノードＰを用いて先頭ノードから走査します。（クリック） ノードＡから探索します。（クリック） 今回ノードＡは後続ノードを持つのでスルーします。（クリック） 次にノードＢを探索しますが、ノードＢも後続ノードを持ちます。（クリック） ノードＢもスルーします。（クリック） 次にノードＣを探索しますが、ノードＣも後続ノードを持ちます。（クリック） ノードCもスルーします。（クリック） 次にノードＤを探索しますが、ノードＤも後続ノードを持ちます。（クリック） ノードDもスルーします。（クリック） 次にノードＥを探索します。 ノードＥは後続ノードを持たないので後続ポインタの指す先を今回挿入するノードＧに更新します。 そのためにノードＧを生成します。（クリック） ノードＥの後続ポインタをノードＧに更新します。（クリック） この際、生成したノードＧの後続ポインタの指す先をNULLとします。 このように末尾へのノードの挿入は、先頭ノードがNULLならば先頭にノードを挿入、NULLでなければ後続ノードがないノードを探索する、見つけたら新規ノードを生成し探索したノードの後続ノードに接続するといった手順になります。 A B C D E N ・ N ・ N ・ N ・ N ・

14 先頭へのノードの挿入 末尾へのノードの挿入
これは先頭へのノードの挿入と末尾へのノードの挿入のプログラムです。 まずは先頭へのノード挿入の部分についてです。 先頭へのノード挿入については①、②、③が該当します。 ①の部分では挿入前の先頭ノードＡを指すポインタをptrに保存しておきます。 ②の部分では挿入する新規ノードをallocNodeによって生成します。その際、list->headが生成したノードを指すように更新します。 さらに、list->crntも、新しく生成したノードを指すように更新します。 そして③の部分で関数SetNodeを呼び出して値を設定します。その際、挿入後の先頭ノードの後続ポインタの指す先を、ptrに更新します。 次に末尾へのノードの挿入の部分についてです。 末尾へのノード挿入は④、⑤が該当します。 ④の部分で行うのは、末尾ノードを見つける処理です。先頭ノードを指すように初期化されたptrの指す先を、その後続ポインタに更新するという処理を繰り返すことによって、ノードを先頭から順に走査します。 Ptr->nextの指す先がNullとなったらwhile文は終了です。 このとき、ptrの指す先は末尾ノードFとなっています。 ⑤の部分では挿入するノードＧを関数AllocNodeによって生成します。 そして、挿入前末尾ノードＧの後続ポインタの指す先をNULLとします。 後続ポインタをNULLにするのは、末尾ノードがいかなるノードも指さないようにするためです。

15 ポインタによる線形リスト 先頭ノードの削除 先頭ノードを、先頭の後続ノードへ 現先頭ノードの後続ノードへのポインタを保存 先頭ノードを削除
保存してあったポインタを先頭ノードとして置き換え H ・ P ・ 次に先頭ノードの削除について説明します。 削除処理を行うのは、リストが空でないときのみです。 これも図を用いて流れを説明します。（クリック） まず、ノードＰを生成します。（クリック） その後、先頭ノードの後続ノードへのポインタをノードＰに更新します。（クリック） その後、先頭ノードであるノードＡを削除します。（クリック） そして最後にheadの指す場所をノードＰに保存してあったノードＢに更新します。 つまり、流れは現先頭ノードの後続ノードへのポインタを保存、先頭ノードを削除、保存してあったポインタを先頭ノードとして置き換えとなります。 A B C D E N ・ N ・ N ・ N ・ N ・

16 ポインタによる線形リスト 末尾ノードの削除 末尾ノードの先行ノードに、後続ノードがない状態に ノードが1つだけなら先頭ノードの削除処理
末尾から2番目のノードを探索 末尾ノードを削除 末尾から2番目の後続ノード（next）をなし（NULL）に更新 H ・ Pre ・ Ptr ・ 末尾ノードを削除する場合はリストに存在するノードが１個だけであるかどうかで異なる処理をします。 リスト上にノードが１個だけ存在するときとは、つまりは先頭ノードのみ場合のことを表す。 よって先頭ノードを削除します。 リスト上にノードが２個以上存在するときは、こちらの図を用いて具体的に説明します。 ここで行うのは末尾ノードと末尾から２番目のノードを見つける処理です。（クリック） 現在走査中のノードを指すptrだけでなく、走査中の先行ノードを指す変数preが追加されます。（クリック） まずはpreもptrも先頭ノードであるノードＡを指します。（クリック） ノードＡは末尾ノードではないため次の処理に移ります。（クリック） その後、preは走査中のノードの先行ノード、ptrは走査中のノードを指すためそれぞれノードＡとノードＢを指します。（クリック） ノードＢは末尾ノードでないため探索を続けます。（クリック） 次にpreはノードB、ptrはノードＣを指します。（クリック） ノードＣも末尾ノードではないので探索を続けます。（クリック） 次にpreはノードＣ、ptrはノードＤを指します。（クリック） ノードＤも末尾ノードではないので探索を続けます。（クリック） 次にpreはノードＤ、ptrはノードＥを指します。（クリック） ノードＥは末尾ノードであるため探索は終了します。（クリック） 次に末尾ノードを削除する前に別の処理を行います。（クリック） その後、末尾ノードであるノードＥの先行ノード、つまりノードＤの後続ノードをNULLに更新します。（クリック） 同時に末尾ノードを削除して終了です。 A B C D E N ・ N ・ N ・ N ・ N ・

17 先頭ノードの削除 末尾ノードの削除 上三分の一が先頭ノードを削除するプログラムである。
流れはさきほど話した通り、先頭ノードの後続ノードへのポインタを保存してから、現先頭ノードを削除します。 その後、先頭ノードを更新するといった流れになります。 以上のことを上の部分で行っています。 残りの部分では、末尾ノードの削除を行っています。 リスト上にノードが１個だけ存在する場合は関数RemoveFrontに処理を委ねます。 先頭ノードの削除を行います。 Else以降はリスト上にノードが２個以上存在するときの処理になります。 ①の部分では末尾ノードと末尾ノードから２番目のノードを見つける処理です。 そのための走査は、末尾にノード挿入するときに用いた関数InsertRearとほぼ同じです。 しかし、さきほども言った通り現在走査しているノードの先行ノードを指す変数preが追加されている点が異なります。 さきほどのスライドの図でいうと、While文が終了したときには、preが指す先はノードＤ、ptrが指す先はノードＥとなります。 ②の部分では末尾から２番目のノードＤの後続ポインタにNULLを代入するとともに、末尾ノードＥの記憶域を解放します。 ここで着目ノードであるcrntの指す先は、削除後の末尾ノードpreになります。

18 ポインタによる線形リスト 着目ノードの削除 着目ノードの先行ノードの後続ノードを、着目ノードの後続ノードに付け替え
ノードが1つだけなら先頭ノードの削除処理 着目ノードの先行ノードを探索 探索したノードの後続ノードを着目ノードの後続ノードに更新 着目ノードを削除 次は着目ノードの削除についてです。 着目ノードの削除においても着目ノードが先頭ノードであるかどうかで異なる処理をします。 Crntが先頭ノードのとき、先頭ノードを削除する場合と同じ処理を行います。 Crntが先頭ノードでないときはこの図を用いて具体的に考えてみましょう。 まず、今回の着目ノードはノードＣとします。 着目ノードの先行ノードを探索するので今回探索するのはノードＢです。（クリック） Ptrを生成します。（クリック） Ptrは着目ノードの先行ノードの探索を行います。（クリック） まず先頭ノード、つまりノードＡは着目ノードではありません。（クリック） 後続ノードがあるため探索を続けます。（クリック） 次にノードＢは着目ノードではありませんが、探索の目的ノードです。（クリック） よって探索は終了です。（クリック） ここでノードＢの後続ノードを着目ノードであるノードＣの後続ノードに更新します。 今の場合だとノードＤに更新されます。（クリック） その後、着目ノードであるノードＣを削除して終了です。 H ・ Ptr ・ A B C D E N ・ N ・ N ・ N ・ N ・

19 ポインタによる線形リスト 全ノードの削除 全ノードの表示 線形リストが空になるまで先頭要素の削除の繰り返し 先頭ノードから順に内容表示
後続ノードがなくなったら終了 ポインタによる線形リストには他に全ノードの削除、全ノードの表示があります。 まず、全ノードの削除ですが、その名の通り全ノードを削除します。 関数Clearを用いります。 線形リストが空になる、すなわちheadがNULLになるまで先頭要素の削除を繰り返します。 全ノードを削除するとリストが空になるため、着目ノードcrntの値もNULLに更新します。 次は全ノードの表示です。 着目ノードのデータを表示する関数PrintCurrentと関数PrintLnCurrentを用いります。 List->crntが指しているノードのデータを、関数PrintMemberによって表示します。

20 着目ノードの削除 全ノードの削除・表示 こちらがプログラムになります。 まず着目ノードを削除する部分から説明していきます。
着目ノードの削除　　 全ノードの削除・表示 こちらがプログラムになります。 まず着目ノードを削除する部分から説明していきます。 最初にcrntが先頭ノードに着目しているかどうかを判別します。 もし、先頭ノードに着目しているならば先頭ノードを関数RemoveCurrentによって削除します。 Crntが先頭ノードではないときは①の部分と②の部分に移ります。 ①の部分では着目ノードの先行ノードを見つける処理を行っています。 While文は、走査を先頭ノードから開始して、着目ノードptrの後続ポインタptr->nextがlist->crntと等しくなるまで繰り返されます。 While文が終了した時点で、ptrの指す先はさきほどの図の場合ですと、削除する着目ノードＣの先行ノードであるノードＢになります。 ②の部分では、削除する着目ノードＣの後続ポインタlist->crnt->nextをノードＢの後続ポインタptr->nextに代入することで、ノードＢの後続ポインタの指す先をノードＤに更新します。 以上で着目ノードを削除するプログラムは終わりです。 次に全ノードを削除するプログラムですが、これはさきほど言ったように関数Clearを用いります。 空になるまで先頭要素を繰り返し削除を行います。 着目ノードのデータ表示についても先ほど言った通り、関数PrintCurrent、PrintLnCurrentを用いります。 Crntが指しているノードのデータを関数PrintMemberによって表示します。 ただし、着目ノードが存在しない場合は、「着目ノードはありません。」というメッセージを表示します。 なお、関数PrintLnCurrentは、データあるいはメッセージの表示の後に改行文字の出力を行います。

21 計算量の比較 p [0] last [1] init p 2 [2] [3] [4] [5] [6] データ構造
INSERT, DELETE FIND, LAST, PREVIOUS 配列 要素数に比例O (n) 一定時間O (1) 単方向リスト 2 last T E I [0] [1] [2] [3] [4] [5] [6] p E I p T init ここでデータ構造が配列によるものと単方向リストによるものでどう変化するのか見ていこうと思います。 関数が変わると配列と単方向リストで時間の変化としてどう変わるのでしょうか。 まず、関数INSERT,DELETE,FIND,LAST,PREVIOUSの場合を見てみましょう。 関数INSERT,DELETEでは配列のときは要素数に比例します。 単方向リストは一定時間なので要素数が多いときを考えると配列より時間は短縮できます。 関数FIND,LAST,PREVIOUSの場合では、配列の時は一定時間に比例します。 単方向リストのときは要素数に比例するのでさきほどとは逆に時間がかかってしまうことがあります。

22 メモリの使用効率に関する比較 init p p [0] last [1] 2 [2] [3] [4] [5] [6] データ構造
リストの最大長 余分に必要になるメモリ 配列 固定 MAXLENGTH - 実際の長さ 単方向リスト 可変 ポインタ用の空間 E I p T init 2 last T E I [0] [1] [2] [3] [4] [5] [6] p 配列のリストの最大長は配列を宣言するため、固定となります。 メモリが余分に必要になる文は左の図の通り、宣言した長さから実際に使っている長さを引いた部分になります。 しかし、単方向リストについてはポインタ用の空間を宣言せずとも使えるので可変となります。 余分に必要になるメモリはポインタ用の空間そのものになります。 データが 入っていない ポインタ用の空間

23 循環・重連結リスト 循環リスト 重連結（双方向）リスト 循環・重連結リスト ap-1 ap ap+1
線形リストの末尾ノードが先頭ノードを指すリスト 重連結（双方向）リスト 後続ノードへのポインタだけでなく、先行ノードへのポインタも備えたリスト 長所：リストを前方にも後方にもたどれる 短所：前のセルを指すポインタが必要になる 　　　　　単方向リストと比べ，操作が複雑になる 循環・重連結リスト 循環リストと重連結リストの両方を併せ持つリスト ap-1 ap ap+1 そして次に循環・重連結リストについて学んでいこうと思います。 まず、循環・重連結リストを循環リストと重連結リストに分けて考えていこうと思います。 最初に、循環リストとは線形リストの末尾ノードに、先頭ノードを指すポインタを与えたものです。 循環に並んだデータの表現に適した構造です。 線形リストとの大きな違いは、末尾ノードの後続ポインタが、NULLではなく先頭ノードへのポインタになっている点です。 次に、重連結リストとは各ノードに後続ノードへのポインタだけでなく、先行ノードへのポインタが与えられたものです。 線形リストの最大の欠点は、後続ノードを見つけるのが容易である一方で、先行ノードを見つけるのが困難であることです。 この欠点を解消するリスト構造が重連結リストです。 重連結リストは、双方向リストとも呼ばれます。 重連結リストのノードは、本来のデータ、先行ノードへのポインタ、後続ノードへのポインタの３つのデータから構成される構造体として実現できます。 リストを前後にたどれることが長所として挙げられますが、前のセルを指すポインタが必要になることと、単方向リストと比べ、操作が複雑になることが短所として挙げられます。 この循環リストと重連結リストの両方を併せ持つリストが循環・重連結リストです。

24 循環・重連結リスト 循環・重連結リストの実現 実現方法 リストの初期化
本来のデータと、先行ノード、後続ノードを示す2つのポインタを備えたノードを用意 リストの初期化 データがなくてもダミーとして1つノードを作成 ノードの追加や削除を円滑に行うため 循環・重連結リストの実現にあたって、ノードは重連結リストと同じで本来のデータと、先行ノード、後続ノードを示す２つのポインタの３つのデータが与えられます。 循環・重連結リストを管理するための構造体は、線形リストと同様に先頭ノードへのポインタと、着目ノードへのポインタから構成されます。 リストの初期化についてはダミーノードをひとつだけ作成します。 ダミーノードとはデータを持たないノードです。 ノードの挿入や削除の処理を円滑に行うために、リストの先頭位置に存在し続けます。 ダミーノードを生成した後は、そのノードの先行ポインタと後続ポインタの両方が自分自身のダミーノードを指すように設定します。

25 循環・重連結リスト 循環・重連結リストの実現 ノードの探索 線形探索でデータを探索 ダミーノードの次のノードから目的値を持つノードを探索
探索すべき値と等しい要素を持つノードを見つけたら探索成功 探索すべき値が見つからずダミーノードまで戻ったら探索失敗 関数Searchを用いて、リストからノードを探索できます。 先頭ノードから始めて、後続ポインタを順次たぐって操作する手順は、線形リストのプログラムの関数Searchとほぼ同じです。 ただし、実質的な先頭ノードが、ダミーノードの後続ノードであるため、探索の開始点が異なります。 よってダミーノードの次のノードから目的地を持つノードの探索を開始します。 While文による走査の過程で、比較関数compareによって比較した結果が０であれば探索成功です。 目的とするノードが見つからず操作が一巡してダミーノードに戻ってきたときにwhile文は終了です。 つまり探索失敗であるためNULLを返します。

26 循環・重連結リスト 循環・重連結リストの実現 ノードの探索 B G を探索： 成功 失敗 H ・ ・ P ・ P ・ P ・ P ・ P
図を用いてノード探索を詳しく説明します。（クリック） まず、ノードＢを探索したいと思います。（クリック） 探索の開始点はダミーノードの後続ポインタが指すノードからであるため今回はノードＡが開始点になります。（クリック） ノードＡの後続ノードはノードＢであるのでノードＢに移ります。 ここでノードＢが見つかったので探索成功です。（クリック） しかし、ノードＧを探索する場合はどうなるのでしょうか。（クリック） 実際に行ってみましょう。（クリック） 先ほどと同じように探索の開始点はノードＡからです。 ノードＡの後続ノードはノードＢです。 ノードＢは目的ノードではないので次に移ります。（クリック） ノードＢの後続ノードはノードＣです。 ノードＣも目的ノードではないので次に移ります。（クリック） ノードＣの後続ノードはノードＤです。 ノードＤも目的ノードではないので次に移ります。（クリック） ノードＤの後続ノードはダミーノードです。 ダミーノードに戻ってきたということは一巡したことになります。（クリック） つまり探索は失敗です。 ・ P ・ P ・ P ・ P ・ P （ダミー） A B C D N ・ N ・ N ・ N ・ N ・

27 循環・重連結リスト 循環・重連結リストの実現 ノードの挿入 先頭へのノードの挿入 末尾へのノードの挿入
新規ノードと、挿入すべき前後のノードでポインタの付け替え（4つ） 先頭へのノードの挿入 ダミーノードの直後へノードを挿入 末尾へのノードの挿入 ダミーノードの直前へノードを挿入 ノードの挿入、先頭へのノードの挿入、末尾へのノード挿入も行うことができます。 ノードの挿入は関数InsertAfterを用いります。 あるポインタが指すノードの直後にノードを挿入する関数です。 挿入の手順を簡単に説明したいと思います。 まずは新しく挿入するノードを生成します。 生成されたノードの先行ポインタの指す先と後続ポインタの指す先を設定します。 そして、生成されたノードの先行ノードにあたるノードの後続ポインタと後続ノードにあたるノードの先行ポインタの両方が新たに挿入したノードを指すように更新します。 その後、着目ノードが挿入したノードを指すように更新します。 以上が流れになります。 先頭へのノード挿入についてはダミーノードの直後にノードを挿入します。 ダミーノードの後ろへの挿入を、関数InsertAfterに依頼します。 末尾へのノード挿入についてはダミーノードの直前にノードを挿入します。 こちらも関数InsertAfterに末尾ノードの後ろへ挿入を依頼します。

28 循環・重連結リスト 循環・重連結リストの実現 ノードの挿入 ・ P G N ・ ・ P ・ P ・ P A B C N ・ N ・ N ・
こちらも図を追って説明していきます。 まず、こちらに循環・重連結リストの一部分があります。 ここにとあるノードＧを挿入したいと思います。 挿入したい場所はノードＢとノードＣの間とします。（クリック） さきほども言ったようにまずはノードＧを作成します。 そして生成したノードの先行ポインタの指す先と後続ポインタの指す先を設定します。（クリック） 今回だと先行ポインタをノードＢに、後続ポインタをノードＣに設定します。（クリック） 次に、ノードＢの後続ポインタと、ノードＣの先行ポインタをノードＧに更新します。 これでノードＧがノードＢとノードＣの間に挿入できたことになります。 ・ P ・ P ・ P A B C N ・ N ・ N ・

29 循環・重連結リスト 循環・重連結リストの実現 ノードの削除 先頭ノードの削除 末尾ノードの削除
削除するノードの記憶域を開放し、前後のポインタを適宜付け替え 先頭ノードの削除 ダミーノードの直後のノードを削除 末尾ノードの削除 ダミーノードの直前のノードを削除 ノードの挿入ができればもちろん削除も行えます。 関数Removeを用いて処理を行うことができます。 手順を簡単に説明します。 まず、削除したいノードの先行ノードの後続ポインタと後続ノードの先行ポインタの指す先を更新します。 削除したいノードの記憶域を解放すると、削除処理は終了です。 最後に着目ノードが、削除したノードの先行ノードとなるようにcrntを更新します。 以上がおおまかな流れになります。 先頭ノードの削除は関数RemoveFrontを用いります。 ポインタlist->head->nextが指す先頭ノードの削除を関数Removeに依頼します。 ちなみにlist->headではありません。 これはダミーノードを指しており、実質的な先頭ノードはその後続ノードであるためです。 末尾ノードの削除は関数RemoveRearを用いります。 ポインタlist->head->prevが指す末尾コードの削除を、関数Removeに依頼します。

30 循環・重連結リスト 循環・重連結リストの実現 ノードの削除 ・ P ・ P ・ P A B C N ・ N ・ N ・
こちらも図を使って説明していきます。 こちらも先ほどの図と同じようにある循環・重連結リストの一部です。 今回削除したいノードはノードＢであるとします。（クリック） 削除の処理として、まずノードＢの記憶域を解放します。（クリック） そして、ノードＢの先行ノードであるノードＡの後続ポインタの指す先が、ノードＣとなるように更新します。 次にノードＢの後続ノードであるノードＣの先行ポインタの指す先がノードＡとなるように更新します。 ・ P ・ P ・ P A B C N ・ N ・ N ・

31 まとめ 抽象データ型としての「リスト」 リストの実現方法 一定の型の要素を０個以上一列に並べたもの
リスト中のどの位置でも自由に参照，挿入(Insert)，削除(Delete)の操作を行える リストの実現方法 配列を用いる方法 ： 「要素の配列」と「最後の要素の位置を示す変数」で実現 ポインタを用いる方法 ： 「要素」と「次のセルを指すポインタ」でセルを構成し，セルを順次つなぐことで，連結リストを作成し，実現 本日の講義のまとめになります。 本日はポインタによる線形リストについて学習しました。 リストとは０個以上のデータが順序付けされて並んでいるデータ構造の一種です。 リスト中のどの位置でも自由に参照、挿入、削除の操作を行えることが特徴です。 リストを実現するにあたって方法は２つあります。 ひとつは配列を用いる方法です。 これは前回説明しました。 配列による線形リストの実現するには、２つの点を考える必要があります。 一つ目は用意した配列の先頭からデータを順次格納することです。 二つ目は後続ノードへの着目は添え字をインクリメントすることです。 しかし、この方法には２つの問題点があります。 一つ目はデータを挿入・削除する際、配列内の要素ブロックを移動する必要があることです。 二つ目はあらかじめ用意した要素数以上のデータは格納できないということです。 配列によるリストの実現方法において「配列の大きさ」と最後の要素の位置を記録することで実現できます。 次にポインタによる線形リストについてのまとめです。 この場合の線形リストの要素としまして、本来のデータに加えてポインタが含まれます。 連結リストのような方向が後ろのみにリストが持つポインタは後続ポインタのみとなります。 しかし、循環リスト、重連結リスト、その両方を併せ持つ循環・重連結リストのような方向が前と後ろを持つリストは先行ポインタと後続ポインタの２つのポインタを持ちます。 ポインタでセルを順次つなぐことでリストの実現が可能です。

32 演習問題