第12回：木構造

Transcription

1 アルゴリズムとデータ構造 講義スライド 4 スタック キュー リスト 茨城大学工学部知能システム工学科井上康介 E2 棟 801 号室

2 第5章 データ構造 授業の最初で述べたとおり 大量 複雑なデータを扱う上 では データを構造化 組織化する必要がある どのようなデータ構造 (data structure) を採用するかに よって 問題解決のアルゴリズムも異なってくる つまり アルゴリズムとデータ構造とは密接な関係にあり よいデータ構造を選ぶことがよいプログラムを作ることに つながる 特に重要なデータ構造として リスト ツリー グラフが 上げられる ツリー (木) は第6章 グラフは第7章で扱う この章では スタック (stack: 棚) キュー (queue: 待ち 行列) リスト (list) を説明する.213 2

3 データ構造とは 代表的なデータ構造として 以下のものが挙げられる 1. 表 (table: テーブル) 2. 棚 (stack: スタック) 3. 待ち行列 (queue: キュー) 4. リスト (list) 5. 木 (tree: ツリー) 6. グラフ (grah) 表については ふつうの配列で扱うことができるので ここでは扱わない 良いデータ構造とは何かの基準は一概には言えないが データの追加 削除 検索が効率よく行えること およ び 複雑な構造が簡潔に表現できることなどがある

4 これから学ぶデータ構造 テーブル ( ただの配列 ) スタック ( 後入れ先だし ) a[0] a[0][0] a[0][1] a[1] a[1][0] a[1][1] a[2] a[2][0] a[2][1] a[3] a[3][0] a[3][1] a[4] a[5] a[4][0] a[5][0] a[4][1] a[5][1] キュー ( 先入れ先出し ) 4

5 これから学ぶデータ構造 リスト ( 一本鎖 ) データデータデータ 次のデータへのポインタ 終端は NULL ツリー ( 分岐を含む ) データ データ データ データ データ データ 5

6 これから学ぶデータ構造 グラフ ネットワーク (ループも含む) 3分 秦病院 油縄子 Bulldog 秦病院 6分 油縄子 Bulldog 4分 7分 5分 カワチ 茨大 カスミ グラフ (接続関係だけ) カワチ 10分 茨大 カスミ ネットワーク (区間に属性) 6

7 スタック スタック (stack) は 一時的データ置き場 (buffer) と して利用される代表的なデータ構造の一つである データを棚に上から順に積んでいき 取り出すときも上 から取り出す データを放り込む操作を プッシュ (ush) 取り出す操作を ポップ (o) という o ush このように 取り出せるのは最後に Data-1 Data-0 入れたデータからである Data-2 このような方式を LIFO (Last In First Out: 後入れ先出し) と呼ぶ スタックの実装は 1次元配列を 用いて行われる スタック (棚) (前半) 7

8 スタック スタックは データを格納する配列 と 現在いくつのデー タが入っているか を示す スタックポインタ から実現さ れる 配列を stack[] スタックポインタを s とするとき 次のようになる s==4 での ush は あふれ プッシュ Data-A Data-B Data-D Data-C s==0 での o は 空っぽ ポップ これらは エラー処理 stack[3] stack[2] stack[1] stack[0] s=

9 スタック (ソースコード).217 プリプロセッサでスタックのサイズ MaxSize を定義 スタックの実体である配列 stack[] はグローバル変数 として定義 スタックポインタ s もグローバル変数と して定義し 0 に初期化している (ほんとうは グロー バル変数は極力使わないことが望ましい) プッシュ関数 int ush(int n); とポップ関数 int o(int *n); では int型の返値を返す メイン関数では while文でループさせてユーザからの 文字入力を繰り返し受けている int getchar(void) は キーボードから文字を読み 込み int型に変換して返す関数 9

10 スタック (ソースコード) while文のかっこ内でキーボードから1文字を読み込む 読み込んだ文字が 'i' あるいは 'I' であるときは ユーザからデータを入力して それをスタックにプッ シュする スタックが既にいっぱいの場合, それ以上プッシュでき ない このとき 関数 ush() は -1 を返す 読み込んだ文字が 'o' あるいは 'O' であるときは ス タックからデータを1つポップする スタックが空の場合は取り出せないので関数 o() は -1 を返す プッシュもポップも 正常に実行した場合は返値は 0 となる 10

11 スタック (ソースコード) さて, ポップを行ったとき データが正しく取り出せれば 0 を スタックが空のときは -1 を返す このために 返 値 という情報チャンネルは使われてしまう では, 2つめの情報 ポップにより取り出したデータ を どうやって呼出側に返せばよいだろうか データを返すために ここでは ポインタ渡し (参照渡し) という方法が使われている (通常は 値渡し) ポップしたデータを入れる変数は main関数のローカル 変数 n であり main関数で o() を呼び出すとき 引 数としてその n へのポインタ (n のアドレス) を o() に渡す o() 内では もらったアドレスにデータを書き込む 11

12 スタック (ソースコード) それぞれの関数を見ていこう ush() では 最初にサイズあふれ (s >= MaxSize) が起きていないかチェックしている 起きていない場合は 配列の s の位置に 値渡しで受け 取ったデータ n を書き込み s を1つ増やす 正常終了 なので この場合は返値として 0 を返す サイズあふれが起きていた場合 何もせずに -1 を返す 値渡しでデータを受け取る際 main関数のローカル変数 n がコピーされ これが関数に渡されている 従って 関 数 ush() の中で n に変更を加えたとしても main関数 内の n の値には影響しない 12

13 スタック (ソースコード) 一方 o() では main関数内のローカル変数 n のポイ ンタを受け取る 関数 o() 内においては n はそのポインタ (アドレス) を示す変数であり, そのアドレスに書かれた情報を読み書 きするときは *n としてアクセスする 関数では まずスタックが空 (s==0) でないかチェック し 空でないときは s を1だけ減らしてから 配列の s 番要素を *n に書き込み 正常終了を示す返値 0 を返す 空の場合は何もせずに異常終了の返値 -1 を返す 13

14 スタックからのポップ 関数 o()の引数はポインタ渡しによる n これは main()関数内のローカル変数 n への参照 である グローバル変数 s 0 関数 main() 3 2 o(&n) stack c n o -51 int o(int int *n) *n n

15 キュー スタックでは データを入れたのとは逆の順番でデータ を取り出していた (LIFO方式) このやり方は まさに再 帰呼出で紹介したような用途に向く 一方 例えば役所 の窓口に人がどんどん来る場合を考えよう LIFO方式では 最後に列に加わった人から処理を行うが これは言うまでもなく不公平である 列に並んだ人々を 最初に並んだ人から順番に捌いていく必要がある これ を FIFO (First In First Out: 先入れ先出し) という このモデルを キュー (queue: 待ち行列) という 例 PCがインターネットで通信するとき ネットからは 続々とデータが流入するが 処理が追いつかない場合が ある このとき データを一時的にキューに置いておき 手が空き次第 先に来たデータから順に処理する

16 キュー 実装は スタックと同様 1次元配列 待ち行列の先頭位置を head 終端を tail とする tail の位置にデータを入れ head から出す キューのサイズは, (配列サイズ)ー1 になる queue[5] Data-F head tail queue[4] Data-E head tail queue[3] Data-D head tail queue[2] Data-C これが限界 head tail queue[1] Data-B Data-H head tail queue[0] Data-A Data-G head tail 16

17 キュー (ソースコード).223. プリプロセッサで配列サイズ MaxSize を100としている よって 容量は99となる キューの実体である配列 queue[] および先頭 末端位 置 head tail はグローバル変数として定義 キューにデータを入れる関数は int queuein(int n) データを取り出す関数は int queueout(int *n) main関数では スタックの場合と同様 キーボードから1 文字ずつの入力を繰り返し受け付け それが 'i' または 'I' のときはデータを入れ 'o' または 'O' の時はデー タを出している 17

18 キュー (ソースコード) キューがいっぱいの時に更にデータを入れようとすると queuein() が -1 を返す キューが空の時に取り出し をしようとすると queueout() が -1 を返す点はスタッ クと同じ また queueout() において 取り出した データを返すために参照渡しを使っている点も同じ キューにデータを入れる関数 queuein() においては キューがいっぱいであるかどうかを tail の次の位置が head と同じかどうかによって調べている 次の位置 を求めるために (tail+1)%maxsize とい う計算をしている MaxSize が 100 とするとき もしも tail が配列最後の位置 99 にあったとすれば 次の位置 は先頭 0 であり それはこの計算で求まる 18

19 キュー (ソースコード) tail の次の位置が head と重ならなければ キューには まだ余裕がある このとき tail の位置にデータ n を書 き込み tail を1つ進める queueout() では 最も古いデータを取り出す その位 置は head である 最初にキューが空かどうかを調べる head == tail な らキューは空っぽなので取り出せない head 位置のデータ queue[head] を ポインタ変数 *n に代入することで main関数に返した後 head を一つ進 める head の 次の位置 は (head+1)%maxsize である 例 配列サイズが100のとき 99の次は(99+1)%100=0 19

20 リストとは リスト (list) とは, データを鎖のようにつなぎ合わせて管理するデータ構造である. 各データは次のデータを指すポインタを持っている. このポインタで次々とデータをつないでいく ( リンクする ) ことによって, 任意の数のデータを扱える. 一方, データを配列で扱う場合は, あらかじめ決められた配列サイズを超えるデータは格納できない. リストでは, データを新たに格納するたびに, そのデータのための記憶領域を新規に確保していくので, サイズの制限がない ( もちろんコンピュータ上のメモリサイズ以上は格納できないが ). といっても理解しづらいので, 絵的に理解しよう..228~229 20

21 リストとは リスト構造においてつながれる各データ要素 (ノード node) は レコード によって構成される ノードはデータを入れる データ部 の他に 次のノードの アドレスを指し示す ポインタ部 を含む 最後尾のポインタ部は NULL としておく プログラムからリスト構造にアクセスするため リストの 先頭へのポインタ head を変数として記録しておく head ノード A データ部 B C ポインタ部 21

22 リストとは リストのノードはレコードであるから C言語において は構造体を用いて実装することができる struct tfield { char name[20]; データ部 char tel[20]; struct tfield *ointer; ポインタ部 }; このように 自分自身と同じ構造体へのポインタを持つ 構造体を 自己参照構造体 (self-referential structure) という 教科書.228 のコードに 誤植 tfieled ではなく tfield 型です 22

23 リストとは 前述の通り リスト構造では 必要に応じてノードを追 加 削除することができる このためにはノードのためのメモリ領域を 動的に確保 解放 しなくてはならない この目的で使われるのが メモリの動的確保 という方法で ある C言語ではメモリの動的確保のための関数が2つ用意され ている これらの間には微妙な違いがあるがほとんど同 じ ここでは malloc() を使う void *malloc(size_t size); void *calloc(size_t nmemb, size_t size); 23

24 リストとは 関数 malloc() は 引数 size で与えられたバイト数 のメモリ領域をそのプログラムのために確保し, 確保さ れた領域の先頭アドレスを返値として返す void *malloc(size_t size); 例えば int型の配列 (要素数10) の領域を確保して配 列 a[] を作るには 以下のようにする int *a; a = (int *)malloc(sizeof(int)*10); ただし sizeof(型名) は その型のサイズ (バイト 数) を表す 24

25 リストとは メモリ動的確保関数 malloc() を使って ノードの動的 確保を以下の関数で記述できる struct tfield *talloc(void) { return (struct tfield *)malloc(sizeof(struct tfield)); } tfield型ポインタへの型キャスト tfield型のサイズ この関数を用いて struct tfield *; = talloc(); 初期化前では 何が入って いるかは分からない とすると tfield 型のデータ領域を新たに確保し それへのポインタが に代入される 25

26 リストとは ノード内部のデータの参照方法は以下の通り 下記のように ノードへのポインタ によってノードが 指定されている場合 名前欄は ->name 電話番号欄は ->tel ポインタ欄は ->ointer により参照され る (*).name とかと同じ意味 ->ointer ->name ->tel inoue 一方, ノードがポインタでなく実体で記述されている 場合 つまり struct tfield node; として指定されて いる場合は それぞれの欄は node.name node.tel node.ointer として参照される 何を言っているか分からない人は十分復習すること 26

27 入力とは逆順なリストの作成 教科書.230 の例題 34 は ユーザが名前と電話番号を 次々に入力したとき そのデータが 入力されたのと逆順 で並ぶような リストを作成する手順である リストの先頭ノードを示すポインタを head とする 初期状態は空のリストであり このとき head は NULL データ追加手順は以下の通り (1) ノード 1つを新規生成し で指し示す = talloc(); (2) が指すノードにデータを書き込む (3) が指すノードのポインタ部に head をコピー ->ointer = head; (4) head から が指すノードを指す head = ; coy head Sato coy 27

28 入力とは逆順なリストの作成 次以降も同じ手順を繰り返すことで 入力とは逆順のリス トを生成できる (1) ノード 1つを新規生成し で指し示す = talloc(); (2) が指すノードにデータを書き込む (3) が指すノードのポインタ部に head をコピー ->ointer = head; (4) head から が指すノードを指し示す head = ; 手順 (3) と (4) の順序を取り違えるとまずいことになる head head Ota Sato Ota Sato 28

29 入力とは逆順なリストの作成 これを繰り返すと 入力されたのとは逆の順番のリスト構 造ができあがる head A B head C B A D C B head A 29

30 入力とは逆順なリストの作成 (ソース).231 動的メモリ確保関数 malloc() を使うため stdlib.h をインクルードする main関数では ローカル変数として リストの先頭を 示すポインタ head 新規ノードのポインタ を宣言 head を NULL で初期化している 次の while文では まず talloc() により新規ノード を作成してそのアドレスを に代入し ユーザから入 力された2つの文字列を ->name ->tel に代入 もしユーザから入力終了信号を受けた場合は, ループを 抜ける そうでないときは, (1) 新ノードのポインタ部 に旧リストの先頭アドレス (head) を代入 (2) head の指し示す先を新ノードに変更. 30

31 入力とは逆順なリストの作成 ( ソース ) while 文を抜けた時点で, ユーザから入力されたデータ群を逆順に保存したリスト構造ができている. その次の処理は, リスト構造の内容を表示する. 最初にポインタ変数 に head をコピー. これにより, は先頭ノードのアドレスを示す. 次の while 文は が NULL でない限り繰り返す. まず, が指し示すノードの内容を表示. 次に, = ->ointer とすることで, ポインタ変数 が, 今表示したノードの次のノードのアドレスを指し示すようにする. つまり, ここで は 視点 の役割. 末尾のノードのポインタ部は NULL なので, これにより に NULL が入って while 文を抜けることになる. 次ページで説明 31

32 リストの内容表示について 前のページの リストの内容表示の部分を説明する 今回は 変数 は 視点 として使う =head; while(!=null){ ループを抜けて終了 rintf("%15s%15s n",->name,->tel); =->ointer; がもともと指し示していたノードのポイン } タ部の情報を にコピーすると言うことは 視点 はもう一つ次のノードを指し示す head 作ったリスト構造 表示 表示 名3 電3 名2 電2 表示 名1 電1 講義スライドでは いちいち変数 から矢印を描くのは煩雑なので が示しているノードの上に単に と表記することが多いです 32

33 ノードへのポインタの表示方法 今後, 先ほどのポインタ変数 のように, 様々なノードを指し示すポインタについては, 上の図のようにいちいち矢印で指し示さず, 下の図のようにノードに と示すだけにする. が指し示すノードを ノード などと書く. =->ointer; head Iida Ota Sato head Iida Ota Sato 33

34 入力順のリストの作成 ここまでの話は, 入力順と逆順のリストの作成. では, 入力順のリストはどうすれば作れるか 途中まで作ったリストの最後尾のさらにあとに新規ノードを追加していけばよい. 仕上げとして, 最後に作ったノードのポインタ部を NULL にする. head A B head A B C D 34

35 入力順のリストの作成 面倒な問題 : ノード作成手順が 最初のノード と 次以降のノード で異なる. 最初のノードへのポインタ :head から 次以降のノードへのポインタ : 既存リスト最後尾から 最後尾ノードへのポインタを old とすると head A ノード作成 : head=talloc(); データ記入 : head->name, head->tel へ head A old B C コードが異なる ノード作成 : =talloc(); old->ointer=; データ記入 : ->name, ->tel へ 35

36 入力順のリストの作成 ( ソースコード ) 教科書.232~233 のソースコード (Dr34_1) 前半部 head=talloc(); 前処理 scanf("%s %s",head->name,head->tel); old=head; ( 最後尾ノードをポインタ old でポイントしておく ) while (=talloc(),scanf("%s %s",->name,->tel)!=eof){ old->ointer=; old=; } old->ointer=null; 後処理 head old old old ムダ A B C 36

37 ダミー ノード 先ほどのソース コードのデータ入力部は head=talloc(); scanf("%s %s",head->name,head->tel); 前処理での入力処理 old=head; while (=talloc(),scanf("%s %s",->name,->tel)!=eof){ old->ointer=; old=; } old->ointer=null; ループ内での入力処理 データ入力処理が scanf() 一つだけならいいが, より複雑な処理の場合, これは避けたい. これを避けるための一つの方法がダミー ノードである. 先頭ノードはデータを格納せず, ダミーとする. 37

38 ダミー ノード ( ソースコード ) 教科書.234~235 のソースコード (Dr34_2) 前半部 head=talloc(); scanf("%s %s",head->name,head->tel); old=head; while (=talloc(),scanf("%s %s",->name,->tel)!=eof){ old->ointer=; old=; } old->ointer=null; 入力処理はこれに統一 head old old old old A B C ダミー ノード 実際のデータ 38

39 ダミー ノード ( ソースコード ) 教科書.234~235 のソースコード (Dr34_2) 後半部 ( リスト内容の表示 ) =head->ointer; ( 視点は第 2ノードからスタートする ) while (!=NULL){ rintf("%15s%15s n",->name,->tel); =->ointer; } head A B C : NULL ダミー ノード 実際のデータ 39

40 リストへの挿入 リスト構造は データ列の途中の任意の位置においてデー タを挿入 削除するのに適している 配列の場合 挿入 削除に伴って他のデータの移動が必要 となるが リストではつなぎ換えだけでよい リストの場合 A C B D a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] 配列の場合 A C D B

41 リストへの挿入 教科書の例では 既存のリストの中から 特定のデータ (キーデータ) を逐次探索で探し出し そのノードの次の位置にデータを挿入する 例えば B のデータの次に C を挿入する場合 視点 を head で初期化 の位置のデータが B なら発見 そうで ないなら視点を右へずらす (=->ointer;) 発見したら ->ointer のところにノードを挿入 head ノード挿入手順 A B n=talloc(); scanf("%s",n->name); n n->ointer=->ointer; ->ointer=n; C D - 新規ノード n を作成 - そのポインタ部を次の ノードへ - のポインタ部を新しい ノードへ 41

42 リストへの挿入 (ソース) リストの先頭位置を示すポインタ head はグローバル変数として宣言 (struct tfield の型定義の部分) リストの生成は関数 genlist()にまとめられている ここでは逆順 リストの生成を行っている リスト内容表示は関数 dislist()にまとめられている ノードの挿入を行っているのは関数 link()である 引数は char 型 へのポインタ key であり キーデータの文字列に対応している (key というポインタ (アドレス) は char 型の配列の位置を表して おり, その配列に文字コード列が入っている. ) key の実体 (配列) は main関 数のローカル変数である key 'I' 'n' 'o' 'u' key[0] key[1] key[2] key[3] 42

43 リストへの挿入 (ソース) 関数 link() の中で行っている処理を見てみよう ローカル変数としてノードへのポインタ と n がある 最初にノードを一つ作成し それへのポインタを n に代 入 その中に入れるデータをキーボードから入力してい る 次に を視点として head で初期化 while (!=NULL) のループを回し いま視点を置いてい るノードの name欄が key と一致するかどうかを strcm() によって調べる 合致した場合は 視点位置 の次にノード n を挿入 ま ず n のポインタを の次 (->ointer) に向ける 次 に のポインタを n に向ける 合致しない場合は視点を次へ送る (=->ointer) 43

44 リストへの挿入 (ソース) キーデータが存在しなかった場合, 最後のノードで合致し ないことが分かった後 =->ointer; の処理によっ て には NULL が入る これにより while文の条件 ( が NULL でない限り続け ろ) が満たされなくなり while文を抜ける すると, 関数の最後でエラーメッセージを表示して終了す る つまり 新しいノード n は作りっぱなしで放置され てしまう (見つかったノード がリストの最後尾であった場合も 新規ノード n のポインタを n->ointer=->ointer とするので n->ointer はきちんと NULL になる ) 44

45 リストへの挿入 (キーデータ不在時) キーデータが見つからないときはリストの先頭へデータを 追加するように書き直したコードが 単に 先程の whileループを抜けたところでエラーメッ セージを出すだけではなく, そこに先頭への挿入手順を書 き加えればよい 先頭への挿入手順 (復習) (1) 新しいノード n のポイン タ部を 既存リストの先頭位置 (それまでの head) に向 ける (2) head を新しいノード n に向ける head Keisatsu 110 n Kyuukyuu

46 リストからの削除 既に存在するリストからキーデータを逐次探索で探し出し, そのノードをリストから削除する関数 del()を作る ダミー ノードを用いない場合は 先頭データを削除する 場合 と 先頭以外の場合 とで手順が異なるため 場合分けが 必要である 視点2つ と old を用意し 双方 head で初期化 while(!=null) のループで 視点 を回す キーデータが先頭 (A) だったとき (キーデータ発見の時点 で ==head) head を ->ointer に向ける head,old A B C ほんとは不要になったノードの消去を

47 リストからの削除 キーデータが先頭ではなかったとき (例えば C) キーデータと一致するノード () の一つ手前のノード (old) のポインタを の次のノード位置 (->ointer) に向けかえる, old は head で初期化していた 最初の位置 (A) では 発見しなかった場合 old = としてから を一つ進める ( = ->ointer) 発見したら old のポインタを ->ointer へ向ける キーデータが C の時, old A old->ointer = ->ointer;, old B C D 47

48 リストからの削除 発見したノード () が最後尾だとした場合も今のアルゴリ ズムできちんと処理可能 ノードが複数の場合 (検索キー C),old A,old B C old->ointer = ->ointer; = NULL ノードが一つだけしかなかった場合 (検索キー A),old A head = ->ointer; = NULL 48

49 リストからの削除 (ソース) 削除の関数は del() void del(char *key) キー文字列へのポインタを受け取っている { struct tfield *,*old; 視点 old 視点の一つ前のノード =old=head; 初期化 while (!=NULL){ if (strcm(key,->name)==0){ 視点位置 での照合 if (==head) head=->ointer; else old->ointer=->ointer; return; 抜ける 場合分けしてポインタ向けかえ } old=; =->ointer; 視点を右にずらす old は一個遅れて追従 } rintf("キーデータが見つかりません n"); エラーメッセージ } 49

50 リストからの削除 (ダミー ノード版) 先程の例では 削除されるべきノードが head に直結して いる場合と 次以降である場合とで head を変更す る 場合と old->ointer を変更する 場合の場合分 けが必要となる 前の議論と同様, この場合もダミー ノードが有用 これにより head 直後に対する場合分けがなくなるので 一つ手前の視点 である old を使う必要がなくなる 視点位置を とするとその次を見る の次のノー ドの名前欄 は ->ointer->name 次のノードのポ インタ欄 は ->ointer->ointer で参照できる ソースは.246 を head で初期化 ->ointer が NULL でない限り続ける while ループを回す 50

51 リストからの削除 (ダミー ノード版) ループ内部では ->ointer->name (の一つ先のノー ドのデータ部) と key との照合を行う 合致しない場合は 単に を1つ進める 合致した場合 ->ointer を ->ointer->ointer に向けかえる つまり のポインタ部を の二つ先につ ないでしまう 検索データが B の場合 A B C ダミー ノード ->ointer->name つまり A を調べる A B より 合致せず ここで合致 を2つ先 (->ointer->ointer) につなぐ 51

52 メモリ領域の開放 教科書のやり方では 削除されたノードへのポインタを向け変 えてすましている つまり 削除されたノードのメモリ領域 は どこからも参照されないムダ領域として残る ノードはもともと malloc() によって動的に確保されたも の つまり, プログラムのためにコンピュータから分けても らった領域である 教科書のやり方では ノードを削除してもそのノードのための メモリ領域はプログラムのために確保され続けるため 大量に ノードの作成 削除を繰り返すと 無駄に確保され続ける無用 のメモリ領域 (ゴミ) が大量に生まれてしまう コンピュータを ゴミ屋敷 のようにしないためには きちん とゴミを処分しなくてはならない 即ち 不要になったメモリ 領域を開放し コンピュータに返してやる 52

53 メモリ領域の開放 malloc() を使って動的に確保したメモリを解放してシス テム (コンピュータ) に返還する関数 free() 例えば ポインタ で参照されるノードを解放するに は free(); とすればよい これだけで スライド上に 大きな赤のバッテンで描いた消去処理が実現できる 例えば教科書.244 のコードでは 以下を追加すればよい if (strcm(key,->name)==0) 赤ペンなどで if (==head) 書き加えてください { head=->ointer; free();} else { old->ointer=->ointer; free();} return; } お行儀の良いプログラミングを 53

54 いろいろなリスト構造 ここまでで扱ってきたリスト構造 head から順にノード を後ろへたどっていき 最後は NULL で終わる このよう なリストを 線形リスト (linear list) と呼ぶ リストにはこれ以外の形式もある 循環リスト (circular list) 線形リストの最後が NULL で はなく 先頭ノードへのポインタとなっている 従って データの終端はない 線形リスト A B C D A B C D 循環リスト

55 双方向リスト また 線形リストでは常に前から後ろへ進むことしかできな い 次のノードへのポインタ (順ポインタ) はあるが 手 前のノードへのポインタ (逆ポインタ) はない 順ポインタとともに 逆ポインタも付け加えたリストがあり これを 双方向リスト (doubly-linked list) と呼ぶ ノードの構造体にはこれら2つのポインタ部, すなわち 順方向 のポインタ right 逆方向のポインタ left が入る 循環型でない場合は 両端の外側ポインタは NULL とし 両端 ノードへのポインタ head と tail を用いる 順ポインタ head A left tail B right C 逆ポインタ 55

56 双方向リストの作成 教科書の例では 末端である tail を起点にして 逆順リ ストの作成 を行い 左端を head からつなぐことによ り 逆順リストの生成手順を使って入力順リストを作って いる ソースは head A B tail C =talloc(); =talloc(); =talloc(); ->left=tail; ->left=tail; ->left=tail; tail=; tail=; tail=; ->right=head;->right=head;->right=head; head=; head=; head=; =->left; = NULL =->left; =->left; 56

57 循環 双方向リスト 双方向リストの両端のノード同士を相互に接続すれば, 循 環 双方向リストとなる (tail は不要となる) head tail A B ダミー ノード ダミー ノードが以下の2点で重要な役割を果たす (1) 先頭ノードに対する特別な処理の排除 (2) データ探索における番兵の役割 リストの作成時には まず空きリストから初めて新しい ノードを後ろへつなげていく head ダミー ノード 57

58 循環 双方向リスト 既存の循環 双方向リストに新たなノードを加える手順は 以下のようになる (順番に注意) (1) (新ノード) の right を先頭ノード (head) へ (2) の left を最後尾ノード (head->left) へ (3) 最後尾ノード (head->left) の right を へ (4) 先頭ノード (head) の left を へ 教科書に誤植.252 一つめの A は 正しくは D 初期状態 head A B この順番を間違うと何が起こるか考えてみること 58

59 自己再編成探索 (試験範囲外) 線形リストとして記録されたデータに対して逐次探索を行 うことを考える 逐次探索ではデータの先頭から1つ1つ調べていくので 後ろにあるものほど探索に時間がかかる ここで 一つの傾向を利用して探索効率を高めることを考 える 自己再編成探索 (self re-organizing search) 傾向 一度使われたデータは再度使われる可能性が高い そこで データが探索されるたびに 探索されたデータを 前の方に移動する 例 PC上で漢字変換をした場合 直前に変換した漢字が 今回の第1候補となる 学習機能 データの挿入 削除を頻繁に行う リストが適切

60 自己再編成探索 (探索データを先頭へ) まず逐次探索を行う 視点 と視点の手前 old を用意し て head で初期化 の位置を照合 一致しないときは old を のところへ 引っ張ってきてから を進める (=->ointer) 一致した場合 まず手前ノード (old) を の次のノード (->ointer) へつなげる 次に のポインタを先頭ノード (head) へ向け head を に向ける 探索データが C の場合 head, old, old A B C D 60

61 自己再編成探索 (探索データを1つ前へ) 探索データを1つだけ前に持って行くのは少し大変 探索データと1つ前との入れ替えのために, 2つ前 の位 置も分かっていなければならない ダミー ノード, old1, old2 の利用 で一致しないとき old1 を old2 へ old2 を へ を次へ 一致したら (1) old1->ointer を q として保存 (2) old1 のポインタを に (3) old2 のポインタを の次 に (4) のポインタを q に 探索データが C の場合 head old2,old1, old2 A 見つかったのがAまたはDのときは q B C D 61