ホーム » スタッフ » 斉藤徹 » リスト構造の導入

2013年5月
« 4月   6月 »
 1234
567891011
12131415161718
19202122232425
262728293031  

最近の投稿(電子情報)

アーカイブ

カテゴリー

リスト構造の導入

先日の演習で、配列が途中データ挿入にあたり、O(N)の処理を要する問題提起を踏まえ、 今回はリスト構造を説明。

次のデータの場所

途中にデータを挿入する手間を簡単にする方法として、リスト構造を説明するために、 最初に以下のプログラムを示す。このプログラムでは、一見デタラメな数字が 並んでいるように見えるが、table[*].data部が 1,2,5,7,8 と昇順に表示される。 これは、table[*].next 部に、次に大きいデータの場所が記載されているため。

int top = 3 ;
struct DataNext {
int data ;
int next ;
} table[ 10 ] = {
5 , 1 ,
7 , 4 ,
2 , 0 ,
1 , 2 ,
8 , -1 ,
} ;
for( int i = top ; i >= 0 ; i = table[ i ].next )
printf( "%d" , table[ i ].data ) ;

このような方法を取っていれば、data に3を加えたい時は、 table[5].data = 3 ; table[5].next = 0 ; table[2].next = 5 ; を実行すれば、 データ順序を守ったまま、2と5の間に3を挿入できる。

しかし、このままでは、配列のサイズが固定値の問題を解決できない。

リスト構造

これらの問題を解決するために、必要に malloc で data と next の記憶場所を確保すれば良い。

(( まずは基本 ))
struct List {
int          data ;
struct List* next ;
} ;
struct List* top ;
top = (struct List*)malloc( sizeof(struct List) ) ;
top->data = 1 ;
top->next = (struct List*)malloc( sizeof(struct List) ) ;
top->next->data = 2 ;
top->next->next = (struct List*)malloc( sizeof(struct List) ) ;
top->next->data = 3 ;
top->next->next = NULL ;
// top ◯→[1|◯]→[2|◯]→[3|×]
struct List* p ;
for( p = top ; p != NULL ; p = p->next )
printf( "%d" , p->data ) ;
(( 補助関数を作ってシンプルに ))
struct List* cons( int x ; struct List* n ) {
struct List* nw ;
nw = (struct List*)malloc( sizeof( struct List ) ) ;
if ( nw != NULL ) {
nw->data = x ;
nw->next = n ;
}
return nw ;
}
struct List* top = cons( 1, cons( 2, cons( 3, NULL ) ) ) ;

typedef命令

時間が微妙に会ったので、補足説明として typedef を説明する。 ただし、リスト宣言を typedef で記載するのは、C言語の場合だけ。 C++では、構造体・クラス名はそのまま型名として使用できる。

(( typedef の使い方の基本 ))
// 符号なし16bit整数をいつも書くと面倒
typedef unsigned short int uint16 ;
uint16 x = 0x1234 ;
(( typedefでList宣言 ))
typedef struct LIST {
int          data ;
struct LIST* next ;
} List ;
List* cons( int x , List* n ) {
// 補助関数の宣言もシンプルに
}
List* top = cons(1,cons(2,cons(3,NULL)));