第２回

Transcription

1 明星大学情報学科 年後期 アルゴリズムとデータ構造 Ⅰ 第 回 Page 第 回基本データ構造 連結リストとその操作 -. リスト構造 データ部 と ポインタ部 で構成され ポインタをたどることによりデータを扱うことができる構造 -. 単方向リストとその操作 --. 単方向リスト 次のデータへのポインタを つだけ持っているデータ構造 ( データ部は 複数のデータを持っている場合もある ) データ部 ポインタ部 ノード リストを構成する要素のことを ノード (node) という --. 単方向リストを実現するデータ構造 struct singly_list int value; /* データ */ struct singly_list *next; /* 次へのポインタ */ --. 挿入 p 挿入する新しいノード p [/]

2 明星大学情報学科 年後期 アルゴリズムとデータ構造 Ⅰ 第 回 Page ポインタによって指されているノード p の次に新しいノードを挿入する #include <stdio.h> #include <stdlib.h> struct singly_list /* 単方向リストの構造体定義 */ int value; /* データ */ struct singly_list *next; /* 次へのポインタ */ struct singly_list *g_top; /* 単方向リストの先頭へのポインタ */ void init( void ); struct singly_list *insert( struct singly_list *p, int value ); int main( void ) struct singly_list *now; init(); now = insert( g_top, ); /* 先頭のノードの次に挿入 */ now = insert( g_top, ); /* 先頭のノードの次に挿入 */ now = insert( g_top->next, ); /* 先頭のノードの次の次に挿入 */ now = insert( now, ); /* 新たに追加したのノードの次に挿入 */ return ( 0 ); /* ポインタによって指されているノード p の次に新しいノードを挿入する */ /* 新しいノードへ格納する値も設定する */ /* 戻り値は 正常時 : 挿入したノードのポインタエラー時 :NULL */ struct singly_list *insert( struct singly_list *p, int value ) struct singly_list *new_node; new_node = malloc( sizeof( struct singly_list ) ); if ( new_node!= NULL ) /* 新たなノードが生成できたら */ new_node->next = p->next; /* 新たなノードからのリンクを接続する */ p->next = new_node; /* 新たなノードへリンクをつなぎ替える */ new_node->value = value; /* 新たなノードの値を格納する */ return ( new_node ); void init( void ) /* 単方向リストの先頭のノードを生成する */ g_top = malloc( sizeof( struct singly_list ) ); if ( g_top!= NULL ) /* 新たなノードが生成できたら */ g_top ->next = NULL; /* 次のノードは存在しないので NULL */ g_top ->value = 0; /* とりあえず初期値を 0 と設定 */ [/]

3 明星大学情報学科 年後期 アルゴリズムとデータ構造 Ⅰ 第 回 Page --. 削除 p 削除するノード p ポインタによって指されているノード p の次のノードを削除する #include <stdio.h> #include <stdlib.h> struct singly_list /* 単方向リストの構造体定義 */ int value; /* データ */ struct singly_list *next; /* 次へのポインタ */ struct singly_list *g_top; /* 単方向リストの先頭へのポインタ */ struct singly_list *delete( struct singly_list *p ); int main( void ) /* 初期化と push は省略 */ delete( g_top ); /* 先頭のノードの次を削除 */ delete( g_top->next ); /* 先頭のノードの次の次を削除 */ return ( 0 ); /* ポインタによって指されているノード p の次のノードを削除する */ void delete( struct singly_list *p ) struct singly_list *delete_node; delete_node = p->next; if ( delete_node!= NULL ) /* 削除するノードが存在したら */ p->next = delete_node->next; /* 次のノードへリンクをつなぎ替える */ free( delete_node ); /* 削除するノードをメモリから解放する */ [/]

4 -. 双方向リストとその操作 --. 双方向リスト 明星大学情報学科 年後期 アルゴリズムとデータ構造 Ⅰ 第 回 Page 次のデータと前のデータへのポインタを両方持っているデータ構造 ( データ部は 複数のデータを持っている場合もある ) --. 双方向リストを実現するデータ構造 struct doubly_list int value; /* データ */ struct doubly_list *pre; /* 前へのポインタ */ struct doubly_list *next; /* 次へのポインタ */ --. 挿入 p 挿入する新しいノード p [/]

5 明星大学情報学科 年後期 アルゴリズムとデータ構造 Ⅰ 第 回 Page () ポインタによって指されているノード p の次に新しいノードを挿入する #include <stdio.h> #include <stdlib.h> struct doubly_list /* 双方向リストの構造体定義 */ int value; /* データ */ struct doubly_list *pre; /* 前へのポインタ */ struct doubly_list *next; /* 次へのポインタ */ struct doubly_list *g_top; /* 双方向リストの先頭へのポインタ */ struct doubly_list *g_end; /* 双方向リストの末尾へのポインタ */ void init( void ); struct doubly_list *insert_next( struct doubly_list *p, int value ); int main( void ) struct doubly_list *now; init(); now = insert_next( g_top, ); /* 先頭のノードの次に挿入 */ now = insert_next( g_top, ); /* 先頭のノードの次に挿入 */ now = insert_next( g_top->next, ); /* 先頭のノードの次の次に挿入 */ now = insert_next( now, ); /* 新たに追加したのノードの次に挿入 */ return ( 0 ); /* ポインタによって指されているノードpの次に新しいノードを挿入する */ /* 新しいノードへ格納する値も設定する */ /* 戻り値は 正常時 : 挿入したノードのポインタエラー時 :NULL */ struct doubly_list *insert_next( struct doubly_list *p, int value ) struct doubly_list *new_node; new_node = malloc( sizeof( struct doubly_list ) ); if ( new_node!= NULL ) /* 新たなノードが生成できたら */ new_node->pre = p; /* 新たなノードからのリンクを接続する */ new_node->next = p->next; /* 新たなノードからのリンクを接続する */ p->next = new_node; /* 新たなノードへリンクをつなぎ替える */ new_node->next->pre = new_node; /* 新たなノードへリンクをつなぎ替える */ new_node->value = value; /* 新たなノードの値を格納する */ return ( new_node ); void init( void ) /* 双方向リストの先頭のノードを生成する */ g_top = malloc( sizeof( struct doubly_list ) ); g_end = malloc( sizeof( struct doubly_list ) ); if ( (g_top!= NULL) && (e_end!= NULL) ) /* 新たなノードが生成できたら */ g_top->pre = NULL; /* 先頭の前のノードは存在しないので NULL */ g_top->next = g_end; /* 先頭の次のノードは g_end */ g_end->pre = g_top; /* 末尾の前のノードは g_top */ g_end->next = NULL; /* 末尾の次のノードは存在しないので NULL */ g_top->value = 0; /* とりあえず初期値を0と設定 */ g_end->value = 0; /* とりあえず初期値を0と設定 */ [/]

6 明星大学情報学科 年後期 アルゴリズムとデータ構造 Ⅰ 第 回 Page () ポインタによって指されているノード p の場所に新しいノードを挿入する #include <stdio.h> #include <stdlib.h> struct doubly_list /* 双方向リストの構造体定義 */ int value; /* データ */ struct doubly_list *pre; /* 前へのポインタ */ struct doubly_list *next; /* 次へのポインタ */ struct doubly_list *g_top; /* 双方向リストの先頭へのポインタ */ struct doubly_list *g_end; /* 双方向リストの末尾へのポインタ */ void init( void ); struct doubly_list *insert_now( struct doubly_list *p, int value ); int main( void ) struct doubly_list *now; init(); now = insert_now( g_end, ); /* 末尾のノードに挿入 */ now = insert_now( now, ); /* 新たに追加したノードに挿入 */ now = insert_now( now->next, ); /* 新たに追加したノードの次に挿入 */ now = insert_now( now, ); /* 新たに追加したノードに挿入 */ return ( 0 ); /* ポインタによって指されているノードpの場所に新しいノードを挿入する */ /* 新しいノードへ格納する値も設定する */ /* 戻り値は 正常時 : 挿入したノードのポインタエラー時 :NULL */ struct doubly_list *insert_now( struct doubly_list *p, int value ) struct doubly_list *new_node; new_node = malloc( sizeof( struct doubly_list ) ); if ( new_node!= NULL ) /* 新たなノードが生成できたら */ new_node->pre = p->pre; /* 新たなノードからのリンクを接続する */ new_node->next = p; /* 新たなノードからのリンクを接続する */ p->pre->next = new_node; /* 新たなノードへリンクをつなぎ替える */ p->pre = new_node; /* 新たなノードへリンクをつなぎ替える */ new_node->value = value; /* 新たなノードの値を格納する */ return ( new_node ); void init( void ) /* 双方向リストの先頭のノードを生成する */ g_top = malloc( sizeof( struct doubly_list ) ); g_end = malloc( sizeof( struct doubly_list ) ); if ( (g_top!= NULL) && (e_end!= NULL) ) /* 新たなノードが生成できたら */ g_top->pre = NULL; /* 先頭の前のノードは存在しないので NULL */ g_top->next = g_end; /* 先頭の次のノードは g_end */ g_end->pre = g_top; /* 末尾の前のノードは g_top */ g_end->next = NULL; /* 末尾の次のノードは存在しないので NULL */ g_top->value = 0; /* とりあえず初期値を0と設定 */ g_end->value = 0; /* とりあえず初期値を0と設定 */ [/]

7 明星大学情報学科 年後期 アルゴリズムとデータ構造 Ⅰ 第 回 Page 削除 p 削除するノード p ポインタによって指されているノード p を削除する #include <stdio.h> #include <stdlib.h> struct doubly_list /* 双方向リストの構造体定義 */ int value; /* データ */ struct doubly_list *pre; /* 前へのポインタ */ struct doubly_list *next; /* 次へのポインタ */ struct doubly_list *g_top; /* 双方向リストの先頭へのポインタ */ struct doubly_list *g_end; /* 双方向リストの末尾へのポインタ */ struct doubly_list *delete_now( struct doubly_list *p ); int main( void ) /* 初期化と push は省略 */ delete( now ); /* 現在のノードを削除 */ delete( now->next ); /* 現在のノードの次を削除 */ return ( 0 ); /* ポインタによって指されているノード p を削除する */ void delete_now( struct doubly_list *p ) if ( p!= NULL ) /* 削除するノードが存在したら */ p->pre->next = p->next; /* 前のノードのリンクをつなぎ替える */ p->next->pre = p->pre; /* 次のノードのリンクをつなぎ替える */ free( p ); /* 削除するノードをメモリから解放する */ [7/]

8 -. 木構造 (tree structure) 明星大学情報学科 年後期 アルゴリズムとデータ構造 Ⅰ 第 回 Page 8 階層の上位から下位に節点をたどることにより データを取り出すことができる構造 root ( ルート ) branch ( ブランチ ) leaf ( リーフ ) の部分を 節 (node) の部分を 枝 (branch) という 特に 最上位の節 ( 赤の節 ) を 根 (root) 最下位の節 ( 緑の節 ) を 葉 (leaf) という さらに 木構造の各節どうしには親子関係があり 上位の節を 親 下位の節を 子 という よって 根 は 親がない節 葉 は 子がない節 ということもできる また 節にぶら下がっている部分を 部分木 という 部分木をさらに区別して 節の左側のものを 左部分木 節の右側の部分を 右部分木 という 右図の例の場合 の子は と の子は と の親は の親は の左部分木は の右部分木は の左部分木は の右部分木は [8/]

9 -. 木構造の種類 明星大学情報学科 年後期 アルゴリズムとデータ構造 Ⅰ 第 回 Page 分木 (binary tree) すべての枝の分岐が 高々 つ であるもの --. 完全 分木 (complete binary tree) 分木のうち 根から葉までの深さがすべて等しいもの --. 分探索木 (binary search tree) 各節において 左の子 < 親 < 右の子の関係になっているもの 根から葉へ向かって データを探索するときに利用される --. ヒープ木 (heap tree) 各節における大小関係が すべての節において親 < 子の関係になっているか 親 > 子の関係になっているもの 親 < 子の関係のヒープ木の場合は 根が最小値となり 親 > 子の関係のヒープ木の場合は 根が最大値となる データを整列するときに利用される -. 分木とその操作 --. 分木を実現するデータ構造 struct binary_tree int value; /* データ */ struct binary_tree *left; /* 左の子へのポインタ */ struct binary_tree *right; /* 右の子へのポインタ */ --. 節の挿入と削除 単方向リストでの挿入 削除と 同様の手順で行なう ( 参考 : 第 回 -. 単方向リストとその操作 ) ただし 葉ではない節を削除する際は その節にぶら下がっている子のつなぎ替えを注意して行なう必要がある 高々 : 多くても の意味 高々 つ だと 0 個または 個または 個が該当する [9/]

10 明星大学情報学科 年後期 アルゴリズムとデータ構造 Ⅰ 第 回 Page 0 [0/] --. 挿入 --. 削除 () 子がない場合 () 子が つの場合 new new

11 明星大学情報学科 年後期 アルゴリズムとデータ構造 Ⅰ 第 回 Page () 子が つの場合 子が つの場合は 子のどちらか ( 仮に 子 A ) を削除する節の場所に移動し もう一方の子 ( 仮に 子 B ) を 子 A の子にする もともと 子 A にも 子が つあった場合は その子のどちらかを順に下の階層に送る [/]

12 -7. 木構造の応用 明星大学情報学科 年後期 アルゴリズムとデータ構造 Ⅰ 第 回 Page -7-. 四則演算式の解析 コンパイラや簡易言語等で 計算機が数式を構文解析する際 演算子の優先順位に従って数式の構成を解析するときに 木構造が用いられる 例 )(+) (-) という数式の場合 + - このように 分木に展開する 展開のルールは 葉の部分には 数値を置く それ以外の節は 演算子を置く 演算子の優先順位が高いものほど 深い階層 ( 葉に近いほう ) にする 分木に展開した後 ( 左部分木 )( 演算子 )( 右部分木 ) という計算を進めればよい 計算を進めるにあたり 各節に入っているものを つずつ読み出して処理をすることになるのだが 次のような順番で読み出して処理をすることにより プログラム的な処理を簡素化できる + - この読み出し順に従って記述すると 次のようになる [/]

13 明星大学情報学科 年後期 アルゴリズムとデータ構造 Ⅰ 第 回 Page このように演算子を 計算するつの項の後ろに配置する記法を 逆ポーランド記法 ( 後置記法 ) という この記法の特徴は 演算子の優先順位を考えることなく 括弧を必要としないで 読み出した順番どおりに計算処理を進められることにある 実際に スタックを用いてこの計算をすると 次のようになる 計算処理をする際のルール 数値の項を読み出したら 演算子を読み出したら を積む を積む + の計算をし結果を積む を積む を積む - の計算をし結果を積む の計算をし結果を積む 例 )+ - という数式の場合 - + [/]

14 -7-. データファイルの圧縮 明星大学情報学科 年後期 アルゴリズムとデータ構造 Ⅰ 第 回 Page コンピュータで扱う電子データは ネットワーク上で送信したり パッケージとして配布したりする場合 ファイルサイズが小さいほうがよい そのために 元のデータを構成している符号を効率よく置き換えることにより 全体の符号長 ( ビット数 ) を小さくする このことを 圧縮 (compress) という その符号置換の方法の一つに ハフマン法 というものがあり 置換符号の生成に 木構造が用いられる ハフマン法文字などの固定長の符号で構成されているデータについて 出現回数が多いものには短いビット列 少ないものには長いビット列に置き換えることにより つあたりの平均ビット長を最小にする符号化方式 例 ) 文字列データの圧縮 'a', 'b', 'c', 'd' の 文字からなるデータで それぞれの出現回数が 0%, 0%, 0%, 0% で ある場合 木への展開の手順は 葉の部分に文字を置き 出現回数の多い順に並べる 最小の つを選んで それらを子にもつ部分木を作る その子の重みの和を 部分木の重みとする を つの木になるまで繰り返す 作成された木の左右の枝に 0 と を割り振っていく 根から葉までをたどり 枝に割り振った 0/ を並べたビット列を 葉の要素に割り当てる 圧縮前の均等の長さに符号が割り振られているものとの比較をすると 文字 a b c d 固定長符号 出現回数 0% 0% 0% 0% ハフマン符号 この表から 圧縮前の固定長では 文字あたりのビット長は bit だが 圧縮後の 文字あたりの平均ビット長は bit 0. + bit 0. + bit 0. + bit 0. = =.7bit となり 仮に 00 文字分のデータの場合 圧縮前 bit 00 = 00 bit が圧縮後.7 bit 00 = 70 bit で 0bit( 文字分 ) 少なくなる a 0% 0 b 0% 0 c 0% 0% 0 d 0% 0% [/]

15 -8. 再帰プログラム 明星大学情報学科 年後期 アルゴリズムとデータ構造 Ⅰ 第 回 Page -8-. 木構造と再帰関数 木構造は 親と部分木から成り立っており 部分木をみても その中身は ( 新たな ) 親と部分木となっている その性質に着目すると 節をたどっていくときに 部分木の中身をたどる という処理の中でさらに 部分木の中身をたどる という処理が出てくる このように ある処理をする関数の中で その関数自身を呼び出す仕組みを 再帰 (recursive) という また そのように自分のなかで自分自身の関数を呼び出すことを 再帰的に呼び出す ともいう 例 ) 分木の一番深い階層レベルを調べる 関数 kaisou 引数 : その節の階層レベル その節へのポインタ 左部分木はあるか? ない 左のレベルは その階層で終わりなので それが左部分木の階層レベルになる ある 左のレベルを つ増やして 左部分木について関数 kaisou を呼ぶ戻ってきた値が左部分木の深さなので それが左部分木の階層レベルになる 右部分木はあるか? ない 右のレベルは その階層で終わりなので それが右部分木の階層レベルになる ある 右のレベルを つ増やして 右部分木について関数 kaisou を呼ぶ戻ってきた値が右部分木の深さなので それが右部分木の階層レベルになる 左と右の階層レベルのうち より深いほうが その節以下の深さなので それを戻り値とする 関数 kaisou の処理が終了なので 戻る [/]

16 明星大学情報学科 年後期 アルゴリズムとデータ構造 Ⅰ 第 回 Page struct binary_tree /* 二分木の節の構造体 */ int value; /* データ */ struct binary_tree *left; /* 左の子へのポインタ */ struct binary_tree *right; /* 右の子へのポインタ */ struct binary_tree *root; /* 根のポインタ */ int kaisou( int level, struct binary_tree *sub_tree ) /* 部分木の階層を調べる */ int left_level, right_level; if ( sub_tree->left == NULL ) /* 左部分木の階層を調べる */ left_level = level; else left_level = kaisou( level +, sub_tree->left ); if ( sub_tree->right == NULL ) /* 右部分木の階層を調べる */ right_level = level; else right_level = kaisou( level +, sub_tree->right ); if ( left_level > right_level ) /* 深いほうを戻り値にする */ return ( left_level ); else return ( right_level ); int main( void ) 子がない場合は その枝のポインタは NULL としてデータを作っている tree_entry(); /* 二分木のデータを作る ( 関数の中身は省略 ) */ printf( "deepest level = %d\n", kaisou(, root ) ); /* 根からたどって深さを調べる */ return ( 0 ); 呼ぶ + 呼ぶ 根の左部分木は で右部分木は なので 全体としては 最終的に深いほうの になる + + で戻る この部分木は ( 左が 右が なので深いほうの になる ) この部分木は [/]

17 明星大学情報学科 年後期 アルゴリズムとデータ構造 Ⅰ 第 回 Page 再帰的に呼び出す関数を作る際の注意 自分の関数内で 自分自身を呼び出しているので 終了条件をきちんと設定していないと 無限に呼び続けることになり 終わらなくなってしまう よって 必ず もうこれ以上は呼ばない という条件を設定し 適切に処理を戻す必要がある -8-. 再帰プログラムの例題 ある自然数 n までの総和 (+++ +n) を求めるプログラムを 再帰的に呼び出す関数を用いて作成せよ #include <stdio.h> int sigma( int value ) if ( value == ) else return ( ); return ( + sigma( ) ); int main( void ) int n; printf( "n = " ); scanf( "%d", &n ); if ( n <= 0 ) printf( "Error! Input value is illegal!\n" ); return ( ); printf( "sigma = %d\n", sigma( n ) ); return ( 0 ); この例では エラーチェックが充分でないので n が 0 くらいまでしか正常に動作しない [7/]

18 -9.Appendix 明星大学情報学科 年後期 アルゴリズムとデータ構造 Ⅰ 第 回 Page 単方向リスト操作のプログラム singly_list.c #include <stdio.h> #include <stdlib.h> struct singly_list /* 単方向リストの構造体定義 */ unsigned char value; /* データ */ struct singly_list *next; /* 次へのポインタ */ struct singly_list *g_top; /* 単方向リストの先頭へのポインタ */ void init( void ); struct singly_list *insert( struct singly_list *p, unsigned char value ); void delete( struct singly_list *p ); void disp_list( void ); int main( void ) struct singly_list *now; init(); printf( "init " ); disp_list(); now = insert( g_top, 'A' ); printf( "insert g_top 'A' " ); disp_list(); now = insert( g_top, 'B' ); printf( "insert g_top 'B' " ); disp_list(); now = insert( g_top->next, 'C' ); printf( "insert g_top->next 'C' " ); disp_list(); now = insert( now, 'D' ); printf( "insert now 'D' " ); disp_list(); delete( now ); printf( "delete now " ); disp_list(); delete( g_top ); printf( "delete g_top " ); disp_list(); return ( 0 ); /* ポインタによって指されているノードpの次に新しいノードを挿入する */ /* 新しいノードへ格納する値も設定する */ /* 戻り値は 正常時 : 挿入したノードのポインタエラー時 :NULL */ struct singly_list *insert( struct singly_list *p, unsigned char value ) struct singly_list *new_node; new_node = malloc( sizeof( struct singly_list ) ); if ( new_node!= NULL ) /* 新たなノードが生成できたら */ new_node->next = p->next; /* 新たなノードからのリンクを接続する */ p->next = new_node; /* 新たなノードへリンクをつなぎ替える */ new_node->value = value; /* 新たなノードの値を格納する */ return ( new_node ); /* ポインタによって指されているノードpの次のノードを削除する */ void delete( struct singly_list *p ) struct singly_list *delete_node; delete_node = p->next; if ( delete_node!= NULL ) /* 削除するノードが存在したら */ p->next = delete_node->next; /* 次のノードへリンクをつなぎ替える */ free( delete_node ); /* 削除するノードをメモリから解放する */ void init( void ) /* 単方向リストの先頭のノードを生成する */ g_top = malloc( sizeof( struct singly_list ) ); if ( g_top!= NULL ) /* 新たなノードが生成できたら */ g_top->next = NULL; /* 次のノードは存在しないので NULL */ g_top->value = '.'; /* とりあえず初期値を '.' と設定 */ [8/]

19 明星大学情報学科 年後期 アルゴリズムとデータ構造 Ⅰ 第 回 Page 9 void disp_list( void ) struct singly_list *disp_node; disp_node = g_top; while ( disp_node!= NULL ) printf( "%c", disp_node->value ); disp_node = disp_node->next; printf( "\n" ); [9/]

20 明星大学情報学科 年後期 アルゴリズムとデータ構造 Ⅰ 第 回 Page 双方向リスト操作のプログラム doubly_list.c #include <stdio.h> #include <stdlib.h> struct doubly_list /* 双方向リストの構造体定義 */ unsigned char value; /* データ */ struct doubly_list *pre; /* 前へのポインタ */ struct doubly_list *next; /* 次へのポインタ */ struct doubly_list *g_top; /* 双方向リストの先頭へのポインタ */ struct doubly_list *g_end; /* 双方向リストの末尾へのポインタ */ void init( void ); struct doubly_list *insert_next( struct doubly_list *p, unsigned char value ); struct doubly_list *insert_now( struct doubly_list *p, unsigned char value ); struct doubly_list *delete_now( struct doubly_list *p ); void disp_list( struct doubly_list *p ); #define NOW_DISP_OFFSET 7 int main( void ) struct doubly_list *now; init(); printf( "init " ); disp_list(g_top); now = insert_next( g_top, 'A' ); printf( "insert_next g_top 'A' " ); disp_list(now); now = insert_next( g_top, 'B' ); printf( "insert_next g_top 'B' " ); disp_list(now); now = insert_next( now->next, 'C' ); printf( "insert_next now->next 'C' " ); disp_list(now); now = insert_next( now, 'D' ); printf( "insert_next now 'D' " ); disp_list(now); now = now->pre->pre; printf( "now = now->pre->pre " ); disp_list(now); now = delete_now( now ); printf( "delete_now now " ); disp_list(now); now = delete_now( now ); printf( "delete_now now " ); disp_list(now); init(); printf( "init " ); disp_list(g_top); now = insert_next( g_top, 'A' ); printf( "insert_next g_top 'A' " ); disp_list(now); now = insert_now( now, 'B' ); printf( "insert_now now 'B' " ); disp_list(now); now = insert_now( now->next, 'C' ); printf( "insert_now now->next 'C' " ); disp_list(now); now = insert_now( now, 'D' ); printf( "insert_now now 'D' " ); disp_list(now); now = delete_now( now ); printf( "delete_now now " ); disp_list(now); now = delete_now( now ); printf( "delete_now now " ); disp_list(now); return ( 0 ); /* ポインタによって指されているノード p の次に新しいノードを挿入する */ /* 新しいノードへ格納する値も設定する */ /* 戻り値は 正常時 : 挿入したノードのポインタエラー時 :NULL */ struct doubly_list *insert_next( struct doubly_list *p, unsigned char value ) struct doubly_list *new_node; new_node = malloc( sizeof( struct doubly_list ) ); if ( new_node!= NULL ) /* 新たなノードが生成できたら */ new_node->pre = p; /* 新たなノードからのリンクを接続する */ new_node->next = p->next; /* 新たなノードからのリンクを接続する */ p->next = new_node; /* 新たなノードへリンクをつなぎ替える */ new_node->next->pre = new_node; /* 新たなノードへリンクをつなぎ替える */ new_node->value = value; /* 新たなノードの値を格納する */ return ( new_node ); [0/]

21 明星大学情報学科 年後期 アルゴリズムとデータ構造 Ⅰ 第 回 Page /* ポインタによって指されているノード p の場所に新しいノードを挿入する */ /* 新しいノードへ格納する値も設定する */ /* 戻り値は 正常時 : 挿入したノードのポインタエラー時 :NULL */ struct doubly_list *insert_now( struct doubly_list *p, unsigned char value ) struct doubly_list *new_node; new_node = malloc( sizeof( struct doubly_list ) ); if ( new_node!= NULL ) /* 新たなノードが生成できたら */ new_node->pre = p->pre; /* 新たなノードからのリンクを接続する */ new_node->next = p; /* 新たなノードからのリンクを接続する */ p->pre->next = new_node; /* 新たなノードへリンクをつなぎ替える */ p->pre = new_node; /* 新たなノードへリンクをつなぎ替える */ new_node->value = value; /* 新たなノードの値を格納する */ return ( new_node ); /* ポインタによって指されているノード p を削除する */ struct doubly_list *delete_now( struct doubly_list *p ) struct doubly_list *now_p; if ( p!= NULL ) /* 削除するノードが存在したら */ p->pre->next = p->next; /* 前のノードのリンクをつなぎ替える */ p->next->pre = p->pre; /* 次のノードのリンクをつなぎ替える */ now_p = p->next; free( p ); /* 削除するノードをメモリから解放する */ return ( now_p ); void init( void ) /* 双方向リストの先頭のノードを生成する */ g_top = malloc( sizeof( struct doubly_list ) ); g_end = malloc( sizeof( struct doubly_list ) ); if ( (g_top!= NULL) && (g_end!= NULL) ) /* 新たなノードが生成できたら */ g_top->pre = NULL; /* 先頭の前のノードは存在しないので NULL */ g_top->next = g_end; /* 先頭の次のノードは末尾 */ g_end->pre = g_top; /* 末尾の前のノードは先頭 */ g_end->next = NULL; /* 末尾の次のノードは存在しないので NULL */ g_top->value = '.'; /* とりあえず初期値を '.' と設定 */ g_end->value = '.'; /* とりあえず初期値を '.' と設定 */ void disp_list( struct doubly_list *p ) struct doubly_list *disp_node; int i; disp_node = g_top; while ( disp_node!= NULL ) printf( "%c", disp_node->value ); disp_node = disp_node->next; printf( "\n" ); for ( i = 0 ; i < NOW_DISP_OFFSET ; i++ ) printf( " " ); disp_node = g_top; while ( (disp_node!= p) && (disp_node!=null) ) printf( " " ); disp_node = disp_node->next; printf( "^now\n" ); [/]