第 5 回基本データ構造 2 連結リストとその操作 第 5 回 Page 1 5-1. リスト構造 データ部 と ポインタ部 で構成され ポインタをたどることによりデータを扱うことができる構造 5-2. 単方向リストとその操作 5-2-1. 単方向リスト 次のデータへのポインタを 1 つだけ持っているデータ構造 ( データ部は 複数のデータを持っている場合もある ) データ部 ポインタ部 ノード リストを構成する要素のことを ノード (node) という 5-2-2. 単方向リストを実現するデータ構造 struct singly_list struct singly_list *next; /* 次へのポインタ */ 5-2-3. 挿入 挿入する新しいノード 2 1 [1/11]
第 5 回 Page 2 ポインタによって指されているノード の次に新しいノードを挿入する struct singly_list /* 単方向リストの構造体定義 */ struct singly_list *next; /* 次へのポインタ */ struct singly_list *g_to; /* 単方向リストの先頭へのポインタ */ void init( void ); struct singly_list *insert( struct singly_list *, int value ); struct singly_list *now; init(); now = insert( g_to, 1 ); /* 先頭のノードの次に挿入 */ now = insert( g_to, 2 ); /* 先頭のノードの次に挿入 */ now = insert( g_to->next, 3 ); /* 先頭のノードの次の次に挿入 */ now = insert( now, 4 ); /* 新たに追加したのノードの次に挿入 */ /* ポインタによって指されているノード の次に新しいノードを挿入する */ /* 戻り値は 正常時 : 挿入したノードのポインタエラー時 :NULL */ struct singly_list *insert( struct singly_list *, int value ) struct singly_list *new_node; new_node = malloc( sizeof( struct singly_list ) ); if ( new_node!= NULL ) /* 新たなノードが生成できたら */ new_node->next = ->next; /* 新たなノードからのリンクを接続する */ ->next = new_node; /* 新たなノードへリンクをつなぎ替える */ void init( void ) /* 単方向リストの先頭のノードを生成する */ g_to = malloc( sizeof( struct singly_list ) ); if ( g_to!= NULL ) /* 新たなノードが生成できたら */ g_to ->next = NULL; /* 次のノードは存在しないので NULL */ g_to ->value = 0; /* とりあえず初期値を 0 と設定 */ [2/11]
第 5 回 Page 3 5-2-4. 削除 削除するノード 1 2 ポインタによって指されているノード の次のノードを削除する struct singly_list /* 単方向リストの構造体定義 */ struct singly_list *next; /* 次へのポインタ */ struct singly_list *g_to; /* 単方向リストの先頭へのポインタ */ struct singly_list *delete( struct singly_list * ); /* 初期化と ush は省略 */ delete( g_to ); /* 先頭のノードの次を削除 */ delete( g_to->next ); /* 先頭のノードの次の次を削除 */ /* ポインタによって指されているノード の次のノードを削除する */ void delete( struct singly_list * ) struct singly_list *delete_node; delete_node = ->next; if ( delete_node!= NULL ) /* 削除するノードが存在したら */ ->next = delete_node->next; /* 次のノードへリンクをつなぎ替える */ free( delete_node ); /* 削除するノードをメモリから解放する */ [3/11]
5-3. 双方向リストとその操作 第 5 回 Page 4 5-3-1. 双方向リスト 次のデータと前のデータへのポインタを両方持っているデータ構造 ( データ部は 複数のデータを持っている場合もある ) 5-3-2. 双方向リストを実現するデータ構造 struct doubly_list struct doubly_list *re; /* 前へのポインタ */ struct doubly_list *next; /* 次へのポインタ */ 5-3-3. 挿入 挿入する新しいノード 3 1 2 4 [4/11]
第 5 回 Page 5 (1) ポインタによって指されているノード の次に新しいノードを挿入する struct doubly_list /* 双方向リストの構造体定義 */ struct doubly_list *re; /* 前へのポインタ */ struct doubly_list *next; /* 次へのポインタ */ struct doubly_list *g_to; /* 双方向リストの先頭へのポインタ */ struct doubly_list *g_end; /* 双方向リストの末尾へのポインタ */ void init( void ); struct doubly_list *insert_next( struct doubly_list *, int value ); struct doubly_list *now; init(); now = insert_next( g_to, 1 ); /* 先頭のノードの次に挿入 */ now = insert_next( g_to, 2 ); /* 先頭のノードの次に挿入 */ now = insert_next( g_to->next, 3 ); /* 先頭のノードの次の次に挿入 */ now = insert_next( now, 4 ); /* 新たに追加したのノードの次に挿入 */ /* ポインタによって指されているノードの次に新しいノードを挿入する */ /* 戻り値は 正常時 : 挿入したノードのポインタエラー時 :NULL */ struct doubly_list *insert_next( struct doubly_list *, int value ) struct doubly_list *new_node; new_node = malloc( sizeof( struct doubly_list ) ); if ( new_node!= NULL ) /* 新たなノードが生成できたら */ new_node->re = ; /* 新たなノードからのリンクを接続する */ new_node->next = ->next; /* 新たなノードからのリンクを接続する */ ->next = new_node; /* 新たなノードへリンクをつなぎ替える */ new_node->next->re = new_node; /* 新たなノードへリンクをつなぎ替える */ void init( void ) /* 双方向リストの先頭のノードを生成する */ g_to = malloc( sizeof( struct doubly_list ) ); g_end = malloc( sizeof( struct doubly_list ) ); if ( (g_to!= NULL) && (e_end!= NULL) ) /* 新たなノードが生成できたら */ g_to->re = NULL; /* 先頭の前のノードは存在しないので NULL */ g_to->next = g_end; /* 先頭の次のノードは g_end */ g_end->re = g_to; /* 末尾の前のノードは g_to */ g_end->next = NULL; /* 末尾の次のノードは存在しないので NULL */ g_to->value = 0; /* とりあえず初期値を0と設定 */ g_end->value = 0; /* とりあえず初期値を0と設定 */ [5/11]
第 5 回 Page 6 (2) ポインタによって指されているノード の場所に新しいノードを挿入する struct doubly_list /* 双方向リストの構造体定義 */ struct doubly_list *re; /* 前へのポインタ */ struct doubly_list *next; /* 次へのポインタ */ struct doubly_list *g_to; /* 双方向リストの先頭へのポインタ */ struct doubly_list *g_end; /* 双方向リストの末尾へのポインタ */ void init( void ); struct doubly_list *insert_now( struct doubly_list *, int value ); 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 ); /* 新たに追加したノードに挿入 */ /* ポインタによって指されているノードの場所に新しいノードを挿入する */ /* 戻り値は 正常時 : 挿入したノードのポインタエラー時 :NULL */ struct doubly_list *insert_now( struct doubly_list *, int value ) struct doubly_list *new_node; new_node = malloc( sizeof( struct doubly_list ) ); if ( new_node!= NULL ) /* 新たなノードが生成できたら */ new_node->re = ->re; /* 新たなノードからのリンクを接続する */ new_node->next = ; /* 新たなノードからのリンクを接続する */ ->re->next = new_node; /* 新たなノードへリンクをつなぎ替える */ ->re = new_node; /* 新たなノードへリンクをつなぎ替える */ void init( void ) /* 双方向リストの先頭のノードを生成する */ g_to = malloc( sizeof( struct doubly_list ) ); g_end = malloc( sizeof( struct doubly_list ) ); if ( (g_to!= NULL) && (e_end!= NULL) ) /* 新たなノードが生成できたら */ g_to->re = NULL; /* 先頭の前のノードは存在しないので NULL */ g_to->next = g_end; /* 先頭の次のノードは g_end */ g_end->re = g_to; /* 末尾の前のノードは g_to */ g_end->next = NULL; /* 末尾の次のノードは存在しないので NULL */ g_to->value = 0; /* とりあえず初期値を0と設定 */ g_end->value = 0; /* とりあえず初期値を0と設定 */ [6/11]
第 5 回 Page 7 5-3-4. 削除 削除するノード 1 ポインタによって指されているノード を削除する 3 2 struct doubly_list /* 双方向リストの構造体定義 */ struct doubly_list *re; /* 前へのポインタ */ struct doubly_list *next; /* 次へのポインタ */ struct doubly_list *g_to; /* 双方向リストの先頭へのポインタ */ struct doubly_list *g_end; /* 双方向リストの末尾へのポインタ */ struct doubly_list *delete_now( struct doubly_list * ); /* 初期化と ush は省略 */ delete( now ); /* 現在のノードを削除 */ delete( now->next ); /* 現在のノードの次を削除 */ /* ポインタによって指されているノード を削除する */ void delete_now( struct doubly_list * ) if (!= NULL ) /* 削除するノードが存在したら */ ->re->next = ->next; /* 前のノードのリンクをつなぎ替える */ ->next->re = ->re; /* 次のノードのリンクをつなぎ替える */ free( ); /* 削除するノードをメモリから解放する */ [7/11]
5-4.Aendix 第 5 回 Page 8 5-4-1. 単方向リスト操作のプログラム singly_list.c struct singly_list /* 単方向リストの構造体定義 */ unsigned char value; /* データ */ struct singly_list *next; /* 次へのポインタ */ struct singly_list *g_to; /* 単方向リストの先頭へのポインタ */ void init( void ); struct singly_list *insert( struct singly_list *, unsigned char value ); void delete( struct singly_list * ); void dis_list( void ); struct singly_list *now; init(); rintf( "init " ); dis_list(); now = insert( g_to, 'A' ); rintf( "insert g_to 'A' " ); dis_list(); now = insert( g_to, 'B' ); rintf( "insert g_to 'B' " ); dis_list(); now = insert( g_to->next, 'C' ); rintf( "insert g_to->next 'C' " ); dis_list(); now = insert( now, 'D' ); rintf( "insert now 'D' " ); dis_list(); delete( now ); rintf( "delete now " ); dis_list(); delete( g_to ); rintf( "delete g_to " ); dis_list(); /* ポインタによって指されているノードの次に新しいノードを挿入する */ /* 戻り値は 正常時 : 挿入したノードのポインタ エラー時 :NULL */ struct singly_list *insert( struct singly_list *, unsigned char value ) struct singly_list *new_node; new_node = malloc( sizeof( struct singly_list ) ); if ( new_node!= NULL ) /* 新たなノードが生成できたら */ new_node->next = ->next; /* 新たなノードからのリンクを接続する */ ->next = new_node; /* 新たなノードへリンクをつなぎ替える */ /* ポインタによって指されているノードの次のノードを削除する */ void delete( struct singly_list * ) struct singly_list *delete_node; delete_node = ->next; if ( delete_node!= NULL ) /* 削除するノードが存在したら */ ->next = delete_node->next; /* 次のノードへリンクをつなぎ替える */ free( delete_node ); /* 削除するノードをメモリから解放する */ void init( void ) /* 単方向リストの先頭のノードを生成する */ g_to = malloc( sizeof( struct singly_list ) ); if ( g_to!= NULL ) /* 新たなノードが生成できたら */ g_to->next = NULL; /* 次のノードは存在しないので NULL */ g_to->value = '.'; /* とりあえず初期値を '.' と設定 */ [8/11]
第 5 回 Page 9 void dis_list( void ) struct singly_list *dis_node; dis_node = g_to; while ( dis_node!= NULL ) rintf( "%c", dis_node->value ); dis_node = dis_node->next; rintf( "\n" ); [9/11]
第 5 回 Page 10 5-4-2. 双方向リスト操作のプログラム doubly_list.c struct doubly_list /* 双方向リストの構造体定義 */ unsigned char value; /* データ */ struct doubly_list *re; /* 前へのポインタ */ struct doubly_list *next; /* 次へのポインタ */ struct doubly_list *g_to; /* 双方向リストの先頭へのポインタ */ struct doubly_list *g_end; /* 双方向リストの末尾へのポインタ */ void init( void ); struct doubly_list *insert_next( struct doubly_list *, unsigned char value ); struct doubly_list *insert_now( struct doubly_list *, unsigned char value ); struct doubly_list *delete_now( struct doubly_list * ); void dis_list( struct doubly_list * ); #define NOW_DISP_OFFSET 27 struct doubly_list *now; init(); rintf( "init " ); dis_list(g_to); now = insert_next( g_to, 'A' ); rintf( "insert_next g_to 'A' " ); dis_list(now); now = insert_next( g_to, 'B' ); rintf( "insert_next g_to 'B' " ); dis_list(now); now = insert_next( now->next, 'C' ); rintf( "insert_next now->next 'C' " ); dis_list(now); now = insert_next( now, 'D' ); rintf( "insert_next now 'D' " ); dis_list(now); now = now->re->re; rintf( "now = now->re->re " ); dis_list(now); now = delete_now( now ); rintf( "delete_now now " ); dis_list(now); now = delete_now( now ); rintf( "delete_now now " ); dis_list(now); init(); rintf( "init " ); dis_list(g_to); now = insert_next( g_to, 'A' ); rintf( "insert_next g_to 'A' " ); dis_list(now); now = insert_now( now, 'B' ); rintf( "insert_now now 'B' " ); dis_list(now); now = insert_now( now->next, 'C' ); rintf( "insert_now now->next 'C' " ); dis_list(now); now = insert_now( now, 'D' ); rintf( "insert_now now 'D' " ); dis_list(now); now = delete_now( now ); rintf( "delete_now now " ); dis_list(now); now = delete_now( now ); rintf( "delete_now now " ); dis_list(now); /* ポインタによって指されているノード の次に新しいノードを挿入する */ /* 戻り値は 正常時 : 挿入したノードのポインタエラー時 :NULL */ struct doubly_list *insert_next( struct doubly_list *, unsigned char value ) struct doubly_list *new_node; new_node = malloc( sizeof( struct doubly_list ) ); if ( new_node!= NULL ) /* 新たなノードが生成できたら */ new_node->re = ; /* 新たなノードからのリンクを接続する */ new_node->next = ->next; /* 新たなノードからのリンクを接続する */ ->next = new_node; /* 新たなノードへリンクをつなぎ替える */ new_node->next->re = new_node; /* 新たなノードへリンクをつなぎ替える */ [10/11]
/* ポインタによって指されているノード の場所に新しいノードを挿入する */ /* 戻り値は 正常時 : 挿入したノードのポインタエラー時 :NULL */ struct doubly_list *insert_now( struct doubly_list *, unsigned char value ) struct doubly_list *new_node; 第 5 回 Page 11 new_node = malloc( sizeof( struct doubly_list ) ); if ( new_node!= NULL ) /* 新たなノードが生成できたら */ new_node->re = ->re; /* 新たなノードからのリンクを接続する */ new_node->next = ; /* 新たなノードからのリンクを接続する */ ->re->next = new_node; /* 新たなノードへリンクをつなぎ替える */ ->re = new_node; /* 新たなノードへリンクをつなぎ替える */ /* ポインタによって指されているノードを削除する */ struct doubly_list *delete_now( struct doubly_list * ) struct doubly_list *now_; if (!= NULL ) /* 削除するノードが存在したら */ ->re->next = ->next; /* 前のノードのリンクをつなぎ替える */ ->next->re = ->re; /* 次のノードのリンクをつなぎ替える */ now_ = ->next; free( ); /* 削除するノードをメモリから解放する */ return ( now_ ); void init( void ) /* 双方向リストの先頭のノードを生成する */ g_to = malloc( sizeof( struct doubly_list ) ); g_end = malloc( sizeof( struct doubly_list ) ); if ( (g_to!= NULL) && (g_end!= NULL) ) /* 新たなノードが生成できたら */ g_to->re = NULL; /* 先頭の前のノードは存在しないので NULL */ g_to->next = g_end; /* 先頭の次のノードは末尾 */ g_end->re = g_to; /* 末尾の前のノードは先頭 */ g_end->next = NULL; /* 末尾の次のノードは存在しないので NULL */ g_to->value = '.'; /* とりあえず初期値を '.' と設定 */ g_end->value = '.'; /* とりあえず初期値を '.' と設定 */ void dis_list( struct doubly_list * ) struct doubly_list *dis_node; int i; dis_node = g_to; while ( dis_node!= NULL ) rintf( "%c", dis_node->value ); dis_node = dis_node->next; rintf( "\n" ); for ( i = 0 ; i < NOW_DISP_OFFSET ; i++ ) rintf( " " ); dis_node = g_to; while ( (dis_node!= ) && (dis_node!=null) ) rintf( " " ); dis_node = dis_node->next; rintf( "^now\n" ); [11/11]