第４回
基本データ構造２
連結リスト と その操作
４－１．リスト構造
「データ部」と「ポインタ部」で構成され、ポインタをたどることによりデータを扱うことが できる構造。４－２．単方向リスト と その操作
４－２-１．単方向リスト
次のデータへのポインタを 1 つだけ持っているデータ構造。 （データ部は、複数のデータを持っている場合もある） リストを構成する要素のことを「ノード（node）」という。４－２-２．単方向リストを実現するデータ構造
４－２-３．挿入
② ① データ部 ポインタ部 struct singly_list { int value; /* データ */struct singly_list *next; /* 次へのポインタ */
}; ノード 挿入する新しいノード ｐ ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●
ポインタによって指されているノード 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 , 1 ); /* 先頭のノードの次に挿入 */ now = insert( g_top , 2 ); /* 先頭のノードの次に挿入 */ now = insert( g_top->next , 3 ); /* 先頭のノードの次の次に挿入 */ now = insert( now , 4 ); /* 新たに追加したのノードの次に挿入 */ return ( 0 );
}
/* ポインタによって指されているノードｐの次に新しいノードを挿入する */ /* 新しいノードへ格納する値も設定する */
/* 戻り値は、正常時：挿入したノードのポインタ エラー時：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; /* とりあえず初期値を０と設定 */
} }
４－２-４．削除
ポインタによって指されているノード 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 ); } /* ポインタによって指されているノードｐの次のノードを削除する */ 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 ); /* 削除するノードをメモリから解放する */ } } ｐ ● ｐ ● ● ● ● ●
４－３．双方向リスト と その操作
４－３-１．双方向リスト
次のデータと前のデータへのポインタを両方持っているデータ構造。 （データ部は、複数のデータを持っている場合もある）４－３-２．双方向リストを実現するデータ構造
４－３-３．挿入
struct doubly_list { int value; /* データ */struct doubly_list *pre; /* 前へのポインタ */
struct doubly_list *next; /* 次へのポインタ */
}; ● ● ● ● ● ● ● ● ● ● ● ● ｐ ● ① ② ③ ④ ● ● ● ● ● ● ● ● 挿入する新しいノード ｐ ● ● ● ● ● ● ● ● ● ● ●
（１）ポインタによって指されているノード 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 , 1 ); /* 先頭のノードの次に挿入 */ now = insert_next( g_top , 2 ); /* 先頭のノードの次に挿入 */ now = insert_next( g_top->next , 3 ); /* 先頭のノードの次の次に挿入 */ now = insert_next( now , 4 ); /* 新たに追加したのノードの次に挿入 */ return ( 0 );
}
/* ポインタによって指されているノードｐの次に新しいノードを挿入する */ /* 新しいノードへ格納する値も設定する */
/* 戻り値は、正常時：挿入したノードのポインタ エラー時：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; /* とりあえず初期値を０と設定 */
g_end->value = 0; /* とりあえず初期値を０と設定 */ }
（２）ポインタによって指されているノード 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 , 1 ); /* 末尾のノードに挿入 */
now = insert_now( now , 2 ); /* 新たに追加したノードに挿入 */ now = insert_now( now->next , 3 ); /* 新たに追加したノードの次に挿入 */ now = insert_now( now , 4 ); /* 新たに追加したノードに挿入 */ return ( 0 );
}
/* ポインタによって指されているノードｐの場所に新しいノードを挿入する */ /* 新しいノードへ格納する値も設定する */
/* 戻り値は、正常時：挿入したノードのポインタ エラー時：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; /* とりあえず初期値を０と設定 */
g_end->value = 0; /* とりあえず初期値を０と設定 */ }
４－３-４．削除
ポインタによって指されているノード 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 ); } /* ポインタによって指されているノードｐを削除する */ void delete_now( struct doubly_list *p )
{ if ( p != NULL ) { /* 削除するノードが存在したら */ p->pre->next = p->next; /* 前のノードのリンクをつなぎ替える */ p->next->pre = p->pre; /* 次のノードのリンクをつなぎ替える */ free( p ); /* 削除するノードをメモリから解放する */ } } ｐ ● ｐ ● ② ● ● ● ● ● ● ● ●
４－４．木構造（tree structure）
階層の上位から下位に節点をたどることにより、データを取り出すことができる構造。 の部分を「節（node）」、 の部分を「枝（branch）」という。 特に、最上位の節（赤の節）を「根（root）」、最下位の節（緑の節）を「葉（leaf）」という。 さらに、木構造の各節どうしには親子関係があり、上位の節を「親」、下位の節を「子」という。 よって、「根」は「親がない節」、「葉」は「子がない節」ということもできる。 また、節にぶら下がっている部分を「部分木」という。 部分木をさらに区別して、節の左側のものを「左部分木」 節の右側の部分を「右部分木」という。 右図の例の場合、 ①の子は、②と③ ②の子は、④と⑤ ②の親は、① ④の親は、② ①の左部分木は、②・④・⑤ ①の右部分木は、③ ②の左部分木は、④ ②の右部分木は、⑤ ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● root （ルート） leaf （リーフ） branch （ブランチ） ● ⑤ ● ● ④ ● ● ① ● ● ② ● ● ③ ●４－５．木構造の種類
４－５-１．２分木（binary tree）
すべての枝の分岐が、高々２つ1であるもの。
４－５-２．完全２分木（complete binary tree）
２分木のうち、根から葉までの深さがすべて等しいもの。４－５-３．２分探索木（binary search tree）
各節において、左の子＜親＜右の子 の関係になっているもの。 根から葉へ向かって、データを探索するときに利用される。
４－５-４．ヒープ木（heap tree）
各節における大小関係が、すべての節において 親＜子 の関係になっているか、 親＞子 の関係になっているもの。 親＜子 の関係のヒープ木の場合は、根が最小値となり、 親＞子 の関係のヒープ木の場合は、根が最大値となる。 データを整列するときに利用される。４－６．２分木 と その操作
４－６-１．２分木を実現するデータ構造
４－６-２．節の 挿入と削除
単方向リストでの挿入・削除と、同様の手順で行なう。 （ → 参考：第 4 回 ４－２．単方向リストとその操作） ただし、葉ではない節を削除する際は、その節にぶら下がっている子のつなぎ替えを 注意して行なう必要がある。 1 「高々」：「多くても」の意味。「高々２つ」だと、0 個 または 1 個 または 2 個が該当する。 struct binary_tree { int value; /* データ */struct binary_tree *left; /* 左の子へのポインタ */
struct binary_tree *right; /* 右の子へのポインタ */
４－６-３．挿入
４－６-４．削除
（１）子がない場合
（２）子が１つの場合
● ⑤ ● ● ④ ● ● ① ● ● ② ● ● ③ ● ● new ● ● ⑤ ● ● ④ ● ● ① ● ● ② ● ● ③ ● ● new ● ● ⑥ ● ● ⑤ ● ● ① ● ● ④ ● ● ③ ● ● ② ● ● ⑥ ● ● ⑤ ● ● ① ● ● ④ ● ● ③ ● ● ② ● ● ⑥ ● ● ⑤ ● ● ① ● ● ④ ● ● ③ ● ● ⑤ ● ● ① ● ● ④ ● ● ③ ● ● ② ●（３）子が２つの場合
子が 2 つの場合は、子のどちらか（仮に「子 A」）を削除する節の場所に移動し、もう一方の子 （仮に「子 B」）を「子 A」の子にする。 もともと「子 A」にも、子が２つあった場合は、その子のどちらかを順に下の階層に送る。 ● ⑥ ● ● ⑤ ● ● ① ● ● ④ ● ● ③ ● ● ② ● ● ⑥ ● ● ① ● ● ⑤ ● ● ③ ● ● ② ● 4 8 9 5 10 11 2 6 12 13 7 14 15 3 1 8 9 5 10 11 4 6 12 13 7 14 15 3 2 4 8 9 2 6 12 13 7 14 15 3 1 8 9 4 6 12 13 7 14 15 3 2 5 10 11 2 6 12 13 7 14 15 3 1 10 11 5 6 12 13 7 14 15 3 2４－７．木構造の応用
４－７-１．四則演算式の解析
コンパイラや簡易言語等で、計算機が数式を構文解析する際、演算子の優先順位に従って 数式の構成を解析するときに、木構造が用いられる。 例）（４＋２）×（３－１） という数式の場合 このように 2 分木に展開する。 展開のルールは、 ・葉の部分には、数値を置く。それ以外の節は、演算子を置く。 ・演算子の優先順位が高いものほど、深い階層（葉に近いほう）にする。 2 分木に展開した後、「（左部分木）（演算子）（右部分木）」という計算を進めればよい。 計算を進めるにあたり、各節に入っているものを１つずつ読み出して処理をすることに なるのだが、次のような順番で読み出して処理をすることにより、プログラム的な処理を 簡素化できる。 この読み出し順に従って記述すると、次のようになる。 ４ ２ ＋ ３ １ － × ＋ ４ ２ － ３ １ × ６ － ３ １ × ６ × ４ ２ ＋ ３ １ － × ① ②このように演算子を、計算する２つの項の後ろに配置する記法を、
逆ポーランド記法
（後置記法）という。 この記法の特徴は、演算子の優先順位を考えることなく、括弧を必要としないで、読み出した 順番どおりに計算処理を進められることにある。 実際に、スタックを用いてこの計算をすると、次のようになる。 例）４＋２×３－１ という数式の場合 ４ ４を積む ２ ４ ２を積む ６ ＋の計算をし 結果を積む ３ ６ ３を積む １ ３ ６ １を積む ２ ６ －の計算をし 結果を積む 12 ×の計算をし 結果を積む ・数値の項を読み出したら · ・演算子を読み出したら ·· 計算処理をする際のルール ４ × ＋ ２ ３ １ －４－７-２．データファイルの圧縮
コンピュータで扱う電子データは、ネットワーク上で送信したり、パッケージとして配布したり する場合、ファイルサイズが小さいほうがよい。 そのために、元のデータを構成している符号を効率よく置き換えることにより、全体の符号長 （ビット数）を小さくする。このことを「圧縮（compress）」という。 その符号置換の方法の一つに「ハフマン法」というものがあり、置換符号の生成に、木構造が 用いられる。 例）文字列データの圧縮 'a' , 'b' , 'c' , 'd'の 4 文字からなるデータで、それぞれの出現回数が 50% , 30% , 10% , 10% で、ある場合。 木への展開の手順は、 ① 葉の部分に文字を置き、出現回数の多い順に並べる。 ② 最小の 2 つを選んで、それらを子にもつ部分木を作る。 ③ その子の重みの和を、部分木の重みとする。 ④ ②、③を 1 つの木になるまで繰り返す。 ⑤ 作成された木の左右の枝に０と１を割り振っていく。 ⑥ 根から葉までをたどり、枝に割り振った 0/1 を並べた ビット列を、葉の要素に割り当てる。 圧縮前の均等の長さに符号が割り振られているものとの比較をすると、 文字 a b c d 固定長符号 00 01 10 11 出現回数 50% 30% 10% 10% ハフマン符号 0 10 110 111 この表から、圧縮前の固定長では 1 文字あたりのビット長は 2bit だが、 圧縮後の 1 文字あたりの平均ビット長は、1bit×0.5 ＋ 2bit×0.3 ＋ 3bit×0.1 ＋ 3bit×0.1 ＝ 0.5＋0.6＋0.3＋0.3 ＝ 1.7bit
となり、仮に 100 文字分のデータの場合、 圧縮前 2 bit×100 = 200 bit が 圧縮後 1.7 bit×100 = 170 bit で、 30bit（15 文字分）少なくなる。 文字などの固定長の符号で構成されているデータについて、出現回数が多いものには短い ビット列、少ないものには長いビット列に置き換えることにより、1 つあたりの平均ビット長 を最小にする符号化方式。 ハフマン法 b a c d 0 0 1 1 0 1 50% 30% 10% 10% 20% 50%
４－８．再帰プログラム
４－８-１．木構造と再帰関数
木構造は、親と部分木から成り立っており、部分木をみても、その中身は(新たな)親と部分木と なっている。 その性質に着目すると、節をたどっていくときに、「部分木の中身をたどる」という処理の中で さらに「部分木の中身をたどる」という処理が出てくる。 このように、ある処理をする関数の中で、その関数自身を呼び出す仕組みを「再帰（recursive）」 という。 また、そのように自分のなかで自分自身の関数を呼び出すことを「再帰的に呼び出す」ともいう。 例）2 分木の一番深い階層レベルを調べる。 関数 kaisou 引数：その節の階層レベル、その節へのポインタ 左のレベルは、その階層で終わりなので、 それが左部分木の階層レベルになる 左のレベルを１つ増やして、 左部分木について関数 kaisou を呼ぶ 戻ってきた値が左部分木の深さなので、 それが左部分木の階層レベルになる ない ある 左部分木はあるか？ 右のレベルは、その階層で終わりなので、 それが右部分木の階層レベルになる 右のレベルを１つ増やして、 右部分木について関数 kaisou を呼ぶ 戻ってきた値が右部分木の深さなので、 それが右部分木の階層レベルになる ない ある 右部分木はあるか？ 左と右の階層レベルのうち、 より深いほうが、その節以下の深さなので、 それを戻り値とする 関数 kaisou の処理が終了なので、戻る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 + 1 , sub_tree->left ); }
if ( sub_tree->right == NULL ) { /* 右部分木の階層を調べる */
right_level = level; } else {
right_level = kaisou( level + 1 , sub_tree->right ); } if ( left_level > right_level ) { /* 深いほうを戻り値にする */ return ( left_level ); } else { return ( right_level ); } }
int main( void ) {
tree_entry(); /* 二分木のデータを作る（関数の中身は省略） */
printf( "deepest level = %d\n" , kaisou( 1 , root ) );
/* 根からたどって深さを調べる */ return ( 0 ); } ３ ３ ２ ４ ４ ２ １ ＋１ ＋１ ＋１ ＋１ ＋１ ＋１ 呼ぶ 呼ぶ ３で戻る ４ ４ ４ ４ ２ この部分木は４ この部分木は４ （左が３、右が４なので 深いほうの４になる） 根の左部分木は４で 右部分木は２なので、 全体としては、最終的に 深いほうの４になる。 子がない場合は、 その枝のポインタは NULL として データを作っている
４－８-２．再帰的に呼び出す関数を作る際の注意
自分の関数内で、自分自身を呼び出しているので、終了条件をきちんと設定していないと、 無限に呼び続けることになり、終わらなくなってしまう。 よって、必ず「もうこれ以上は呼ばない」という条件を設定し、適切に処理を戻す必要がある。４－８-３．再帰プログラムの例題
ある自然数ｎまでの総和（1+2+3+・・・+ｎ）を求めるプログラムを、再帰的に呼び出す関数 を用いて作成せよ。 ※この例では、エラーチェックが充分でないので、n が 250 くらいまでしか正常に動作しない。 #include <stdio.h>int sigma( int value ) { if ( value == ) { return ( ); } else { return ( + sigma( ) ); } }
int main( void ) {
int n;
printf( "n = " ); scanf( "%d" , &n );
if ( n <= 0 ) {
printf( "Error! Input value is illegal!\n" ); return ( 1 );
}
printf( "sigma = %d\n" , sigma( n ) ); return ( 0 );
４－９．Appendix
４－９-１．単方向リスト操作のプログラム「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 );
}
/* ポインタによって指されているノードｐの次に新しいノードを挿入する */ /* 新しいノードへ格納する値も設定する */
/* 戻り値は、正常時：挿入したノードのポインタ エラー時：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 ); } /* ポインタによって指されているノードｐの次のノードを削除する */
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 = '.'; /* とりあえず初期値を'.'と設定 */
} }
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" ); }
４－９-２．双方向リスト操作のプログラム「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 27 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 );
}
/* ポインタによって指されているノードｐの次に新しいノードを挿入する */ /* 新しいノードへ格納する値も設定する */
/* 戻り値は、正常時：挿入したノードのポインタ エラー時：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 ); }
/* ポインタによって指されているノードｐの場所に新しいノードを挿入する */ /* 新しいノードへ格納する値も設定する */
/* 戻り値は、正常時：挿入したノードのポインタ エラー時：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 ); } /* ポインタによって指されているノードｐを削除する */
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" ); }
